2.2 鏈表 數(shù)據(jù)結(jié)構(gòu)ppt課件

1、第第2章章 線性表線性表2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4 1;.上堂課要點(diǎn)回顧上堂課要點(diǎn)回顧線性結(jié)構(gòu)線性結(jié)構(gòu)( (包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn) 僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。2. 2. 線性表線性表邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：“一對(duì)一一對(duì)一” 或或 1:11:1存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)運(yùn) 算算 ：修改、插入、刪除：修改、插入、刪除3.3.順序存儲(chǔ)

2、順序存儲(chǔ)特征：邏輯上相鄰，物理上也相鄰；特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找快優(yōu)點(diǎn)：隨機(jī)查找快 O(1)O(1)缺點(diǎn)：插入、刪除慢缺點(diǎn)：插入、刪除慢 O(n)O(n)2;.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)總結(jié)總結(jié)線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素，方便快捷優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素，方便快捷缺點(diǎn)：在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素。缺點(diǎn)：在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素。解決問(wèn)題的思路：改用另一種線性存儲(chǔ)方式：解決問(wèn)題的思路：改用另一種

3、線性存儲(chǔ)方式：3;.2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1 鏈表的表示鏈表的表示2.3.2 鏈表的實(shí)現(xiàn)鏈表的實(shí)現(xiàn)2.3.3 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析4;.復(fù)習(xí)復(fù)習(xí)C語(yǔ)言語(yǔ)言指針指針: :即地址。即地址。指針變量指針變量: :是專(zhuān)門(mén)用來(lái)存放另一個(gè)變量的地址的是專(zhuān)門(mén)用來(lái)存放另一個(gè)變量的地址的變量變量，即專(zhuān)門(mén)存放地址的，即專(zhuān)門(mén)存放地址的，指針變指針變量量的值是指針的值是指針I(yè)nt *p,*q; / /* *p,q是變量名，都是指向整型變量的指針變量，是變量名，都是指向整型變量的指針變量，*表示該變量為指針表示該變量為指針變量變量，（，（*p)是指指針變量是指指針變

4、量P P所指向的變量所指向的變量* */ /數(shù)組指針數(shù)組指針: :是指數(shù)組的起始地址，數(shù)組元素的指針是數(shù)組元素的地址。是指數(shù)組的起始地址，數(shù)組元素的指針是數(shù)組元素的地址。 Int *p, a10; 若若p=a , ,則則p+1=a+1 指針數(shù)組指針數(shù)組: :是指數(shù)組元素均為指針類(lèi)型的數(shù)組是指數(shù)組元素均為指針類(lèi)型的數(shù)組5;.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。定相鄰。如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？通過(guò)指針來(lái)實(shí)現(xiàn)！通過(guò)指針來(lái)實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針

5、域讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針指針指針指針指針指針或或樣樣 式式數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)值數(shù)據(jù)指針域：存儲(chǔ)直接后繼或者直接前指針域：存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置驅(qū)的存儲(chǔ)位置2.3.1 鏈表的表示鏈表的表示6;.例：請(qǐng)畫(huà)出例：請(qǐng)畫(huà)出26 個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下： 解：該字母表的邏輯結(jié)構(gòu)為：（解：該字母表的邏輯結(jié)構(gòu)為：（ a, b, a, b, ,y, z ,y, z）鏈表存放示意圖如下：鏈表存放示意圖如下： a1heada2/an討論討論1:1

6、:每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)和每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)和 。討論討論2:2:在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 指示。指示。 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域指針域( (鏈域鏈域) )7;.1 1）結(jié)點(diǎn)：）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2 2）鏈表：）鏈表： n 個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱(chēng)為線性個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱(chēng)為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3 3）單

7、鏈表、雙鏈表、多鏈表、循環(huán)鏈表：）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱(chēng)為單鏈表或線性鏈表結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱(chēng)為單鏈表或線性鏈表有兩個(gè)指針域的鏈表，稱(chēng)為雙鏈表（但未必是雙向鏈表）；有兩個(gè)指針域的鏈表，稱(chēng)為雙鏈表（但未必是雙向鏈表）；有多個(gè)指針域的鏈表，稱(chēng)為多鏈表；有多個(gè)指針域的鏈表，稱(chēng)為多鏈表；首尾相接的鏈表稱(chēng)為循環(huán)鏈表。首尾相接的鏈表稱(chēng)為循環(huán)鏈表。a1heada2an循環(huán)鏈表示意圖：循環(huán)鏈表示意圖：(2) (2) 與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：8;.4 4）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)首

8、元結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2infoan頭指針頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；一般用頭是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；一般用頭指針唯一標(biāo)識(shí)一個(gè)單鏈表指針唯一標(biāo)識(shí)一個(gè)單鏈表. .頭結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度信息，它不計(jì)入表長(zhǎng)度首元結(jié)點(diǎn)首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a a1 1的結(jié)點(diǎn)的結(jié)點(diǎn) 示意圖如下：示意圖如下：9;.答答:討論1. 在鏈表中設(shè)置頭結(jié)點(diǎn)有什么

9、好處？在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2. 如何表示空表？如何表示空表？頭結(jié)點(diǎn)頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放也可存放表長(zhǎng)度表長(zhǎng)度等附加信息，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空等附加信息，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答答:無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；頭指針頭指針無(wú)頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭

