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

1、12.3 線性表的鏈?zhǔn)奖硎竞筒僮?鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)回顧：回顧：2.22.2 線性表的順序表示和操作線性表的順序表示和操作線性表線性表順序存儲(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.3 線性表的鏈?zhǔn)奖硎竞筒僮?2.3 線性

2、表的鏈?zhǔn)奖硎竞筒僮骶€性表的鏈?zhǔn)奖硎竞筒僮?.3.1 鏈表的表示鏈表的表示2.3.2 鏈表的操作鏈表的操作2.3.3 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析2.3 線性表的鏈?zhǔn)奖硎竞筒僮?其結(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ǔ)位置者直

3、接前驅(qū)的存儲(chǔ)位置2.3.1 鏈表的表示鏈表的表示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, 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ǔ)位

4、置 由由 指示。指示。 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域指針域(鏈域鏈域)2.3.1 鏈表的表示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è)指針域的鏈表，稱

5、為有兩個(gè)指針域的鏈表，稱為雙鏈表雙鏈表（但未必是雙向鏈表）（但未必是雙向鏈表）；有多個(gè)指針域的鏈表，稱為有多個(gè)指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2an循環(huán)鏈表循環(huán)鏈表示意圖：示意圖：2.3.1 鏈表的表示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è)的一

6、個(gè)結(jié)點(diǎn)；數(shù)據(jù)域的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計(jì)入表長度。內(nèi)只放空表標(biāo)志和表長等信息，它不計(jì)入表長度。首元結(jié)點(diǎn)首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a a1 1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 示意圖如下：示意圖如下：2.3.1 鏈表的表示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ì)空表

7、、非空表空表、非空表的情況以及對(duì)的情況以及對(duì)首首元結(jié)點(diǎn)元結(jié)點(diǎn)進(jìn)行進(jìn)行統(tǒng)一統(tǒng)一處理，編程更方便。處理，編程更方便。答：答：無頭結(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í)表示空表。2.3.1 鏈表的表示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)用）

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

9、OUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無頭結(jié)點(diǎn)無頭結(jié)點(diǎn) 有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)2.3.1 鏈表的表示11答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = 。 線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(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è)字

10、節(jié)個(gè)字節(jié)）組成，如下圖所示。）組成，如下圖所示。其中指針其中指針X X，Y Y，Z Z的的值值分別為多少？該線性表的分別為多少？該線性表的首結(jié)點(diǎn)起始首結(jié)點(diǎn)起始地址地址為多少？為多少？末結(jié)點(diǎn)的起始地址末結(jié)點(diǎn)的起始地址為多少？為多少？：2.3.1 鏈表的表示12討論: 鏈表的數(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è)分量：個(gè)字母的鏈表為

11、例，每個(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).nextb2.3.1 鏈表的表示13設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個(gè)元素的指針個(gè)元素的指針, ,則第則第i i個(gè)元

12、素的個(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è)變量。2.3.1 鏈表的表示14sizeof(x)計(jì)算計(jì)算x x的長度

13、的長度malloc(m) 開開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=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 鏈表的表示單鏈表的特點(diǎn)：單鏈表的特點(diǎn)： 通過頭結(jié)點(diǎn)（帶頭結(jié)點(diǎn)的單鏈表）或首結(jié)點(diǎn)（不帶頭結(jié)點(diǎn)通過頭結(jié)點(diǎn)（帶頭結(jié)點(diǎn)的單鏈表）或首結(jié)點(diǎn)（不帶頭結(jié)點(diǎn)的單鏈表）指針來標(biāo)識(shí)一個(gè)單鏈表；的單鏈表）指針來標(biāo)識(shí)一個(gè)單鏈表； 從一個(gè)已知結(jié)點(diǎn)出發(fā)，只能訪問該結(jié)點(diǎn)和通過從一個(gè)已知結(jié)點(diǎn)出

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

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

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

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

