數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：第02章_線性表B

1、12.3 線性表的鏈?zhǔn)奖硎竞筒僮?鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)回顧：回顧：2.22.2 線性表的順序表示和操作線性表的順序表示和操作線性表線性表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)特點特點：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰；也相鄰；優(yōu)點：優(yōu)點：可以隨機存取表中任一元素，方便快捷；可以隨機存取表中任一元素，方便快捷；O(1)O(1)缺點：缺點：在插入或刪除某一元素時，需移動大量元素在插入或刪除某一元素時，需移動大量元素O(n)O(n)解決問題的思路：解決問題的思路：改用另一種線性存儲方式：改用另一種線性存儲方式：2.3 線性表的鏈?zhǔn)奖硎竞筒僮?2.3 線性

2、表的鏈?zhǔn)奖硎竞筒僮骶€性表的鏈?zhǔn)奖硎竞筒僮?.3.1 鏈表的表示鏈表的表示2.3.2 鏈表的操作鏈表的操作2.3.3 鏈表的運算效率分析鏈表的運算效率分析2.3 線性表的鏈?zhǔn)奖硎竞筒僮?其結(jié)點在存儲器中的位置是其結(jié)點在存儲器中的位置是隨意隨意的，即的，即邏輯上相鄰的數(shù)據(jù)元邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰素在物理上不一定相鄰。如何實現(xiàn)？通過來實現(xiàn)！讓每個存儲結(jié)點都包含兩部分：讓每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域指針指針數(shù)據(jù)指針指針數(shù)據(jù)指針指針或或樣式：樣式：數(shù)據(jù)域：數(shù)據(jù)域：存儲存儲元素數(shù)值數(shù)據(jù)元素數(shù)值數(shù)據(jù)指針域：指針域：存儲直接后繼或存儲直接后繼或者直接前驅(qū)的存儲位置者直

3、接前驅(qū)的存儲位置2.3.1 鏈表的表示鏈表的表示2.3.1 鏈表的表示5例：請畫出例：請畫出26 26 個英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。個英文字母表的鏈?zhǔn)酱鎯Y(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 ：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和 。討論討論2：在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位

4、置 由由 指示。指示。 其直接前驅(qū)結(jié)點的鏈域的值其直接前驅(qū)結(jié)點的鏈域的值指針域指針域(鏈域鏈域)2.3.1 鏈表的表示61）結(jié)點：結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：鏈表： n n個結(jié)點由個結(jié)點由指針鏈指針鏈組成一個鏈表。它是線性表的鏈?zhǔn)酱娼M成一個鏈表。它是線性表的鏈?zhǔn)酱鎯τ诚駜τ诚?，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點只有一個指針域的鏈表，稱為結(jié)點只有一個指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個指針域的鏈表，稱

5、為有兩個指針域的鏈表，稱為雙鏈表雙鏈表（但未必是雙向鏈表）（但未必是雙向鏈表）；有多個指針域的鏈表，稱為有多個指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2an循環(huán)鏈表循環(huán)鏈表示意圖：示意圖：2.3.1 鏈表的表示74）頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針頭指針頭結(jié)點頭結(jié)點首元結(jié)點首元結(jié)點a1heada2infoan頭指針頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）的指針；結(jié)點）的指針；頭結(jié)點頭結(jié)點是在鏈表的首元結(jié)點之前是在鏈表的首元結(jié)點之前附設(shè)附設(shè)的一

6、個結(jié)點；數(shù)據(jù)域的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計入表長度。內(nèi)只放空表標(biāo)志和表長等信息，它不計入表長度。首元結(jié)點首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素是指鏈表中存儲線性表第一個數(shù)據(jù)元素a a1 1的結(jié)點。的結(jié)點。 示意圖如下：示意圖如下：2.3.1 鏈表的表示8答：答：討論1. 在鏈表中設(shè)置在鏈表中設(shè)置頭結(jié)點頭結(jié)點有什么好處？有什么好處？討論2. 如何表示如何表示空表空表？頭結(jié)點頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的點的等附加信息，其作用是等附加信息，其作用是為了對鏈表進行操作時，可以對為了對鏈表進行操作時，可以對空表

