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

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

3、定義線性表的類型定義 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)，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總個為元素總個數(shù)，即表長數(shù)，即

4、表長空表空表表尾表尾例例1 1 分析分析26 26 個英文字母組成的英文表個英文字母組成的英文表 （ A, B, C, D, , Z）學(xué)號學(xué)號姓名姓名性別性別年齡年齡班級班級541407010126541407010126于春梅于春梅女女 18 1820142014級計科級計科1 1班班2626號號541407010127541407010127何仕鵬何仕鵬男男 18 1820142014級計科級計科1 1班班2727號號541407010128541407010128王王 爽爽女女 18 1820142014級計科級計科1 1班班2828號號541407010129541407010129王

5、亞武王亞武男男 18 1820142014級計科級計科1 1班班2929號號： ：例例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)，因為矩陣、數(shù)組、字符串、線性表是最常見的數(shù)據(jù)結(jié)構(gòu)，因為矩陣、數(shù)組、字符串、堆棧、堆棧、 隊列等都符合線性條件。隊列等都符合線性條件。練：判斷下列敘述的

6、正誤：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)定義是唯一的，不依賴于計算機(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)系是一對一的。線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對一的。5. 一維向量是線性表，但二維或一維向量是線性表，但二維或N維數(shù)組不是。維數(shù)組不是。6. “同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所

7、有數(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的長度是的長度是42，之后把，之后把Lb集合中的元素依次和集合中的元素依次和La中的元素進(jìn)行比對中的元素進(jìn)行比對形成一個循環(huán)，首先形成一個循環(huán)，首先Lb中的中的8與與La的元素依次比對，的元素依次比對，8與所有與所有La中中元素不同，將元素不同，將8插入插入La中，中，3，2與與2相同進(jìn)

8、入相同進(jìn)入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進(jìn)入下一個進(jìn)入下一個元素元素3, La中中4與與Lb中中4比較，把比較，把La的的4插入插入Lc,LaLb都下一個元素都下一個元素4,La中中6與與Lb中中7比較，把小的比較，把小的La中的中的6的插入的插入Lc，La進(jìn)入下進(jìn)入下一

9、個元素，無元素了一個元素，無元素了5，就將，就將Lb中剩余元素依次加入中剩余元素依次加入Lc中中47910246LaLbLc2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 2.2.1 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu) 用一組地址連續(xù)的存儲單元依次用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過存儲線性表的元素，可通過數(shù)組數(shù)組來實現(xiàn)。來實現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲在物把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上理上相鄰相鄰的存儲單元中的存儲結(jié)構(gòu)。的存儲單元中的存儲結(jié)構(gòu)。順序存儲定義：順序存儲定義：順序存儲方法：順序存儲方法：簡言之，邏輯上相鄰，物理上也相鄰簡言之，邏輯上相鄰，物理上也

10、相鄰線性表順序存儲特點(diǎn)：1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2. 若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）。計算方法是：用數(shù)組下標(biāo)）。計算方法是： 設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為LOC(a1)（稱為首地址），設(shè)每個元素占用存儲空稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為間（地址長度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC(ai) = LOC(a1) + L *(i-1) LOC(

11、ai+1) = LOC(ai)+L 它是一種它是一種隨機(jī)存取隨機(jī)存取的數(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 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L L一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的元素用相鄰的個字節(jié)個字

12、節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素數(shù)組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是9898，則，則 的第的第一個字節(jié)的地址是一個字節(jié)的地址是 113例1 1因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址計算通式為：地址計算通式為：LOC(ai) = 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=

13、n-1;i+) Vi=Vi-1+1; 核心語句：法1 Vi= Vi-1+1;法2 Vi=a+i;法3 Vi=97+i;例2void build();void display();#define n 26int Vn;void main(void) /*主函數(shù)，字母線性表的生成和輸出*/ build(); 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

14、z2626個字母 另一種寫法#includeint main()int i;for(i=0;i=i;j-)aj+1=aj; ai=x; n+;/ 元素后移一個位置/ 插入x / 表長加1 4. 刪除操作刪除操作 指將表的第指將表的第i(1in)個元素刪去，使長度為個元素刪去，使長度為n的線性表的線性表(e1，, ei-1，ei，ei+1，en)變成長度為變成長度為n-1的線性表的線性表(e1，, ei-1， ei+1，en)。 實現(xiàn)步驟：實現(xiàn)步驟： 將第將第i +1至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置； 表長減表長減1。注意：注意：事先需要判斷，事先需要判斷，刪除位置

