數(shù)據(jù)結(jié)構(gòu)分析與管理講義全

1、 .PAGE104 / NUMPAGES107 .前言緣起數(shù)據(jù)結(jié)構(gòu)是一門計算機專業(yè)基礎(chǔ)課，各類計算機考試都禁不住要考它，專升本考試自然也不例外。我給學生輔導這門課程已經(jīng)有幾個年頭了，講稿換了幾次，逐漸豐富起來。加之看到學生們埋頭記筆記時辛苦的樣子，就產(chǎn)生了寫一本小冊子的想法。另外，還有一層意思就是對數(shù)次輔導進行總結(jié)，以便交流之用。說明首先，需要說明的是這本書在語言風格上不太講究，常有些不嚴謹?shù)谋磉_，或調(diào)侃，或土得掉渣，難登大雅之堂，請勿在正規(guī)場合引用這些說法。這樣做的目的，僅僅是為了更簡練、更直接地描述思想，方便理解、記憶和使用。凡是這種情況，往往都用引號括起來，并加以腳注說明。還有，本書需配

2、合數(shù)據(jù)結(jié)構(gòu)(嚴蔚敏)教材使用。由于篇幅有限，多數(shù)概念、術(shù)語沒有詳釋。 另外，每章之后都配有習題，或多或少，難度不一，并沒有局限于專升本的要求。對所有習題都提供了參考答案。致我要感所有給予我?guī)椭娜?。志老師的大力支持和幫助使得本書得以面世，他還提供了近年專升本試題。永干老師的幫助使得本書順利印刷。譚業(yè)武老師給了我很大支持，還提出了很多建議。最后，我要感隆坤，她總是給我最大的支持，使那些本來只在我想象中的事情變成現(xiàn)實。莊波于濱州學院 TOC o 1-3 h z u HYPERLINK l _Toc101798259第0章 復習提示 PAGEREF _Toc101798259 h 1HYPERLIN

3、K l _Toc101798260一、 教材容 PAGEREF _Toc101798260 h 1HYPERLINK l _Toc101798261二、 復習提示 PAGEREF _Toc101798261 h 1HYPERLINK l _Toc1017982621. 經(jīng)典算法 PAGEREF _Toc101798262 h 1HYPERLINK l _Toc1017982632. 緒論 PAGEREF _Toc101798263 h 1HYPERLINK l _Toc1017982643. 線性表 PAGEREF _Toc101798264 h 1HYPERLINK l _Toc101798

4、2654. 棧和隊列 PAGEREF _Toc101798265 h 2HYPERLINK l _Toc1017982665. 串 PAGEREF _Toc101798266 h 2HYPERLINK l _Toc1017982676. 樹和二叉樹 PAGEREF _Toc101798267 h 2HYPERLINK l _Toc1017982687. 圖 PAGEREF _Toc101798268 h 2HYPERLINK l _Toc1017982698. 查找表 PAGEREF _Toc101798269 h 3HYPERLINK l _Toc1017982709. 部排序 PAGERE

5、F _Toc101798270 h 3HYPERLINK l _Toc101798271第1章 緒論 PAGEREF _Toc101798271 h 5HYPERLINK l _Toc101798272一、 基礎(chǔ)知識 PAGEREF _Toc101798272 h 5HYPERLINK l _Toc101798273二、 算法 PAGEREF _Toc101798273 h 5HYPERLINK l _Toc101798274三、 習題 PAGEREF _Toc101798274 h 6HYPERLINK l _Toc101798275第2章 線性表 PAGEREF _Toc101798275

6、 h 7HYPERLINK l _Toc101798276一、 基礎(chǔ)知識和算法 PAGEREF _Toc101798276 h 7HYPERLINK l _Toc1017982771. 線性表與其特點 PAGEREF _Toc101798277 h 7HYPERLINK l _Toc1017982782. 順序表線性表的順序存儲結(jié)構(gòu) PAGEREF _Toc101798278 h 7HYPERLINK l _Toc1017982793. 單鏈表線性表的鏈式存儲結(jié)構(gòu)之一 PAGEREF _Toc101798279 h 10HYPERLINK l _Toc1017982804. 循環(huán)鏈表 PAGE

7、REF _Toc101798280 h 15HYPERLINK l _Toc1017982815. 雙向循環(huán)鏈表 PAGEREF _Toc101798281 h 15HYPERLINK l _Toc1017982826. 順序表與單鏈表的比較 PAGEREF _Toc101798282 h 16HYPERLINK l _Toc101798283二、 習題 PAGEREF _Toc101798283 h 16HYPERLINK l _Toc101798284第3章 棧和隊列 PAGEREF _Toc101798284 h 17HYPERLINK l _Toc101798285一、 基礎(chǔ)知識和算法