7、、非空表空表、非空表的情況以及對的情況以及對首首元結(jié)點元結(jié)點進行進行統(tǒng)一統(tǒng)一處理，編程更方便。處理，編程更方便。答：答：無頭結(jié)點時，當(dāng)頭無頭結(jié)點時，當(dāng)頭指針指針的值為的值為空空時表示空表；時表示空表；頭指針頭指針無頭結(jié)點無頭結(jié)點頭指針頭指針頭結(jié)點頭結(jié)點有頭結(jié)點有頭結(jié)點有頭結(jié)點時，當(dāng)頭有頭結(jié)點時，當(dāng)頭結(jié)點結(jié)點的的指針域為空指針域為空時表示空表。時表示空表。2.3.1 鏈表的表示9例例1 1：一個線性表的邏輯結(jié)構(gòu)為：一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用）

8、，其存儲結(jié)構(gòu)用單鏈表單鏈表表示如下，表示如下，請問其請問其頭指針頭指針的的值值是多少？是多少？存儲地址存儲地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：頭指針頭指針是指向鏈表是指向鏈表中中第一個第一個結(jié)點的指針，結(jié)點的指針，因此關(guān)鍵是要尋找因此關(guān)鍵是要尋找第一第一個結(jié)點的地址個結(jié)點的地址。7ZHAOH31稱：頭指針稱：頭指針H的值是的值是31（3）舉例）舉例2.3.1 鏈表的表示10上例鏈表的邏輯結(jié)構(gòu)示意圖有以下上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式兩種形式：ZHAOQIANLISUNZH

9、OUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無頭結(jié)點無頭結(jié)點 有頭結(jié)點有頭結(jié)點2.3.1 鏈表的表示11答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = 。 線性表具有兩種存儲方式，即順序方式和鏈接方式?，F(xiàn)有一個線性表具有兩種存儲方式，即順序方式和鏈接方式?，F(xiàn)有一個具有五個元素的線性表具有五個元素的線性表L=23，17，47，05，31，若它以鏈接方式存儲在下列若它以鏈接方式存儲在下列100119號地址空間號地址空間中，每個結(jié)點由中，每個結(jié)點由數(shù)據(jù)（占數(shù)據(jù)（占2個字節(jié)個字節(jié)）和指針（占）和指針（占2個字

10、節(jié)個字節(jié)）組成，如下圖所示。）組成，如下圖所示。其中指針其中指針X X，Y Y，Z Z的的值值分別為多少？該線性表的分別為多少？該線性表的首結(jié)點起始首結(jié)點起始地址地址為多少？為多少？末結(jié)點的起始地址末結(jié)點的起始地址為多少？為多少？：2.3.1 鏈表的表示12討論: 鏈表的數(shù)據(jù)元素有鏈表的數(shù)據(jù)元素有兩個域兩個域，不再是簡單數(shù)據(jù)，不再是簡單數(shù)據(jù)類型，類型，編程編程時該如何表示？時該如何表示？因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用以要采用數(shù)據(jù)類型。數(shù)據(jù)類型。答：答：以以2626個字母的鏈表為例，每個結(jié)點都有兩個分量：個字母的鏈表為

11、例，每個結(jié)點都有兩個分量：字符型字符型指針型指針型設(shè)每個結(jié)點用變量設(shè)每個結(jié)點用變量表示，其指表示，其指針用針用 表示，兩個分量分別用表示，兩個分量分別用和和表示，這兩個分量如何賦值？表示，這兩個分量如何賦值？p方式方式1： 直接表示為直接表示為 node.data；node.next=方式方式2：p指向結(jié)點首地址，然后指向結(jié)點首地址，然后 p-data=; p-next= ; 方式方式3： p指向結(jié)點首地址，然后指向結(jié)點首地址，然后 (*p).data=； (*p).nextb2.3.1 鏈表的表示13設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個元素的指針個元素的指針, ,則第則第i i個元

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

13、的長度malloc(m) 開開m m字節(jié)字節(jié)空間空間free(p) 刪除一個變量刪除一個變量問問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=P-data=a a; p-next=q; p-next=q2.3.1 鏈表的表示15單

