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

1、12.3 線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)一、單鏈表的存儲結(jié)構一、單鏈表的存儲結(jié)構二、二、 單單 鏈表的操作實現(xiàn)鏈表的操作實現(xiàn)三、鏈表的運算效率分析三、鏈表的運算效率分析2、單鏈式及表示方法、單鏈式及表示方法(1)單鏈表單鏈表:構成鏈表的結(jié)點只有一個指向直接后繼結(jié)點構成鏈表的結(jié)點只有一個指向直接后繼結(jié)點的指針。的指針。其結(jié)構特點：其結(jié)構特點：邏輯上相鄰的數(shù)據(jù)元素在物理上邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。不一定相鄰。如何實現(xiàn)？通過來實現(xiàn)！讓每個存儲結(jié)點都包含兩部分：讓每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域指針域指針域next或或樣式：樣式：數(shù)據(jù)域：數(shù)據(jù)域：存儲存

2、儲元素數(shù)值數(shù)據(jù)元素數(shù)值數(shù)據(jù)指針域：指針域：存儲直接后繼的存儲直接后繼的存儲位置存儲位置一、一、 單鏈表的存儲結(jié)構單鏈表的存儲結(jié)構3定義單鏈表結(jié)點的結(jié)構體如下定義單鏈表結(jié)點的結(jié)構體如下:typedef struct Node DataType data; struct Node *next;SLNode; 其中其中, ,datadata域域用來存放數(shù)據(jù)元素用來存放數(shù)據(jù)元素, ,nextnext域域用來存放指向下用來存放指向下一個結(jié)點的指針。一個結(jié)點的指針。4例：請畫出例：請畫出2626個英文字母表的鏈式存儲結(jié)構。個英文字母表的鏈式存儲結(jié)構。該字母表在內(nèi)存中鏈式存放的樣式舉例如下：該字母表在內(nèi)存中

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

4、表：）鏈表： n n 個結(jié)點由個結(jié)點由指針鏈指針鏈組成一個鏈表。它是線性表的鏈式組成一個鏈表。它是線性表的鏈式存儲映像存儲映像，稱為線性表的鏈式存儲結(jié)構稱為線性表的鏈式存儲結(jié)構。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點只有一個指針域的鏈表，稱為結(jié)點只有一個指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個指針域的鏈表，稱為有兩個指針域的鏈表，稱為雙鏈表雙鏈表（但未必是雙向鏈表）（但未必是雙向鏈表）；有多個指針域的鏈表，稱為有多個指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2an循環(huán)鏈表循環(huán)鏈表

5、示意圖：示意圖：(2) 與鏈式存儲有關的術語：與鏈式存儲有關的術語：64）頭指針、頭結(jié)點和首元結(jié)點的區(qū)別）頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針頭指針頭結(jié)點頭結(jié)點首元結(jié)點首元結(jié)點a1heada2infoan頭指針頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）的指針；的指針；頭結(jié)點頭結(jié)點是在鏈表的首元結(jié)點之前是在鏈表的首元結(jié)點之前附設附設的一個結(jié)點；數(shù)據(jù)域內(nèi)只放的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息，它不計入表長度?？毡順酥竞捅黹L等信息，它不計入表長度。首元結(jié)點首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素是指鏈表中存儲線性表第一個數(shù)據(jù)

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

7、頭結(jié)點頭指針頭指針頭結(jié)點頭結(jié)點有頭結(jié)點有頭結(jié)點有頭結(jié)點時，當頭有頭結(jié)點時，當頭結(jié)點結(jié)點的的指針域為空指針域為空時表示空表。時表示空表。8一個線性表的邏輯結(jié)構為：一個線性表的邏輯結(jié)構為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構用），其存儲結(jié)構用單鏈表單鏈表表示如下，表示如下，請問其請問其頭指針頭指針的的值值是多少？是多少？存儲地址存儲地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答

8、：頭指針頭指針是指向鏈是指向鏈表中表中第一個第一個結(jié)點的指結(jié)點的指針，因此關鍵是要尋針，因此關鍵是要尋找找第一個結(jié)點第一個結(jié)點的的地址地址。7ZHAOH31稱：頭指針稱：頭指針H的值是的值是31、帶頭結(jié)點單鏈表和不帶頭結(jié)點單鏈表的比較、帶頭結(jié)點單鏈表和不帶頭結(jié)點單鏈表的比較例：例：9上例鏈表的邏輯結(jié)構示意圖有以下上例鏈表的邏輯結(jié)構示意圖有以下兩種形式兩種形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無頭結(jié)點無頭結(jié)點 有頭結(jié)點有頭結(jié)點10對比帶頭結(jié)點的單鏈表的插入、刪除過程和對比帶頭結(jié)點的單鏈表的插入、

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

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

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

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

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

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

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

16、head; /一般需要一般需要3 3個指針變量個指針變量int n ; / / 數(shù)據(jù)元素的個數(shù)數(shù)據(jù)元素的個數(shù)int m=sizeof(node); / /* *結(jié)構類型定義好之后，結(jié)構類型定義好之后，每個每個nodenode類型類型的長的長度就固定了，度就固定了，m m求一次即可求一次即可* */ /18新手特別容易忘記！新手特別容易忘記！ int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出前面已求出p=head;for( i=1; idata=i+a-1; / 第一個結(jié)點值為字符第一個結(jié)點值為字符ap-next=(node*)malloc(m

17、); /為后繼結(jié)點為后繼結(jié)點“挖坑挖坑”！p=p-next； /讓指針變量讓指針變量P指向后一個結(jié)點指向后一個結(jié)點p-data=i+a-1; /最后一個元素要單獨處理最后一個元素要單獨處理p-next=NULL ; / /單鏈表尾結(jié)點的指針域要置空！單鏈表尾結(jié)點的指針域要置空！void build( ) /字母鏈表的生成字母鏈表的生成。要一個個慢慢鏈入要一個個慢慢鏈入19p=head;while (p) /當指針不空時循環(huán)（僅限于當指針不空時循環(huán)（僅限于無頭結(jié)點無頭結(jié)點的情況）的情況） printf(%c,p-data); p=p-next; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” 討論：

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

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

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

21、點的生成方式：結(jié)點的生成方式：m=m=sizeof(SLNode); q=(SLNode *)malloc(m);q-data=X X ;q-next= ?bapX X 、向單鏈表中插入一個元素、向單鏈表中插入一個元素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ù)錯！插入位置參數(shù)錯！););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é)點的注：此單鏈表是帶頭結(jié)點的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) ； /徹底釋放徹底

24、釋放b b結(jié)點空間結(jié)點空間p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - nextq、從、從 單鏈表中刪除一個元素單鏈表中刪除一個元素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ù)錯！插入位置參數(shù)錯！”););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） 查找查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為查找的時間復雜度為 O(n)。時間效率分析時間效率分析（2） 插入和刪除插入和刪除 因線性鏈表不需要移動元素，只要修改指針，僅就插入或刪因線性鏈表不需要移動元素，只要修改指針，僅就插入或刪除而言，時間復雜度為除而言，時間復雜度為 O(1)。但是，如果要在單鏈表中進行在某結(jié)點但是，如果要在單鏈表中進行在某結(jié)點前前插或刪除操作，插或

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