數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)_嚴(yán)蔚敏版_第2章_線性表_信大(第2講)講解

1、緒論要點(diǎn)回顧 數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用 D_S=( D, S ) 數(shù)據(jù)結(jié)構(gòu)是相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)是相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素 的集合。的集合。 數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)內(nèi)容內(nèi)容數(shù)據(jù)的數(shù)據(jù)的邏輯邏輯結(jié)構(gòu)、結(jié)構(gòu)、存儲(chǔ)存儲(chǔ)結(jié)構(gòu)和結(jié)構(gòu)和運(yùn)算運(yùn)算 算法效率指標(biāo)算法效率指標(biāo)時(shí)間效率和空間效率時(shí)間效率和空間效率 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 邏輯結(jié)構(gòu)唯一邏輯結(jié)構(gòu)唯一 存儲(chǔ)結(jié)構(gòu)不唯一存儲(chǔ)結(jié)構(gòu)不唯一 運(yùn)算的實(shí)現(xiàn)依賴運(yùn)算的實(shí)現(xiàn)依賴 于存儲(chǔ)結(jié)構(gòu)于存儲(chǔ)結(jié)構(gòu) 近期 上課 內(nèi)容 第第2 2章章 線性表線性表 第第3 3章章 棧和隊(duì)

2、列棧和隊(duì)列 第第4 4章章 串串 第第5 5章章 數(shù)組和廣義表數(shù)組和廣義表 線性結(jié)構(gòu) (邏輯、存儲(chǔ)和運(yùn)算) 若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié) 點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè) 直接前趨和一個(gè)直接后繼。 可表示為：(a1 , a2 , , an) 線性結(jié)構(gòu)的定義： 線性結(jié)構(gòu)的特點(diǎn)： 只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)； 除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一 個(gè)直接后繼。個(gè)直接后繼。 線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù) 組等等，其中，最典型、最常用的是- 簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一 的 第二

3、章線性表 第第2章章 線性表線性表 2.1 線性表的類型定義線性表的類型定義 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 圖圖2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 2.1 線性表的類型定義線性表的類型定義 2.1.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) （a1, a2, ai-1， ，ai, ai1 ， ，, an） 線性表的定義：線性表的定義：是是n個(gè)數(shù)據(jù)元素的個(gè)數(shù)據(jù)元素的有限序列有限序列 n=0時(shí)稱為時(shí)稱為 數(shù)據(jù)元素?cái)?shù)據(jù)元素 表頭表頭ai的直接的直接前趨前趨ai的直接的直接后繼后繼 下標(biāo)，下標(biāo)，是元素的是元素的 序號(hào)，表示元

4、素序號(hào)，表示元素 在表中的位置在表中的位置 n為元素總個(gè)為元素總個(gè) 數(shù)，即表長(zhǎng)數(shù)，即表長(zhǎng) 空表空表 表尾表尾 例例1 1 分析分析26 26 個(gè)英文字母組成的英文表個(gè)英文字母組成的英文表 （ A, B, C, D, , Z） 學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí) 541407010126541407010126于春梅于春梅女女 18 1820142014級(jí)計(jì)科 級(jí)計(jì)科1 1班班26 26號(hào) 號(hào) 541407010127541407010127何仕鵬何仕鵬男男 18 1820142014級(jí)計(jì)科 級(jí)計(jì)科1 1班班27 27號(hào) 號(hào) 541407010128541407010128 王王 爽 爽

5、女女 18 1820142014級(jí)計(jì)科 級(jí)計(jì)科1 1班班28 28號(hào) 號(hào) 541407010129541407010129王亞武王亞武男男 18 1820142014級(jí)計(jì)科 級(jí)計(jì)科1 1班班29 29號(hào) 號(hào) ： ： 例例2 分析學(xué)生情況登記表分析學(xué)生情況登記表 數(shù)據(jù)元素都是記錄數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性元素間關(guān)系是線性 數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性元素間關(guān)系是線性 同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性 線性表的特點(diǎn)可概括如下：線性表的特點(diǎn)可概括如下： 同一性同一性 有窮性有窮性 有序性有序性 線性表是最常見的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榫仃嚒?/p>