14、鏈表的抽象數(shù)據(jù)類型描述如下單鏈表的抽象數(shù)據(jù)類型描述如下（參見教材參見教材P28P28）：）：Typedef struct LNode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct LNode *next; /指針域指針域LNode, *LinkList; / *LinkList為為LNode類型的指針類型的指針2.3.1 鏈表的表示單鏈表的特點：單鏈表的特點： 通過頭結(jié)點（帶頭結(jié)點的單鏈表）或首結(jié)點（不帶頭結(jié)點通過頭結(jié)點（帶頭結(jié)點的單鏈表）或首結(jié)點（不帶頭結(jié)點的單鏈表）指針來標(biāo)識一個單鏈表；的單鏈表）指針來標(biāo)識一個單鏈表； 從一個已知結(jié)點出發(fā)，只能訪問該結(jié)點和通過從一個已知結(jié)點出

15、發(fā)，只能訪問該結(jié)點和通過nextnext指針訪指針訪問其后繼結(jié)點，無法直接找到該結(jié)點之前的其他結(jié)點；問其后繼結(jié)點，無法直接找到該結(jié)點之前的其他結(jié)點；16如何具體編程來建立和訪問鏈表？如何具體編程來建立和訪問鏈表？鏈表的實現(xiàn)和操作鏈表的實現(xiàn)和操作單鏈表的特點：單鏈表的特點： 在單鏈表中插入一個結(jié)點或刪除一個結(jié)點必須已知其前趨在單鏈表中插入一個結(jié)點或刪除一個結(jié)點必須已知其前趨結(jié)點，插入或刪除操作不需要移動結(jié)點；結(jié)點，插入或刪除操作不需要移動結(jié)點； 單鏈表中每個數(shù)據(jù)結(jié)點都有一個序號單鏈表中每個數(shù)據(jù)結(jié)點都有一個序號i (1in) i (1in) ，對應(yīng)，對應(yīng)邏輯元素邏輯元素a ai i, ,單鏈表中的

16、頭結(jié)點可以看成是第單鏈表中的頭結(jié)點可以看成是第0 0個結(jié)點。個結(jié)點。 a1anL La2(a(a1 1,a,a2 2,a,an n) )將線性表映射成單鏈表將線性表映射成單鏈表17采用采用頭頭插法建立單鏈表：插法建立單鏈表：該方法從一個空表開始，讀取線該方法從一個空表開始，讀取線性表中的元素，生成新結(jié)點性表中的元素，生成新結(jié)點*s，將讀取的數(shù)據(jù)存放到新結(jié)，將讀取的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭，即點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭，即頭結(jié)點之后，直到結(jié)束為止。頭結(jié)點之后，直到結(jié)束為止。1. 單鏈表的建立單鏈表的建立sa1ajL Lai每次將每次將s所指

