前言緣起數(shù)據(jù)結(jié)構(gòu)是一門計算機專業(yè)基礎(chǔ)課，各類計算機考試都禁不住要考它，專升本考試自然也不例外。我給學(xué)生輔導(dǎo)這門課程已經(jīng)有幾個年頭了，講稿換了幾次，逐漸豐富起來。加之看到學(xué)生們埋頭記筆記時辛苦的樣子，就產(chǎn)生了寫一本小冊子的想法。另外，還有一層意思就是對數(shù)次輔導(dǎo)進行總結(jié)，以便交流之用。說明首先，需要說明的是這本書在語言風(fēng)格上不太講究，常有些不嚴(yán)謹?shù)谋磉_，或調(diào)侃，或土得掉渣，難登大雅之堂，請勿在正規(guī)場合引用這些說法。這樣做的目的，僅僅是為了更簡練、更直接地描述思想，方便理解、記憶和使用。凡是這種情況，往往都用引號括起來，并加以腳注說明。還有，本書需配合數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)教材使用。由于篇幅有限，多數(shù)概念、術(shù)語沒有詳釋。 另外，每章之后都配有習(xí)題，或多或少，難度不一，并沒有局限于專升本的要求。對所有習(xí)題都提供了參考答案。致謝我要感謝所有給予我?guī)椭娜?。張志老師的大力支持和幫助使得本書得以面世，他還提供了近年專升本試題。李永干老師的幫助使得本書順利印刷。譚業(yè)武老師給了我很大支持，還提出了很多建議。最后，我要感謝隆坤，她總是給我最大的支持，使那些本來只在我想象中的事情變成現(xiàn)實。莊波于濱州學(xué)院2005年2月26日第0章 復(fù)習(xí)提示1一、 教材內(nèi)容1二、 復(fù)習(xí)提示11. 經(jīng)典算法12. 緒論13. 線性表14. 棧和隊列25. 串26. 樹和二叉樹27. 圖28. 查找表39. 內(nèi)部排序3第1章 緒論5一、 基礎(chǔ)知識5二、 算法5三、 習(xí)題6第2章 線性表7一、 基礎(chǔ)知識和算法71. 線性表及其特點72. 順序表線性表的順序存儲結(jié)構(gòu)73. 單鏈表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)之一104. 循環(huán)鏈表155. 雙向循環(huán)鏈表156. 順序表與單鏈表的比較16二、 習(xí)題16第3章 棧和隊列17一、 基礎(chǔ)知識和算法171. 棧172. 鏈棧173. 順序棧184. 隊列195. 鏈隊列206. 循環(huán)隊列207. 棧和隊列比較228. 簡化的棧和隊列結(jié)構(gòu)239. 棧和隊列的應(yīng)用23二、 習(xí)題24第4章 串25一、 基礎(chǔ)知識和算法251. 概念252. 串的基本操作253. 串的存儲結(jié)構(gòu)25二、 習(xí)題25第6章 樹和二叉樹27一、 基礎(chǔ)知識和算法271. 樹及有關(guān)概念272. 二叉樹273. 二叉樹的性質(zhì)274. 二叉樹的存儲結(jié)構(gòu)285. 二叉樹的五種基本形態(tài)286. 遍歷二叉樹297. 遍歷二叉樹的應(yīng)用338. 線索二叉樹349. 樹和森林3510. 赫夫曼樹及其應(yīng)用36二、 習(xí)題37第7章 圖39一、 基礎(chǔ)知識和算法391. 圖的有關(guān)概念392. 圖的存儲結(jié)構(gòu)393. 圖的遍歷424. 最小生成樹445. 拓撲排序466. 關(guān)鍵路徑467. 最短路徑47二、 習(xí)題49第9章 查找51一、 基礎(chǔ)知識和算法511. 有關(guān)概念512. 順序查找513. 折半查找524. 索引順序表545. 二叉排序樹546. 平衡二叉樹577. B-樹和B+樹588. 鍵樹599. 哈希表59二、 習(xí)題61第10章 內(nèi)部排序63一、 基礎(chǔ)知識和算法631. 排序的有關(guān)概念632. 直接插入排序633. 折半插入排序644. 希爾排序（縮小增量排序）645. 起泡排序656. 快速排序667. 簡單選擇排序678. 堆排序689. 歸并排序7110. 基數(shù)排序7211. 各種排序方法比較73- III - 11. 各種排序方法比較第0章 復(fù)習(xí)提示一、 教材內(nèi)容l 使用教材數(shù)據(jù)結(jié)構(gòu)C語言版 嚴(yán)蔚敏，清華大學(xué)出版社。l 章節(jié) 去掉 第5、8、11、12章 去掉 *部分 去掉1.3，2.4，4.4二、 復(fù)習(xí)提示1. 經(jīng)典算法單鏈表：遍歷、插入、刪除循環(huán)隊列：隊列空、隊列滿的條件二叉樹：遞歸遍歷及應(yīng)用有序表的二分法查找快速排序簡單選擇排序2. 緒論掌握幾個重要概念數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、算法時間復(fù)雜度的簡單計算（C 記號C，表示要求掌握計算方法，會計算。本節(jié)下同。）掌握幾種說法數(shù)據(jù)元素是，數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中關(guān)系的四種基本結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義算法的五個特征3. 線性表線性表的概念和四個特征順序表和單鏈表的類型定義在順序表中查找、插入、刪除，靈活運用在單鏈表中查找、插入、刪除，靈活運用循環(huán)鏈表及雙向鏈表的定義、插入、刪除算法：單鏈表的算法，靈活運用、會編程（P 記號P，要求達到編寫算法和程序的能力。本節(jié)下同。）4. 棧和隊列棧和隊列的概念、特點入棧、出棧操作，靈活掌握了解棧的實現(xiàn)：鏈棧和順序棧（A 記號A，要求掌握算法思想，會演算。本節(jié)下同。算法，P）了解隊列的實現(xiàn)，鏈隊列和循環(huán)隊列，注意鏈隊列中的出隊列操作算法：注意循環(huán)隊列空和滿的條件（A，P）會運用棧和隊列5. 串掌握相關(guān)概念會運用串的基本操作（C），特別是Concat()，Substring()，Index()和Replace()知道串的三種存儲結(jié)構(gòu)及其特點6. 樹和二叉樹樹和二叉樹的有關(guān)概念二叉樹的性質(zhì)熟練掌握遍歷二叉樹的遞歸算法，并靈活運用知道線索二叉樹，會對二叉樹進行線索化樹、森林和二叉樹的轉(zhuǎn)化，會遍歷樹和森林赫夫曼樹及其應(yīng)用算法： 遞歸遍歷二叉樹及其應(yīng)用（P） 構(gòu)造赫夫曼樹和赫夫曼編碼（A） 樹和二叉樹的轉(zhuǎn)換（A） 森林和二叉樹的轉(zhuǎn)換（A） 遍歷樹和森林（A）7. 圖圖的有關(guān)概念熟練掌握圖的各種存儲結(jié)構(gòu)圖的遍歷：深度優(yōu)先、廣度優(yōu)先（A）最小生成樹算法（兩個）及其特點（A）拓撲排序（A）關(guān)鍵路徑算法（A）最短路徑算法（兩個）（A，O 記號O，要求掌握算法的時間復(fù)雜度。本節(jié)下同。：時間復(fù)雜度）8. 查找表查找的有關(guān)概念，ASL等順序查找（A，P）熟練掌握有序表的折半查找算法（A，P，C）了解索引順序表熟練掌握二叉排序樹的概念，建立（A），查找（A，P），刪除（A），計算ASL（C）平衡二叉排序樹的概念，建立（A），判斷失去平衡的類型，平衡化（A），計算ASL（C）了解B_樹，B+樹的概念和特點知道鍵樹（數(shù)字查找樹）哈希表的概念、特點、構(gòu)造哈希表（A），計算ASL和裝填因子（C）了解各種查找表的性能（O）9. 內(nèi)部排序直接插入排序（A）折半插入排序（A，P）希爾排序（A）起泡排序（A）快速排序（A，P，O）簡單選擇排序（P，A，O）堆的概念，調(diào)整成堆（A），堆排序（A，O）歸并排序（A，O）鏈?zhǔn)交鶖?shù)排序（A，O）各種排序算法的對比結(jié)論（O）- 98 -第1章 緒論一、 基礎(chǔ)知識概念和術(shù)語(黑體字部分)。另外，注意：1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。P42、數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。P53、數(shù)據(jù)結(jié)構(gòu)及其形式定義。P5四種基本結(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)）位置“相鄰” 非順序映像（鏈?zhǔn)酱鎯Y(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、算法的時間復(fù)雜度 P15 常見有： O(1)，O(n)，O(n2)，O(log2n) 分析算法的時間復(fù)雜度時，log2n常簡單記作log n。，O(n log2n)，O(2n) 語句頻度，用歸納法計算。10、算法的空間復(fù)雜度 P17二、 算法起泡排序。P16另一種形式void BubbleSort ( DataType a, int n ) for ( i=0; i<n-1; i+ ) for ( j=0; j<n-i-1; j+ ) if ( aj>aj+1 ) aj<>aj+1;或void BubbleSort ( DataType a, int n ) for ( i=1; i<n; i+ ) for ( j=0; j<n-i; j+ ) if( aj>aj+1 ) aj<>aj+1;或void BubbleSort ( DataType a, int n ) for ( i=0; i<n-1; i+ ) change = fasle; for ( j=0; j<n-i-1; j+ ) if ( aj>aj+1 ) aj<>aj+1; change = true; if ( !change ) break; 說明：a) 考試中要求寫算法時，可用類C，也可用C程序。b) 盡量書寫算法說明，言簡意賅。c) 技巧：用“邊界值驗證法”檢查下標(biāo)越界錯誤。 如上第一個： 第二個循環(huán)條件若寫作j<n-i，則當(dāng)i=0時 aj+1會越界。d) 時間復(fù)雜度為O(n2)，第3個在最好情況下（待排記錄有序），時間復(fù)雜度為O(n)。三、 習(xí)題1.1 編寫冒泡排序算法，使結(jié)果從大到小排列。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;/ 第2章 線性表一、 基礎(chǔ)知識和算法1. 線性表及其特點線性表是n個數(shù)據(jù)元素的有限序列。線性結(jié)構(gòu)的特點： “第一個” “最后一個” 前驅(qū) 后繼。 這里太簡煉了，只是為了便于記憶。2. 順序表線性表的順序存儲結(jié)構(gòu)(1) 特點a) 邏輯上相鄰的元素在物理位置上相鄰。b) 隨機訪問。(2) 類型定義簡而言之，“數(shù)組+長度” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。凡此情形，都加引號以示提醒。const int MAXSIZE = 線性表最大長度;typedef structDataType elemMAXSIZE;int length; SqList;注：a) SqList為類型名，可換用其他寫法。 b) DataType是數(shù)據(jù)元素的類型，根據(jù)需要確定。 c) MAXSIZE根據(jù)需要確定。如const int MAXSIZE=64; d) 課本上的SqList類型可在需要時增加存儲空間，在上面這種定義下不可以。(這樣做避免了動態(tài)內(nèi)存分配，明顯減少了算法的復(fù)雜程度，容易理解。而且，原來Pascal版本的數(shù)據(jù)結(jié)構(gòu)（嚴(yán)蔚敏）就是這樣做的。) e) 課本上的SqList類型定義中l(wèi)istsize表示已經(jīng)分配的空間大小（容納數(shù)據(jù)元素的個數(shù)）。當(dāng)插入元素而遇到L.length=L.listsize時，用realloc (L.elem, L.listsize+增量) 重新分配內(nèi)存，而realloc()函數(shù)在必要的時候自動復(fù)制原來的元素到新分配的空間中。(3) 基本形態(tài)1°. 順序表空01MAXSIZE-1.L.elemL.elemL.elemL.length=0L.length=MAXSIZE0<L.length<MAXSIZE條件 L.length=0不允許刪除操作2°. 順序表滿條件 L.length=MAXSIZE不允許插入操作3°. 不空也不滿可以插入，刪除(4) 基本算法遍歷1°. 順序訪問所有元素for ( i=0; i<L.length; i+ ) visit ( L.elemi );2°. 查找元素xfor ( i=0; i<L.length; i+ ) if ( L.elemi=x ) break;if ( i<L.length ) 找到;else 未找到;(5) 插入算法 ListInsert(&L,i,x)1°. 前提：表不滿2°. 合理的插入范圍：1iL.length+1注：位序i在C/C+中對應(yīng)于下標(biāo)i-1。3°. 步驟 第i至最后所有元素后移一個元素 在第i個位置插入元素x 表長增14°. 算法bool 這里返回true表示正確插入，返回false表示插入失敗。以下常用來區(qū)分操作是否正確執(zhí)行。 ListInsert ( SqList& L, int i, DataType x ) if ( L.length=MAXSIZE | i<1 | i>L.length+1 ) return false; / 失敗 / 元素后移 for ( j=L.length-1; j>=i-1; j- ) / 這里j為下標(biāo)，從L.length-1到i-1 L.elemj+1 = L.elemj; / 若作為位序，有如何修改？ / 插入x L.elemi-1 = x; / 表長增1 L.length+; return true; / 插入成功(6) 刪除算法 ListDelete(&L,i,&x)1°. 前提：表非空2°. 合理的刪除范圍：1iL.length3°. 步驟取出第i個元素第i個元素之后的元素向前移動一個位置表長減14°. 算法bool ListDelete ( SqList& L, int i, DataType& x ) if ( L.length=0 | i<1 | i>L.length ) return false; / 失敗 x = L.elemi-1; for ( j=i; j<L.length; j+ ) L.elemj-1 = L.elemj; L.length-; return true; / 刪除成功(7) 算法分析表 2.1 順序表插入和刪除算法的分析插入刪除基本操作平均移動次數(shù)移動元素移動元素時間復(fù)雜度O(n)O(n)尾端操作插入第n+1個元素，不移動刪除第n個元素，不移動插入、刪除需移動大量元素O(n)；但在尾端插入、刪除效率高O(1)。(8) 其他算法1°. InitList (&L), ClearList (&L) L.length = 0;2°. ListEmpty (L) return L.length = 0;3°. ListLength (L) return L.length;4°. GetElem (L, i, &e) e = L.elemi-1;3. 單鏈表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)之一(1) 概念線性鏈表，單鏈表，結(jié)點；數(shù)據(jù)域，指針域；頭指針，頭結(jié)點。(2) 特點用指針表示數(shù)據(jù)之間的邏輯關(guān)系（邏輯相鄰的元素物理位置不一定相鄰）。(3) 類型定義簡而言之，“數(shù)據(jù) + 指針” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。datanexttypedef struct LNode DataType data; struct LNode *next; LNode, *LinkList;(4) 基本形態(tài)帶頭結(jié)點的單鏈表的基本形態(tài)有：1°. 單鏈表空/an/CBA(b)(a)Ea1LL.條件： L->next = 02°. 單鏈表不空條件：L->next != 0(5) 基本算法 （遍歷）1°. 順序訪問所有元素借助指針，“順藤摸瓜”(沿著鏈表訪問結(jié)點)。p = L->next; / 注意起始位置的考慮while ( p!=NULL ) / 判表尾，另外 (p!=0)或(p)均可 visit( p->data ); / 訪問:可以換成各種操作 p = p->next; / 指針沿著鏈表向后移動例：打印單鏈表中的數(shù)據(jù)。void PrintLinkList ( LinkList L ) p = L->next; while ( p!=NULL ) print ( p->data ); / 訪問：打印數(shù)據(jù)域 p = p->next; 2°. 查找元素x/ 在單鏈表L中查找元素x/ 若找到，返回指向該結(jié)點的指針；否則返回空指針LinkList Find ( LinkList L, DataType x ) p = L->next; while ( p!=NULL ) if ( p->data = x ) return p; / 找到x p = p->next; return NULL; / 未找到/ 在單鏈表L中查找元素x/ 若找到，返回該元素的位序；否則返回0int 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;while ( p && p->data!=x ) p = p->next;if ( p && p->data=x ) return p;else return 0;或者p = L->next;while ( p && p->data!=x ) p = p->next;return p; / 為什么3°. 查找第i個元素LinkList Get ( LinkList L, int i ) p = L->next; j = 1; while ( p && j<i ) p = p->next; j+; if ( p && j=i ) return p; else return 0;4°. 查找第i-1個元素p = L; j = 0;while ( p && j<i-1 ) p = p->next; j+;if ( p && j=i-1 ) return p;else return 0;(6) 插入算法 ListInsert(&L,i,x)技巧：畫圖輔助分析。思路： 先查找第i-1個元素 若找到，在其后插入新結(jié)點bool 這里返回true表示正確插入，返回false表示插入失敗。 ListInsert ( LinkList &L, int i, DataType x ) / 查找第i-1個元素p p = L; j = 0; while ( p && j<i-1 ) p = p->next; j+; / 若找到，在p后插入xai-1·-插入前執(zhí)行之后執(zhí)行之后·-pxsai-1·-·-px·-sai-1·-·-px·-s if ( p && j=i-1 ) s = (LinkList) malloc(sizeof(LNode); s->data = x; s->next = p->next; / p->next = s; / return true; / 插入成功 else return false; / 插入失敗注意： a) 要讓p指向第i-1個而不是第i個元素（否則，不容易找到前驅(qū)以便插入）。 b) 能夠插入的條件： p && j=i-1 。即使第i個元素不存在，只要存在第i-1個元素，仍然可以插入第i個元素。 c) 新建結(jié)點時需要動態(tài)分配內(nèi)存。 s = (LinkList) malloc(sizeof(LNode); 若檢查是否分配成功，可用 if ( s=NULL ) exit(1); / 分配失敗則終止程序 d) 完成插入的步驟：。技巧：先修改新結(jié)點的指針域。(7) 刪除算法 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 ( LinkList &L, int i, int &x ) / 查找第i-1個元素p p = L; j = 0; while ( p && j<i-1 ) p = p->next; j+; /若存在第i個元素，則用x返回數(shù)據(jù)，并刪除之 if ( p && j=i-1 && p->next ) / 可以刪除 s = p->next; / p->next = s->next; / x = s->data; free (s); return true; else return false;注意： 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->next && p && j=i-1，因為先有p!=0才有p->next，上式顛倒了這一關(guān)系。 c) 釋放結(jié)點的方法。 free(s); d) 完成刪除的步驟：。(8) 建立鏈表的兩種方法思路： 建立空表（頭結(jié)點）； 依次插入數(shù)據(jù)結(jié)點（每次插入表尾得(a1,a2,an)，每次插入表頭得(an,a2,a1)）。1°. 順序建表void CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkList) malloc(sizeof(LNode); L->next = NULL; / 空表 p = L; / 用p指向表尾 / 插入元素 for ( i=0; i<n; i+ ) scanf ( x ); s = (LinkList) malloc(sizeof(LNode); s->data = x; / 插入表尾 s->next = p->next; p->next = s; p = s; / 新的表尾 2°. 逆序建表void CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkList) malloc(sizeof(LNode); L->next = NULL; / 空表 / 插入元素 for ( i=0; i<n; i+ ) scanf ( x ); s = (LinkList) malloc(sizeof(LNode); s->data = x; / 插入表頭 s->next = L->next; L->next = s; 4. 循環(huán)鏈表(1) 特點最后一個結(jié)點的指針指向頭結(jié)點。anCBA(b)(a)Ea1L.L(2) 類型定義同單鏈表。(3) 基本形態(tài)空表：L->next = L。非空表。(4) 與單鏈表的聯(lián)系判斷表尾的方法不同：單鏈表用p=NULL；循環(huán)鏈表用p=L。其余操作相同。5. 雙向循環(huán)鏈表(1) 特點一個結(jié)點包含指向后繼(next)和指向前驅(qū)(prior)兩個指針，兩個方向又分別構(gòu)成循環(huán)鏈表。datapriornext(2) 類型定義typedef struct DuLNode DataType data; struct DuLNode *prior, *next; / 兩個指針 DuLNode, *DuLinkList;(3) 基本形態(tài)空表：用后向指針判斷L->next = L，或者用前向指針判斷L->prior = L。非空表。a1a2anLL. .(4) 與單鏈表和循環(huán)鏈表的聯(lián)系最大不同：前驅(qū)容易求得，可以向前遍歷。判斷表尾的方法與循環(huán)鏈表相同：p=L。插入和刪除時需要修改兩個方向的指針。(5) 插入和刪除需要修改兩個方向的指針。例如：(見下表)表 2.2 雙向循環(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 = s->next;p->next->prior = p;p->prior->next = p->next;p->next->prior = p->prior;6. 順序表與單鏈表的比較表 2.3 順序表和單鏈表的比較順序表單鏈表以地址相鄰表示關(guān)系用指針表示關(guān)系隨機訪問，取元素O(1)順序訪問，取元素O(n)插入、刪除需要移動元素O(n)插入、刪除不用移動元素O(n)(用于查找位置)總結(jié)：需要反復(fù)插入、刪除，宜采用鏈表；反復(fù)提取，很少插入、刪除，宜采用順序表。二、 習(xí)題2.1 將順序表中的元素反轉(zhuǎn)順序。2.2 在非遞減有序的順序表中插入元素x，并保持有序。2.3 刪除順序表中所有等于x的元素。2.4 編寫算法實現(xiàn)順序表元素唯一化(即使順序表中重復(fù)的元素只保留一個)，給出算法的時間復(fù)雜度。2.5 非遞減有序的順序表元素唯一化(參見習(xí)題2.4)，要求算法的時間復(fù)雜度為O(n)。2.6 將單鏈表就地逆置，即不另外開辟結(jié)點空間，而將鏈表元素翻轉(zhuǎn)順序。2.7 采用插入法將單鏈表中的元素排序。2.8 采用選擇法將單鏈表中的元素排序。2.9 將兩個非遞減有序的單鏈表歸并成一個，仍并保持非遞減有序。第3章 棧和隊列一、 基礎(chǔ)知識和算法1. 棧棧，棧頂，棧底，空棧，后進先出(LIFO)，入棧(Push)，出棧(Pop)。順序棧：棧的順序存儲結(jié)構(gòu)；鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2. 鏈棧(1) 存儲結(jié)構(gòu)a1/anS.an-1用不帶頭結(jié)點的單鏈表實現(xiàn)。(2) 類型定義同單鏈表。(3) 基本形態(tài)a1/anS.an-1S/1°. ?？諚l件: S = NULL2°. 棧非空3°. 棧滿（一般不出現(xiàn)）(4) 基本算法1°. 入棧 Push (&s, x)bool Push ( LinkList &s, DataType x ) / 新建結(jié)點 p = (LinkList) malloc (sizeof(LNode); if ( !p ) return false; / 失敗 p->data = x; / 插入棧頂 p->next = s; s = p; return true;2°. 出棧 Pop (&s, &x)前提：棧非空。bool Pop ( LinkList &s, DataType &x ) if ( s=NULL ) return false; / ?？?/ 刪除棧頂元素 p = s; s = s->next; x = p->data; free ( p ); return true;3°. 棧頂元素前提：棧非空。bool Top ( LinkList &s, DataType &x ) if ( s=NULL ) return false; / ?？?x = s->data; return true;3. 順序棧(1) 存儲結(jié)構(gòu)類似于順序表，插入和刪除操作固定于表尾。(2) 類型定義簡單說，“數(shù)組 + 長度” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。const int MAXSIZE = 棧的最大容量；typedef struct DataType elemMAXSIZE; int top; SqStack;(3) 基本形態(tài)1°. ?？諚l件 s.top = 0;2°. 棧滿條件 s.top = MAXSIZE3°. 棧不空、不滿(4) 基本算法1°. 入棧 Push (&s, x)前提：棧不滿bool Push ( SqStack& s, DataType x ) if ( s.top = MAXSIZE ) return false; / 棧滿 s.elemtop = x; / 或者s.elemtop+ = x; top+; / 代替這兩行 return true;2°. 出棧 Pop (&s, &x)前提：棧非空bool Pop ( SqStack &s, DataType &x ) if ( s.top=0 ) return false; top-; / 可用x=s.elem-top; x = s.elemtop; / 代替這兩行 return true;3°. 棧頂元素前提：棧非空s.elemtop-1 即是。4. 隊列隊列，隊頭，隊尾，空隊列，先進先出(FIFO)。鏈隊列：隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)。循環(huán)隊列：隊列的順序存儲結(jié)構(gòu)之一。5. 鏈隊列(1) 存儲結(jié)構(gòu)/·-a1·-a2·-an/.Q.frontQ.rearQ.frontQ.rear簡而言之，“單鏈表 + 尾指針” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。(2) 類型定義課本P61。typedef struct LinkList front; LinkList rear; LinkQueue;(3) 基本形態(tài)隊列空：Q.front=Q.rear。非空隊列。(4) 基本算法1°. 入隊列課本P62。插入隊尾，注意保持Q.rear指向隊尾。2°. 出隊列課本P62。刪除隊頭元素，特別注意：如果隊列中只有一個元素，則隊頭也同時是隊尾，刪除隊頭元素后也需要修改隊尾指針。6. 循環(huán)隊列(1) 存儲結(jié)構(gòu)簡單說，“數(shù)組 + 頭、尾位置” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。(2) 類型定義const int MAXSIZE = 隊列最大容量;typedef struct DataType elemMAXSIZE; int front, rear; / 隊頭、隊尾位置 SqQueue;(3) 基本形態(tài)通常少用一個元素區(qū)分隊列空和隊列滿，也可以加一標(biāo)志。約定front指向隊頭元素的位置，rear指向隊尾的下一個位置，隊列內(nèi)容為 front, rear)。1°. 隊列空條件：Q.front = Q.rear。不能出隊列。2°. 隊列滿條件：(Q.rear+1)%MAXSIZE = Q.front （少用一個元素時）。不能入隊列。3°. 隊列不空也不滿frontreara1rearfronta3a2a4a1rearfronta3a2frontreartag:0frontreara3a4a1a2frontreartag:1a3a4a5a1a24°. 加一標(biāo)志區(qū)分隊列空和隊列滿的情況可以用滿所有空間。隊列空和隊列滿時都有Q.front=Q.rear，再用標(biāo)志區(qū)分。隊列空：Q.front=Q.rear and Q.tag=0；隊列滿：Q.front=Q.rear and Q.tag=1。(4) 基本算法1°. 入隊列前提：隊列不滿。bool EnQueue ( SqQueue &Q, DataType x ) if ( (Q.rear+1)%MAXSIZE=Q.front ) return false; / 隊列滿 / 入隊列 Q.elem Q.rear = x; Q.rear = (Q.rear+1)%MAXSIZE; return true;2°. 出隊列前提：隊列非空。bool DeQueue ( SqQueue &Q, DataType &x ) if ( Q.front=Q.rear ) return false; / 隊列空 / 出隊列 x = Q.elem Q.front; Q.front = (Q.front+1)%MAXSIZE; return true;3°. 隊列中元素個數(shù)結(jié)論：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。int QueueLength ( SqQueue Q ) return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;4°. 用標(biāo)志區(qū)分隊列空和滿用標(biāo)志區(qū)分隊列空和滿時，隊列初始化、入隊列、出隊列和隊列長度的算法如下：void InitQueue ( SqQueue &Q ) Q.front = Q.rear = 0; Q.tag = 0;bool EnQueue ( SqQueue &Q, DataType x ) if ( Q.front=Q.rear and Q.tag=1 ) return false; Q.elem Q.rear = x; Q.rear = (Q.rear+1)%MAXSIZE; if ( Q.tag=0 ) Q.tag = 1; / 隊列非空 return true;bool DeQueue ( SqQueue &Q, DataType &x ) if ( Q.front=Q.rear and Q.tag=0 ) return false; x = Q.elem Q.front ; Q.front = (Q.front+1)%MAXSIZE; if ( Q.front=Q.rear ) Q.tag = 0; / 隊列空 return true;int QueueLength ( SqQueue Q ) if ( Q.front=Q.rear and Q.tag=1 ) return MAXSIZE; / 隊列滿 else return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; / 隊列不滿(包含隊列空的情況)7. 棧和隊列比較都是線形結(jié)構(gòu)，棧的操作LIFO（后進先出），隊列操作FIFO（先進先出）。8. 簡化的棧和隊列結(jié)構(gòu)在算法中使用棧和隊列時可以采用簡化的形式。表 3.1 簡化的棧和隊列結(jié)構(gòu)簡化棧簡化隊列結(jié)構(gòu)“s + top”結(jié)構(gòu)“q + front + rear”初始化top = 0;初始化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說明：只要棧(隊列)的容量足夠大，算法中可以省去檢查棧(隊列)滿的情況。9. 棧和隊列的應(yīng)用1°. 表達式求值參見課本P53。2°. 括號匹配例：檢查表達式中的括號是否正確匹配。如 ( ) 正確，( ) 則錯誤。分析：每個左括號都“期待”對應(yīng)的右括號，匹配成功則可以消去。思路：遇到左括號則入棧，遇到右括號則與棧頂括號相比較，如果匹配則消去，否則匹配失敗。當(dāng)然，如果棧中沒有括號可以匹配，或者最后棧中還有未匹配的左括號，也都是匹配錯誤。/ 檢查輸入的表達式中括號是否匹配bool MatchBrackets () const int MAXSIZE = 1024; / 棧的最大容量 char s MAXSIZE; / 簡化的棧結(jié)構(gòu) int top; / 棧頂 / 棧初始化 top = 0; / 檢查括號是否匹配 ch = getchar(); while ( ch!=EOF ) switch ( ch ) case (, , : s top+ = ch; / 所有左括號入棧 break; case ): if ( top=0 or s -top!=( ) return false; / 棧空或右括號與棧頂左括號失配 case : if ( top=0 or s -top!= ) return false; case : if ( top=0 or s -top!= ) return false; ch = getchar(); / 取下一個字符 if ( top=0 ) return true; / 正好匹配 else return false; / 棧中尚有未匹配的左括號3°. 遞歸程序的非遞歸化將遞歸程序轉(zhuǎn)化為非遞歸程序時常使用棧來實現(xiàn)。4°. 作業(yè)排隊如操作系統(tǒng)中的作業(yè)調(diào)度中的作業(yè)排隊，打印機的打印作業(yè)也排成隊列。5°. 按層次遍歷二叉樹void LevelOrder ( BinTree bt, VisitFunc visit ) const int MAXSIZE = 1024; / 隊列容量(足夠大即可) BinTree q MAXSIZE; / 簡化的隊列結(jié)構(gòu) int front, rear; / 隊頭、隊尾 if ( ! bt ) return ; / 初始化隊列，根結(jié)點入隊列 front = rear = 0; q rear = bt; rear = (rear+1)%MAXSIZE; / 隊列不空，則取出隊頭訪問并將其左右孩子入隊列 while ( front!=rear ) p = q front; front = (front+1)%MAXSIZE; if ( p ) visit ( p->data ); / 訪問結(jié)點 q rear = p->lchild; rear = (rear+1)%MAXSIZE; q rear = p->rchild; rear = (rear+1)%MAXSIZE; 二、 習(xí)題3.1 元素1,2,3,4依次入棧，不可能的出棧序列有哪些？3.2 設(shè)循環(huán)隊列Q少用一個元素區(qū)分隊列空和隊列滿，MAXSIZE=5，Q.front=Q.rear=0，畫出執(zhí)行下列操作時隊列空和隊列滿的狀態(tài)。入隊列a,b,c，出隊列a,b,c，入隊列d,e,f,g。3.3 編寫算法利用棧將隊列中的元素翻轉(zhuǎn)順序。第4章 串一、 基礎(chǔ)知識和算法1. 概念串，空串，空格串，串的長度；子串，子串在主串中的位置，主串；串相等。2. 串的基本操作表 4.1 串的基本操作Assign (s, t), Create (s, cs)Assign(s,t)將變量t賦值給s，Create(s,cs)根據(jù)字串創(chuàng)建變量s。Equal (s, t), Length (s)判斷串相等，求串長度。如Length(“”)=0。Concat (s, t)串連接。如Concat(“ab”,”cd”)=”abcd”。Substr (s, pos, len)取子串，pos為開始位置，len為子串長度。Index (s, t)求子串t在主串s中的位置。如Index(“abc”,”ab”)=1，Index(“a bc”,”bc”)=3。Replace (s, t, v)把串s中的字串t替換成v。如Replace(“aaa”,”aa”,”a”)=”aa”。Delete (s, pos, len)刪除串s的一部分。注：完成習(xí)題集4.14.6。3. 串的存儲結(jié)構(gòu)表 4.2 串的存儲結(jié)構(gòu)定長順序串最大長度固定，超過最大長度則作截斷處理堆分配存儲表示串的長度幾乎沒有限制塊鏈存儲表示塊內(nèi)存儲空間連續(xù)，塊間不連續(xù)二、 習(xí)題4.1 長度為n的串的子串最多有多少個？第5章 數(shù)組和廣義表(略)第6章 樹和二叉樹一、 基礎(chǔ)知識和算法1. 樹及有關(guān)概念樹，根，子樹；結(jié)點，結(jié)點的度，葉子（終端結(jié)點），分支結(jié)點（非終端結(jié)點），內(nèi)部結(jié)點，樹的度；孩子，雙親，兄弟，祖先，子孫，堂兄弟；層次（根所在層為第1層），深度，高度；有序樹，無序樹，二叉樹是有序樹；森林。2. 二叉樹二叉樹（二叉樹與度為2的樹不同，二叉樹的度可能是0，1，2）；左孩子，右孩子。二叉樹的五種基本形態(tài)。3. 二叉樹的性質(zhì)1°. 二叉樹的第i