6、數(shù)組、字符串、線性表是最常見的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榫仃?、?shù)組、字符串、 堆棧、堆棧、 隊(duì)列等都符合線性條件。隊(duì)列等都符合線性條件。 練：判斷下列敘述的正誤： 1. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系， 是用戶按使用需要建立的。是用戶按使用需要建立的。 2. 線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴于計(jì)線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴于計(jì) 算機(jī)。算機(jī)。 3. 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的 數(shù)據(jù)元素的全體。數(shù)據(jù)元素的全體。 4. 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的。線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一

7、的。 5. 一維向量是線性表，但二維或一維向量是線性表，但二維或N維數(shù)組不是。維數(shù)組不是。 6. “同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相 同的特性同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè) 數(shù)都相等。數(shù)都相等。 例例2-1 兩個(gè)集合兩個(gè)集合La和和Lb的合并的合并 假設(shè)兩個(gè)集合假設(shè)兩個(gè)集合La7,2,3Lb8,4,5,6怎樣將他們合并呢？怎樣將他們合并呢？ 1，首先知道，首先知道La的長(zhǎng)度是的長(zhǎng)度是3和和Lb的長(zhǎng)度是的長(zhǎng)度是4 2，之后把，之后把Lb集合中的元素依次和集合中的元素依次和La中的元素進(jìn)行比對(duì)中的元素進(jìn)行比對(duì)

8、形成一個(gè)循環(huán)，首先形成一個(gè)循環(huán)，首先Lb中的中的8與與La的元素依次比對(duì)，的元素依次比對(duì)，8與所有與所有La中中 元素不同，將元素不同，將8插入插入La中，中， 3，2與與2相同進(jìn)入相同進(jìn)入Lb的下一個(gè)元素，都不相同，的下一個(gè)元素，都不相同， 之后將元素合并到之后將元素合并到La中，中， 例例2-2 兩個(gè)非遞減有序的線性表兩個(gè)非遞減有序的線性表La和和Lb的合并的合并 如如La2,4,6Lb4,7,9,10合并合并 1，定義，定義Lc,長(zhǎng)度是長(zhǎng)度是La長(zhǎng)度長(zhǎng)度+Lb長(zhǎng)度長(zhǎng)度 2，La中中2與與Lb中中4，把小，把小La中的中的2的插入的插入Lc，La進(jìn)入下一個(gè)進(jìn)入下一個(gè) 元素元素 3, La中

9、中4與與Lb中中4比較，把比較，把La的的4插入插入Lc,LaLb都下一個(gè)元素都下一個(gè)元素 4,La中中6與與Lb中中7比較，把小的比較，把小的La中的中的6的插入的插入Lc，La進(jìn)入下進(jìn)入下 一個(gè)元素，無(wú)元素了一個(gè)元素，無(wú)元素了 5，就將，就將Lb中剩余元素依次加入中剩余元素依次加入Lc中中 47910 246La Lb Lc 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元依次用一組地址連續(xù)的存儲(chǔ)單元依次 存儲(chǔ)線性表的元素，可通過(guò)存儲(chǔ)線性表的元素，可通過(guò)數(shù)組數(shù)組來(lái)實(shí)現(xiàn)。來(lái)實(shí)現(xiàn)。 把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在

10、物把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物 理上理上相鄰相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)定義：順序存儲(chǔ)定義： 順序存儲(chǔ)方法：順序存儲(chǔ)方法： 簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰 線性表順序存儲(chǔ)特點(diǎn)： 1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰； 2. 若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利 用數(shù)組下標(biāo)）。計(jì)算方法是：用數(shù)組下標(biāo)）。計(jì)算方法是： 設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為L(zhǎng)OC(a1)（稱為首地址），設(shè)每

