【正文】 28—129），起始地址128，其伙伴起始地址192（192—255）掛到26空閑塊鏈表中。 （4）100〈=27=128，因無27空閑塊，28塊產(chǎn)生分裂，其中首址256（256—383）的一半分給用戶，其伙伴（首址384）掛到27空閑塊鏈表中。 （5）11〈=16=24，因無24空閑塊，25產(chǎn)生分裂，一半（首址32（32—47））分給用戶，其伙伴（首址48）掛到24大小的空閑塊鏈塊表。（6）19〈=32=25。因無25空閑塊，26塊分裂，一半（首址192（192—223））分給用戶，其伙伴（首址224）掛到25空閑塊鏈表中。 總之，6個用戶占用塊首址依次為0，64，128，256，32和192，這時可利用空間表的狀態(tài)為： 20^21^22^23^242526^2728^29^│ 0 │ 4 │ │ 0 │ 5 │ │ 0 │ 7 │ 回收（1） （1） 45〈=26=64，其首址為64，因64 MOD 26+1=26，所以其伙伴地址為6464=0（不空）其伙伴占用，故僅將此結(jié)點(diǎn)掛到26空閑塊鏈表中。（2） （2） 52=26=64,其首址為128，因128 MOD 26+1=0，所以，伙伴地址=128+64=192（占用），故僅將此塊掛到26空閑塊鏈表中。（3） （3） 11〈=24=16，首址32因32 MOD 24+1=0，伙伴地址32+24=48（空閑），故合并成25（塊）。因32 MOD 25+1=2，新伙伴地址為3232=0（不空），故將25一塊掛于25的空閑塊鏈表中。總之，三塊釋放后空閑表狀態(tài)如下：20^21^22^23^24^25262728^29^│ 0 │ 7│ 首地址384│ 0 │ 6 │ 首地址64│ 0 │ 6│ 首地址128│ 0 │ 5│ 首地址224│ 0 │ 5│ 首地址32第九章　 查找一、內(nèi)容提要 本章介紹的查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個集合中。 查找表的操作：查找，檢索，插入，刪除，成員關(guān)系判斷。 靜態(tài)查找表：順序表，有序表，靜態(tài)樹表，索引順序表。 動態(tài)查找表：二叉排序樹，平衡二叉樹，B樹，B+樹，鍵樹。 哈希表。二、學(xué)習(xí)重點(diǎn)查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。因元素間關(guān)系非常松散，其操作需借助其它數(shù)據(jù)結(jié)構(gòu) 來實(shí)現(xiàn)。本章列舉了三種方法（靜態(tài)查找表，動態(tài)查找表，哈希表）實(shí)現(xiàn)查找表的運(yùn) 算。順序表因引設(shè)置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長度不超過樹的深度，其判定樹是唯一的。索引順序查找綜合了上述二者的優(yōu)點(diǎn)，既能較快速的查找，又能適應(yīng)動態(tài)變化的要求。二叉排序樹的形態(tài)取決于元素的輸入順序。按中序遍歷可得到結(jié)點(diǎn)的有序序列，應(yīng)熟 練掌握其建立、查找，插入和刪除算法。 最佳二叉排序樹是平均查找長度最短的二叉排序樹，平衡二叉樹是介于最佳和一般間的折中，應(yīng)熟練掌握手工繪制平衡二叉樹。 鍵樹中每個結(jié)點(diǎn)是關(guān)鍵字的一個字符，該樹是有序樹（同層兄弟間從左到右遞增，最 小是結(jié)束符號$）。 哈希表是查找表（集合）的又一表示方法，根據(jù)選定的哈希函數(shù)和處理沖突的方法，將關(guān)鍵字映像到哈希表中。沖突是不可避免的。 哈希表中關(guān)鍵字的查找只能用哈希函數(shù)來計(jì)算，不能順序、折半查找。元素刪除也只能作標(biāo)記，不能物理的刪除。三、例題解析 1．設(shè)二叉排序樹中元素均為整數(shù)，試編寫算法從大到小輸出各元素值。 【分析】中序遍歷二叉排序樹可得元素的有（升）序序列。 【算法】 PROC bstoutput (bst:bitreptr)； {bst是二叉排序樹根結(jié)點(diǎn)指針，本算法從大到小輸出二叉排序樹的各結(jié)點(diǎn)的值} IF bstNIL THEN [ bstoutput (bst↑.rchild)。 write (bst↑.data:5)； bstoutput(bst↑.lchild)。 ]； ENDP；{bstoutput} 【討論】課本中討論了二叉樹的三種遞歸遍歷算法,另三種并非沒用。本題就是先中序　　　遍歷右子樹，再訪問根結(jié)點(diǎn)，最后中序遍歷左子樹。本題另一種解法是在中序遍歷　　　二叉排序樹 ，訪問根結(jié)點(diǎn)時將結(jié)點(diǎn)值進(jìn)棧保存，遍歷結(jié)束后依次彈出棧中元素，直至?？?，所得結(jié)果亦符合要求，但多用了一個棧，不如這里所采用的算法簡單。 2． 編寫在二叉排序樹上插入結(jié)點(diǎn)s的算法。 【分析】二叉排序樹上插入結(jié)點(diǎn)都是在葉子上插入。 【算法】 PROC insert (VAR bst: bitreptr。；s:bitreptr)。 {本算法在二叉排序樹bst 上插入結(jié)點(diǎn)s} IF bst =NIL THEN bst:=s ELSE IF s↑.data THEN insert (bst↑.lchild,s) ELSE insert (bst↑.rchild,s)。 ENDP。 {insert}【討論】 這是最簡潔的遞歸算法。 3．編寫在索引順序表中查找數(shù)據(jù)k的算法?！痉治觥克饕樞虿檎矣址Q分塊查找，設(shè)表中共有n個記錄，每塊中有s個記錄，故共有b=┌ (n/s) ┐(上取整)塊。現(xiàn)設(shè)一索引表，其結(jié)構(gòu)如下：TYPE idxtb1=RECORD key: keytype。 low,high:integer。 END。 Index=ARRAY[1..b]OF idxtbl。記錄中三個域：key為索引所指塊中最大關(guān)鍵字，low和high指該塊中最低下標(biāo)值和最高下標(biāo)值。先折半查找索引表，再順序在索引所指的某塊內(nèi)查找?！舅惴ā縁UNC indxblk( r:seqlisttp: idx:index。 k:keytype):integer。 {本算法在索引順序表r中，查找其關(guān)鍵字值為待查元素值k的元素。Idx是索引表} low:=1。high:=b；{在索引表中折半查找其值 =k的最小元素} found:=false。 WHIEL （low=high）AND NOT found DO [ mid：=（low+high） DIV 2。 CASE r[mid].key=k： low:=mid。 found:=true。 r[mid].keyk:：high:=mid1。 r[mid].keyk:：low:=mid+1。 ENDC；{若查找失敗low值即為所求} IF lowb THEN low:=b。 {取最后一塊} l:=idx[low].low。 {取待查塊在r中的最低和最高下標(biāo)} h:=idx(low).high。 i:=l。 WHILE (r[i].keyk) AND (i=h) DO i:=i+1。 IF r[i].key=k THEN idxblk:=i ELSE idxblk:=o。ENDF；{indxblk} 4．已知一個含有100個記錄的表，關(guān)鍵字是中國人名的拼音。請給出此表的一個哈希表設(shè)計(jì)方案。要求在等概率情況下查找成功的平均查找長度不超過3。 【分析】（1） 根據(jù)平均查找長度不超過3，確定裝填因子α； snl≈1/2(1+(1/(1α))){使用線性探測再散列解決沖突} 因snl=3,取α=.（2） 根據(jù)α確定表長 由α=（表中添入的記錄數(shù)）/（哈希表的長度） 所以 哈希表的長度=100/α=125 取表長=150；（3） 選取哈希函數(shù) H(key)=key MOD 149 (4) key 的選取方法。 設(shè)大寫字母在表中用1..26 表示，小寫字母用2752 表示。每個人的姓名取四個字　　　母（兩字姓名取首尾兩個字母，三字姓名取各字拼音第一個字母，中間字取首尾兩　　　個拼音字母）。 將前兩個拼音字母的序號并起來，后兩個也并起來, 然后相加形成關(guān)鍵字。要求姓名　　　的第一個拼音字母要大寫，如姓名39。王麗明39。拼音為39。Wang liming39。，取出四個拼音字母　　　為39。W,l,i,m39。,個字母序號依次為 23 38 35 39，組成關(guān)鍵字為 2338+3539=5877，該姓　　　名的哈希地址為 5877 MOD 149=66。(5) (5) 用線性探測再散列處理沖突。第十章 內(nèi)部排序一、內(nèi)容提要排序的定義，排序可以看作是線性表的一種操作排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。插入排序（對分插入、二路插入、表插入、希爾插入排序）。交換排序（冒泡排序、快速排序）。選擇排序（簡單選擇排序、樹形選擇排序、堆排序）。歸并排序、基數(shù)排序。二、學(xué)習(xí)要點(diǎn)1． 1．各種排序所基于的基本思想。2． 2．在“最好”和“最差”情況下，排序性能的分析，是否是穩(wěn)定排序的結(jié)論。3． 3．插入排序基于假定待排序文件第一個記錄有序，然后從第二個記錄起，依次插入到已排好序的有序子文件中，直到整個文件有序。從減少比較次數(shù)和移動次數(shù)進(jìn)行了各種改進(jìn)，產(chǎn)生了折半、二路、表插入、希爾等一系列插入排序。4． 4．交換排序基于相鄰記錄比較，若逆序則進(jìn)行交換。冒泡排序和快速排序是交換排序的例子，快速排序是目前最快的內(nèi)部排序法。應(yīng)采用“三者取中”法防止其性能退化。5． 5．簡單選擇排序、樹形選擇排序、堆排序是選擇排序的例子。堆排序較為重要，其最差性能比快速排序的最差性能好（Ologn）6． 6．歸并排序、基數(shù)排序及時間復(fù)雜度O(n2)的排序?yàn)榉€(wěn)定排序，而希爾排序、快速排序、堆排序等時間性能好的排序方法，包括簡單選擇排序，是不穩(wěn)定排序。7． 7．對每種排序方法的學(xué)習(xí)，應(yīng)掌握其本質(zhì)（排序所基于的思想），并能舉一反三。二、例題解析1． 1．設(shè)待排序文件有n ( n0 )個記錄，試編寫算法，不經(jīng)全部排序，將第j (0j≤n)個元素放在適當(dāng)位置（即在排序后它應(yīng)在的位置）。　　　【分析】 將該記錄作樞軸，進(jìn)行一趟快速排序，則可將該記錄放在其排序后應(yīng)在的位置上。　　　【算法】　　　　PROC quickpass(VAR r:listtype。j:integer)。 ｛本算法將第j個記錄快速放到它排序后的位置上｝ IF j1 THEN r[j] ←→ r[1]。 i:=1。 k:=n。 rp:=r[i]。 x:=r[1].key。 WHILE ik DO [ WHILE (ik) AND (r[k].key≥x) DO k:=k1。 IF ik THEN [ r[i]:=r[k]。i:=i+1 ]。 WHILE (ik) AND (r[i].key≤x) DO i:=i+1。 IF ik THEN [ r[k]:=r[i]。k:=k1] ] r[i]:=rp。 ENDP。{quickpass} 　　　 【討論】本題的一種變形可敘述為：不經(jīng)全部排序，求出排序后第j(0jn)個位　　　　置的元素。即，若將n個記錄排序后，該元素是第j個記錄?！　　? 設(shè)待排序文件的記錄下標(biāo)的下界、上界是s和t,根據(jù)一趟快速排序，求出　　　　第一個元素（樞軸）所在位置i,若i=j則該位置即為所求，若ij則到(i+1t)　　　　　中去找j,否則到(si1)中去求，直到i=j為止。 PROC Quicksort_J(VAR r:Listype。 j:integer；VAR rp:rcdtype)。 {求記錄序列r[1..n]中排序后第j個的記錄rp。} s:=1。 t:=n。 quickpass( r,s,t,k) WHILE kj DO IF kj THEN quickpass( r,k+1