10、結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。頭結(jié)點(diǎn)不計(jì)入鏈表頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！長(zhǎng)度！10;.一個(gè)線性表的邏輯結(jié)構(gòu)為：（一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？請(qǐng)問(wèn)其頭指針的值是多少？存儲(chǔ)地址存儲(chǔ)地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU

11、25答：答：頭指針是指向鏈表中第一個(gè)頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱(chēng)：頭指針?lè)Q：頭指針H的值是的值是31（3 3）舉例）舉例例例1 1：11;.上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無(wú)頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn) 有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！度！12;. 其中指針其中指針X X，Y Y，Z Z的值分別為多少

12、？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？的起始地址為多少？答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = 。例例2 2：線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)：線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表元素的線性表L=23L=23，1717，4747，0505，3131，若它以鏈接方式存儲(chǔ)在下列，若它以鏈接方式存儲(chǔ)在下列100100119119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2 2個(gè)字節(jié)）和指針（占個(gè)字

13、節(jié)）和指針（占2 2個(gè)字節(jié)）組成，個(gè)字節(jié)）組成，如下圖所示。如下圖所示。13;.討論: 鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類(lèi)型，編程時(shí)該如何表示？鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類(lèi)型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類(lèi)型通常不一致，所以要采用因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類(lèi)型通常不一致，所以要采用數(shù)據(jù)類(lèi)數(shù)據(jù)類(lèi)型。型。答答:以以2626個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型字符型指針型指針型pb14;.實(shí)現(xiàn)實(shí)現(xiàn)typedef struct node datatype data; struct node *next;*l

14、inklist, node;node *head,*p;datanextp結(jié)點(diǎn)（結(jié)點(diǎn)（*p）(*p)表示表示p p所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn)(*p).datap-data表示表示p p指向結(jié)點(diǎn)的數(shù)據(jù)域指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).nextp-next表示表示p p指向結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)的指針域生成一個(gè)生成一個(gè)lnodelnode型型新結(jié)點(diǎn)：新結(jié)點(diǎn)：p=(node p=(node * *)malloc(sizeof(node);)malloc(sizeof(node);系統(tǒng)回收系統(tǒng)回收p p結(jié)點(diǎn)：結(jié)點(diǎn)：free(p)free(p)15;. 對(duì)于指向結(jié)構(gòu)類(lèi)型的指針變量，可被說(shuō)明為：對(duì)于指向結(jié)構(gòu)類(lèi)型的指

15、針變量，可被說(shuō)明為： node *p, *q; /或用或用 struct bird *p , *q; /注：上面已經(jīng)定義了注：上面已經(jīng)定義了nodenode為用戶(hù)自定義的為用戶(hù)自定義的birdbird類(lèi)型。類(lèi)型。補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類(lèi)型的補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類(lèi)型的C C表示法表示法 類(lèi)型定義和變量說(shuō)明可以合寫(xiě)為：類(lèi)型定義和變量說(shuō)明可以合寫(xiě)為：typedef struct bird /bird/bird是自定義結(jié)構(gòu)類(lèi)型名稱(chēng)是自定義結(jié)構(gòu)類(lèi)型名稱(chēng) char data; /定義數(shù)據(jù)域的變量名及其類(lèi)型定義數(shù)據(jù)域的變量名及其類(lèi)型struct bird *next; /定義指針域的變量名及其類(lèi)型定義指針域的變量名及其類(lèi)型n

16、ode，*pointer; /node/node是是birdbird結(jié)構(gòu)類(lèi)型的類(lèi)型替代結(jié)構(gòu)類(lèi)型的類(lèi)型替代, , * *pointerpointer是指針型的是指針型的birdbird結(jié)構(gòu)類(lèi)型的替代，也是數(shù)據(jù)類(lèi)型結(jié)構(gòu)類(lèi)型的替代，也是數(shù)據(jù)類(lèi)型* */ /16;.Typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 教材教材P28P28對(duì)于線性表的單鏈表存儲(chǔ)結(jié)構(gòu)對(duì)于線性表的單鏈表存儲(chǔ)結(jié)構(gòu)描述描述: :教材問(wèn)題討論：教材問(wèn)題討論：Q1Q1：第一行的：第一行的Lnode Lnode 與最后一行的與最后一行的Ln

17、odeLnode是不是一回事？是不是一回事？A1A1：不是。前者：不是。前者LnodeLnode是結(jié)構(gòu)名，后者是結(jié)構(gòu)名，后者LnodeLnode是對(duì)整個(gè)是對(duì)整個(gè)structstruct類(lèi)型的一種類(lèi)型的一種“縮寫(xiě)縮寫(xiě)”，是一種是一種“新定義名新定義名”，它只是對(duì)現(xiàn)有類(lèi)型名的補(bǔ)充，而不是取代。，它只是對(duì)現(xiàn)有類(lèi)型名的補(bǔ)充，而不是取代。請(qǐng)注意：請(qǐng)注意：TypedefTypedef不可能創(chuàng)造任何新的不可能創(chuàng)造任何新的數(shù)據(jù)類(lèi)型，而僅僅是在原有的數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型，而僅僅是在原有的數(shù)據(jù)類(lèi)型中命名一個(gè)新名字，其目的是使你的程中命名一個(gè)新名字，其目的是使你的程序更易閱讀和移植。序更易閱讀和移植。17;.Typed

18、ef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; Q2Q2： 那為何兩處要同名那為何兩處要同名( (Lnode和和Lnode）？太不嚴(yán)謹(jǐn)）？太不嚴(yán)謹(jǐn) 了吧？了吧？A2A2：同名是為了表述起來(lái)方便。例如，若結(jié)構(gòu)名為：同名是為了表述起來(lái)方便。例如，若結(jié)構(gòu)名為studentstudent，其新定義名縮寫(xiě)也，其新定義名縮寫(xiě)也最好寫(xiě)成最好寫(xiě)成studentstudent，因?yàn)槊枋龅膶?duì)象相同，方便閱讀和理解。，因?yàn)槊枋龅膶?duì)象相同，方便閱讀和理解。Q3Q3：結(jié)構(gòu)體中間的那個(gè)：結(jié)構(gòu)體中間的那個(gè)struct Lnodestr

