數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)第2章線性表

1、1/95數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data Structures)(C語(yǔ)言版語(yǔ)言版)Instructor: WU, RANGZHONGE-mail: 2/95第二章第二章 線性表線性表 2.1 2.1 線性表的類型定義線性表的類型定義 2.2 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 2.3 2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 2.3.1 2.3.1 線性鏈表線性鏈表 2.3.2 2.3.2 循環(huán)鏈表循環(huán)鏈表 2.3.3 2.3.3 雙向鏈表雙向鏈表 2.4 2.4 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示及相加3/95 2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 線性表線性

2、表(Linear List) (Linear List) ：由：由n(nn(n0)0)個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素( (結(jié)結(jié)點(diǎn)點(diǎn))a)a1 1，a a2 2， aan n組成的有限序列。其中數(shù)據(jù)元素的組成的有限序列。其中數(shù)據(jù)元素的個(gè)數(shù)個(gè)數(shù)n n定義為表的長(zhǎng)度。當(dāng)定義為表的長(zhǎng)度。當(dāng)n=0n=0時(shí)稱為空表，常常將時(shí)稱為空表，常常將非空的線性表非空的線性表(n0)(n0)記作：記作： (a(a1 1，a a2 2，aan n) ) 這里的數(shù)據(jù)元素這里的數(shù)據(jù)元素a ai i(1(1i in)n)只是一個(gè)抽象的符號(hào)，只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。其具體含義在不同的情況下可以不同。 例例1

3、 1、2626個(gè)英文字母組成的字母表個(gè)英文字母組成的字母表 （A A，B B，C C、Z Z） 例例2 2、某校從、某校從19781978年到年到19831983年各種型號(hào)的計(jì)算機(jī)擁有年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。量的變化情況。 （6 6，1717，2828，5050，9292，188188）4/95例例3、學(xué)生健康情況登記表如下：、學(xué)生健康情況登記表如下：姓姓 名名學(xué)學(xué) 號(hào)號(hào)性性 別別年齡年齡 健康情況健康情況王小林王小林790631 男男 18 健康健康陳陳 紅紅790632 女女 20 一般一般劉建平劉建平790633 男男 21 健康健康張立立張立立790634 男男 17 神經(jīng)

4、衰弱神經(jīng)衰弱 . . .5/95例例4 4、一副撲克的點(diǎn)數(shù)、一副撲克的點(diǎn)數(shù)（2 2，3 3，4 4，J J，Q Q，K K，A A） 從以上例子可看出線性表的邏輯特征是：從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)在非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a a1 1，它沒(méi)，它沒(méi)有直接前趨，而僅有一個(gè)直接后繼有直接前趨，而僅有一個(gè)直接后繼a a2 2；有且僅有一個(gè)終端結(jié)點(diǎn)有且僅有一個(gè)終端結(jié)點(diǎn)a an n，它沒(méi)有直接后繼，而僅，它沒(méi)有直接后繼，而僅有一個(gè)直接前趨有一個(gè)直接前趨a a n-1n-1；其余的內(nèi)部結(jié)點(diǎn)其余的內(nèi)部結(jié)點(diǎn)a ai i(2(2i in-1)n-1)都有且僅

5、有一個(gè)直接都有且僅有一個(gè)直接前趨前趨a ai-1i-1和一個(gè)直接后繼和一個(gè)直接后繼a ai+1i+1。 線性表是一種典型的線性結(jié)構(gòu)。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。抽象數(shù)據(jù)類型的定義為：抽象數(shù)據(jù)類型的定義為：P P19196/95抽象數(shù)據(jù)類型線性表的定義抽象數(shù)據(jù)類型線性表的定義ADT List數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=ai=aiElemSet，i=1，2，n，n0數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1= |ai-1 ， ai D, i=2,.,n 基本操作：基本操作：In

