哈工大數(shù)據(jù)結(jié)構(gòu)1

1、第第2章章 線性表線性表 2.1 線性表的定義與運(yùn)算線性表的定義與運(yùn)算非空的線性表非空的線性表 (n0) 記作：記作：（ a1,a2, ai, an）1.線性表的定義線性表的定義 線性表是由線性表是由 n (n=0)個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a1,a2, ai, an組成的有限序列。組成的有限序列。其中：其中： n為數(shù)據(jù)元素的個(gè)數(shù)，也稱為表的長(zhǎng)度。為數(shù)據(jù)元素的個(gè)數(shù)，也稱為表的長(zhǎng)度。當(dāng)當(dāng)n=0 時(shí)，稱為空表。時(shí)，稱為空表。（4） ai 是屬于某個(gè)數(shù)據(jù)對(duì)象的元素，是屬于某個(gè)數(shù)據(jù)對(duì)象的元素， 它可以是它可以是 一個(gè)數(shù)字、一個(gè)字母或一個(gè)記錄。一個(gè)數(shù)字、一個(gè)字母或一個(gè)記錄。（a1,a2, ai

2、-1, ai, ai+1, an）2. 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)（1）有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)）有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1，它沒(méi)有直接前驅(qū)。，它沒(méi)有直接前驅(qū)。（2）有且僅有一個(gè)終端結(jié)點(diǎn)）有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼。，它沒(méi)有直接后繼。（3）其余的結(jié)點(diǎn)）其余的結(jié)點(diǎn)ai (1in) 都都有且僅有有且僅有一個(gè)直接一個(gè)直接 前驅(qū)前驅(qū) ai-1 和一個(gè)直接后繼和一個(gè)直接后繼 ai+1 3.線性表的特性線性表的特性（3）數(shù)據(jù)元素在線性表中的位置只取決于它的序號(hào)。）數(shù)據(jù)元素在線性表中的位置只取決于它的序號(hào)。（1）結(jié)點(diǎn)間的邏輯關(guān)系是線性的。）結(jié)點(diǎn)間的邏輯關(guān)系是線性的。（2）線性表中所有數(shù)據(jù)元素的

3、數(shù)據(jù)類(lèi)型是一致的。）線性表中所有數(shù)據(jù)元素的數(shù)據(jù)類(lèi)型是一致的。例：例： 26個(gè)英文字母組成的字母表個(gè)英文字母組成的字母表（A，B，C、Z）例：例： 某校從某校從1978年到年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的年各種型號(hào)的計(jì)算機(jī)擁有量的 變化情況。變化情況。（6，17，28，50，92，188）姓姓 名名學(xué)學(xué) 號(hào)號(hào)性性 別別年齡年齡 健康情況健康情況王小林王小林790631 男男 18 健康健康陳陳 紅紅790632 女女 20 一般一般劉建平劉建平790633 男男 21 健康健康張立立張立立790634 男男 17 健康健康 . . .例例2_3 學(xué)生健康情況登記表學(xué)生健康情況登記表 4.

4、線性表的運(yùn)算線性表的運(yùn)算（1）存取）存?。?）插入）插入（3）刪除）刪除（4）查找）查找（5）合并）合并（6）分解）分解（7）排序）排序（8）求線性表的長(zhǎng)度）求線性表的長(zhǎng)度 數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的。 具體的實(shí)現(xiàn)則在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。具體的實(shí)現(xiàn)則在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。 運(yùn)算分為運(yùn)算分為: 加工型加工型：改變結(jié)構(gòu)的運(yùn)算。：改變結(jié)構(gòu)的運(yùn)算。 例：初始化線性表。插入、刪除某個(gè)結(jié)點(diǎn)。例：初始化線性表。插入、刪除某個(gè)結(jié)點(diǎn)。 引用型引用型：不改變結(jié)構(gòu)的運(yùn)算。：不改變結(jié)構(gòu)的運(yùn)算。 例：在線性表上的查找運(yùn)算。例：在線性表上的查找運(yùn)算。2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表

5、示和實(shí)現(xiàn) 1. 順序表的定義順序表的定義 用一組連續(xù)的存儲(chǔ)單元（地址連續(xù)）依次存放線性表用一組連續(xù)的存儲(chǔ)單元（地址連續(xù)）依次存放線性表的各個(gè)數(shù)據(jù)元素。的各個(gè)數(shù)據(jù)元素。 即：在順序表中邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素，其物理即：在順序表中邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素，其物理位置也是相鄰的。位置也是相鄰的。 2. 順序表中數(shù)據(jù)元素的存儲(chǔ)地址順序表中數(shù)據(jù)元素的存儲(chǔ)地址a1a2.ai.an線性表的順序存儲(chǔ)示意圖線性表的順序存儲(chǔ)示意圖數(shù)組的下標(biāo)last 存儲(chǔ)地址data01i-1n-1loc(a 1)=BB+dB+(i-1)*dB+(n-1)*dMAXLEN-1 只要知道順序表基地址和每個(gè)數(shù)據(jù)元素所占字節(jié)數(shù)，即可只

6、要知道順序表基地址和每個(gè)數(shù)據(jù)元素所占字節(jié)數(shù)，即可求出第求出第 i 個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。 所以順序表具有所以順序表具有按數(shù)據(jù)元素序號(hào)按數(shù)據(jù)元素序號(hào)隨機(jī)存取的特點(diǎn)。隨機(jī)存取的特點(diǎn)。 若每個(gè)數(shù)據(jù)元素占用若每個(gè)數(shù)據(jù)元素占用 d 個(gè)字節(jié)，則第個(gè)字節(jié)，則第 i 個(gè)數(shù)據(jù)元素的存儲(chǔ)地個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為：址為： loc( ai ) = loc( a1 ) + (i-1)*d (1=i=n) = B + (i-1)*d 其中：其中：loc(a1)為第為第 1 個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，稱為基地址。個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，稱為基地址。 3. 順序表的描述（靜態(tài)）順序表的描述（靜態(tài)） 在在C語(yǔ)言

7、中，一維數(shù)組在內(nèi)存中占用一組連續(xù)的存儲(chǔ)區(qū)域。語(yǔ)言中，一維數(shù)組在內(nèi)存中占用一組連續(xù)的存儲(chǔ)區(qū)域。可用一維數(shù)組來(lái)表示順序表的數(shù)據(jù)存儲(chǔ)。可用一維數(shù)組來(lái)表示順序表的數(shù)據(jù)存儲(chǔ)。typedef int datatype;datatype dataMAXLEN;int last; 線性表的數(shù)據(jù)元素線性表的數(shù)據(jù)元素 a1,a2, ai, an 可依次存入數(shù)組元素可依次存入數(shù)組元素data0, data1, datai-1.,datan-1中。中。 其中：其中： MAXLEN 是一個(gè)根據(jù)實(shí)際問(wèn)題定義的足夠大的整是一個(gè)根據(jù)實(shí)際問(wèn)題定義的足夠大的整數(shù)。數(shù)。 變量變量 last 用來(lái)記錄當(dāng)前線性表中最后一個(gè)元素用來(lái)記錄