19、uct Lnode是何意？是何意？A3A3：在：在“縮寫(xiě)縮寫(xiě)” LnodeLnode還沒(méi)出現(xiàn)之前，只能用原始的還沒(méi)出現(xiàn)之前，只能用原始的struct Lnodestruct Lnode來(lái)進(jìn)行變來(lái)進(jìn)行變量說(shuō)明。此處說(shuō)明了指針?lè)至康臄?shù)據(jù)類(lèi)型是量說(shuō)明。此處說(shuō)明了指針?lè)至康臄?shù)據(jù)類(lèi)型是struct Lnodestruct Lnode。Typedef struct student char name; int age; student,*pointer; 18;.設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個(gè)元素的指針個(gè)元素的指針, ,則第則第i i個(gè)元素的個(gè)元素的數(shù)據(jù)域?qū)憺閿?shù)據(jù)域?qū)憺?，指針域?qū)憺?，指?/p>

20、域?qū)憺?。練習(xí)：練習(xí)：p-dataai的值的值p-nextai+1的地址的地址附附1 1：介紹：介紹C C的三個(gè)有用的庫(kù)函數(shù)的三個(gè)有用的庫(kù)函數(shù)/ /算符（都在算符（都在 中）中）sizeof(x)計(jì)算變量計(jì)算變量x x的長(zhǎng)度（字節(jié)數(shù)）；的長(zhǎng)度（字節(jié)數(shù)）；malloc(m) 開(kāi)辟開(kāi)辟m m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；free(p ) 釋放指針釋放指針p p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。19;.sizeof(x)計(jì)算計(jì)算x x的長(zhǎng)度的長(zhǎng)度malloc(m) 開(kāi)開(kāi)m m字節(jié)空間字節(jié)空間fre