6、itList(&L); Destory(&L); ClearList(&L)；ListEmpty(L); ListLength(L); GetElem(L, i, &e);LocateElem(L, e, compare(); PriorElem(L, cur_e, &pre_e)NextElem(L, cur_e, &next_e); ListInsert(&L, i, e);ListDelete(&L,I,&e);7/952 The List ADTObjects: ( item0, item1, , itemN 1 )Operations: Finding the length, N,

7、of a list. Printing all the items in a list. Making an empty list. Finding the k-th item from a list, 0 k N. Inserting a new item after the k-th item of a list, 0 k N. Deleting an item from a list. Finding next of the current item from a list. Finding previous of the current item from a list. ADT:Wh

8、y after?8/95【Definition】Data Type = Objects Operations Example int = 0, 1, 2, , INT_MAX, INT_MIN , , , , , 【Definition】An Abstract Data Type (ADT) is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated fro

9、m the representation of the objects and the implementation on the operations.9/95 算法算法2.12.1 例例2-1 2-1 利用兩個(gè)線性表利用兩個(gè)線性表LALA和和LBLB分別表示兩個(gè)集合分別表示兩個(gè)集合A A和和B B，現(xiàn)要求一個(gè)新的集合，現(xiàn)要求一個(gè)新的集合A=ABA=AB。 void Union(SqList *La,SqList Lb) ElemType e; int La_len,Lb_len; int i; La_len=ListLength(*La); Lb_len=ListLength(Lb); f

10、or(i=1;i=Lb_len;i+) GetElem(Lb,i,&e); if( !LocateElem(*La, e, equal) ) ListInsert( La, +La_len, e); 10/95 算法算法2.22.2 例例2-2 2-2 巳知線性表巳知線性表LALA和線性表和線性表LBLB中的數(shù)中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將據(jù)元素按值非遞減有序排列，現(xiàn)要求將LALA和和LBLB歸并為一個(gè)新的線性表歸并為一個(gè)新的線性表LCLC，且，且LCLC中的元素仍按值非遞減有序排列。中的元素仍按值非遞減有序排列。 此問(wèn)題的算法如下：此問(wèn)題的算法如下： 11/95void merge

11、list(list la，list lb，list &lc) initlist(lc); I=j=1;k=0; la_len=listlength(la); lb_len=listlength(lb); while(I=la_len)&(j=lb_len)12/95 getelem(la，I，ai);getelem(lb，j，bj); if(ai=bj)listinsert(lc，+k，ai);+I; elselistinsert(lc，+k，bj);+j; while(I=la_len) getelem(la，I+，ai);listinsert(lc，+k，ai); while(j0n0）。

12、）。 【清華大學(xué)清華大學(xué) 1998 1998 一一.4.4（2 2分）分）】 A A表元素表元素 B B字符字符 C C數(shù)據(jù)元素?cái)?shù)據(jù)元素 D D數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) E E信息項(xiàng)信息項(xiàng)15/95 2.2 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu) 2.2.1 2.2.1 線性表線性表( (Linear List) ) 把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。表。 假設(shè)線性表的每個(gè)元素需占用假設(shè)線性表的每個(gè)元素需占用l l個(gè)存儲(chǔ)單元，并以個(gè)存儲(chǔ)單元，并以所

13、占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第置。則線性表中第i+1i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(aLOC(ai+1i+1) )和第和第i i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(aLOC(ai i) )之間滿足下列關(guān)之間滿足下列關(guān)系：系： LOC(aLOC(ai+1i+1)=LOC(a)=LOC(ai i)+l)+l 線性表的第線性表的第i i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素a ai i的存儲(chǔ)位置為：的存儲(chǔ)位置為： LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)* *l

14、l16/95 由于由于C C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表。又因?yàn)槭?，故可以用?shù)組類型來(lái)描述順序表。又因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線性表的元素之外，順序表除了用數(shù)組來(lái)存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來(lái)表示線性表的長(zhǎng)度屬性，還應(yīng)該用一個(gè)變量來(lái)表示線性表的長(zhǎng)度屬性，所以我們用結(jié)構(gòu)類型來(lái)定義順序表類型。所以我們用結(jié)構(gòu)類型來(lái)定義順序表類型。 # define ListSize 100# define ListSize 100 typedef int DataType; typedef int DataType; typedef

15、struc typedef struc DataType dataListSize; DataType dataListSize; int length; int length; Sqlist; Sqlist;17/95Simple Array implementation of Listsarray i = itemi MaxSize has to be estimated.AddressContentarray+iitemiarray+i+1itemi+1Sequential mapping Find_Kth takes O(1) time. Insertion and Deletion

16、not only take O(N) time, but also involve a lot of data movements which takes time.3/1818/95 2.2.2 2.2.2 順序表上實(shí)現(xiàn)的基本操作順序表上實(shí)現(xiàn)的基本操作 在順序表在順序表( (Sequential List) )存儲(chǔ)結(jié)構(gòu)中，很容易存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i i個(gè)元個(gè)元素的訪問(wèn)。素的訪問(wèn)。 注意：注意：C C語(yǔ)言中的數(shù)組下標(biāo)從語(yǔ)言中的數(shù)組下標(biāo)從“0”0”開始，因此，若開始，因此，若L L是是SqlistSqlist類型的順

