數(shù)據(jù)結構(c語言版)_嚴蔚敏版_第2章_線性表_信大(第2講)講解

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

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

3、章線性表 第第2章章 線性表線性表 2.1 線性表的類型定義線性表的類型定義 2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 2.3 線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn) 圖圖2.1 線性表的邏輯結構線性表的邏輯結構 2.1 線性表的類型定義線性表的類型定義 2.1.1 線性表的邏輯結構線性表的邏輯結構 （a1, a2, ai-1， ，ai, ai1 ， ，, an） 線性表的定義：線性表的定義：是是n個數(shù)據(jù)元素的個數(shù)據(jù)元素的有限序列有限序列 n=0時稱為時稱為 數(shù)據(jù)元素數(shù)據(jù)元素 表頭表頭ai的直接的直接前趨前趨ai的直接的直接后繼后繼 下標，下標，是元素的是元素的 序號，表示元

4、素序號，表示元素 在表中的位置在表中的位置 n為元素總個為元素總個 數(shù)，即表長數(shù)，即表長 空表空表 表尾表尾 例例1 1 分析分析26 26 個英文字母組成的英文表個英文字母組成的英文表 （ A, B, C, D, , Z） 學號學號姓名姓名性別性別年齡年齡班級班級 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 分析學生情況登記表分析學生情況登記表 數(shù)據(jù)元素都是記錄數(shù)據(jù)元素都是記錄; 元素間關系是線性元素間關系是線性 數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母; 元素間關系是線性元素間關系是線性 同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性 線性表的特點可概括如下：線性表的特點可概括如下： 同一性同一性 有窮性有窮性 有序性有序性 線性表是最常見的數(shù)據(jù)結構，因為矩陣、

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

7、的。 5. 一維向量是線性表，但二維或一維向量是線性表，但二維或N維數(shù)組不是。維數(shù)組不是。 6. “同一數(shù)據(jù)邏輯結構中的所有數(shù)據(jù)元素都具有相同一數(shù)據(jù)邏輯結構中的所有數(shù)據(jù)元素都具有相 同的特性同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個 數(shù)都相等。數(shù)都相等。 例例2-1 兩個集合兩個集合La和和Lb的合并的合并 假設兩個集合假設兩個集合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 線性表的順序存儲結構線性表的順序存儲結構 用一組地址連續(xù)的存儲單元依次用一組地址連續(xù)的存儲單元依次 存儲線性表的元素，可通過存儲線性表的元素，可通過數(shù)組數(shù)組來實現(xiàn)。來實現(xiàn)。 把邏輯上相鄰的數(shù)據(jù)元素存儲在

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

11、個元素占用存儲空稱為首地址），設每個元素占用存儲空 間（地址長度）為間（地址長度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC(ai) = LOC(a1) + L *(i-1) LOC(ai+1) = LOC(ai)+L 它是一種它是一種隨機存取隨機存取的數(shù)據(jù)結構。的數(shù)據(jù)結構。 注意：C語言中的數(shù)組的下標從0開始， 即：Vn的有效范圍是V0Vn-1 線性表的順序存儲結構示意圖線性表的順序存儲結構示意圖 a a1 1 a a2 2 a ai i a ai+1 i+1 a an n 地址地址 內容內容 元素在表中的位序元素在表中的位序 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ù)組，下標的范圍是到，每個數(shù)組一個一維數(shù)組，下標的范圍是到，每個數(shù)組 元素用相鄰的元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器按字節(jié)編址，設存儲存儲。存儲器按字節(jié)編址，設存儲 數(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)，寫出在順序結構上生 成和顯示該表的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í)行結果： 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指向該結點的首地址，然后用： (*p).data=a； (*p).nextq 單鏈表可以由頭指針唯一確定單鏈表可以由頭指針唯一確定。 單鏈表的存儲結構描述如下：單鏈表的存儲結構描述如下： typedeftypedef structstruct LNodeLNode ElemType ElemType data;data; struct struct LNodeLNode * *next;next; LNode ,*LinkList; /*

17、 LinkList為結構指針類型為結構指針類型*/ 假設假設L是是LinkList型的變量，則型的變量，則L是一個結構指針，即單鏈表的是一個結構指針，即單鏈表的 頭指針，它指向表中第一個結點。頭指針，它指向表中第一個結點。 若若L=NULL（對于帶頭結點的單鏈表為（對于帶頭結點的單鏈表為L-next=NULL），）， 則表示單鏈表為一個空表，其長度為則表示單鏈表為一個空表，其長度為0。 若不是空表，對于帶頭結點的單鏈表若不是空表，對于帶頭結點的單鏈表L，p=L-next指向指向 表中的第一個結點表中的第一個結點a1，即，即p-data=a1，而，而p-next-data=a2。 其余依此類推。

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

19、申請一個新的結點并由指針指示，然后申請一個新的結點并由指針s指示，其數(shù)據(jù)域指示，其數(shù)據(jù)域 的值為的值為e。 修改第修改第i-1個結點的指針使其指向個結點的指針使其指向s，使，使s結點的指針域指結點的指針域指 向原第向原第i個結點。個結點。 插入：插入：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結點應預先生成：結點應預先生成： 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兩結點相連兩結點相連 free(q) ； /刪除刪

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

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

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

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

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

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

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