第二章線性表B

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

2、：32.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其結(jié)點(diǎn)在存儲(chǔ)器中的位置是其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意隨意的，即的，即邏輯上相鄰的數(shù)據(jù)元邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過來實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域指針指針數(shù)據(jù)指針指針數(shù)據(jù)指針指針或或樣式：樣式：數(shù)據(jù)域：數(shù)據(jù)域：存儲(chǔ)存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)元素?cái)?shù)值數(shù)據(jù)指針域：指針域：存儲(chǔ)直接后繼或存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置者直接前驅(qū)的存儲(chǔ)位

3、置2.3.1 鏈表的表示鏈表的表示5例：請(qǐng)畫出例：請(qǐng)畫出26 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, ,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)的鏈域的

4、值其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域指針域(鏈域鏈域)61）結(jié)點(diǎn)：結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：鏈表： 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è)指針域的鏈表，稱為雙鏈表雙鏈表（但未必是雙向鏈表）（但未必是

5、雙向鏈表）；有多個(gè)指針域的鏈表，稱為有多個(gè)指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2an循環(huán)鏈表循環(huán)鏈表示圖：示圖：74）頭指針、頭結(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)槭自侵赶蜴湵碇械谝粋€(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)之前是在鏈表的首元結(jié)點(diǎn)之前附設(shè)附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計(jì)入表長度。內(nèi)只放空表標(biāo)志和表

6、長等信息，它不計(jì)入表長度。首元結(jié)點(diǎn)首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a a1 1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 示意圖如下：示意圖如下：8答：答：討論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)一處理，編程更方便。處理，編程更方便。答：

7、答：無頭結(jié)點(diǎn)時(shí)，當(dāng)頭無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針指針的值為的值為空空時(shí)表示空表；時(shí)表示空表；頭指針頭指針無頭結(jié)點(diǎn)無頭結(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í)表示空表。9例例1 1：一個(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)問其請(qǐng)問其頭指針頭指針的的值值是多少？是多少？存儲(chǔ)地址存儲(chǔ)地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域1L

8、I437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：頭指針頭指針是指向鏈?zhǔn)侵赶蜴湵碇斜碇械谝粋€(gè)第一個(gè)結(jié)點(diǎn)的指結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋針，因此關(guān)鍵是要尋找找第一個(gè)結(jié)點(diǎn)的地址第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱：頭指針稱：頭指針H的值是的值是31（3）舉例）舉例10上例鏈表的邏輯結(jié)構(gòu)示意圖有以下上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式兩種形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無頭結(jié)點(diǎn)無頭結(jié)點(diǎn) 有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)11 線性表具有兩種存

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

10、Z= , , 首址首址= = 末址末址= = 。：和和12 對(duì)于指向結(jié)構(gòu)類型的指針變量，可說明為：對(duì)于指向結(jié)構(gòu)類型的指針變量，可說明為： *p, *q; 或用或用 struct *p , *q; 注：上面已經(jīng)定義了注：上面已經(jīng)定義了node為用戶自定義的為用戶自定義的liuyuliuyu類型。類型。 類型定義和變量說明可以合寫為：類型定義和變量說明可以合寫為： liuyu /liuyuliuyu是自定義結(jié)構(gòu)類型名稱是自定義結(jié)構(gòu)類型名稱 char data; /定義數(shù)據(jù)域的變量名及其類型定義數(shù)據(jù)域的變量名及其類型 liuyu *next; /定義指針域的變量名及其類型定義指針域的變量名及其類型n

11、ode，*pointer; /nodenode是是liuyuliuyu結(jié)構(gòu)類型的類型替代結(jié)構(gòu)類型的類型替代 / * *pointerpointer是指針型的是指針型的liuyuliuyu結(jié)構(gòu)類型的替代結(jié)構(gòu)類型的替代附附: 補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法表示法13討論: 鏈表的數(shù)據(jù)元素有鏈表的數(shù)據(jù)元素有兩個(gè)域兩個(gè)域，不再是簡單數(shù)據(jù)，不再是簡單數(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è)分

12、量：個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型字符型指針型指針型設(shè)每個(gè)結(jié)點(diǎn)用變量設(shè)每個(gè)結(jié)點(diǎn)用變量表示，其指表示，其指針用針用 表示，兩個(gè)分量分別用表示，兩個(gè)分量分別用和和表示，這兩個(gè)分量如何賦值？表示，這兩個(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).nextb14設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個(gè)元素的指針個(gè)元素的指針, ,則第則第i i個(gè)元素的

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

14、開開m m字節(jié)字節(jié)空間空間free(p) 刪除一個(gè)變量刪除一個(gè)變量問問1：自定義結(jié)構(gòu)類型自定義結(jié)構(gòu)類型node的長度的長度m是多少？是多少？問問2：結(jié)構(gòu)變量結(jié)構(gòu)變量node的首地址的首地址(指針指針p）是多少？）是多少？問問3：怎樣刪除結(jié)構(gòu)變量怎樣刪除結(jié)構(gòu)變量node？*nextdatanode，長度為長度為m字節(jié)字節(jié)pmsizeof(node) /單位是字節(jié)單位是字節(jié)p(node*)malloc(m)free(p) /只能借助只能借助node的指針刪除！的指針刪除！P-data=a; p-P-data=a; p-next=qnext=q161.單鏈表如何實(shí)現(xiàn)單鏈表如何實(shí)現(xiàn)建表和輸出建表和輸出

15、例：用單鏈表結(jié)構(gòu)來存放例：用單鏈表結(jié)構(gòu)來存放26個(gè)英文字母組成的線個(gè)英文字母組成的線性表（性表（a，b，c，z）,請(qǐng)寫出請(qǐng)寫出C語言程序。語言程序。實(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ù)提前說明：將全局變量及函數(shù)提前說明：node *p,*q,*head; /一般

16、需要一般需要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類型類型的長的長度就固定了，度就固定了，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); /為后繼結(jié)點(diǎn)

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