17、序表，則表中第類型的順序表，則表中第i i個(gè)元素是個(gè)元素是L.datai-1L.datai-1。 以下主要討論線性表的插入和刪除兩種運(yùn)算。以下主要討論線性表的插入和刪除兩種運(yùn)算。 1 1、插入插入(Insert)(Insert) 線性表的插入運(yùn)算是指在表的第線性表的插入運(yùn)算是指在表的第i i個(gè)位置上，插入個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)一個(gè)新結(jié)點(diǎn)x x，19/95使長(zhǎng)度為使長(zhǎng)度為n n的線性表的線性表 (a(a1 1，a a i-1i-1，a ai i，a an n) ) 變成長(zhǎng)度為變成長(zhǎng)度為n+1n+1的線性表的線性表 (a(a1 1，a a i-1i-1，x x，a ai i，a an n) )

18、算法算法2.32.3 void InsertList(Sqlistvoid InsertList(Sqlist* *L L，DataType xDataType x，int i)int i) int j; int j; if(il.length+1) if(il.length+1) printf(“Position error”); printf(“Position error”); return ERROR return ERROR 20/95 if(L.length=ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1

19、;j=i-1;j-) L.dataj+1=L.dataj; L.datai-1=x; L.length+; 21/95 現(xiàn)在分析算法的復(fù)雜度?，F(xiàn)在分析算法的復(fù)雜度。 這里的問(wèn)題規(guī)模是表的長(zhǎng)度，設(shè)它的值為。這里的問(wèn)題規(guī)模是表的長(zhǎng)度，設(shè)它的值為。該算法的時(shí)間主要化費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句該算法的時(shí)間主要化費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，該語(yǔ)句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）上，該語(yǔ)句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）是。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依是。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。 當(dāng)時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后當(dāng)時(shí)

20、，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語(yǔ)句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜移語(yǔ)句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜度度O O（1 1）；）； 當(dāng)當(dāng)i=1i=1時(shí)，結(jié)點(diǎn)后移語(yǔ)句將循環(huán)執(zhí)行時(shí)，結(jié)點(diǎn)后移語(yǔ)句將循環(huán)執(zhí)行n n次，需移次，需移動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，其時(shí)間復(fù)雜其時(shí)間復(fù)雜度為度為O O（n n）。）。22/95 由于插入可能在表中任何位置上進(jìn)行，因此需分由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平均復(fù)雜度析算法的平均復(fù)雜度 在長(zhǎng)度為在長(zhǎng)度為n n的線性表中第的線性表中第i i個(gè)位置上插入一個(gè)結(jié)點(diǎn)，個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令令E Eisis(n)(

21、n)表示移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次表示移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次數(shù)），則在第數(shù)），則在第i i個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1n-i+1。故。故 E Eisis(n)=(n)=p pi i(n-i+1)(n-i+1) 不失一般性，假設(shè)在表中任何位置不失一般性，假設(shè)在表中任何位置(1(1i in+1)n+1)上插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則上插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則 p p1 1=p=p2 2=p=p3 3=p =p n+1n+1=1/(n+1)=1/(n+1) 因此，在等概率插入的情況下，因此，在等概率插入的情況下， E Eisis(n)=

22、(n)= (n-i+1)/(n+1)=n/2 (n-i+1)/(n+1)=n/2 23/95 也就是說(shuō)，在順序表上做插入運(yùn)算，平均要移動(dòng)也就是說(shuō)，在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng) n n較大時(shí)，算法的效率相當(dāng)較大時(shí)，算法的效率相當(dāng)?shù)?。雖然低。雖然E Eisis(n)(n)中中n n的的系數(shù)較小，但就數(shù)量級(jí)而言，的的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為O(n)O(n)。 2 2、刪除刪除(Delete)(Delete) 線性表的刪除運(yùn)算是指將表的第線性表的刪除運(yùn)算是指將表的第i(

23、1i(1i in)n)結(jié)點(diǎn)刪除，使長(zhǎng)度為結(jié)點(diǎn)刪除，使長(zhǎng)度為n n的線性表：的線性表： (a(a1 1，a a i-1i-1，a ai i，a a i+1i+1，a an n) ) 變成長(zhǎng)度為變成長(zhǎng)度為n-1n-1的線性表的線性表 (a(a1 1，a a i-1i-1，a a i+1i+1，a an n) )24/95 void deleteList(Sqlist*L，int i) int j; if(iL.length) printf(“Position error”); return ERROR for(j=i; jdata = ZHAO ;N2-data = QIAN ;N1-next =

24、 N2 ;N2-next = NULL ;ptr = N1 ;ZHAOQIANptrNULLLocations of the nodes maychange on different runs.4/1830/95 2.3.1 2.3.1 線性鏈表線性鏈表 鏈表是指用一組任意的存儲(chǔ)單元來(lái)依次存放線鏈表是指用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元即可以是連續(xù)的，也可性表的結(jié)點(diǎn)，這組存儲(chǔ)單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序

25、不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱為指針結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱為指針(pointer)(pointer)或鏈或鏈(link)(link)。這兩部分組成了鏈表中的。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)：結(jié)構(gòu)：31/95 其中：其中：datadata域域是數(shù)據(jù)域，用來(lái)存放結(jié)點(diǎn)的值。是數(shù)據(jù)域，用來(lái)存放結(jié)點(diǎn)的值。nextnext是是指針域（亦稱鏈域），用來(lái)存放結(jié)點(diǎn)的直接后指針域（亦稱鏈域），用來(lái)存放結(jié)點(diǎn)的直接后繼的