17、結(jié)點插在最前端所指結(jié)點插在最前端18采用采用頭頭插法建立單鏈表的算法：插法建立單鏈表的算法：void CreateListF(LinkList *&L, ElemType a, int n) LinkList *s; int i; L = (LinkList *)malloc(sizeof (LinkList) ); /創(chuàng)建頭結(jié)點 L-next = NULL; for (i=0; idata = ai; s-next = L-next; /將*s插入在首結(jié)點之前、頭結(jié)點之后 L-next = s; 本算法的時間復(fù)雜度為本算法的時間復(fù)雜度為O(n)O(n)19采用采用尾尾插法建立單鏈表：

18、插法建立單鏈表：該方法將新結(jié)點插到當(dāng)前鏈表的該方法將新結(jié)點插到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前，使其始終指向當(dāng)前鏈表的尾結(jié)點。鏈表的尾結(jié)點。1. 單鏈表的建立單鏈表的建立a1ajL Lais每次將每次將s所指結(jié)點鏈到末尾所指結(jié)點鏈到末尾r20采用采用尾尾插法建立單鏈表的算法：插法建立單鏈表的算法：void CreateListR(LinkList *&L, ElemType a, int n) LinkList *s; int i; L = (LinkList *)malloc(sizeof (LinkList) ); /創(chuàng)建頭

19、結(jié)點 r = L; / r始終指向終端節(jié)點，開始時指向頭節(jié)點 for (i=0; idata = ai; s-next = NULL; r-next = s; /將*s插入在*r之后 r = s; r-next = NULL;本算法的時間復(fù)雜度為本算法的時間復(fù)雜度為O(n)O(n)21例：用單鏈表結(jié)構(gòu)來存放例：用單鏈表結(jié)構(gòu)來存放26個英文字母組成的線個英文字母組成的線性表（性表（a，b，c，z）,請寫出請寫出C語言程序。語言程序。實現(xiàn)思路：實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲空間并及時賦值，后繼結(jié)點的地址要空間并及時賦值，后繼結(jié)點的地址要提

20、前提前送給前面的指針。送給前面的指針。2.3.2 鏈表的操作應(yīng)用：應(yīng)用： 單鏈表的建表和輸出單鏈表的建表和輸出typedef struct node char data; struct node *next;node; 將全局變量及函數(shù)提前說明：將全局變量及函數(shù)提前說明：node *p,*q,*head; /一般需要一般需要3 3個指針變量個指針變量int n ; / / 數(shù)據(jù)元素的個數(shù)數(shù)據(jù)元素的個數(shù)int m=sizeof(node); / /* *結(jié)構(gòu)類型定義好之后，每個結(jié)構(gòu)類型定義好之后，每個nodenode類型的長類型的長 度就固定了，度就固定了，m m求一次即可求一次即可* */ /

21、222.3.2 鏈表的操作新手特別容易忘記！新手特別容易忘記！ int i; head=(node*)malloc(m); /m=sizeof(node) 前面已求出前面已求出 p=head; for( i=1; idata=i+a-1; / 第一個結(jié)點值為字符第一個結(jié)點值為字符a p-next=(node*)malloc(m); /為后繼結(jié)點為后繼結(jié)點“挖坑挖坑”！ p=p-next；/讓指針變量讓指針變量P指向后一個結(jié)點指向后一個結(jié)點 p-data=i+a-1; /最后一個元素要單獨處理最后一個元素要單獨處理 p-next=NULL; / /單鏈表尾結(jié)點的指針域要置空！單鏈表尾結(jié)點的指針域

22、要置空！void build( ) /字母鏈表的生成字母鏈表的生成。要一個個慢慢鏈入要一個個慢慢鏈入232.3.2 鏈表的操作 p=head; while (p) /當(dāng)指針不空時循環(huán)（僅限于無頭結(jié)點的情況當(dāng)指針不空時循環(huán)（僅限于無頭結(jié)點的情況） printf(%c,p-data); p=p-next; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” 討論：要統(tǒng)計鏈表中數(shù)據(jù)元素的個數(shù)，該如何改寫？討論：要統(tǒng)計鏈表中數(shù)據(jù)元素的個數(shù)，該如何改寫？ sum+;sum+;sum=0;sum=0;void display() /字母鏈表的輸出字母鏈表的輸出242.3.2 鏈表的操作2. 單鏈表的讀取和單鏈表的

23、讀取和修改修改思路：思路：要修改第要修改第i i個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點的指針的指針p p，然后才能：，然后才能：p-data=p-data=new_valuenew_value 。缺點：缺點：想尋找單鏈表中第想尋找單鏈表中第i i個元素，只能從頭指針開始逐一個元素，只能從頭指針開始逐一查詢（順藤摸瓜），無法隨機存取。查詢（順藤摸瓜），無法隨機存取。讀取讀取第第i i個數(shù)據(jù)元素的核心語句是：個數(shù)據(jù)元素的核心語句是：Status GetElem_L(LinkList L, int i, ElemType &e) p=L-next;

24、j=1; /假設(shè)是帶有頭結(jié)點的鏈表假設(shè)是帶有頭結(jié)點的鏈表 while(p&jnext; +j; if(!p ji) return ERROR; e=p-data; return OK;252.3.2 鏈表的操作3. 單鏈表的插入單鏈表的插入在鏈表中插入一個元素在鏈表中插入一個元素X X 的示意圖如下：的示意圖如下：X Xsabp鏈表插入的核心語句：鏈表插入的核心語句：p-nexts-nextX X 結(jié)點的生成方式：結(jié)點的生成方式：S=(node*)malloc(m);S-data=X X ;S-next=p-nextbapX X 262.3.2 鏈表的操作4. 4. 單鏈表的刪除單鏈表

25、的刪除在鏈表中刪除某元素在鏈表中刪除某元素b b的示意圖如下：的示意圖如下：c a bp刪除動作的核心語句（要借助輔助指針變量刪除動作的核心語句（要借助輔助指針變量q q）：）：q = p-next; /首先保存首先保存b b的指針，靠它才能找到的指針，靠它才能找到c c；p-next=q-next; /將將a a、c c兩結(jié)點相連，淘汰兩結(jié)點相連，淘汰b b結(jié)點結(jié)點；free(q) ; /徹底釋放徹底釋放b b結(jié)點空間結(jié)點空間p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - nextq272.3.2 鏈表的操作討論：討論： 單鏈表只能查找結(jié)點的直接

26、后繼，若想查找單鏈表只能查找結(jié)點的直接后繼，若想查找結(jié)點的直接前驅(qū)，該如何設(shè)計？結(jié)點的直接前驅(qū)，該如何設(shè)計？答：只要把單鏈表再多開一個指針域即可答：只要把單鏈表再多開一個指針域即可( (例如用例如用* *nextnext和和* *priorprior) ) 。data這種鏈表稱為這種鏈表稱為。其特點是可以雙向查找。其特點是可以雙向查找表中結(jié)點。表中結(jié)點。282.3.2 鏈表的操作單鏈表的運算效率分析單鏈表的運算效率分析1. 查找查找 因線性鏈表只能順序存取，即在查找時要從頭指針因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為找起，查找的時間復(fù)雜度為 O(n)。時間效率分析2

27、. 插入和刪除插入和刪除 因線性鏈表不需要移動元素，只要修改指針，一般因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為情況下時間復(fù)雜度為 O(1)。 但是，如果要在單鏈表中進行前插或刪除操作，因但是，如果要在單鏈表中進行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度將是為要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度將是 O(n)。292.3.3 鏈表的運算效率分析填空：填空：空間效率分析空間效率分析鏈表中每個結(jié)點都要增加一個指針空間，相當(dāng)于總鏈表中每個結(jié)點都要增加一個指針空間，相當(dāng)于總共增加了共增加了n 個整型變量，空間復(fù)雜度為個整型變量，空間復(fù)雜度為 O(n)。在在n n個結(jié)點的

28、單鏈表中要刪除已知結(jié)點個結(jié)點的單鏈表中要刪除已知結(jié)點* *P P，需找到它，需找到它的的 ，其時間復(fù)雜度為，其時間復(fù)雜度為 。 O(n)(n)302.3.3 鏈表的運算效率分析在雙向鏈表中如何實現(xiàn)插入和刪除運算？在雙向鏈表中如何實現(xiàn)插入和刪除運算？單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點上增加一個指針域，用來存結(jié)點的直接前驅(qū)，高查找速度，可以在結(jié)點上增加一個指針域，用來存結(jié)點的直接前驅(qū)，這樣的鏈表，稱為雙向鏈表。其結(jié)點的結(jié)構(gòu)為：這樣的鏈表，稱為雙向鏈表。其結(jié)點的結(jié)構(gòu)為：prior data n

29、exttypedef struct DuLNode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct DuLNode *prior; /前驅(qū)指針域前驅(qū)指針域 struct DuLNode *next; /后繼指針域后繼指針域 DuLNode , *DuLinkList ; 雙向鏈表類型的定義如下：雙向鏈表類型的定義如下：雙鏈表雙鏈表31雙向鏈表的插入操作：雙向鏈表的插入操作：設(shè)設(shè)p已指向第已指向第 i 元素，請在第元素，請在第 i 元素元素前前插入元素插入元素 x ai-1的后繼從 ai ( 指針是p)變?yōu)?x（指針是s) : s-next = p ; p-prior-next =

30、s ; ai 的前驅(qū)從 ai-1 ( 指針是p-prior)變?yōu)?x ( 指針是s); s-prior = p -prior ; p-prior = s ; 注意：要修改注意：要修改雙向指針！雙向指針！x sai-1 ai p指針域的變化指針域的變化：32指針域的變化指針域的變化： 后繼方向：ai-1的后繼由 ai ( 指針p)變?yōu)?ai+1(指針 p -next ); p -prior-next = p-next ; 前驅(qū)方向：ai+1 的前驅(qū)由 ai ( 指針p)變?yōu)閍i-1 (指針 p - prior ); p-next-prior = p -prior ; ai-1 ai+1 ai p

