字典與檢索詳解演示文稿現在是1頁\一共有102頁\編輯于星期六（優選）字典與檢索現在是2頁\一共有102頁\編輯于星期六元素個數與字符數組長度的關系：

size=(n+7)/8每個字符8位，最后一個字符可能不滿。給定成員位置idx，確定在那個字符中：

which_char=idx>>3; //即：idx/8確定哪一位：

which_bit=idx&07; //即：idx%8

(后三位)765432109821010101010arraysizeS={1,3,5,7,9}現在是3頁\一共有102頁\編輯于星期六創建空集合：BitSet*CreateEmptySet(intn){ BitSet*s=(BitSet*)malloc(sizeof(BitSet)); if(!s)returnNULL; s->size=(n+7)/8; s->array=(char*)malloc(s->size);

memset(s->array,0,s->size); returns;}現在是4頁\一共有102頁\編輯于星期六插入運算：intInsert(BitSet*s,intidx){ if(idx>=0&&(idx>>3<s->size)) {

s->array[idx>>3]|=(1<<(idx&07)); return1; } return0;}模板，對應位置1▲111或現在是5頁\一共有102頁\編輯于星期六刪除運算：intDelete(BitSet*s,intidx){ if(idx>=0&&(idx>>3<s->size)) {

s->array[idx>>3]&=~(1<<(idx&07)); return1; } return0;}模板，對應位置0▲1111011110與00010000現在是6頁\一共有102頁\編輯于星期六屬于判斷：intMember(BitSet*s,intidx){ if(idx>=0&&(idx>>3<s->size)) { return(s->array[idx>>3]&(1<<(idx&07))); } return0;}1與對應位“與”運算▲1現在是7頁\一共有102頁\編輯于星期六集合并：通過對應位“或”運算完成intUnion(BitSet*s0,BitSet*s1,BitSet*s2){ inti; if(s0->size!=s1->size||s2->size!=s1->size)return0; for(i=0;i<s1->size;i++) {

s2->array[i]=s0->array[i]|s1->array[i]; } return1;}011000100111001101010001000010010111001101111011S1S0S1S0S2現在是8頁\一共有102頁\編輯于星期六集合交：通過對應位“與”運算完成intIntersection(BitSet*s0,BitSet*s1,BitSet*s2){ inti; if(s0->size!=s1->size||s2->size!=s1->size)return0; for(i=0;i<s1->size;i++) {

s2->array[i]=s0->array[i]&s1->array[i]; } return1;}011000100111001101010001000010010100000000000001S0S1S0S1S2現在是9頁\一共有102頁\編輯于星期六集合差：在第一個集合中，同時不在第二個集合中

第一個集合與第二個集合的逆做“與”運算intDifference(BitSet*s0,BitSet*s1,BitSet*s2){ inti; if(s0->size!=s1->size||s2->size!=s1->size)return0; for(i=0;i<s1->size;i++)

s2->array[i]=s0->array[i]&~(s1->array[i]); return1;}1001110110001100010100010000100100010001000010000110001001110011S1~S1S0S0S1S2現在是10頁\一共有102頁\編輯于星期六單鏈表：有序單鏈表，各個結點存放成員本身。structNode{ DataTypeinfo; structNode*link;};typedefstructNode*PNode;基本運算實現：p177~180

注意兩個有序單鏈表運算如何實現集合運算?，F在是11頁\一共有102頁\編輯于星期六字典的組成：關鍵碼+屬性字典與索引:6.2字典的基本概念key1key2key3……keyi……keyn-2keyn-1keynd1d2d3……di……dn-2dn-1dn目錄表字典字典相關的運算（排序、檢索等），直接在字典的目錄表（索引）下進行，不用關心字典本身。現在是12頁\一共有102頁\編輯于星期六3.檢索：按照關鍵碼進行給定一個值key,按照某種次序在字典中進行檢索（與關鍵碼進行比較），如果找到則檢索成功，否則失敗。4.存儲結構：靜態、動態靜態：一旦建立，不再修改，只有檢索運算動態：除檢索外，字典經常變化（插入、刪除）現在是13頁\一共有102頁\編輯于星期六5.衡量檢索算法的標準平均查找長度

pi為查找第i個元素的概率，

ci為查找第i個元素的比較次數如不特別聲明為等概率查找，pi=1/n檢索中的基本運算：關鍵碼與給定值的比較字典（索引）的表示：順序表，散列表，樹表靜態字典動態字典現在是14頁\一共有102頁\編輯于星期六順序檢索、二分法檢索、分塊檢索順序表的表示typedefstruct /*元素結構*/{ KeyTypekey; /*元素的關鍵碼*/ DataTypeother;/*其它屬性字段*/}DicElement;typedefstruct/*字典結構*/{DicElementelement[MAXNUM]; /*字典數組*/intn;/*實際元素個數*/}SeqDictionary;6.3順序表檢索KeyType:intDataType:int現在是15頁\一共有102頁\編輯于星期六2.順序檢索（1）思想：從字典一端開始順序掃描，將字典元素的關鍵碼與給定值進行比較。如果相等，則檢索成功；當全部元素皆比較完，到達了字典的另一端，則檢索失敗。（2）算法：intSeqSearch(SeqDictionary*pdic,KeyTypekey,int*pos){inti;for(i=0;i<pdic->n;i++)/*從頭開始*/{if(pdic->element[i].key==key)/*成功*/{*pos=i; returnTRUE;}}*pos=i;returnFALSE;/*失敗*/}現在是16頁\一共有102頁\編輯于星期六

