計算機軟件及應(yīng)用查找

Page12024/7/21學(xué)習(xí)目標理解“查找表”的結(jié)構(gòu)特點以及各種表示方法的適用性；熟練掌握以順序表或有序表表示靜態(tài)查找表時的查找方法；熟練掌握二叉查找樹的構(gòu)造和查找方法；理解二叉平衡樹的構(gòu)造過程；熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實質(zhì)性的差別；掌握描述查找過程的判定樹的構(gòu)造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。Page22024/7/21重點和難點重點：理解查找表的結(jié)構(gòu)特點及其各種表示方法的特點和適用場合。知識點順序表、有序表、索引順序表二叉查找樹、二叉平衡樹哈希表Page72024/7/218.2靜態(tài)查找表抽象數(shù)據(jù)類型靜態(tài)查找表的定義ADTStaticSearchTable{數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類

型相同的關(guān)鍵字，可唯一標識數(shù)據(jù)元素。數(shù)據(jù)關(guān)系：D中所有數(shù)據(jù)元素同屬一個集合。基本操作：

CreateTable(&ST,n);

操作結(jié)果：構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。

DestroyTable(&ST);

初始條件：靜態(tài)查找表ST存在；

操作結(jié)果：銷毀查找表ST。Page82024/7/21 Search(ST,kval);

初始條件：靜態(tài)查找表ST存在，kval為和查找表中元素的關(guān)鍵字

類型相同的給定值；

操作結(jié)果：若ST中存在其關(guān)鍵字等于kval的數(shù)據(jù)元素，則函數(shù)值

為該元素的值或在表中的位置，否則為“空”。

Traverse(ST,visit());

初始條件：靜態(tài)查找表ST存在，visit是對元素操作的應(yīng)用函數(shù)；

操作結(jié)果：按某種次序?qū)T的每個元素調(diào)用函數(shù)visit()一次且僅

一次，一旦visit()失敗，則操作失敗。}ADTStaticSearchTablePage92024/7/218.2.1順序表的查找適用情況查找表用順序存儲結(jié)構(gòu)存放。查找過程從表中最后一個記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比較；若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒有所查記錄，查找不成功。Page102024/7/2101234567891011513192137566475808892ST.elem順序表的類型描述：typedefstruct{

ElemType*elem;//數(shù)據(jù)元素存儲空間基址，建表

//時按實際長度分配，0號單元留空

intlength;//表中元素個數(shù)

}SSTable;i找6464監(jiān)視哨iiii比較次數(shù)=5ST.lengthPage112024/7/21順序查找的算法intsearch_seq(SSTableST,KeyTypekey){

//在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。

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

ST.elem[0].key=key; //ST.elem[0]為監(jiān)視哨

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);

//從后往前找

return(i);//找不到時，i為0}//search_seq

監(jiān)視哨會給系統(tǒng)帶來什么好處?

為什么從最后一個記錄開始？從第一個記錄開始，不可以嗎？&&i>=0Page122024/7/21順序表性能分析在順序表中進行(順序)查找查找成功的平均查找長度為：查找不成功的平均查找長度為n+1。Page132024/7/21平均查找長度較大，特別是當(dāng)待查找集合中元素較多時，查找效率較低。順序查找的缺點：算法簡單而且使用面廣。對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可；對表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可。順序查找的優(yōu)點：Page142024/7/218.2.2有序表的查找——折半查找適用情況查找表用順序存儲結(jié)構(gòu)存放，且各數(shù)據(jù)元素按關(guān)鍵字有序（升或降）排列。查找過程初始時，以整個查找表作為查找范圍。用查找條件中給定值k與查找范圍的中間位置的關(guān)鍵字比較；若相等，則查找成功；否則，根據(jù)比較結(jié)果縮小查找范圍；若k<中間位置的關(guān)鍵字，將查找范圍縮小到左子表；若k>中間位置的關(guān)鍵字，將查找范圍縮小到右子表；如此反復(fù)，直到查找成功或查找范圍縮小為空（即查找失?。┙Y(jié)束。Page152024/7/21待查序列為5,13,19,21,37,56,64,75,80,88,92，查找21。lowhighmid1234567891011513192137566475808892找211次比較ST.elemPage162024/7/211234567891011513192137566475808892highmid找21low2次ST.elemPage172024/7/211234567891011513192137566475808892lowhighmid找213次比較后，21查找成功ST.elemPage182024/7/21待查序列為5,13,19,21,37,56,64,75,80,88,92，查找70。lowhighmid1234567891011513192137566475808892找701次比較ST.elemPage192024/7/21low1234567891011513192137566475808892找70highmid2次比較ST.elemPage202024/7/211234567891011513192137566475808892找70lowhighmid3次比較ST.elemPage212024/7/211234567891011513192137566475808892找70highlowmid4次比較ST.elemPage222024/7/21low1234567891011513192137566475808892找70high失敗ST.elemPage232024/7/21折半查找算法intSearch_Bin(SSTableST,KeyTypekey){

//在有序表ST中折半查找其關(guān)鍵字等于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;

//找到待查元素

else

if(LT(key,ST.elem[mid].key))

high=mid-1;//繼續(xù)在前半?yún)^(qū)間內(nèi)進行查找

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

}//while return0;

