【正文】 data。2176。. n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，結(jié)點(diǎn)按層次編號(hào)有： i的雙親是，如果i = 1時(shí)為根（無(wú)雙親）； i的左孩子是2i，如果2in，則無(wú)左孩子； i的右孩子是2i + 1，如果2i + 1n則無(wú)右孩子。 2) 注意考慮到符合條件的二叉樹(shù)的深度可能是3或4，所以有10或11個(gè)結(jié)點(diǎn)。. 葉子結(jié)點(diǎn)n0，度為2的結(jié)點(diǎn)為n2，則n0 = n2+1。. 深度為k的二叉樹(shù)至多有2k1個(gè)結(jié)點(diǎn)。3. 二叉樹(shù)的性質(zhì)1176。注：~。如Index(“abc”,”ab”)=1，Index(“a bc”,”bc”)=3。Concat (s, t)串連接。第4章 串一、 基礎(chǔ)知識(shí)和算法1. 概念串，空串，空格串，串的長(zhǎng)度；子串，子串在主串中的位置，主串；串相等。 rear = (rear+1)%MAXSIZE。 if ( p ) { visit ( pdata )。 q [rear] = bt。 // 隊(duì)列容量(足夠大即可) BinTree q [MAXSIZE]。4176。 // 取下一個(gè)字符 } if ( top==0 ) return true。 case ‘)’: if ( top==0 or s [top]!=’(’ ) return false。 // 棧頂 // 棧初始化 top = 0。當(dāng)然，如果棧中沒(méi)有括號(hào)可以匹配，或者最后棧中還有未匹配的左括號(hào)，也都是匹配錯(cuò)誤。. 括號(hào)匹配例：檢查表達(dá)式中的括號(hào)是否正確匹配。棧頂s[top1]隊(duì)列頭q[front]?？誸op == 0隊(duì)列空f(shuō)ront == rear說(shuō)明：只要棧(隊(duì)列)的容量足夠大，算法中可以省去檢查棧(隊(duì)列)滿的情況。rear = (rear+1)%MAXSIZE。表 簡(jiǎn)化的棧和隊(duì)列結(jié)構(gòu)簡(jiǎn)化棧簡(jiǎn)化隊(duì)列結(jié)構(gòu)“s[] + top”結(jié)構(gòu)“q[] + front + rear”初始化top = 0。}int QueueLength ( SqQueue Q ){ if ( == and ==1 ) return MAXSIZE。 x = [ ]。 // 隊(duì)列非空 return true。Q, DataType x ) { if ( == and ==1 ) return false。. 用標(biāo)志區(qū)分隊(duì)列空和滿用標(biāo)志區(qū)分隊(duì)列空和滿時(shí)，隊(duì)列初始化、入隊(duì)列、出隊(duì)列和隊(duì)列長(zhǎng)度的算法如下：void InitQueue ( SqQueue amp。. 隊(duì)列中元素個(gè)數(shù)結(jié)論：(+MAXSIZE)%MAXSIZE。 // 隊(duì)列空 // 出隊(duì)列 x = []。. 出隊(duì)列前提：隊(duì)列非空。 // 隊(duì)列滿 // 入隊(duì)列 [] = x。(4) 基本算法1176。. 隊(duì)列不空也不滿frontreara1rearfronta3a2a4a1rearfronta3a2frontreartag:0frontreara3a4a1a2frontreartag:1a3a4a5a1a24176。2176。約定front指向隊(duì)頭元素的位置，rear指向隊(duì)尾的下一個(gè)位置，隊(duì)列內(nèi)容為 [front, rear)。typedef struct { DataType elem[MAXSIZE]。刪除隊(duì)頭元素，特別注意：如果隊(duì)列中只有一個(gè)元素，則隊(duì)頭也同時(shí)是隊(duì)尾，刪除隊(duì)頭元素后也需要修改隊(duì)尾指針。. 入隊(duì)列課本P62。} LinkQueue。5. 鏈隊(duì)列(1) 存儲(chǔ)結(jié)構(gòu)/\. 棧頂元素前提：棧非空[top1] 即是。 // 可用x=[top]。x)前提：棧非空bool Pop ( SqStack amp。 // 代替這兩行 return true。 s, DataType x ){ if ( == MAXSIZE ) return false。. 棧滿條件 == MAXSIZE3176。} SqStack。(2) 類型定義簡(jiǎn)單說(shuō)，“數(shù)組 + 長(zhǎng)度” 不準(zhǔn)確的說(shuō)法，只為便于理解和記憶，不要在正式場(chǎng)合引用。x ){ if ( s==NULL ) return false。}3176。 s = snext。bool Pop ( LinkList amp。}2176。 // 失敗 pdata = x。. 入棧 Push (amp。(3) 基本形態(tài)a1/\anS...an1S/\1176。第3章 棧和隊(duì)列一、 基礎(chǔ)知識(shí)和算法1. 棧棧，棧頂，棧底，空棧，后進(jìn)先出(LIFO)，入棧(Push)，出棧(Pop)。 將單鏈表就地逆置，即不另外開(kāi)辟結(jié)點(diǎn)空間，而將鏈表元素翻轉(zhuǎn)順序。 在非遞減有序的順序表中插入元素x，并保持有序。ppriornext = pnext。spriornext = s。snextprior = s。(5) 插入和刪除需要修改兩個(gè)方向的指針。非空表。datapriornext(2) 類型定義typedef struct DuLNode { DataType data。非空表。 Lnext = s。 i++ ) { scanf ( x )。L, int n){ // 建立空表 L = (LinkList) malloc(sizeof(LNode))。 pnext = s。 i++ ) { scanf ( x )。 Lnext = NULL。(8) 建立鏈表的兩種方法思路： 建立空表（頭結(jié)點(diǎn)）； 依次插入數(shù)據(jù)結(jié)點(diǎn)（每次插入表尾得(a1,a2,…,an)，每次插入表頭得(an,…,a2,a1)）。 j==i1，因?yàn)橄扔衟!=0才有pnext，上式顛倒了這一關(guān)系。該條件也不可以寫成pnext amp。若寫成pnext amp。 j==i1 amp。 } else return false。 // ① pnext = snext。amp。amp。L, int i, int amp。①sai1p(7) 刪除算法 ListDelete(amp。 s = (LinkList) malloc(sizeof(LNode))。amp。 // ② return true。 j==i1 ) { s = (LinkList) malloc(sizeof(LNode))。pxsai1 ji1 ) { p = pnext。L, int i, DataType x ){ // 查找第i1個(gè)元素p p = L。(6) 插入算法 ListInsert(amp。}if ( p amp。while ( p amp。 else return 0。 j++。 j = 1。 pdata!=x ) p = pnext。else return 0。 pdata!=x ) p = pnext。 // 計(jì)數(shù)器隨指針改變 } return 0。 j = 1。 while ( p!=NULL ) { if ( pdata == x ) return p。 while ( p!=NULL ) { print ( pdata )。 // 注意起始位置的考慮while ( p!=NULL ) { // 判表尾，另外 (p!=0)或(p)均可 visit( pdata )。. 單鏈表空/\an/\CBA(b)(a)Ea1LL...條件： Lnext == 02176。datanexttypedef struct LNode { DataType data。3. 單鏈表——線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)之一(1) 概念線性鏈表，單鏈表，結(jié)點(diǎn)；數(shù)據(jù)域，指針域；頭指針，頭結(jié)點(diǎn)。. ListLength (L) return 。L) = 0。 // 刪除成功}(7) 算法分析表 順序表插入和刪除算法的分析插入刪除基本操作平均移動(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)。 j。 L, int i, DataTypeamp。. 前提：表非空2176。 return true。 j=i1。以下常用來(lái)區(qū)分操作是否正確執(zhí)行。. 合理的插入范圍：1≤i≤+1注：位序i在C/C++中對(duì)應(yīng)于下標(biāo)i1。else 未找到。. 查找元素xfor ( i=0。. 順序訪問(wèn)所有元素for ( i=0。(3) 基本形態(tài)1176。(這樣做避免了動(dòng)態(tài)內(nèi)存分配，明顯減少了算法的復(fù)雜程度，容易理解。 b) DataType是數(shù)據(jù)元素的類型，根據(jù)需要確定。typedef struct{ DataType elem[MAXSIZE]。(2) 類型定義簡(jiǎn)而言之，“數(shù)組+長(zhǎng)度” 不準(zhǔn)確的說(shuō)法，只為便于理解和記憶，不要在正式場(chǎng)合引用。 線性結(jié)構(gòu)的特點(diǎn)： ①“第一個(gè)” ②“最后一個(gè)” ③前驅(qū) ④后繼。 j++ ) x++。 計(jì)算下面語(yǔ)句段中指定語(yǔ)句的頻度： 1) for ( i=1。c) 技巧：用“邊界值驗(yàn)證法”檢查下標(biāo)越界錯(cuò)誤。 change = true。 i++ ) { change = fasle。 jni。 j++ ) if ( a[j]a[j+1] ) a[j]—a[j+1]。P16另一種形式void BubbleSort ( DataType a[], int n ){ for ( i=0。P8算法的概念 P13算法的五個(gè)特征 ①有窮性 ②確定性 ③可行性 ④輸入（0個(gè)或多個(gè)） ⑤輸出（1個(gè)或多個(gè)）算法設(shè)計(jì)的要求：①正確性②可讀性③健壯性④效率與低存儲(chǔ)量 其中正確性的四個(gè)層次（通常要求達(dá)到C層）。另外，注意：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。本節(jié)下同。本節(jié)下同。譚業(yè)武老師給了我很大支持，還提出了很多建議。對(duì)所有習(xí)題都提供了參考答案。凡是這種情況，往往都用引號(hào)括起來(lái)，并加以腳注說(shuō)明。加之看到學(xué)生們埋頭記筆記時(shí)辛苦的樣子，就產(chǎn)生了寫一本小冊(cè)子的想法。我給學(xué)生輔導(dǎo)這門課程已經(jīng)有幾個(gè)年頭了，講稿換了幾次，逐漸豐富起來(lái)。這樣做的目的，僅僅是為了更簡(jiǎn)練、更直接地描述思想，方便理解、記憶和使用。 另外，每章之后都配有習(xí)題，或多或少，難度不一，并沒(méi)有局限于專升本的要求。李永干老師的幫助使得本書順利印刷。l 章節(jié) 去掉 第112章 去掉 **部分 ，二、 復(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ì)算。）4. 棧和隊(duì)列棧和隊(duì)列的概念、特點(diǎn)入棧、出棧操作，靈活掌握了解棧的實(shí)現(xiàn)：鏈棧和順序棧（A 記號(hào)A，要求掌握算法思想，會(huì)演算。：時(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）第1章 緒論一、 基礎(chǔ)知識(shí)概念和術(shù)語(yǔ)(黑體字部分)。P5 四種基本結(jié)構(gòu)：①集合②線性結(jié)構(gòu)③樹(shù)形結(jié)構(gòu)④圖（網(wǎng)）狀結(jié)構(gòu)數(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)系P6數(shù)據(jù)類型 P7 抽象數(shù)據(jù)類型（ADT）P7 ADT=（數(shù)據(jù)對(duì)象，數(shù)據(jù)關(guān)系，基本操作） ADT細(xì)分為原子類型，固定聚合，可變聚合類型。算法的空間復(fù)雜度 P17二、 算法起泡排序。 jni1。 i++ ) for ( j=0。 in1。 j++ ) if ( a[j]a