第九章 查找表課件教學

第九章查找表9.1靜態(tài)查找表9.2動態(tài)查找表9.3哈希表及其查找查找表：由同一類元素或記錄構成的集合。對數(shù)據(jù)元素間的關系未作限定。對查找表的操作有查找某個“特定”的元素是否在表中。查找某個“特點”的元素的各種屬性。在查找表中插入一個元素。在查找表中刪除一個元素靜態(tài)查找表、動態(tài)查找表關鍵字數(shù)據(jù)元素中的某個數(shù)據(jù)項值。可以表示一個數(shù)據(jù)元素，如可以唯一表示，則為主關鍵字（primarykey）。查找根據(jù)給定的某個值，在查找表中確定一個關鍵字等于給定值的數(shù)據(jù)元素。若找到表示查找成功，返回該元素詳細信息或在查找表中的位置；否則返回NULL

9.1靜態(tài)查找表9.1.1順序查找

typdefstruct{ ElemType*elem;//元素存儲空間，0單元保留 int length;//表長度}SSTable;查找成功和失敗

平均查找長度查找過程中先后和給定值進行比較的關鍵字的個數(shù)的期望值ASL＝∑PiCi∑Pi＝1i＝1，2，……nCi＝n－i＋1Pi＝1/nASLss＝1/n∑（n－i＋1）=(n+1)/2

9.1.2折半查找

折半查找（binarySearch）：二分查找。例8.2利用二分查找在順序有序表中查找。算法8.2IntSearch_Bin(SStableST,KeyTypekval)ASLbs＝（n＋1）/nlog(n+1)-1

二分查找平均查找長度（假設滿二叉樹）ASLbs＝（n＋1）/nlog(n+1)-1ASLbs=(20+21*2+…+2h-1*h)Pi=

又稱索引順序查找介于順序查和折半查找之間。適合于關鍵字分塊有序typedefstruct{ KeyType key; int stadr;}indexItem;typedefstruct{ indexItem *elem; int length;}indexTable;算法Search_Idx(SSTableST,indexTableID,KeyTkval)設索引長度b，順序表長度為n，則：ASLidx=ASL(b)+ASL(n/b)≈log2(b+1)-1+(n/b+1)/29.1.3分塊查找9.2動態(tài)查找表ADTDynamicSearchTable{ 數(shù)據(jù)對象：D是具有相同特性的元素集合。 數(shù)據(jù)關系：同屬集合關系。

基本操作：InitDSTable（&DT）DestroyDSTable（&DT）SearchDSTable（DT，kval）InsertDSTable（&DT,e）*DeleteDSTable（&DT,kval）*TraverseDSTable（DT,Visit()）}ADTDynamicSearchTable;9.2.1二叉查找樹查找樹、二叉查找樹通過和根結點的關鍵字進行比較可以將繼續(xù)查找的范圍縮小到某一顆子樹中，具有該特性的樹稱查找樹。二叉查找樹又稱二叉排序樹。例:二叉查找樹的查詢過程。StatusSearch_BST(BiTreeT,KeyTypekval,BiTreef,BiTree&p)例:二叉查找樹的插入算法StatusInsert_BST(BiTree&T,ElemTypee)刪除結點的處理方法

1)若是葉子結點，直接刪除2)只有一個孩子，則將其孩子直接掛到其雙親上。3)有兩個孩子，找左孩子中最大的一個元素，代替被刪除結點，最大元素肯定只有一個孩子，按2）處理刪除最大元素StatusDelete_BST(BiTree&T,KeyTypekval)二叉查找樹的平均查找長度p（n）＝2（n＋1）/n*logn+C

二叉平衡（查找）樹

樹中每個結點的左、右子樹深度之差的絕對值不大于1，這種平衡狀態(tài)的二叉查找樹。實現(xiàn)方法：平衡旋轉技術9.2.2B樹和B+樹B樹：每個結點n個關鍵字，n+1個指針 m階B樹除根和葉子外，每個結點子樹在[m/2,m]B+樹:每個結點n個關鍵字，n個指針m階B+樹除根和葉子外，每個結點子樹在[m/2,m]9.2.3鍵樹鍵樹、數(shù)字查找樹（Digitalsearchtrees）結點不是關鍵字，而是關鍵字中的一個字符,從根到葉子結點的路徑（根、葉子本身除外）才是關鍵字鍵樹的存儲（雙鏈樹）采用孩子－兄弟的存儲方法。

四階B樹四階B+樹9.3哈希表及其查找9.3.1哈希表的定義和特點哈希表在記錄的關鍵字和其存儲位置（數(shù)組下標）之間設定一個確定的對應關系f，關鍵字為kval的記錄存儲在f（kval）位置處哈希表的裝填系數(shù)α＝n/m

其中m為哈希表分配空間n為填入的記錄數(shù)。