8、當(dāng)前線性表中最后一個(gè)元素在數(shù)組中在數(shù)組中的位置的位置，起到了指針的作用，始終，起到了指針的作用，始終指向線性表中的最后一個(gè)指向線性表中的最后一個(gè)元素元素。 數(shù)據(jù)元素分別存放在數(shù)據(jù)元素分別存放在data0到到datalast中中 從從datalast+1 到到dataMAXLEN-1為空閑區(qū)為空閑區(qū) 表長(zhǎng)為表長(zhǎng)為last+1，即為，即為 n 當(dāng)當(dāng)last0時(shí)，表示表為空。時(shí)，表示表為空。從結(jié)構(gòu)性考慮，通常將一個(gè)順序表封裝成一個(gè)結(jié)構(gòu)（靜態(tài)）：從結(jié)構(gòu)性考慮，通常將一個(gè)順序表封裝成一個(gè)結(jié)構(gòu)（靜態(tài)）：typedef int datatype;typedef struct datatype dataMAX

9、LEN; int last; SeqList; / 定義定義SeqList為此種結(jié)構(gòu)類(lèi)型為此種結(jié)構(gòu)類(lèi)型Seqlist L; / 定義一個(gè)順序表定義一個(gè)順序表 （a1,a2,ai-1,x,ai,an） （a1,a2,ai-1,ai,an）（1）插入運(yùn)算）插入運(yùn)算 在線性表的第在線性表的第 i ( 1=ilast=MAXLEN-1) printf(“順序表已滿順序表已滿”); / 最后一個(gè)結(jié)點(diǎn)的位置是最后一個(gè)結(jié)點(diǎn)的位置是 MAXLEN-1 / 表明順序表表明順序表 已滿，不能插入。已滿，不能插入。 return( -1 ); if( iL-last+2 ) / i1 即即 ilast=n-1 L-

10、last+2=n-1+2=n+1 / i L-last+2 即即 i n+1 即即 i = n+2 / 檢查空表及插入位置合法性檢查空表及插入位置合法性 printf(“位置出錯(cuò)位置出錯(cuò)”); return( 0 ); / 以下處理以下處理 i 的有效范圍的有效范圍 1=ilast; j=i-1; j-) L-dataj+1=L-dataj ; / 結(jié)點(diǎn)依次向后移動(dòng)結(jié)點(diǎn)依次向后移動(dòng) / 當(dāng)當(dāng) i=n+1 時(shí)，時(shí)，j= L-last=n-1, i-1=n+1-1=n / 不滿足不滿足j=i-1 所以不做此循環(huán)即不移動(dòng)結(jié)點(diǎn)所以不做此循環(huán)即不移動(dòng)結(jié)點(diǎn)L-datai-1=x ; / 新元素插入新元素插

11、入 將將 x 放在原來(lái)放在原來(lái) ai 的位置的位置 / 當(dāng)當(dāng) i=n+1時(shí)，時(shí)， datai-1= datan= x / 將將 x 直接作為直接作為an+1 放在線性表的最后放在線性表的最后L-last+; / last仍指向最后的元素仍指向最后的元素 return( 1 )插入算法時(shí)間性能分析：插入算法時(shí)間性能分析： 順序表的插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)的移動(dòng)上，在第順序表的插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)的移動(dòng)上，在第 i 個(gè)位置上插入個(gè)位置上插入 x，從，從 an 到到 ai 都要向后移動(dòng)一個(gè)位置，共需移都要向后移動(dòng)一個(gè)位置，共需移 動(dòng)動(dòng) n-i+1 個(gè)元素。個(gè)元素。 而而 i 的取值范圍為

12、：的取值范圍為： 1=i=n+1 即：有即：有 n+1 個(gè)位置可以插入。個(gè)位置可以插入。 設(shè)在第設(shè)在第 i 個(gè)位置上作插入的概率為個(gè)位置上作插入的概率為 pi 則平均移動(dòng)結(jié)點(diǎn)的次數(shù)：則平均移動(dòng)結(jié)點(diǎn)的次數(shù)：)1(11inPEniiI按等概率考慮：按等概率考慮： 可能插入的位置為可能插入的位置為 i=1,2,n,n+1 共共 n+1 個(gè)，個(gè)，則則 pi=1/(n+1) 所以：所以：1111)1(11)1(niniiIinninPE2)1(2)1)1()1111nnnnnn（得出：得出： 順序表插入算法平均約需移動(dòng)一半結(jié)點(diǎn)。順序表插入算法平均約需移動(dòng)一半結(jié)點(diǎn)。 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n) （線

13、性階）（線性階） 。（a1,a2,ai-1,ai+1,an）（2）刪除運(yùn)算）刪除運(yùn)算 （a1,a2,ai-1,ai,ai+1,an） 將線性表的第將線性表的第 i（1=i=n)個(gè)結(jié)點(diǎn)刪除，使得長(zhǎng)度為個(gè)結(jié)點(diǎn)刪除，使得長(zhǎng)度為 n 的的線性表變?yōu)殚L(zhǎng)度為線性表變?yōu)殚L(zhǎng)度為 n-1 的線性表。的線性表。若若i=n，只需刪除終端結(jié)點(diǎn)，不用移動(dòng)結(jié)點(diǎn)。，只需刪除終端結(jié)點(diǎn)，不用移動(dòng)結(jié)點(diǎn)。當(dāng)當(dāng)1=in時(shí)，將時(shí)，將ai+1-an之間的結(jié)點(diǎn)依次向前移動(dòng)。之間的結(jié)點(diǎn)依次向前移動(dòng)。（共需移動(dòng)（共需移動(dòng) n-i 個(gè)結(jié)點(diǎn)）。個(gè)結(jié)點(diǎn)）。修改修改 last 指針（相當(dāng)于修改表長(zhǎng)）使之仍指向最后一個(gè)指針（相當(dāng)于修改表長(zhǎng)）使之仍指向最

14、后一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)。刪除算法思想：刪除算法思想：刪除算法：刪除算法：int DelList( SeqList *L, int i ) int j; if( iL-last+1 ) / iL-last+1 即即in n為原表長(zhǎng)為原表長(zhǎng) / 檢查空表及刪除位置合法性檢查空表及刪除位置合法性 printf(“不存在第不存在第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)”) ; return( 0 ) ; /以下處理以下處理 i 的有效范圍的有效范圍 1=i=n for( j=i; jlast; j+ ) L-dataj-1=L-dataj ; / j=i ai+1 移到了移到了ai 的位置的位置 / j=L-last an 移

