【正文】 的性質(zhì)。◆ 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹。具體操作步驟：學(xué)習(xí)重點：（本章內(nèi)容是本課程的重點）◆ 二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K叉樹。(4) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹為止。(2) 在F 中選取兩棵根結(jié)點權(quán)值最小的樹 做為左右子樹構(gòu)造一棵新的二叉樹，且讓新二叉樹根結(jié)點的權(quán)值等于其左右子樹的根結(jié)點權(quán)值之和。樹的帶權(quán)路徑長度：（樹中所有葉子結(jié)點的帶權(quán)路徑長度之和）構(gòu)造Huffman樹的基本思想：權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑?！?二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。① 先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點；先根遍歷第一棵樹的根結(jié)點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。② 后根遍歷：依次后根遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。 法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹 討論2：二叉樹如何還原為森林？ 要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值軜浜蜕值拇鎯Ψ绞剑簶溆腥N常用存儲方式：①雙親表示法 ②孩子表示法 ③孩子—兄弟表示法問：樹→二叉樹的“連線—抹線—旋轉(zhuǎn)” 如何由計算機自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、R若限定先左后右，則有三種實現(xiàn)方案： DLR LDR LRD先序遍歷 中序遍歷 后序遍歷 ◆ 樹的存儲結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換。優(yōu)點：①不浪費空間；②插入、刪除方便 ◆ 二叉樹的遍歷。缺點：①浪費空間；②插入、刪除不便 二、鏈?zhǔn)酱鎯Y(jié)構(gòu)用二叉鏈表即可方便表示。若是完全/滿二叉樹則可以做到唯一復(fù)原。 性質(zhì)5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）。性質(zhì)2: 深度為k的二叉樹至多有2k1個結(jié)點（k0）。術(shù)語：P88◆ 二叉樹的性質(zhì)，存儲結(jié)構(gòu)。每個集合本身又是棵樹，被稱作這個根的子樹 ?！?樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語?？沾?Null String)是指長度為零的串；而空白串(Blank String),是指包含一個或多個空白字符‘ ’(空格鍵)的字符串.2. “空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串。 //T子串指針j正常到尾，說明匹配成功， else return 0。 j=1。 j=T[0] ) //如果i,j二指針在正常長度范圍， { if (S[i] = = T[j] ) {++i, ++j。 while ( i=S[0] amp。若不存在，則函數(shù)值為0. // 其中，T非空，1≤pos≤StrLength(S) i=pos。否則，匹配失敗，返回值 0。 直到主串S的一個連續(xù)子串字符序列與模式T相等。串有三種機內(nèi)表示方法：模式匹配算法 ◆ 串的存儲結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點大小”的問題。 求串長：int strlen(char *s)。串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。第四章 串內(nèi)容提要不同點：① 運算規(guī)則不同：線性表為隨機存?。欢鴹Ｊ侵辉试S在一端進行插入和刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。那么，從循環(huán)隊列中刪除一個元素時，其操作是先 移動隊首位置 ，后 取出元素。解決假溢出的途徑———采用循環(huán)隊列。 ？它有什么獨特用途？① 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊列）；② 操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU執(zhí)行多個作業(yè)）；③ 簡化程序設(shè)計。 }// DeQueue◆ 鏈隊列空的條件是首尾指針相等，而循環(huán)隊列滿的條件的判定，則有隊尾加1等于隊頭和設(shè)標(biāo)記兩種方法。 e = [ ] 。e) {//若隊列不空，刪除循環(huán)隊列q的隊頭元素， //由 e 返回其值，并返回OK if ( = = ) return ERROR。3） 出隊操作Status DeQueue ( SqQueue amp。 //新元素e入隊 return OK。 //隊滿則上溢，無法再入隊 = ( q . rear + 1 ) % QUEUE_MAXSIZE。2） 入隊操作Status EnQueue(SqQueue amp。 //置空隊列 return OK。 //分配空間if (!) exit(OVERFLOW)。 //分配空間順序隊示意圖：循環(huán)隊列：隊空條件 : front = rear (初始化時：front = rear )隊滿條件： front = (rear+1) % N (N=maxsize)隊列長度（即數(shù)據(jù)元素個數(shù)）：L=（N＋rear－front）% N 1） 初始化一個空隊列Status InitQueue ( SqQueue amp。 //隊首指針 int rear。2. 順序隊順序隊類型定義：define QUEUEMAXSIZE 100 //最大隊列長度 typedef struct { QElemType *base。 rear=S。鏈隊示意圖：① 空鏈隊的特征：front=rear② 鏈隊會滿嗎？一般不會，因為刪除時有free動作。 //隊首指針 QueuePtr rear 。 //指向下一結(jié)點的指針 }Qnode , * QueuePtr 。鏈隊列結(jié)點類型定義： typedef Struct QNode{ QElemType data。因此在兩種存儲結(jié)構(gòu)中，都需要隊頭和隊尾兩個指針。 return(e)。 順序棧入棧函數(shù)PUSH（）status Push(ElemType e) { if(topM){上溢} else s[top++]=e。 從棧頂刪除最后一個元素的操作，稱為出棧。棧是只準(zhǔn)在一端進行插入和刪除操作的線性表，該端稱為棧的頂端。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。}第3章 棧和隊列內(nèi)容提要： // n是表長，是數(shù)據(jù)元素的個數(shù)，而不是V的實際下標(biāo) build( )。 printf( \n )。 i=n1。 }void display( ) //字母線性表的顯示，即讀表操作{ int i。 i=n1。a39。void build() //字母線性表的生成，即建表操作{ int i。法1：用線性表表示： （( 1,2,12) ，(1,3,9)， (3,1,3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,7)）法2：用十字鏈表表示用途：方便稀疏矩陣的加減運算方法：每個非0元素占用5個域法3：用三元組矩陣表示：稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能代碼：（a，b，c，…，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。 11. 寫出右圖所示稀疏矩陣的壓縮存儲形式。③數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。9. 判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對嗎？答：對的?！? 順序表適宜于做查找這樣的靜態(tài)操作；◆ 鏈表宜于做插入、刪除這樣的動態(tài)操作。鏈?zhǔn)酱鎯Φ膬?yōu)點是插入或刪除元素時很方便，使用靈活。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。但是，如果要在單鏈表中進行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度將是 O(n)。7. 鏈表的運算效率分析：（1）查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為 O(n)。，不再是簡單數(shù)據(jù)類型，編程時該如何表示？ 因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。 ？ 頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理，編程更方便?！?稀疏矩陣的十字鏈表存儲方法?！?數(shù)組（主要是二維）在以行序/列序為主的存儲中的地址計算方法。因此，若在某結(jié)點前插入一個元素，或刪除某元素，必須知道該元素的前驅(qū)結(jié)點的指針?！?順序存儲結(jié)構(gòu)用一維數(shù)組表示，