第2章(3)_線性鏈表

1、 河南科技大學計算機系第2章 數(shù)據(jù)結(jié)構(gòu)-線性鏈表軟件技術(shù)基礎第第2 2頁頁本單元要點n線性鏈表及其運算線性鏈表及其運算n鏈棧鏈棧n鏈隊列鏈隊列n循環(huán)鏈表循環(huán)鏈表第第3 3頁頁（一）線性表的鏈式存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)容易實現(xiàn)，可以隨機存取線性表的順序存儲結(jié)構(gòu)容易實現(xiàn)，可以隨機存取表中的任意元素。表中的任意元素。鏈表存儲結(jié)構(gòu)在這兩個方面恰好是優(yōu)點：n容易插入、刪除操作n不需要預分空間。順序表缺點是：n難于插入、刪除操作；n需要預先分配空間，不管這些空間能否最大限度地利用。第第4 4頁頁鏈式存儲結(jié)構(gòu)特點鏈式存儲結(jié)構(gòu)特點其結(jié)點在存儲器中的位置是其結(jié)點在存儲器中的位置是隨意隨意的，的，即邏輯上相鄰

2、的數(shù)邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。據(jù)元素在物理上不一定相鄰。如何實現(xiàn)？通過來實現(xiàn)！讓每個存儲結(jié)點都包含兩部分：讓每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域指針指針指針指針指針指針或或樣式：樣式：數(shù)據(jù)域：數(shù)據(jù)域：存儲存儲元素數(shù)值數(shù)據(jù)元素數(shù)值數(shù)據(jù)指針域：指針域：存儲直接后繼或存儲直接后繼或者直接前驅(qū)的存儲位置者直接前驅(qū)的存儲位置設計思想：犧牲空間效率換取時間效率設計思想：犧牲空間效率換取時間效率1. 鏈表的表示鏈表的表示第第5 5頁頁例：請畫出例：請畫出26 個英文字母表的鏈式存儲結(jié)構(gòu)。個英文字母表的鏈式存儲結(jié)構(gòu)。該字母表在內(nèi)存中鏈式存放的樣式舉例如下：該字母表在內(nèi)存中鏈式存

3、放的樣式舉例如下： 解：該字母表的邏輯結(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é)點的存儲位置 由由 指示。指示。 其直接前驅(qū)結(jié)點的鏈域的值其直接前驅(qū)結(jié)點的鏈域的值指針域指針域(鏈域鏈域)第第6 6頁頁1）結(jié)點：）結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；成

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

5、與鏈式存儲有關(guān)的術(shù)語第第7 7頁頁4）頭指針、頭結(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)只放空表標志和表長等信息，它不計入表長度。標志和表長等信息，它不計入表長度。首元結(jié)點首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素是指鏈表中存儲線性表第一個數(shù)據(jù)元素a a1 1的結(jié)點。的結(jié)點。 示意圖如下：示意圖如下：第第8 8

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

7、，當頭有頭結(jié)點時，當頭結(jié)點結(jié)點的的指針域為空指針域為空時表示空表。時表示空表。第第9 9頁頁上例鏈表的邏輯結(jié)構(gòu)示意圖有以下上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式兩種形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無頭結(jié)點無頭結(jié)點 有頭結(jié)點有頭結(jié)點第第10 10頁頁討論: 鏈表的數(shù)據(jù)元素有鏈表的數(shù)據(jù)元素有兩個域兩個域，不再是簡單數(shù)據(jù)，不再是簡單數(shù)據(jù)類型，類型，編程編程時該如何表示？時該如何表示？因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用以要

8、采用數(shù)據(jù)類型。數(shù)據(jù)類型。答：答：以以2626個字母的鏈表為例，每個結(jié)點都有兩個分量：個字母的鏈表為例，每個結(jié)點都有兩個分量：字符型指針型設每個結(jié)點用變量設每個結(jié)點用變量表示，其指表示，其指針用針用 表示，兩個分量分別用表示，兩個分量分別用和和表示，這兩個分量如何賦值？表示，這兩個分量如何賦值？p方式方式1： 直接表示為直接表示為 node.data；node.next=方式方式2：p指向結(jié)點首地址，然后指向結(jié)點首地址，然后 p-data=; p-next= ; 方式方式3： p指向結(jié)點首地址，然后指向結(jié)點首地址，然后 (*p).data=； (*p).nextb第第11 11頁頁設設p p為指

