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