26、地址（或位置）。鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域繼的地址（或位置）。鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的將線性表的n n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。由于個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。由于上述鏈表的每一個(gè)結(jié)只有一個(gè)鏈域，故將這種鏈表稱上述鏈表的每一個(gè)結(jié)只有一個(gè)鏈域，故將這種鏈表稱為為單鏈表單鏈表（Single Linked)Single Linked)。 顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)前趨結(jié)點(diǎn)nextnext域中，而開始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指域中，而開始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針針headhead指向開始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后繼，

27、指向開始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭?，即故終端結(jié)點(diǎn)的指針域?yàn)榭?，即nullnull（圖示中也可用（圖示中也可用 表表示示) )。 例例1 1、線性表、線性表:(bat:(bat，catcat，eateat，fatfat，hathat，jatjat，latlat，mat)mat)datalink32/95單鏈表示意圖如下：?jiǎn)捂湵硎疽鈭D如下： 110 130 135 160頭指針頭指針 head 165 170 200 205 hathat200200.catcat135135eateat170170.matmatNullNullbatbat130130fatfat110

28、110jatjat205205latlat160160 16533/95 headbat cat eat mat 單鏈表是由表頭唯一確定，因此單鏈表可以用頭單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。指針的名字來(lái)命名。例如：若頭指針名是例如：若頭指針名是headhead，則把鏈表稱為表，則把鏈表稱為表headhead。用用C C語(yǔ)言描述的單鏈表如下：語(yǔ)言描述的單鏈表如下：Typedef char datatype; Typedef struct node datatype data; struct node *next;listnode;34/95 typedef listno