21、e(p) 刪除一個(gè)變量刪除一個(gè)變量問(wèn)問(wèn)1 1：自定義結(jié)構(gòu)類(lèi)型變量：自定義結(jié)構(gòu)類(lèi)型變量nodenode的長(zhǎng)度的長(zhǎng)度m m是多少？是多少？問(wèn)問(wèn)2 2：結(jié)構(gòu)變量：結(jié)構(gòu)變量nodenode的首地址的首地址( (指針指針p p）是多少？）是多少？問(wèn)問(wèn)3 3：怎樣刪除結(jié)構(gòu)變量：怎樣刪除結(jié)構(gòu)變量nodenode？*nextdatanode，長(zhǎng)度為，長(zhǎng)度為m字節(jié)字節(jié)pmsizeof(nodenode) /單位是字節(jié)單位是字節(jié)p(node(node* *) )malloc(m)free(p) /只能借助只能借助nodenode的指針刪除！的指針刪除！P-data=P-data=a a; p-next=q; p-

22、next=q20;.單鏈表的抽象數(shù)據(jù)類(lèi)型描述如下單鏈表的抽象數(shù)據(jù)類(lèi)型描述如下（參見(jiàn)教材（參見(jiàn)教材P28P28）：）：Typedef struct Lnode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct Lnode *next; /指針域指針域Lnode, *LinkList; / *LinkList為為L(zhǎng)node類(lèi)型的指針類(lèi)型的指針 至此應(yīng)可看懂教材至此應(yīng)可看懂教材P22P22關(guān)于順序表動(dòng)態(tài)分配的存儲(chǔ)結(jié)構(gòu)。關(guān)于順序表動(dòng)態(tài)分配的存儲(chǔ)結(jié)構(gòu)。其特點(diǎn)是：用結(jié)構(gòu)類(lèi)型和指針來(lái)表示順序結(jié)構(gòu)，更靈活。其特點(diǎn)是：用結(jié)構(gòu)類(lèi)型和指針來(lái)表示順序結(jié)構(gòu)，更靈活。如何具體編程來(lái)建立和訪問(wèn)如何具體編程來(lái)建立和

23、訪問(wèn)鏈表？鏈表？鏈表的實(shí)現(xiàn)鏈表的實(shí)現(xiàn)21;.2.3.2 鏈表的實(shí)現(xiàn)鏈表的實(shí)現(xiàn)（1 1） 單鏈表的建立和輸出單鏈表的建立和輸出（2 2） 單鏈表的修改單鏈表的修改（3 3） 單鏈表的插入單鏈表的插入（4 4） 單鏈表的刪除單鏈表的刪除22;.（1） 單鏈表的建立和輸出單鏈表的建立和輸出例：用單鏈表結(jié)構(gòu)來(lái)存放例：用單鏈表結(jié)構(gòu)來(lái)存放26個(gè)英文字母組成的線性表（個(gè)英文字母組成的線性表（a，b，c，z）,請(qǐng)寫(xiě)出請(qǐng)寫(xiě)出C語(yǔ)言程序。語(yǔ)言程序。實(shí)現(xiàn)思路：實(shí)現(xiàn)思路：先開(kāi)辟頭指針，然后陸續(xù)為每個(gè)結(jié)點(diǎn)開(kāi)辟存儲(chǔ)空間并及時(shí)賦值，先開(kāi)辟頭指針，然后陸續(xù)為每個(gè)結(jié)點(diǎn)開(kāi)辟存儲(chǔ)空間并及時(shí)賦值，后繼結(jié)點(diǎn)的地址要提前送給前面的指針。

24、后繼結(jié)點(diǎn)的地址要提前送給前面的指針。先挖先挖“坑坑”, ,后種后種“蘿卜蘿卜”！23;.typedef struct node char data; struct node *next;node; node *p,*q,*head; /一般需要一般需要3 3個(gè)指針變量個(gè)指針變量int n ; / / 數(shù)據(jù)元素的個(gè)數(shù)數(shù)據(jù)元素的個(gè)數(shù)int m=sizeof(node); / /* *結(jié)構(gòu)類(lèi)型定義好之后，每個(gè)變量的長(zhǎng)度就固定了，結(jié)構(gòu)類(lèi)型定義好之后，每個(gè)變量的長(zhǎng)度就固定了，m m求一次求一次即可即可* */ /將全局變量及函數(shù)提前說(shuō)明：將全局變量及函數(shù)提前說(shuō)明：24;.新手特別容易忘記！新手特別容易忘

25、記！ int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出前面已求出p=head; for( i=1; idata=i+a-1; / 第一個(gè)結(jié)點(diǎn)值為字符第一個(gè)結(jié)點(diǎn)值為字符a p-next=(node*)malloc(m); /為后繼結(jié)點(diǎn)為后繼結(jié)點(diǎn)“挖坑挖坑”！ p=p-next； /讓指針變量讓指針變量P指向后一個(gè)結(jié)點(diǎn)指向后一個(gè)結(jié)點(diǎn)p-data=i+a-1; /最后一個(gè)元素要單獨(dú)處理最后一個(gè)元素要單獨(dú)處理p-next=NULL ; / /單鏈表尾結(jié)點(diǎn)的指針域要置空！單鏈表尾結(jié)點(diǎn)的指針域要置空！void build( ) /字母鏈表的生成。字母鏈表

26、的生成。要一個(gè)個(gè)慢慢鏈入要一個(gè)個(gè)慢慢鏈入25;.p=head;while (p) /當(dāng)指針不空時(shí)循環(huán)，僅限于無(wú)頭結(jié)點(diǎn)的情況當(dāng)指針不空時(shí)循環(huán)，僅限于無(wú)頭結(jié)點(diǎn)的情況 printf(%c,p-data); p=p-next; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” 討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何 改寫(xiě)？改寫(xiě)？ sum+;sum+;sum=0;sum=0;void display() /*字母鏈表的輸出字母鏈表的輸出*/26;.（2） 單鏈表的修改單鏈表的修改(或讀取）或讀?。┧悸罚核悸罚阂薷牡谝薷牡趇個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的

27、指針個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針p，然后才，然后才能執(zhí)行能執(zhí)行p-data=new_value 。修改第修改第i i個(gè)數(shù)據(jù)元素的操作函數(shù)可寫(xiě)為：個(gè)數(shù)據(jù)元素的操作函數(shù)可寫(xiě)為：Status GetElem_L(LinkList L, int i, ElemType &e)p=L-next; j=1; /帶頭結(jié)點(diǎn)的鏈表帶頭結(jié)點(diǎn)的鏈表while(p&jnext; +j; /順指針向后查找，直到順指針向后查找，直到p指向第指向第i個(gè)元素或個(gè)元素或p唯空唯空if( !p | ji ) return ERROR; p-data =e; /若是讀取則為：若是讀取則為：e=p-

28、data; return OK;/ GetElem_L缺點(diǎn)：缺點(diǎn)：想尋找單鏈表中第想尋找單鏈表中第i i個(gè)元素，只能從頭指針開(kāi)始逐一查詢(xún)（順藤摸瓜），個(gè)元素，只能從頭指針開(kāi)始逐一查詢(xún)（順藤摸瓜），無(wú)法隨機(jī)存取無(wú)法隨機(jī)存取 。27;.在鏈表中插入一個(gè)元素在鏈表中插入一個(gè)元素X X 的示意圖如下：的示意圖如下：X Xsabp鏈表插入的核心語(yǔ)句：鏈表插入的核心語(yǔ)句：p-nexts-nextX X 結(jié)點(diǎn)的生成方式：結(jié)點(diǎn)的生成方式：s=(nodes=(node* *)malloc(m);)malloc(m);s-data=s-data=X X ; ;s-next= ?s-next= ?bapX X （3

29、） 單鏈表的插入單鏈表的插入28;. Status ListInsert_L(LinkList L, int i, ElemType e) / L 為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法 / 在鏈表中第在鏈表中第i 個(gè)結(jié)點(diǎn)之前插入新的元素個(gè)結(jié)點(diǎn)之前插入新的元素 e / LinstInsert_L算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度為為:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 尋找第尋找第 i-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)if (!p | j i-1) return ERROR; / i 大于表長(zhǎng)或者小于大于

30、表長(zhǎng)或者小于1 s = new LNode; / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)s-data = e; s-next = p-next; p-next = s; / 插入插入return OK;29;.在鏈表中刪除某元素在鏈表中刪除某元素b b的示意圖如下：的示意圖如下：c a bp刪除動(dòng)作的核心語(yǔ)句（要借助輔助指針變量刪除動(dòng)作的核心語(yǔ)句（要借助輔助指針變量q q）：）：q = p-next; /首先保存首先保存b b的指針，靠它才能找到的指針，靠它才能找到c c；p-next=q-next; /將將a a、c c兩結(jié)點(diǎn)相連，淘汰兩結(jié)點(diǎn)相連，淘汰b b結(jié)點(diǎn)；結(jié)點(diǎn)；free(q) ； /徹底釋放徹底釋放b

31、 b結(jié)點(diǎn)空間結(jié)點(diǎn)空間p-next思考：思考： 省略省略free(q)語(yǔ)句語(yǔ)句行不行？行不行？(p-next) - nextq（4） 單鏈表的刪除單鏈表的刪除30;. Status ListDelete_L(LinkList L, int i, ElemType &e) / / 刪除以刪除以 L L 為頭指針為頭指針( (帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)) )的單鏈表中第的單鏈表中第 i i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) / ListDelete_L算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度為:O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / / 尋找第尋

32、找第 i i 個(gè)結(jié)點(diǎn)，并令個(gè)結(jié)點(diǎn)，并令 p p 指向其前趨指向其前趨if (!(p-next) | j i-1) return ERROR; / / 刪除位置不合理刪除位置不合理q = p-next; p-next = q-next; / / 刪除并釋放結(jié)點(diǎn)刪除并釋放結(jié)點(diǎn)e = q-data; free(q);return OK;31;.2.3.3 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析（1） 查找查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為度為 O(n)。時(shí)間效率分析時(shí)間效率分析（2） 插入和刪除插入

33、和刪除 因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是所耗時(shí)間復(fù)雜度將是 O(n)。32;.空間效率分析空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了n 個(gè)整型變量，個(gè)整型變量，空間復(fù)雜度為空間復(fù)雜度為 O(n)。在在n n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)* *

