【正文】 下述性質：廣義表是n(n≥0)個元素a1，a2，…，ai，…，an的有限序列。特點：: 二叉樹的每個結點最多有兩個孩子。 BinaryTree)。將一個森林轉換為二叉樹:將森林中的每棵樹轉化成二叉樹，然后再將二叉樹的根節(jié)點看做兄弟連在一起，形成一棵二叉樹、森林的轉換: 方式是：若二叉樹中結點x是雙親y的左孩子，則把x的右孩子，右孩子的右孩子，…，都與y用連線連起來，最后去掉所有雙親到右孩子的連線。 哈夫曼樹又稱為最優(yōu)樹，是一類帶權路徑長度最短的樹。 ② n個葉子的哈夫曼樹要經過n1次合并，產生n1個新結點。無向圖中，頂點的度定義為以該頂點為一個端點的邊的數目，有向圖的度等于出度和入度之和。圖的鄰接表表示不是唯一的,這是因為在每個頂點的鄰接表中，各邊結點的鏈接次序可以是任意的，其具體鏈接次序與邊的輸入次序和生成算法有關。這樣的有向無環(huán)圖DAG稱為頂點活動網，簡稱為AOV網。還有算法本身的復雜度。時間復雜度最好是O(n)，最壞是O(n2)，所以是O(n2)。構造堆的過程：R[1]作為二叉樹的根，R[2..n]依次逐層從左到右順序排列，構成一棵完全二叉樹，任意結點R[i]的左孩子是R[2i]，右孩子是R[2i+1]，雙親是R?i/2?，此稱為篩選法。 查找也分為內查找和外查找。二叉判定樹的輸出：每次以?(low+high)/2?為根建樹。若二叉排序樹是一顆理想的平衡樹或接近理想的平衡樹，則時間復雜度為O(log2n)，若退化為一棵單支樹，則時間復雜度為O(n)。散列存儲中使用的函數稱為散列函數或哈希函數，散列地址或哈希地址，散列表或哈希表。用拉鏈法處理沖突比開放定址法多占用一些存儲空間用作鏈表指針，但它可以減少在插入和查找過程中關鍵字的平均比較次數(平均查找長度)。開放定址法：線性探查法、二次探查法和雙重散列法(幾種方法中最好的方法)。在B樹上插入和刪除元素的運算比較復雜，它要求進行運算后的結點中關鍵字個數≥?m/2?1， 在B樹進行查找包括兩種基本操作：在B樹中查找結點、在結點中查找關鍵字。 由此可得，按中序遍歷二叉排序樹所得到的遍歷序列是一個遞增有序序列。因此，二分查找算法在查找成功時進行關鍵字比較的次數最多不超過判定樹的深度。時間復雜度空間復雜度穩(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)定分配排序基數排序O(d*(rd+n))rd是基數，O(rd+n)穩(wěn)定箱排序選取排序方法時需要考慮的主要因素：a、待排序的記錄個數，b、記錄本身的大小和存儲結構，c、關鍵字的分布情況，d、對排序穩(wěn)定性的要求，e、時間和空間復雜度要等排序方法的選?。篴、若待排序的一組記錄數目n較小(如n≤50)時，可采用插入排序或選擇排序；b、n較大時，則應采用快速排序、堆排序或歸并排序；c、若待排序記錄按關鍵字基本有序時，則宜選用直接插入排序或冒泡排序；d、當n很大，而且關鍵字位數較少時，采用鏈式基數排序較好；e、關鍵字比較次數與記錄的初始排列順序無關的排序方法是選擇排序。 堆排序：是對直接選擇排序的改進，是一種樹形選擇排序。記錄的總比較次數和總移動次數都要比直接插入排序少得多，特別是當n越大越明顯。排序在內存中處理，不涉及數據的內外存交換，稱為內部排序，反之為外部排序。 構造最小生成樹的算法：普里姆Prim算法的時間復雜度為O（n2）與網中邊數無關適于稠密圖。無向圖的鄰接矩陣表示法可以僅存儲主對角線以下的元素，時間復雜度為O(n2) 鄰接表表示法：鄰接表是圖的一種鏈式存儲結構。用尖括號表示圖的有向邊vi,vj,有向邊又稱為弧，起點稱為弧尾，終點稱為弧頭。而(b)圖所示二叉樹的前序序列和中序序列也分別為ABCDEFIGJH和BDCAIFJGHE。因此對于n個結點的二叉樹，線索化的算法時間復雜度為O(n)。 已知一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。②若2i+1n，則qi的左孩子的編號是2i+1；否則，qi無左孩子，即qi必定是葉子。滿二叉樹的特點：（1）每一層上的結點數都達到最大值。根結點又稱為開始結點。樹結構的基本術語由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行、列位置，所以可用三元組(i，j，aij)來確定非零元素。 a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn Pascal和C語言是按行優(yōu)先順序存儲的，而Fortran語言是按列優(yōu)先順序存儲的。 Qrear==Qfront。 Qrearnext=p。 pdata=x。 為了簡化處理，在隊頭結點之前附加一個頭結點，并設隊頭指針指向此結點?！　、?少用一個元素的空間。循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。兩個棧共享同一存儲空間: 當程序中同時使用兩個棧時，可以將兩個棧的棧底分別設在順序存儲空間的兩端，讓兩個棧頂各自向中間延伸。 free(p)。r=pnext。 p=pnext。//找到了第i個結點while((ch=getchar())!=39。④//尾指針指向新表尾（3） 尾插法建帶頭結點的單鏈表：頭結點及作用：頭結點是在鏈表的開始結點之前附加一個結點。③ head=p。順序表（Sequential List）：用順序存儲方法存儲的線性表稱為順序表。：算法的正確性是首先要考慮的。數據的邏輯結構分類: 線性結構和非線性結構。數據對象是具有相同性質的數據元素的集合。：輸入，0個或多個數據作為輸入；輸出，產生一個或多個輸出；有窮性，算法執(zhí)行有限步后結束；確定性，每一條指令的含義都明確；可行性，算法是可行的。(5)InsertList（L，i，x）在線性表L的第i個元素之前插入一個值為x 的新元素，表L的長度加1。② //將讀入的數據放入新結點的數據域中③//將新結點插到*r之后算法：p=head。③ snext=pnext。 {//假設A，B為非空循環(huán)鏈表的尾指針LinkList p=Anext。③將頭結點和尾結點鏈接起來，為雙（向）循環(huán)鏈表。 sdata=x。 snext=p。 pprior=s。//①在非空隊列里，頭指針始終指向隊頭元素，而隊尾指針始終指向隊尾元素的下一位置。 i=(i+1)%QueueSize；循環(huán)隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。⑥取隊頭元素 return Qdata[Qfront]。 //隊尾指針指向新的尾（4） 出隊：當隊列長度大于1時，只需修改頭結點指針，尾指針不變 return x。 a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn（2）列優(yōu)先順序①上三角矩陣中aij和sa[k]之間的對應關系k=i(2ni+1)/2+ji 當i≤j k=n(n+1)/2 當i＞j②下三角矩陣中aij和sa[k]之間的對應關系k=i(i+1)/2+j 當i≥j k=n(n+1)/2 當i＜j三角矩陣的壓縮存儲結構是隨機存取結構。 ?、跒榱藚^(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而后者是長度為l的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表()。例如5層的二叉樹，第5層上的結點數目最多為24=16性質2 深度為k的二叉樹至多有2k1個結點(k≥1)。每一層的結點個數恰好是上一層結點個數的2倍。先序遍歷的遞歸算法定義：(1)訪問根結點； (2)遍歷左子樹； (3)遍歷右子樹。 線索二叉樹中，一個結點是葉結點的充要條件為：左、右標志均是1。：孩子鏈表表示法是為樹中每個結點設置一個孩子鏈表，并將這些結點及相應的孩子鏈表的頭指針存放在一個向量中。：一般都只給出兩種次序遍歷樹的方法：前序(先根次序)遍歷和后序(后根次序)遍歷?！　?2)在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時，可以從中任選兩棵)，將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關緊要)，將這兩個孩子的權值之和作為新樹根的權值。因此設計電文總長最短的二進制前綴編碼，就是以n種字符出現的頻率作為權構造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼。 鄰接矩陣表示法：vi,vj或(vi,vj)是邊，則值為1，不是邊則值為0。 因此，一個具有n個頂點的生成樹有且僅有n1條邊，但有n1條邊的圖不一定是生成樹，同一個圖可以有不同的生成樹。 拓撲排序實際上是對鄰接表表示的圖G進行遍歷的過程。 是穩(wěn)定的算法。 直接選擇排序：初始時，R[1..n]為無序區(qū)，R[1]為空；第一趟是在R[1..n]中選出最小的記錄與R[1]交換，R[1]為有序區(qū)；第二趟是在R[2..n]中選出最小的記錄與R[2]交換，R[1..2]為有序區(qū)。d趟箱排序。由于二分查找是在有序表上進行的，所以其對應的判定樹必定是一棵二叉排序樹。 上述三種查找的時間復雜度分別是O(n)、O(log2n)和O(n的平方根)(二叉查找樹)：或者是一棵空樹，或者具有下面性質：a、若右子樹非空，則右子樹上所有結點的值均大于根節(jié)點的值。 一棵m(m≥3)階的B樹，或為