29、de typedef listnode * *linklist;linklist; listnode listnode * *p;p; linklist head; linklist head;注意區(qū)分指針變量和結(jié)點(diǎn)變量這兩個(gè)不同的概念。注意區(qū)分指針變量和結(jié)點(diǎn)變量這兩個(gè)不同的概念。P P為動(dòng)態(tài)變量，它是通過(guò)標(biāo)準(zhǔn)函數(shù)生成的，即為動(dòng)態(tài)變量，它是通過(guò)標(biāo)準(zhǔn)函數(shù)生成的，即 p=(listnodep=(listnode* *) )mallocmalloc(sizeof(listnode);(sizeof(listnode);函數(shù)函數(shù)mallocmalloc分配了一個(gè)類型為分配了一個(gè)類型為listnodel

30、istnode的結(jié)點(diǎn)變量的的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量空間，并將其首地址放入指針變量p p中。一旦中。一旦p p所指所指的結(jié)點(diǎn)變量不再需要了，又可通過(guò)標(biāo)準(zhǔn)函數(shù)的結(jié)點(diǎn)變量不再需要了，又可通過(guò)標(biāo)準(zhǔn)函數(shù) freefree(p)(p)釋放所指的結(jié)點(diǎn)變量空間。釋放所指的結(jié)點(diǎn)變量空間。35/95一、建立單鏈表一、建立單鏈表 假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是字符，我們逐個(gè)輸假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是字符，我們逐個(gè)輸入這些字符型的結(jié)點(diǎn)，并以換行符入這些字符型的結(jié)點(diǎn)，并以換行符n為輸入結(jié)束為輸入結(jié)束標(biāo)記。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：標(biāo)記。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種： 1、頭插法建

31、表、頭插法建表 該方法從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新該方法從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。為止。36/95 linklist createlistf(void) char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!= n) p=(listnode*)malloc(sizeof(listnode); pda

32、ta=ch; pnext=head; head=p; ch=getchar( ); return (head); 37/95 listlink createlist(int n) int data; linklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d，&pdata); pnext=head; head=p; return(head); 38/952 2、尾插法建表、尾插法建表 頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈頭插法建立鏈表雖然算法簡(jiǎn)單，但生成

33、的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針尾指針r r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例：，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例：39/95 linklist creater( ) char ch; linklist head; listnode *p，*r; head=NULL;r=NULL; while(ch=getchar( )!= n) p=(listnode *)mall

34、oc(sizeof(listnode); pdata=ch; if(head=NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); 40/95 說(shuō)明：說(shuō)明：第一個(gè)生成的結(jié)點(diǎn)是開始結(jié)點(diǎn)，將開始結(jié)點(diǎn)第一個(gè)生成的結(jié)點(diǎn)是開始結(jié)點(diǎn)，將開始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結(jié)點(diǎn)的位置是存放作處理是不一樣的，原因是開始結(jié)點(diǎn)的位置是存放在頭指針（

35、指針變量）中，在頭指針（指針變量）中，而其余結(jié)點(diǎn)的位置是在而其余結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中。算法中的第一個(gè)其前趨結(jié)點(diǎn)的指針域中。算法中的第一個(gè)ifif語(yǔ)句就語(yǔ)句就是用來(lái)對(duì)第一個(gè)位置上的插入操作做特殊處理。算是用來(lái)對(duì)第一個(gè)位置上的插入操作做特殊處理。算法中的第二個(gè)法中的第二個(gè)ifif語(yǔ)句的作用是為了分別處理空表和語(yǔ)句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個(gè)字符就是非空表兩種不同的情況，若讀入的第一個(gè)字符就是結(jié)束標(biāo)志符，則鏈表結(jié)束標(biāo)志符，則鏈表headhead是空表，尾指針是空表，尾指針r r亦為空，亦為空，結(jié)點(diǎn)結(jié)點(diǎn)* *r r不存在；否則鏈表不存在；否則鏈表head

36、head非空，最后一個(gè)尾結(jié)非空，最后一個(gè)尾結(jié)點(diǎn)點(diǎn)* *r r是終端結(jié)點(diǎn)，應(yīng)將其指針域置空。是終端結(jié)點(diǎn)，應(yīng)將其指針域置空。41/95 如果我們?cè)阪湵淼拈_始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，如果我們?cè)阪湵淼拈_始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，并稱它為頭結(jié)點(diǎn)并稱它為頭結(jié)點(diǎn)( (dummy head node ) )，那么會(huì)帶來(lái)，那么會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)：以下兩個(gè)優(yōu)點(diǎn)： a a、由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針、由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理；的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理；

37、 b b、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn) 在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨?，因在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨虼丝毡砗头强毡淼奶幚硪簿徒y(tǒng)一了。此空表和非空表的處理也就統(tǒng)一了。H(a)a1a2anH(b)42/95其算法如下：其算法如下：linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode); listnode *p，*r; r=head; while(ch=getchar( )!= n p=(listnode*)mall

38、oc(sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=NULL; return(head); 43/95上述算法里動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，上述算法里動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，可作下列處理：可作下列處理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can be obtained); return ERROR; 以上算法的時(shí)間復(fù)雜度均為以上算法的時(shí)間復(fù)雜度均為O(n)。44/95二、查找運(yùn)算二、查找運(yùn)算 1 1、按序號(hào)查找、按序號(hào)查

39、找 在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i i，也不，也不能象順序表中那樣直接按序號(hào)能象順序表中那樣直接按序號(hào)i i訪問(wèn)結(jié)點(diǎn)，而只能從訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域鏈表的頭指針出發(fā)，順鏈域nextnext逐個(gè)結(jié)點(diǎn)往下搜索，逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第直到搜索到第i i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存?zhèn)€結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。取結(jié)構(gòu)。 設(shè)單鏈表的長(zhǎng)度為設(shè)單鏈表的長(zhǎng)度為n n，要查找表中第，要查找表中第i i個(gè)結(jié)點(diǎn)，僅個(gè)結(jié)點(diǎn)，僅當(dāng)當(dāng)1 1i in n時(shí)，時(shí)，i i的值是合法的。但有時(shí)需要找頭結(jié)的值是合法的。但有時(shí)需要找頭結(jié)點(diǎn)的位置，故我們

40、將頭結(jié)點(diǎn)看做是第點(diǎn)的位置，故我們將頭結(jié)點(diǎn)看做是第0 0 個(gè)結(jié)點(diǎn)，其個(gè)結(jié)點(diǎn)，其算法如下：算法如下：45/95Listnode * getnode(linklist head ， int i) int j; listnode * p; p=head; j=0; while(pnext & jnext; j+; if (i=j) return p; else return NULL; 46/95 2 2、按值查找、按值查找 按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值值keykey的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為的結(jié)點(diǎn)，若有的話，則返回首次找到的

41、其值為keykey的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULLNULL。查找過(guò)程從開。查找過(guò)程從開始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值keykey作作比較。其算法如下：比較。其算法如下：47/95Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p & pdata!=key) p=pnext; return p; 該算法的執(zhí)行時(shí)間亦與輸入實(shí)例中的的取值該算法的執(zhí)行時(shí)間亦與輸入實(shí)例中的的取值keykey有有關(guān)，其平均時(shí)間復(fù)雜度的分析類

