第0章 復(fù)習(xí)提示1一、 教材內(nèi)容1二、 復(fù)習(xí)提示11. 經(jīng)典算法12. 緒論13. 線性表14. 棧和隊(duì)列25. 串26. 樹(shù)和二叉樹(shù)27. 圖28. 查找表39. 內(nèi)部排序3第1章 緒論5一、 基礎(chǔ)知識(shí)5二、 算法5三、 習(xí)題6第2章 線性表7一、 基礎(chǔ)知識(shí)和算法71. 線性表及其特點(diǎn)72. 順序表線性表的順序存儲(chǔ)結(jié)構(gòu)73. 單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)之一104. 循環(huán)鏈表155. 雙向循環(huán)鏈表156. 順序表與單鏈表的比較16二、 習(xí)題16第3章 棧和隊(duì)列17一、 基礎(chǔ)知識(shí)和算法171. 棧172. 鏈棧173. 順序棧184. 隊(duì)列195. 鏈隊(duì)列206. 循環(huán)隊(duì)列207. 棧和隊(duì)列比較238. 簡(jiǎn)化的棧和隊(duì)列結(jié)構(gòu)239. 棧和隊(duì)列的應(yīng)用23二、 習(xí)題25第4章 串25一、 基礎(chǔ)知識(shí)和算法251. 概念252. 串的基本操作253. 串的存儲(chǔ)結(jié)構(gòu)25二、 習(xí)題26第6章 樹(shù)和二叉樹(shù)27一、 基礎(chǔ)知識(shí)和算法271. 樹(shù)及有關(guān)概念272. 二叉樹(shù)273. 二叉樹(shù)的性質(zhì)274. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)285. 二叉樹(shù)的五種基本形態(tài)286. 遍歷二叉樹(shù)297. 遍歷二叉樹(shù)的應(yīng)用338. 線索二叉樹(shù)349. 樹(shù)和森林3510. 赫夫曼樹(shù)及其應(yīng)用36二、 習(xí)題37第7章 圖39一、 基礎(chǔ)知識(shí)和算法391. 圖的有關(guān)概念392. 圖的存儲(chǔ)結(jié)構(gòu)393. 圖的遍歷424. 最小生成樹(shù)445. 拓?fù)渑判?66. 關(guān)鍵路徑467. 最短路徑48二、 習(xí)題49第9章 查找51一、 基礎(chǔ)知識(shí)和算法511. 有關(guān)概念512. 順序查找513. 折半查找524. 索引順序表545. 二叉排序樹(shù)546. 平衡二叉樹(shù)577. B-樹(shù)和B+樹(shù)598. 鍵樹(shù)599. 哈希表59二、 習(xí)題61第10章 內(nèi)部排序63一、 基礎(chǔ)知識(shí)和算法631. 排序的有關(guān)概念632. 直接插入排序633. 折半插入排序644. 希爾排序（縮小增量排序）645. 起泡排序656. 快速排序667. 簡(jiǎn)單選擇排序678. 堆排序689. 歸并排序7010. 基數(shù)排序7211. 各種排序方法比較73- II - 9. 哈希表第0章 復(fù)習(xí)提示一、 教材內(nèi)容l 使用教材數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 嚴(yán)蔚敏，清華大學(xué)出版社。l 章節(jié) 去掉 第5、8、11、12章 去掉 *部分 去掉1.3，2.4，4.4二、 復(fù)習(xí)提示1. 經(jīng)典算法單鏈表：遍歷、插入、刪除循環(huán)隊(duì)列：隊(duì)列空、隊(duì)列滿的條件二叉樹(shù)：遞歸遍歷及應(yīng)用有序表的二分法查找快速排序簡(jiǎn)單選擇排序2. 緒論掌握幾個(gè)重要概念數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、算法時(shí)間復(fù)雜度的簡(jiǎn)單計(jì)算（C 記號(hào)C，表示要求掌握計(jì)算方法，會(huì)計(jì)算。本節(jié)下同。）掌握幾種說(shuō)法數(shù)據(jù)元素是，數(shù)據(jù)項(xiàng)是數(shù)據(jù)結(jié)構(gòu)中關(guān)系的四種基本結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義算法的五個(gè)特征3. 線性表線性表的概念和四個(gè)特征順序表和單鏈表的類型定義在順序表中查找、插入、刪除，靈活運(yùn)用在單鏈表中查找、插入、刪除，靈活運(yùn)用循環(huán)鏈表及雙向鏈表的定義、插入、刪除算法：?jiǎn)捂湵淼乃惴ǎ`活運(yùn)用、會(huì)編程（P 記號(hào)P，要求達(dá)到編寫算法和程序的能力。本節(jié)下同。）4. 棧和隊(duì)列棧和隊(duì)列的概念、特點(diǎn)入棧、出棧操作，靈活掌握了解棧的實(shí)現(xiàn)：鏈棧和順序棧（A 記號(hào)A，要求掌握算法思想，會(huì)演算。本節(jié)下同。算法，P）了解隊(duì)列的實(shí)現(xiàn)，鏈隊(duì)列和循環(huán)隊(duì)列，注意鏈隊(duì)列中的出隊(duì)列操作算法：注意循環(huán)隊(duì)列空和滿的條件（A，P）會(huì)運(yùn)用棧和隊(duì)列5. 串掌握相關(guān)概念會(huì)運(yùn)用串的基本操作（C），特別是Concat()，Substring()，Index()和Replace()知道串的三種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)6. 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)的有關(guān)概念二叉樹(shù)的性質(zhì)熟練掌握遍歷二叉樹(shù)的遞歸算法，并靈活運(yùn)用知道線索二叉樹(shù)，會(huì)對(duì)二叉樹(shù)進(jìn)行線索化樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)化，會(huì)遍歷樹(shù)和森林赫夫曼樹(shù)及其應(yīng)用算法： 遞歸遍歷二叉樹(shù)及其應(yīng)用（P） 構(gòu)造赫夫曼樹(shù)和赫夫曼編碼（A） 樹(shù)和二叉樹(shù)的轉(zhuǎn)換（A） 森林和二叉樹(shù)的轉(zhuǎn)換（A） 遍歷樹(shù)和森林（A）7. 圖圖的有關(guān)概念熟練掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)圖的遍歷：深度優(yōu)先、廣度優(yōu)先（A）最小生成樹(shù)算法（兩個(gè)）及其特點(diǎn)（A）拓?fù)渑判颍ˋ）關(guān)鍵路徑算法（A）最短路徑算法（兩個(gè)）（A，O 記號(hào)O，要求掌握算法的時(shí)間復(fù)雜度。本節(jié)下同。：時(shí)間復(fù)雜度）8. 查找表查找的有關(guān)概念，ASL等順序查找（A，P）熟練掌握有序表的折半查找算法（A，P，C）了解索引順序表熟練掌握二叉排序樹(shù)的概念，建立（A），查找（A，P），刪除（A），計(jì)算ASL（C）平衡二叉排序樹(shù)的概念，建立（A），判斷失去平衡的類型，平衡化（A），計(jì)算ASL（C）了解B_樹(shù)，B+樹(shù)的概念和特點(diǎn)知道鍵樹(shù)（數(shù)字查找樹(shù)）哈希表的概念、特點(diǎn)、構(gòu)造哈希表（A），計(jì)算ASL和裝填因子（C）了解各種查找表的性能（O）9. 內(nèi)部排序直接插入排序（A）折半插入排序（A，P）希爾排序（A）起泡排序（A）快速排序（A，P，O）簡(jiǎn)單選擇排序（P，A，O）堆的概念，調(diào)整成堆（A），堆排序（A，O）歸并排序（A，O）鏈?zhǔn)交鶖?shù)排序（A，O）各種排序算法的對(duì)比結(jié)論（O）- 62 -第1章 緒論一、 基礎(chǔ)知識(shí)概念和術(shù)語(yǔ)(黑體字部分)。另外，注意：1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。P42、數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。P53、數(shù)據(jù)結(jié)構(gòu)及其形式定義。P5四種基本結(jié)構(gòu)：集合線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖（網(wǎng)）狀結(jié)構(gòu)4、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)（抽象的，與實(shí)現(xiàn)無(wú)關(guān)）物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)） 順序映像（順序存儲(chǔ)結(jié)構(gòu)）位置“相鄰” 非順序映像（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）指針表示關(guān)系P65、數(shù)據(jù)類型 P7 抽象數(shù)據(jù)類型（ADT）P7 ADT=（數(shù)據(jù)對(duì)象，數(shù)據(jù)關(guān)系，基本操作） ADT細(xì)分為原子類型，固定聚合，可變聚合類型。P86、算法的概念 P137、算法的五個(gè)特征 有窮性 確定性 可行性 輸入（0個(gè)或多個(gè)） 輸出（1個(gè)或多個(gè)）8、算法設(shè)計(jì)的要求：正確性可讀性健壯性效率與低存儲(chǔ)量其中正確性的四個(gè)層次（通常要求達(dá)到C層）。9、算法的時(shí)間復(fù)雜度 P15 常見(jiàn)有： O(1)，O(n)，O(n2)，O(log2n) 分析算法的時(shí)間復(fù)雜度時(shí)，log2n常簡(jiǎn)單記作log n。，O(n log2n)，O(2n) 語(yǔ)句頻度，用歸納法計(jì)算。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; 說(shuō)明：a) 考試中要求寫算法時(shí)，可用類C，也可用C程序。b) 盡量書寫算法說(shuō)明，言簡(jiǎn)意賅。c) 技巧：用“邊界值驗(yàn)證法”檢查下標(biāo)越界錯(cuò)誤。 如上第一個(gè)： 第二個(gè)循環(huán)條件若寫作j<n-i，則當(dāng)i=0時(shí) aj+1會(huì)越界。d) 時(shí)間復(fù)雜度為O(n2)，第3個(gè)在最好情況下（待排記錄有序），時(shí)間復(fù)雜度為O(n)。三、 習(xí)題1.1 編寫冒泡排序算法，使結(jié)果從大到小排列。1.2 計(jì)算下面語(yǔ)句段中指定語(yǔ)句的頻度： 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ǔ)知識(shí)和算法1. 線性表及其特點(diǎn)線性表是n個(gè)數(shù)據(jù)元素的有限序列。線性結(jié)構(gòu)的特點(diǎn)： “第一個(gè)” “最后一個(gè)” 前驅(qū) 后繼。 這里太簡(jiǎn)煉了，只是為了便于記憶。2. 順序表線性表的順序存儲(chǔ)結(jié)構(gòu)(1) 特點(diǎn)a) 邏輯上相鄰的元素在物理位置上相鄰。b) 隨機(jī)訪問(wèn)。(2) 類型定義簡(jiǎn)而言之，“數(shù)組+長(zhǎng)度” 不準(zhǔn)確的說(shuō)法，只為便于理解和記憶，不要在正式場(chǎng)合引用。凡此情形，都加引號(hào)以示提醒。const int MAXSIZE = 線性表最大長(zhǎng)度;typedef structDataType elemMAXSIZE;int length; SqList;注：a) SqList為類型名，可換用其他寫法。 b) DataType是數(shù)據(jù)元素的類型，根據(jù)需要確定。 c) MAXSIZE根據(jù)需要確定。如const int MAXSIZE=64; d) 課本上的SqList類型可在需要時(shí)增加存儲(chǔ)空間，在上面這種定義下不可以。(這樣做避免了動(dòng)態(tài)內(nèi)存分配，明顯減少了算法的復(fù)雜程度，容易理解。而且，原來(lái)Pascal版本的數(shù)據(jù)結(jié)構(gòu)（嚴(yán)蔚敏）就是這樣做的。) e) 課本上的SqList類型定義中l(wèi)istsize表示已經(jīng)分配的空間大?。ㄈ菁{數(shù)據(jù)元素的個(gè)數(shù)）。當(dāng)插入元素而遇到L.length=L.listsize時(shí)，用realloc (L.elem, L.listsize+增量) 重新分配內(nèi)存，而realloc()函數(shù)在必要的時(shí)候自動(dòng)復(fù)制原來(lái)的元素到新分配的空間中。(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°. 順序訪問(wèn)所有元素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+中對(duì)應(yīng)于下標(biāo)i-1。3°. 步驟 第i至最后所有元素后移一個(gè)元素 在第i個(gè)位置插入元素x 表長(zhǎng)增14°. 算法bool 這里返回true表示正確插入，返回false表示插入失敗。以下常用來(lái)區(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; / 表長(zhǎng)增1 L.length+; return true; / 插入成功(6) 刪除算法 ListDelete(&L,i,&x)1°. 前提：表非空2°. 合理的刪除范圍：1iL.length3°. 步驟取出第i個(gè)元素第i個(gè)元素之后的元素向前移動(dòng)一個(gè)位置表長(zhǎng)減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 順序表插入和刪除算法的分析插入刪除基本操作平均移動(dòng)次數(shù)移動(dòng)元素移動(dòng)元素時(shí)間復(fù)雜度O(n)O(n)尾端操作插入第n+1個(gè)元素，不移動(dòng)刪除第n個(gè)元素，不移動(dòng)插入、刪除需移動(dòng)大量元素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)酱鎯?chǔ)結(jié)構(gòu)之一(1) 概念線性鏈表，單鏈表，結(jié)點(diǎn)；數(shù)據(jù)域，指針域；頭指針，頭結(jié)點(diǎn)。(2) 特點(diǎn)用指針表示數(shù)據(jù)之間的邏輯關(guān)系（邏輯相鄰的元素物理位置不一定相鄰）。(3) 類型定義簡(jiǎn)而言之，“數(shù)據(jù) + 指針” 不準(zhǔn)確的說(shuō)法，只為便于理解和記憶，不要在正式場(chǎng)合引用。datanexttypedef struct LNode DataType data; struct LNode *next; LNode, *LinkList;(4) 基本形態(tài)帶頭結(jié)點(diǎn)的單鏈表的基本形態(tài)有：1°. 單鏈表空/an/CBA(b)(a)Ea1LL.條件： L->next = 02°. 單鏈表不空條件：L->next != 0(5) 基本算法 （遍歷）1°. 順序訪問(wèn)所有元素借助指針，“順藤摸瓜”(沿著鏈表訪問(wèn)結(jié)點(diǎn))。p = L->next; / 注意起始位置的考慮while ( p!=NULL ) / 判表尾，另外 (p!=0)或(p)均可 visit( p->data ); / 訪問(wèn):可以換成各種操作 p = p->next; / 指針沿著鏈表向后移動(dòng)例：打印單鏈表中的數(shù)據(jù)。void PrintLinkList ( LinkList L ) p = L->next; while ( p!=NULL ) print ( p->data ); / 訪問(wèn)：打印數(shù)據(jù)域 p = p->next; 2°. 查找元素x/ 在單鏈表L中查找元素x/ 若找到，返回指向該結(jié)點(diǎn)的指針；否則返回空指針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+; / 計(jì)數(shù)器隨指針改變 return 0; / 未找到前一個(gè)算法的另一種寫法：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個(gè)元素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個(gè)元素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個(gè)元素 若找到，在其后插入新結(jié)點(diǎn)bool 這里返回true表示正確插入，返回false表示插入失敗。 ListInsert ( LinkList &L, int i, DataType x ) / 查找第i-1個(gè)元素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個(gè)而不是第i個(gè)元素（否則，不容易找到前驅(qū)以便插入）。 b) 能夠插入的條件： p && j=i-1 。即使第i個(gè)元素不存在，只要存在第i-1個(gè)元素，仍然可以插入第i個(gè)元素。 c) 新建結(jié)點(diǎn)時(shí)需要?jiǎng)討B(tài)分配內(nèi)存。 s = (LinkList) malloc(sizeof(LNode); 若檢查是否分配成功，可用 if ( s=NULL ) exit(1); / 分配失敗則終止程序 d) 完成插入的步驟：。技巧：先修改新結(jié)點(diǎn)的指針域。(7) 刪除算法 ListDelete(&L,i,&x)思路： 先查找第i-1個(gè)元素 若找到且其后存在第i個(gè)元素，則用x返回?cái)?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個(gè)元素p p = L; j = 0; while ( p && j<i-1 ) p = p->next; j+; /若存在第i個(gè)元素，則用x返回?cái)?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個(gè)而非第i個(gè)元素。為什么？ b) 能夠進(jìn)行刪除的條件： p && j=i-1 && p->next 。條件中的p->next就是要保證第i個(gè)元素存在，否則無(wú)法刪除。若寫成p->next && j=i-1也不妥，因?yàn)榇藭r(shí)(循環(huán)結(jié)束時(shí))可能有p=NULL，所以必須先確定p不空。技巧：將條件中的“大前提”放在前面。該條件也不可以寫成p->next && p && j=i-1，因?yàn)橄扔衟!=0才有p->next，上式顛倒了這一關(guān)系。 c) 釋放結(jié)點(diǎn)的方法。 free(s); d) 完成刪除的步驟：。(8) 建立鏈表的兩種方法思路： 建立空表（頭結(jié)點(diǎn)）； 依次插入數(shù)據(jù)結(jié)點(diǎn)（每次插入表尾得(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) 特點(diǎn)最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)。anCBA(b)(a)Ea1L.L(2) 類型定義同單鏈表。(3) 基本形態(tài)空表：L->next = L。非空表。(4) 與單鏈表的聯(lián)系判斷表尾的方法不同：?jiǎn)捂湵碛胮=NULL；循環(huán)鏈表用p=L。其余操作相同。5. 雙向循環(huán)鏈表(1) 特點(diǎn)一個(gè)結(jié)點(diǎn)包含指向后繼(next)和指向前驅(qū)(prior)兩個(gè)指針，兩個(gè)方向又分別構(gòu)成循環(huán)鏈表。datapriornext(2) 類型定義typedef struct DuLNode DataType data; struct DuLNode *prior, *next; / 兩個(gè)指針 DuLNode, *DuLinkList;(3) 基本形態(tài)空表：用后向指針判斷L->next = L，或者用前向指針判斷L->prior = L。非空表。a1a2anLL. .(4) 與單鏈表和循環(huán)鏈表的聯(lián)系最大不同：前驅(qū)容易求得，可以向前遍歷。判斷表尾的方法與循環(huán)鏈表相同：p=L。插入和刪除時(shí)需要修改兩個(gè)方向的指針。(5) 插入和刪除需要修改兩個(gè)方向的指針。例如：(見(jiàn)下表)表 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)系隨機(jī)訪問(wèn)，取元素O(1)順序訪問(wèn)，取元素O(n)插入、刪除需要移動(dòng)元素O(n)插入、刪除不用移動(dòng)元素O(n)(用于查找位置)總結(jié)：需要反復(fù)插入、刪除，宜采用鏈表；反復(fù)提取，很少插入、刪除，宜采用順序表。二、 習(xí)題2.1 將順序表中的元素反轉(zhuǎn)順序。2.2 在非遞減有序的順序表中插入元素x，并保持有序。2.3 刪除順序表中所有等于x的元素。2.4 編寫算法實(shí)現(xiàn)順序表元素唯一化(即使順序表中重復(fù)的元素只保留一個(gè))，給出算法的時(shí)間復(fù)雜度。2.5 非遞減有序的順序表元素唯一化(參見(jiàn)習(xí)題2.4)，要求算法的時(shí)間復(fù)雜度為O(n)。2.6 將單鏈表就地逆置，即不另外開(kāi)辟結(jié)點(diǎn)空間，而將鏈表元素翻轉(zhuǎn)順序。2.7 采用插入法將單鏈表中的元素排序。2.8 采用選擇法將單鏈表中的元素排序。2.9 將兩個(gè)非遞減有序的單鏈表歸并成一個(gè)，仍并保持非遞減有序。第3章 棧和隊(duì)列一、 基礎(chǔ)知識(shí)和算法1. 棧棧，棧頂，棧底，空棧，后進(jìn)先出(LIFO)，入棧(Push)，出棧(Pop)。順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)；鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2. 鏈棧(1) 存儲(chǔ)結(jié)構(gòu)a1/anS.an-1用不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(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é)點(diǎn) 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) 存儲(chǔ)結(jié)構(gòu)類似于順序表，插入和刪除操作固定于表尾。(2) 類型定義簡(jiǎn)單說(shuō)，“數(shù)組 + 長(zhǎng)度” 不準(zhǔn)確的說(shuō)法，只為便于理解和記憶，不要在正式場(chǎng)合引用。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. 隊(duì)列隊(duì)列，隊(duì)頭，隊(duì)尾，空隊(duì)列，先進(jìn)先出(FIFO)。鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。循環(huán)隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)之一。5. 鏈隊(duì)列(1) 存儲(chǔ)結(jié)構(gòu)/·-a1·-a2·-an/.Q.frontQ.rearQ.frontQ.rear簡(jiǎn)而言之，“單鏈表 + 尾指針” 不準(zhǔn)確的說(shuō)法，只為便于理解和記憶，不要在正式場(chǎng)合引用。(2) 類型定義課本P61。typedef struct LinkList front; LinkList rear; LinkQueue;(3) 基本形態(tài)隊(duì)列空：Q.front=Q.rear。非空隊(duì)列。(4) 基本算法1°. 入隊(duì)列課本P62。插入隊(duì)尾，注意保持Q.rear指向隊(duì)尾。2°. 出隊(duì)列課本P62。刪除隊(duì)頭元素，特別注意：如果隊(duì)列中只有一個(gè)元素，則隊(duì)頭也同時(shí)是隊(duì)尾，刪除隊(duì)頭元素后也需要修改隊(duì)尾指針。6. 循環(huán)隊(duì)列(1) 存儲(chǔ)結(jié)構(gòu)簡(jiǎn)單說(shuō)，“數(shù)組 + 頭、尾位置” 不準(zhǔn)確的說(shuō)法，只為便于理解和記憶，不要在正式場(chǎng)合引用。(2) 類型定義const int MAXSIZE = 隊(duì)列最大容量;typedef struct DataType elemMAXSIZE; int front, rear; / 隊(duì)頭、隊(duì)尾位置 SqQueue;(3) 基本形態(tài)通常少用一個(gè)元素區(qū)分隊(duì)列空和隊(duì)列滿，也可以加一標(biāo)志。約定front指向隊(duì)頭元素的位置，rear指向隊(duì)尾的下一個(gè)位置，隊(duì)列內(nèi)容為 front, rear)。1°. 隊(duì)列空條件：Q.front = Q.rear。不能出隊(duì)列。2°. 隊(duì)列滿條件：(Q.rear+1)%MAXSIZE = Q.front （少用一個(gè)元素時(shí)）。不能入隊(duì)列。3°. 隊(duì)列不空也不滿frontreara1rearfronta3a2a4a1rearfronta3a2frontreartag:0frontreara3a4a1a2frontreartag:1a3a4a5a1a24°. 加一標(biāo)志區(qū)分隊(duì)列空和隊(duì)列滿的情況可以用滿所有空間。隊(duì)列空和隊(duì)列滿時(shí)都有Q.front=Q.rear，再用標(biāo)志區(qū)分。隊(duì)列空：Q.front=Q.rear and Q.tag=0；隊(duì)列滿：Q.front=Q.rear and Q.tag=1。(4) 基本算法1°. 入隊(duì)列前提：隊(duì)列不滿。bool EnQueue ( SqQueue &Q, DataType x ) if ( (Q.rear+1)%MAXSIZE=Q.front ) return false; / 隊(duì)列滿 / 入隊(duì)列 Q.elem Q.rear = x; Q.rear = (Q.rear+1)%MAXSIZE; return true;2°. 出隊(duì)列前提：隊(duì)列非空。bool DeQueue ( SqQueue &Q, DataType &x ) if ( Q.front=Q.rear ) return false; / 隊(duì)列空 / 出隊(duì)列 x = Q.elem Q.front; Q.front = (Q.front+1)%MAXSIZE; return true;3°. 隊(duì)列中元素個(gè)數(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ū)分隊(duì)列空和滿用標(biāo)志區(qū)分隊(duì)列空和滿時(shí)，隊(duì)列初始化、入隊(duì)列、出隊(duì)列和隊(duì)列長(zhǎng)度的算法如下：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; / 隊(duì)列非空 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; / 隊(duì)列空 return true;int QueueLength ( SqQueue Q ) if ( Q.front=Q.rear and Q.tag=1 ) return MAXSIZE; / 隊(duì)列滿 else return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; / 隊(duì)列不滿(包含隊(duì)列空的情況)7. 棧和隊(duì)列比較都是線形結(jié)構(gòu)，棧的操作LIFO（后進(jìn)先出），隊(duì)列操作FIFO（先進(jìn)先出）。8. 簡(jiǎn)化的棧和隊(duì)列結(jié)構(gòu)在算法中使用棧和隊(duì)列時(shí)可以采用簡(jiǎn)化的形式。表 3.1 簡(jiǎn)化的棧和隊(duì)列結(jié)構(gòu)簡(jiǎn)化棧簡(jiǎn)化隊(duì)列結(jié)構(gòu)“s + top”結(jié)構(gòu)“q + front + rear”初始化top = 0;初始化front=rear=0;入棧stop+ = x;入隊(duì)列qrear = x;rear = (rear+1)%MAXSIZE;出棧x = s-top;出隊(duì)列x = qfront;front = (front+1)%MAXSIZE;棧頂stop-1隊(duì)列頭qfront?？誸op = 0隊(duì)列空f(shuō)ront = rear說(shuō)明：只要棧(隊(duì)列)的容量足夠大，算法中可以省去檢查棧(隊(duì)列)滿的情況。9. 棧和隊(duì)列的應(yīng)用1°. 表達(dá)式求值參見(jiàn)課本P53。2°. 括號(hào)匹配例：檢查表達(dá)式中的括號(hào)是否正確匹配。如 ( ) 正確，( ) 則錯(cuò)誤。分析：每個(gè)左括號(hào)都“期待”對(duì)應(yīng)的右括號(hào)，匹配成功則可以消去。思路：遇到左括號(hào)則入棧，遇到右括號(hào)則與棧頂括號(hào)相比較，如果匹配則消去，否則匹配失敗。當(dāng)然，如果棧中沒(méi)有括號(hào)可以匹配，或者最后棧中還有未匹配的左括號(hào)，也都是匹配錯(cuò)誤。/ 檢查輸入的表達(dá)式中括號(hào)是否匹配bool MatchBrackets () const int MAXSIZE = 1024; / 棧的最大容量 char s MAXSIZE; / 簡(jiǎn)化的棧結(jié)構(gòu) int top; / 棧頂 / 棧初始化 top = 0; / 檢查括號(hào)是否匹配 ch = getchar(); while ( ch!=EOF ) switch ( ch ) case (, , : s top+ = ch; / 所有左括號(hào)入棧 break; case ): if ( top=0 or s -top!=( ) return false; / ?？栈蛴依ㄌ?hào)與棧頂左括號(hào)失配 case : if ( top=0 or s -top!= ) return false; case : if ( top=0 or s -top!= ) return false; ch = getchar(); / 取下一個(gè)字符 if ( top=0 ) return true; / 正好匹配 else return false; / 棧中尚有未匹配的左括號(hào)3°. 遞歸程序的非遞歸化將遞歸程序轉(zhuǎn)化為非遞歸程序時(shí)常使用棧來(lái)實(shí)現(xiàn)。4°. 作業(yè)排隊(duì)如操作系統(tǒng)中的作業(yè)調(diào)度中的作業(yè)排隊(duì)，打印機(jī)的打印作業(yè)也排成隊(duì)列。5°. 按層次遍歷二叉樹(shù)void LevelOrder ( BinTree bt, VisitFunc visit ) const int MAXSIZE = 1024; / 隊(duì)列容量(足夠大即可) BinTree q MAXSIZE; / 簡(jiǎn)化的隊(duì)列結(jié)構(gòu) int front, rear; / 隊(duì)頭、隊(duì)尾 if ( ! bt ) return ; / 初始化隊(duì)列，根結(jié)點(diǎn)入隊(duì)列 front = rear = 0; q rear = bt; rear = (rear+1)%MAXSIZE; / 隊(duì)列不空，則取出隊(duì)頭訪問(wèn)并將其左右孩子入隊(duì)列 while ( front!=rear ) p = q front; front = (front+1)%MAXSIZE; if ( p ) visit ( p->data ); / 訪問(wèn)結(jié)點(diǎn) 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)隊(duì)列Q少用一個(gè)元素區(qū)分隊(duì)列空和隊(duì)列滿，MAXSIZE=5，Q.front=Q.rear=0，畫出執(zhí)行下列操作時(shí)隊(duì)列空和隊(duì)列滿的狀態(tài)。入隊(duì)列a,b,c，出隊(duì)列a,b,c，入隊(duì)列d,e,f,g。3.3 編寫算法利用棧將隊(duì)列中的元素翻轉(zhuǎn)順序。第4章 串一、 基礎(chǔ)知識(shí)和算法1. 概念串，空串，空格串，串的長(zhǎng)度；子串，子串在主串中的位置，主串；串相等。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)判斷串相等，求串長(zhǎng)度。如Length(“”)=0。Concat (s, t)串連接。如Concat(“ab”,”cd”)=”abcd”。Substr (s, pos, len)取子串，pos為開(kāi)始位置，len為子串長(zhǎng)度。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. 串的存儲(chǔ)結(jié)構(gòu)表 4.2 串的存儲(chǔ)結(jié)構(gòu)定長(zhǎng)順序串最大長(zhǎng)度固定，超過(guò)最大長(zhǎng)度則作截?cái)嗵幚矶逊峙浯鎯?chǔ)表示串的長(zhǎng)度幾乎沒(méi)有限制塊鏈存儲(chǔ)表示塊內(nèi)存儲(chǔ)空間連續(xù)，塊間不連續(xù)二、 習(xí)題4.1 長(zhǎng)度為n的串的子串最多有多少個(gè)？第5章 數(shù)組和廣義表(略)第6章 樹(shù)和二叉樹(shù)一、 基礎(chǔ)知識(shí)和算法1. 樹(shù)及有關(guān)概念樹(shù)，根，子樹(shù)；結(jié)點(diǎn)，結(jié)點(diǎn)的度，葉子（終端結(jié)點(diǎn)），分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)），內(nèi)部結(jié)點(diǎn)，樹(shù)的度；孩子，雙親，兄弟，祖先，子孫，堂兄弟；層次（根所在層為第1層），深度，高度；有序樹(shù)，無(wú)序樹(shù)，二叉樹(shù)是有序樹(shù)；森林。2. 二叉樹(shù)二叉樹(shù)（二叉樹(shù)與度為2的樹(shù)不同，二叉樹(shù)的度可能是0，1，2）；左孩子，右孩子。二叉樹(shù)的五種基本形態(tài)。3. 二叉樹(shù)的性質(zhì)1°. 二叉樹(shù)的第i層 本書中約定根結(jié)點(diǎn)在第1層，也有約定根在第0層的，則計(jì)算公式會(huì)有所不同。上至多有2i-1個(gè)結(jié)點(diǎn)。2°. 深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。 滿二叉樹(shù)：深度為k，有2k-1個(gè)結(jié)點(diǎn)。 完全二叉樹(shù)：給滿二叉樹(shù)的結(jié)點(diǎn)編號(hào)，從上至下，從左至右，n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中結(jié)點(diǎn)在對(duì)應(yīng)滿二叉樹(shù)中的編號(hào)正好是從1到n。3°. 葉子結(jié)點(diǎn)n0，度為2的結(jié)點(diǎn)為n2，則n0 = n2+1?？紤]結(jié)點(diǎn)個(gè)數(shù)：n = n0 + n1 + n2考慮分支個(gè)數(shù)：n-1 = 2n2 + n1可得n0 = n2+1例：1) 二叉樹(shù)有n個(gè)葉子，沒(méi)有度為1的結(jié)點(diǎn)，共有 個(gè)結(jié)點(diǎn)。 2) 完全二叉樹(shù)的第3層有2個(gè)葉子，則共有 個(gè)結(jié)點(diǎn)。分析：1) 度為2的結(jié)點(diǎn)有n-1個(gè)，所以共2n-1個(gè)結(jié)點(diǎn)。 2) 注意考慮到符合條件的二叉樹(shù)的深度可能是3或4，所以有5、10或11個(gè)結(jié)點(diǎn)。4°. n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為。5°. n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，結(jié)點(diǎn)按層次編號(hào)有： i的雙親是，如果i = 1時(shí)為根（無(wú)雙親）； i的左孩子是2i，如果2i>n，則無(wú)左孩子； i的右孩子是2i + 1，如果2i + 1>n則無(wú)右孩子。4. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1°. 順序