31、雙向鏈表的刪除操作：雙向鏈表的刪除操作：設(shè)設(shè)p指向第指向第 i 個元素，刪除第個元素，刪除第 i 個個 元素元素注意：要修改注意：要修改雙向指針！雙向指針！33循環(huán)鏈表循環(huán)鏈表34 循環(huán)循環(huán)單單鏈表是將原單鏈表中尾結(jié)點的鏈表是將原單鏈表中尾結(jié)點的nextnext域由域由NULLNULL改為指向頭結(jié)點。改為指向頭結(jié)點。 循環(huán)循環(huán)雙雙鏈表是將原雙鏈表中尾結(jié)點的鏈表是將原雙鏈表中尾結(jié)點的nextnext域由域由NULLNULL改為指向頭結(jié)點改為指向頭結(jié)點, ,再將頭節(jié)點的再將頭節(jié)點的priorprior域該為指向尾節(jié)點。域該為指向尾節(jié)點。 循環(huán)循環(huán)雙雙鏈表中某結(jié)點為尾結(jié)點的條件鏈表中某結(jié)點為尾結(jié)點的

32、條件帶頭結(jié)點的循環(huán)雙鏈表帶頭結(jié)點的循環(huán)雙鏈表L L中，某結(jié)點中，某結(jié)點* *p p為尾結(jié)點的條件是：為尾結(jié)點的條件是：p-next = L;p-next = L;35 在循環(huán)在循環(huán)雙雙鏈表中鏈表中插入插入結(jié)點的操作結(jié)點的操作在循環(huán)雙鏈表在循環(huán)雙鏈表* *p p結(jié)點之后插入結(jié)點之后插入* *q q結(jié)點，操作為：結(jié)點，操作為：q-next = p-next;q-next = p-next;p-next-prior = q;p-next-prior = q;q-prior = p;q-prior = p;p-next = q;p-next = q; 在循環(huán)在循環(huán)雙雙鏈表中鏈表中刪除刪除結(jié)點的操作結(jié)點