42、似于按序號(hào)查找，關(guān)，其平均時(shí)間復(fù)雜度的分析類似于按序號(hào)查找，也為也為O(n)O(n)。48/95三、插入運(yùn)算三、插入運(yùn)算 插入運(yùn)算是將值為插入運(yùn)算是將值為x x的新結(jié)點(diǎn)插入到表的第的新結(jié)點(diǎn)插入到表的第i i個(gè)結(jié)點(diǎn)的位置上，即插入到個(gè)結(jié)點(diǎn)的位置上，即插入到a ai-1i-1與與a ai i之間。因之間。因此，我們必須首先找到此，我們必須首先找到a ai-1i-1的存儲(chǔ)位置的存儲(chǔ)位置p p，然，然后生成一個(gè)數(shù)據(jù)域?yàn)楹笊梢粋€(gè)數(shù)據(jù)域?yàn)閤 x的新結(jié)點(diǎn)的新結(jié)點(diǎn)* *p p，并令結(jié)點(diǎn)，并令結(jié)點(diǎn)* *p p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)向結(jié)點(diǎn)a ai i。從而

43、實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)。從而實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)a ai-1i-1，x x和和a ai i之間之間的邏輯關(guān)系的變化，插入過(guò)程如：的邏輯關(guān)系的變化，插入過(guò)程如：49/95 s-next=p-next; p-next=s; pxsaianhai-1 注意：兩條語(yǔ)句的順序不能顛倒注意：兩條語(yǔ)句的順序不能顛倒，否則，否則ai的地址會(huì)的地址會(huì) 丟失。丟失。 另外，要注意合法另外，要注意合法 i 值為：值為：1i n+1 若若 in+1，則，則 i 值非法。值非法。 Question: What will happen if the order of the two steps is reversed?50/95具體算法如

44、下：具體算法如下： void insertnode(linklist head，datetype x，int i) listnode * p，*q; p=getnode(head，i-1); if(p=NULL) error(position error); q=(listnode *)malloc(sizeof(listnode); qdata=x; qnext=pnext; pnext=q; 51/95 設(shè)鏈表的長(zhǎng)度為設(shè)鏈表的長(zhǎng)度為n n，合法的插入位置是，合法的插入位置是1 1i in+1n+1。注意當(dāng)注意當(dāng)i=1i=1時(shí)，時(shí)，getnodegetnode找到的是頭結(jié)點(diǎn)，當(dāng)找到的是頭結(jié)點(diǎn)

45、，當(dāng) i=n+1i=n+1時(shí)，時(shí)，getnodegetnode找到的是結(jié)點(diǎn)找到的是結(jié)點(diǎn)a an n。因此，用。因此，用i-1i-1做做實(shí)參調(diào)用實(shí)參調(diào)用getnodegetnode時(shí)可完成插入位置的合法性檢查。時(shí)可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作算法的時(shí)間主要耗費(fèi)在查找操作getnodegetnode上，故時(shí)上，故時(shí)間復(fù)雜度亦為間復(fù)雜度亦為O(n)O(n)。四、刪除運(yùn)算四、刪除運(yùn)算 刪除運(yùn)算是將表的第刪除運(yùn)算是將表的第i i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂渹€(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)表中結(jié)點(diǎn)a ai i的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)a a a a i-1i

46、-1的指針域的指針域nextnext中，所以我們必須首先找到中，所以我們必須首先找到 52/95 a a i-1i-1的存儲(chǔ)位置的存儲(chǔ)位置p p。然后令。然后令p pnextnext指向指向a ai i的的直接后繼結(jié)點(diǎn)，即把直接后繼結(jié)點(diǎn)，即把a(bǔ) ai i從鏈上摘下。最后釋放從鏈上摘下。最后釋放結(jié)點(diǎn)結(jié)點(diǎn)a ai i的空間，將其歸還給的空間，將其歸還給“存儲(chǔ)池存儲(chǔ)池”。此過(guò)。此過(guò)程為：程為：53/95s=p-next;phai-1sp-next=p-next-next;free(s);aianai+1ai Question: How can wedelete the first node from