15、到了移到了 an-1 的位置的位置 / 當(dāng)當(dāng) i=n 時(shí)，時(shí)，j=n 不滿足此循環(huán)條件不滿足此循環(huán)條件 L-last- ; / 當(dāng)當(dāng) i=n 時(shí)，不用移動(dòng)結(jié)點(diǎn)，表長(zhǎng)直接減時(shí)，不用移動(dòng)結(jié)點(diǎn)，表長(zhǎng)直接減1 return( 1 ) ; 與插入運(yùn)算相同，時(shí)間主要消耗在移動(dòng)表中結(jié)點(diǎn)上。刪除與插入運(yùn)算相同，時(shí)間主要消耗在移動(dòng)表中結(jié)點(diǎn)上。刪除第第 i 個(gè)結(jié)點(diǎn)，其后面的結(jié)點(diǎn)個(gè)結(jié)點(diǎn)，其后面的結(jié)點(diǎn) ai+1-an 都要向前移動(dòng)一個(gè)位置，共都要向前移動(dòng)一個(gè)位置，共移動(dòng)移動(dòng) n-i 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 若若 i=1, 最壞：最壞：O(n) 若若 i=n, 無(wú)需移動(dòng)結(jié)點(diǎn)，直接刪除即可。最好：無(wú)需移動(dòng)結(jié)點(diǎn)，直接刪除即可。最

16、好：O(1)i)(nPEn1iid 刪除算法時(shí)間性能分析：刪除算法時(shí)間性能分析：移動(dòng)結(jié)點(diǎn)的平均次數(shù)：移動(dòng)結(jié)點(diǎn)的平均次數(shù)：按等概率考慮：按等概率考慮：可能刪除的位置為可能刪除的位置為 i=1,2,n 共共 n 個(gè)，則個(gè)，則 pi=1/n 所以：所以： niniiIinninPE11)(1)(212)1(111 nnnnnninnnni得出：順序表刪除算法平均約需移動(dòng)一半結(jié)點(diǎn)。得出：順序表刪除算法平均約需移動(dòng)一半結(jié)點(diǎn)。 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n) （線性階）。（線性階）。（3）按值查找）按值查找按值查找是指在線性表中查找與給定值按值查找是指在線性表中查找與給定值 x 相等的結(jié)點(diǎn)。相等的結(jié)點(diǎn)。

17、查找算法思想：查找算法思想：從第一個(gè)結(jié)點(diǎn)從第一個(gè)結(jié)點(diǎn) a1 起依次和起依次和 x 比較，直到找到一個(gè)與比較，直到找到一個(gè)與 x 相等的相等的結(jié)點(diǎn)，則返回它的序號(hào)或在順序表中的存儲(chǔ)下標(biāo)結(jié)點(diǎn)，則返回它的序號(hào)或在順序表中的存儲(chǔ)下標(biāo) 。 若查遍整個(gè)線性表都沒(méi)有找到與若查遍整個(gè)線性表都沒(méi)有找到與 x 相等的結(jié)點(diǎn)，則返回相等的結(jié)點(diǎn)，則返回 -1。查找算法：查找算法：int LocationSeqList( SeqList *L, datatype x) int i=0 ; while ( ilast & L-datai!=x ) i+ ; if ( iL-last ) return -1 ; /

18、當(dāng)當(dāng) iL-last 時(shí)肯定沒(méi)找著時(shí)肯定沒(méi)找著 else return i ; / 返回的是存儲(chǔ)位置返回的是存儲(chǔ)位置 即數(shù)組元素的下標(biāo)即數(shù)組元素的下標(biāo)查找算法時(shí)間性能分析：查找算法時(shí)間性能分析：查找算法的主要運(yùn)算是比較。查找算法的主要運(yùn)算是比較。比較次數(shù)與比較次數(shù)與 x 在表中的位置及表的長(zhǎng)度有關(guān)。在表中的位置及表的長(zhǎng)度有關(guān)。當(dāng)當(dāng) a1=x 時(shí)，比較時(shí)，比較 1 次成功。次成功。當(dāng)當(dāng) an=x 時(shí)，比較時(shí)，比較 n 次成功。次成功。平均比較次數(shù)為平均比較次數(shù)為 (n+1)/2 。時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)，即線性階。即線性階。5. 順序表其他基本運(yùn)算順序表其他基本運(yùn)算 (動(dòng)態(tài)分配順序存儲(chǔ)

19、結(jié)構(gòu)動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu))約定約定:Data0=a1(1)初始化初始化-構(gòu)造一個(gè)空的線性表構(gòu)造一個(gè)空的線性表 L void InitList ( SeqList & L ) L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data = = NULL ) printf ( “存儲(chǔ)分配失敗存儲(chǔ)分配失敗!n” ); exit (overflow); L.length = 0; L.listsize=ListSize (2)(2)順序表的插入順序表的插入( (動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)動(dòng)態(tài)分配順序存儲(chǔ)

20、結(jié)構(gòu)) )int Insert ( SeqList &L, ListData x, int i ) /在表中第在表中第 i 個(gè)位置之前插入新元素個(gè)位置之前插入新元素 x if (i L.length +1) return error; if( L.length = = L.listSize) newbase=( ListData * ) realloc(L.date, ( listSize +listadd)* sizeof ( ListData ) ); if(!newbase) exit(overflow); L.Data=newbase; L.listsize+=listadd;

21、 q=&(L.Datai-1); /q為插入位置為插入位置 for ( p =&( L.DataL.length-1); p=q; -p) *(p+1)=*p; *q=x; L.length+; return 1; /插入成功插入成功 找找x x在表中的位置，若查找成功，返回在表中的位置，若查找成功，返回x x元素第一次出現(xiàn)在表元素第一次出現(xiàn)在表 中的位序，否則返回中的位序，否則返回-1-1int Locate-sq ( SeqList *L, ListData x ) int i = 1; /按序列下標(biāo)按序列下標(biāo) while ( i = L.length & L.da

22、tai-1 != x ) i+; if ( i = 0 & i L.length ) return L.datai-1; else printf ( “參數(shù)參數(shù) i 不合理不合理！n” ); int Length ( SeqList L ) return L.length; (4) 求表的長(zhǎng)度求表的長(zhǎng)度(5) 提取提取函數(shù)函數(shù)(1) (1) 集合的集合的“并并”運(yùn)算運(yùn)算void Union ( SeqList &A, SeqList B ) int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i m; i+

23、) int x = GetData ( B, i ); /在在B中取一元素中取一元素 int k = Locate-sq (A, x); /在在A中查找它中查找它 if ( k = - -1 ) /若未找到插入它若未找到插入它 Insert ( A, x, +n ); n+; n n先先+再傳再傳參數(shù)參數(shù)6. 順序表的應(yīng)用順序表的應(yīng)用 void Intersection ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i data P-next結(jié)點(diǎn)