19、結(jié)點(diǎn) r = L; / r始終指向終端節(jié)點(diǎn)，開始時(shí)指向頭節(jié)點(diǎn) for (i=0; idata = ai; s-next = NULL; r-next = s; /將*s插入在*r之后 r = s; r-next = NULL;本算法的時(shí)間復(fù)雜度為本算法的時(shí)間復(fù)雜度為O(n)O(n)21例：用單鏈表結(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)的地址要提

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個(gè)指針變量個(gè)指針變量int n ; / / 數(shù)據(jù)元素的個(gè)數(shù)數(shù)據(jù)元素的個(gè)數(shù)int m=sizeof(node); / /* *結(jié)構(gòu)類型定義好之后，每個(gè)結(jié)構(gòu)類型定義好之后，每個(gè)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; / 第一個(gè)結(jié)點(diǎn)值為字符第一個(gè)結(jié)點(diǎn)值為字符a p-next=(node*)malloc(m); /為后繼結(jié)點(diǎn)為后繼結(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)的指針域

22、要置空！void build( ) /字母鏈表的生成字母鏈表的生成。要一個(gè)個(gè)慢慢鏈入要一個(gè)個(gè)慢慢鏈入232.3.2 鏈表的操作 p=head; while (p) /當(dāng)指針不空時(shí)循環(huán)（僅限于無頭結(jié)點(diǎn)的情況當(dāng)指針不空時(shí)循環(huán)（僅限于無頭結(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() /字母鏈表的輸出字母鏈表的輸出242.3.2 鏈表的操作2. 單鏈表的讀取和單鏈表的

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

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

25、的刪除在鏈表中刪除某元素在鏈表中刪除某元素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é)點(diǎn)空間p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - nextq272.3.2 鏈表的操作討論：討論： 單鏈表只能查找結(jié)點(diǎn)的直接

26、后繼，若想查找單鏈表只能查找結(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)。282.3.2 鏈表的操作單鏈表的運(yùn)算效率分析單鏈表的運(yùn)算效率分析1. 查找查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為找起，查找的時(shí)間復(fù)雜度為 O(n)。時(shí)間效率分析2

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

28、單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)* *P P，需找到它，需找到它的的 ，其時(shí)間復(fù)雜度為，其時(shí)間復(fù)雜度為 。 O(n)(n)302.3.3 鏈表的運(yùn)算效率分析在雙向鏈表中如何實(shí)現(xiàn)插入和刪除運(yùn)算？在雙向鏈表中如何實(shí)現(xiàn)插入和刪除運(yùn)算？單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點(diǎn)上增加一個(gè)指針域，用來存結(jié)點(diǎn)的直接前驅(qū)，高查找速度，可以在結(jié)點(diǎn)上增加一個(gè)指針域，用來存結(jié)點(diǎn)的直接前驅(qū)，這樣的鏈表，稱為雙向鏈表。其結(jié)點(diǎn)的結(jié)構(gòu)為：這樣的鏈表，稱為雙向鏈表。其結(jié)點(diǎn)的結(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 元素，請(qǐng)?jiān)诘谠?，?qǐng)?jiān)诘?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 個(gè)元素，刪除第個(gè)元素，刪除第 i 個(gè)個(gè) 元素元素注意：要修改注意：要修改雙向指針！雙向指針！33循環(huán)鏈表循環(huán)鏈表34 循環(huán)循環(huán)單單鏈表是將原單鏈表中尾結(jié)點(diǎn)的鏈表是將原單鏈表中尾結(jié)點(diǎn)的nextnext域由域由NULLNULL改為指向頭結(jié)點(diǎn)。改為指向頭結(jié)點(diǎn)。 循環(huán)循環(huán)雙雙鏈表是將原雙鏈表中尾結(jié)點(diǎn)的鏈表是將原雙鏈表中尾結(jié)點(diǎn)的nextnext域由域由NULLNULL改為指向頭結(jié)點(diǎn)改為指向頭結(jié)點(diǎn), ,再將頭節(jié)點(diǎn)的再將頭節(jié)點(diǎn)的priorprior域該為指向尾節(jié)點(diǎn)。域該為指向尾節(jié)點(diǎn)。 循環(huán)循環(huán)雙雙鏈表中某結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件鏈表中某結(jié)點(diǎn)為尾結(jié)點(diǎn)的

32、條件帶頭結(jié)點(diǎn)的循環(huán)雙鏈表帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L L中，某結(jié)點(diǎn)中，某結(jié)點(diǎn)* *p p為尾結(jié)點(diǎn)的條件是：為尾結(jié)點(diǎn)的條件是：p-next = L;p-next = L;35 在循環(huán)在循環(huán)雙雙鏈表中鏈表中插入插入結(jié)點(diǎn)的操作結(jié)點(diǎn)的操作在循環(huán)雙鏈表在循環(huán)雙鏈表* *p p結(jié)點(diǎn)之后插入結(jié)點(diǎn)之后插入* *q q結(jié)點(diǎn)，操作為：結(jié)點(diǎn)，操作為：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é)點(diǎn)的操作結(jié)點(diǎn)

33、的操作在循環(huán)雙鏈表中，刪除在循環(huán)雙鏈表中，刪除* *p p結(jié)點(diǎn)之后的結(jié)點(diǎn)，操作為：結(jié)點(diǎn)之后的結(jié)點(diǎn)，操作為：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é)點(diǎn)的操作結(jié)點(diǎn)的操作在循環(huán)單鏈表中的在循環(huán)單鏈表中的* *p p結(jié)點(diǎn)之后插入結(jié)點(diǎn)之后插入* *q q結(jié)點(diǎn)，操作為：結(jié)點(diǎn)，操作為：q-next = p-next;q-next = p-next;p-next = q;p-next = q; 在循環(huán)在循

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

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

36、。高級(jí)語言中。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 為一個(gè)靜態(tài)鏈表；為一個(gè)靜態(tài)鏈表；S0.curS0.cur則表示第則表示第1 1個(gè)結(jié)點(diǎn)在數(shù)組中的個(gè)結(jié)點(diǎn)在數(shù)組中的位置。位置。說明說明2 2：如果數(shù)組的第如果數(shù)組的第i i個(gè)分量表示鏈表個(gè)分量表示鏈表的第的第k k個(gè)結(jié)點(diǎn)，則：個(gè)結(jié)點(diǎn)，則：Si.dat

37、aSi.data表示第表示第k k個(gè)結(jié)點(diǎn)的數(shù)據(jù)；個(gè)結(jié)點(diǎn)的數(shù)據(jù)；Si.curSi.cur 表示第表示第k+1k+1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( (即即k k的直接的直接后繼后繼) )的位置。的位置。i392.4 應(yīng)用舉例說明說明3 3：靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。動(dòng)元素，只需修改指示器就可以了。例如：在線性表例如：在線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )的的QIAN, SUN之間之間LIU，可以這樣實(shí)現(xiàn)：，可以這樣實(shí)現(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)( (包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。直接后繼。2. 2. 線性表線性表邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：“一對(duì)一一對(duì)一” 或或 “1:11:1”存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)運(yùn) 算：修改、插入、刪除算：修改、插入、

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