47、 a list?Answer: We can add a dummy head node to a list.54/95具體算法如下具體算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 55/95 設(shè)單鏈表的長(zhǎng)度為設(shè)單鏈表的長(zhǎng)度為n n，則刪去第，則刪去第i i個(gè)結(jié)點(diǎn)僅當(dāng)個(gè)結(jié)點(diǎn)僅當(dāng)1 1i in n時(shí)是合法的。注意，當(dāng)時(shí)是合法的。

48、注意，當(dāng)i=n+1i=n+1時(shí)，雖然時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨* *p p存在并存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)* *p p存在存在（即（即p!=NULLp!=NULL）且）且* *p p不是終端結(jié)點(diǎn)不是終端結(jié)點(diǎn) （即（即p pnext!=NULLnext!=NULL）時(shí)，才能確定被刪結(jié)點(diǎn)）時(shí)，才能確定被刪結(jié)點(diǎn)存在。存在。 顯然此算法的時(shí)間復(fù)雜度也是顯然此算法的時(shí)間復(fù)雜度也是O(n)O(n)。 從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和

49、從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。56/95線性表實(shí)現(xiàn)方法的比較線性表實(shí)現(xiàn)方法的比較 實(shí)現(xiàn)不同實(shí)現(xiàn)不同 順序表方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組類型，容順序表方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組類型，容易實(shí)現(xiàn)；鏈表的操作是基于指針的，相對(duì)來(lái)講復(fù)雜些。易實(shí)現(xiàn)；鏈表的操作是基于指針的，相對(duì)來(lái)講復(fù)雜些。 存儲(chǔ)空間的占用和分配不同存儲(chǔ)空間的占用和分配不同 從存儲(chǔ)的角度考慮，順序表的存儲(chǔ)空間是靜態(tài)分配的，從存儲(chǔ)的角度考慮，順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模，也就是在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)

50、規(guī)模，也就是說(shuō)事先對(duì)說(shuō)事先對(duì)“MAXSIZE”MAXSIZE”要有合適的設(shè)定，過(guò)大造成浪要有合適的設(shè)定，過(guò)大造成浪費(fèi)，過(guò)小造成溢出。而鏈表是動(dòng)態(tài)分配存儲(chǔ)空間的，費(fèi)，過(guò)小造成溢出。而鏈表是動(dòng)態(tài)分配存儲(chǔ)空間的，不用事先估計(jì)存儲(chǔ)規(guī)模?？梢?jiàn)對(duì)線性表的長(zhǎng)度或存儲(chǔ)不用事先估計(jì)存儲(chǔ)規(guī)模。可見(jiàn)對(duì)線性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，采用鏈表。規(guī)模難以估計(jì)時(shí)，采用鏈表。 線性表運(yùn)算的實(shí)現(xiàn)不同線性表運(yùn)算的實(shí)現(xiàn)不同 按序號(hào)訪問(wèn)數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。按序號(hào)訪問(wèn)數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。 插入刪除操作插入刪除操作 ，使用鏈表優(yōu)于順序表。，使用鏈表優(yōu)于順序表。 57/95 2.3.2 2.3.2 循環(huán)鏈表循環(huán)鏈表

51、( (Linked Circular Lists) ) 循環(huán)鏈表時(shí)一種頭尾相接的鏈表。其特點(diǎn)是無(wú)須循環(huán)鏈表時(shí)一種頭尾相接的鏈表。其特點(diǎn)是無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。得表處理更加方便靈活。 單循環(huán)鏈表：?jiǎn)窝h(huán)鏈表：在單鏈表中，將終端結(jié)點(diǎn)的指針在單鏈表中，將終端結(jié)點(diǎn)的指針域域NULLNULL改為指向表頭結(jié)點(diǎn)的或開始結(jié)點(diǎn)，就得到了改為指向表頭結(jié)點(diǎn)的或開始結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱為單循環(huán)鏈表。單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱為單循環(huán)鏈表。 為了使空表和非空表的處理一致，循環(huán)鏈表中為了使空表和非空表的處理

52、一致，循環(huán)鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅有一個(gè)也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅有一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。如下圖所示：自成循環(huán)的頭結(jié)點(diǎn)表示。如下圖所示：58/95 a1 an .head 非空表非空表 空表空表 在用頭指針表示的單鏈表中，找開始結(jié)點(diǎn)在用頭指針表示的單鏈表中，找開始結(jié)點(diǎn)a1的時(shí)間是的時(shí)間是O(1)，然而要找到終端結(jié)點(diǎn)，然而要找到終端結(jié)點(diǎn)an，則需，則需從頭指針開始遍歷整個(gè)鏈表，其時(shí)間是從頭指針開始遍歷整個(gè)鏈表，其時(shí)間是O(n)head59/95 在很多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位在很多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單

