【正文】 ◆ 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹?！?哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。◆ 圖的定義，概念、術(shù)語及基本操作。注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點vi為頭的弧(即入度邊）。2. 鄰接表(鏈式)表示法① 對每個頂點vi 建立一個單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來，表中每個結(jié)點都設(shè)為3個域:② 每個單鏈表還應(yīng)當附設(shè)一個頭結(jié)點（設(shè)為2個域），存vi信息；③ 每個單鏈表的頭結(jié)點另外用順序存儲結(jié)構(gòu)存儲。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索 深度優(yōu)先搜索（遍歷）步驟：① 訪問起始點 v。◆ 圖的應(yīng)用（最小生成樹，最短路經(jīng)） 最小生成樹（MST）的性質(zhì)如下：若U集是V的一個非空子集，若(u0, v0)是一條最小權(quán)值的邊，其中u0206。Prime算法特點: 將頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。 所有頂點之間的最短路徑可以通過調(diào)用n次Dijkstra算法來完成，還有更簡單的一個算法：Floyd算法（自學）。 如果圖中任意一對頂點都是連通的, 則稱此圖是連通圖?！?圖是復雜的數(shù)據(jù)結(jié)構(gòu)，也有順序和鏈式兩種存儲結(jié)構(gòu)：數(shù)組表示法（重點是鄰接距陣）和鄰接表?！?從單源點到其他頂點，以及各個頂點間的最短路徑問題，掌握熟練手工模擬。第8章 　 查找 內(nèi)容提要：◆ 查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。 針對靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找 一、順序查找（線性查找） 技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。 i )。 二、折半查找（二分或?qū)Ψ植檎遥? 若關(guān)鍵字不在表中，怎樣得知并及時停止查找？ 典型標志是：當查找范圍的上界≤下界時停止查找。查找：塊間折半，塊內(nèi)線性查找步驟分兩步進行：① 對索引表使用折半查找法（因為索引表是有序表）；② 確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因為各子表內(nèi)部是無序表）；查找效率ASL分析：◆ 動態(tài)查找表：二叉排序樹，平衡二叉樹。② 二叉排序樹的插入與刪除思路：查找不成功，生成一個新結(jié)點s，插入到二叉排序樹中；查找成功則返回。 sdata=K。 //若t為空，則插入的結(jié)點s作為根結(jié)點K qdata: qL_child=s。 SR=PR 。如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復平衡。因元素間關(guān)系非常松散，其操作需借助其它數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)?！?查找的ASL◆ 二叉排序樹的形態(tài)取決于元素的輸入順序。？ 查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。ASL=∑ Pi. Ci，要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序：① 查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；② 中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列（即實現(xiàn)了排序運算）；③ 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點上，而且插入或刪除時只需修改指針而不需移動元素?！?插入排序（直接插入、折半插入，索引表插入、希爾插入排序）。時間效率： 因為在最壞情況下，所有元素的比較次數(shù)總和為（0＋1＋…＋n1)→O(n2)。 i =。 j 。時間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少， 所以排序效率仍為O(n2) 。但由于比較次數(shù)沒有減少，故時間效率仍為O(n2) 。5） 希爾（shell）排序基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。1) 冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。此時便為有序序列了。1） 簡單選擇排序思路異常簡單：每經(jīng)過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可。 i。 } //for } //SelectSort2） 錦標賽排序 (又稱樹形選擇排序)基本思想：與體育比賽時的淘汰賽類似。然后在這 233。 解釋：如果讓滿足以上條件的元素序列 （k1，k2，…，kn）順次排成一棵完全二叉樹，則此樹的特點是：樹中所有結(jié)點的值均大于（或小于）其左右孩子，此樹的根結(jié)點（即堆頂）必最大（或最小）。僅在第二個for循環(huán)中交換記錄時用到一個臨時變量temp?！?各種排序所基于的基本思想。2. “快速排序”是否真的比任何排序算法都快？ ——基本上是，因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的?！?對每種排序方法的學習，應(yīng)掌握其本質(zhì)（排序所基于的思想），熟練掌握手工模擬各種排序的過程。優(yōu)點：對小文件效果不明顯，但對大文件有效。堆排序算法分析：時間效率： O(nlog2n)。 個較小者之間再進行兩兩比較，…，如此重復，直到選出最小關(guān)鍵字的記錄為止。n/2249。 if( i!=j ) r[i] 171。優(yōu)點：實現(xiàn)簡單缺點：每趟只能確定一個元素，表長為n時需要n1趟前提：順序存儲結(jié)構(gòu) Void SelectSort(SqList amp?！?選擇排序（簡單選擇排序、樹形選擇排序、堆排序）。前提：順序存儲結(jié)構(gòu) 冒泡排序的算法分析：時間效率：O（n2) —因為要考慮最壞情況空間效率：O（1） —只在交換時用到一個緩沖單元穩(wěn) 定 性： 穩(wěn)定 —25和25*在排序前后的次序未改變冒泡排序的優(yōu)點：每一趟整理元素時，不僅可以完全確定一個元素的位置（擠出一個泡到表尾），還可以對前面的元素作一些整理，所以比一般的排序要快?！?交換排序（冒泡排序、快速排序）。③ 穩(wěn)定性：25和25*排序前后次序未變，穩(wěn)定。優(yōu)點：在排序過程中不移動元素，只修改指針。 //直到子表元素小于哨兵，將哨兵值送入 //當前要插入的位置（包括插入到表首）} } 2） 折半插入排序既然子表有序且為順序存儲結(jié)構(gòu)，則插入時采用折半查找定可加速。 j=i1 。 故時間復雜度為O(n2) 空間效率：僅占用1個緩沖單元——O（1）算法的穩(wěn)定性：因為25*排序后仍然在25的后面——穩(wěn)定直接插入排序算法的實現(xiàn)：void InsertSort ( SqList amp。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。 ◆ 排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。？用比較次數(shù)的平均值來評估算法的優(yōu)劣。◆ 平衡二叉樹的概念，應(yīng)熟練掌握手工繪制平衡二叉樹?！?順序表因設(shè)置了監(jiān)視哨使查找效率大大提高。平衡旋轉(zhuǎn)可以歸納為四類：學習重點：平衡因子：——該結(jié)點的左子樹的深度減去它的右子樹的深度。 //若K比葉子大，掛右邊 }return OK}③ 二叉排序樹的刪除操作如何實現(xiàn)？如何刪除一個結(jié)點？假設(shè)：*p表示被刪結(jié)點的指針； PL和PR 分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點指針；并假定*p是*f的左孩子；則可能有三種情況： *p有兩棵子樹時，如何進行刪除操作？設(shè)刪除前的中序遍歷序列為：…. PL s p PR f //顯然p的直接前驅(qū)是s ，s是*p左子樹最右下方的結(jié)點希望刪除p后，其它元素的相對位置不變。 s R_child=NULL。t) { //K為待查關(guān)鍵字，t為根結(jié)點指針 p=t。要求：對于給定值key, 若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key 的記錄。然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。} // Search_Seq//ASL＝（1＋n）/2，時間效率為 O(n)，這是查找成功的情況:順序查找的特點：優(yōu)點：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。 for( i=。（同一類型的數(shù)據(jù)元素構(gòu)成的集合）◆ 查找表的操作：查找，插入，刪除。2. 區(qū)別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。◆ 連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權(quán)值之和是唯一的。 ② 生成樹：是一個極小連通子圖，它含有圖中全部n個頂點，但只有n1條邊?！?基本概念中，連通分量，生成樹，鄰接點是重點。兩種常見的最短路徑問題：一、 單源最短路徑—用Dijkstra（迪杰斯特拉）算法二、所有頂點間的最短路徑—用Floyd（弗洛伊德）算法一、單源最短路徑 (Dijkstra算法)一頂點到其余各頂點（v0→j）目的： 設(shè)一有向圖G=（V, E），已知各邊的權(quán)值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。VU；則：(u0, v0)必在最小生成樹上?；舅枷耄骸聵涞南刃虮闅v過程。◆ 圖的遍歷。鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊(弧)。 術(shù)語：見課件