時間效率分析從算法可以看出：c1=1,c2=2,…,ci=i,…(找到第i個元素），因此，查找成功

如果等概率查找，則pi=1/n,ASL=(1+2+…+i+…+n)/n=(n+1)/2

查找失敗的比較次數：n次時間復雜度為：O(n)現在是17頁\一共有102頁\編輯于星期六(4)不等概率情況下的改進：在不等概率情況下，當P1≥P2…≥Pn時，ASL最小。因此，在不等概率時，應該保持概率最大的元素在最前面，概率最小的元素在最后面。通常，無法預先知道各個元素的查找概率，解決的辦法是為用檢索成功次數代替查找概率，當檢索元素成功時，其檢索成功次數加1，保持檢索成功次數最大的元素在前面，檢索成功次數最小的元素在最后面。Rs……Cmax…Cmin現在是18頁\一共有102頁\編輯于星期六(5)順序檢索的優缺點：

優點：算法簡單，適應面廣，對字典結構無要求，無論是否按關鍵碼有序，適用于順序表和鏈表。

缺點：ASL長，O(n)數量級，大約一半元素個數的比較次數?，F在是19頁\一共有102頁\編輯于星期六3.二分法檢索（折半檢索）（1）思想：當字典按關鍵碼有序時，將字典元素按關鍵碼從小到大保存在數組中。首先給定值key與字典的中間位置元素進行比較，如果相等，則檢索成功；否則根據key與中間位置元素的關鍵碼的比較確定在左邊進行繼續查找，還是在右邊繼續查找。如key小，則在左邊繼續進行二分法檢索，否則，在右邊繼續二分法檢索。從上面可以看出，折半檢索的實質是逐步縮小查找區間的檢索方法。<=>現在是20頁\一共有102頁\編輯于星期六

例如給定值key=25和78的檢索：

01234567891005，10，18，25，27，32，41，51，68，73，99

05，10，18，25，2741，51，68，73，9925，2773，9999成功失敗需要指定搜索區間。對于順序表：[低界，高界]現在是21頁\一共有102頁\編輯于星期六（2）算法intBinSearch(SeqDictionary*pdic,KeyTypekey,int*pos){intlow,mid,high;low=0;high=pdic->n-1; /*初始搜索區間*/while(low<=high){

mid=(low+hight)/2;/*中間位置*/if(key==pdic->element[mid].key)/*查找成功*/{*pos=mid;returnTRUE;}elseif(key<pdic->element[mid].key){high=mid-1;}/*左邊區間繼續*/else{low=mid+1;}/*右邊區間繼續*/}*pos=low;returnFALSE;/*查找失敗*/}現在是22頁\一共有102頁\編輯于星期六（3）時間效率分析每比較一次縮小一半的查找區間。為了分析折半檢索的性能，可以用二叉樹來描述折半檢索的過程。當前檢索區間中間記錄作為根，左半區間和右半區間中的記錄分別為根的左子樹和右子樹，這樣得到的二叉樹稱為折半檢索二叉樹。樹中結點數字表示結點在有序表中的位置。536092810714右圖為11個記錄的折半檢索二叉樹。如要檢索第6個記錄，則只需要一次比較；檢索第3、9個記錄需要2次比較；檢索第1、4、7、10個記錄需要3次比較；檢索第2、5、8、11個記錄需要4次比較?，F在是23頁\一共有102頁\編輯于星期六536092810714由此可見，折半檢索的過程恰好是在判定樹中走了一條從根到檢索結點的路徑，比較的關鍵碼個數恰為該結點在二叉樹中的層數。因此，成功折半檢索關鍵碼比較次數不會超過樹的深度：那么，折半檢索的ASL等于多少？現在是24頁\一共有102頁\編輯于星期六假定記錄數n=2h-1，即h=log2(n+1)，則描述折半檢索的判定樹是一棵深度為h的全滿二叉樹。在該全滿二叉判定樹中，有：

第1層的結點個數為20，比較1次；

第2層的結點個數為21，比較2次；

……

第k層的結點個數為2k-1，比較k次；

……

第h層的結點個數為2h-1，比較h次；等概率檢索下，檢索成功時的當n很大時，如n>100，則得到:ASL≈log2(n+1)-1現在是25頁\一共有102頁\編輯于星期六由此可見，折半檢索的效率要高于順序檢索。如n=1000，順序ASL=500，而折半ASL≈9。（4）優缺點

優點：檢索效率高，ASL≈log2(n+1)-1缺點：只適用于數據元素很少變動的有序順序表，應用范圍有限制。現在是26頁\一共有102頁\編輯于星期六每行中：列按照經度有序每列中：行按照緯度有序經度數組緯度數組問題描述：地球觀測網格點m行m列，網格點經緯度位置分別存儲在經度數組和緯度數組中。對于經度數組，各行按照列經度有序；對于緯度數組，各列按照行緯度有序。算法設計：給定一個經緯度值（lon,lat），檢索最近網格點的行列坐標。

voidgeo2grid(floatlon,floatlat,int*gx,int*gy);------雙折半實現，速度較順序檢索，大大提高。順序：m2/2,雙折半：(log2(m+1)-1)2,分區雙折半：(log2(m/2+1)-1)2。如：m=2000,ASL≈【2000000,100,82(81+1)】現在是27頁\一共有102頁\編輯于星期六經度數組(每行中：經度有序)MidYTopBottomLeftRightMidXvoidgeo2grid(floatlon,floatlat,int*gx,int*gy){inttop=0,bottom=rows-1,midy;intleft,right,midx;while(top<=bottom) //緯度控制的行折半檢索

{midy=(top+bottom)/2;//中間行

left=0,right=cols-1;//在中間行中折半經度檢索

while(left<=right){midx=(left+right)/2;//中間列

if(lon==lons[midy][midx])break;//找到列

elseif(lon<lons[midy][midx])right=midx-1;elseleft=midx+1;}if(lat==lats[midy][midx])break;//成功

elseif(lat<lats[midy][midx])bottom=midy-1;elsetop=midy+1;}*ix=midx;*iy=midy;//近似解}進一步改進:(lon,lat)先與中心點經緯度進行比較，確定在那個1/4區域，再在該區域內雙折半檢索?，F在是28頁\一共有102頁\編輯于星期六4.分塊檢索(BlockingSearch)（1）數據元素排列又稱索引順序檢索，是介于順序、折半之間的檢索方法。

分塊檢索要求所有的記錄分成若干塊，并且塊間按關鍵碼有序，而塊內不一定有序。即：第一塊中所有記錄的關鍵碼均不超過第二塊中任意記錄的關鍵碼，而第二塊中所有記錄的關鍵碼均不超過第三塊中任意記錄的關鍵碼，……，塊內記錄可以任意排列。這樣，可以建立一個塊索引表，存儲每塊的最大關鍵碼值以及該塊第一個元素在字典中的位置?，F在是29頁\一共有102頁\編輯于星期六塊索引表數據元素結構：字典：(27,13,8,9,12,5,6,35,43,38,47,59,58,79,82,52)最大關鍵碼值第一個記錄的位置2704778211塊索引表最小關鍵碼值最后一個記錄的位置5635105215現在是30頁\一共有102頁\編輯于星期六（2）檢索思想給定值key,首先在塊索引表中進行檢索確定下一步要檢索的塊，然后到確定的塊中進行檢索。由于塊索引表按關鍵碼有序，因此塊間檢索可以采用折半檢索，也可以采用順序檢索。但由于塊內記錄無序，任意排列，只能采用順序檢索。由此可以看出，分塊檢索有兩步組成：塊間檢索和塊內檢索。如上例中檢索key=38，首先在塊索引表中檢索發現在第二塊，然后在第二塊中順序檢索，得到記錄是第二塊的第三個記錄（總的字典位置為7+2)。又如key=15，有塊索引表得到如果記錄存在，必定在第一塊。在第一塊中順序檢索失敗，因此字典中不存在這樣的記錄，分塊檢索失敗?，F在是31頁\一共有102頁\編輯于星期六（3）檢索算法

索引表結構

typedefstruct{KeyTypemaxkey;/*塊中最大關鍵字*/intpos_1rec;/*塊的第一個元素的位置*/}IndexNode;

typedefstruct{IndexNodeidx_block[MAXNUM];/*塊索引表*/intnum_block;/*實際塊數*/}*Pindex;現在是32頁\一共有102頁\編輯于星期六intBlockSearch(SeqDictionary*pdic,Pindexidx,KeyTypekey,int*pos){inti=0,j,last_j;

//在塊索引表中確定塊

while(i<idx->num_block&&key>idx->idx_block[i].maxkey)i++;if(i>idx->num_block)*pos=-1;//塊間檢索失敗

else{//塊內順序檢索，確定檢索范圍

j=idx->idx_block[i].pos_1rec;//起始記錄

if(i==idx->num_block)last_j=pdic->n-1;//終止記錄

elselast_j=idx->idx_block[i+1].pos_1rec-1;while(j<=last_j&&key!=pdic->element[j].key)j++;if(j>last_j) *pos=-1;//塊內檢索失敗

else*pos=j;//檢索成功

}現在是33頁\一共有102頁\編輯于星期六

//檢索成功或失敗

if(*pos>-1)returnTRUE;elsereturnFALSE;}（4）檢索效率

ASLbs=Lb+Lw

其中，Lb為塊間檢索的ASL，Lw為塊內檢索的ASL假定總共有n個記錄，分成b塊，每塊含有s個記錄，即s=n/b。假定塊間檢索為等概率：1/b，塊內檢索仍然等概率：1/s。根據塊間檢索方法不同，ASL計算不同?，F在是34頁\一共有102頁\編輯于星期六

塊間順序檢索

Lb=(b+1)/2Lw=(s+1)/2ASL=(b+s)/2+1=(n/s+s)/2+1由此可見，ASL不僅與n有關，而且與每塊記錄數目s有關。對上式ASL求導，可以得到當時，ASL取最小值。

如：n=1000時，，ASL≈32

順序檢索：ASL≈500

折半檢索：ASL≈9

因此，分塊檢索介于順序、折半檢索之間。塊間折半檢索

ASL=log2(n/s+1)-1+(s+1)/2≈log2(n/s+1)+s/2現在是35頁\一共有102頁\編輯于星期六現在是36頁\一共有102頁\編輯于星期六開始掃描角度終止掃描角度Nintfind_bin(floatazim){intsi,ei,mi;if(azim>=a[0]){si=0;ei=i_max;}else{si=i_min,ei=n-1;}while(si<=ei){mi=(si+ei)/2;if(azim==a[mi])returnmi;elseif(azim<a[mi])ei=mi-1;elsesi=mi+1;}returnmi;}雷達掃描形成方位角序列：a0,a1,a2,….,359.88,0.01,…,a0-0.1分成兩塊：

a0,a1,a2,….,359.880.01,…,a0-0.1i_maxi_min0n-1塊間有序、塊內有序的分塊檢索應用現在是37頁\一共有102頁\編輯于星期六索引存儲結構及其檢索：1）密集索引:每個元素一個索引順序表鏈表k1k2…knd11…d1nd21…d2ndk1…dkn順序表索引d11…d1kd21…d2kdn1…dnk^…H索引k1k2…kn鏈表…現在是38頁\一共有102頁\編輯于星期六2）稀疏索引[分塊索引]

多個元素一個索引順序表鏈表d1.1…d1.md2.1…d2.m………db1.1…db1.m順序表索引…………H索引kmin1kmin2…kminb鏈表kmin1pos1kmin2pos2….….kminbposb………塊1塊2現在是39頁\一共有102頁\編輯于星期六6.4散列表檢索思想與基本概念前面的檢索方法都是通過給定值與關鍵碼的比較才能確定記錄位置，檢索效率與檢索過程中進行的比較次數有關。本節介紹的Hash表檢索是一種基于“盡可能不通過比較操作而直接得到記錄的存儲位置”的想法而提出來的檢索方法。其基本思想是以記錄關鍵碼key為自變量，通過某種確定的函數h(key)計算的函數值作為存儲地址，將該記錄（或記錄的關鍵碼）存放到該位置上。 檢索時仍然需要h(key)計算得到關鍵碼所在記錄的存儲地址。顯然，按照這種思路可以不需要比較運算就能直接確定記錄?，F在是40頁\一共有102頁\編輯于星期六散列函數（哈希函數）：h(key)散列地址（哈希地址）：h(key)的值散列表（哈希表）：通過h(key)建立起來的線性表，稱為Hash表

到目前為止，已經接觸了四種存儲結構：

順序、鏈接、索引、散列。 給定一個散列函數h，可能出現兩個或多個不同的關鍵碼具有相同的散列地址，稱這些不同的關鍵碼為“同義詞”，而這種現象稱為“碰撞”。 對于任意的散列函數，都可能出現“碰撞”現象。因此，如何選擇合適的散列函數減少碰撞發生是Hash表構造中的一個關鍵問題?，F在是41頁\一共有102頁\編輯于星期六通過散列函數得到的散列地址空間稱為“基本區域”，發生碰撞時，同義詞可以放在基本區域中未被占用的空間，也可以放到基本區域以外另開辟的區域（溢出區）。負載因子：當α>1時，碰撞不可避免。由此可以看出，散列表的構造和檢索中，需要解決的主要問題有：（1）如何選擇合適的散列函數構造散列表？（2）碰撞發生時如何處理？（3）散列表如何檢索？檢索效率如何？檢索效率與那些因素有關？現在是42頁\一共有102頁\編輯于星期六2.散列函數的選擇散列函數的選擇在散列表的構造和檢索中是非常重要的，合適的散列函數可以減少碰撞的發生，提高檢索效率。散列函數的選擇標準：字典中的關鍵碼均勻分布在散列地址空間中，減少碰撞的發生；散列函數盡可能簡單，提高計算速度。常用的散列函數：（1）直接定址法

h(key)=a*key+b適用于關鍵碼分布基本連續情況。若關鍵碼分布不連續，容易造成空單元，存儲空間浪費?，F在是43頁\一共有102頁\編輯于星期六（2）除留余數法

h(key)=key%pp的選擇非常重要，通常選擇小于等于散列表長度m的某個最大素數。如：m=600，則p可以選擇為599。除留余數法計算簡單，許多情況下效果較好，是一種常用的散列函數。（3）數字分析法對關鍵碼的數字位進行分析，然后用其中的某些較分散的數字位構成散列函數。通常用于已知記錄關鍵碼，并且關鍵碼各位分布已經知道的情況。例如：(395003,395010,395012,395085,395097)中，前四位相同，后兩位隨機分布，故可以取后兩位構成散列函數，得到的散列地址為（03，10，12，85，97）現在是44頁\一共有102頁\編輯于星期六（4）折疊法如果關鍵碼的位數多于地址位數，且各位分布均勻，此時可以將關鍵碼分成若干塊，塊長度不超過地址位數。各塊相加，舍棄進位，最后的和作為散列地址。

如：key=0582422241，地址位數為4。

2241224182422428+)05+)05[1]04884672移動疊加間界疊加現在是45頁\一共有102頁\編輯于星期六（5）平方取中法先求出關鍵碼的平方，然后取中間若干位構成散列函數。例如：key=4731，key2=22382361，如地址碼為3位，則可以取382為散列地址，即h(4731)=382（6）基數轉換法將關鍵碼首先看作是另一進制的表示，然后再轉換為原來的進制數，用數字分析法取若干位作為散列地址。一般轉換基數大于原基數，且最好二者互素。例如：key=(236075)10,把它看作13進制數(236075)13,再轉換為10進制，地址位數為4：