53、循環(huán)鏈表就顯得不夠置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便方便. .如果改用尾指針如果改用尾指針rearrear來(lái)表示單循環(huán)鏈表，則查來(lái)表示單循環(huán)鏈表，則查找開始結(jié)點(diǎn)找開始結(jié)點(diǎn)a a1 1和終端結(jié)點(diǎn)和終端結(jié)點(diǎn)a an n都很方便，它們的存儲(chǔ)位都很方便，它們的存儲(chǔ)位置分別是置分別是(rear(rearnext) nextnext) next和和rearrear，顯然，查找，顯然，查找時(shí)間都是時(shí)間都是O(1)O(1)。因此，實(shí)際中多采用尾指針表示單循。因此，實(shí)際中多采用尾指針表示單循環(huán)鏈表。環(huán)鏈表。 由于循環(huán)鏈表中沒(méi)有由于循環(huán)鏈表中沒(méi)有NULLNULL指針，故涉及遍歷操作指針，故涉及遍歷

54、操作時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷p p或或ppnextnext是否為空，而是判斷它們是否等于某一指定指是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等針，如頭指什或尾指針等. .60/95算法舉例算法舉例 單鏈表的合并單鏈表的合并 LinkedList Union(LinkedList la，LinkedList lb) 將非遞減有序的單鏈表將非遞減有序的單鏈表la和和lb合并成新的合并成新的 非遞減有序單鏈表非遞減有序單鏈表lc，并要求利用原表空間，并要求利用原表空間 lc=(LNode*)malloc(sizeof(LNod

55、e); 申請(qǐng)結(jié)點(diǎn)申請(qǐng)結(jié)點(diǎn) lc-next=NULL; 初始化鏈表初始化鏈表lc pa=la-next; pa是鏈表是鏈表la的工作指針的工作指針 pb=lb-next; pb是鏈表是鏈表lb的工作指針的工作指針 pc=lc; pc是鏈表是鏈表lc的工作指針的工作指針 while(pa & pb) la和和lb均非空均非空 if(pa-datadata) la中元素插入中元素插入lc pc-next=pa; pc=pa; pa=pa-next; 61/95 （接上頁(yè)）（接上頁(yè)） else lb中元素插入中元素插入lc pc-next=pb; pc=pb; pb=pb-next; if(pa) p

56、c-next=pa; 若若pa未到尾，將未到尾，將pc指向指向pa else pc-next=pb; 若若pb未到尾，將未到尾，將pc指向指向pbreturn(lc); Union 62/95自測(cè)題自測(cè)題 2 2 若線性表最常用的操作是存取第若線性表最常用的操作是存取第I I個(gè)元素及其前驅(qū)個(gè)元素及其前驅(qū)和后繼元素的值，為節(jié)省時(shí)間應(yīng)采用的存儲(chǔ)方式和后繼元素的值，為節(jié)省時(shí)間應(yīng)采用的存儲(chǔ)方式( )( )。 A.A.單鏈表單鏈表 B.B.雙向鏈表雙向鏈表 C.C.單循環(huán)鏈表單循環(huán)鏈表 D.D.順序表順序表【北京理工大學(xué)北京理工大學(xué)20042004一一.3(1.3(1分分) )】63/952.3.3 雙

57、向循環(huán)鏈表雙向循環(huán)鏈表Doubly Linked Circular Lists Dont we have enough headache already?Why do we need the doubly linked lists? Suppose you have a list 1-2-3-m.Now how would youget the m-th node? Ill go from the 1st nodeto the m-th node. Then you are asked to find its previous node m 1? Uhhh . Then Ill have to

58、 go from the 1st node again.But hey, why do I wantta find the previous node? Why do you ask me? :-)Maybe you wantta deletethe m-th node?typedef struct node *node_ptr ;typedef struct node node_ptr llink; element item; node_ptr rlink; ;item llinkrlinkptr = ptr-llink-rlink = ptr-rlink-llinkA doubly lin

59、ked circular list with head node:item1 item2 item3 HAn empty list : H7/1864/95 雙向鏈表雙向鏈表( (Doubly Linked Lists)Doubly Linked Lists): :在單鏈表的每在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域priorprior。這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。形式描述為：向鏈表。形式描述為： typedef struct dlistnode datatype dat

60、a; struct dlistnode *prior，*next; dlistnode; typedef dlistnode * dlinklist; dlinklist head;65/95 和單鏈表類似，雙鏈表一般也是由頭指針唯和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運(yùn)一確定的，增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)算變得方便，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。成循環(huán)鏈表，并稱之為雙向鏈表。 設(shè)指針設(shè)指針p p指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)稱性可用下式描述：