9、向鏈表的第為指向鏈表的第i i個元素的指針個元素的指針, ,則第則第i i個元素的個元素的數(shù)據(jù)域?qū)憺閿?shù)據(jù)域?qū)憺?，指針域?qū)憺椋羔樣驅(qū)憺?。練習：練習：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所指變量的存儲空間，即徹底刪除所指變量的存儲空間，即徹底刪除一個變

10、量。一個變量。第第12 12頁頁sizeof(x)計算x的長度malloc(m) 開m字節(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-n

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

12、 /nodenode是是liuyu結(jié)構(gòu)類型的類型替代結(jié)構(gòu)類型的類型替代, , * *pointerpointer是指針型的是指針型的liuyu結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型* */ / 補充：結(jié)構(gòu)數(shù)據(jù)類型的補充：結(jié)構(gòu)數(shù)據(jù)類型的C表示法表示法第第14 14頁頁單鏈表的抽象數(shù)據(jù)類型描述如下單鏈表的抽象數(shù)據(jù)類型描述如下typedef struct Lnode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct Lnode *next; /指針域指針域Lnode, *LinkList; / *LinkList為為Lnode類型的指針類型的指針如何具體編程來建立如何具體

13、編程來建立和訪問鏈表？和訪問鏈表？鏈表的實現(xiàn)鏈表的實現(xiàn)第第15 15頁頁typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 線性表的單鏈表存儲結(jié)構(gòu)描述:問題討論：問題討論：Q1Q1：第一行的第一行的LnodeLnode 與最后一行的與最后一行的LnodeLnode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LnodeLnode是結(jié)構(gòu)名，后者是結(jié)構(gòu)名，后者LnodeLnode是對整個是對整個structstruct類型的一種類型的一種“縮寫縮寫”，是一種，是一種“新定義名新定義名”，它只

14、，它只是對現(xiàn)有類型名的補充，而不是取代。是對現(xiàn)有類型名的補充，而不是取代。請注意：請注意：typedeftypedef不可能創(chuàng)造不可能創(chuàng)造任何新的數(shù)據(jù)類型，而僅僅是任何新的數(shù)據(jù)類型，而僅僅是在原有的數(shù)據(jù)類型中命名一個在原有的數(shù)據(jù)類型中命名一個新名字，其目的是使你的程序新名字，其目的是使你的程序更易閱讀和移植。更易閱讀和移植。第第16 16頁頁Typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; Q2Q2：為何兩處要同名為何兩處要同名( (Lnode和和Lnode）？）？A2A2：同名是為了表述起來方便

15、。例如，若結(jié)構(gòu)名為同名是為了表述起來方便。例如，若結(jié)構(gòu)名為Lnode ，其新定義名縮寫也最好寫成其新定義名縮寫也最好寫成Lnode ，因為描述的對象相同，因為描述的對象相同，方便閱讀和理解。方便閱讀和理解。Q3Q3：結(jié)構(gòu)體中間的那個：結(jié)構(gòu)體中間的那個structstruct LnodeLnode是何意？是何意？A3A3：在：在“縮寫縮寫” LnodeLnode還沒出現(xiàn)之前，只能用原始的還沒出現(xiàn)之前，只能用原始的struct Lnodestruct Lnode來進行變量說明。此處說明了指針分量的數(shù)來進行變量說明。此處說明了指針分量的數(shù)據(jù)類型是據(jù)類型是structstruct LnodeLnode

16、。typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 第第17 17頁頁2. 鏈表的實現(xiàn)鏈表的實現(xiàn)（1 1） 單鏈表的建立和輸出單鏈表的建立和輸出（2 2） 單鏈表的修改單鏈表的修改（3 3） 單鏈表的插入單鏈表的插入（4 4） 單鏈表的刪除單鏈表的刪除第第18 18頁頁（1）鏈表的動態(tài)生成）鏈表的動態(tài)生成n鏈表是一種動態(tài)存儲結(jié)構(gòu)。因此，建立鏈表的過程是動態(tài)生成的過程。 n 按鏈表結(jié)點建立的順序、方向不同，分為兩種方法：n從前往后的動態(tài)生成法n從后往前的動態(tài)生成法第第19 19頁頁鏈表的動態(tài)生成（方

17、法一）：從前往后鏈表的動態(tài)生成（方法一）：從前往后n算法操作步驟：算法操作步驟：step1 step1 初始化；頭指針置初始化；頭指針置NULLNULLstep2 step2 輸入結(jié)點數(shù)據(jù)輸入結(jié)點數(shù)據(jù),(,(非非0)0)循環(huán)循環(huán) 1)1)使使s s指向新生成的結(jié)點，指向新生成的結(jié)點，s-data = nums-data = num 2) 2)若若 head=NULL(head=NULL(第第1 1個結(jié)點個結(jié)點) ,head=p=s) ,head=p=s，否則，否則 p-next=sp-next=s 3) 3) 指針指針p p始終指向始終指向s , p=ss , p=sstep3 step3 結(jié)