24、結(jié)點(diǎn) node p 為指向鏈表中某一結(jié)點(diǎn)的指針變量。為指向鏈表中某一結(jié)點(diǎn)的指針變量。 *p 表示表示 指針指針 p 所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn) 。 (*p).data 或或 p-data 表示表示 p 所指向結(jié)點(diǎn)的數(shù)據(jù)域所指向結(jié)點(diǎn)的數(shù)據(jù)域 。 (*p).next 或或 p-next 表示表示 p 所指向結(jié)點(diǎn)的指針域所指向結(jié)點(diǎn)的指針域 。p=(node*)malloc(sizeof(node) =(linklist)malloc(sizeof(node) 對(duì)指針對(duì)指針 p 賦值使其指向某一新結(jié)點(diǎn)賦值使其指向某一新結(jié)點(diǎn)（按需生成一個(gè)（按需生成一個(gè)node結(jié)點(diǎn)類(lèi)型的新結(jié)點(diǎn)，動(dòng)態(tài)申請(qǐng)空間）結(jié)點(diǎn)類(lèi)型的新結(jié)

25、點(diǎn)，動(dòng)態(tài)申請(qǐng)空間）其中：其中： (node*) 進(jìn)行類(lèi)型轉(zhuǎn)換。進(jìn)行類(lèi)型轉(zhuǎn)換。sizeof(node) 求結(jié)點(diǎn)需占用的字節(jié)數(shù)。求結(jié)點(diǎn)需占用的字節(jié)數(shù)。malloc(size) 在內(nèi)存中分配在內(nèi)存中分配 size 個(gè)個(gè)連續(xù)可用字節(jié)連續(xù)可用字節(jié)的空間的空間結(jié)點(diǎn)的申請(qǐng)與釋放：結(jié)點(diǎn)的申請(qǐng)與釋放：free(p)系統(tǒng)回收系統(tǒng)回收 p 結(jié)點(diǎn)結(jié)點(diǎn)，即，即動(dòng)態(tài)動(dòng)態(tài)釋放釋放 p 指向的結(jié)點(diǎn)的空間指向的結(jié)點(diǎn)的空間 單鏈表上的基本運(yùn)算：?jiǎn)捂湵砩系幕具\(yùn)算：（1）建立單鏈表）建立單鏈表B A C HeadHead S 頭插法頭插法建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）：建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）： 思想：從

26、一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)：將讀思想：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)：將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。 DB A C HeadHead S 頭插法頭插法建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）：建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）： 思想：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀思想：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將

27、新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。 DB A C HeadHead S 頭插法頭插法建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）：建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）： 思想：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀思想：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。 DB A C HeadHead S注：頭插法生成的鏈注：頭插法生成的鏈表中結(jié)點(diǎn)的次序和輸表中結(jié)

28、點(diǎn)的次序和輸入的順序相反。入的順序相反。 頭插法頭插法建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）：建表（在鏈表的頭部插入結(jié)點(diǎn)建立線性鏈表）： 思想：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀思想：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。 Dvoid CREATELISTF( )char x; / 逐個(gè)插入字符，以逐個(gè)插入字符，以x為結(jié)束符為結(jié)束符 node *head, *s; int n=0; / n 為鏈表表

29、長(zhǎng)為鏈表表長(zhǎng) head=NULL; / 鏈表開(kāi)始為空鏈表開(kāi)始為空 x=getchar( ); / 讀入第讀入第1個(gè)結(jié)點(diǎn)的值個(gè)結(jié)點(diǎn)的值 while(x!=x) s=（node *）malloc(sizeof(node); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) s-data=x; / 將將 x 的值存入新結(jié)點(diǎn)的數(shù)據(jù)域中的值存入新結(jié)點(diǎn)的數(shù)據(jù)域中 s-next=head; /第第1個(gè)結(jié)點(diǎn)鏈域?yàn)榭諅€(gè)結(jié)點(diǎn)鏈域?yàn)榭説ead=s; n+; /表長(zhǎng)加表長(zhǎng)加1 x=getchar(); 頭插法建表頭插法建表: : 尾插法建表：尾插法建表：尾插建表可使生尾插建表可使生成的結(jié)點(diǎn)次序和成的結(jié)點(diǎn)次序和輸入的順序相同輸入的順序相同算法

30、思想：算法思想： 將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上。將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上。 可增加一個(gè)尾指針可增加一個(gè)尾指針 r r ，使其始終指向鏈表的尾結(jié)點(diǎn)。，使其始終指向鏈表的尾結(jié)點(diǎn)。A C B 尾插法建表：尾插法建表：head r S rD 尾插建表可使生尾插建表可使生成的結(jié)點(diǎn)次序和成的結(jié)點(diǎn)次序和輸入的順序相同輸入的順序相同void CREATLISTR( ) char x; / 逐個(gè)插入字符，以逐個(gè)插入字符，以 x 為為 結(jié)束結(jié)束符符 node *head, *s, *r; head=NULL; / 鏈表開(kāi)始為空鏈表開(kāi)始為空 r=NULL; / 尾指針初值為空尾指針初值為空 int n=0;

31、 / n 為鏈表表長(zhǎng)為鏈表表長(zhǎng) x=getchar(); / 讀入第讀入第1個(gè)結(jié)點(diǎn)的值個(gè)結(jié)點(diǎn)的值 while(x!=x) / x為輸入結(jié)束符為輸入結(jié)束符 s=( node * ) malloc(sizeof(node); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)s-data=x; / 將將x 的值存入新結(jié)點(diǎn)的數(shù)據(jù)域中的值存入新結(jié)點(diǎn)的數(shù)據(jù)域中 if (head=NULL) head=s;else r-next=s;r=s; / r 始終指向鏈表的尾結(jié)點(diǎn)始終指向鏈表的尾結(jié)點(diǎn)n+; / 表長(zhǎng)加表長(zhǎng)加1 x=getchar(); if(r!=NULL) r-next=NULL; / 保證尾結(jié)點(diǎn)的鏈域?yàn)榭毡ＷC尾結(jié)點(diǎn)的鏈

32、域?yàn)榭瘴膊宸ńū恚何膊宸ńū恚何膊宸ńū矸治觯何膊宸ńū矸治觯?上述尾插法建表由于沒(méi)有設(shè)頭結(jié)點(diǎn)（附加），因此上述尾插法建表由于沒(méi)有設(shè)頭結(jié)點(diǎn)（附加），因此開(kāi)始結(jié)點(diǎn)和其它結(jié)點(diǎn)的插入處理并不一樣。開(kāi)始結(jié)點(diǎn)和其它結(jié)點(diǎn)的插入處理并不一樣。算法思想：算法思想： 設(shè)設(shè)頭結(jié)點(diǎn)頭結(jié)點(diǎn)，使第一個(gè)結(jié)點(diǎn)和其余結(jié)點(diǎn)的插入操作一致。，使第一個(gè)結(jié)點(diǎn)和其余結(jié)點(diǎn)的插入操作一致。 尾插法建表的改進(jìn)算法尾插法建表的改進(jìn)算法增加頭結(jié)點(diǎn)：增加頭結(jié)點(diǎn)： 頭結(jié)點(diǎn)的數(shù)據(jù)域：可有可無(wú)頭結(jié)點(diǎn)的數(shù)據(jù)域：可有可無(wú) 頭結(jié)點(diǎn)的指針域：為指向第一個(gè)結(jié)點(diǎn)的指針。頭結(jié)點(diǎn)的指針域：為指向第一個(gè)結(jié)點(diǎn)的指針。改進(jìn)的尾插法建表算法：改進(jìn)的尾插法建表算法：帶頭結(jié)點(diǎn)的單