//有序表中不存在待查元素}//Search_BinPage242024/7/21性能分析查找成功的平均查找長度1185210741936判定樹1234567891011513192137566475808892成功不成功Page252024/7/21性能分析查找成功的平均查找長度1185210741936判定樹成功不成功Page262024/7/21性能分析查找成功的平均查找長度Page272024/7/21性能分析查找不成功的平均查找長度1185210741936判定樹成功不成功Page282024/7/21折半查找的特點優(yōu)點：查找速度快；但表必須有序。缺點：頻繁插入和刪除不方便。

折半查找適于表中元素很少變化且查找頻繁的

情況；順序表查找適于查找少而表中元素頻繁變化的

情況。Page292024/7/21折半查找判定樹

判定樹：折半查找的過程可以用二叉樹來描述，樹中的每個結(jié)點對應(yīng)有序表中的一個記錄，結(jié)點的值為該記錄在表中的位置。通常稱這個描述折半查找過程的二叉樹為折半查找判定樹，簡稱判定樹。Page302024/7/21⑴當(dāng)n=0時，折半查找判定樹為空；⑵當(dāng)n＞0時，折半查找判定樹的根結(jié)點是有序表中序號為mid=(n+1)/2的記錄，根結(jié)點的左子樹是與有序表r[1]~r[mid-1]相對應(yīng)的折半查找判定樹，根結(jié)點的右子樹是與r[mid+1]~r[n]相對應(yīng)的折半查找判定樹。

判定樹的構(gòu)造方法Page312024/7/21－11－22－33－44－510－1111－9－108－97－85－66－7內(nèi)部結(jié)點外部結(jié)點3691011784512判定樹的構(gòu)造方法Page332024/7/21highmidlow12345678910111213141516171822121389203342443824486058745786532248861713索引表查38Page342024/7/21lowhighmid12345678910111213141516171822121389203342443824486058745786532248861713索引表查38Page352024/7/21查找成功的平均查找長度性能分析Page362024/7/21索引順序表的特點平均查找長度介于順序表和有序表之間；表的結(jié)構(gòu)比較靈活例如，存儲記錄的線性表可以采用鏈式存儲結(jié)構(gòu)，且整個表不需要有序，可便于插入和刪除；又如，索引順序表中的“索引”不一定按“塊內(nèi)最大值”建立，而是可以根據(jù)靜態(tài)查找表的特點建立“分類索引”；再如，在查找表的記錄數(shù)眾多時還可建立"多層索引"等。Page382024/7/21基本操作P：

InitDSTable(&DT);

操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。

DestroyDSTable(&DT);

初始條件：動態(tài)查找表DT存在；

操作結(jié)果：銷毀動態(tài)查找表DT。

SearchDSTable(DT,kval);

初始條件：動態(tài)查找表DT存在，kval為和關(guān)鍵字類型相同的

給定值；

操作結(jié)果：若DT中存在其關(guān)鍵字等于kval的數(shù)據(jù)元素，則函

數(shù)值為該元素的值或在表中的位置，否則為“空”。Page392024/7/21

InsertDSTable(&DT,e);

初始條件：動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素；

操作結(jié)果：若DT中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則插

入e到DT。

DeleteDSTable(&T,kval);

初始條件：動態(tài)查找表DT存在，kval為和關(guān)鍵字類型相同的給

定值；