34、P P，需找到它的，需找到它的 ，其，其時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 。 O(n)O(n)練習(xí)：練習(xí)：33;.如何從線性表得到單鏈表？如何從線性表得到單鏈表？鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要預(yù)分配空間，因此生成鏈表的過(guò)程是一個(gè)結(jié)鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要預(yù)分配空間，因此生成鏈表的過(guò)程是一個(gè)結(jié)點(diǎn)點(diǎn)“逐個(gè)插入逐個(gè)插入”的過(guò)程。的過(guò)程。34;.例如：逆位序輸入例如：逆位序輸入 n n 個(gè)數(shù)據(jù)元素的值，個(gè)數(shù)據(jù)元素的值， 建立帶頭結(jié)點(diǎn)的單鏈表。建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：操作步驟：一、建立一個(gè)一、建立一個(gè)“空表空表”；二、輸入數(shù)據(jù)元素二、輸入數(shù)據(jù)元素an， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)

35、元素三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；ananan-1四、依次類(lèi)推，直至輸入四、依次類(lèi)推，直至輸入a1為止。為止。35;.Void CreateList_L(LinkList &L,int n)/逆位序輸入逆位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈線性表個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈線性表L L=(LinkList) malloc (sizeof(Lnode); L-next=NULL; /先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 for(i=n; i0; -i) p= (LinkList) malloc (sizeof(Lnode); /生成新結(jié)

36、點(diǎn)生成新結(jié)點(diǎn) scanf(&p-data); /輸入元素值輸入元素值 p-next= L-next; L-next=p; / CreateList_L從表尾到表頭逆向建立單鏈表算法描述從表尾到表頭逆向建立單鏈表算法描述36;.操作操作 ClearList(&L) 在鏈表中的實(shí)現(xiàn)在鏈表中的實(shí)現(xiàn):void ClearList(&L) / 將單鏈表重新置為一個(gè)空表將單鏈表重新置為一個(gè)空表 while (L-next) p=L-next; L-next=p-next; / ClearListfree(p);算法時(shí)間復(fù)雜度：O(ListLength(L)37;.2.4 應(yīng)用舉例應(yīng)

37、用舉例算法要求：算法要求：已知已知: :線性表線性表 A A和和B B，分別由單鏈表，分別由單鏈表 LaLa和和Lb Lb 存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列（即已經(jīng)有序）；列（即已經(jīng)有序）；要求：要求：將將A A和和B B歸并為一個(gè)新的線性表歸并為一個(gè)新的線性表C, CC, C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C C由單鏈表由單鏈表LcLc存儲(chǔ)。存儲(chǔ)。假設(shè)：假設(shè)：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）預(yù)測(cè)：預(yù)測(cè)：合并后的合并后的C =C =（2, 3, 5

38、, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，1111）例例1 1：兩個(gè)鏈表的歸并（：兩個(gè)鏈表的歸并（教材教材P31P31例例）重點(diǎn)是鏈表重點(diǎn)是鏈表38;.鏈表示意圖：鏈表示意圖： 3 3 5 51111 / 8 8 LaLa 2 2 6 61111 / 8 8 LbLb 9 9 2 2 3 3 6 6 5 5 LcLc 8 8 811 / 911頭結(jié)點(diǎn)頭結(jié)點(diǎn)39;.算法設(shè)計(jì)：算法設(shè)計(jì)：算法主要包括搜索、比較、插入三個(gè)操作：算法主要包括搜索、比較、插入三個(gè)操作：搜索：需要設(shè)立三個(gè)指針來(lái)指向搜索：需要設(shè)立三個(gè)指針來(lái)指向La La 、LbLb和和LcLc鏈表；鏈表

39、；比較：比較比較：比較LaLa和和LbLb表中結(jié)點(diǎn)數(shù)據(jù)的大??；表中結(jié)點(diǎn)數(shù)據(jù)的大??；插入：將插入：將LaLa和和LbLb表中數(shù)據(jù)較小的結(jié)點(diǎn)插入新鏈表表中數(shù)據(jù)較小的結(jié)點(diǎn)插入新鏈表Lc Lc 。請(qǐng)注意鏈表的特點(diǎn)，僅改變指針便可實(shí)現(xiàn)數(shù)據(jù)的移動(dòng)請(qǐng)注意鏈表的特點(diǎn)，僅改變指針便可實(shí)現(xiàn)數(shù)據(jù)的移動(dòng), ,即即“數(shù)據(jù)不動(dòng)，指針動(dòng)數(shù)據(jù)不動(dòng)，指針動(dòng)”40;.La3 5 8 11 Lb2 6 8 119 PaPbPaPbPaPa、PbPb用于搜索用于搜索LaLa和和LbLb， PcPc指向新鏈表當(dāng)前結(jié)點(diǎn)。指向新鏈表當(dāng)前結(jié)點(diǎn)。歸并過(guò)程示意如下：歸并過(guò)程示意如下：Lc=LaPbPaPaPb41;.算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： Voi

40、d MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /已知單鏈線性表已知單鏈線性表LaLa和和LbLb的元素按值非遞減排列。歸并為的元素按值非遞減排列。歸并為L(zhǎng)cLc后也按值非遞減排列。后也按值非遞減排列。 free(Lb); /釋放釋放LbLb的頭結(jié)點(diǎn)的頭結(jié)點(diǎn) /MergeList_L pc-next = pa pa: pb ; /插入非空表的剩余段插入非空表的剩余段 while(pa&pb) /將將pa pa 、pbpb結(jié)點(diǎn)按大小依次插入結(jié)點(diǎn)按大小依次插入LcLc中中 if(pa-datadata) p

41、c-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=LaLa-next; pb=LbLb-next; Lc=pc=La； /有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)見(jiàn)見(jiàn)P31P31算法算法2.122.12? ?是條件運(yùn)算符（為真則取第是條件運(yùn)算符（為真則取第1 1項(xiàng)，見(jiàn)項(xiàng)，見(jiàn)P10P10條件賦值）條件賦值）注：注：LcLc用的是用的是LaLa的頭指針的頭指針42;.思思 考：考：1 1、不用、不用LcLc，直接把，直接把LaLa表插到表插到LbLb表中；或者把表中；或者把LbLb表插到表插到LaLa表中，怎么表中，怎么修改？修改？2

42、2、重復(fù)的數(shù)據(jù)元素不需要插入，怎么修改？、重復(fù)的數(shù)據(jù)元素不需要插入，怎么修改？43;.循環(huán)鏈表循環(huán)鏈表(circular linked list)循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率操作與單鏈表基本一致操作與單鏈表基本一致, ,循環(huán)條件不同循環(huán)條件不同單鏈表單鏈表p或或p-next=NULL循環(huán)鏈表循環(huán)鏈表p或或p-next=headhh空表空表44;.雙向鏈表（雙向鏈表（double linked

43、list）單鏈表具有單向性的缺點(diǎn)單鏈表具有單向性的缺點(diǎn)結(jié)點(diǎn)定義結(jié)點(diǎn)定義typedef struct node datatype element; struct node *prior,*next;dnode;priorelementnextL空雙向循環(huán)鏈表：空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp-prior-next= p= p-next-prior;NextElem的執(zhí)行時(shí)間為的執(zhí)行時(shí)間為O(1)PriorElem的執(zhí)行時(shí)間為的執(zhí)行時(shí)間為O(n)45;.bcaPvoid del_dulist(dnode *p)p-prior-next=p-next; p-nex

44、t-prior=p-prior; free(p);刪除刪除算法描述算法描述算法評(píng)價(jià)：算法評(píng)價(jià)：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;46;.void ins_dulist(dnode* p,int x)dnode *s; s=(dnode*)malloc(sizeof(dnode); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;算法描述算法描述算法評(píng)價(jià)：算法評(píng)價(jià)：T(n)=O(1)xSbaP插入插入47;.用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，用

45、上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問(wèn)題：存在的問(wèn)題： 改進(jìn)鏈表的設(shè)置：改進(jìn)鏈表的設(shè)置：1單鏈表的表長(zhǎng)是一個(gè)隱含的值；單鏈表的表長(zhǎng)是一個(gè)隱含的值； 1增加增加“表長(zhǎng)表長(zhǎng)”、“表尾指針表尾指針” 和和 “當(dāng)前位置的當(dāng)前位置的 指針指針” 三個(gè)數(shù)據(jù)域；三個(gè)數(shù)據(jù)域；2在單鏈表的最后一個(gè)元素之后插入元素時(shí)，在單鏈表的最后一個(gè)元素之后插入元素時(shí)， 需遍歷整個(gè)鏈表；需遍歷整個(gè)鏈表；3在鏈表中，元素的在鏈表中，元素的“位序位序”概念淡化，結(jié)點(diǎn)的概念淡化，結(jié)點(diǎn)的 “位置位置”概念加強(qiáng)。概念加強(qiáng)。2將基本操作中的將基本操作中的“位序位序 i ”改變?yōu)楦淖優(yōu)椤爸羔樦羔?p ”。48;.四、一個(gè)帶頭結(jié)點(diǎn)的線性

46、鏈表類(lèi)型四、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類(lèi)型typedef struct LNode / 結(jié)點(diǎn)類(lèi)型結(jié)點(diǎn)類(lèi)型 ElemType data; struct LNode *next; *Link, *Position;Status MakeNode( Link &p, ElemType e ); / 分配由分配由 p 指向的值為指向的值為e的結(jié)點(diǎn)，并返回的結(jié)點(diǎn)，并返回OK； / 若分配失敗，則返回若分配失敗，則返回 ERRORvoid FreeNode( Link &p ); / 釋放釋放 p 所指結(jié)點(diǎn)所指結(jié)點(diǎn)49;.typedef struct / 鏈表類(lèi)型鏈表類(lèi)型 Link head,

47、 tail; / 分別指向頭結(jié)點(diǎn)和分別指向頭結(jié)點(diǎn)和 / 最后一個(gè)結(jié)點(diǎn)的指針最后一個(gè)結(jié)點(diǎn)的指針 int len; / 指示鏈表長(zhǎng)度指示鏈表長(zhǎng)度 Link current; / 指向當(dāng)前被訪問(wèn)的結(jié)點(diǎn)指向當(dāng)前被訪問(wèn)的結(jié)點(diǎn) /的指針，初始位置指向頭結(jié)點(diǎn)的指針，初始位置指向頭結(jié)點(diǎn) LinkList;50;.鏈表的基本操作鏈表的基本操作: : 結(jié)構(gòu)初始化和銷(xiāo)毀結(jié)構(gòu)結(jié)構(gòu)初始化和銷(xiāo)毀結(jié)構(gòu) Status InitList( LinkList &L ); / 構(gòu)造一個(gè)空的線性鏈表構(gòu)造一個(gè)空的線性鏈表 L，其頭指針、，其頭指針、 / 尾指針和當(dāng)前指針均指向頭結(jié)點(diǎn)，尾指針和當(dāng)前指針均指向頭結(jié)點(diǎn)， / 表長(zhǎng)為零

48、。表長(zhǎng)為零。Status DestroyList( LinkList &L ); / 銷(xiāo)毀線性鏈表銷(xiāo)毀線性鏈表 L，L不再存在。不再存在。 O(1) O(n)51;. 引用型操作引用型操作 Status ListEmpty ( LinkList L ); /判表空判表空int ListLength( LinkList L ); / 求表長(zhǎng)求表長(zhǎng)Status Prior( LinkList L ); / 改變當(dāng)前指針指向其前驅(qū)改變當(dāng)前指針指向其前驅(qū)Status Next ( LinkList L ); / 改變當(dāng)前指針指向其后繼改變當(dāng)前指針指向其后繼ElemType GetCurElem

49、 ( LinkList L ); / 返回當(dāng)前指針?biāo)笖?shù)據(jù)元素返回當(dāng)前指針?biāo)笖?shù)據(jù)元素O(1)O(1)O(n)O(1)O(1)52;. Status LocatePos( LinkList L, int i ); / 改變當(dāng)前指針指向第改變當(dāng)前指針指向第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType); / 若存在與若存在與e 滿足函數(shù)滿足函數(shù)compare( )判定關(guān)系的元判定關(guān)系的元 / 素，則移動(dòng)當(dāng)前指針指向第素，則移動(dòng)當(dāng)前指針指向第1個(gè)滿足條件的個(gè)滿足條件的 /