實際應用：0.65～0.85哈希函數(shù)可以對關鍵字做簡單的算術或邏輯運算。例：i=f1(key)=key例：i=f2(key)=(關鍵字的第一個字母ASCII碼)－(‘A’的ASCII碼)例：i=f3(key)=(f2(關鍵字的第一個字母)+f2(關鍵字的最后一個字母))/2沖突若出現(xiàn)f（key1）＝f（key2）的現(xiàn)象稱沖突。沒有沖突的哈希函數(shù)很少存在，只能盡量均勻。稱“再散列”。在建哈希表時，不僅要設定哈希函數(shù)，還要設定處理沖突的方法哈希表的嚴格定義：根據(jù)設定的哈希函數(shù)和處理沖突的方法為一組記錄建立的一種存儲結構，哈希函數(shù)又稱散列函數(shù)。構建哈希表又稱散列技術9.3.2構造哈希函數(shù)的方法除留余數(shù)法Hash（key）＝keymodp（p<=m）其中p為不大于m且最接近m的最大素數(shù)。如m=1000p=997平方取中法對一個關鍵字平方，取中間幾位，中間幾位和每位數(shù)字都有關系，不易沖突折疊法將關鍵字分割成位數(shù)相同的幾部分（最后一部分可以不同），然后幾部分相加舍進位作為哈希地址。有移位疊加、間界疊加9.3.3處理沖突的方法開放定址法

從哈希地址Hash(key)求得一個地址序列H1、H2…Hk,0<=k<=m-1,即H1－Hk-1都不空，直到Hk為空為止。若哈希表未滿，必能找到k<m，使Hk空。 Hi=(Hash(key)+di)modmi=1,2,...,kk<=m-1 di為遞增序列,有三種取法：p(i,k)探測函數(shù) a)di＝1,2,...,m-1 b)di=12，-12，22，－22...，k2，－k2

（k<=m/2） c)di＝偽隨機序列例

設一組關鍵字(07,15,20,31,48,53,64,76,82,99)試構建哈希表 取m＝11，p=11,Hash（key）＝keymod1101234567891053647699154882072031鏈地址法