(236075)13=2*135+3*134+6*133+7*131+5=(841547)10

選擇2~5，得到散列地址h(236075)=4154現在是46頁\一共有102頁\編輯于星期六

上面為常用的散列函數選擇，實際情況應該根據問題的要求選擇適合散列表構造和檢索的散列函數。從上面的散列函數選擇可以看出，無論選擇何種散列函數，碰撞都可能發生。換句話講，合適的散列函數可以減少碰撞發生的幾率，但不能保證不發生碰撞。碰撞發生時如何處理？？現在是47頁\一共有102頁\編輯于星期六3.碰撞的處理（開放地址法，拉鏈法）開放地址法（基本區域內解決)

假定散列表地址空間為[0，m-1]，碰撞指的是由關鍵碼得到的散列地址為j(0≤j≤m-1)的位置上已經存在記錄，則處理碰撞就是為該關鍵碼找到一個空的散列地址。找到該空的散列地址可能需要經過一個地址序列Hi(i=0,1,2,…,k)，即在處理碰撞時，如果得到的散列地址H1仍然沖突，則再求下一個地址H2，如H2沖突，再求H3，…，直到Hk不發生沖突為止。

Hi=(H(key)+di)%m(i=1,2,…,k[k≤m-1])

其中，H(key)為散列函數，

