第2章(3)_線性鏈表

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

2、的數(shù)邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過(guò)來(lái)實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(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ǔ)位置設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率1. 鏈表的表示鏈表的表示第第5 5頁(yè)頁(yè)例：請(qǐng)畫出例：請(qǐng)畫出26 個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：該字母表在內(nèi)存中鏈?zhǔn)酱?/p>

3、放的樣式舉例如下： 解：該字母表的邏輯結(jié)構(gòu)為：解：該字母表的邏輯結(jié)構(gòu)為：（ a, b, a, b, ,y, z ,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)的鏈域的值指針域指針域(鏈域鏈域)第第6 6頁(yè)頁(yè)1）結(jié)點(diǎn)：）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；成

4、；2）鏈表：）鏈表： n n 個(gè)結(jié)點(diǎn)由個(gè)結(jié)點(diǎn)由指針鏈指針鏈組成一個(gè)鏈表。它是線性表的組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像鏈?zhǔn)酱鎯?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)鏈表。(2) 與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)

5、與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)第第7 7頁(yè)頁(yè)4）頭指針、頭結(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ù)元素a a1 1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 示意圖如下：示意圖如下：第第8 8

6、頁(yè)頁(yè)答：答：討論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ú)頭結(jié)點(diǎn)頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)

7、，當(dāng)頭有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)結(jié)點(diǎn)的的指針域?yàn)榭罩羔樣驗(yàn)榭諘r(shí)表示空表。時(shí)表示空表。第第9 9頁(yè)頁(yè)上例鏈表的邏輯結(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 10頁(yè)頁(yè)討論: 鏈表的數(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ù)類型通常不一致，所以要采用以要

8、采用數(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è)分量如何賦值？表示，這兩個(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).nextb第第11 11頁(yè)頁(yè)設(shè)設(shè)p p為指

9、向鏈表的第為指向鏈表的第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ù)/算符（都在算符（都在 中）：中）：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è)變

10、量。一個(gè)變量。第第12 12頁(yè)頁(yè)sizeof(x)計(jì)算x的長(zhǎng)度malloc(m) 開m字節(jié)空間free(p) 刪除一個(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的首地址的首地址(指針指針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=P-data=a a; p-next=q; p-n

11、ext=q第第13 13頁(yè)頁(yè) 對(duì)于指向結(jié)構(gòu)類型的指針變量，可說(shuō)明為：對(duì)于指向結(jié)構(gòu)類型的指針變量，可說(shuō)明為：node *p, *q; /或用或用 struct liuyu *p , *q; /注：上面已經(jīng)定義了注：上面已經(jīng)定義了node為用戶自定義的為用戶自定義的liuyu類型。類型。 類型定義和變量說(shuō)明可以合寫為：類型定義和變量說(shuō)明可以合寫為： 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ù)類型* */ / 補(bǔ)充：結(jié)構(gòu)數(shù)據(jù)類型的補(bǔ)充：結(jié)構(gòu)數(shù)據(jù)類型的C表示法表示法第第14 14頁(yè)頁(yè)單鏈表的抽象數(shù)據(jù)類型描述如下單鏈表的抽象數(shù)據(jù)類型描述如下typedef struct Lnode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct Lnode *next; /指針域指針域Lnode, *LinkList; / *LinkList為為L(zhǎng)node類型的指針類型的指針如何具體編程來(lái)建立如何具體

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

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

15、。例如，若結(jié)構(gòu)名為同名是為了表述起來(lái)方便。例如，若結(jié)構(gòu)名為L(zhǎng)node ，其新定義名縮寫也最好寫成其新定義名縮寫也最好寫成Lnode ，因?yàn)槊枋龅膶?duì)象相同，因?yàn)槊枋龅膶?duì)象相同，方便閱讀和理解。方便閱讀和理解。Q3Q3：結(jié)構(gòu)體中間的那個(gè)：結(jié)構(gòu)體中間的那個(gè)structstruct LnodeLnode是何意？是何意？A3A3：在：在“縮寫縮寫” LnodeLnode還沒(méi)出現(xiàn)之前，只能用原始的還沒(méi)出現(xiàn)之前，只能用原始的struct Lnodestruct Lnode來(lái)進(jìn)行變量說(shuō)明。此處說(shuō)明了指針?lè)至康臄?shù)來(lái)進(jìn)行變量說(shuō)明。此處說(shuō)明了指針?lè)至康臄?shù)據(jù)類型是據(jù)類型是structstruct LnodeLnode

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