將所有關鍵字為同義詞（即具有相同的哈希函數(shù)值）的記錄存貯在同一線性鏈表中，而哈希表中下標為i的分量存儲哈希函數(shù)值為i的鏈表的頭指針012345678910^^^^^99158207207648315364開放定址法的存儲結構int hashsize[]={997,...}typedefstruct{ ElemType *elem;//記錄存儲基址

int count; //記錄數(shù)

int sizeindex;//哈希表容量}HashTable;constSUCCESS＝1；constUNSUCCESS＝0；constDUPLICATE＝-1；StatusSearchHash(HashTableH,KeyTypekval,int&p,int&c)*StatusInsertHash(HashTable&H,ElemTypee)9.3.4哈希函數(shù)的查找及其性能分析鏈地址法存儲結構：typedefstructLHNode{ ElemType data; LHNode *next; //記錄數(shù)}LHNode,*LHNodeptr;typedefstruct{ LHNodeptr *elem; int count; //記錄數(shù) int sizeindex;//哈希表容量}LHashTable;StatusSearchHash(LHashTableH,KeyTypekval,LHNodeptr&p,int&c)StatusInsertHash(HashTable&H,ElemTypee)線形探測散列、二次探測散列、鏈地址法構建哈希函數(shù)比較（07，15，20，31，48，53，64，76，82，99）m=11n=10p=11α＝0.91關鍵字07152031485364768299ASL線形11122344242.4二次11122342222.0鏈地址法11122341111.7*11211111131.3*表示m=13p=13α＝0.77平均查找長度對比查找成功時平均查找長度：ASLsl（α）≈(1+1/(1-α))/2線性探測ASLsr（α）≈-1/αln(1-α)二次探測ASLsc（α）≈1+α/2鏈地址查找不成功時平均查找長度ASLul（α）≈(1+1/(1-α)2)/2ASLsr（α）≈1/(1-α)ASLsc（α）≈α+e-α平均查找長度與α的關系C語言中編譯程序使用的符號表，操作有對給定的名字查是否已在表中。填入新的名字。對給定的名字訪問其有關信息。對給定名字更新和填寫其信息。刪除一些無用的名字例

C語言32關鍵字的查找表希望ASL<=2以二次探測散列處理沖突,得α<=0.795因n=32故m>40考慮m＝4j＋3取m＝43，p＝41hash（key）＝[（key的第一個字符序號）×100＋（key的最后一個字符序號）]mod41

實際ASL=2.59.3.5哈希表的應用舉例謝謝順序表查找intSearch_Seq(SSTableST,KeyTypekey){//設監(jiān)視哨//在順序表ST中順序查找其關鍵字等于key的數(shù)據(jù)元素。

//若找到，則函數(shù)值為該元素在表中的位置，否則為0。

inti=0;ST.elem[0].key=key;//"哨兵"for(i=ST.length;ST.elem[i].key!=key;--i);//從后往前找

returni;//找不到時，i為0}//Search_Seq折半查找intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其關鍵字等于key的數(shù)據(jù)元素。

//若找到，則函數(shù)值為該元素在表中的位置，否則為0。low=1;high=ST.length;//置區(qū)間初值

while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;//找到待查元素

elseif(LT(key,ST.elem[mid].key))high=mid-1;//繼續(xù)在前半?yún)^(qū)間進行查找

elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間進行查找

}return0;//順序表中不存在待查元素}//Search_Bin索引查找intSearch_Idx(SSTableST,indexTableID,KeyTypekval){low=1;high=ID.length;found=FALSE;if(kval>ID.elem[high].key)return0;//給定值kval大于查找表中所有關鍵字

while(low<=high&&!found){//折半查找索引表，確定記錄查找區(qū)間

mid=(low+high)/2;if(kval<ID.elem[mid].key)high=mid-1;elseif(kval>ID.elem[mid].key)low=mid+1;else{found=TRUE;low=mid;}}//whiles=ID.elem[low].stadr;//經索引表查找后，下一步的查找范圍定位在第low塊

if(low<ID.length)t=ID.elem[low+1].stadr-1;elset=ST.length;//s和t為在ST表進行查找的下界和上界，若不是最后一塊，則上界為“下一塊的起始位置之前”

if(ST.elem[t].key==kval)returnt;else{//在ST.elem[s]至ST.elem[t-1]的區(qū)間內進行順序查找

ST.elem[0]=ST.elem[t];ST.elem[t].key=kval;//設置監(jiān)視哨

for(k=s;ST.elem[k].key!=kval;k++);ST.elem[t]=ST.elem[0];//恢復暫存值

if(k!=t)returnk;elsereturn0;}//else}//Search_Idx二叉排序樹查找BiTreeSearchBST(BiTreeT,KeyTypekey){//算法9.5aif(!T||EQ(key,T->data.key))returnT;//查找結束if(LT(key,T->data.key))returnSearchBST(T->lchild,keyelsereturnSearchBST(T->rchild,key);//在右子樹查找}//SearchBSTStatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){if(!T){p=f;returnFALSE;}//查找不成功

if(EQ(key,T->data.key)){p=T;returnTRUE;}//查找成功

if(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);//在左子樹查找

elsereturnSearchBST(T->rchild,key,T,p);//在右子樹查找}//SearchBST查到空樹或對應值結束二叉排序樹插入StatusInsertBST(BiTree&T,ElemTypee){//算法9.6//當二叉排序樹T中不存在關鍵字等于e.key的數(shù)據(jù)元素時，

//插入e并返回TRUE，否則返回FALSE

BiTreep,s;if(SearchBST(T,e.key,NULL,p))returnFALSE;

s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//插入s為新的根結點

elseif(LT(e.key,p->data.key))p->lchild=s;//插入s為左孩子

elsep->rchild=s;//插入s為右孩子

returnTRUE;}//InsertBST刪除結點StatusDeleteBST(BiTree&T,KeyTypekey){//算法9.7if(!T)returnFALSE;//不存在等于key的數(shù)據(jù)元素if(EQ(key,T->data.key))

returnDelete(T);if(LT(key,T->data.key))returnDeleteBST(T->lchild,key);elsereturnDeleteBST(T->rchild,key);}//DeleteBSTStatusDelete(BiTree&p){//算法9.8if(!p->rchild){

q=p;p=p->lchild;free(q);elseif(!p->lchild){q=p;p=p->rchild;free(q);}else{//左右子樹均不空

q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;

free(s);}//elsereturnTRUE;}//Delete什么情況下會出現(xiàn)q==p?開放定址Hash查找StatusSearchHash(HashTableH,HKeyTypeK,int&p,int&c){//在開放定址哈希表H中查找關鍵碼為K的元素，

//若查找成功，以p指示位置，并返回SUCCESS；

//否則，以p指示插入位置，并返回UNSUCCESS,//c用以計沖突次數(shù)，其初值置零，供建表插入時參考

p=Hash(K);//求得哈希地址

while((H.elem[p].key!=NULLKEY)&&//該位置中填有記錄

!equal(K,(H.elem[p].key)))collision(p,++c);//求得下一探查地址pif(equal(K,(H.elem[p].key)))returnSUCCESS;//查找成功，p返回待查數(shù)據(jù)元素位置

elsereturnUNSUCCESS;//查找不成功(H.elem[p].key==NULLKEY)，

//p返回的是插入位置}//SearchHash開放定址Hash插入StatusInsertHash(HashTable&H,HElemTypee){/