8、 PAGEREF _Toc101798285 h 17HYPERLINK l _Toc1017982861. 棧 PAGEREF _Toc101798286 h 17HYPERLINK l _Toc1017982872. 鏈棧 PAGEREF _Toc101798287 h 17HYPERLINK l _Toc1017982883. 順序棧 PAGEREF _Toc101798288 h 18HYPERLINK l _Toc1017982894. 隊列 PAGEREF _Toc101798289 h 19HYPERLINK l _Toc1017982905. 鏈隊列 PAGEREF _Toc1

9、01798290 h 20HYPERLINK l _Toc1017982916. 循環(huán)隊列 PAGEREF _Toc101798291 h 20HYPERLINK l _Toc1017982927. 棧和隊列比較 PAGEREF _Toc101798292 h 22HYPERLINK l _Toc1017982938. 簡化的棧和隊列結(jié)構(gòu) PAGEREF _Toc101798293 h 23HYPERLINK l _Toc1017982949. 棧和隊列的應用 PAGEREF _Toc101798294 h 23HYPERLINK l _Toc101798295二、 習題 PAGEREF _T

10、oc101798295 h 24HYPERLINK l _Toc101798296第4章 串 PAGEREF _Toc101798296 h 25HYPERLINK l _Toc101798297一、 基礎(chǔ)知識和算法 PAGEREF _Toc101798297 h 25HYPERLINK l _Toc1017982981. 概念 PAGEREF _Toc101798298 h 25HYPERLINK l _Toc1017982992. 串的基本操作 PAGEREF _Toc101798299 h 25HYPERLINK l _Toc1017983003. 串的存儲結(jié)構(gòu) PAGEREF _Toc

11、101798300 h 25HYPERLINK l _Toc101798301二、 習題 PAGEREF _Toc101798301 h 25HYPERLINK l _Toc101798303第6章 樹和二叉樹 PAGEREF _Toc101798303 h 27HYPERLINK l _Toc101798304一、 基礎(chǔ)知識和算法 PAGEREF _Toc101798304 h 27HYPERLINK l _Toc1017983051. 樹與有關(guān)概念 PAGEREF _Toc101798305 h 27HYPERLINK l _Toc1017983062. 二叉樹 PAGEREF _Toc1

12、01798306 h 27HYPERLINK l _Toc1017983073. 二叉樹的性質(zhì) PAGEREF _Toc101798307 h 27HYPERLINK l _Toc1017983084. 二叉樹的存儲結(jié)構(gòu) PAGEREF _Toc101798308 h 28HYPERLINK l _Toc1017983095. 二叉樹的五種基本形態(tài) PAGEREF _Toc101798309 h 28HYPERLINK l _Toc1017983106. 遍歷二叉樹 PAGEREF _Toc101798310 h 29HYPERLINK l _Toc1017983117. 遍歷二叉樹的應用 P

13、AGEREF _Toc101798311 h 33HYPERLINK l _Toc1017983128. 線索二叉樹 PAGEREF _Toc101798312 h 34HYPERLINK l _Toc1017983139. 樹和森林 PAGEREF _Toc101798313 h 35HYPERLINK l _Toc10179831410. 赫夫曼樹與其應用 PAGEREF _Toc101798314 h 36HYPERLINK l _Toc101798315二、 習題 PAGEREF _Toc101798315 h 37HYPERLINK l _Toc101798316第7章 圖 PAGE

14、REF _Toc101798316 h 39HYPERLINK l _Toc101798317一、 基礎(chǔ)知識和算法 PAGEREF _Toc101798317 h 39HYPERLINK l _Toc1017983181. 圖的有關(guān)概念 PAGEREF _Toc101798318 h 39HYPERLINK l _Toc1017983192. 圖的存儲結(jié)構(gòu) PAGEREF _Toc101798319 h 39HYPERLINK l _Toc1017983203. 圖的遍歷 PAGEREF _Toc101798320 h 42HYPERLINK l _Toc1017983214. 最小生成樹 P

15、AGEREF _Toc101798321 h 44HYPERLINK l _Toc1017983225. 拓撲排序 PAGEREF _Toc101798322 h 46HYPERLINK l _Toc1017983236. 關(guān)鍵路徑 PAGEREF _Toc101798323 h 46HYPERLINK l _Toc1017983247. 最短路徑 PAGEREF _Toc101798324 h 47HYPERLINK l _Toc101798325二、 習題 PAGEREF _Toc101798325 h 49HYPERLINK l _Toc101798327第9章 查找 PAGEREF _

16、Toc101798327 h 51HYPERLINK l _Toc101798328一、 基礎(chǔ)知識和算法 PAGEREF _Toc101798328 h 51HYPERLINK l _Toc1017983291. 有關(guān)概念 PAGEREF _Toc101798329 h 51HYPERLINK l _Toc1017983302. 順序查找 PAGEREF _Toc101798330 h 51HYPERLINK l _Toc1017983313. 折半查找 PAGEREF _Toc101798331 h 52HYPERLINK l _Toc1017983324. 索引順序表 PAGEREF _T