50、 元素的前驅(qū)，并返回元素的前驅(qū)，并返回OK; 否則返回否則返回ERRORStatus ListTraverse(LinkList L, Status(*visit)() ); / 依次對(duì)依次對(duì)L的每個(gè)元素調(diào)用函數(shù)的每個(gè)元素調(diào)用函數(shù)visit()O(n)O(n)O(n)53;. 加工型操作加工型操作Status ClearList ( LinkList &L ); / 重置重置 L 為空表為空表Status SetCurElem(LinkList &L, ElemType e ); / 更新當(dāng)前指針?biāo)笖?shù)據(jù)元素更新當(dāng)前指針?biāo)笖?shù)據(jù)元素Status Append ( LinkLis

51、t &L, Link s ); / 在表尾結(jié)點(diǎn)之后鏈接一串結(jié)點(diǎn)在表尾結(jié)點(diǎn)之后鏈接一串結(jié)點(diǎn)Status InsAfter ( LinkList &L, Elemtype e ); / 將元素將元素 e 插入在當(dāng)前指針之后插入在當(dāng)前指針之后Status DelAfter ( LinkList &L, ElemType& e ); / 刪除當(dāng)前指針之后的結(jié)點(diǎn)刪除當(dāng)前指針之后的結(jié)點(diǎn) O(1)O(n) O(s) O(1) O(1)54;.Status InsAfter( LinkList& L, ElemType e ) / 若當(dāng)前指針在鏈表中，則將數(shù)據(jù)元素若當(dāng)前