m為散列表長度，

di為增量序列。?????H1H2H3Hk現在是48頁\一共有102頁\編輯于星期六線性探測容易出現不同的關鍵碼爭奪同一個散列地址問題，這種現象稱為“二次聚集[堆積]”。例如：長度為11的散列表已填有關鍵碼分別為17，60，29的記錄[散列函數h(key)=key%11]，現第4個記錄的關鍵碼為38，由散列函數得到其散列地址為5，由于該地址已經存放關鍵碼為60的記錄，產生沖突。如何尋找下一個空的地址？601729012345678910 [a]線性探測：di=1,2,3,…,m-1di有下面三種形式：

[b]平方探測：di=12,-12,22,-22,…,k2,-k2(k≤m/2) [c]隨機探測：di=偽隨機數序列現在是49頁\一共有102頁\編輯于星期六

按照線性探測得到下一個地址為6，仍然沖突，繼續探測得到下一個地址為7，仍然沖突，再繼續探測下一個地址為8，該地址為空，因此將關鍵碼為38的記錄存放在地址為8的單元。如果按照平方探測方法，則得到地址為4的空地址用于存放關鍵碼為38的記錄。如果按照隨機探測方法，則得到地址為3的空地址用于存放關鍵碼為38的記錄。在線性探測中可以發現，當表中i、i+1、i+2位置上已填有記錄時，散列地址為i、i+1、i+2、i+3的記錄都將填入i+3的位置上，此時出現“二次聚集[堆積]”問題。這不利于查找。但是，當散列表未滿時總可以找到一個空單元。平方探測和隨機探測不能保證一定能找到下一個空單元。601729601729601729601729383838012345678910現在是50頁\一共有102頁\編輯于星期六