17、oc101798332 h 54HYPERLINK l _Toc1017983335. 二叉排序樹 PAGEREF _Toc101798333 h 54HYPERLINK l _Toc1017983346. 平衡二叉樹 PAGEREF _Toc101798334 h 57HYPERLINK l _Toc1017983357. B-樹和B+樹 PAGEREF _Toc101798335 h 58HYPERLINK l _Toc1017983368. 鍵樹 PAGEREF _Toc101798336 h 59HYPERLINK l _Toc1017983379. 哈希表 PAGEREF _Toc1

18、01798337 h 59HYPERLINK l _Toc101798338二、 習題 PAGEREF _Toc101798338 h 61HYPERLINK l _Toc101798339第10章 部排序 PAGEREF _Toc101798339 h 63HYPERLINK l _Toc101798340一、 基礎(chǔ)知識和算法 PAGEREF _Toc101798340 h 63HYPERLINK l _Toc1017983411. 排序的有關(guān)概念 PAGEREF _Toc101798341 h 63HYPERLINK l _Toc1017983422. 直接插入排序 PAGEREF _To

19、c101798342 h 63HYPERLINK l _Toc1017983433. 折半插入排序 PAGEREF _Toc101798343 h 64HYPERLINK l _Toc1017983444. 希爾排序（縮小增量排序） PAGEREF _Toc101798344 h 64HYPERLINK l _Toc1017983455. 起泡排序 PAGEREF _Toc101798345 h 65HYPERLINK l _Toc1017983466. 快速排序 PAGEREF _Toc101798346 h 66HYPERLINK l _Toc1017983477. 簡單選擇排序 PAGE

20、REF _Toc101798347 h 67HYPERLINK l _Toc1017983488. 堆排序 PAGEREF _Toc101798348 h 68HYPERLINK l _Toc1017983499. 歸并排序 PAGEREF _Toc101798349 h 71HYPERLINK l _Toc10179835010. 基數(shù)排序 PAGEREF _Toc101798350 h 72HYPERLINK l _Toc10179835111. 各種排序方法比較 PAGEREF _Toc101798351 h 73復習提示教材容使用教材數(shù)據(jù)結(jié)構(gòu)C語言版 嚴蔚敏，清華大學。章節(jié) 去掉 第5

21、、8、11、12章 去掉 *部分 去掉1.3，2.4，4.4復習提示經(jīng)典算法單鏈表：遍歷、插入、刪除循環(huán)隊列：隊列空、隊列滿的條件二叉樹：遞歸遍歷與應用有序表的二分法查找快速排序簡單選擇排序緒論掌握幾個重要概念數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、算法時間復雜度的簡單計算（C 記號C，表示要求掌握計算方法，會計算。本節(jié)下同。）掌握幾種說法數(shù)據(jù)元素是，數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中關(guān)系的四種基本結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義算法的五個特征線性表線性表的概念和四個特征順序表和單鏈表的類型定義在順序表中查找、插入、刪除，靈活運用在單鏈表中查找、插入、刪除，靈活運用循環(huán)鏈表與雙向鏈表的定義、插入、刪除算法：單鏈表的算法，靈活運用、會編

22、程（P 記號P，要求達到編寫算法和程序的能力。本節(jié)下同。）棧和隊列棧和隊列的概念、特點入棧、出棧操作，靈活掌握了解棧的實現(xiàn)：鏈棧和順序棧（A 記號A，要求掌握算法思想，會演算。本節(jié)下同。算法，P）了解隊列的實現(xiàn)，鏈隊列和循環(huán)隊列，注意鏈隊列中的出隊列操作算法：注意循環(huán)隊列空和滿的條件（A，P）會運用棧和隊列串掌握相關(guān)概念會運用串的基本操作（C），特別是Concat()，Substring()，Index()和Replace()知道串的三種存儲結(jié)構(gòu)與其特點樹和二叉樹樹和二叉樹的有關(guān)概念二叉樹的性質(zhì)熟練掌握遍歷二叉樹的遞歸算法，并靈活運用知道線索二叉樹，會對二叉樹進行線索化樹、森林和二叉樹的轉(zhuǎn)化，

23、會遍歷樹和森林赫夫曼樹與其應用算法： 遞歸遍歷二叉樹與其應用（P） 構(gòu)造赫夫曼樹和赫夫曼編碼（A） 樹和二叉樹的轉(zhuǎn)換（A） 森林和二叉樹的轉(zhuǎn)換（A） 遍歷樹和森林（A）圖圖的有關(guān)概念熟練掌握圖的各種存儲結(jié)構(gòu)圖的遍歷：深度優(yōu)先、廣度優(yōu)先（A）最小生成樹算法（兩個）與其特點（A）拓撲排序（A）關(guān)鍵路徑算法（A）最短路徑算法（兩個）（A，O 記號O，要求掌握算法的時間復雜度。本節(jié)下同。：時間復雜度）查找表查找的有關(guān)概念，ASL等順序查找（A，P）熟練掌握有序表的折半查找算法（A，P，C）了解索引順序表熟練掌握二叉排序樹的概念，建立（A），查找（A，P），刪除（A），計算ASL（C）平衡二叉排序樹的概