17、法一）：從前往后鏈表的動(dòng)態(tài)生成（方法一）：從前往后n算法操作步驟：算法操作步驟：step1 step1 初始化；頭指針置初始化；頭指針置NULLNULLstep2 step2 輸入結(jié)點(diǎn)數(shù)據(jù)輸入結(jié)點(diǎn)數(shù)據(jù),(,(非非0)0)循環(huán)循環(huán) 1)1)使使s s指向新生成的結(jié)點(diǎn)，指向新生成的結(jié)點(diǎn)，s-data = nums-data = num 2) 2)若若 head=NULL(head=NULL(第第1 1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)) ,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, 返回頭指針?lè)祷仡^指針headhead。shead .pa iai-1a2a1第第2020頁(yè)頁(yè)鏈表的動(dòng)態(tài)生成（方法二）：從后往前鏈表的動(dòng)態(tài)生成（方法二）：從后往前n 算法操作步驟：算法操作步驟：nStep1 Step1 初始化；頭指針置初始化；頭指針置NULLNULLnStep2 Step2 輸入結(jié)點(diǎn)數(shù)據(jù)輸入結(jié)點(diǎn)數(shù)據(jù),(,(非非0)0)循環(huán)循環(huán) 1) 1) 使使s s指向新生成的結(jié)點(diǎn)，指向新生成的結(jié)點(diǎn)， 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), , 返回頭指針?lè)祷仡^指針headhead。shead . aiai-1a1ai+1第第21 21頁(yè)頁(yè)單鏈表的建立和輸出舉例單鏈表的建立和輸出舉例例：從鍵盤輸入n個(gè)字符，以0作為結(jié)束標(biāo)記，產(chǎn)生不帶表頭的單鏈表，請(qǐng)寫出C語(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)的地址要提前提前送給前面的指針。送給前面的指針。先挖先挖“坑坑”, ,后種后種“蘿蘿

20、卜卜”！第第2222頁(yè)頁(yè)Typedef struct Lnode char data; struct Lnode *next; Lnode, *LList; 將全局變量及函數(shù)提前說(shuō)明：將全局變量及函數(shù)提前說(shuō)明：int m=sizeof(Lnode); /*結(jié)構(gòu)類型定義好之后，結(jié)構(gòu)類型定義好之后，每個(gè)每個(gè)LnodeLnode類類型型的長(zhǎng)度就固定了，的長(zhǎng)度就固定了，m求一次即可求一次即可*/第第2323頁(yè)頁(yè)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é)點(diǎn)生成新結(jié)點(diǎn)*/ s-data=ch; s-next=head; /*置新結(jié)點(diǎn)的數(shù)據(jù)域和指針域置新結(jié)點(diǎn)的數(shù)據(jù)域和指針域*/ head=s; scanf(%c,&ch);return head;/*返回頭指針?lè)祷仡^指針*/Lnode *Create( void) /字符鏈表的生成，從后往前生成字符鏈表的生成，從后往前生成或者：或者：s=(Lnode

22、*)malloc(m);或者：或者： LList head, s;第第2424頁(yè)頁(yè) Lnode *p; p=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; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” 討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？ sum+;sum+;sum=0;sum=0;void display(Lnode *head) /*鏈表的輸出鏈表的輸出*/第第2525頁(yè)頁(yè)（2） 單鏈表的修改單鏈表的修改(或讀取

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

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

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

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

27、結(jié)點(diǎn)空間p-next思考：思考： 省略省略free(q)語(yǔ)句語(yǔ)句行不行？行不行？(p-next) - nextq（4） 單鏈表的刪除單鏈表的刪除第第3030頁(yè)頁(yè)單鏈表的刪除算法程序(刪除單鏈表中值為b的結(jié)點(diǎn)）LList delete(LList head, char b)Lnode *p,*q;if(head=NULL) return head; /鏈表為空，無(wú)刪除的元素鏈表為空，無(wú)刪除的元素 if(head-data)=b) /刪除第一個(gè)結(jié)點(diǎn)刪除第一個(gè)結(jié)點(diǎn) 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的前一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)q if(q-next=NULL) return head; /鏈表中無(wú)刪除的元素鏈表中無(wú)刪除的元素p=q-next; q-next=p-next; /刪除刪除q的下一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)p free(p); /釋放結(jié)點(diǎn)釋放結(jié)點(diǎn)p的存儲(chǔ)空間的存儲(chǔ)空間return head;第第31 31頁(yè)頁(yè)3. 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析（1） 查找查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為查找的

29、時(shí)間復(fù)雜度為 O(n)。時(shí)間效率分析時(shí)間效率分析（2） 插入和刪除插入和刪除 因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進(jìn)行但是，如果要在單鏈表中進(jìn)行前前插或刪除操作，因?yàn)橐寤騽h除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是 O(n)。第第3232頁(yè)頁(yè)討論討論1 1： 順序存儲(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ù)元素，其物理存放地址也相鄰。

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

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

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

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

34、成：鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：datadata域和域和nextnext域，其定義為：域，其定義為：typedef Struct SNode SElemType data; Struct SNode * next; Node;第第3636頁(yè)頁(yè)P(yáng)ush (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) 操作操作由此可以看出：一個(gè)鏈棧由其由此可以看出：一個(gè)鏈棧由其棧頂指針唯一指定棧頂指針唯一指定 設(shè)設(shè)指向棧頂元素，當(dāng)指向棧頂元素，當(dāng)=NULL=NULL時(shí)表示?？諘r(shí)表示?？盏诘?737頁(yè)頁(yè)鏈棧鏈棧不必設(shè)頭結(jié)點(diǎn)不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；，因?yàn)闂ｍ敚ū眍^）操作頻繁；鏈棧一般鏈棧一般不會(huì)出現(xiàn)棧滿不會(huì)出現(xiàn)棧滿情況，除非沒(méi)有空間導(dǎo)致情況，除非沒(méi)有空間導(dǎo)致mallocmalloc分配失敗。分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成修改指針即可完成。幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明:第第3838頁(yè)頁(yè)鏈鏈隊(duì)列隊(duì)列類型定義：類型定義

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