第2章線性表2(單鏈表)

1、12.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、單鏈表的存儲(chǔ)結(jié)構(gòu)一、單鏈表的存儲(chǔ)結(jié)構(gòu)二、二、 單單 鏈表的操作實(shí)現(xiàn)鏈表的操作實(shí)現(xiàn)三、鏈表的運(yùn)算效率分析三、鏈表的運(yùn)算效率分析2、單鏈?zhǔn)郊氨硎痉椒?、單鏈?zhǔn)郊氨硎痉椒?1)單鏈表單鏈表:構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針。的指針。其結(jié)構(gòu)特點(diǎn)：其結(jié)構(gòu)特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素在物理上邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。不一定相鄰。如何實(shí)現(xiàn)？通過(guò)來(lái)實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域指針域指針域next或或樣式：樣式：數(shù)據(jù)域：數(shù)據(jù)域：存儲(chǔ)存

2、儲(chǔ)元素?cái)?shù)值數(shù)據(jù)元素?cái)?shù)值數(shù)據(jù)指針域：指針域：存儲(chǔ)直接后繼的存儲(chǔ)直接后繼的存儲(chǔ)位置存儲(chǔ)位置一、一、 單鏈表的存儲(chǔ)結(jié)構(gòu)單鏈表的存儲(chǔ)結(jié)構(gòu)3定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體如下定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體如下:typedef struct Node DataType data; struct Node *next;SLNode; 其中其中, ,datadata域域用來(lái)存放數(shù)據(jù)元素用來(lái)存放數(shù)據(jù)元素, ,nextnext域域用來(lái)存放指向下用來(lái)存放指向下一個(gè)結(jié)點(diǎn)的指針。一個(gè)結(jié)點(diǎn)的指針。4例：請(qǐng)畫出例：請(qǐng)畫出2626個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：該字母表在內(nèi)存中

3、鏈?zhǔn)酱娣诺臉邮脚e例如下： 解：解：該字母表的邏輯結(jié)構(gòu)為：該字母表的邏輯結(jié)構(gòu)為：（ a, b, ,y, za, b, ,y, z）鏈表存放示意圖如下：鏈表存放示意圖如下： a1heada2/an討論討論1 ：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和 。討論討論2：在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置 由由 指示。指示。 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域指針域(鏈域鏈域)51）結(jié)點(diǎn)：）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈

4、表：）鏈表： n n 個(gè)結(jié)點(diǎn)由個(gè)結(jié)點(diǎn)由指針鏈指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)浇M成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像存儲(chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個(gè)指針域的鏈表，稱為有兩個(gè)指針域的鏈表，稱為雙鏈表雙鏈表（但未必是雙向鏈表）（但未必是雙向鏈表）；有多個(gè)指針域的鏈表，稱為有多個(gè)指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2an循環(huán)鏈表循環(huán)鏈表

5、示意圖：示意圖：(2) 與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：64）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)首元結(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)）的指針；的指針；頭結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前是在鏈表的首元結(jié)點(diǎn)之前附設(shè)附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度?？毡順?biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度。首元結(jié)點(diǎn)首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)

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

7、頭結(jié)點(diǎn)頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)，當(dāng)頭有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)結(jié)點(diǎn)的的指針域?yàn)榭罩羔樣驗(yàn)榭諘r(shí)表示空表。時(shí)表示空表。8一個(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ù)域指針域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答

8、：頭指針頭指針是指向鏈?zhǔn)侵赶蜴湵碇斜碇械谝粋€(gè)第一個(gè)結(jié)點(diǎn)的指結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋針，因此關(guān)鍵是要尋找找第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)的的地址地址。7ZHAOH31稱：頭指針?lè)Q：頭指針H的值是的值是31、帶頭結(jié)點(diǎn)單鏈表和不帶頭結(jié)點(diǎn)單鏈表的比較、帶頭結(jié)點(diǎn)單鏈表和不帶頭結(jié)點(diǎn)單鏈表的比較例：例：9上例鏈表的邏輯結(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)10對(duì)比帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過(guò)程和對(duì)比帶頭結(jié)點(diǎn)的單鏈表的插入、

