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