33、鏈表：帶頭結(jié)點(diǎn)的單鏈表：特點(diǎn)：特點(diǎn)：無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針。無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針。所以對(duì)于尾插法建表，表的第所以對(duì)于尾插法建表，表的第 1 個(gè)結(jié)點(diǎn)和其它結(jié)點(diǎn)的操作一致。個(gè)結(jié)點(diǎn)和其它結(jié)點(diǎn)的操作一致。heada1 an 頭結(jié)點(diǎn)頭結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)非空表：除頭結(jié)點(diǎn)外還有其他結(jié)點(diǎn)非空表：除頭結(jié)點(diǎn)外還有其他結(jié)點(diǎn)終端結(jié)點(diǎn)終端結(jié)點(diǎn)空表：只有空表：只有1個(gè)頭結(jié)點(diǎn)個(gè)頭結(jié)點(diǎn)head頭結(jié)點(diǎn)頭結(jié)點(diǎn)void CREATLISTR1( ) / 帶頭結(jié)點(diǎn)的尾插法建立單鏈表帶頭結(jié)點(diǎn)的尾插法建立單鏈表char x; int n=0; node *head, *s, *r;

34、 head=(node*)malloc(sizeof(node); / 生成頭結(jié)點(diǎn)生成頭結(jié)點(diǎn) r=head; /尾指針初值指向頭結(jié)點(diǎn)尾指針初值指向頭結(jié)點(diǎn) x=getchar(); while(x!=x) / x為輸入結(jié)束符為輸入結(jié)束符 s=（node *）malloc(sizeof(node); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) n+; / 表長(zhǎng)加表長(zhǎng)加1 s-data=x;r-next=s; / 新結(jié)點(diǎn)插入表尾新結(jié)點(diǎn)插入表尾 r=s; / 尾指針尾指針 r 指向新的表尾指向新的表尾x=getchar(); / 讀下一結(jié)點(diǎn)讀下一結(jié)點(diǎn) r-next=NULL;改進(jìn)的改進(jìn)的尾插建表算法尾插建表算法: :v

35、oid createlist()node *p,*s; char x; int z=1;n=0; head=(node*)malloc(sizeof(node); p=head; printf(ntt建立一個(gè)線性表建立一個(gè)線性表); printf(“ntt請(qǐng)逐個(gè)輸入字符，請(qǐng)逐個(gè)輸入字符， 結(jié)束標(biāo)記為結(jié)束標(biāo)記為xn); while(z)printf(tt輸入：輸入：); scanf(%c,&x); getchar();if(x!=x) s=(node*)malloc(sizeof(node); n+; s-data=x; p-next=s; s-next=NULL; p=s;else z

36、=0;帶頭結(jié)點(diǎn)的帶頭結(jié)點(diǎn)的尾插建表算法（尾插建表算法（p總指向尾結(jié)點(diǎn)）：（不講）總指向尾結(jié)點(diǎn)）：（不講）（2）查找運(yùn)算）查找運(yùn)算設(shè)單鏈表的長(zhǎng)度為設(shè)單鏈表的長(zhǎng)度為 n n ，要查找表中第，要查找表中第 i i 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。算法思想：算法思想：從頭結(jié)點(diǎn)開(kāi)始順鏈掃描。從頭結(jié)點(diǎn)開(kāi)始順鏈掃描。用指針用指針 p p 指向當(dāng)前掃描到的結(jié)點(diǎn)。指向當(dāng)前掃描到的結(jié)點(diǎn)。用用 j j 作統(tǒng)計(jì)已掃描結(jié)點(diǎn)數(shù)的計(jì)數(shù)器。作統(tǒng)計(jì)已掃描結(jié)點(diǎn)數(shù)的計(jì)數(shù)器。p p 的的初值指向頭結(jié)點(diǎn)，初值指向頭結(jié)點(diǎn)，j j 的初值為的初值為 0 0 。當(dāng)當(dāng) p p 掃描下一個(gè)結(jié)點(diǎn)時(shí)，掃描下一個(gè)結(jié)點(diǎn)時(shí)，j j 自動(dòng)加自動(dòng)加 1 1 。 當(dāng)當(dāng) j=i

37、j=i時(shí)，指針時(shí)，指針 p p 所指的結(jié)點(diǎn)就是第所指的結(jié)點(diǎn)就是第 i i 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。按序號(hào)查找按序號(hào)查找node * searchlist1( linklist L, int i ) / L接收已存在的鏈表的頭指針接收已存在的鏈表的頭指針/ i 接收要查找的結(jié)點(diǎn)的位置接收要查找的結(jié)點(diǎn)的位置 node *p; int j=0; p=L; while( p-next!=NULL & jnext; j+; if(j= =i) return p; else return NULL;i 的合法位置為：的合法位置為：1=i=n帶頭結(jié)點(diǎn)，則可：帶頭結(jié)點(diǎn)，則可：0=inext=NULL) / 鏈

38、表只有頭結(jié)點(diǎn)鏈表只有頭結(jié)點(diǎn) printf(tt線性表為空！線性表為空！); return; p=L-next; / 從除頭結(jié)點(diǎn)外的第從除頭結(jié)點(diǎn)外的第 1 個(gè)結(jié)點(diǎn)開(kāi)始個(gè)結(jié)點(diǎn)開(kāi)始while( p!=NULL & p-data!=x ) p=p-next; i+; if( p!=NULL ) return p; printf(tt 在第在第%d位上找到值為位上找到值為%d的結(jié)點(diǎn)！的結(jié)點(diǎn)！, i, x ); else / p為空，肯定將最后一個(gè)結(jié)點(diǎn)的鏈域給了為空，肯定將最后一個(gè)結(jié)點(diǎn)的鏈域給了p，即沒(méi)找到，即沒(méi)找到 printf(tt 未找到值為未找到值為%c的結(jié)點(diǎn)！的結(jié)點(diǎn)！n, x ); re

39、turn NULL; 設(shè)設(shè) 指針指針 p 指向單鏈表的某一結(jié)點(diǎn)。指向單鏈表的某一結(jié)點(diǎn)。設(shè)設(shè) 指針指針 s 指向等待插入的、值為指向等待插入的、值為 x 的新結(jié)點(diǎn)。的新結(jié)點(diǎn)。實(shí)現(xiàn)方法（兩種）：實(shí)現(xiàn)方法（兩種）： 后插：將新結(jié)點(diǎn)后插：將新結(jié)點(diǎn) * *s s 插在結(jié)點(diǎn)插在結(jié)點(diǎn) * *p p 之后。之后。 前插：將新結(jié)點(diǎn)前插：將新結(jié)點(diǎn) * *s s 插在結(jié)點(diǎn)插在結(jié)點(diǎn) * *p p 之前。之前。（3）插入運(yùn)算）插入運(yùn)算算法思想：算法思想： 取一新結(jié)點(diǎn)，將其數(shù)據(jù)域置為新結(jié)點(diǎn)，再修改有關(guān)結(jié)點(diǎn)的取一新結(jié)點(diǎn)，將其數(shù)據(jù)域置為新結(jié)點(diǎn)，再修改有關(guān)結(jié)點(diǎn)的鏈域：鏈域： 把原把原 p 結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)作為結(jié)點(diǎn)的直接后繼結(jié)

40、點(diǎn)作為 s 結(jié)點(diǎn)的直接后繼；結(jié)點(diǎn)的直接后繼； s 結(jié)點(diǎn)作為結(jié)點(diǎn)作為 p 結(jié)點(diǎn)的直接后繼。結(jié)點(diǎn)的直接后繼。 后插操作后插操作X S PINSERTAFTER( p，x ) / 將值為將值為 x 的新結(jié)點(diǎn)插在的新結(jié)點(diǎn)插在*P 之后之后 node *p; datatype x; s=( node *)malloc(sizeof(node); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) s-data=x; s-next=p-next; / p-next=s; / 將將 *s 插在插在 *p 之后之后后插算法：后插算法：后插算法時(shí)間復(fù)雜度：后插算法時(shí)間復(fù)雜度：O（1）先找到先找到 p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（單鏈表無(wú)前驅(qū)指針）；

41、結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（單鏈表無(wú)前驅(qū)指針）；然后修改此前驅(qū)結(jié)點(diǎn)的鏈域，使其指向等待插入的然后修改此前驅(qū)結(jié)點(diǎn)的鏈域，使其指向等待插入的 s 結(jié)點(diǎn)結(jié)點(diǎn) ；然后將然后將 s 結(jié)點(diǎn)的鏈域指向結(jié)點(diǎn)的鏈域指向 p 結(jié)點(diǎn)結(jié)點(diǎn) 。 前插操作：前插操作：X S q p INSERTBEFORE（p, x） / 在帶頭結(jié)點(diǎn)的單鏈表在帶頭結(jié)點(diǎn)的單鏈表 head 中中,將值為將值為 x 的新結(jié)點(diǎn)插在的新結(jié)點(diǎn)插在 *P 之前之前 node *p; datatype x; node *q; q=head; / 從頭指針開(kāi)始從頭指針開(kāi)始 if( q= =NULL ) printf(“error!”); else s=（node*）

42、malloc(sizeof(node); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) s-data=x; while(q-next!=p) q=q-next; / 找找 *p 的前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) s-next=p; / q-next=s; / 將將 *s 插在插在 *p 之之 前前,插在插在 *q 之后之后 前插算法前插算法：前插算法的平均時(shí)間復(fù)雜度為：前插算法的平均時(shí)間復(fù)雜度為：O（n） 改進(jìn)的前插算法改進(jìn)的前插算法算法思想：算法思想：后插算法為后插算法為 O(1) ，而前插算法為，而前插算法為O(n) ?？稍诳稍?*p 之后插入新結(jié)點(diǎn)之后插入新結(jié)點(diǎn) *s ，然后，然后交換交換 *s 和和 *p 的的值值。

43、交換后實(shí)際上就是前插。交換后實(shí)際上就是前插。pA X s插入前：插入前：后插：后插：A X ps交換調(diào)整：交換調(diào)整：x A p sINSERTBEFORE2( p，x) / 將值為將值為 x 的新結(jié)點(diǎn)插在的新結(jié)點(diǎn)插在 *p 之后之后 node *p; datatype x, y; s=（node *）malloc(sizeof(node); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) s-data=x; s-next=p-next; p-next=s; / 將將 *s 插在插在 *p 之后之后 y=s-data ; / 交換交換 *s 和和 *p 的值的值 s-data=p-data ; p-data=y ;

44、p=s ;算法描述：算法描述：算法思想：算法思想：先求出第先求出第 i-1 個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，然后在第然后在第 i-1 個(gè)結(jié)點(diǎn)之后插入結(jié)點(diǎn)個(gè)結(jié)點(diǎn)之后插入結(jié)點(diǎn) x。 插入運(yùn)算插入運(yùn)算 inslist（i,x ) )（不講）（不講）void inslist(int i,char x) /i 的合法位置為：的合法位置為：1=i=n node *s,*p; int j; if(idata=x; s-next=p-next; p-next=s; else printf( tt 未找到前驅(qū)結(jié)點(diǎn)未找到前驅(qū)結(jié)點(diǎn)!n); （4）刪除運(yùn)算）刪除運(yùn)算刪除單鏈表中刪除單鏈表中 *p 的后繼結(jié)點(diǎn)。的后繼結(jié)點(diǎn)。算法描述：算

45、法描述：DeleteA( p ) / 刪除刪除 *p 的后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn) *r, 設(shè)設(shè) *r 存在存在 node *p; node *r; if(p-next!=NULL) / 說(shuō)明其后繼結(jié)點(diǎn)存在說(shuō)明其后繼結(jié)點(diǎn)存在 r=p-next; / 將后繼結(jié)點(diǎn)存到將后繼結(jié)點(diǎn)存到 r 中，便于釋放中，便于釋放 p-next=r-next; / 將將 p 的鏈域指向其后繼結(jié)點(diǎn)的后繼的鏈域指向其后繼結(jié)點(diǎn)的后繼 free(r); 存儲(chǔ)池p r例：在單鏈表上刪除序號(hào)為例：在單鏈表上刪除序號(hào)為 i 的結(jié)點(diǎn)的結(jié)點(diǎn) Delete( L, i ) （按序號(hào)刪除結(jié)點(diǎn)）（按序號(hào)刪除結(jié)點(diǎn)）算法思想：算法思想：（1）找到被刪結(jié)