11、個(gè)元素占用存儲(chǔ)空稱為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空 間（地址長(zhǎng)度）為間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC(ai) = LOC(a1) + L *(i-1) LOC(ai+1) = LOC(ai)+L 它是一種它是一種隨機(jī)存取隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。 注意：C語(yǔ)言中的數(shù)組的下標(biāo)從0開始， 即：Vn的有效范圍是V0Vn-1 線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 a a1 1 a a2 2 a ai i a ai+1 i+1 a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序 1 1 i i 2

12、 2 n n 空閑區(qū)空閑區(qū) i+1i+1 L b=LOC(a1) b + + L L b +(i-1)+(i-1)L L b +(n-1)+(n-1)L L 一個(gè)一維數(shù)組，下標(biāo)的范圍是到，每個(gè)數(shù)組一個(gè)一維數(shù)組，下標(biāo)的范圍是到，每個(gè)數(shù)組 元素用相鄰的元素用相鄰的個(gè)字節(jié)個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ) 數(shù)組元素?cái)?shù)組元素 的第一個(gè)字節(jié)的地址是的第一個(gè)字節(jié)的地址是9898，則，則 的第的第 一個(gè)字節(jié)的地址是一個(gè)字節(jié)的地址是 113 例1 1 因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113 解：解：地址計(jì)算通式為：地址計(jì)算通式為： LOC(ai)

13、 = LOC(a1) + L *（i-1） 用數(shù)組V V來(lái)存放2626個(gè)英文字母組成的線 性表(a(a，b b，c c，z)z)，寫出在順序結(jié)構(gòu)上生 成和顯示該表的C C語(yǔ)言程序。 void build() /*字母線性表的生成，即建表操作*/ int i; V0=a; for(i=1;i=n-1;i+) Vi=Vi-1+1; 核心語(yǔ)句： 法1 Vi= Vi-1+1; 法2 Vi=a+i; 法3 Vi=97+i; 例2 void build(); void display(); #define n 26 int Vn; void main(void) /*主函數(shù)，字母線性表的生成和輸出*/ b

14、uild(); display(); void display() /*字母線性表的顯示，即讀表操作*/ int i; for(i=0;i=n-1;i+) printf(%c,Vi); printf(n); 執(zhí)行結(jié)果： a b c d e f g h i j k l m n o p q r s t u v w x y z 2626個(gè)字母 另一種寫法 #include int main() int i; for(i=0;i=i;j-) aj+1=aj; ai=x; n+; / 元素后移一個(gè)位置 / 插入x / 表長(zhǎng)加1 4. 刪除操作刪除操作 指將表的第指將表的第i(1in)個(gè)元素刪去，使長(zhǎng)度為

15、個(gè)元素刪去，使長(zhǎng)度為n的線性表的線性表(e1，, ei-1，ei，ei+1，en)變成長(zhǎng)度為變成長(zhǎng)度為n-1的線性表的線性表(e1，, ei-1， ei+1，en)。 實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： 將第將第i +1至第至第n 位的元素向前移動(dòng)一個(gè)位置；位的元素向前移動(dòng)一個(gè)位置； 表長(zhǎng)減表長(zhǎng)減1。 注意：注意：事先需要判斷，事先需要判斷，刪除位置刪除位置i 是否合法是否合法? 圖圖2.4 順序表中刪除元素順序表中刪除元素 例如：線性表例如：線性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)刪除第刪除第5 個(gè)元素，則需將第個(gè)元素，則需將第6個(gè)元素到第個(gè)元素到第10個(gè)元素依次