24、念，建立（A），判斷失去平衡的類型，平衡化（A），計算ASL（C）了解B_樹，B+樹的概念和特點知道鍵樹（數(shù)字查找樹）哈希表的概念、特點、構(gòu)造哈希表（A），計算ASL和裝填因子（C）了解各種查找表的性能（O）部排序直接插入排序（A）折半插入排序（A，P）希爾排序（A）起泡排序（A）快速排序（A，P，O）簡單選擇排序（P，A，O）堆的概念，調(diào)整成堆（A），堆排序（A，O）歸并排序（A，O）鏈式基數(shù)排序（A，O）各種排序算法的對比結(jié)論（O）緒論基礎(chǔ)知識概念和術(shù)語(黑體字部分)。另外，注意：1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。P42、數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。P53、數(shù)據(jù)結(jié)構(gòu)與其形式定義。P5四種基

25、本結(jié)構(gòu)：集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖（網(wǎng)）狀結(jié)構(gòu)4、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)（抽象的，與實現(xiàn)無關(guān)）物理結(jié)構(gòu)（存儲結(jié)構(gòu)） 順序映像（順序存儲結(jié)構(gòu)）位置“相鄰” 非順序映像（鏈式存儲結(jié)構(gòu)）指針表示關(guān)系P65、數(shù)據(jù)類型 P7 抽象數(shù)據(jù)類型（ADT）P7 ADT=（數(shù)據(jù)對象，數(shù)據(jù)關(guān)系，基本操作） ADT細分為原子類型，固定聚合，可變聚合類型。P86、算法的概念 P137、算法的五個特征有窮性 確定性 可行性 輸入（0個或多個） 輸出（1個或多個）8、算法設(shè)計的要求：正確性可讀性健壯性效率與低存儲量其中正確性的四個層次（通常要求達到C層）。9、算法的時間復雜度 P15 常見有： O(1)，O(n)，O(n2)，O(

26、log2n) 分析算法的時間復雜度時，log2n常簡單記作log n。，O(n log2n)，O(2n) 語句頻度，用歸納法計算。10、算法的空間復雜度 P17算法起泡排序。P16另一種形式voidBubbleSort XE BubbleSort (DataType a, int n)for(i=0;in-1;i+)for(j=0;jaj+1)ajaj+1;或voidBubbleSort XE BubbleSort (DataType a, int n)for(i=1;in;i+)for(j=0;jaj+1)ajaj+1;或voidBubbleSort XE BubbleSort (DataT

27、ype a, int n)for(i=0;in-1;i+) change = fasle;for(j=0;jaj+1) ajaj+1; change = true; if ( !change ) break; 說明：a) 考試中要求寫算法時，可用類C，也可用C程序。b) 盡量書寫算法說明，言簡意賅。c) 技巧：用“邊界值驗證法”檢查下標越界錯誤。 如上第一個： 第二個循環(huán)條件若寫作jn-i，則當i=0時 aj+1會越界。d) 時間復雜度為O(n2)，第3個在最好情況下（待排記錄有序），時間復雜度為O(n)。習題 STYLEREF 1 s 1. SEQ 習題 * ARABIC s 1 1 編寫冒

28、泡排序算法，使結(jié)果從大到小排列。 STYLEREF 1 s 1. SEQ 習題 * ARABIC s 1 2 計算下面語句段中指定語句的頻度： 1) for ( i=1; i=n; i+ ) for ( j=i; j=n; j+ ) x+;/ 2) i = 1; while ( i=n ) i = i*2;/ 線性表基礎(chǔ)知識和算法線性表與其特點線性表是n個數(shù)據(jù)元素的有限序列。線性結(jié)構(gòu)的特點： “第一個”“最后一個”前驅(qū) 后繼。 這里太簡煉了，只是為了便于記憶。順序表線性表的順序存儲結(jié)構(gòu)特點a) 邏輯上相鄰的元素在物理位置上相鄰。b) 隨機訪問。類型定義簡而言之，“數(shù)組+長度” 不準確的說法，只