9、刪除過(guò)程和不帶帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過(guò)程，可以不帶帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過(guò)程，可以得知：若設(shè)計(jì)的單鏈表得知：若設(shè)計(jì)的單鏈表帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)，則無(wú)論是在第，則無(wú)論是在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入還是在其他數(shù)據(jù)元素結(jié)一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入還是在其他數(shù)據(jù)元素結(jié)點(diǎn)前點(diǎn)前插入都不會(huì)改變頭指針的數(shù)值插入都不會(huì)改變頭指針的數(shù)值。若設(shè)計(jì)的單。若設(shè)計(jì)的單鏈表鏈表不帶頭結(jié)點(diǎn)不帶頭結(jié)點(diǎn)，則在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插，則在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入與在其他數(shù)據(jù)元素結(jié)點(diǎn)前入與在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入其算法的處理方插入其算法的處理方法不同法不同。在單鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)類似。因此，。在單鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)類似。因此

10、，單鏈表一般構(gòu)造成單鏈表一般構(gòu)造成帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)的單鏈表的單鏈表。11討論: 鏈表的數(shù)據(jù)元素有鏈表的數(shù)據(jù)元素有兩個(gè)域兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)，不再是簡(jiǎn)單數(shù)據(jù)類型，類型，編程編程時(shí)該如何表示？時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用以要采用數(shù)據(jù)類型。數(shù)據(jù)類型。答：答：以以2626個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型字符型指針型指針型設(shè)每個(gè)結(jié)點(diǎn)用變量設(shè)每個(gè)結(jié)點(diǎn)用變量表示，其指表示，其指針用針用 表示，兩個(gè)分量分別用表示，兩個(gè)分量分別用和和表示，這兩個(gè)分量如何賦值？表示

11、，這兩個(gè)分量如何賦值？p方式方式1： 直接表示為直接表示為 node.data；node.next=方式方式2：p指向結(jié)點(diǎn)首地址，然后指向結(jié)點(diǎn)首地址，然后 p-data=; p-next= ; 方式方式3： p指向結(jié)點(diǎn)首地址，然后指向結(jié)點(diǎn)首地址，然后 (*p).data=； (*p).nextb12設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個(gè)元素的指針個(gè)元素的指針, ,則第則第i i個(gè)元素的個(gè)元素的數(shù)據(jù)域?qū)憺閿?shù)據(jù)域?qū)憺?，指針域?qū)憺?，指針域?qū)憺?。練習(xí)：練習(xí)：p-dataai的值的值p-nextai+1的地址的地址附附1：介紹介紹C的三個(gè)有用的庫(kù)函數(shù)的三個(gè)有用的庫(kù)函數(shù)/算符（都在算符（都在