16、向前移動(dòng)個(gè)元素依次向前移動(dòng) 一個(gè)位置，如圖一個(gè)位置，如圖2.4所示。所示。 for (j=i+1;jdata=a; p-next=q; 方式3：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用： (*p).data=a； (*p).nextq 單鏈表可以由頭指針唯一確定單鏈表可以由頭指針唯一確定。 單鏈表的存儲(chǔ)結(jié)構(gòu)描述如下：?jiǎn)捂湵淼拇鎯?chǔ)結(jié)構(gòu)描述如下： typedeftypedef structstruct LNodeLNode ElemType ElemType data;data; struct struct LNodeLNode * *next;next; LNode ,*LinkList; /*

17、 LinkList為結(jié)構(gòu)指針類型為結(jié)構(gòu)指針類型*/ 假設(shè)假設(shè)L是是LinkList型的變量，則型的變量，則L是一個(gè)結(jié)構(gòu)指針，即單鏈表的是一個(gè)結(jié)構(gòu)指針，即單鏈表的 頭指針，它指向表中第一個(gè)結(jié)點(diǎn)。頭指針，它指向表中第一個(gè)結(jié)點(diǎn)。 若若L=NULL（對(duì)于帶頭結(jié)點(diǎn)的單鏈表為（對(duì)于帶頭結(jié)點(diǎn)的單鏈表為L(zhǎng)-next=NULL），）， 則表示單鏈表為一個(gè)空表，其長(zhǎng)度為則表示單鏈表為一個(gè)空表，其長(zhǎng)度為0。 若不是空表，對(duì)于帶頭結(jié)點(diǎn)的單鏈表若不是空表，對(duì)于帶頭結(jié)點(diǎn)的單鏈表L，p=L-next指向指向 表中的第一個(gè)結(jié)點(diǎn)表中的第一個(gè)結(jié)點(diǎn)a1，即，即p-data=a1，而，而p-next-data=a2。 其余依此類推。

18、其余依此類推。 1. 查找查找 算法描述：算法描述： 查找第查找第i個(gè)結(jié)點(diǎn)，從頭指針個(gè)結(jié)點(diǎn)，從頭指針L出發(fā)，順著鏈域掃描。出發(fā)，順著鏈域掃描。 用指針用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用指向當(dāng)前掃描到的結(jié)點(diǎn)，用j做計(jì)數(shù)器，累計(jì)當(dāng)前掃做計(jì)數(shù)器，累計(jì)當(dāng)前掃 描過(guò)的結(jié)點(diǎn)數(shù)。描過(guò)的結(jié)點(diǎn)數(shù)。 當(dāng)當(dāng)j = i時(shí)，指針時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 2.3.2 單鏈表上的基本運(yùn)算單鏈表上的基本運(yùn)算 2. 單鏈表插入操作單鏈表插入操作 算法描述：算法描述： 要在第要在第i個(gè)位置插入元素個(gè)位置插入元素e，需要找到第，需要找到第i-1個(gè)結(jié)點(diǎn)并由指?jìng)€(gè)結(jié)點(diǎn)并由指 針針p指示，然后

19、申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由指針指示，然后申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由指針s指示，其數(shù)據(jù)域指示，其數(shù)據(jù)域 的值為的值為e。 修改第修改第i-1個(gè)結(jié)點(diǎn)的指針使其指向個(gè)結(jié)點(diǎn)的指針使其指向s，使，使s結(jié)點(diǎn)的指針域指結(jié)點(diǎn)的指針域指 向原第向原第i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 插入：插入：s-next=p-next; p-next=s; 在鏈表中插入一個(gè)元素的示意圖如下：在鏈表中插入一個(gè)元素的示意圖如下： x x s b ba a p a ab b p 插入步驟（即核心語(yǔ)句）：插入步驟（即核心語(yǔ)句）： Step 1Step 1：s-next=p-next; Step 2Step 2：p-next=s ； p-next s-next

20、 元素元素x x結(jié)點(diǎn)應(yīng)預(yù)先生成：結(jié)點(diǎn)應(yīng)預(yù)先生成： s=(LinkList)malloc(m);s=(LinkList)malloc(m); s-data=x;s-data=x; s-next=p-next;s-next=p-next; p-next=s;p-next=s; 3. 3. 刪除 在鏈表中刪除某元素的示意圖如下：在鏈表中刪除某元素的示意圖如下： c ca ab b p 刪除步驟（即核心語(yǔ)句）：刪除步驟（即核心語(yǔ)句）： q = p-next; /保存保存b的指針，靠它才能指向的指針，靠它才能指向c p-next=q-next; /a、c兩結(jié)點(diǎn)相連兩結(jié)點(diǎn)相連 free(q) ； /刪除刪