46、點(diǎn)（第）找到被刪結(jié)點(diǎn)（第 i 個(gè)結(jié)點(diǎn)）的前驅(qū)結(jié)點(diǎn)（第個(gè)結(jié)點(diǎn)）的前驅(qū)結(jié)點(diǎn)（第 i-1個(gè)個(gè)結(jié)結(jié)點(diǎn)點(diǎn)）（2）用指針）用指針 p 指向該前驅(qū)結(jié)點(diǎn)；指向該前驅(qū)結(jié)點(diǎn)；（3）刪除）刪除 *p 的后繼結(jié)點(diǎn)即第的后繼結(jié)點(diǎn)即第 i 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。思考：思考：（1）如何刪除單鏈表中）如何刪除單鏈表中 p 結(jié)點(diǎn)本身？結(jié)點(diǎn)本身？ （找前驅(qū)結(jié)點(diǎn)）（找前驅(qū)結(jié)點(diǎn)）（2）如何刪除單鏈表中）如何刪除單鏈表中 p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)？結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)？ （找前驅(qū)的前驅(qū)）（找前驅(qū)的前驅(qū)）DELETE(L,i)node *L;int i; node*p; int j; j=i-1; p=searchlist1(L,j)；/ 找到第找到第i

47、-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*p if (p!=NULL)&(p-next!=NULL) DeleteA(p); else printf(“errorn”)算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：例：刪除線性表例：刪除線性表 head 中數(shù)據(jù)域?yàn)橹袛?shù)據(jù)域?yàn)?x 的結(jié)點(diǎn)。的結(jié)點(diǎn)。 （按值刪除結(jié)點(diǎn)）（按值刪除結(jié)點(diǎn)）算法思想：算法思想： （1）若鏈表為空，返回；）若鏈表為空，返回； （2）查找值為）查找值為 x 的結(jié)點(diǎn)及其前驅(qū)結(jié)點(diǎn)；的結(jié)點(diǎn)及其前驅(qū)結(jié)點(diǎn)； （3）將）將 x 結(jié)點(diǎn)刪除。結(jié)點(diǎn)刪除。 void dellist( char x ) node *p,*q; / 始終用始終用 q 指向指向 *p 的前驅(qū)的前驅(qū) if(he

48、ad=NULL) / 為空表為空表 printf(tt鏈表下溢！鏈表下溢！n); return; if(head-next=NULL) /表只有頭結(jié)點(diǎn)表只有頭結(jié)點(diǎn) printf(tt線性表為空！線性表為空！); return; q=head; p=head-next;算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：while(p!=NULL&p-data!=x) / 始終用始終用 q 指向指向 *p 的前驅(qū)的前驅(qū) q=p; p=p-next; if ( p!=NULL ) / p!=NULL說(shuō)明說(shuō)明 p 不是尾結(jié)點(diǎn)，不是尾結(jié)點(diǎn)，p還在表內(nèi)還在表內(nèi) ，說(shuō)明找到了值為，說(shuō)明找到了值為x的結(jié)點(diǎn)，就是的結(jié)點(diǎn)，就是p q-