再散列:當發生碰撞時，Hi的計算可以采用其它的散列函數得到。

Hi=Rhi(key),i=0,1,2,…,k(2)拉鏈法（溢出區內解決）將所有關鍵碼為同義詞的記錄存儲在同一個線性鏈表中。假定由散列函數得到的散列地址空間為[0，m-1]，則可以建立一個指針向量：ChainChainHash[m]其初始狀態皆為空指針。散列地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。鏈表中記錄排列可以是任意的，也可以按照關鍵碼有序。如:(8,13,3,6,10),H(key)=key%7^8361310^^^0123456現在是51頁\一共有102頁\編輯于星期六4.散列表的建立與檢索

散列表的建立與檢索是通過相同的散列函數進行的，并且當出現碰撞時應采用相同的解決碰撞的方法。對于給定關鍵碼值key，計算H(key)，得到散列地址。

對于散列表的建立，如果該散列地址對應的單元為空，表明沒有沖突，直接將記錄插入；否則如果該散列地址對應的單元非空，表明該單元已經被前面的記錄占用，出現碰撞問題。此時，需要按照解決碰撞的方法進行處理[如果采用開放地址法，則按照一定的序列尋找下一個空單元；如果是采用拉練法，則在碰撞地址對應的同義詞鏈表中完成插入]?，F在是52頁\一共有102頁\編輯于星期六

對于散列表的檢索，如果該散列地址對應的單元（或指針）為空，表明檢索失敗；否則:(1)如果散列表是采用開放地址法解決碰撞建立的，那么給定值key與該單元存儲的記錄的關鍵碼進行比較。如果相等，表明檢索成功；否則按照散列表建立時尋找下一個單元的序列尋找下一個地址，如此反復進行，直到關鍵碼比較相等（檢索成功）或找到空單元（檢索失敗）為止；

(2)如果散列表是采用拉練法解決碰撞建立的，那么沿著該非空指針進入同義詞單鏈表，在該鏈表中進行檢索。如果找到某個結點的存儲記錄的關鍵碼與給定值key相同，檢索成功；否則，檢索失敗?，F在是53頁\一共有102頁\編輯于星期六//開放地址法，散列表結構定義：typedefstruct{DicElementelement[REGION_LEN];intm; /*m=REGION_LEN,基本區域長度*/}HashDictionary;現在是54頁\一共有102頁\編輯于星期六//使用開放地址法中的線性探測方法解決碰撞的散列表檢索intLinearSearch(HashDictionary*phash,KeyTypekey,int*pos){intd,inc;d=H(key);//計算散列地址

