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

1、緒論要點回顧 數(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ù)元素數(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)、存儲存儲結(jié)構(gòu)和結(jié)構(gòu)和運算運算 算法效率指標(biāo)算法效率指標(biāo)時間效率和空間效率時間效率和空間效率 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 邏輯結(jié)構(gòu)唯一邏輯結(jié)構(gòu)唯一 存儲結(jié)構(gòu)不唯一存儲結(jié)構(gòu)不唯一 運算的實現(xiàn)依賴運算的實現(xiàn)依賴 于存儲結(jié)構(gòu)于存儲結(jié)構(gòu) 近期 上課 內(nèi)容 第第2 2章章 線性表線性表 第第3 3章章 棧和隊

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

3、章線性表 第第2章章 線性表線性表 2.1 線性表的類型定義線性表的類型定義 2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的鏈?zhǔn)奖硎竞蛯崿F(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個數(shù)據(jù)元素的個數(shù)據(jù)元素的有限序列有限序列 n=0時稱為時稱為 數(shù)據(jù)元素數(shù)據(jù)元素 表頭表頭ai的直接的直接前趨前趨ai的直接的直接后繼后繼 下標(biāo)，下標(biāo)，是元素的是元素的 序號，表示元

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

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

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

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

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

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

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

11、個元素占用存儲空稱為首地址），設(shè)每個元素占用存儲空 間（地址長度）為間（地址長度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC(ai) = LOC(a1) + L *(i-1) LOC(ai+1) = LOC(ai)+L 它是一種它是一種隨機存取隨機存取的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。 注意：C語言中的數(shù)組的下標(biāo)從0開始， 即：Vn的有效范圍是V0Vn-1 線性表的順序存儲結(jié)構(gòu)示意圖線性表的順序存儲結(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 一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組 元素用相鄰的元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲存儲。存儲器按字節(jié)編址，設(shè)存儲 數(shù)組元素數(shù)組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是9898，則，則 的第的第 一個字節(jié)的地址是一個字節(jié)的地址是 113 例1 1 因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113 解：解：地址計算通式為：地址計算通式為： LOC(ai)

13、 = LOC(a1) + L *（i-1） 用數(shù)組V V來存放2626個英文字母組成的線 性表(a(a，b b，c c，z)z)，寫出在順序結(jié)構(gòu)上生 成和顯示該表的C C語言程序。 void build() /*字母線性表的生成，即建表操作*/ int i; V0=a; for(i=1;i=n-1;i+) Vi=Vi-1+1; 核心語句： 法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個字母 另一種寫法 #include int main() int i; for(i=0;i=i;j-) aj+1=aj; ai=x; n+; / 元素后移一個位置 / 插入x / 表長加1 4. 刪除操作刪除操作 指將表的第指將表的第i(1in)個元素刪去，使長度為

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

16、向前移動個元素依次向前移動 一個位置，如圖一個位置，如圖2.4所示。所示。 for (j=i+1;jdata=a; p-next=q; 方式3：先讓指針變量p指向該結(jié)點的首地址，然后用： (*p).data=a； (*p).nextq 單鏈表可以由頭指針唯一確定單鏈表可以由頭指針唯一確定。 單鏈表的存儲結(jié)構(gòu)描述如下：單鏈表的存儲結(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是一個結(jié)構(gòu)指針，即單鏈表的是一個結(jié)構(gòu)指針，即單鏈表的 頭指針，它指向表中第一個結(jié)點。頭指針，它指向表中第一個結(jié)點。 若若L=NULL（對于帶頭結(jié)點的單鏈表為（對于帶頭結(jié)點的單鏈表為L-next=NULL），）， 則表示單鏈表為一個空表，其長度為則表示單鏈表為一個空表，其長度為0。 若不是空表，對于帶頭結(jié)點的單鏈表若不是空表，對于帶頭結(jié)點的單鏈表L，p=L-next指向指向 表中的第一個結(jié)點表中的第一個結(jié)點a1，即，即p-data=a1，而，而p-next-data=a2。 其余依此類推。

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

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

20、 元素元素x x結(jié)點應(yīng)預(yù)先生成：結(jié)點應(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 刪除步驟（即核心語句）：刪除步驟（即核心語句）： q = p-next; /保存保存b的指針，靠它才能指向的指針，靠它才能指向c p-next=q-next; /a、c兩結(jié)點相連兩結(jié)點相連 free(q) ； /刪除刪

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

22、教材P31)P31) 算法要求： 已知：線性表 A、B，分別由單鏈表 LA , LB 存儲， 其中數(shù)據(jù)元素按值非遞減有序排列， 要求：將 A ，B 歸并為一個新的線性表C , C 的數(shù)據(jù) 元素仍按值非遞減排列 。設(shè)線性表 C 由單鏈表 LC 存儲。 假設(shè)：A=(3，5，8，11)，B=(2，6，8，9，11) 預(yù)測：合并后 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é)點 算法

23、分析： 算法主要包括：搜索、比較、插入三個操作： 搜索：需要兩個指針?biāo)阉鲀蓚€鏈表； 比較：比較結(jié)點數(shù)據(jù)域中數(shù)據(jù)的大??； 插入：將兩個結(jié)點中數(shù)據(jù)小的結(jié)點插入新鏈表。 La 3 5 8 11 Lb 2 6 8 119 Pa Pb Pa Pb Pa、Pb用于搜索La和Lb， Pc指向新鏈表當(dāng)前結(jié)點 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ù)組也能存放鏈表嗎？怎樣實現(xiàn)？ 答：能。只要定義一個結(jié)構(gòu)類型(含

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

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

26、表的結(jié)點結(jié)構(gòu)雙向鏈表的結(jié)點結(jié)構(gòu) priordatanext 前驅(qū)指針域數(shù)據(jù)域后繼指針域 由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一 個結(jié)點的直接前驅(qū)結(jié)點與直接后繼結(jié)點變得非常方便。個結(jié)點的直接前驅(qū)結(jié)點與直接后繼結(jié)點變得非常方便。 設(shè)指針設(shè)指針p指向雙鏈表中某一結(jié)點，則有下式成立：指向雙鏈表中某一結(jié)點，則有下式成立： 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 要點回顧 1. 鏈表的表示(包括有關(guān)術(shù)語、結(jié)構(gòu)數(shù)據(jù)類型等) 2. 鏈表的實現(xiàn)(建表、輸出、修改、插入、刪除) 了解：其它鏈表形式了解：其它鏈表形式 靜態(tài)鏈表 循環(huán)鏈表 雙向鏈表 提問： 怎樣讀取頭結(jié)點數(shù)據(jù)域中的信息？ 鏈表的操作要用指針？ 用L-data 僅兩個作用：找位置 和改地址！ 順序表和鏈表的比較順序表和鏈表的比較 1. 基于空間的考慮基于空間的考慮 在鏈表中的每個結(jié)點，除了數(shù)據(jù)域外，還要額外

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