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