33、的操作在循環(huán)雙鏈表中，刪除在循環(huán)雙鏈表中，刪除* *p p結(jié)點之后的結(jié)點，操作為：結(jié)點之后的結(jié)點，操作為：q = p-next;q = p-next;p-next = q-next;p-next = q-next;q-next-prior = p;q-next-prior = p;free(q)free(q)36 在循環(huán)在循環(huán)單單鏈表中鏈表中插入插入結(jié)點的操作結(jié)點的操作在循環(huán)單鏈表中的在循環(huán)單鏈表中的* *p p結(jié)點之后插入結(jié)點之后插入* *q q結(jié)點，操作為：結(jié)點，操作為：q-next = p-next;q-next = p-next;p-next = q;p-next = q; 在循環(huán)在循

34、環(huán)單單鏈表中鏈表中刪除刪除結(jié)點的操作結(jié)點的操作在循環(huán)單鏈表中，刪除在循環(huán)單鏈表中，刪除* *p p結(jié)點之后的結(jié)點，操作為：結(jié)點之后的結(jié)點，操作為：q = p-next;q = p-next;p-next = q-next;p-next = q-next;free(q);free(q); 循環(huán)循環(huán)單單鏈表中某結(jié)點為尾結(jié)點的條件鏈表中某結(jié)點為尾結(jié)點的條件帶頭結(jié)點的循環(huán)單鏈表帶頭結(jié)點的循環(huán)單鏈表L L中，某節(jié)點中，某節(jié)點* *p p為尾結(jié)點的條件是：為尾結(jié)點的條件是：p-next = Lp-next = L討論：討論： 若某種高級語言沒有指針類型，能否實若某種高級語言沒有指針類型，能否實現(xiàn)鏈?zhǔn)酱鎯?/p>

35、運算？如何實現(xiàn)？現(xiàn)鏈?zhǔn)酱鎯瓦\算？如何實現(xiàn)？具體實現(xiàn)方法：定義一個結(jié)構(gòu)型數(shù)組（每個元具體實現(xiàn)方法：定義一個結(jié)構(gòu)型數(shù)組（每個元素都含有數(shù)據(jù)域和指示域），就可以完全描述素都含有數(shù)據(jù)域和指示域），就可以完全描述鏈表，指示域就相當(dāng)于動態(tài)鏈表中的指針。鏈表，指示域就相當(dāng)于動態(tài)鏈表中的指針。指示域也常稱為指示域也常稱為“游標(biāo)游標(biāo)”372.4 應(yīng)用舉例動態(tài)鏈表樣式：動態(tài)鏈表樣式：靜態(tài)鏈表樣式：靜態(tài)鏈表樣式：指針指針指針指針指針指針指示指示指示指示指示指示指示指示指示指示數(shù)組中每個元素數(shù)組中每個元素都至少有兩個分都至少有兩個分量，屬于量，屬于結(jié)構(gòu)型結(jié)構(gòu)型數(shù)組數(shù)組。常用于常用于無指針類型無指針類型的的高級語言中