18、束循環(huán)結(jié)束循環(huán),p-next =NULL, ,p-next =NULL, 返回頭指針返回頭指針headhead。shead .pa iai-1a2a1第第2020頁頁鏈表的動態(tài)生成（方法二）：從后往前鏈表的動態(tài)生成（方法二）：從后往前n 算法操作步驟：算法操作步驟：nStep1 Step1 初始化；頭指針置初始化；頭指針置NULLNULLnStep2 Step2 輸入結(jié)點數(shù)據(jù)輸入結(jié)點數(shù)據(jù),(,(非非0)0)循環(huán)循環(huán) 1) 1) 使使s s指向新生成的結(jié)點，指向新生成的結(jié)點， 2) 2) s-data = nums-data = num，s-next = head s-next = head 3

19、) 3)頭指針始終指向頭指針始終指向s s ，head=shead=sn step3 step3 結(jié)束循環(huán)結(jié)束循環(huán), , 返回頭指針返回頭指針headhead。shead . aiai-1a1ai+1第第21 21頁頁單鏈表的建立和輸出舉例單鏈表的建立和輸出舉例例：從鍵盤輸入n個字符，以0作為結(jié)束標記，產(chǎn)生不帶表頭的單鏈表，請寫出C語言程序。（從后往前生成）實現(xiàn)思路：實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲空間并及時賦值，后繼結(jié)點的地址要空間并及時賦值，后繼結(jié)點的地址要提前提前送給前面的指針。送給前面的指針。先挖先挖“坑坑”, ,后種后種“蘿蘿