52、指針在鏈表中，則將數(shù)據(jù)元素e插入在線性鏈插入在線性鏈 / 表表L中當(dāng)前指針?biāo)附Y(jié)點(diǎn)之后中當(dāng)前指針?biāo)附Y(jié)點(diǎn)之后,并返回并返回OK; / 否則返回否則返回ERROR。 / InsAfter if ( ! L.current ) return ERROR; if (! MakeNode( s, e) ) return ERROR; s-next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; +L.len; return OK;55;.Status DelAfter( L

53、inkList& L, ElemType& e ) / / 若當(dāng)前指針及其后繼在鏈表中，則刪除線性鏈表若當(dāng)前指針及其后繼在鏈表中，則刪除線性鏈表L L中當(dāng)前中當(dāng)前 / / 指針?biāo)附Y(jié)點(diǎn)之后的結(jié)點(diǎn)，并返回指針?biāo)附Y(jié)點(diǎn)之后的結(jié)點(diǎn)，并返回OK; OK; 否則返回否則返回ERRORERROR。 /DelAfterif ( !(L.current & L.current-next ) ) return ERROR;q = L.current-next;L.current-next = q-next;if (L.tail = q) L.tail = L.current;e=q-da

54、ta; FreeNode(q); L.len=len-1;return OK;56;. 例一例一Status ListInsert_L(LinkList L, int i, ElemType e) / 在帶頭結(jié)點(diǎn)的單鏈線性表在帶頭結(jié)點(diǎn)的單鏈線性表 L 的第的第 i 個(gè)元素之前插入元素個(gè)元素之前插入元素 e / ListInsert_L 利用上述定義的線性鏈表如何完成利用上述定義的線性鏈表如何完成 線性表的其它操作線性表的其它操作 ？if (!LocatePos (L, i-1, h) return ERROR; / i 值不合法，第值不合法，第 i-1 個(gè)結(jié)點(diǎn)不存在個(gè)結(jié)點(diǎn)不存在if (!Mak

55、eNode (s, e) return ERRORInsAfter (h, s); return OK; / 完成插入完成插入57;.Status MergeList_L(LinkList &Lc, LinkList &La,LinkList &Lb ，int (*compare)(ElemType,ElemType) / 歸并有序表歸并有序表 La 和和 Lb , ,生成新的有序表生成新的有序表 Lc, , / 并在歸并之后銷(xiāo)毀并在歸并之后銷(xiāo)毀La 和和 Lb, , / compare 為指定的元素大小判定函數(shù)為指定的元素大小判定函數(shù) / MergeList_L例二例

56、二58;.if ( !InitList(Lc) return ERROR; / 存儲(chǔ)空間分配失敗存儲(chǔ)空間分配失敗while (!( a=MAXC & b=MAXC) / La 或或 Lb 非空非空 LocatePos (La, 0); LocatePos (Lb, 0); / 當(dāng)前指針指向頭結(jié)點(diǎn)當(dāng)前指針指向頭結(jié)點(diǎn)if ( DelAfter( La, e) a = e; / 取得取得 La 表中第一個(gè)元素表中第一個(gè)元素 aelse a = MAXC; / MAXC為常量最大值為常量最大值if ( DelFirst( Lb, e) b = e; / 取得取得 Lb 表中第一個(gè)元素表中第一個(gè)

57、元素 belse b = MAXC; / a 和和 b 為兩表中當(dāng)前比較元素為兩表中當(dāng)前比較元素DestroyList(La); DestroyList(Lb); / 銷(xiāo)毀鏈表銷(xiāo)毀鏈表 La 和和 Lbreturn OK;59;. if (*compare)(a, b) exponPa-expon =、Pb-exponPb-expon等情況，等情況，再?zèng)Q定是將兩系數(shù)域的數(shù)值相加再?zèng)Q定是將兩系數(shù)域的數(shù)值相加（并判其和是否為（并判其和是否為0 0），還是將較高指數(shù)項(xiàng)的結(jié)點(diǎn)插入到新表），還是將較高指數(shù)項(xiàng)的結(jié)點(diǎn)插入到新表c c中。中。3 142 81 0 aPaPa8 14-3 1010 6 bPbPb11 14-3 102 81 0 cPcPc10 6+64;.運(yùn)算效率分析：運(yùn)算效率分析：(1)系數(shù)相加系數(shù)相加0 加法次數(shù)加法次數(shù) min(m, n)其中其中 m m和和n n分別表示表分別表示表A A和表和表B B的結(jié)點(diǎn)數(shù)。的結(jié)點(diǎn)數(shù)。(2)指數(shù)比較指數(shù)比較極端情況是極端情況是表表A A和表和表B B 沒(méi)