12、中）：中）：sizeof(x)計(jì)算變量計(jì)算變量x x的長(zhǎng)度（字節(jié)數(shù)）；的長(zhǎng)度（字節(jié)數(shù)）；malloc(m) 開辟開辟m m字節(jié)長(zhǎng)度的地址空間，并返回這段空間字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；的首地址；free(p) 釋放指針釋放指針p p所指變量的存儲(chǔ)空間，即徹底刪除所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。一個(gè)變量。13sizeof(x)計(jì)算計(jì)算x x的長(zhǎng)度的長(zhǎng)度malloc(m) 開開m m字節(jié)字節(jié)空間空間free(p) 刪除一個(gè)變量刪除一個(gè)變量問(wèn)問(wèn)1：自定義結(jié)構(gòu)類型變量自定義結(jié)構(gòu)類型變量node的長(zhǎng)度的長(zhǎng)度m是多少？是多少？問(wèn)問(wèn)2：結(jié)構(gòu)變量結(jié)構(gòu)變量node的首地址的首地址(指針指

13、針p）是多少？）是多少？問(wèn)問(wèn)3：怎樣刪除結(jié)構(gòu)變量怎樣刪除結(jié)構(gòu)變量node？*nextdatanode，長(zhǎng)度為長(zhǎng)度為m字節(jié)字節(jié)pmsizeof(node) /單位是字節(jié)單位是字節(jié)p(node*)malloc(m)free(p) /只能借助只能借助node的指針刪除！的指針刪除！p-data=a; p-data=a; p-next=qnext=q14 對(duì)于指向結(jié)構(gòu)類型的指針變量，可說(shuō)明為：對(duì)于指向結(jié)構(gòu)類型的指針變量，可說(shuō)明為： *p, *q; /或用或用 struct SLNode *p , *q; /注：上面已經(jīng)定義了注：上面已經(jīng)定義了SLNSLNode為用戶自定義的為用戶自定義的NodeNod

14、e類型。類型。 類型定義和變量說(shuō)明可以合寫為：類型定義和變量說(shuō)明可以合寫為： Node /Node/Node是自定義結(jié)構(gòu)類型名稱是自定義結(jié)構(gòu)類型名稱 DataType data; /定義數(shù)據(jù)域的變量名及其類型定義數(shù)據(jù)域的變量名及其類型 Node *next; /定義指針域的變量名及其類型定義指針域的變量名及其類型SLNode，*p; /SLNodeSLNode是是NodeNode結(jié)構(gòu)類型的類型替代結(jié)構(gòu)類型的類型替代, , * *p p是指針型的是指針型的NodeNode結(jié)構(gòu)類型的替代結(jié)構(gòu)類型的替代附附2： 補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法表示法1516例：例： 單鏈表的建立和輸出單

15、鏈表的建立和輸出例：用單鏈表結(jié)構(gòu)來(lái)存放例：用單鏈表結(jié)構(gòu)來(lái)存放26個(gè)英文字母組成的個(gè)英文字母組成的線性表（線性表（a，b，c，z）,請(qǐng)寫出請(qǐng)寫出C語(yǔ)言程序。語(yǔ)言程序。實(shí)現(xiàn)思路：實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個(gè)結(jié)點(diǎn)開辟存儲(chǔ)先開辟頭指針，然后陸續(xù)為每個(gè)結(jié)點(diǎn)開辟存儲(chǔ)空間并及時(shí)賦值，后繼結(jié)點(diǎn)的地址要空間并及時(shí)賦值，后繼結(jié)點(diǎn)的地址要提前提前送給前面的指針。送給前面的指針。先挖先挖“坑坑”, ,后種后種“蘿蘿卜卜”！17typedef struct nodechar data; struct node *next;node; 將全局變量及函數(shù)提前說(shuō)明：將全局變量及函數(shù)提前說(shuō)明：node *p,*q,*

16、head; /一般需要一般需要3 3個(gè)指針變量個(gè)指針變量int n ; / / 數(shù)據(jù)元素的個(gè)數(shù)數(shù)據(jù)元素的個(gè)數(shù)int m=sizeof(node); / /* *結(jié)構(gòu)類型定義好之后，結(jié)構(gòu)類型定義好之后，每個(gè)每個(gè)nodenode類型類型的長(zhǎng)的長(zhǎng)度就固定了，度就固定了，m m求一次即可求一次即可* */ /18新手特別容易忘記！新手特別容易忘記！ 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)值為字符ap-next=(node*)malloc(m

17、); /為后繼結(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( ) /字母鏈表的生成字母鏈表的生成。要一個(gè)個(gè)慢慢鏈入要一個(gè)個(gè)慢慢鏈入19p=head;while (p) /當(dāng)指針不空時(shí)循環(huán)（僅限于當(dāng)指針不空時(shí)循環(huán)（僅限于無(wú)頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)的情況）的情況） printf(%c,p-data); p=p-next; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” 討論：

18、要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？ sum+;sum+;sum=0;sum=0;void display() /*字母鏈表的輸出字母鏈表的輸出*/20void main( )void main( ) build( ); build( ); display( ); display( ); 問(wèn)：上述建立的單鏈表帶頭結(jié)點(diǎn)嗎？問(wèn)：上述建立的單鏈表帶頭結(jié)點(diǎn)嗎？21二、單鏈表的操作實(shí)現(xiàn)二、單鏈表的操作實(shí)現(xiàn)定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體如下定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體如下: :t typedef struct Node DataType data; struct Nod

19、e *next;SLNode;、初始化、初始化void ListInitiate(SLNode *head)*初始化*/ /*如果有內(nèi)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/if(*head = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);(*head)-next = NULL; /*置鏈尾標(biāo)記NULL */22、求單鏈表中數(shù)據(jù)元素的個(gè)數(shù)、求單鏈表中數(shù)據(jù)元素的個(gè)數(shù)int ListLength(SLNode int ListLength(SLNode * *head)head) SLNode SLNode * *p = head;

20、p = head;/ /* *p p指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)* */ /int size = 0;int size = 0;/ /* *sizesize初始為初始為0 0* */ / while(p-next != NULL) /while(p-next != NULL) /* *循環(huán)計(jì)數(shù)循環(huán)計(jì)數(shù)* */ / p = p-next;p = p-next;size +;size +; return size;return size; 23在鏈表中插入一個(gè)元素在鏈表中插入一個(gè)元素X X 的示意圖如下：的示意圖如下：X Xqabp鏈表插入的核心語(yǔ)句：鏈表插入的核心語(yǔ)句：p-nextp-nextX X 結(jié)