49、next=p-next; free(p); printf(tt %c 已經(jīng)被刪除！已經(jīng)被刪除！,x); else printf(tt 未找到！未找到！n);3. 單單循環(huán)鏈表循環(huán)鏈表 整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)均可找到整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。表中其它結(jié)點(diǎn)。a1 an .(非空表）非空表） h(空表）空表）h特點(diǎn)：特點(diǎn)：（1）表中最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)或）表中最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)或表頭結(jié)點(diǎn)（如果有表頭結(jié)點(diǎn)）。表頭結(jié)點(diǎn)（如果有表頭結(jié)點(diǎn)）。（2）循環(huán)鏈表的運(yùn)算與單鏈表基本一致。但兩者判斷是否）循環(huán)鏈表的運(yùn)算與單鏈表基本一致。但

50、兩者判斷是否到表尾的條件不同：到表尾的條件不同：?jiǎn)捂湵恚号袛嗄辰Y(jié)點(diǎn)的鏈域是否為空。單鏈表：判斷某結(jié)點(diǎn)的鏈域是否為空。循環(huán)鏈表：判斷某結(jié)點(diǎn)的鏈域值是否等于頭指針。循環(huán)鏈表：判斷某結(jié)點(diǎn)的鏈域值是否等于頭指針。（3）用只有頭指針表示的單循環(huán)鏈表查找結(jié)點(diǎn)：）用只有頭指針表示的單循環(huán)鏈表查找結(jié)點(diǎn)： 找找 a1(開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)) O(1) 找找 an 需要遍歷表需要遍歷表 O(n) 由于在實(shí)際問(wèn)題中，對(duì)表的操作常在表的首尾位置進(jìn)行，因由于在實(shí)際問(wèn)題中，對(duì)表的操作常在表的首尾位置進(jìn)行，因此可增加一個(gè)尾指針此可增加一個(gè)尾指針(rear)，則：，則： 找找a1(開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)) ：rear-next-nex

51、t O(1) 找找an ： rear O(1) 實(shí)用中多用實(shí)用中多用尾指針尾指針表示表示單循環(huán)鏈表單循環(huán)鏈表。尾指針表示的單循環(huán)鏈表：尾指針表示的單循環(huán)鏈表：headhead非空表非空表空表空表rearrear例：表的合并例：表的合并 在鏈表上實(shí)現(xiàn)將兩個(gè)線性表在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1,a2,.,an)和和(b1,b2bm)鏈接成鏈接成一個(gè)線性表一個(gè)線性表(a1,a2,.,an,b1,b2,.,bm)的的運(yùn)算。運(yùn)算。分析：分析： 若在若在單鏈表單鏈表或或只有頭指針表示的單循環(huán)鏈表只有頭指針表示的單循環(huán)鏈表上做這種鏈接上做這種鏈接運(yùn)算，運(yùn)算， 都要遍歷第一個(gè)鏈表找到結(jié)點(diǎn)都要遍歷第一個(gè)鏈表找到

52、結(jié)點(diǎn) an ， 然后將結(jié)點(diǎn)然后將結(jié)點(diǎn) b1 鏈接鏈接到到 an 的后面的后面，其執(zhí)行時(shí)間為其執(zhí)行時(shí)間為 O(n) 。算法思想：算法思想： 在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無(wú)在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無(wú)需遍歷，需遍歷，其執(zhí)行時(shí)間為其執(zhí)行時(shí)間為O(1) 。兩個(gè)單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：兩個(gè)單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：rarbp 兩個(gè)單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：兩個(gè)單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：rarbnode *CONNECT(ra,rb)node *ra,*rb; node*p;p=ra-next;/ 保存鏈表

53、保存鏈表ra的頭結(jié)點(diǎn)地址的頭結(jié)點(diǎn)地址 ra-next=rb-next-next; / 將表將表rb的開(kāi)始結(jié)點(diǎn)鏈接到表的開(kāi)始結(jié)點(diǎn)鏈接到表ra的終端結(jié)點(diǎn)之后的終端結(jié)點(diǎn)之后 free(rb-next);/ 釋放鏈表釋放鏈表rb的頭結(jié)點(diǎn)的頭結(jié)點(diǎn) rb-next=p；/ 鏈表鏈表ra的頭結(jié)點(diǎn)鏈到鏈表的頭結(jié)點(diǎn)鏈到鏈表rb的終端結(jié)點(diǎn)之后的終端結(jié)點(diǎn)之后 return rb ;/返回新循環(huán)鏈表的尾指針?lè)祷匦卵h(huán)鏈表的尾指針4 .雙向鏈表（雙向鏈表（Double linked list)查找某個(gè)結(jié)點(diǎn)：查找某個(gè)結(jié)點(diǎn)： 單鏈表只能順鏈向后（順著直接后繼指針）查找。單鏈表只能順鏈向后（順著直接后繼指針）查找。查找某個(gè)結(jié)

54、點(diǎn)的前驅(qū)結(jié)點(diǎn)：查找某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)： 單鏈表：從頭順鏈找。單鏈表：從頭順鏈找。O(n) 單循環(huán)鏈表：可從任一已知結(jié)點(diǎn)出發(fā)進(jìn)行查找。單循環(huán)鏈表：可從任一已知結(jié)點(diǎn)出發(fā)進(jìn)行查找。O(n)雙向鏈表（雙向鏈表（Double linked list)： 單鏈表的每個(gè)結(jié)點(diǎn)再增加一個(gè)指向其前驅(qū)的指針域單鏈表的每個(gè)結(jié)點(diǎn)再增加一個(gè)指向其前驅(qū)的指針域 prior，這樣形成的鏈表有兩條不同方向的鏈，稱之為雙向鏈表。這樣形成的鏈表有兩條不同方向的鏈，稱之為雙向鏈表。特點(diǎn)：特點(diǎn)：雙鏈表一般也由頭指針雙鏈表一般也由頭指針 head 唯一確定。唯一確定。每一結(jié)點(diǎn)均有：每一結(jié)點(diǎn)均有： 數(shù)據(jù)域數(shù)據(jù)域 （data ） 左鏈域左鏈