21、除b結(jié)點(diǎn)，徹底釋放結(jié)點(diǎn)，徹底釋放 p-next 思考：思考： 省略省略free(q)語(yǔ)句語(yǔ)句行不行？行不行？ (p-next) - next 4. 建立單鏈表建立單鏈表 圖圖2.10 頭插法建立單鏈表圖示頭插法建立單鏈表圖示 2） 尾插法建表尾插法建表 圖圖2.11 尾插法建表圖示尾插法建表圖示 rs；r 始終指向單鏈表的表尾 L (a) 建空表 c1 s s 指向新申請(qǐng)的結(jié)點(diǎn)空間 sdatac 1 (b) 申請(qǐng)新結(jié)點(diǎn)并賦值 Lc1 s (c) 插入第一個(gè)結(jié)點(diǎn) Lc2c1 r r r nexts； (d) 插入第二個(gè)結(jié)點(diǎn) sr 5.5.應(yīng)用舉例：兩個(gè)鏈表的歸并應(yīng)用舉例：兩個(gè)鏈表的歸并( (教材

22、教材P31)P31) 算法要求： 已知：線性表 A、B，分別由單鏈表 LA , LB 存儲(chǔ)， 其中數(shù)據(jù)元素按值非遞減有序排列， 要求：將 A ，B 歸并為一個(gè)新的線性表C , C 的數(shù)據(jù) 元素仍按值非遞減排列 。設(shè)線性表 C 由單鏈表 LC 存儲(chǔ)。 假設(shè)：A=(3，5，8，11)，B=(2，6，8，9，11) 預(yù)測(cè)：合并后 C =( 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ) 用鏈表可表示為： 3 3 5 511 11 / 8 8 La 2 2 6 611 11 / 8 8 Lb 9 9 2 2 3 3 6 6 5 5 Lc 8 8 811 / 911 頭結(jié)點(diǎn) 算法

23、分析： 算法主要包括：搜索、比較、插入三個(gè)操作： 搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表； 比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??； 插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。 La 3 5 8 11 Lb 2 6 8 119 Pa Pb Pa Pb Pa、Pb用于搜索La和Lb， Pc指向新鏈表當(dāng)前結(jié)點(diǎn) Lc Pa 3 Pc Pa 5 Pc 11 Pc 2 Pb Pc Pa 思考： 1、不用Lc，直接把La表插到Lb表中；或者把Lb表 插到La表中，如何編程？ 2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？ 6 6，其他形式的鏈表 討論1： 用一維數(shù)組也能存放鏈表嗎？怎樣實(shí)現(xiàn)？ 答：能。只要定義一個(gè)結(jié)構(gòu)類型(含

24、數(shù)據(jù)域和指示域)數(shù) 組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。 注：數(shù)據(jù)域含義與前面相同，指示域相當(dāng)于前面的指針 域。 靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣， 不需要移動(dòng)元素，只需修改指示器就可以了。 具體實(shí)現(xiàn)過(guò)程見教材P31-34。 討論討論2 2： 鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？ 答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié) 點(diǎn)即可 (P-next=head;) 。這種形成環(huán)路的鏈表稱 為循環(huán)鏈表。 特別：帶頭結(jié)點(diǎn)的 空循環(huán)鏈表樣式 H 參見教材P35 特點(diǎn)： 圖圖2.13 循環(huán)鏈表循環(huán)鏈表 L a1ai 1aian L (a) 帶頭結(jié)點(diǎn)的空循環(huán)鏈表

25、(b) 帶頭結(jié)點(diǎn)的循環(huán)單鏈表的一般形式 a1ai 1aian rear rear *(rearnext) * (c) 采用尾指針的循環(huán)單鏈表的一般形式 討論討論3 3： 單鏈表只能查找結(jié)點(diǎn)的直接后繼，單鏈表只能查找結(jié)點(diǎn)的直接后繼， 能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？ 答：能。只要把單鏈表再多開一個(gè)指針域即可(例 如用*next和*prior;) 。 雙向鏈表在非線性結(jié)構(gòu)(如樹結(jié)構(gòu))中將大量使用。 priordatanext 這種有兩個(gè)指針的鏈表稱為雙向鏈表。其特點(diǎn)是 可以雙向查找表中結(jié)點(diǎn)。參見教材P3539。 特別：帶頭結(jié)點(diǎn)的空雙向鏈表樣式： / 圖圖2.14 雙向鏈