for(inc=0;inc<phash->m;inc++){if(phash->element[d].key==key)//檢索成功

{*pos=d;returnTRUE;}elseif(phash->element[d].key==NIL)

//檢索失敗，找到插入位置

{*pos=d;returnFALSE;}d=(d+1)%phash->m;//采用線性探測找下一個探測地址

}*pos=-1;returnFALSE;//散列表溢出}現在是55頁\一共有102頁\編輯于星期六//使用開放地址法中的線性探測方法解決碰撞的散列表建立intLinearInsert(HashDictionary*phash,KeyTypekey){intpos;if(LinearSearch(phash,key,&pos)==TRUE)printf(“找到相同的記錄！\n”);

//散列表中已經存在關鍵碼為key的記錄，不能再插入

elseif(pos!=-1)phash->element[pos].key=key;//插入記錄

elsereturnFALSE;//散列表溢出

returnTRUE;}現在是56頁\一共有102頁\編輯于星期六5.檢索效率分析從散列表的檢索過程可以發現：（1）雖然散列表在關鍵碼與記錄的存儲位置之間建立了直接映象，但由于“碰撞”的產生，使得散列表的檢索過程仍然是一個給定值和記錄關鍵碼進行比較的過程。因此，仍需要以平均查找長度作為衡量散列表查找效率的度量。（2）查找過程中需和關鍵碼進行比較的次數取決于下列三個因素：散列函數處理碰撞的方法裝填因子

散列函數的“好壞”首先影響出現沖突的頻率。對于同一組隨機的關鍵碼，“均勻分布”的散列函數產生碰撞的可能性相同，則可不考慮它對ASL的影響?，F在是57頁\一共有102頁\編輯于星期六對同樣一組關鍵碼，相同的散列函數，但不同的碰撞處理方法得到的散列表不一樣，其ASL也必然不同，通常拉鏈法的ASL要小于開放地址法。線性探測容易產生“二次聚集[堆積]”問題，而拉鏈法不會出現這種情況。

另外，處理碰撞相同的散列表，其ASL依賴于散列表的裝填因子。裝填因子表示散列表的裝滿程度。裝填因子越小，發生碰撞的可能性越??；反之，裝填因子越大，表中已填入的記錄多，再填記錄時，發生碰撞的可能性就越大，檢索時比較次數就越多。現在是58頁\一共有102頁\編輯于星期六在“開放地址法”處理碰撞時，刪除的元素需要特別標注，否則今后會出現檢索錯誤。例如：散列函數key%116.散列表的刪除5166刪除5后，再檢索16：失敗！166特殊標志，如-1-1166檢索時，碰到-1，繼續按照找空單元的方法檢索下一單元。插入時，碰到-1，與空單元一樣處理【可以插入】現在是59頁\一共有102頁\編輯于星期六6.5樹表的檢索折半檢索效率高，但只適合于有序的順序表。順序表中插入、刪除結點需要數據元素移動，效率低。能否找到一種既能把鏈式存儲結構的優點與折半檢索高效率結合，并且又不要求有序表的檢索方法？樹表：二叉排序樹、平衡二叉排序樹（AVL樹）、B樹二叉排序樹（1）定義：或者是一棵空二叉樹；或者具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左右子樹也分別為二叉排序樹。1810057368272599413251K={18,73,10,05,68,99,27,41,51,32,25}現在是60頁\一共有102頁\編輯于星期六字典的二叉排序樹索引1810057368272599413251字典的二叉排序樹表示二叉排序樹D1D2…Dn現在是61頁\一共有102頁\編輯于星期六（2）為什么二叉排序樹是動態字典的合適表達？無序序列構造得到二叉排序樹，然后中序遍歷，得到一個有序的序列。字典的檢索效率非常高。另外，二叉排序樹插入、刪除結點都非常方便。因此二叉排序樹是動態字典的合適表達。（3）檢索思想首先根據無序序列的先后順序，構造二叉排序樹。然后根據二叉排序樹的定義進行檢索:

若二叉排序樹為空樹，檢索失?。环駝t，如給定值key等于二叉排序樹的根結點的關鍵字，則檢索成功；如給定值key小于二叉排序樹的根結點的關鍵字，則說明待檢索記錄只可能在左子樹中，繼續在左子樹檢索；如給定值key大于二叉排序樹的根結點的關鍵字，則說明待檢索記錄只可能在右子樹中，繼續在右子樹檢索；與折半相似縮小區間搜索=<>現在是62頁\一共有102頁\編輯于星期六（4）二叉排序樹結構描述與檢索算法typedefstructBinNode{ KeyType key; /*結點的關鍵碼字段*/ DataType other; /*結點的屬性字段*/ structBinNode*llink; /*二叉樹的左指針*/ structBinNode*rlink; /*二叉樹的右指針*/}BinTreeNode,*PBinTreeNode,BinTree,*PBinTree;1810057368272599413251pq現在是63頁\一共有102頁\編輯于星期六intSearchNode(PBinTreeptree,KeyTypekey,PBinTreeNodepos){PBinTreeNodep,q;p=ptree;q=p;while(!p){ q=p; //q指向父結點位置

if(p->key==key) {pos=p; return(TRUE);} //檢索成功

elseif(p->key>key) p=p->llink; //進入左子樹

else p=p->rlink; //進入右子樹

}pos=q; //檢索失敗

return(FALSE);}現在是64頁\一共有102頁\編輯于星期六（5）二叉排序樹的插入與構造插入新的結點后，必須保證插入后仍然滿足二叉排序樹的性質。