20、卜卜”！第第2222頁頁Typedef struct Lnode char data; struct Lnode *next; Lnode, *LList; 將全局變量及函數(shù)提前說明：將全局變量及函數(shù)提前說明：int m=sizeof(Lnode); /*結(jié)構(gòu)類型定義好之后，結(jié)構(gòu)類型定義好之后，每個每個LnodeLnode類類型型的長度就固定了，的長度就固定了，m求一次即可求一次即可*/第第2323頁頁char ch;Lnode *head, *s;/*s為工作指針，為工作指針，head為頭指針為頭指針*/head=NULL; /*鏈表開始為空鏈表開始為空*/ printf(“please i

21、nput data,use 0 as the end flagn);scanf(“%c”,&ch); /*輸入字符輸入字符*/ while (ch!=0) s=(Lnode *)malloc(sizeof(Lnode); /*生成新結(jié)點生成新結(jié)點*/ s-data=ch; s-next=head; /*置新結(jié)點的數(shù)據(jù)域和指針域置新結(jié)點的數(shù)據(jù)域和指針域*/ head=s; scanf(%c,&ch);return head;/*返回頭指針返回頭指針*/Lnode *Create( void) /字符鏈表的生成，從后往前生成字符鏈表的生成，從后往前生成或者：或者：s=(Lnode

22、*)malloc(m);或者：或者： LList head, s;第第2424頁頁 Lnode *p; p=head; while (p) /當指針不空時循環(huán)（僅限于當指針不空時循環(huán)（僅限于無頭結(jié)點無頭結(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(Lnode *head) /*鏈表的輸出鏈表的輸出*/第第2525頁頁（2） 單鏈表的修改單鏈表的修改(或讀取

23、或讀取/查找）查找）n 舉例舉例: 設有數(shù)列設有數(shù)列4,5,8,10,21,30,43,59，長度為，長度為8，輸入一個，輸入一個結(jié)點值結(jié)點值30，顯示該結(jié)點的位置。，顯示該結(jié)點的位置。第第2626頁頁算法 單鏈表查找算法 Lnode *get(Lnode *head, char x） Lnode *p=head; /*從頭結(jié)點開始比較從頭結(jié)點開始比較*/ int count= 1; while(p!=NULL)&(p-data!=x) /*直到直到p為為NULL或或p-data是是x為止為止*/ p=p-next; count+; /*掃描下一結(jié)點掃描下一結(jié)點*/ if(p=NULL

24、) printf(找不到該元素找不到該元素n); else printf(找到了，它的位置是找到了，它的位置是:%dn ,count); return p; 第第2727頁頁在鏈表中插入一個元素在鏈表中插入一個元素X X 的示意圖如下：的示意圖如下：X Xsabp鏈表插入的核心語句：鏈表插入的核心語句：p-nexts-nextX X 結(jié)點的生成方式：結(jié)點的生成方式：s=(Lnode*)malloc(m);s-data=X X ;s-next= ?bapX X （3） 單鏈表的插入單鏈表的插入第第2828頁頁單鏈表的插入算法程序(將x插入到值為b的結(jié)點前） LList insert(Lnode

25、*head, char b,char x)Lnode *p,*q;p=(Lnode *)malloc(sizeof(Lnode); /申請一個新結(jié)點申請一個新結(jié)點p-data=x; /置新結(jié)點的數(shù)據(jù)域置新結(jié)點的數(shù)據(jù)域if(head=NULL) /原鏈表為空原鏈表為空 head=p; p-next=NULL; return head;if(head-data=b) /在第一個結(jié)點前插入在第一個結(jié)點前插入 p-next=head; head=p; return head;q=head;while(q-next!=NULL)&(q-next)-data)!=b)q=q-next; /尋找包含

26、元素尋找包含元素b的前一個結(jié)點的前一個結(jié)點qp-next=q-next; q-next=p; /新結(jié)點新結(jié)點p插入到結(jié)點插入到結(jié)點q之后之后return head;第第2929頁頁在鏈表中刪除某元素在鏈表中刪除某元素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é)點空間

27、結(jié)點空間p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - nextq（4） 單鏈表的刪除單鏈表的刪除第第3030頁頁單鏈表的刪除算法程序(刪除單鏈表中值為b的結(jié)點）LList delete(LList head, char b)Lnode *p,*q;if(head=NULL) return head; /鏈表為空，無刪除的元素鏈表為空，無刪除的元素 if(head-data)=b) /刪除第一個結(jié)點刪除第一個結(jié)點 p=head-next; free(head); head=p; return head; q=head;while(q-next!=N

28、ULL)&(q-next)-data)!=b)q=q-next; /尋找包含元素尋找包含元素b的前一個結(jié)點的前一個結(jié)點q if(q-next=NULL) return head; /鏈表中無刪除的元素鏈表中無刪除的元素p=q-next; q-next=p-next; /刪除刪除q的下一個結(jié)點的下一個結(jié)點p free(p); /釋放結(jié)點釋放結(jié)點p的存儲空間的存儲空間return head;第第31 31頁頁3. 鏈表的運算效率分析鏈表的運算效率分析（1） 查找查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為查找的

29、時間復雜度為 O(n)。時間效率分析時間效率分析（2） 插入和刪除插入和刪除 因線性鏈表不需要移動元素，只要修改指針，一般情況下時因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復雜度為間復雜度為 O(1)。但是，如果要在單鏈表中進行但是，如果要在單鏈表中進行前前插或刪除操作，因為要插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復雜度將是從頭查找前驅(qū)結(jié)點，所耗時間復雜度將是 O(n)。第第3232頁頁討論討論1 1： 順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？順序存儲時，順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。

30、順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。缺點是插入或刪除元素時不方便。鏈式存儲時，鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，關(guān)系的指針。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。使用靈活。缺點是存儲密度小，存儲空間利用率低。順序表順序表適宜于做適宜于做查找查找這樣的靜

31、態(tài)操作；這樣的靜態(tài)操作；鏈表鏈表宜于做宜于做插插入、刪除入、刪除這樣的動態(tài)操作。若這樣的動態(tài)操作。若線性表的長度變化不大線性表的長度變化不大，且，且其主要操作是查找，則采用順序表；若其主要操作是查找，則采用順序表；若線性表的長度變化線性表的長度變化較大較大，且其主要操作是插入、刪除操作，則采用鏈表。，且其主要操作是插入、刪除操作，則采用鏈表。第第3333頁頁討論討論2：什么是指針？指針的作用？什么是指針？指針的作用？ 指針指針即變量的內(nèi)存地址。即變量的內(nèi)存地址。指針主要功能指針主要功能有二：有二：提供了一種快速訪問數(shù)組單元的途徑；提供了一種快速訪問數(shù)組單元的途徑；使使C C語言函數(shù)可以修改其調(diào)

32、用的參數(shù)。語言函數(shù)可以修改其調(diào)用的參數(shù)。 & &-指針操作符指針操作符（單目），返回操作數(shù)地址；（單目），返回操作數(shù)地址； *-運算符運算符（單目），是對（單目），是對&的補充，返回位于這個的補充，返回位于這個地址內(nèi)的變量之值。地址內(nèi)的變量之值。例：例： q=*m意即意即“q取地址取地址m中的值中的值”。如果數(shù)值。如果數(shù)值100存存儲在內(nèi)存地址儲在內(nèi)存地址2000中，而這一地址又存在中，而這一地址又存在m中，則中，則q=(2000)=100討論討論3 3：與指針有關(guān)的符號與指針有關(guān)的符號& &和和* *之間有何區(qū)別？之間有何區(qū)別？第第3434頁頁預告第預

33、告第1 1次上機內(nèi)容：次上機內(nèi)容：單鏈表的運算（含鏈表的建立、輸出、查找、插單鏈表的運算（含鏈表的建立、輸出、查找、插入、刪除等）入、刪除等）上機時間：待定上機時間：待定上機地點：待定上機地點：待定第第3535頁頁（二）鏈棧（二）鏈棧(1) 鏈棧的構(gòu)造方式鏈棧的構(gòu)造方式以頭指針為棧頂，以頭指針為棧頂，在頭指針處在頭指針處插入或刪除插入或刪除.Node *st, *p;int m=sizeof(Node); 棧頂棧頂棧底棧底棧也可以用鏈式結(jié)構(gòu)來表示，用鏈式結(jié)構(gòu)來表示的棧就是棧也可以用鏈式結(jié)構(gòu)來表示，用鏈式結(jié)構(gòu)來表示的棧就是鏈棧鏈棧 a1 a2an-1 annextdata鏈棧中每個結(jié)點由兩個域構(gòu)

34、成：鏈棧中每個結(jié)點由兩個域構(gòu)成：datadata域和域和nextnext域，其定義為：域，其定義為：typedef Struct SNode SElemType data; Struct SNode * next; Node;第第3636頁頁Push (SElemType e) p=(Node*)malloc(m); if(!p)上溢上溢else p-data=e; p-next=st; st=p; Status Pop( ) if(st=NULL)下溢下溢elsee=st-data;p=st;st=st-next; free(p); return(e); 插入插入表頭表頭從表頭從表頭刪除刪除

35、(2) 操作操作由此可以看出：一個鏈棧由其由此可以看出：一個鏈棧由其棧頂指針唯一指定棧頂指針唯一指定 設設指向棧頂元素，當指向棧頂元素，當=NULL=NULL時表示棧空時表示?？盏诘?737頁頁鏈棧鏈棧不必設頭結(jié)點不必設頭結(jié)點，因為棧頂（表頭）操作頻繁；，因為棧頂（表頭）操作頻繁；鏈棧一般鏈棧一般不會出現(xiàn)棧滿不會出現(xiàn)棧滿情況，除非沒有空間導致情況，除非沒有空間導致mallocmalloc分配失敗。分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成修改指針即可完成。幾點說明幾點說明:第第3838頁頁鏈鏈隊列隊列類型定義：類型定義

36、： typedef struct QueuePtr front ; /隊首指針隊首指針 QueuePtr rear ; /隊尾指針隊尾指針 LinkQueue;結(jié)點結(jié)點類型定義：類型定義： typedef Struct QNode QElemType data; /元素元素 Struct QNode *next; /指向下一結(jié)點的指針指向下一結(jié)點的指針 Qnode , * QueuePtr ;關(guān)于整個鏈隊的關(guān)于整個鏈隊的總體描述總體描述鏈隊中任一鏈隊中任一結(jié)點的結(jié)構(gòu)結(jié)點的結(jié)構(gòu)第第3939頁頁討論：討論： 空鏈隊的特征？空鏈隊的特征？Q(隊尾隊尾)(隊首隊首)fronta1a2a3rearpfrontrear 怎樣實現(xiàn)鏈隊的怎樣實現(xiàn)鏈隊的入隊和出隊入隊和出隊操作？操作？ 鏈隊會滿嗎？鏈隊會滿嗎？front=rear一般不會，因為刪除時有一般不會，因為刪除時有free動作。除非內(nèi)存不足！動作。除非內(nèi)存不足！入隊（尾部插入）：入隊（尾部插入）：rear-next=S; rear=S;出隊（頭部刪除）：出隊（頭部刪除）：front-next=p-next;SD鏈隊示意圖：鏈隊示意圖：第第4040頁頁（1）單鏈表中存在的問題：）單鏈表中存在的問題：在運算過程中對于空表與對第一在運算過程中對于空表與對第一個結(jié)點的處理必須單獨考慮，從而使空表與非空表