15、刪除位置i 是否合法是否合法?圖圖2.4 順序表中刪除元素順序表中刪除元素 例如：線性表例如：線性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)刪除第刪除第5個元素，則需將第個元素，則需將第6個元素到第個元素到第10個元素依次向前移動個元素依次向前移動一個位置，如圖一個位置，如圖2.4所示。所示。 for (j=i+1;jdata=a; p-next=q; 方式3：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用： (*p).data=a； (*p).nextq單鏈表可以由頭指針唯一確定單鏈表可以由頭指針唯一確定。 單鏈表的存儲結(jié)構(gòu)描述如下：單鏈表的存儲結(jié)構(gòu)描述如下：

16、typedeftypedef structstruct LNodeLNode ElemType ElemType data;data; struct struct LNodeLNode * *next;next;LNode ,*LinkList; /* LinkList為結(jié)構(gòu)指針類型為結(jié)構(gòu)指針類型*/ 假設(shè)假設(shè)L是是LinkList型的變量，則型的變量，則L是一個結(jié)構(gòu)指針，即單鏈表的是一個結(jié)構(gòu)指針，即單鏈表的頭指針，它指向表中第一個結(jié)點(diǎn)。頭指針，它指向表中第一個結(jié)點(diǎn)。 若若L=NULL（對于帶頭結(jié)點(diǎn)的單鏈表為（對于帶頭結(jié)點(diǎn)的單鏈表為L-next=NULL），），則表示單鏈表為一個空表，其長度為

17、則表示單鏈表為一個空表，其長度為0。 若不是空表，對于帶頭結(jié)點(diǎn)的單鏈表若不是空表，對于帶頭結(jié)點(diǎn)的單鏈表L，p=L-next指向指向表中的第一個結(jié)點(diǎn)表中的第一個結(jié)點(diǎn)a1，即，即p-data=a1，而，而p-next-data=a2。其余依此類推。其余依此類推。1. 查找查找 算法描述：算法描述： 查找第查找第i個結(jié)點(diǎn)，從頭指針個結(jié)點(diǎn)，從頭指針L出發(fā)，順著鏈域掃描。出發(fā)，順著鏈域掃描。 用指針用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用指向當(dāng)前掃描到的結(jié)點(diǎn)，用j做計數(shù)器，累計當(dāng)前掃做計數(shù)器，累計當(dāng)前掃描過的結(jié)點(diǎn)數(shù)。描過的結(jié)點(diǎn)數(shù)。 當(dāng)當(dāng)j = i時，指針時，指針p所指的結(jié)點(diǎn)就是要找的第所指的結(jié)點(diǎn)就是要找的第i個

18、結(jié)點(diǎn)。個結(jié)點(diǎn)。 2.3.2 單鏈表上的基本運(yùn)算單鏈表上的基本運(yùn)算 2. 單鏈表插入操作單鏈表插入操作 算法描述：算法描述： 要在第要在第i個位置插入元素個位置插入元素e，需要找到第，需要找到第i-1個結(jié)點(diǎn)并由指個結(jié)點(diǎn)并由指針針p指示，然后申請一個新的結(jié)點(diǎn)并由指針指示，然后申請一個新的結(jié)點(diǎn)并由指針s指示，其數(shù)據(jù)域指示，其數(shù)據(jù)域的值為的值為e。 修改第修改第i-1個結(jié)點(diǎn)的指針使其指向個結(jié)點(diǎn)的指針使其指向s，使，使s結(jié)點(diǎn)的指針域指結(jié)點(diǎn)的指針域指向原第向原第i個結(jié)點(diǎn)。個結(jié)點(diǎn)。 插入：插入：s-next=p-next; p-next=s; 在鏈表中插入一個元素的示意圖如下：在鏈表中插入一個元素的示意圖如

19、下：x xsb ba apa ab bp插入步驟（即核心語句）：插入步驟（即核心語句）：Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s ；p-nexts-next元素元素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 bp刪除步驟（即核心語句）：

20、刪除步驟（即核心語句）：q = p-next; /保存保存b的指針，靠它才能指向的指針，靠它才能指向cp-next=q-next; /a、c兩結(jié)點(diǎn)相連兩結(jié)點(diǎn)相連free(q) ； /刪除刪除b結(jié)點(diǎn)，徹底釋放結(jié)點(diǎn)，徹底釋放p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - next4. 建立單鏈表建立單鏈表圖圖2.10 頭插法建立單鏈表圖示頭插法建立單鏈表圖示 2） 尾插法建表尾插法建表 圖圖2.11 尾插法建表圖示尾插法建表圖示 rs；r 始終指向單鏈表的表尾L(a) 建空表c1ss 指向新申請的結(jié)點(diǎn)空間sdatac1(b) 申請新結(jié)點(diǎn)并賦值Lc1s(

21、c) 插入第一個結(jié)點(diǎn)Lc2c1rrr nexts；(d) 插入第二個結(jié)點(diǎn)sr5.5.應(yīng)用舉例：兩個鏈表的歸并應(yīng)用舉例：兩個鏈表的歸并( (教材教材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

22、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)算法分析：算法主要包括：搜索、比較、插入三個操作：搜索：需要兩個指針?biāo)阉鲀蓚€鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大小；插入：將兩個結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。La3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索La和Lb， Pc指向新鏈表當(dāng)前結(jié)點(diǎn)Lc Pa3 PcPa5 Pc11Pc2 PbPcPa思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表 插到La表中，如何編程？2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？6 6，其他形式的鏈表討論1：

23、 用一維數(shù)組也能存放鏈表嗎？怎樣實現(xiàn)？答：能。只要定義一個結(jié)構(gòu)類型(含數(shù)據(jù)域和指示域)數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數(shù)據(jù)域含義與前面相同，指示域相當(dāng)于前面的指針域。靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。具體實現(xiàn)過程見教材P31-34。討論討論2 2： 鏈表能不能首尾相連？怎樣實現(xiàn)？鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最后一個結(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)鏈表 La1ai 1ai

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

25、鏈表的結(jié)點(diǎn)結(jié)構(gòu)雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu) priordatanext前驅(qū)指針域數(shù)據(jù)域后繼指針域 由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)與直接后繼結(jié)點(diǎn)變得非常方便。個結(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)鏈表圖示 La1a2a3L(a) 空的雙向循環(huán)鏈表(b) 非空的雙向循環(huán)鏈表1. 雙向鏈表的前插操作雙向鏈表的前插操作 圖圖2.16

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

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