操作結(jié)果：若DT中存在其關(guān)鍵字等于kval的數(shù)據(jù)元素，則刪

除之。

TraverseDSTable(DT,Visit());

初始條件：動態(tài)查找表DT存在，Visit是對結(jié)點操作的應(yīng)用函

數(shù)；

操作結(jié)果：按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù)visit()一次且

至多一次。一旦visit()失敗，則操作失敗。}ADTDynamicSearchTablePage402024/7/218.3.1二叉排序樹和平衡二叉樹二叉排序樹定義二叉排序樹或為一棵空樹，或為具有如下性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；它的左右子樹也分別是二叉排序樹。Page412024/7/2145125332724100619078二叉排序樹Page422024/7/21CAOZHAODINGCHENWANGXIALIDUMA二叉排序樹Page432024/7/2150308030401025233560908588不是二叉排序樹二叉樹的一個重要特征是中序遍歷得到一個關(guān)鍵字的有序序列Page442024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于100的記錄Page452024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于100的記錄Page462024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于100的記錄Page472024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于100的記錄Page482024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于40的記錄Page492024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于40的記錄Page502024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于40的記錄Page512024/7/21二叉排序樹的查找若二叉排序樹為空，則查找不成功；否則若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。45125332724100619078查找關(guān)鍵字等于40的記錄右子樹為空，說明樹中沒有待查記錄，返回空指針。Page522024/7/21算法BiTreeSearchBST(BSTreeT,KeyTypekey){

//根指針T所指二叉查找樹中遞歸查找關(guān)鍵字等于key的數(shù)據(jù)元素,

//若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點的指針，否則返回空指針。

if(!T&&EQ(key,T->data.key)return(T);

//查找結(jié)束

elseifLT(key,T->data.key)

return(SearchBST(T->lchild.key));

//在左子樹中繼續(xù)查找

elsereturn(SearchBST(T->rchild.key));

//在右子樹中繼續(xù)查找}//SearchBSTPage532024/7/21二叉排序樹的插入用遞歸過程實現(xiàn)在一棵二叉排序樹中插入一個結(jié)點若二叉排序樹為空，則新結(jié)點作為二叉排序樹的根結(jié)點；若給定結(jié)點的關(guān)鍵字值小于根結(jié)點關(guān)鍵字值，則插入在左子樹上；若給定結(jié)點的關(guān)鍵字值大于根結(jié)點關(guān)鍵字值，則插入在右子樹上。Page542024/7/21插入關(guān)鍵字是40的記錄4512533272410061907840Page552024/7/21插入關(guān)鍵字是59的記錄

新插入的結(jié)點一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子。4512533272410061907859Page562024/7/21二叉排序樹的查找算法的修改StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){

//在根指針T所指二叉排序樹中遞歸地查找關(guān)鍵字等于key的數(shù)據(jù)元素，//若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點，并返回TRUE，否則指針

//p指向查找路徑上訪問的最后一個結(jié)點并返回FALSE，指針f指向T的

//雙親，其初始調(diào)用值為NULL。

if(!T){p=f;return(FALSE);}

//查找不成功

elseifEQ(key,T->data.key){p=T;return(TRUE);}

//查找成功

elseifLT(key,T->data.key)returnSearchBST(T->lchild.key,T,p);

//在左子樹中繼續(xù)查找

elsereturnSearchBST(T->rchild.key,T,p);

//在右子樹中繼續(xù)查找}//SearchBSTPage572024/7/21二叉排序樹的插入算法StatusInsertBST(BiTree&T,ElemTypee){

//當(dāng)二叉排序樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時，

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

if(!SearchBST(T,e.key,NULL,p){ //查找不成功

s=(BiTree)malloc(sizeof(BiTNode));

if(!s)exit(1);

//存儲分配失敗

s->data=e;s->lchild=s->rchild=NULL; if(!p)T=s;

//被插結(jié)點*s為新的根結(jié)點

elseifLT(e.key<p->data.key)p->lchild=s;

//被插結(jié)點*s為*p的左孩子

elsep->rchild=s;

//被插結(jié)點*s為*p的右孩子

returnTRUE; }//if elsereturnFALSE;

//樹中已有關(guān)鍵字相同的結(jié)點，不再插入}//InsertBSTPage582024/7/21創(chuàng)建二叉排序樹的操作基本思想從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹。設(shè)關(guān)鍵字序列{10,18,3,8,12,2,7,3}，初始構(gòu)造二叉樹。10183812273Page592024/7/21二叉排序樹的刪除在二叉查找樹上刪除一個結(jié)點之后應(yīng)該仍是一棵二叉樹，并保持其二叉查找樹的特性。分四種情況討論：被刪結(jié)點為“葉子”

此時刪除該結(jié)點不影響其它結(jié)點之間的關(guān)系，因此可以直接刪除，即僅需修改其雙親結(jié)點的相應(yīng)指針即可；SPKQSPQ中序遍歷：KPSQ中序遍歷：PSQPage602024/7/21被刪結(jié)點只有左子樹只需要將其左子樹直接鏈接到其雙親結(jié)點成為為其雙親的子樹即可；SPPLQ中序遍歷：PLPSQSPLQ中序遍歷：PLSQPage612024/7/21被刪結(jié)點只有左子樹只需要將其左子樹直接鏈接到其雙親結(jié)點成為為其雙親的子樹即可；中序遍歷：QSPLP中序遍歷：QSPLSQPLPSQPLPage622024/7/21被刪結(jié)點只有右子樹只需要將其右子樹直接鏈接到其雙親結(jié)點成為為其雙親的子樹即可；中序遍歷：PPRSQ中序遍歷：PRSQSPRQSPPRQPage632024/7/21被刪結(jié)點只有右子樹只需要將其右子樹直接鏈接到其雙親結(jié)點成為為其雙親的子樹即可；中序遍歷：QSPPR中序遍歷：QSPRSQPRSQPRPPage662024/7/21算法StatusDeleteBST(BiTree&T,KeyTypekey){

//若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除

//該數(shù)據(jù)元素結(jié)點，并返回TRUE；否則返回FALSE if(!T)returnFALSE;

//不存在關(guān)鍵字等于key的數(shù)據(jù)元素

else{

if(EQ(key,T->data.key)returnDelete(T);

//找到關(guān)鍵字等于key的數(shù)據(jù)元素

elseif(LT(key,T->data.key)

returnDeleteBST(T->lchild,key);

//返回在左子樹上查找的結(jié)果

elsereturnDeleteBST(T->rchild,key);

//返回在右子樹上查找的結(jié)果

}//else}//DeleteBSTPage672024/7/21算法StatusDelete(BiTree&p){

//從二叉排序樹中刪除結(jié)點p，并重接它的左或右子樹

if(!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;}

//轉(zhuǎn)左，然后向右到盡頭

p->data=s->data;

//s指向被刪結(jié)點的前驅(qū)

if(q!=p)q->rchild=s->lchild;

//重接*q的右子樹

elseq->lchild=s->lchild;

//重接*q的左子樹

deletes;

}}//DeletePage682024/7/21805012060110150557053806012011015055705380551201101505370刪除50刪除60Page692024/7/211042581365842561358425513刪除6刪除10Page722024/7/21關(guān)鍵字輸入序列最差的情況二叉排序樹為單支樹，深度為n最好的情況二叉排序樹和折半查找判定樹相同，深度為

log2n+1在動態(tài)生成二叉排序樹的過程中，進行平衡化處理，使之成為平衡二叉樹。二叉排序樹與關(guān)鍵字序列無關(guān)。Page762024/7/21RR型原因：由于在*a的右子樹根結(jié)點的右子樹上插入結(jié)點，*a的

平衡因子由-1增至-2，致使以*a為根的子樹失去平衡。處理：進行一次向左的逆時針旋轉(zhuǎn)。0000-1x-1-2abecd-1cabedxPage772024/7/21LR型原因：由于在*a的左子樹根結(jié)點的右子樹上插入結(jié)點，*a的

平衡因子由1增至2，致使以*a為根的子樹失去平衡。處理：進行先左旋、后右旋的兩次旋轉(zhuǎn)。xabhicdef12abhicdefgxPage782024/7/21RL型原因：由于在*a的右子樹根結(jié)點的左子樹上插入結(jié)點，*a的

平衡因子由-1增至-2，致使以*a為根的子樹失去平衡。處理：進行先右旋、后左旋的兩次旋轉(zhuǎn)。x-1100-10000111-2abcfdeghiabcfdeghixPage792024/7/21對關(guān)鍵字序列(13,24,37,90,53)，構(gòu)造平衡二叉樹。132437132437RR905300-10-1-20000-1-101-2-2從最先不平衡結(jié)點開始調(diào)整RL13243790531324379053Page802024/7/218.4哈希表靜態(tài)查找表和動態(tài)查找表的缺點為了從查找表中找到關(guān)鍵字值等于某個值的記錄，都要經(jīng)過一系列的關(guān)鍵字比較，以確定待查記錄的存儲位置或查找失敗，查找所需時間總是與比較次數(shù)有關(guān)。哈希表的基本思想將記錄的存儲位置與它的關(guān)鍵字之間建立一個確定的關(guān)系H，使每個關(guān)鍵字和唯一的存儲位置對應(yīng)。在查找時，只需要根據(jù)對應(yīng)關(guān)系計算出給定的關(guān)鍵字值H(k)，就可以得到記錄的存儲位置。這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。Page832024/7/21哈希法主要解決兩個問題：對給定的一組關(guān)鍵字，設(shè)定一個“好”的哈希函數(shù)，使其計算簡單，并且分不均勻，即減少沖突。沖突不可避免，擬定解決沖突的方法。Page842024/7/218.4.2哈希函數(shù)的構(gòu)造方法直接定址法思想取關(guān)鍵字本身或關(guān)鍵字的某個線性函數(shù)值作為哈希表的地址。公式H(key)=key或H(key)=a*key+b（a和b均為常數(shù)）特點該方法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突。適用情況給定的一組關(guān)鍵字為關(guān)鍵字集合中全體元素，若不是全體關(guān)鍵字，則必有某地址單元空閑。實際中能用這種哈希函數(shù)的情況很少。Page852024/7/21解放后出生人口調(diào)查表H(key)=key+(-1948)地址H(key)010203

22

57年份key194919501951

1970

1999人數(shù)800070006000

15000

40001歲到100歲的人口統(tǒng)計表H(key)=key地址H(key)010203

25

100年齡key123

25

100人數(shù)300020005000

1050

40Page892024/7/21

為標識符建立一個哈希表，假設(shè)標識符為一個字母或一個字母和數(shù)字。在計算機內(nèi)用兩位八進制數(shù)表示字母和數(shù)字。71626160320302019

210Z

CBA哈希地址(217~29)（關(guān)鍵字）2關(guān)鍵字記錄745741734314310370440210010174565147413044734741431470443105411370400144000012100000010000216321622161206220611160120011000100Q3Q2Q1P2P1I0JIAPage902024/7/21折疊法思想若關(guān)鍵字的位數(shù)很多，且每一位上數(shù)字分布大致均勻，則可采用移位疊加或間界疊加。即將關(guān)鍵字分成若干部分，然后以它們的疊加和(舍去進位)作為哈希地址。移位疊加是將分割后的每一部分的最低位對齊，然后相加；間界疊加是從一端向另一端沿分割界來回折疊，然后對齊相加。適用情況適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況。Page912024/7/21例如：關(guān)鍵字為0442205864，哈希地址位數(shù)為4。586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加Page932024/7/21例如：給定存儲單元地址為1,000,000

1,000,027，即

表長度為28。則關(guān)鍵字172,148的哈希地址為H(key)=172148MOD23+1,000,000=16+1,000,000=1,000,016Page942024/7/21隨機數(shù)法思想當(dāng)關(guān)鍵字不等長時，可取關(guān)鍵字的某個偽隨機函數(shù)值作為哈希地址。公式H(key)=random(key)使用情況適于關(guān)鍵字長度不等的情況。Page952024/7/21選取哈希函數(shù)，考慮以下因素：計算哈希函數(shù)所需時間關(guān)鍵字長度哈希表長度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率Page962024/7/218.4.3處理沖突的方法開放定址法思想當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中。公式Hi=(H(key)+di)MODm，i=1,2,……k(km-1)

其中：H(key)——哈希函數(shù)

m——哈希表表長

di——增量序列線性探測再散列：di=1,2,3,……m-1二次探測再散列：di=12,-12,22,-22,32,……±k2(km/2)偽隨機探測再散列：di=偽隨機數(shù)序列Page972024/7/21線性探測再散列

H(38)=38MOD11=5 沖突

H1=(5+1)MOD11=6 沖突

H2=(5+2)MOD11=7 沖突

H3=(5+3)MOD11=8 不沖突38例如：表長為11的哈希表中已填有關(guān)鍵字為17、60、29的記

錄，H(key)=keyMOD11，現(xiàn)有第4條記錄，其關(guān)鍵字

為38，按三種處理沖突的方法，將它填入表中。29176010987654321Page982024/7/2138例如：表長為11的哈希表中已填有關(guān)鍵字為17、60、29的記

錄，H(key)=keyMOD11，現(xiàn)有第4條記錄，其關(guān)鍵字

為38，按三種處理沖突的方法，將它填入表中。29176010987654321二次探測再散列

H(38)=38MOD11=5 沖突

H1=(5+12)MOD11=6 沖突

H2=(5-12)MOD11=4 不沖突Page992024/7/2138例如：表長為11的哈希表中已填有關(guān)鍵字為17、60、29的記

錄，H(key)=keyMOD11，現(xiàn)有第4條記錄，其關(guān)鍵字

為38，按三種處理沖突的方法，將它填入表中。29176010987654321偽隨機探測再散列

H(38)=38MOD11=5沖突 設(shè)偽隨機數(shù)序列為9，則：

H1=(5+9)MOD11=3不沖突Page1002024/7/21鏈地址法思想將所有關(guān)鍵字為"同義詞"的記錄鏈接在一個線性鏈表中。此時的哈希表以"指針數(shù)組"的形式出現(xiàn)，數(shù)組內(nèi)各個分量存儲相應(yīng)哈希地址的鏈表的頭指針。Page1012024/7/21例如：已知一組關(guān)鍵字(19,56,23,14,68,82,70,36,91)

哈希函數(shù)為：H(key)=keyMOD7，用鏈地址法處理沖突。

654321056

19

23

14

68

82

7036

91Page1022024/7/21再哈希法思想構(gòu)造若干個哈希函數(shù)，當(dāng)發(fā)生沖突時，用另一個哈希函數(shù)計算另一個哈希地址，直至不發(fā)生沖突為止。特點需要預(yù)先設(shè)置一個哈希函數(shù)的序列；計算時間增加。建立一個公共溢出區(qū)思想建立兩個表，一個是基本表，另一個是溢出表（存放所有關(guān)鍵字和基本表中關(guān)鍵字沖突的記錄，一旦沖突發(fā)生，就存入溢出表）。Page1032024/7/218.4.4哈希表的查找及其分析哈希查找過程給定k值計算H(k)此地址為空關(guān)鍵字==k查找失敗查找成功按處理沖突方法計算HiYNYNPage1042024/7/211514131211109876543210

已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù)H(key)=keyMOD13和線性探測再散列處理沖突構(gòu)造哈希表，設(shè)每個記錄的查找概率相等，求平均查找長度。（哈希表長16）141682755192084792311101H(19)=6H(14)=1H(23)=10H(1)=1H(68)=3H(20)=7H(84)=611沖突，H1=(1+1)MOD16=2211沖突，H1=(6+1)MOD16=7沖突，H2=(6+2)MOD16=83H(27)=1沖突，H3=(1+3)MOD16=4沖突，H1=(1+1)MOD16=2沖突，H2=(1+2)MOD16=34Page1052024/7/211514131211109876543210

已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù)H(key)=keyMOD13和線性探測再散列處理沖突構(gòu)造哈希表，設(shè)每個記錄的查找概率相等，求平均查找長度。（哈希表長16）1416827551920847923111011121134H(55)=3H(10)=10H(11)=11沖突，H1=(3+1)MOD16=4沖突，H2=(3+2)MOD16=53沖突，H1=(10+1)MOD16=11沖突，H2=(10+2)MOD16=1231Page1062024/7/21H(79)=1ASL=1514131211109876543210

已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù)H(key)=keyMOD13和線性探測再散列處理沖突構(gòu)造哈希表，設(shè)每個記錄的查找概率相等，求平均查找長度。（哈希表長16）14168275519208479231110沖突，H1=(1+1)MOD16=2沖突，H2=(1+2)MOD16=3沖突，H3=(1+3)MOD16=4沖突，H4=(1+4)MOD16=5沖突，H5=(1+5)MOD16=6沖突，H6=(1+6)MOD16=7沖突，H7=(1+7)MOD