55、域 （prior） 指向前驅(qū)結(jié)點(diǎn)。指向前驅(qū)結(jié)點(diǎn)。 右鏈域右鏈域 （next ） 指向后繼結(jié)點(diǎn)。指向后繼結(jié)點(diǎn)。是一種對(duì)稱結(jié)構(gòu)（既有左鏈域，又有右鏈域）。是一種對(duì)稱結(jié)構(gòu)（既有左鏈域，又有右鏈域）。（1）雙向鏈表的分類(lèi)：）雙向鏈表的分類(lèi)： 非循環(huán)雙向鏈表非循環(huán)雙向鏈表 循環(huán)雙向鏈表循環(huán)雙向鏈表 為了運(yùn)算方便，還可添加一個(gè)表頭結(jié)點(diǎn)。為了運(yùn)算方便，還可添加一個(gè)表頭結(jié)點(diǎn)。（2）雙鏈表的結(jié)點(diǎn)類(lèi)型描述）雙鏈表的結(jié)點(diǎn)類(lèi)型描述typedef struct dnode datatype data; struct dnode *prior,*next;dlinknode;dlinknode *head;(3)結(jié)點(diǎn)結(jié)構(gòu)

56、示意圖結(jié)點(diǎn)結(jié)構(gòu)示意圖headheadhead結(jié)點(diǎn)結(jié)構(gòu)示意圖結(jié)點(diǎn)結(jié)構(gòu)示意圖帶頭結(jié)點(diǎn)的雙循環(huán)帶頭結(jié)點(diǎn)的雙循環(huán)空空鏈表鏈表帶頭結(jié)點(diǎn)的雙循環(huán)鏈表帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 p-prior-next=p-next-prior=p 即：即： 結(jié)點(diǎn)結(jié)點(diǎn)*p 的存儲(chǔ)位置的存儲(chǔ)位置 ： 既存放在其前驅(qū)結(jié)點(diǎn)既存放在其前驅(qū)結(jié)點(diǎn)( * p-prior )的后繼指針域中；的后繼指針域中； 也存放在其后繼結(jié)點(diǎn)也存放在其后繼結(jié)點(diǎn)( * p-next ) 的前驅(qū)指針域中。的前驅(qū)指針域中。(4)雙鏈表結(jié)構(gòu)對(duì)稱性描述：雙鏈表結(jié)構(gòu)對(duì)稱性描述：插入；插入；刪除；刪除；查找；查找；在單鏈表中：在單鏈表中：前插不如后插方便；前插不如后插方便；

57、刪除某結(jié)點(diǎn)自身不如刪除該結(jié)點(diǎn)的后繼方便。刪除某結(jié)點(diǎn)自身不如刪除該結(jié)點(diǎn)的后繼方便。而在雙向鏈表中，上述運(yùn)算均十分方便。而在雙向鏈表中，上述運(yùn)算均十分方便。雙鏈表的基本運(yùn)算：雙鏈表的基本運(yùn)算：/在帶頭結(jié)點(diǎn)的雙鏈表中，將值為在帶頭結(jié)點(diǎn)的雙鏈表中，將值為 x 的新結(jié)點(diǎn)插在的新結(jié)點(diǎn)插在 *p 之前之前 void dinsert(p,x)dlinknode *p;datatype x; dlinknode *s; s= (dlinknode*) malloc(sizeof(dlinknode); s-data=x; s-prior=p-prior; s-next=p; p-prior-next=s; p-

58、prior=s; （1）前插操作（將結(jié)點(diǎn)）前插操作（將結(jié)點(diǎn) x 插在插在 *p 之前）之前）spax注意：注意：5，6步的順序不能顛倒步的順序不能顛倒如果是后插，則注意如果是后插，則注意5，6步的順序步的順序spxa p-next-prior=s; p-next=s;Ddelete(p)dlinknode *p; p-prior-next=p-next; p-next-prior=p-prior; free(p);pxa（2）刪除操作（在雙向鏈表中刪除）刪除操作（在雙向鏈表中刪除 p 結(jié)點(diǎn)）結(jié)點(diǎn)）算法思想：算法思想： 從第一個(gè)結(jié)點(diǎn)開(kāi)始（從第一個(gè)結(jié)點(diǎn)開(kāi)始（頭結(jié)點(diǎn)的后繼頭結(jié)點(diǎn)的后繼）依次比較每個(gè)結(jié)

59、點(diǎn)）依次比較每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的值，若找到結(jié)點(diǎn)的數(shù)據(jù)域的值，若找到結(jié)點(diǎn) x，則，則返回指向該結(jié)點(diǎn)的指針?lè)祷刂赶蛟摻Y(jié)點(diǎn)的指針； 否則：若又回到頭結(jié)點(diǎn)，說(shuō)明表中不存在結(jié)點(diǎn)否則：若又回到頭結(jié)點(diǎn)，說(shuō)明表中不存在結(jié)點(diǎn) x，則，則返回返回空指針空指針。（3）查找（在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中查找結(jié)點(diǎn)）查找（在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中查找結(jié)點(diǎn) x ）算法描述：算法描述：( 自己完成）自己完成）5. 靜態(tài)鏈表靜態(tài)鏈表 靜態(tài)鏈表可以借助一維數(shù)組來(lái)描述：靜態(tài)鏈表可以借助一維數(shù)組來(lái)描述： #define MAXSIZE 1000 typedef struct ElemType data; int cur; compon

60、ent, SlinkListMAXSIZE; 為了便于在不設(shè)指針類(lèi)型的高級(jí)程序設(shè)計(jì)語(yǔ)言中使用為了便于在不設(shè)指針類(lèi)型的高級(jí)程序設(shè)計(jì)語(yǔ)言中使用鏈表結(jié)構(gòu)，引入靜態(tài)鏈表。鏈表結(jié)構(gòu)，引入靜態(tài)鏈表。 靜態(tài)鏈表和前面的動(dòng)態(tài)鏈表一樣，便于插入和刪除操靜態(tài)鏈表和前面的動(dòng)態(tài)鏈表一樣，便于插入和刪除操作：插入和刪除同樣不需要移動(dòng)元素。作：插入和刪除同樣不需要移動(dòng)元素。 設(shè)設(shè) S S 為為 SlinkList SlinkList 型變量，則型變量，則 S0.cur S0.cur 指示第一個(gè)結(jié)點(diǎn)在指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置，設(shè)數(shù)組中的位置，設(shè) i=s0.curi=s0.cur，則，則 si.datasi.data存放線性表的第一存放線性表的第一個(gè)元素，且個(gè)元素，且 si.cur si.cur 指示第二個(gè)結(jié)點(diǎn)在數(shù)組中位置。指示第二個(gè)結(jié)點(diǎn)在數(shù)組中位置。 一