【正文】 　　第六章 樹　　樹是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱根的子樹。凹入表示法　　二叉樹的4個(gè)重要性質(zhì)： 在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1；　　它就是由根指針root唯一確定的。利用二叉鏈表中的n+1個(gè)空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。樹變二叉樹：兄弟相連，保留長子的連線。森林變二叉樹：樹變二叉樹，各個(gè)樹的根相連。孩子鏈表表示法：為樹中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域?！　≡谌~子的權(quán)值相同的二叉樹中，完全二叉樹的路徑長度最短?！　」蚵鼧涞膽?yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。有向圖Digraph：每條邊有方向；無向圖Undigraph：每條邊沒有方向?！　〗⑧徑泳仃囁惴ǖ臅r(shí)間是O（n+n^2+e），其時(shí)間復(fù)雜度為O（n^2）　　有向圖又分出邊表和逆鄰接表；深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用隊(duì)列保存已訪問結(jié)點(diǎn)。Prim算法的時(shí)間復(fù)雜度為O（n^2）與邊數(shù)無關(guān)適于稠密圖。Dijkstra算法，時(shí)間復(fù)雜度為O（n^2）。拓?fù)渑判蛞灿袃煞N方法：第八章 排序　　記錄中可用某一項(xiàng)來標(biāo)識(shí)一個(gè)記錄，則稱為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字?！　?nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。逐個(gè)向前插入到合適位置。是在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否越界。希爾排序： 冒泡排序：時(shí)間復(fù)雜度為O（n^2），比較次數(shù)為n（n1）/2；移動(dòng)次數(shù)為3n（n1）/2；　　　　選擇最小的放在比較區(qū)前。比較次數(shù)為n（n1）/2；　　　　　　歸并排序： 箱排序： 　基數(shù)排序是非就穩(wěn)定的排序，時(shí)間復(fù)雜度是O（d*n+d*rd）。關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；　　時(shí)間和輔助空間復(fù)雜度。順序查找：逐個(gè)查找，ASL=（n+1）/2；　　分塊查找。若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可?！￡P(guān)于B樹（多路平衡查找樹）。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡單和均勻。相乘取整法：hash=int（m*（x*Aint（x*A））；A=　　 一般形式為hi=（h（key）+di）%m1≤i≤m1，開放定址法要求散列表的裝填因子α≤1. 　　雙重散列法：address=（hash（x）+i*hash（y））%m；　　 拉鏈法的優(yōu)點(diǎn)： 拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。：便于查找。不滿足主關(guān)鍵字定義的關(guān)鍵字稱為次關(guān)鍵字。 ：(1)時(shí)間復(fù)雜度—— 它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)。 簡言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11第六次排序： 【3, 5, 6, 9, 13，27, 31】, 11第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 注：方括號(hào) [ ]中為已排序記錄的關(guān)鍵字，下劃橫線的 關(guān)鍵字表示它對(duì)應(yīng)的記錄后移一個(gè)位置。 i n 1。amp。 }}初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11直接插入排序算法分析(1)時(shí)間效率：當(dāng)數(shù)據(jù)有序時(shí)，執(zhí)行效率最好，此時(shí)的時(shí)間復(fù)雜度為O(n)；當(dāng)數(shù)據(jù)基本反序時(shí)，執(zhí)行效率最差，此時(shí)的時(shí)間復(fù)雜度為O(n2)。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。 int n = 。 //取本次的增量值 for(k = 0。 i = i + span){ temp = a[i+span]。 temp a[j]){ a[j + span] = a[j]。 時(shí)間效率：O(n(log2n)2) 空間效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元 算法的穩(wěn)定性：不穩(wěn)定 練習(xí)：1. 欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母升序重排，則初始d為4的希爾排序一趟的結(jié)果是？答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, Xshell一趟后： P,A,C,S,Q,D,F,X,R,H,M,Y2. 以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行希爾排序（取d=5,3,1）算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。）優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡單缺點(diǎn)：每趟只能確定一個(gè)元素，表長為n時(shí)需要n1趟例3：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出直接選擇排序的具體實(shí)現(xiàn)過程。 for(i = 0。 j n。 a[small] = temp。 int temp。 i++){ small = i。 //記住最小元素的下標(biāo) } if(small != i){ temp = a[small]。 a[i] = temp。終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(dú)調(diào)整例：關(guān)鍵字序列T= (21，25，49，25*，16，08），請(qǐng)建最大堆。 i = h。 while(j n amp。 a[j] a[j + 1]) j++。 j = 2 * i + 1。 for(int i = (n11) / 2。 再對(duì)前面的n1個(gè)對(duì)象，使用堆的調(diào)整算法，重新建立堆（調(diào)整根結(jié)點(diǎn)使之滿足最大堆的定義）。 int n = 。 i ){ //當(dāng)前最大堆個(gè)數(shù)每次遞減1 //把堆頂a[0]元素和當(dāng)前最大堆的最后一個(gè)元素交換 temp = a[0]。 //調(diào)整根結(jié)點(diǎn)滿足最大堆 }}堆排序算法分析：時(shí)間效率：O(nlog2n)。A.{1,4,8,9,20,7,15,7*} B.{1,7,15,7*,4,8,20,9}C.{1,4,7,8,20,15,7*,9} 練習(xí)3：已知序列{503，87，512，61，908，170，897，275，653，462}，寫出采用堆排序?qū)υ撔蛄凶鞣沁f減排列時(shí)的排序過程。例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)按從小到大的順序，寫出冒泡排序的具體實(shí)現(xiàn)過程。 for(i = 1。 i++){ flag = 0。 temp = a[j]。初態(tài)：31，15，9， 25，16， 28第1趟15，9，25，16， 28， 31第2趟9，15， 16， 25，28，31第3趟9，15， 16，25， 28，31基本思想：設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，low為數(shù)組的低端下標(biāo)，high為數(shù)組的高端下標(biāo)，從數(shù)組a中任取一個(gè)元素（通常取a[low]）做為標(biāo)準(zhǔn)元素，以該標(biāo)準(zhǔn)元素調(diào)整數(shù)組a中其他各個(gè)元素的位置，使排在標(biāo)準(zhǔn)元素前面的元素均小于標(biāo)準(zhǔn)元素，排在標(biāo)準(zhǔn)元素后面的均大于或等于標(biāo)準(zhǔn)元素。 例、關(guān)鍵字序列 T=(60，55，48，37，10，90，84，36），請(qǐng)按從小到大的順序，寫出快速排序的具體實(shí)現(xiàn)過程。 j = high。 temp = a[j]) j。amp。 } } a[i] = temp。練習(xí)：已知序列{503,87,512,61,908,170,897,275,653,462}，給出采用快速排序?qū)υ撔蛄凶鞣沁f減排序時(shí)每趟的結(jié)果。（ A ） (n) (nlog2n) C. O(log2n) (n2) {8,9,10,4,5,6,20,1,2}只能是（ C ）算法的兩趟排序后的結(jié)果。A.{85，80，45，40，42，55} B.{85，80，55，40，42，45} C.{85，80，55，45，42，40} D.{85，55，80，42，45，40}第十章 文件　　文件是性質(zhì)相同的記錄的集合?！　〈鎯?chǔ)結(jié)構(gòu)是指文件在外存上的組織方式。常用的文件組織方式：順序文件、索引文件、散列文件和多關(guān)鍵字文件。主關(guān)鍵字有序稱順序有序文件，否則稱順序無序文件?！　∷饕琼樞蛭募械乃饕頌槌砻芩饕?。　　索引順序文件常用的有兩種：　　　　散列文件是利用散列存儲(chǔ)方式組織的文件，亦稱為直接存取文件。缺點(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問方式限地簡單詢問，需要重新組織文件