插入新結點的方法∶如果二叉排序樹為空，則新結點作為根結點。如果二叉排序樹非空，則將新結點的關鍵碼與根結點的關鍵碼比較，若小于根結點的關鍵碼，則將新結點插入到根結點的左子樹中；否則，插入到右子樹中。子樹中的插入過程和樹中的插入過程相同，如此進行下去，直到找到該結點，或者直到新結點成為葉子結點為止。如插入70，二叉排序樹形式如右圖。181005736827259941325170現在是65頁\一共有102頁\編輯于星期六voidInsertNode(PBinTreeptree,KeyTypekey){PBinTreeNodep,q;if(SearchNode(ptree,key,q)==TRUE) { return;} //已經存在關鍵碼為key的結點

//q返回插入位置

p=(PBinTreeNode)malloc(sizeof(structBinTreeNode));if(p==NULL) //內存申請錯誤*/{ printf(“MemoryallocatedError!\n”);exit(1);}p->key=key;p->llink=p->rlink=NULL;if(q==NULL) //空樹插入，直接為根

ptree=p;elseif(key<q->key) //插入為q的左子樹

q->llink=p;else //插入為q的右子樹

q->rlink=p;}現在是66頁\一共有102頁\編輯于星期六二叉排序樹的構造：從空樹開始，將元素逐個插入到二叉排序樹中。voidCreateTree(PBinTreeptree,SeqDictionarydic){inti;for(i=0;i<dic.n;i++)InsertNode(ptree,dic.element[i].key);}K={20,99,88,50,10}992088501020992088992050889920二叉樹的形態與關鍵碼序列有關。n個記錄，n!種形態，那種檢索效率最高？現在是67頁\一共有102頁\編輯于星期六（5）二叉排序樹的刪除刪除結點后，仍然滿足二叉排序樹的性質。…Lroot…LlastPR…

方法1∶

如果被刪除結點p沒有左子樹，則用p的右子女代替p即可。否則，在p的左子樹中，中序遍歷找出最后一個結點r(r一定無右子女)，將r的右指針指向p的右子女，用p的左子女代替p結點。Lrootr=LlastrRRLrootpp現在是68頁\一共有102頁\編輯于星期六

方法2∶

