數(shù)據(jù)結(jié)構(gòu)PPT教學(xué)課件-第2章_線(xiàn)性表.ppt

第二章 線(xiàn)性表,2.1 線(xiàn)性表的類(lèi)型定義 2.2 線(xiàn)性表的順序表示和實(shí)現(xiàn) 2.3 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 2.4 一元多項(xiàng)式的表示及相加,線(xiàn)性表,線(xiàn)性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集。 線(xiàn)性結(jié)構(gòu)的特點(diǎn)： 存在唯一的一個(gè)被稱(chēng)做“第一個(gè)”的數(shù)據(jù)元素； 存在唯一的一個(gè)被稱(chēng)做“最后一個(gè)”的數(shù)據(jù)元素； 除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)； 除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。,2.1 線(xiàn)性表的類(lèi)型定義,線(xiàn)性表（liner list）：n（ 0）個(gè)數(shù)據(jù)元素的有限序列，記作（a1, ai-1, ai, ai+1, an）；其中ai是表中數(shù)據(jù)元素，n是表長(zhǎng)度。 線(xiàn)性表的特點(diǎn)： 同一線(xiàn)性表中元素具有相同特性； 相鄰數(shù)據(jù)元素之間存在序偶關(guān)系； 除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)； 除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。,線(xiàn)性表舉例： 1. 數(shù)據(jù)元素只要是同性質(zhì)就可以： 比如（a，b，z），又如（6，17，28，50，92，188） 2. 一個(gè)數(shù)據(jù)元素可以由若干項(xiàng)目（數(shù)據(jù)項(xiàng)item）組成，此時(shí)數(shù)據(jù)元素稱(chēng)為記錄（record），而含有大量記錄的線(xiàn)性表又稱(chēng)文件（file）。,線(xiàn)性表定義演示,結(jié)論： 線(xiàn)性表中的數(shù)據(jù)元素可以是各種各樣的，但同一線(xiàn)性表（a1, ai-1, ai, ai+1, an）中所有元素具有相同特性，即屬同一數(shù)據(jù)對(duì)象。 任意兩相鄰元素ai-1和 ai之間存在序偶關(guān)系；其中稱(chēng)ai-1為ai的直接前驅(qū)，而ai為ai-1的直接后繼。當(dāng)i=1,2,n-1時(shí)，ai有且僅有一個(gè)直接后繼，當(dāng)i=2,3,n時(shí)，ai有且僅有一個(gè)直接前驅(qū)。 線(xiàn)性表中元素的個(gè)數(shù)n定義為線(xiàn)性表的長(zhǎng)度，n=0時(shí)稱(chēng)為空表。 在非空線(xiàn)性表中，任意一個(gè)元素ai是表的第i個(gè)元素，i稱(chēng)為數(shù)據(jù)元素在線(xiàn)性表中的位序。,線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義以及基本操作,數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。 抽象數(shù)據(jù)類(lèi)型線(xiàn)性表的定義如下： adt list 數(shù)據(jù)對(duì)象：d= ai|aielemset，i=1,2,n, n0 數(shù)據(jù)關(guān)系：r1= | ai-1， ai di，i=2,n 基本操作：,線(xiàn)性表的基本操作（一）,initlist(&l) 操作結(jié)果：構(gòu)造一個(gè)空的線(xiàn)性表l。 destroylist(&l) 初始條件：線(xiàn)性表l已存在。 操作結(jié)果：銷(xiāo)毀線(xiàn)性表。,線(xiàn)性表的基本操作（二）,cleanlist(&l) 初始條件：線(xiàn)性表l已存在。 操作結(jié)果：將l重置為空表。 listempty(&l) 初始條件：線(xiàn)性表l已存在。 操作結(jié)果：若l為空表，則返回true，否則返回false。,線(xiàn)性表的基本操作（三）,listlength(l) 初始條件：線(xiàn)性表l已存在。 操作結(jié)果：返回l中數(shù)據(jù)元素個(gè)數(shù)。 getelem(l, i, &e) 初始條件：線(xiàn)性表l已存在，1i listlength(l)。 操作結(jié)果：用e返回l中第i個(gè)數(shù)據(jù)元素的值。,線(xiàn)性表的基本操作（四）,locateelem(l, e, compare() 初始條件：線(xiàn)性表l已存在， compare()是數(shù)據(jù)元素判定函數(shù)。 操作結(jié)果：返回l中第1個(gè)與e滿(mǎn)足關(guān)系compare()的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在，則返回值為0。 priorelem(l, cur_e, &pre_e) 初始條件：線(xiàn)性表l已存在。 操作結(jié)果：若cur _e是l的數(shù)據(jù)元素，且不是第一個(gè)，則用pre _e返回它的前驅(qū)，否則操作失敗， pre _e無(wú)定義。,線(xiàn)性表的基本操作（五）,nextelem(l, cur_e, &next_e) 初始條件：線(xiàn)性表l已存在。 操作結(jié)果：若cur_e是l的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗， next_e無(wú)定義。 listinsert(&l, i, e) 初始條件：線(xiàn)性表l已存在， 1i listlength(l)+1。 操作結(jié)果：在l中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，l的長(zhǎng)度加1。,線(xiàn)性表的基本操作（六）,listdelete(&l, i, &e) 初始條件：線(xiàn)性表l已存在且非空， 1i listlength(l)。 操作結(jié)果：刪除l的第i個(gè)數(shù)據(jù)元素，并用e返回其值，l的長(zhǎng)度減1。 listtraverse( l, visit() ) 初始條件：線(xiàn)性表l已存在。 操作結(jié)果：依次對(duì)l的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit() 。一旦visit()失敗，則操作失敗。,線(xiàn)性表基本操作演示,例2-1：假設(shè)利用兩個(gè)線(xiàn)性表la和lb分別表示兩個(gè)集合a和b（即：線(xiàn)性表中的數(shù)據(jù)元素即為集合中的成員），先要求一個(gè)新的集合a=ab。 要求對(duì)線(xiàn)性表做如下操作： 擴(kuò)大線(xiàn)性表la； 將存在于線(xiàn)性表lb中而不存在于la中的數(shù)據(jù)元素插入到線(xiàn)性表la中去。,集合：a = 5, 17, -3, 36 ,集合：b = 25, 17, -3, 54, 13, 88 ,集合：ab = 5, 25, 17, -3, 36, 54, 13, 88 ,需要做：擴(kuò)大線(xiàn)性表la，將存在于線(xiàn)性表lb中而不存在于線(xiàn)性表la中的數(shù)據(jù)元素插入到線(xiàn)性表la中。 解決方法：只要從線(xiàn)性表lb中依次取得每個(gè)數(shù)據(jù)元素，并依值在線(xiàn)性表la中進(jìn)行查訪，若不存在，則插入la。,基本操作： 1、從線(xiàn)性表lb中依次取得每個(gè)數(shù)據(jù)元素; getelem(lb, i) e 2、依值在線(xiàn)性表la中進(jìn)行查訪; locateelem(la, e, equal( ) 3、若不存在，則插入la。 listinsert(la, n+1, e),void union(list ,算法2.1,算法的復(fù)雜度分析,上述算法的時(shí)間復(fù)雜度取決于抽象數(shù)據(jù)類(lèi)型list定義中基本操作的執(zhí)行時(shí)間。 假如getelem和listinsert這兩個(gè)操作的執(zhí)行時(shí)間與表長(zhǎng)無(wú)關(guān)，locateelem的執(zhí)行時(shí)間和表長(zhǎng)成正比，則算法2.1的時(shí)間復(fù)雜度為： o(listlength(la)listlength(lb),例2-2：已知線(xiàn)性表la和lb中的數(shù)據(jù)元素按值非遞減有序排列，先要求將la和lb歸并為一個(gè)新的線(xiàn)性表lc，且lc中的元素仍舊按值非遞減有序排列。 要求對(duì)線(xiàn)性表做如下操作： 建立空表lc； 將la或者lb中的元素逐個(gè)插入到lc中即可； 同時(shí)要保證lc的有序性。,線(xiàn)性表：la = ( -3, 17, 25, 36 ),線(xiàn)性表：lb = ( 27, 33, 54, 63, 88 ),線(xiàn)性表：lc = ( -3, 17, 25, 27, 33, 36, 54, 63, 88 ),lc中的數(shù)據(jù)元素或是la中的數(shù)據(jù)元素，或是lb中的數(shù)據(jù)元素，只要先設(shè)lc為空表，然后將la或lb中的元素逐個(gè)插入到lc中即可。 為使lc中元素按值非遞減有序排列，可設(shè)兩個(gè)指針i和j分別指向la和lb中某個(gè)元素，若設(shè)i當(dāng)前所指的元素為a，j當(dāng)前所指的元素為b，則當(dāng)前應(yīng)插入到lc中的元素min(a,b)。 顯然，指針i和j的初值均為1，在所指元素插入lc之后，在la或lb中順序后移。,線(xiàn)性表：la = ( -3, 17, 25, 36 ),線(xiàn)性表：lb = ( 27, 33, 54, 63, 88 ),線(xiàn)性表：lc = ( -3, 17, 25, 27, 33, 36, 54, 63, 88 ),基本操作步驟,設(shè)：la = (a1, , ai, , an)，lb = (b1, , bj, , bm) ， lc = (c1, , ck, , cm+n) 且已由(a1, , ai-1)和(b1, ,bj-1)歸并得 (c1, , ck-1) 則 k = 1, 2, , m+n。,具體步驟： 1、分別從la和lb中取得當(dāng)前元素ai和bj； 2、若aibj，則將ai插入到lc中，否則將bj插入到lc中。 3、將 la表或 lb 表中剩余元素復(fù)制插入到lc表中。,void mergelist(list la，list lb，list /求取lb的長(zhǎng)度 while(i=la-len)&(j=lb-len) /取la和lb兩表中當(dāng)前所考慮兩元素ai和bj中較小者放入lc中；同時(shí)，當(dāng)la或者lb已考察完時(shí)，循環(huán)結(jié)束。,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) /如果la中仍有元素沒(méi)有合并到lc中 /將這些元素依次插入到lc的尾部 getelem(la，i+，ai);listinsert(lc，+k，ai); while(j=lb-len) /如果lb中仍有元素沒(méi)有合并到lc中 /將這些元素依次插入到lc的尾部 getelem(lb，j+，bj);listinsert(lc，+k，bj); /此時(shí)，新表lc不僅僅包含la和lb中的所有元素，且lc中的數(shù)據(jù)元素按值非遞減有序,算法2.2,算法的復(fù)雜度分析,上述算法的時(shí)間復(fù)雜度取決于抽象數(shù)據(jù)類(lèi)型list定義中基本操作的執(zhí)行時(shí)間。 雖然算法2.2中含3個(gè)while循環(huán)語(yǔ)句，但只有當(dāng)i和j均指向表中實(shí)際存在的數(shù)據(jù)元素時(shí)，才能取得數(shù)據(jù)元素的值并進(jìn)行相互比較；并且當(dāng)其中一個(gè)線(xiàn)性表的數(shù)據(jù)元素均已插入到線(xiàn)性表lc中后，只要將另外一個(gè)線(xiàn)性表中的剩余元素依次插入即可。因此，對(duì)于每一組具體的輸入（la和lb），后兩個(gè)while循環(huán)語(yǔ)句只執(zhí)行一個(gè)循環(huán)體。 算法2.2的時(shí)間復(fù)雜度為 o(listlength(la) + listlength(lb),2.2 線(xiàn)性表的順序表示和實(shí)現(xiàn),把線(xiàn)性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線(xiàn)性表簡(jiǎn)稱(chēng)順序表。 假設(shè)線(xiàn)性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。 則線(xiàn)性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置loc(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置loc(ai )之間滿(mǎn)足下列關(guān)系： loc(ai+1) = loc(ai) + l 線(xiàn)性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為： loc(ai) = loc(a1) + (i-1) * l,loc(a i+1) = loc( a i )+l loc(a i) = loc(a1)+(i-1)*l,每一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置都和線(xiàn)性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線(xiàn)性表中的位序成正比的常數(shù)。,順序表的特點(diǎn),線(xiàn)性表的這種機(jī)內(nèi)表示稱(chēng)作線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)或順序映象（sequential mapping），稱(chēng)這種存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表為順序表。 特點(diǎn)：為表中相鄰的元素ai和ai+1賦以相鄰的存儲(chǔ)位置loc(ai)和loc(ai+1)。 換句話(huà)說(shuō)，以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線(xiàn)性表中數(shù)據(jù)元素之間的邏輯關(guān)系。 每一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置都和線(xiàn)性表的起始位置相差一個(gè)與數(shù)據(jù)元素在線(xiàn)性表中的位序成正比的常數(shù)。,順序表的特點(diǎn),只要確定了存儲(chǔ)線(xiàn)性表的起始位置，線(xiàn)性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。 所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置：loc(ai) = loc(a1) + (i-1)l 式中l(wèi)oc(a1)是線(xiàn)性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱(chēng)做線(xiàn)性表的起始位置或基地址。,順序表定義演示,由于c語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類(lèi)型來(lái)描述順序表。 又因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線(xiàn)性表的元素之外，順序表還應(yīng)該用一個(gè)變量來(lái)表示線(xiàn)性表的長(zhǎng)度屬性，所以我們用結(jié)構(gòu)類(lèi)型來(lái)定義順序表類(lèi)型。 # define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一維數(shù)組表示順序表 int length; /length表示數(shù)組中實(shí)際元素個(gè)數(shù)，即順序表的實(shí)際長(zhǎng)度 /listsize表示數(shù)組的最大容量，即順序表的最大長(zhǎng)度 sqlist;,# define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一維數(shù)組表示順序表 int length; /length表示數(shù)組中實(shí)際元素個(gè)數(shù)，即順序表的實(shí)際長(zhǎng)度 /listsize表示數(shù)組的最大容量，即順序表的最大長(zhǎng)度 sqlist;, 存放線(xiàn)性表結(jié)點(diǎn)的向量空間的大小listsize應(yīng)仔細(xì)選值，使其既能滿(mǎn)足表結(jié)點(diǎn)的數(shù)目動(dòng)態(tài)增加的需求，又不致于預(yù)先定義過(guò)大而浪費(fèi)存儲(chǔ)空間。,需要注意,# define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一維數(shù)組表示順序表 int length; /length表示數(shù)組中實(shí)際元素個(gè)數(shù)，即順序表的實(shí)際長(zhǎng)度 /listsize表示數(shù)組的最大容量，即順序表的最大長(zhǎng)度 sqlist;, 由于c語(yǔ)言中向量的下標(biāo)從0開(kāi)始，所以若l是sqlist類(lèi)型的順序表，則線(xiàn)性表的開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an分別存儲(chǔ)在l.data0和l.datal.length-1中。,# define listsize 100 typedef int datatype; typedef struc datatype datalistsize; /用一維數(shù)組表示順序表 int length; /length表示數(shù)組中實(shí)際元素個(gè)數(shù)，即順序表的實(shí)際長(zhǎng)度 /listsize表示數(shù)組的最大容量，即順序表的最大長(zhǎng)度 sqlist;, 若l是sqlist類(lèi)型的指針變量，則a1和an分別存儲(chǔ)在l-data0和l-datal-length-1中。,高級(jí)程序設(shè)計(jì)語(yǔ)言中的數(shù)組也有隨機(jī)存取的特性； 同時(shí)，由于線(xiàn)性表的長(zhǎng)度可變，且所需最大存儲(chǔ)空間隨問(wèn)題不同而不同，則在c語(yǔ)言中可用動(dòng)態(tài)分配的一維數(shù)組，如下： #define list_init_size 100 /順序表的初始分配量 #define listincrement 10 /順序表的分配增量 typedef struct elemtype *elem; /存儲(chǔ)空間基址：即數(shù)組的起始地址 int length; /順序表的當(dāng)前長(zhǎng)度：實(shí)際的元素個(gè)數(shù) int listsize; /當(dāng)前分配的存儲(chǔ)容量（以sizeof（elemtype）為單位） sqlist;,線(xiàn)性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu),線(xiàn)性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)的初始化,status initlist_sq( sqlist /順利完成初始化 ,順序表的基本操作：按值查找,按值查找：找x在表中的位置，若查找成功，返回表項(xiàng)的位置，否則返回-1： int find( sqlist ,求表的長(zhǎng)度 int length( seqlist ,在順序表存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線(xiàn)性表的一些操作，如：線(xiàn)性表的構(gòu)造、第i個(gè)元素的訪問(wèn)。 注意：c語(yǔ)言中的數(shù)組下標(biāo)從“0”開(kāi)始，因此，若l是sqlist類(lèi)型的順序表，則表中第i個(gè)元素是l.elemi-1。 以下主要討論線(xiàn)性表的插入和刪除兩種運(yùn)算：,線(xiàn)性表的插入運(yùn)算：在表的第i(1in+1)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線(xiàn)性表 (a1，ai-1，ai，an) 變成長(zhǎng)度為n+1的線(xiàn)性表 (a1，ai-1，x，ai，an),插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,在第i（1in）個(gè)元素之前插一個(gè)元素時(shí)： 需將第n至第i（共n-i+1）個(gè)元素向后移動(dòng)一個(gè)位置，依次后移到n+1,n,i+1位置上，空出第i個(gè)位置； 在該位置上插入新結(jié)點(diǎn)e。,插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,注意： 由于向量空間大小在聲明時(shí)確定，當(dāng)l.lengthlistsize時(shí)，表空間已滿(mǎn)，不可再做插入操作； 當(dāng)插入位置i的值為in或i1時(shí)為非法位置，不可做正常插入操作。,插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,順序表插入時(shí)，平均數(shù)據(jù)移動(dòng)次數(shù)amn在各表項(xiàng) 插入概率相等時(shí),線(xiàn)性表的結(jié)構(gòu)定義： -線(xiàn)性表的動(dòng)態(tài)分配存儲(chǔ)結(jié)構(gòu)- #define list_init_size 100 /順序表的初始分配量 #define listincrement 10 /順序表的分配增量 typedef struct elemtype *elem; /存儲(chǔ)空間基址：即數(shù)組的起始地址 int length; /順序表的當(dāng)前長(zhǎng)度：實(shí)際的元素個(gè)數(shù) int listsize; /當(dāng)前分配的存儲(chǔ)容量（以sizeof（elemtype）為單位） sqlist;,線(xiàn)性表的初始化（算法2.3） status initlist_sq( sqlist /initlist_sq,順序表的插入（算法2.4） status insertlist_sq(sqlist /線(xiàn)性表長(zhǎng)度增加 ,q = /返回插入成功標(biāo)志“ok” /listinsert_sq,注意：元素位序與數(shù)組下標(biāo)的關(guān)系。,插入操作演示,線(xiàn)性表的刪除運(yùn)算是指將表的第i(1in)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線(xiàn)性表： (a1，ai-1，ai，ai+1，an) 變成長(zhǎng)度為n-1的線(xiàn)性表 (a1，ai-1，ai+1，an),需將第i+1至第n共（n-i)個(gè)元素前移。 注意：當(dāng)要?jiǎng)h除元素的位置i不在表長(zhǎng)范圍（即i1或il.length）時(shí)，為非法位置，不能做正常的刪除操作。,刪除,25 34 57 50 16 48 09 63 ,16,刪除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,在順序表上實(shí)現(xiàn)刪除運(yùn)算必須移動(dòng)結(jié)點(diǎn)，才能反映出結(jié)點(diǎn)間的邏輯關(guān)系的變化。 若i=n，則只要簡(jiǎn)單地刪除終端結(jié)點(diǎn)，無(wú)須移動(dòng)結(jié)點(diǎn)； 若1in-1，則必須將表中位置i+1,i+2,n的結(jié)點(diǎn)，依次前移到位置i,i+1,n-1上，以填補(bǔ)刪除操作造成的空缺。,刪除,25 34 57 50 16 48 09 63 ,16,刪除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,順序表刪除平均數(shù)據(jù)移動(dòng)次數(shù)amn在各表項(xiàng) 刪除概率相等時(shí),順序表的刪除（算法2.5） status listdelete_sq ( sqlist /返回刪除元素成功標(biāo)志 ,刪除操作演示,總結(jié),當(dāng)在順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中某個(gè)位置上插入或刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)元素上（換句話(huà)說(shuō)，移動(dòng)元素的操作為預(yù)估算法時(shí)間復(fù)雜度的基本操作），而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。 所以在順序表中插入或刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)n很大時(shí)，效率很低。,順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn),優(yōu)點(diǎn)： 邏輯相鄰，物理相鄰 可隨機(jī)存取任一元素 存儲(chǔ)空間使用緊湊 缺點(diǎn)： 插入、刪除操作需要移動(dòng)大量的元素 預(yù)先分配空間需按最大空間分配，利用不充分 表容量難以擴(kuò)充,2.3 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn),順序存儲(chǔ)的弱點(diǎn)：在作插入或刪除操作時(shí)，需移動(dòng)大量元素。 順序存儲(chǔ)的優(yōu)點(diǎn)：隨機(jī)存取。 線(xiàn)性表的另一種表示方法：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 不要求邏輯上相鄰的元素在物理位置上也相鄰； 同時(shí)失去了可隨機(jī)存取的優(yōu)點(diǎn)。,2.3.1 線(xiàn)性鏈表,鏈表是指用一組任意的存儲(chǔ)單元來(lái)依次存放線(xiàn)性表的結(jié)點(diǎn)； 這組存儲(chǔ)單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同； 為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素來(lái)說(shuō)除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。,兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映象，稱(chēng)為結(jié)點(diǎn)（node）。,為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱(chēng)為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)：,data域是數(shù)據(jù)域，用來(lái)存放結(jié)點(diǎn)的值。 next是指針域（亦稱(chēng)鏈域），用來(lái)存放結(jié)點(diǎn)的直接后繼的地址（或位置）。鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€(xiàn)性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。由于上述鏈表的每一個(gè)結(jié)只有一個(gè)鏈域，故將這種鏈表稱(chēng)為單鏈表（single linked)。,n個(gè)結(jié)點(diǎn)鏈結(jié)長(zhǎng)一個(gè)鏈表，即為線(xiàn)性表(a1，ai-1，ai，ai+1，an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 又由于此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱(chēng)線(xiàn)性鏈表或單鏈表。 例如：線(xiàn)性表（zhao,qian,sun,li,zhou,wu,zheng,wang）的線(xiàn)性鏈表存儲(chǔ)結(jié)構(gòu)。,頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)（即第一個(gè)數(shù)據(jù)元素的存儲(chǔ)映象）的存儲(chǔ)位置。 同時(shí)，由于最后一個(gè)數(shù)據(jù)元素沒(méi)有直接后繼，則線(xiàn)性鏈表中最后一個(gè)結(jié)點(diǎn)的指針為“空”（null）。,單鏈表：這個(gè)鏈表的存取從頭指針開(kāi)始。,單鏈表的物理（存儲(chǔ)）結(jié)構(gòu),單鏈表：這個(gè)鏈表的存取從頭指針開(kāi)始。,單鏈表的邏輯結(jié)構(gòu),線(xiàn)性表（zhao,qian,sun,li,zhou,wu,zheng,wang）的線(xiàn)性鏈表存儲(chǔ)結(jié)構(gòu)。,再例：線(xiàn)性表(bat, cat, eat, fat, hat, iat, lat, mat) 顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開(kāi)始結(jié)點(diǎn)（根結(jié)點(diǎn)）無(wú)前趨，故應(yīng)設(shè)頭指針head指向開(kāi)始結(jié)點(diǎn)。 同時(shí)，由于終端結(jié)點(diǎn)（葉子結(jié)點(diǎn)）無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨磏ull（圖示中也可用表示)。 單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。例如：若頭指針名是head，則把鏈表稱(chēng)為表head。,單鏈表和指針,線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn),/-線(xiàn)性單鏈表存儲(chǔ)結(jié)構(gòu)- typedef struct lnode elemtype data; /數(shù)據(jù)域 struct lnode *next; /指針域 lnode, *linklist; / lnode應(yīng)該為線(xiàn)性單鏈表的結(jié)點(diǎn) / *linklist應(yīng)該為指向線(xiàn)性單鏈表結(jié)點(diǎn)的指針,非空的線(xiàn)性單鏈表和空的線(xiàn)性單鏈表。 假設(shè)l是linklist型的變量，則l為單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)； 若l為“空”（l=null），則所以表示的線(xiàn)性表為“空”表，其長(zhǎng)度n為“零”。 有時(shí)，我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱(chēng)之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可存儲(chǔ)如線(xiàn)性表的長(zhǎng)度等類(lèi)的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針（即第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置：地址）。,空表的單鏈表,typedef lnode *linklist; lnode *p; linklist head;,注意：區(qū)分指針變量（p以及head）和結(jié)點(diǎn)變量（*p）這兩個(gè)不同的概念： 指針變量p：其值為結(jié)點(diǎn)地址； 結(jié)點(diǎn)變量*p：其值為結(jié)點(diǎn)內(nèi)容。 linklist和lnode *是不同名字的同一個(gè)指針類(lèi)型（命名的不同是為了概念上更明確）： linklist類(lèi)型的指針變量head表示它是單鏈表的頭指針； lnode *類(lèi)型的指針變量p表示它是指向某一結(jié)點(diǎn)的指針。,typedef struct lnode elemtype data; struct lnode *next; lnode, *linklist;,指針變量p和結(jié)點(diǎn)變量*p,(*p)表示p所指向的結(jié)點(diǎn)： (*p).data，即p-data，表示p指向結(jié)點(diǎn)的數(shù)據(jù)域； (*p).next，即p-next，表示p指向結(jié)點(diǎn)的指針域。,typedef lnode *linklist; lnode *p; linklist head; p為動(dòng)態(tài)變量，它是通過(guò)標(biāo)準(zhǔn)函數(shù)生成的，即 p=( lnode * )malloc( sizeof( lnode ) ); 函數(shù)malloc分配了一個(gè)類(lèi)型為lnode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。 一旦p所指的結(jié)點(diǎn)變量不再需要了，又可通過(guò)標(biāo)準(zhǔn)函數(shù)free(p)釋放所指的結(jié)點(diǎn)變量空間。,typedef struct lnode elemtype data; struct lnode *next; lnode, *linklist;,typedef lnode *linklist; lnode *p; linklist head; 結(jié)點(diǎn)分量的訪問(wèn)：利用結(jié)點(diǎn)變量的名字*p訪問(wèn)結(jié)點(diǎn)分量 方法一：(*p).data和(*p).next 方法二：p-data和p-next 指針變量p和結(jié)點(diǎn)變量*p的關(guān)系： 指針變量p的值結(jié)點(diǎn)地址 結(jié)點(diǎn)變量*p的值結(jié)點(diǎn)內(nèi)容 (*p).data的值p指針?biāo)附Y(jié)點(diǎn)的data域的值 (*p).next的值*p的直接后繼結(jié)點(diǎn)的地址 *(*p).next) *p的直接后繼結(jié)點(diǎn),typedef struct lnode elemtype data; struct lnode *next; lnode, *linklist;,注意：若指針變量p的值為空（null），則它不指向任何結(jié)點(diǎn)。此時(shí)，若通過(guò)*p來(lái)訪問(wèn)結(jié)點(diǎn)就意味著訪問(wèn)一個(gè)不存在的變量，從而引起程序的錯(cuò)誤。,指針變量p和結(jié)點(diǎn)變量*p,線(xiàn)性鏈表的特性,對(duì)于順序表，邏輯上相鄰的兩個(gè)元素在物理位置上緊鄰，則每個(gè)元素的存儲(chǔ)位置都可從線(xiàn)性表的起始位置計(jì)算得到； 對(duì)于單鏈表，任何兩個(gè)元素的存儲(chǔ)位置之間沒(méi)有固定的聯(lián)系； 但是，在單鏈表中，每個(gè)元素的存儲(chǔ)位置都包含在其直接前驅(qū)結(jié)點(diǎn)的信息之中。（指針域） 如果p-data = ai, p-next-data = ai+1； 因此，在單鏈表中，取得第i個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找，因此，單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。,帶頭結(jié)點(diǎn)的線(xiàn)性單鏈表,頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)（首結(jié)點(diǎn)）前附設(shè)一個(gè)結(jié)點(diǎn)叫頭結(jié)點(diǎn)。 頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€(xiàn)性表為空。,從線(xiàn)性單鏈表中取第i個(gè)數(shù)據(jù)元素（算法2.8）,status getelem_l ( linklist l, int i, elemtype /取值成功，結(jié)束操作并返回取值成功標(biāo)志。 /getelem_l,指針的基本操作演示,線(xiàn)性單鏈表的插入與刪除操作,在一個(gè)帶頭結(jié)點(diǎn)的線(xiàn)性單鏈表l中插入一個(gè)新結(jié)點(diǎn)，其結(jié)點(diǎn)值為e，而其插入位置在原鏈表結(jié)點(diǎn)a和結(jié)點(diǎn)b之間。其中結(jié)點(diǎn)a由指針p指向。,插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1（a結(jié)點(diǎn)）與ai（b結(jié)點(diǎn)）之間。（如前例） 因此，我們必須首先找到ai-1的存儲(chǔ)位置p，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*s，并令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化，插入過(guò)程如下：,s=(listnode *)malloc(sizeof(listnode); sdata=e; snext=pnext; pnext=s;,(a1，ai-1，ai，ai+1，an),算法2.9 status listinsert_l(linklist l，int i，elemtype e) /在帶頭結(jié)點(diǎn)的單鏈表l中第i個(gè)位置之前插入元素。 p = l；j = 0； while( p /插入成功。 /listinsert_l,單鏈表結(jié)點(diǎn)插入演示,不帶頭結(jié)點(diǎn)的單鏈表的插入操作如何完成？,在帶頭結(jié)點(diǎn)的線(xiàn)性鏈表中刪除元素b，為了在單鏈表中實(shí)現(xiàn)元素a、b和c之間邏輯關(guān)系的變化，僅需修改結(jié)點(diǎn)a中的指針域即可。,刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。 因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以我們必須首先找到ai-1的存儲(chǔ)位置p； 然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下； 最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。此過(guò)程為： (a1，ai-1，ai，ai+1，an) 變成：(a1，ai-1，ai+1，an)。,算法2.10 status listdelete _l( linklist l， int i，elemtype /釋放結(jié)點(diǎn)的存儲(chǔ)空間。 ,單鏈表結(jié)點(diǎn)刪除演示,不帶頭結(jié)點(diǎn)的單鏈表的刪除操作如何完成？,線(xiàn)性鏈表的兩個(gè)基本操作的時(shí)間復(fù)雜度分析,設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1in+1。 注意當(dāng)i=1時(shí)，是頭結(jié)點(diǎn)，當(dāng) i=n+1時(shí)，是結(jié)點(diǎn)an。 因此，用i-1做可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作上，故時(shí)間復(fù)雜度亦為o(n)。,線(xiàn)性鏈表的兩個(gè)基本操作的時(shí)間復(fù)雜度分析,設(shè)單鏈表的長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1in時(shí)是合法的。 注意，當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。 因此被刪結(jié)點(diǎn)的直接前趨*p存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)*p存在（即p!=null）且*p不是終端結(jié)點(diǎn)（即pnext!=null）時(shí)，才能確定被刪結(jié)點(diǎn)存在。 顯然此算法的時(shí)間復(fù)雜度也是o(n)。,線(xiàn)性鏈表的兩個(gè)基本操作的時(shí)間復(fù)雜度分析,結(jié)論：鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。,線(xiàn)性單鏈表的生成,單鏈表和順序存儲(chǔ)結(jié)構(gòu)不同，它是一種動(dòng)態(tài)結(jié)構(gòu)。整個(gè)可用存儲(chǔ)空間可為多個(gè)鏈表共同享用，每個(gè)鏈表占用的空間不需預(yù)先分配劃定，而是可以由系統(tǒng)應(yīng)需求即時(shí)生成。 建立線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過(guò)程就是一個(gè)動(dòng)態(tài)生成鏈表的過(guò)程。即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。 創(chuàng)建單鏈表方法有兩種，假設(shè)線(xiàn)性表中結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型是字符型，逐個(gè)輸入這些字符型的結(jié)點(diǎn)數(shù)據(jù)，并以換行符n為輸入條件結(jié)束標(biāo)志符，動(dòng)態(tài)地建立單鏈表。,(1) 尾插法建表,算法思路：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，直到讀入結(jié)束標(biāo)志為止。 注意： 采用尾插法建表，生成鏈表結(jié)點(diǎn)的次序與輸入順序一致； 必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。,尾插入法建立線(xiàn)性單鏈表,linklist creatlistr(void) /返回單鏈表的頭指針 char ch; linklist head; /頭指針 listnode *s,*r; /工作指針 head=null; /鏈表開(kāi)始為空 r=null; /尾指針初值為空 ch=getchar(); /讀入第1個(gè)字符 while(ch!=n) s=(listnode*)malloc (sizeof(listnode); /生成新結(jié)點(diǎn) s-data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中,if (head= =null) head=s; /新結(jié)點(diǎn)插入空表 else r-next=s; /將新結(jié)點(diǎn)插到*r之后 r=s; /尾指針指向新表尾 ch=getchar(); /讀入下一字符 /endwhile if (r!=null) r-next=null; /對(duì)于非空表，將尾結(jié)點(diǎn)指針域置空 return head; / 算法2.11,算法時(shí)間復(fù)雜度為：o(listlength(l),說(shuō)明：第一個(gè)生成的結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，將開(kāi)始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開(kāi)始結(jié)點(diǎn)的位置是存放在頭指針（指針變量）中，而其余結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中。 算法中的第一個(gè)if語(yǔ)句是用來(lái)對(duì)第一個(gè)位置上的插入操作做特殊處理。 第二個(gè)if語(yǔ)句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個(gè)字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點(diǎn)*r不存在； 否則鏈表head非空，最后一個(gè)尾結(jié)點(diǎn)*r是終端結(jié)點(diǎn)，應(yīng)將其指針域置空。,如果在鏈表的開(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，并稱(chēng)它為頭結(jié)點(diǎn)，則會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)： 由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理； 無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)所在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨虼丝毡砗头强毡淼奶幚硪簿徒y(tǒng)一了。,帶頭結(jié)點(diǎn)尾插法創(chuàng)建單鏈表算法,linklist creatlistr1(void) /用尾插法建立帶頭結(jié)點(diǎn)的單鏈表 char ch; linklist head=(listnode*) malloc (sizeof(listnode); /生成頭結(jié)點(diǎn) listnode *s,*r; /工作指針 r=head; / 尾指針初值也指向頭結(jié)點(diǎn),while (ch=getchar()!=n) s=(listnode*) malloc (sizeof(listnode); /生成新結(jié)點(diǎn) s-data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中 r-next=s; r=s; r-next=null; /終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空 return head; ,算法的時(shí)間復(fù)雜度為o(listlength(l),(2) 頭插法建表,算法思路：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。 注意：該方法生成鏈表的結(jié)點(diǎn)次序與輸入順序相反。,頭插入法建表演示,線(xiàn)性單鏈表的元素查找,（1）按序號(hào)查找 在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能象順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。 設(shè)單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1in時(shí)，i的值是合法的。但有時(shí)需要找頭結(jié)點(diǎn)的位置，將頭結(jié)點(diǎn)看做是第0 個(gè)結(jié)點(diǎn)，其算法如下：,lnode *getnode (linklist head, int i) int j; lnode *p; p=head; j=0; while (pnext /找不到第i個(gè)結(jié)點(diǎn) ,（2）按值查找 按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)， 若有的話(huà)，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)位置； 否則返回null。 查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。其算法如下：,lnode *locatenode (linklist head, int key) lnode *p=headnext; while( p /若p=null，則查找失敗，否則p指向值為key的結(jié)點(diǎn) ,2.3.2 循環(huán)鏈表,循環(huán)鏈表（circular linked list）是一種頭尾相接的鏈表。是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 特點(diǎn)： 無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)） 從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。（循環(huán)鏈表的特點(diǎn)） 單循環(huán)鏈表：在單鏈表中，將終端結(jié)點(diǎn)的指針域null改為指向表頭結(jié)點(diǎn)的或開(kāi)始結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱(chēng)為單循環(huán)鏈表。,為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅有一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。如下圖所示：,在用頭指針表示的單循環(huán)鏈表中，找開(kāi)始結(jié)點(diǎn)a1的時(shí)間是o(1)，然而要找到終端結(jié)點(diǎn)an，則需從頭指針開(kāi)始遍歷整個(gè)鏈表，其時(shí)間是o(n)。,在很多實(shí)際問(wèn)題中，表的操作常常是在表的尾部進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便。 如果改用尾指針rear來(lái)表示單循環(huán)鏈表，則查找開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便，它們的存儲(chǔ)位置分別是(rear-next) -next和rear，顯然，查找時(shí)間都是o(1)。 因此，實(shí)際中多采用尾指針表示單循環(huán)鏈表。,由于循環(huán)鏈表中沒(méi)有null指針，故涉及遍歷操作時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p-next是否為空，而是判斷它們是否等于某一指定指針，如頭指針或尾指針等。,空循環(huán)鏈表,舉例：在鏈表上實(shí)現(xiàn)將兩個(gè)線(xiàn)性表(a1，a2，a3，an)和(b1，b2，b3，bn)鏈接成一個(gè)線(xiàn)性表的運(yùn)算。,具體算法如下： linklist connect(linklist la，linklist lb) linklist p = la-next; /p指向la頭結(jié)點(diǎn)后的第一個(gè)結(jié)點(diǎn)。 la-next = ( lb-next )-next; /lb中的所有結(jié)點(diǎn)依次連接在la中的尾指針?biāo)赶虻淖詈笠粋€(gè)結(jié)點(diǎn)之后。 /由于鏈表的特性，只需要將lb中頭指針指向的第一結(jié)點(diǎn)的地址賦給la中最后一個(gè)結(jié)點(diǎn)的指針域。 free( lb-next ); /釋放原來(lái)lb表的頭結(jié)點(diǎn)。 lb-next = p; /原lb表的頭指針和la的頭指針指向一致。 return( lb ); /返回lb，操作完成。 ,2.3.3 雙向鏈表,雙向鏈表(double linked list)：在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱(chēng)為雙向鏈表。,形式描述為： /-線(xiàn)性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)- typedef struct dulnode elemtype data; struct dulnode *prior; /指向后件的指針 struct dulnode *next; /指向前件的指針 dulnode，*dulinklist;,雙向鏈表（帶表頭結(jié)點(diǎn)）,雙向循環(huán)鏈表,和單循環(huán)鏈表類(lèi)型，雙向鏈表也可以有循環(huán)表。 鏈表中存有兩個(gè)環(huán)，并帶有頭結(jié)點(diǎn)。,element,prior,next,結(jié)點(diǎn)結(jié)構(gòu),l,空的雙向循環(huán)鏈表,l,非空的雙向循環(huán)鏈表,雙向循環(huán)鏈表的特性：d-next-prior = d-prior-next = d；,在雙向鏈表中，有些操作如：listlength、getelem和locateelem等僅需涉及一個(gè)方向的指針，則它們的算法描述和線(xiàn)性單鏈表的操作相同； 但在插入、刪除時(shí)需要修改兩個(gè)方向上的指針。,雙向鏈表的刪除操作需要修改兩個(gè)方向上的指針：,刪除（算法2.18） status listdelete_dul( dulinklist /刪除操作成功，返回標(biāo)志ok。 /listdelete_dul,雙向鏈表的插入操作需要修改兩個(gè)方向上的指針：,插入（算法2.19） status listinsert_dul( dulinklist /插入結(jié)點(diǎn)s成功，返回操作成功標(biāo)志ok。 ,總結(jié),由于鏈表在空間的合理利用上和插入、刪除時(shí)不需要移動(dòng)等的優(yōu)點(diǎn)，因此在很多場(chǎng)合下，它是線(xiàn)性表的首選存儲(chǔ)結(jié)構(gòu)； 但也存在著實(shí)現(xiàn)某些基本操作如求線(xiàn)性表的長(zhǎng)度時(shí)不如順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)； 由于鏈表中，結(jié)點(diǎn)之間的關(guān)系用指針來(lái)表示，則數(shù)據(jù)元素在線(xiàn)性表中的“位序”的概念淡化，而被“位置”所代替。,2.4 一元多項(xiàng)式的表示及相加,符號(hào)多項(xiàng)式的操作：一元多項(xiàng)式pn(x)可以按升冪寫(xiě)成:,它由n+1個(gè)系數(shù)唯一確定。 因此，在計(jì)算機(jī)里，它可用一個(gè)線(xiàn)性表p來(lái)表示：,假設(shè)qm(x)是一元m次多項(xiàng)式，同樣可用線(xiàn)性表q來(lái)表示：,表示成：,不失一般性，設(shè)nm，則兩個(gè)多項(xiàng)式相加的結(jié)果rn(x) = pn(x) + qm(x)可用線(xiàn)性表r表示：,結(jié)論：對(duì)p、q和r采用順序存儲(chǔ)結(jié)構(gòu)，使得多項(xiàng)式相加的算法定義十分簡(jiǎn)潔。,需要解決這樣的問(wèn)題： 在通常的應(yīng)用中，多項(xiàng)式的次數(shù)可能很高且變化很大，使得順序存儲(chǔ)結(jié)構(gòu)的最大長(zhǎng)度很難確定。 比如：s(x)=1+3x10000+2x20000 就需要用一長(zhǎng)度為20001的線(xiàn)性表來(lái)表示，表中僅有三個(gè)非零元素，這種對(duì)內(nèi)存空間的浪費(fèi)必須避免。 解決方法：在存儲(chǔ)非零元素系數(shù)項(xiàng)則顯然必須同時(shí)存儲(chǔ)相應(yīng)的指數(shù)。,其中，pi是指數(shù)為ei的項(xiàng)的非零系數(shù)，其滿(mǎn)足 0 e1e2 em m,若用一個(gè)長(zhǎng)度為m且每個(gè)元素有兩個(gè)數(shù)據(jù)項(xiàng)（系數(shù)項(xiàng)和指數(shù)項(xiàng)）的線(xiàn)性表 （p1, e1），（p2, e2），（pm, em） 便可唯一確定多項(xiàng)式pn(x)。