【正文】 空?！　?3)對新的森林F重復(fù)(2)，直到森林F中只剩下一棵樹為止。 ② n個葉子的哈夫曼樹要經(jīng)過n1次合并，產(chǎn)生n1個新結(jié)點(diǎn)。：數(shù)據(jù)壓縮過程稱為編碼,反之，解壓縮的過程稱為解碼?？梢岳枚鏄鋪碓O(shè)計(jì)二進(jìn)制的前綴編碼，其左分支表示字符0，右分支表示字符1，則以根結(jié)點(diǎn)到葉結(jié)點(diǎn)路徑上的分支字符組成的串作為該葉節(jié)點(diǎn)的字符編碼。譯碼過程是從樹根結(jié)點(diǎn)出發(fā)，逐個讀入電文中的二進(jìn)制碼。用尖括號表示圖的有向邊vi,vj,有向邊又稱為弧，起點(diǎn)稱為弧尾，終點(diǎn)稱為弧頭。在無向圖中，稱vi和vj相鄰接，在有向圖中稱頂點(diǎn)vi鄰接到vj，頂點(diǎn)vj鄰接于vi在無向圖中，n的取值范圍是0n(n1)/2，將具有n(n1)/2條邊的無向圖稱為無向完全圖。無向圖中，頂點(diǎn)的度定義為以該頂點(diǎn)為一個端點(diǎn)的邊的數(shù)目，有向圖的度等于出度和入度之和。若圖G中的任意兩個頂點(diǎn)都連通，稱G為連通圖。在有向圖中，圖G中任意兩頂點(diǎn)連通，稱為強(qiáng)連通圖，極大連通子圖稱為強(qiáng)連通分量。邊上帶權(quán)的圖稱為帶權(quán)圖，帶權(quán)的連通圖稱為網(wǎng)絡(luò)。圖的頂點(diǎn)編號從0開始。無向圖的鄰接矩陣是按主對角線對稱的。無向圖的鄰接矩陣表示法可以僅存儲主對角線以下的元素，時(shí)間復(fù)雜度為O(n2) 鄰接表表示法：鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。若無向圖有n個頂點(diǎn)和e條邊，則它的鄰接表共有n個頭結(jié)點(diǎn)和2e個表結(jié)點(diǎn)。圖的鄰接表表示不是唯一的,這是因?yàn)樵诿總€頂點(diǎn)的鄰接表中，各邊結(jié)點(diǎn)的鏈接次序可以是任意的，其具體鏈接次序與邊的輸入次序和生成算法有關(guān)。圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法。按訪問頂點(diǎn)的先后次序得到的頂點(diǎn)序列稱為圖的深度優(yōu)先遍歷序列，或簡稱為DFS序列。 廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷，先被訪問的頂點(diǎn)，其鄰接點(diǎn)也先被訪問，就是先進(jìn)先出。 ，一個圖的極小連通子圖恰為一個無回路的連通圖，也就是說，若圖中任意添加一條邊，就會出現(xiàn)回路，若去掉任意一條邊，都會使之成為非連通圖。 生成樹定義為：若從圖的某頂點(diǎn)出發(fā)，可以系統(tǒng)的訪問到圖的所有頂點(diǎn)，則遍歷時(shí)經(jīng)過的邊和圖的所有頂點(diǎn)所構(gòu)成的子圖，稱為該圖的生成樹。 構(gòu)造最小生成樹的算法：普里姆Prim算法的時(shí)間復(fù)雜度為O（n2）與網(wǎng)中邊數(shù)無關(guān)適于稠密圖。：Dijkstra迪杰斯特拉算法，提出了按路徑長度遞增的順序產(chǎn)生諸頂點(diǎn)的最短路徑算法。這樣的有向無環(huán)圖DAG稱為頂點(diǎn)活動網(wǎng)，簡稱為AOV網(wǎng)。由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判颉? AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?。b、從有向圖中刪除該頂點(diǎn)及其與該頂點(diǎn)有關(guān)的所有邊。d、輸出剩余的無前趨結(jié)點(diǎn)。時(shí)間復(fù)雜度是O(n+e)。排序在內(nèi)存中處理，不涉及數(shù)據(jù)的內(nèi)外存交換，稱為內(nèi)部排序，反之為外部排序。在排序過程中需進(jìn)行兩種操作：比較兩個關(guān)鍵字的大小、改變指向記錄的指針或移動記錄本身，而待排序記錄的存儲形式一般有三種：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)和輔助表。還有算法本身的復(fù)雜度。：每次將一個待排序記錄按其關(guān)鍵字大小插入到前面已排好序的文件中的適當(dāng)位置。算法中R[0]作用：保存R[i]副本，監(jiān)視數(shù)組下標(biāo)變量j是否越界。每次的比較是從后往前比較的?？臻g復(fù)雜度O(1)，所以是就地排序。初始情況是有序區(qū)中只有一個元素R[1]，無序區(qū)中R[2..n]。記錄的總比較次數(shù)和總移動次數(shù)都要比直接插入排序少得多，特別是當(dāng)n越大越明顯。：兩兩比較待排序記錄的關(guān)鍵字，如果發(fā)現(xiàn)兩個記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序位置。時(shí)間復(fù)雜度最好是O(n)，最壞是O(n2)，所以是O(n2)。 快速排序(劃分交換排序)：是冒泡排序的改進(jìn)。一趟快速排序步驟：設(shè)兩個指針i和j，初值分別為low和high，基準(zhǔn)為x=R[i]，i自增1，j自減1，重復(fù)直至i=j為止。有非常好的時(shí)間復(fù)雜度，優(yōu)于其他各種排序算法，O(nlog2n)，但是當(dāng)記錄關(guān)鍵字有序或基本有序時(shí)復(fù)雜度反而大了使之轉(zhuǎn)變成冒泡排序?yàn)镺(n2)。：每一趟在待排序的記錄中選出關(guān)鍵字最小的記錄，依次存放在已排序好的記錄序列的最后。時(shí)間復(fù)雜度O(n2)，是不穩(wěn)定的。 堆排序：是對直接選擇排序的改進(jìn)，是一種樹形選擇排序。每一趟排序：將當(dāng)前無序區(qū)調(diào)整為一個大根堆，選取關(guān)鍵字最大的堆頂記錄，將他和無序區(qū)中最后一個記錄交換。構(gòu)造堆的過程：R[1]作為二叉樹的根，R[2..n]依次逐層從左到右順序排列，構(gòu)成一棵完全二叉樹，任意結(jié)點(diǎn)R[i]的左孩子是R[2i]，右孩子是R[2i+1]，雙親是R?i/2?，此稱為篩選法。每一趟的時(shí)間復(fù)雜度是O(log2n)，整個堆排序的時(shí)間復(fù)雜度是O(nlog2n)。每一趟歸并排序的時(shí)間復(fù)雜度是O(n)，所以總的時(shí)間復(fù)雜度是O(nlog2n)。 箱排序(桶排序)：基數(shù)排序：是對箱排序的改進(jìn)和推廣。每個分量可能取值的個數(shù)rd稱為基數(shù)，基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵字的類型而異?；鶖?shù)排序中，沒有進(jìn)行關(guān)鍵字的比較和記錄的移動，而只是掃描鏈表和進(jìn)行指針賦值，所以排序的時(shí)間主要用在修改指針上，初始化鏈表時(shí)間為O(n)。時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性插入直接插入O(n2)O(1)穩(wěn)定希爾排序O(nlog2n)或O()O(1)不穩(wěn)定交換冒泡排序O(n2)O(1)穩(wěn)定快速排序O(nlog2n)O(log2n)不穩(wěn)定選擇直接選擇O(n2)O(1)不穩(wěn)定堆排序O(nlog2n)O(1)不穩(wěn)定歸并排序歸并排序O(nlog2n)O(n)穩(wěn)定分配排序基數(shù)排序O(d*(rd+n))rd是基數(shù)，O(rd+n)穩(wěn)定箱排序選取排序方法時(shí)需要考慮的主要因素：a、待排序的記錄個數(shù)，b、記錄本身的大小和存儲結(jié)構(gòu)，c、關(guān)鍵字的分布情況，d、對排序穩(wěn)定性的要求，e、時(shí)間和空間復(fù)雜度要等排序方法的選?。篴、若待排序的一組記錄數(shù)目n較小(如n≤50)時(shí)，可采用插入排序或選擇排序；b、n較大時(shí)，則應(yīng)采用快速排序、堆排序或歸并排序；c、若待排序記錄按關(guān)鍵字基本有序時(shí)，則宜選用直接插入排序或冒泡排序；d、當(dāng)n很大，而且關(guān)鍵字位數(shù)較少時(shí)，采用鏈?zhǔn)交鶖?shù)排序較好；e、關(guān)鍵字比較次數(shù)與記錄的初始排列順序無關(guān)的排序方法是選擇排序。插入、歸并、基數(shù)排序易于在鏈表上實(shí)現(xiàn)；快速排序和堆排序可以提取關(guān)鍵字建立索引表，然后對索引表進(jìn)行排序。 查找也分為內(nèi)查找和外查找。：順序查找和二分查找 順序查找又稱線性查找：查找成功的平均查找長度(n+1)/2，即約為表長的一半。優(yōu)點(diǎn)是簡單，對表的結(jié)構(gòu)無任何要求，無論是順序存儲和鏈?zhǔn)酱鎯Αo論是否有序，都同樣適用，缺點(diǎn)是效率低。二分查找(折半查找)：要求查找對象的線性表必須是順序存儲結(jié)構(gòu)的有序表。樹中每個子樹的根節(jié)點(diǎn)對應(yīng)當(dāng)前查找區(qū)間的中位記錄R[mid]，它的左子樹和右子樹分別對應(yīng)區(qū)間的左子表和右子表，通常將此樹稱為二叉判定樹。二叉判定樹一定是二叉排序樹，二叉排序樹又稱為二叉查找樹。因此，二分查找算法在查找成功時(shí)進(jìn)行關(guān)鍵字比較的次數(shù)最多不超過判定樹的深度。因?yàn)榕卸涠葦?shù)小于2的結(jié)點(diǎn)只可能在最下面的兩層，所以n個結(jié)點(diǎn)的判定樹的深度和n個結(jié)點(diǎn)的完全二叉樹的深度相同，即為?log2(n+1)?。二叉判定樹的輸出：每次以?(low+high)/2?為根建樹。要求分塊有序，前一塊的最大關(guān)鍵字小于后一塊的最小關(guān)鍵字，抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成索引表。平均查找長度：二分查找log(n/s+1)+s/2， 順序查找(s2+2s+n)/2s。 二分查找成功時(shí)約為log2(n+1)1，但是他要求表以順序存儲且按關(guān)鍵字有序，適用于表不易變動且又經(jīng)常查找的情況。主要缺點(diǎn)是需要增加一個輔助數(shù)組的存儲空間和將初始表塊排序的運(yùn)算，它也不適用于鏈?zhǔn)酱鎯Y(jié)構(gòu)。b、若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值。 由此可得，按中序遍歷二叉排序樹所得到的遍歷序列是一個遞增有序序列。 構(gòu)造二叉排序樹的真正目的并不是為了排序，而是為了更好地查找，又稱為二叉查找樹。若二叉排序樹是一顆理想的平衡樹或接近理想的平衡樹，則時(shí)間復(fù)雜度為O(log2n)，若退化為一棵單支樹，則時(shí)間復(fù)雜度為O(n)。具體操作為：a、若p是葉子結(jié)點(diǎn)，直接刪除p；b、若p只有一棵子樹(左子樹或右子樹)，直接用p的左子樹(或右子樹)取代p的位置而成為f的一棵子樹。s是p的左子樹中最右邊的結(jié)點(diǎn)且沒有右子樹；(2)、用p的直接后繼結(jié)點(diǎn)代替p，即從p的右子樹中選擇值最小的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容)，然后刪除結(jié)點(diǎn)s。在二叉排序樹上實(shí)現(xiàn)插入和查找操作的平均時(shí)間復(fù)雜度為O(log2n)，但在最壞得情況下，會變成O(n)。因此，若根結(jié)點(diǎn)不是葉子，則它至少有兩顆子樹。在B樹上插入和刪除元素的運(yùn)算比較復(fù)雜，它要求進(jìn)行運(yùn)算后的結(jié)點(diǎn)中關(guān)鍵字個數(shù)≥?m/2?1， 在B樹進(jìn)行查找包括兩種基本操作：在B樹中查找結(jié)點(diǎn)、在結(jié)點(diǎn)中查找關(guān)鍵字。因此可對B+樹進(jìn)行兩種查找運(yùn)算：一種是從最小關(guān)鍵字起進(jìn)行順序查找，一種是從根結(jié)點(diǎn)開始進(jìn)行隨機(jī)查找。散列存儲中使用的函數(shù)稱為散列函數(shù)或哈希函數(shù)，散列地址或哈希地址，散列表或哈希表。沖突的頻度除了與散列函數(shù)H相關(guān)外，還與散列表的填滿程度相關(guān)。散列函數(shù)的目標(biāo)是使散列地址盡可能均勻的分布在散列空間上，同時(shí)使計(jì)算盡可能簡單。適合于關(guān)鍵字的分布基本連續(xù)的情況。除余數(shù)法：p最好取小于或等于表長m的最大素?cái)?shù)。平方取中法： 折疊法：把關(guān)鍵字分割成位數(shù)相同的幾段，分為移位疊加和邊界疊加。開放定址法：線性探查法、二次探查法和雙重散列法(幾種方法中最好的方法)。把具有相同散列地址的關(guān)鍵字值放在同一個單鏈表中，稱為同義詞鏈表。用拉鏈法處理沖突比開放定址法多占用一些存儲空間用作鏈表指針，但它可以減少在插入和查找過程中關(guān)鍵字的平均比較次數(shù)(平均查找長度)。散列表查找，計(jì)算查找成功的平均查找長度時(shí)，除數(shù)是結(jié)點(diǎn)的個數(shù)，而在計(jì)算查找不成功的平均查找長度時(shí)，除數(shù)卻是表長。拉鏈法：α可以大于1，但一般取α