18、據(jù)元素的個(gè)數(shù)，該如何改寫？討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？ sum+;sum+;sum=0;sum=0;void display() /字母鏈表的輸出字母鏈表的輸出202. 2. 單鏈表的修改單鏈表的修改( (或讀?。┗蜃x?。┧悸罚核悸罚阂薷男薷牡诘趇 i個(gè)數(shù)據(jù)元素，必須從頭指針起一直找個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針到該結(jié)點(diǎn)的指針p p，然后才能：，然后才能：pdata=pdata=new_valuenew_value 。缺點(diǎn)：缺點(diǎn)：想尋找單鏈表中第想尋找單鏈表中第i i個(gè)元素，只能從頭指針開個(gè)元素，只能從頭指針開始逐一查詢（始逐一查詢（順藤摸瓜順藤摸瓜），無

19、法隨機(jī)存取），無法隨機(jī)存取 。讀取讀取第第i i個(gè)數(shù)據(jù)元素的核心語句是：個(gè)數(shù)據(jù)元素的核心語句是：Status GetElem_L(LinkList L, int i, ElemType &e)p=L-next; j=1; /假設(shè)是帶有頭結(jié)點(diǎn)的鏈表假設(shè)是帶有頭結(jié)點(diǎn)的鏈表while(p&jnext; +j;if(!p ji)return ERROR;e=p-data;return OK;213. 3. 單鏈表的插入單鏈表的插入在鏈表中插入一個(gè)元素在鏈表中插入一個(gè)元素X X 的示意圖如下：的示意圖如下：X Xsabp鏈表插入的核心語句：鏈表插入的核心語句：p-nexts-nextX

20、X 結(jié)點(diǎn)的生成方式：結(jié)點(diǎn)的生成方式：S=(node*)malloc(m);S-data=X X ;S-next=p-nextbapX X 224. 4. 單鏈表的刪除單鏈表的刪除在鏈表中刪除某元素在鏈表中刪除某元素b b的示意圖如下：的示意圖如下：c a bp刪除動(dòng)作的核心語句（要借助輔助指針變量刪除動(dòng)作的核心語句（要借助輔助指針變量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 b結(jié)點(diǎn)空間結(jié)

21、點(diǎn)空間p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - nextq235.5.雙鏈表雙鏈表討論：討論： 單鏈表只能查找結(jié)點(diǎn)的直接后繼，若想查找單鏈表只能查找結(jié)點(diǎn)的直接后繼，若想查找結(jié)點(diǎn)的直接前驅(qū)，該如何設(shè)計(jì)？結(jié)點(diǎn)的直接前驅(qū)，該如何設(shè)計(jì)？答：只要把單鏈表再多開一個(gè)指針域即可答：只要把單鏈表再多開一個(gè)指針域即可( (例如用例如用* *nextnext和和* *priorprior) ) 。data這種鏈表稱為這種鏈表稱為。其特點(diǎn)是可以。其特點(diǎn)是可以雙向查找雙向查找表中結(jié)點(diǎn)。表中結(jié)點(diǎn)。24雙向鏈表的插入操作：雙向鏈表的插入操作：設(shè)設(shè)p已指向第已指向第 i

22、元素，請(qǐng)?jiān)诘谠?，?qǐng)?jiān)诘?i 元素元素前前插入元素插入元素 x ai-1的后繼從 ai ( 指針是p)變?yōu)?x（指針是s) : s-next = p ; p-prior-next = s ; ai 的前驅(qū)從 ai-1 ( 指針是p-prior)變?yōu)?x ( 指針是s); s-prior = p -prior ; p-prior = s ; 注意：要修改注意：要修改雙向指針！雙向指針！x sai-1 ai p指針域的變化指針域的變化：25指針域的變化指針域的變化： 后繼方向：ai-1的后繼由 ai ( 指針p)變?yōu)?ai+1(指針 p -next ); p -prior-next = p-nex

23、t ; 前驅(qū)方向：ai+1 的前驅(qū)由 ai ( 指針p)變?yōu)閍i-1 (指針 p - prior ); p-next-prior = p -prior ; ai-1 ai+1 ai p雙向鏈表的刪除操作雙向鏈表的刪除操作：設(shè)設(shè)p指向第指向第 i 個(gè)元素，刪除第個(gè)元素，刪除第 i 個(gè)個(gè) 元素元素注意：要修改注意：要修改雙向指針！雙向指針！262.3.3. 2.3.3. 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析1. 查找查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為找起，查找的時(shí)間復(fù)雜度為 O(n)。時(shí)間效率分析2. 插入和刪除插

24、入和刪除 因線性鏈表不需要移動(dòng)元素，只要修改指針，一般因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為情況下時(shí)間復(fù)雜度為 O(1)。 但是，如果要在單鏈表中進(jìn)行但是，如果要在單鏈表中進(jìn)行前前插或刪除操作，因插或刪除操作，因?yàn)橐獮橐獜念^查找前驅(qū)從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是 O(n)。27例題：例題：在在n n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)* *P P，需找到它，需找到它的的 ，其時(shí)間復(fù)雜度為，其時(shí)間復(fù)雜度為 。 O O(n)(n)28討論：討論： 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別和優(yōu)缺點(diǎn)？順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別和優(yōu)缺點(diǎn)？順序存儲(chǔ)時(shí)，順序存儲(chǔ)時(shí)，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除元素時(shí)不方便。元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存