26、表的結(jié)點(diǎn)結(jié)構(gòu)雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu) priordatanext 前驅(qū)指針域數(shù)據(jù)域后繼指針域 由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一 個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)與直接后繼結(jié)點(diǎn)變得非常方便。個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)與直接后繼結(jié)點(diǎn)變得非常方便。 設(shè)指針設(shè)指針p指向雙鏈表中某一結(jié)點(diǎn)，則有下式成立：指向雙鏈表中某一結(jié)點(diǎn)，則有下式成立： p-prior-next = p = p-next-prior 圖圖2.15 雙向循環(huán)鏈表圖示雙向循環(huán)鏈表圖示 L a1a2a3 L (a) 空的雙向循環(huán)鏈表 (b) 非空的雙向循環(huán)鏈表 1. 雙向鏈表的前插操作雙向鏈表的前插操作

27、圖圖2.16 雙向鏈表插入操作雙向鏈表插入操作 ab s p c 2. 雙向鏈表的刪除操作雙向鏈表的刪除操作 算法描述：算法描述： 圖圖2.17 雙向鏈表的刪除操作雙向鏈表的刪除操作 abc p 要點(diǎn)回顧 1. 鏈表的表示(包括有關(guān)術(shù)語(yǔ)、結(jié)構(gòu)數(shù)據(jù)類型等) 2. 鏈表的實(shí)現(xiàn)(建表、輸出、修改、插入、刪除) 了解：其它鏈表形式了解：其它鏈表形式 靜態(tài)鏈表 循環(huán)鏈表 雙向鏈表 提問(wèn)： 怎樣讀取頭結(jié)點(diǎn)數(shù)據(jù)域中的信息？ 鏈表的操作要用指針？ 用L-data 僅兩個(gè)作用：找位置 和改地址！ 順序表和鏈表的比較順序表和鏈表的比較 1. 基于空間的考慮基于空間的考慮 在鏈表中的每個(gè)結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外

28、設(shè)置指針在鏈表中的每個(gè)結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外設(shè)置指針 （或光標(biāo)）域，（或光標(biāo)）域，從存儲(chǔ)密度來(lái)講，這是不經(jīng)濟(jì)的從存儲(chǔ)密度來(lái)講，這是不經(jīng)濟(jì)的。所謂存儲(chǔ)密度。所謂存儲(chǔ)密度 (Storage Density), 是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)結(jié)是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)結(jié) 構(gòu)所占的存儲(chǔ)量之比，構(gòu)所占的存儲(chǔ)量之比， 即即 存儲(chǔ)密度存儲(chǔ)密度=結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總 量量 一般地，存儲(chǔ)密度越大，存儲(chǔ)空間的利用率就越高。顯一般地，存儲(chǔ)密度越大，存儲(chǔ)空間的利用率就越高。顯 然，順序表的存儲(chǔ)密度為然，順序表的存儲(chǔ)密度為1，而鏈表的存儲(chǔ)密度小于，而鏈表的存儲(chǔ)密度小于1。 由此可知，由此可知，當(dāng)線性表的長(zhǎng)度變化不大，易于事先確定其當(dāng)線性表的長(zhǎng)度變化不大，易于事先確定其 大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。 2. 基于時(shí)間的考慮基于時(shí)間的考慮 順序表是由向量實(shí)現(xiàn)的，它是一種隨機(jī)存取結(jié)構(gòu)，對(duì)表中任順序表是由向量實(shí)現(xiàn)的，它是一種隨機(jī)存取結(jié)構(gòu)，對(duì)表中任 一結(jié)點(diǎn)都可以在一結(jié)點(diǎn)都可以在O(1)時(shí)間內(nèi)直接地存取，而鏈表中的結(jié)點(diǎn)，需從時(shí)間內(nèi)直接地存取，而鏈表中的結(jié)點(diǎn)，需