36、。高級語言中。382.4 應(yīng)用舉例例例 ：一：一線性表線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )，用靜態(tài)鏈表如何表示？，用靜態(tài)鏈表如何表示？教材教材P32例題例題 data356042cur說明說明1 1：假設(shè)假設(shè)S S為為SLinkListSLinkList型變量，則型變量，則SMAXSIZESMAXSIZE 為一個靜態(tài)鏈表；為一個靜態(tài)鏈表；S0.curS0.cur則表示第則表示第1 1個結(jié)點在數(shù)組中的個結(jié)點在數(shù)組中的位置。位置。說明說明2 2：如果數(shù)組的第如果數(shù)組的第i i個分量表示鏈表個分量表示鏈表的第的第k k個結(jié)點，則：個結(jié)點，則：Si.dat

37、aSi.data表示第表示第k k個結(jié)點的數(shù)據(jù)；個結(jié)點的數(shù)據(jù)；Si.curSi.cur 表示第表示第k+1k+1個結(jié)點個結(jié)點( (即即k k的直接的直接后繼后繼) )的位置。的位置。i392.4 應(yīng)用舉例說明說明3 3：靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。動元素，只需修改指示器就可以了。例如：在線性表例如：在線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )的的QIAN, SUN之間之間LIU，可以這樣實現(xiàn)：，可以這樣實現(xiàn)：Step2:Step2:將將QIANQIAN的游

38、標(biāo)換為新元素的游標(biāo)換為新元素LIULIU的的下標(biāo)：下標(biāo)：Step1:Step1:將將QIANQIAN的游標(biāo)值存入的游標(biāo)值存入LIULIU的游的游標(biāo)中：標(biāo)中：data240653curi402.4 應(yīng)用舉例本章小結(jié)本章小結(jié)1.1.線性結(jié)構(gòu)線性結(jié)構(gòu)( (包括表、棧、隊、數(shù)組）的定義和特點：包括表、棧、隊、數(shù)組）的定義和特點：僅一個首、尾結(jié)點，其余元素僅一個直接前驅(qū)和一個僅一個首、尾結(jié)點，其余元素僅一個直接前驅(qū)和一個直接后繼。直接后繼。2. 2. 線性表線性表邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：“一對一一對一” 或或 “1:11:1”存儲結(jié)構(gòu)：順序、鏈?zhǔn)酱鎯Y(jié)構(gòu)：順序、鏈?zhǔn)竭\運 算：修改、插入、刪除算：修改、插入、

39、刪除 查找和排序另述查找和排序另述 3.3.順序存儲順序存儲特征：邏輯上相鄰，物理上也相鄰；特征：邏輯上相鄰，物理上也相鄰；優(yōu)點：隨機查找修改快優(yōu)點：隨機查找修改快 O(1)O(1)缺點：插入、刪除慢缺點：插入、刪除慢 O(n)O(n)改進方案：改進方案：41循環(huán)鏈表的特點：循環(huán)鏈表的特點：雙向鏈表的特點：雙向鏈表的特點：可方便可方便靜態(tài)鏈表的特點：靜態(tài)鏈表的特點：不用指針也能實現(xiàn)鏈?zhǔn)酱鎯瓦\算不用指針也能實現(xiàn)鏈?zhǔn)酱鎯瓦\算4.4.鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯μ卣鳎哼壿嬌舷噜?，物理上未必相鄰；特征：邏輯上相鄰，物理上未必相鄰；?yōu)點：插入、刪除快優(yōu)點：插入、刪除快 O(1)O(1)缺點：隨機查找修改慢缺點：隨機查找修改慢 O(n)O(n)5.5.幾種特殊鏈表的特點：幾種特殊鏈表的特點：42討論：討論： 順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別和優(yōu)缺點？順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別和優(yōu)缺點？順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除順