29、為便于理解和記憶，不要在正式場合引用。凡此情形，都加引號以示提醒。constint MAXSIZE = 線性表最大長度;typedefstructDataType elemMAXSIZE;int length;SqList;注：a) SqList為類型名，可換用其他寫法。 b) DataType是數(shù)據(jù)元素的類型，根據(jù)需要確定。 c) MAXSIZE根據(jù)需要確定。如constint MAXSIZE=64; d) 課本上的SqList類型可在需要時增加存儲空間，在上面這種定義下不可以。(這樣做避免了動態(tài)存分配，明顯減少了算法的復雜程度，容易理解。而且，原來Pascal版本的數(shù)據(jù)結(jié)構(gòu)（嚴蔚敏）就是這

30、樣做的。) e) 課本上的SqList類型定義中l(wèi)istsize表示已經(jīng)分配的空間大?。ㄈ菁{數(shù)據(jù)元素的個數(shù)）。當插入元素而遇到L.length=L.listsize時，用realloc (L.elem, L.listsize+增量) 重新分配存，而realloc()函數(shù)在必要的時候自動復制原來的元素到新分配的空間中?；拘螒B(tài)順序表空01MAXSIZE-1.L.elemL.elemL.elemL.length=0L.length=MAXSIZE0L.lengthMAXSIZE條件 L.length=0不允許刪除操作順序表滿條件 L.length=MAXSIZE不允許插入操作不空也不滿可以插入，刪

31、除基本算法遍歷順序訪問所有元素for ( i=0; iL.length; i+ ) visit ( L.elemi );查找元素xfor ( i=0; iL.length; i+ )if ( L.elemi=x ) break;if ( iL.length ) 找到;else 未找到;插入算法 ListInsert(&L,i,x)前提：表不滿合理的插入圍：1iL.length+1注：位序i在C/C+中對應于下標i-1。步驟 第i至最后所有元素后移一個元素 在第i個位置插入元素x 表長增1算法bool 這里返回true表示正確插入，返回false表示插入失敗。以下常用來區(qū)分操作是否正確執(zhí)行。 L

32、istInsert XE ListInsert ( SqList& L, int i, DataType x )if ( L.length=MAXSIZE | iL.length+1 ) returnfalse; / 失敗 / 元素后移for ( j=L.length-1; j=i-1; j- ) / 這里j為下標，從L.length-1到i-1 L.elemj+1 = L.elemj; / 若作為位序，有如何修改？ / 插入x L.elemi-1 = x; / 表長增1 L.length+;returntrue; / 插入成功刪除算法 ListDelete(&L,i,&x)前提：表非空合理的

33、刪除圍：1iL.length步驟取出第i個元素第i個元素之后的元素向前移動一個位置表長減1算法bool ListDelete XE ListDelete ( SqList& L, int i, DataType& x )if ( L.length=0 | iL.length ) returnfalse; / 失敗 x = L.elemi-1;for ( j=i; jnext = 0單鏈表不空條件：L-next != 0基本算法（遍歷）順序訪問所有元素借助指針，“順藤摸瓜”(沿著鏈表訪問結(jié)點)。p = L-next; / 注意起始位置的考慮while ( p!=NULL ) / 判表尾，另外 (

34、p!=0)或(p)均可 visit( p-data ); / 訪問:可以換成各種操作 p = p-next; / 指針沿著鏈表向后移動例：打印單鏈表中的數(shù)據(jù)。void PrintLinkList XE PrintLinkList ( LinkList L ) p = L-next;while ( p!=NULL ) print ( p-data ); / 訪問：打印數(shù)據(jù)域 p = p-next; 查找元素x/ 在單鏈表L中查找元素x/ 若找到，返回指向該結(jié)點的指針；否則返回空指針LinkList Find XE Find ( LinkList L, DataType x ) p = L-nex

35、t;while ( p!=NULL ) if ( p-data = x ) return p; / 找到x p = p-next; return NULL; / 未找到/ 在單鏈表L中查找元素x/ 若找到，返回該元素的位序；否則返回0int Find XE Find ( LinkList L, DataType x ) p = L-next; j = 1;while ( p!=NULL ) if ( p-data = x ) return j; / 找到x p = p-next; j+; / 計數(shù)器隨指針改變 return 0; / 未找到前一個算法的另一種寫法：p = L-next;whil

36、e ( p & p-data!=x ) p = p-next;if ( p & p-data=x ) return p;elsereturn 0;或者p = L-next;while ( p & p-data!=x ) p = p-next;return p; / 為什么查找第i個元素LinkList Get XE Get ( LinkList L, int i ) p = L-next; j = 1;while ( p & jnext; j+; if ( p & j=i ) return p;elsereturn 0;查找第i-1個元素p = L; j = 0;while ( p & jne

37、xt; j+;if ( p & j=i-1 ) return p;elsereturn 0;插入算法 ListInsert(&L,i,x)技巧：畫圖輔助分析。思路： 先查找第i-1個元素 若找到，在其后插入新結(jié)點bool 這里返回true表示正確插入，返回false表示插入失敗。 ListInsert XE ListInsert ( LinkList &L, int i, DataType x ) / 查找第i-1個元素p p = L; j = 0;while ( p & jnext; j+; / 若找到，在p后插入xai-1-插入前執(zhí)行之后執(zhí)行之后-pxsai-1-px-sai-1-px-s

38、if ( p & j=i-1 ) s = (LinkList) malloc(sizeof(LNode); s-data = x; s-next = p-next; / p-next = s; / returntrue; / 插入成功 elsereturnfalse; / 插入失敗注意： a) 要讓p指向第i-1個而不是第i個元素（否則，不容易找到前驅(qū)以便插入）。 b) 能夠插入的條件： p & j=i-1 。即使第i個元素不存在，只要存在第i-1個元素，仍然可以插入第i個元素。 c) 新建結(jié)點時需要動態(tài)分配存。 s = (LinkList) malloc(sizeof(LNode); 若檢查

39、是否分配成功，可用if ( s=NULL ) exit(1); / 分配失敗則終止程序 d) 完成插入的步驟：。技巧：先修改新結(jié)點的指針域。刪除算法 ListDelete(&L,i,&x)思路： 先查找第i-1個元素 若找到且其后存在第i個元素，則用x返回數(shù)據(jù)，并刪除之a(chǎn)i-1-刪除前ai-p-sai-1-執(zhí)行之后ai-p-sai-1-執(zhí)行之后ai-p-bool ListDelete XE ListDelete ( LinkList &L, int i, int &x ) / 查找第i-1個元素p p = L; j = 0;while ( p & jnext; j+; /若存在第i個元素，則用

40、x返回數(shù)據(jù)，并刪除之if ( p & j=i-1 & p-next ) / 可以刪除 s = p-next; / p-next = s-next; / x = s-data; free (s);returntrue; elsereturnfalse;注意： a) 要求p找到第i-1個而非第i個元素。為什么？ b) 能夠進行刪除的條件： p & j=i-1 & p-next 。條件中的p-next就是要保證第i個元素存在，否則無法刪除。若寫成p-next & j=i-1也不妥，因為此時(循環(huán)結(jié)束時)可能有p=NULL，所以必須先確定p不空。技巧：將條件中的“大前提”放在前面。該條件也不可以寫成p

41、-next & p & j=i-1，因為先有p!=0才有p-next，上式顛倒了這一關(guān)系。 c) 釋放結(jié)點的方法。 free(s); d) 完成刪除的步驟：。建立鏈表的兩種方法思路： 建立空表（頭結(jié)點）； 依次插入數(shù)據(jù)結(jié)點（每次插入表尾得(a1,a2,an)，每次插入表頭得(an,a2,a1)）。順序建表void CreateLinkList XE CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkList) malloc(sizeof(LNode); L-next = NULL; / 空表 p = L; / 用p指向表尾 / 插入元素f

42、or ( i=0; idata = x; / 插入表尾 s-next = p-next; p-next = s; p = s; / 新的表尾 逆序建表void CreateLinkList XE CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkList) malloc(sizeof(LNode); L-next = NULL; / 空表 / 插入元素for ( i=0; idata = x; / 插入表頭 s-next = L-next; L-next = s; 循環(huán)鏈表特點最后一個結(jié)點的指針指向頭結(jié)點。anCBA(b)(a)Ea1L.

43、L類型定義同單鏈表?；拘螒B(tài)空表：L-next = L。非空表。與單鏈表的聯(lián)系判斷表尾的方法不同：單鏈表用p=NULL；循環(huán)鏈表用p=L。其余操作一樣。雙向循環(huán)鏈表特點一個結(jié)點包含指向后繼(next)和指向前驅(qū)(prior)兩個指針，兩個方向又分別構(gòu)成循環(huán)鏈表。datapriornext類型定義typedefstruct DuLNode DataType data;struct DuLNode *prior, *next; / 兩個指針 DuLNode, *DuLinkList;基本形態(tài)空表：用后向指針判斷L-next = L，或者用前向指針判斷L-prior = L。非空表。a1a2anLL

44、. .與單鏈表和循環(huán)鏈表的聯(lián)系最大不同：前驅(qū)容易求得，可以向前遍歷。判斷表尾的方法與循環(huán)鏈表一樣：p=L。插入和刪除時需要修改兩個方向的指針。插入和刪除需要修改兩個方向的指針。例如：(見下表)表 STYLEREF 1 s2.SEQ 表 * ARABIC s 12 雙向循環(huán)鏈表的插入和刪除p之后插入sp之前插入s刪除p之后繼s刪除ps-next = p-next;p-next = s;s-prior = p;s-next-prior = s;s-prior = p-prior;p-prior = s;s-next = p;s-prior-next = s;s = p-next;p-next =

45、s-next;p-next-prior = p;p-prior-next = p-next;p-next-prior = p-prior;順序表與單鏈表的比較表 STYLEREF 1 s2.SEQ 表 * ARABIC s 13 順序表和單鏈表的比較順序表單鏈表以地址相鄰表示關(guān)系用指針表示關(guān)系隨機訪問，取元素O(1)順序訪問，取元素O(n)插入、刪除需要移動元素O(n)插入、刪除不用移動元素O(n)(用于查找位置)總結(jié)：需要反復插入、刪除，宜采用鏈表；反復提取，很少插入、刪除，宜采用順序表。習題 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 1 將順序表中的元素反轉(zhuǎn)順

46、序。 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 2 在非遞減有序的順序表中插入元素x，并保持有序。 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 3 刪除順序表中所有等于x的元素。 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 4 編寫算法實現(xiàn)順序表元素唯一化(即使順序表中重復的元素只保留一個)，給出算法的時間復雜度。 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 5 非遞減有序的順序表元素唯一化(參見習題REF _Ref944282492.4)，要求算法的時間復雜度為O(n)。 STY

47、LEREF 1 s 2. SEQ 習題 * ARABIC s 1 6 將單鏈表就地逆置，即不另外開辟結(jié)點空間，而將鏈表元素翻轉(zhuǎn)順序。 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 7 采用插入法將單鏈表中的元素排序。 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 8 采用選擇法將單鏈表中的元素排序。 STYLEREF 1 s 2. SEQ 習題 * ARABIC s 1 9 將兩個非遞減有序的單鏈表歸并成一個，仍并保持非遞減有序。棧和隊列基礎(chǔ)知識和算法棧棧，棧頂，棧底，空棧，后進先出(LIFO)，入棧(Push)，出棧(Pop)。順序棧：棧的

48、順序存儲結(jié)構(gòu)；鏈棧：棧的鏈式存儲結(jié)構(gòu)。鏈棧存儲結(jié)構(gòu)a1/anS.an-1用不帶頭結(jié)點的單鏈表實現(xiàn)。類型定義同單鏈表?；拘螒B(tài)a1/anS.an-1S/棧空條件: S = NULL棧非空棧滿（一般不出現(xiàn)）基本算法入棧 Push (&s, x)bool Push XE Push ( LinkList &s, DataType x ) / 新建結(jié)點 p = (LinkList) malloc (sizeof(LNode);if ( !p ) returnfalse; / 失敗 p-data = x; / 插入棧頂 p-next = s; s = p;returntrue;出棧 Pop (&s, &x

49、)前提：棧非空。bool Pop XE Pop ( LinkList &s, DataType &x )if ( s=NULL ) returnfalse; / ?？?/ 刪除棧頂元素 p = s; s = s-next; x = p-data; free ( p );returntrue;棧頂元素前提：棧非空。bool Top XE Top ( LinkList &s, DataType &x )if ( s=NULL ) returnfalse; / ?？?x = s-data;returntrue;順序棧存儲結(jié)構(gòu)類似于順序表，插入和刪除操作固定于表尾。類型定義簡單說，“數(shù)組 + 長度”

50、不準確的說法，只為便于理解和記憶，不要在正式場合引用。constint MAXSIZE = 棧的最大容量；typedefstruct DataType elemMAXSIZE;int top; SqStack;基本形態(tài)?？諚l件 s.top = 0;棧滿條件 s.top = MAXSIZE棧不空、不滿基本算法入棧 Push (&s, x)前提：棧不滿bool Push XE Push ( SqStack& s, DataType x )if ( s.top = MAXSIZE ) returnfalse; / 棧滿 s.elemtop = x; / 或者s.elemtop+ = x; top+;

51、 / 代替這兩行returntrue;出棧 Pop (&s, &x)前提：棧非空bool Pop XE Pop ( SqStack &s, DataType &x )if ( s.top=0 ) returnfalse; top-; / 可用x=s.elem-top; x = s.elemtop; / 代替這兩行returntrue;棧頂元素前提：棧非空s.elemtop-1 即是。隊列隊列，隊頭，隊尾，空隊列，先進先出(FIFO)。鏈隊列：隊列的鏈式存儲結(jié)構(gòu)。循環(huán)隊列：隊列的順序存儲結(jié)構(gòu)之一。鏈隊列存儲結(jié)構(gòu)/-a1-a2-an/.Q.frontQ.rearQ.frontQ.rear簡而言之，

52、“單鏈表 + 尾指針” 不準確的說法，只為便于理解和記憶，不要在正式場合引用。類型定義課本P61。typedefstruct LinkList front; LinkList rear; LinkQueue;基本形態(tài)隊列空：Q.front=Q.rear。非空隊列。基本算法入隊列課本P62。插入隊尾，注意保持Q.rear指向隊尾。出隊列課本P62。刪除隊頭元素，特別注意：如果隊列中只有一個元素，則隊頭也同時是隊尾，刪除隊頭元素后也需要修改隊尾指針。循環(huán)隊列存儲結(jié)構(gòu)簡單說，“數(shù)組 + 頭、尾位置” 不準確的說法，只為便于理解和記憶，不要在正式場合引用。類型定義constint MAXSIZE =

53、隊列最大容量;typedefstruct DataType elemMAXSIZE;int front, rear; / 隊頭、隊尾位置 S ueue;基本形態(tài)通常少用一個元素區(qū)分隊列空和隊列滿，也可以加一標志。約定front指向隊頭元素的位置，rear指向隊尾的下一個位置，隊列容為 front, rear)。隊列空條件：Q.front = Q.rear。不能出隊列。隊列滿條件：(Q.rear+1)%MAXSIZE = Q.front （少用一個元素時）。不能入隊列。隊列不空也不滿frontreara1rearfronta3a2a4a1rearfronta3a2frontreartag:0fr

54、ontreara3a4a1a2frontreartag:1a3a4a5a1a2加一標志區(qū)分隊列空和隊列滿的情況可以用滿所有空間。隊列空和隊列滿時都有Q.front=Q.rear，再用標志區(qū)分。隊列空：Q.front=Q.rear and Q.tag=0；隊列滿：Q.front=Q.rear and Q.tag=1?；舅惴ㄈ腙犃星疤幔宏犃胁粷M。bool EnQueue XE EnQueue ( S ueue &Q, DataType x )if ( (Q.rear+1)%MAXSIZE=Q.front ) returnfalse; / 隊列滿 / 入隊列 Q.elem Q.rear = x;

55、Q.rear = (Q.rear+1)%MAXSIZE;returntrue;出隊列前提：隊列非空。bool DeQueue XE DeQueue ( S ueue &Q, DataType &x )if ( Q.front=Q.rear ) returnfalse; / 隊列空 / 出隊列 x = Q.elem Q.front; Q.front = (Q.front+1)%MAXSIZE;returntrue;隊列中元素個數(shù)結(jié)論：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。int QueueLength

56、 XE QueueLength ( S ueue Q )return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;用標志區(qū)分隊列空和滿用標志區(qū)分隊列空和滿時，隊列初始化、入隊列、出隊列和隊列長度的算法如下：void InitQueue XE InitQueue ( S ueue &Q ) Q.front = Q.rear = 0; Q.tag = 0;bool EnQueue XE EnQueue ( S ueue &Q, DataType x ) if ( Q.front=Q.rear and Q.tag=1 ) returnfalse; Q.elem Q.rear =

57、 x; Q.rear = (Q.rear+1)%MAXSIZE;if ( Q.tag=0 ) Q.tag = 1; / 隊列非空returntrue;bool DeQueue XE DeQueue ( S ueue &Q, DataType &x ) if ( Q.front=Q.rear and Q.tag=0 ) returnfalse; x = Q.elem Q.front ; Q.front = (Q.front+1)%MAXSIZE;if ( Q.front=Q.rear ) Q.tag = 0; / 隊列空returntrue;int QueueLength XE QueueLen

58、gth ( S ueue Q )if ( Q.front=Q.rear and Q.tag=1 )return MAXSIZE; / 隊列滿elsereturn (Q.rear-Q.front+MAXSIZE)%MAXSIZE; / 隊列不滿(包含隊列空的情況)棧和隊列比較都是線形結(jié)構(gòu)，棧的操作LIFO（后進先出），隊列操作FIFO（先進先出）。簡化的棧和隊列結(jié)構(gòu)在算法中使用棧和隊列時可以采用簡化的形式。表 STYLEREF 1 s3.SEQ 表 * ARABIC s 11 簡化的棧和隊列結(jié)構(gòu)簡化棧簡化隊列結(jié)構(gòu)“s + top”結(jié)構(gòu)“q + front + rear”初始化top = 0;初始

59、化front=rear=0;入棧stop+ = x;入隊列qrear = x;rear = (rear+1)%MAXSIZE;出棧x = s-top;出隊列x = qfront;front = (front+1)%MAXSIZE;棧頂stop-1隊列頭qfront?？誸op = 0隊列空front = rear說明：只要棧(隊列)的容量足夠大，算法中可以省去檢查棧(隊列)滿的情況。棧和隊列的應用表達式求值參見課本P53。括號匹配例：檢查表達式中的括號是否正確匹配。如 ( ) 正確，( ) 則錯誤。分析：每個左括號都“期待”對應的右括號，匹配成功則可以消去。思路：遇到左括號則入棧，遇到右括號則與

60、棧頂括號相比較，如果匹配則消去，否則匹配失敗。當然，如果棧中沒有括號可以匹配，或者最后棧中還有未匹配的左括號，也都是匹配錯誤。/ 檢查輸入的表達式中括號是否匹配bool MatchBrackets XE MatchBrackets ()constint MAXSIZE = 1024; / 棧的最大容量char s MAXSIZE; / 簡化的棧結(jié)構(gòu)int top; / 棧頂 / 棧初始化 top = 0; / 檢查括號是否匹配 ch = getchar();while ( ch!=EOF ) switch ( ch ) case (, , : s top+ = ch; / 所有左括號入棧bre