21、點(diǎn)的生成方式：結(jié)點(diǎn)的生成方式：m=m=sizeof(SLNode); q=(SLNode *)malloc(m);q-data=X X ;q-next= ?bapX X 、向單鏈表中插入一個(gè)元素、向單鏈表中插入一個(gè)元素24int ListInsert(SLNode int ListInsert(SLNode * *head, int i, DataType x)head, int i, DataType x) SLNode SLNode * *p, p, * *q; q; int j; int j; p = head;p = head;j = -1;j = -1; while(p-next !

22、= NULL & j next != NULL & j next; j+;p = p-next; j+; if(j != i - 1)if(j != i - 1)printf(printf(插入位置參數(shù)錯(cuò)！插入位置參數(shù)錯(cuò)！););return 0; return 0; (2)(2) if(q = (SLNode if(q = (SLNode * *)malloc(sizeof(SLNode) = NULL) )malloc(sizeof(SLNode) = NULL) exit(1); exit(1);q-data = x;q-data = x;(3)(3) q-next =

23、p-next;q-next = p-next;p-next = q; (4)p-next = q; (4)return 1; return 1; 注：此單鏈表是帶頭結(jié)點(diǎn)的注：此單鏈表是帶頭結(jié)點(diǎn)的25在鏈表中刪除某元素在鏈表中刪除某元素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) ； /徹底釋放徹底

24、釋放b b結(jié)點(diǎn)空間結(jié)點(diǎn)空間p-next思考：思考： 省略省略free(q)語(yǔ)句語(yǔ)句行不行？行不行？(p-next) - nextq、從、從 單鏈表中刪除一個(gè)元素單鏈表中刪除一個(gè)元素26int ListDelete(SLNode int ListDelete(SLNode * *head, int i, DataType head, int i, DataType * *x)x) SLNode SLNode * *p, p, * *s;s;int j;int j;(1) p = head;(1) p = head; j = -1;j = -1;while(p-next != NULL &

25、 p-next-next!= NULL while(p-next != NULL & p-next-next!= NULL & j i - 1) & j next;p = p-next;j+;j+; if(j != i - 1)if(j != i - 1) printf(“printf(“插入位置參數(shù)錯(cuò)！插入位置參數(shù)錯(cuò)！”););return 0;return 0; (2)(2)s = p-next; s = p-next; * *x = s-data; x = s-data; (3) (3) p-next = p-next-next;p-next = p-next-n

26、ext;free(s); free(s); return 1;return 1; 27三、單鏈表的操作效率分析三、單鏈表的操作效率分析（1） 查找查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為查找的時(shí)間復(fù)雜度為 O(n)。時(shí)間效率分析時(shí)間效率分析（2） 插入和刪除插入和刪除 因線性鏈表不需要移動(dòng)元素，只要修改指針，僅就插入或刪因線性鏈表不需要移動(dòng)元素，只要修改指針，僅就插入或刪除而言，時(shí)間復(fù)雜度為除而言，時(shí)間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進(jìn)行在某結(jié)點(diǎn)但是，如果要在單鏈表中進(jìn)行在某結(jié)點(diǎn)前前插或刪除操作，插或

27、刪除操作，因?yàn)橐驗(yàn)橐獜念^查找前驅(qū)從頭查找前驅(qū)結(jié)點(diǎn)，所以一般情況下，結(jié)點(diǎn)，所以一般情況下，單鏈表插單鏈表插入和刪除操作入和刪除操作的時(shí)間復(fù)雜度是的時(shí)間復(fù)雜度是 O(n)（同順序表）。（同順序表）。28五、循環(huán)單鏈表五、循環(huán)單鏈表xheada0an循環(huán)鏈表循環(huán)鏈表示意圖：示意圖：循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點(diǎn)是鏈表中循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點(diǎn)是鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域不再是結(jié)束標(biāo)記，而是指向整個(gè)鏈表的最后一個(gè)結(jié)點(diǎn)的指針域不再是結(jié)束標(biāo)記，而是指向整個(gè)鏈表的第一個(gè)結(jié)點(diǎn)，從而使鏈表形成一個(gè)環(huán)。的第一個(gè)結(jié)點(diǎn)，從而使鏈表形成一個(gè)環(huán)。問(wèn)：帶頭結(jié)點(diǎn)的循環(huán)單鏈表的插入、刪除算法如何寫？問(wèn)：帶頭結(jié)點(diǎn)的循環(huán)單鏈表的插入、刪除算法如何寫？29例例2 2：試用試用C C語(yǔ)言編寫一個(gè)算法，將一循環(huán)