如果被刪除結點p沒有左子樹，則用p的右子女代替p即可；否則，在p的左子樹中，中序遍歷找出最后一個結點r（r一定無右子女），用r結點代替被刪除的結點p，用r的左子女代替r結點。rRRLrootLrootr=Llastpp現在是69頁\一共有102頁\編輯于星期六18100573272599413251刪除key=73結點中序遍歷左子樹最后結點，其關鍵字最大4518100527259941325145方法118100527259941325145方法2現在是70頁\一共有102頁\編輯于星期六方法1算法：voidDeleteNode(PBinTreeptree,KeyTypekey){PBinTreeNodeparentp,p,r;p=ptree;parentp=NULL;while(p!=NULL) //找關鍵碼為key的結點

{ if(p->key==key)break; parentp=p; //保存其父結點

if(p->key>key)p=p->llink; //進入左子樹

elsep=p->rlink; //進入右子樹

}if(p==NULL)return; //無關鍵碼為key的結點

if(p->llink==NULL) //結點p無左子樹

{if(parentp==NULL)ptree=p->rlink; //p為根

elseif(parentp->llink==p) parentp->llink=p->rlink; //左

elseparentp->rlink=p->rlink; //右

}現在是71頁\一共有102頁\編輯于星期六

else //結點p有左子樹

{r=p->llink; //在p的左子樹中找最右下結點rwhile(r->rlink!=NULL)r=r->rlink;r->rlink=p->rlink; //用r的右指針指向p的右孩子

//用p的左孩子代替pif(parentp==NULL) ptree=p->llink; //p為根

elseif(parentp->llink==p) parentp->llink=p->llink;//左

else parentp->rlink=p->llink;//右

}//刪除pfree(p);}現在是72頁\一共有102頁\編輯于星期六給定一組n個記錄的記錄序列（無序），構造的二叉排序樹有n!種形態，各種形態的查找效率不相同。如何構造高效率的二叉排序樹？等概率：折半檢索的二叉判定樹或平衡二叉樹（AVL樹）不等概率：構造最佳二叉排序樹或次優查找樹二叉判定樹構造：

1）記錄序列按照關鍵碼排序；

2）按照關鍵碼的折半檢索次序，在二叉排序樹中加入記錄。27，73，10，5，18，41，99，51，255，10，18，25，27，41，51，73，9927105185141732599現在是73頁\一共有102頁\編輯于星期六2.平衡二叉排序樹（AVL樹）對于一棵二叉排序樹，其檢索效率取決于樹的形態，而構造一棵形態均稱的二叉排序樹與結點的輸入順序有關。因此，為了保證高效率檢索就必須對構造的二叉排序樹進行動態平衡，使得其形態均稱。平衡二叉樹：又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左右子樹均為平衡二叉樹，且左右子樹的深度之差的絕對值不超過1。平衡因子(BalanceFactor)：結點的右子樹的深度減去左子樹的深度。對于AVL樹，各個結點的BF值只可能為-1,0,1?，F在是74頁\一共有102頁\編輯于星期六

構造過程中，每插入一個新的結點，都需要判斷是否破壞了原來的平衡條件。如果破壞，需要進行平衡處理。平衡二叉樹在插入一個新結點后，可能出現三種情況：新結點插入后不影響其父結點為根的子樹深度，則不會破壞整個二叉排序樹的平衡；父結點為根的子樹深度增加了，但在其祖先的某一層上不再影響子樹的深度，則整個二叉排序樹仍然是平衡的；父結點為根的子樹深度增加，且在其祖先的某一層上破壞了平衡的要求，使整個二叉排序樹不再平衡。現在是75頁\一共有102頁\編輯于星期六首先找出最小不平衡子樹，在保證排序樹性質的前提下，調整最小不平衡子樹中各結點的連接關系，以達到新的平衡。最小不平衡子樹：離插入結點最近，平衡因子絕對值大于1的結點為根的子樹假設最小不平衡子樹的根結點為A，根據新插入結點的位置，調整子樹的操作可歸納為以下四種情況：

LL（A的左子女[L]的左子樹[L]上插入新結點）[-1to-2]LR（A的左子女[L]的右子樹[R]上插入新結點）[-1to-2]

RL（A的右子女[R]的左子樹[L]上插入新結點）[1to2]RR（A的右子女[R]的右子樹[R]上插入新結點）[1to2]失去平衡后的處理方法：ANLRANLRANLRANLR現在是76頁\一共有102頁\編輯于星期六

AAB

B

B

A

γ

hγ

h

h+1α

h

αhβ

h+1

α

hβ

h

β

γh-10-2-100LL型調整操作示意圖：(αBβ)A(γ)=(α)B(βAγ)調整規則是∶將A的左子女B提升為新二叉樹的根；原來的根A連同其右子樹向右下旋轉成為B的右子樹；

B的原右子樹β作為A的左子樹。

（1）LL型調整現在是77頁\一共有102頁\編輯于星期六AA

B

B

BA

αh

α

h

h+1γ

h

βhγh

β

h+1γ

h

α

βh100021RR型調整操作示意圖：(α)A(βBγ)=(αAβ)B(γ)調整規則：將A的右子女B提升為新二叉樹的根；原來的根A連同其左子樹向左下旋轉成為B的左子樹；

B的原左子樹作為A的右子樹。（2）RR型調整現在是78頁\一共有102頁\編輯于星期六（3）LR型調整AACBBBAδ

hδ

hCCh

αh

αh

α

βhγh-1δhh-1βγ

h-1hβ

γh-1-1

-2010100-1CLR型調整操作示意圖： ((α)B(βCγ))A(δ)=(αBβ)C(γAδ)調整規則∶設C為A的左子女B的右子女，將A的孫子結點C提升為新二叉樹的根；原C的父結點B連同其左子樹α向左下旋轉成為新根C的左子樹，原C的左子樹β成為B的右子樹；原根A連同其右子樹δ向右下旋轉成為新根C的右子樹，原C的右子樹γ成為A的左子樹?，F在是79頁\一共有102頁\編輯于星期六AACBBABhα

hα

δCC

δh

δh

h

α

βhγ

h-1δhh-1β

γh-1hβ

γh-1010010-12-1(4)RL型調整RL型調整操作示意圖：(α)A((βCγ)B(δ))=(αAβ)C(γBδ)調整規則：設C為A的右子女B的左子女，將A的孫子結點C提升為新二叉樹的根；原來C的父結點B連同其右子樹δ向右下旋轉成為新根C的右子樹，C的原右子樹γ成為B的左子樹；原來的根A連同其左子樹α向左下旋轉成為新根C的左子樹，原來C的左子樹β成為A的右子樹?，F在是80頁\一共有102頁\編輯于星期六結點插入算法的關鍵部分：新結點插入導致失去平衡，需找最小不平衡子樹。令A始終指向離插入位置最近、且平衡因子不為零的結點，若新結點插入后失去平衡，則A是最小不平衡子樹的根。新結點插入后，修改一些結點的平衡因子。判別以A為根的子樹是否失去了平衡。失去平衡后，按照四種類型之一調整。現在是81頁\一共有102頁\編輯于星期六AVL樹的結點結構：typedefstructAVLNode{ KeyType key; /*結點的關鍵碼*/ DataType other; /*結點的其它信息*/ int bf; /*結點的平衡因子*/ structAVLNode*llink, /*指向結點的左子女*/ structAVLNode*rlink; /*指向結點的右子女*/}AVLNode,*PAVLNode,AVLTree,*PAVLTree;下面只討論四種調整，有關AVL樹的檢索與插入算法見教材p229~232，希望大家課后閱讀，時間效率分析O(log2n)?，F在是82頁\一共有102頁\編輯于星期六PAVLNodeLL(PAVLNodea){ PAVLNode b=a->llink; a->bf=0; a->llink=b->rlink; b->bf=0; b->rlink=a; return(b); //b指向調整后的子樹的根結點}PAVLNodeRR(PAVLNodea){ PAVLNod