清華大學出版社數據結構C++描述-07搜索

靜態(tài)搜索表二叉搜索樹AVL樹哈希表第七章搜索結構1搜索表（查找表）查找表是由同一類型的數據元素(或記錄)構成的集合。在某一數據集合中查找數據元素是否存在。搜索（查找）2對查找表經常進行的操作:1）查詢某個“特定的”數據元素是否在查找表中；2）檢索某個“特定的”數據元素的各種屬性；3）在查找表中插入一個數據元素；4）從查找表中刪去某個數據元素。3僅作查詢和檢索操作的查找表。靜態(tài)查找表有時在查詢之后，還需要將“查詢”結果為“不在查找表中”的數據元素插入到查找表中；或者，從查找表中刪除其“查詢”結果為“在查找表中”的數據元素。動態(tài)查找表查找表可分為兩類:4如何進行查找？查找的方法取決于查找表的結構。57.1靜態(tài)查找表7.2動態(tài)查找樹表7.3哈希表67.1靜態(tài)查找表7數據對象D：數據關系R：D是具有相同特性的數據元素的集合。每個數據元素含有類型相同的關鍵字，可唯一標識數據元素。

數據元素同屬一個集合。ADTStaticSearchTable{8

Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());基本操作P：}ADTStaticSearchTable9構造一個含n個數據元素的靜態(tài)查找表ST。

Create(&ST,n);操作結果：10銷毀表ST。Destroy(&ST);初始條件：操作結果：靜態(tài)查找表ST存在；11若ST中存在其關鍵字等于

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

Search(ST,key);初始條件：操作結果：靜態(tài)查找表ST存在，key為和查找表中元素的關鍵字類型相同的給定值；12按某種次序對ST的每個元素調用函數Visit()一次且僅一次，一旦Visit()失敗，則操作失敗。Traverse(ST,Visit());初始條件：操作結果：靜態(tài)查找表ST存在，Visit是對元素操作的應用函數；13數據表與搜索表的類定義

#include<iostream.h>#include<assert.h>constint

defaultSize=100;template<classE,classK>classdataList; //數據表類的前視定義template<classE,classK>classdataNode{ //數據表中結點類的定義friendclassdataList<E,K>;

//聲明其友元類為dataListpublic:14

dataNode(constKx):key(x){} //構造函數

KgetKey()const{returnkey;} //讀取關鍵碼

voidsetKey(Kx){key=x;} //修改關鍵碼private:

Kkey; //關鍵碼域

E

other;

//其他域（視問題而定）};template<classE,classK>classdataList

{ //數據表類定義public:15

dataList(int

sz=defaultSize)

:ArraySize(sz),CuurentSize(0){

Element=newdataNode<E,K>[sz];

assert(Element!=NULL);}

dataList(dataList<E,K>&R);//復制構造函數

virtual～dataList(){delete[]Element;}

//析構函數

virtualint

Length(){returnCurrentSize;}

//求表的長度

virtualKgetKey(inti)const{ //提取第

i（1開始）元素值

16

assert(i>0||i<=CurrentSize);returnElement[i-1].key;}virtualvoidsetKey(Kx,int

i){ //修改第i（1開始）元素值

assert(i>0||i<=CurrentSize);

Element[i-1].key=x;} virtualint

SeqSearch(constKx)const; //搜索

virtualbool

Insert(E&e1); //插入

virtualbool

Remove(K

x,E&e1); //刪除friendostream&operator<<(ostream&out,const

dataList<E,K>&OutList);//輸出17friendistream&operator>>(istream&in,

dataList<E,K>&InList);//輸入protected:

dataNode<E,K>*Element;

//數據表存儲數組

int

ArraySize,CurrentSize;

//數組最大長度和當前長度};18template<classE,classK>bool

dataList<E,K>::Insert(E&e1){//在dataList的尾部插入新元素,若插入失敗函數返//回false,否則返回true.if(CurrentSize==ArraySize)returnfalse;

Element[CurrentSize]=e1; //插入在尾端

CurrentSize++;returntrue;};19

template<classE,classK>bool

dataList<E,K>::Remove(Kx,E&e1){//在dataList中刪除關鍵碼為x的元素,通過e1返回。//用尾元素填補被刪除元素。

if(CurrentSize==0)returnfalse;for(int

i==0;i<CurrentSize

&&

Element[i]!=x;i++); //在表中順序尋找20

if(i==CurrentSize)returnfalse; //未找到

e1=Element[i].other; //找到,保存被刪元素的值

Element[i]=Element[CurrentSize-1];//填補

CurrentSize--;returntrue;};21

template<classE,classK>ostream&operator<<(ostream&out,constdataList<E,K>&OutList){

out<<“存儲數組大小”<<endl;for(int

i=1;i<=OutList.CurrentSize;i++)

out<<OutList.Element[i-1]<<‘’;

out<<endl; //輸出表的所有表項到out

out<<“數組當前長度:”<<

OutList.CurrentSize

<<endl;//輸出表的當前長度到out returnout;};數據表類的友元函數

22

template<classE,classK>istream&operator>>(istream&in,dataList<E,K>&InList){

cout<<“輸入存儲數組當前長度:”;in>>InList.CurrentSize; //從in輸入表的當前長度

cout<<“輸入數組元素的值:\n”;for(int

i=1;i<=InList.CurrentSize;i++){

//從in輸入表的全部表項

cout<<“元素”<<i<<“:”;in>>InList.Element[i-1];}returnin;};23一、順序查找表二、有序查找表三、靜態(tài)查找樹表四、索引順序表24以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表25ST.Element回顧順序表的查找過程：假設給定值e=64,要求ST.Element[k].key=e,問:k=?kk26ST.ElementiST.elemiikey=64key=60i27使用監(jiān)視哨的順序搜索算法

template<classE,classK>int

dataList<E,K>::SeqSearch(constKx)const{

Element[CurrentSize].key=x;

int

i=0; //將x設置為監(jiān)視哨

while(Element[i].key!=x)i++; //從前向后順序搜索

returni+1;};28constint

Size=10;main(){

dataList<int>L1(Size); //定義int型搜索表L1

int

Target;int

Loc;

cin>>L1;cout<<L1; //輸入L1

cout<<“Searchforainteger:”;

cin>>Target; //輸入要搜索的數據

if((Location=L1.Seqsearch(Target))!=

L1.Length())

cout<<“找到待查元素位置在：”<<Loc+1

<<endl; //搜索成功

elsecout<<“沒有找到待查元素\n”;

//搜索不成功};29

定義：

查找算法的平均查找長度

(AverageSearchLength)

為確定記錄在查找表中的位置，需和給定值

進行比較的關鍵字個數的期望值

其中:n

為表長，Pi

為查找表中第i個記錄的概率，且，Ci為找到該記錄時，曾和給定 值比較過的關鍵字的個數。分析順序查找的時間性能30在等概率查找的情況下，

順序表查找成功的平均查找長度為：對順序表而言，Ci=iASL=P1+2P2++（n-1)Pn-1+nPn在搜索不成功情形，ASLunsucc=n+131

上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。二、有序查找表

若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。32ST.elemST.length例如:key=64

的查找過程如下：lowhighmidlow

mid

high

midlow

指示查找區(qū)間的下界high

指示查找區(qū)間的上界mid=(low+high)/233intSearch_Bin(SSTableST,KeyTypekey){

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ù)在前半區(qū)間進行查找

else

low=mid+1;//繼續(xù)在后半區(qū)間進行查找

}return0;//順序表中不存在待查元素}//Search_Bin34先看一個具體的情況，假設：n=11分析折半查找的平均查找長度6391425781011判定樹1223333444435假設n=2h-1并且查找概率相等則

在n>50時，可得近似結果

一般情況下，表長為n的折半查找的判定樹的深度和含有n個結點的完全二叉樹的深度相同。索引順序表36關鍵字:ABCDEPi:0.20.30.050.30.15

Ci:23123三、靜態(tài)查找樹表在不等概率查找的情況下，折半查找不是有序表最好的查找方法。例如:此時ASL=20.2+30.3+10.05+20.3+30.15=2.4若改變Ci的值21323則ASL=20.2+10.3+30.05+20.3+30.15=1.937

使達最小的判定樹稱為最優(yōu)二叉樹。定義:38為計算方便，令wi=pi選擇二叉樹的根結點，使達最小

介紹一種次優(yōu)二叉樹的構造方法：為便于計算，引入累計權值和并設wl-1=0和swl-1=0，則推導可得39023811151823例如:lh211812431018h9608EC21Ah53lhG301340ECGABDF所得次優(yōu)二叉樹如下所示:查找比較“總次數”

=32+41+25+33

+14+33+25=52查找比較“總次數”

=32+21+35+13

+34+23+35=59和折半查找相比較DBACFEG41Status

SecondOptimal(BiTree

&T,ElemTypeR[],

float

sw[],intlow,inthigh)

{

//由有序表R[low..high]及其累計權值表sw//遞歸構造次優(yōu)查找樹T。

選擇最小的ΔPi值

if(!(T=(BiTree)malloc(sizeof(BiTNode))))

returnERROR;T->data=R[i];//生成結點構造次優(yōu)二叉樹的算法CONTINUE42if(i==low)T->lchild=NULL;//左子樹空elseSecondOptimal(T->lchild,R,sw,low,i-1);

//構造左子樹

if(i==high)T->rchild=NULL;//右子樹空

else

SecondOptimal(T->rchild,R,sw,i+1,high);

//構造右子樹

returnOK;}//SecondOptimal43次優(yōu)查找樹采用二叉鏈表的存儲結構Status

CreateSOSTre(SOSTree

&T,SSTableST){//由有序表ST構造一棵次優(yōu)查找樹T//ST的數據元素含有權域weight

if(ST.length=0)T=NULL;

else{

FindSW(sw,ST);//按照有序表ST中各數據元素

//的weight值求累計權值表

SecondOpiamal(T,ST.elem,sw,1,ST.length);

}

returnOK;}//CreatSOSTree44四、索引順序表（分塊查找）將表分成幾塊，塊內無序，塊間有序；先確定待查記錄所在塊，再在塊內查找建立索引表，每個索引表結點含有最大關鍵字域和指向本塊第一個結點的指針4512345678910111213141516171822121389203342443824486058745786532248861713索引表查3846分塊查找方法評價(b=n/s)47ASL最大最小兩者之間表結構有序表、無序表有序表分塊有序表存儲結構順序存儲結構線性鏈表順序存儲結構順序存儲結構線性鏈表查找方法比較順序查找折半查找分塊查找487.2動態(tài)查找樹表49ADTDynamicSearchTable{抽象數據類型動態(tài)查找表的定義如下：數據對象D：數據關系R：

數據元素同屬一個集合。D是具有相同特性的數據元素的集合。每個數據元素含有類型相同的關鍵字，可唯一標識數據元素。50InitDSTable(&DT)基本操作P：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT,Visit());}ADTDynamicSearchTable51操作結果：構造一個空的動態(tài)查找表DT。InitDSTable(&DT);52銷毀動態(tài)查找表DT。DestroyDSTable(&DT);初始條件：操作結果：動態(tài)查找表DT存在；53若DT中存在其關鍵字等于key的數據元素，則函數值為該元素的值或在表中的位置，否則為“空”。SearchDSTable(DT,key);初始條件：操作結果：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值；54動態(tài)查找表DT存在，

e為待插入的數據元素；InsertDSTable(&DT,e);初始條件：操作結果：若DT中不存在其關鍵字等于e.key的數據元素，則插入e到DT。55動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值；DeleteDSTable(&T,key);初始條件：操作結果：若DT中存在其關鍵字等于key的數據元素，則刪除之。56動態(tài)查找表DT存在，Visit是對結點操作的應用函數；TraverseDSTable(DT,Visit());初始條件：操作結果：按某種次序對DT的每個結點調用函數Visit()一次且至多一次。一旦Visit()失敗，則操作失敗。57一、二叉排序樹（二叉查找樹）二、二叉平衡樹58一、二叉排序樹（二叉查找樹）1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析59（1）若它的左子樹不空，則左子樹上

所有結點的值均小于根結點的值；1．定義：

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上

所有結點的值均大于根結點的值；60503080209010854035252388例如:是二叉排序樹。66不61二叉搜索樹的類定義template<classE,classK>struct

BSTNode

{ //二叉樹結點類

Edata; //數據域

BSTNode<E,K>*left,*right;

//左右子女

通常，取二叉鏈表作為二叉排序樹的存儲結構62

BSTNode(){left=NULL;right=NULL;

}

//構造函數

BSTNode(constEd,BSTNode<E,K>*L=NULL,

BSTNode<E,K>*R=NULL){data=d;left=L;right=R;}

//構造函數～BSTNode(){} //析構函數

voidsetData(Ed){data=d;} //修改

EgetData(){returndata;} //提取

booloperator<(constE&x)

//重載：判小于

{returndata.key<

x.key;}63

booloperator>(constE&x)

//重載：判大于

{returndata.key>x.key;}

booloperator==(constE&x)

//重載：判等于

{returndata.key==x.key;}};template<classE,classK>classBST{

//二叉搜索樹類定義public:BST(){root=NULL;

} //構造函數

BST(Kvalue); //構造函數

～BST(){}; //析構函數

64

bool

Search(constKx)const //搜索

{returnSearch(x,root)!=NULL;}

BST<E,K>&operator=(constBST<E,K>&R); //重載：賦值

voidmakeEmpty()

//置空

{makeEmpty(root);root=NULL;}voidPrintTree()const{PrintTree(root);}//輸出

EMin(){returnMin(root)->data;} //求最小

EMax(){returnMax(root)->data;} //求最大

bool

Insert(constE&e1)

//插入新元素

{returnInsert(e1,root);}65

bool

Remove(constKx){returnRemove(x,root);} //刪除含x的結點private:

BSTNode<E,K>*root; //根指針

KRefValue; //輸入停止標志

BSTNode<E,K>* //遞歸：搜索

Search(constKx,BSTNode<E,K>*ptr);voidmakeEmpty(BSTNode<E,K>*&ptr); //遞歸：置空

voidPrintTree(BSTNode<E,K>*ptr)const; //遞歸：打印

BSTNode<E,K>* //遞歸：復制

Copy(constBSTNode<E,K>*ptr); 66

BSTNode<E,K>*Min(BSTNode<E,K>*ptr);

//遞歸：求最小

BSTNode<E,K>*Max(BSTNode<E,K>*ptr);

//遞歸：求最大

boolInsert(constE&e1,

BSTNode<E,K>*&

ptr);

//遞歸：插入

boolRemove(constKx,BSTNode<E,K>*&

ptr);

//遞歸：刪除};二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現與二叉樹類似。672．二叉排序樹的查找算法：1）若給定值等于根結點的關鍵字，則查找成功；2）若給定值小于根結點的關鍵字，則繼續(xù)在左子樹上進行查找；3）若給定值大于根結點的關鍵字，則繼續(xù)在右子樹上進行查找。否則，若二叉排序樹為空，則查找不成功；6850308020908540358832例如:二叉排序樹查找關鍵字==50,505035,503040355090,50809095,69從上述查找過程可見，在查找過程中，生成了一條查找路徑：

從根結點出發(fā)，沿著左分支或右分支逐層向下直至關鍵字等于給定值的結點;或者

從根結點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功

——查找不成功70template<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//私有遞歸函數：在以ptr為根的二叉搜索樹中搜//索含x的結點。若找到，則函數返回該結點的//地址，否則函數返回NULL值。

if(ptr==NULL)returnNULL;

elseif(x<ptr->data)returnSearch(x,ptr->left);elseif(x>ptr->data)returnSearch(x,ptr->right);elsereturnptr; //搜索成功};71template<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//非遞歸函數：作為對比，在當前以ptr為根的二//叉搜索樹中搜索含x的結點。若找到，則函數返//回該結點的地址，否則函數返回NULL值。

if(ptr==NULL)returnNULL;

BSTNode<E,K>*temp=ptr;while(temp!=NULL){if(x==temp->data)returntemp;if(x<temp->data)temp=temp->left;elsetemp=temp->right;}returnNULL;};72

搜索過程是從根結點開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個結點；搜索不成功，搜索指針將走到樹上某個結點的空子樹。設樹的高度為h，最多比較次數不超過h。7330201040352523T設key=48TT22pTTTTTp74根據動態(tài)查找表的定義，“插入”操作在查找不成功時才進行；3．二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結點為新的根結點；否則，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。75{10、18、3、8、12、2、7}10101810183101838101838121018381221018381227101838122776二叉搜索樹的插入算法template<classE,classK>bool

BST<E,K>::Insert(constE&e1,BSTNode<E,K>*&ptr)

//私有函數：在以ptr為根的二叉搜索樹//中插入值為e1的結點。若在樹中已有//含e1的結點則不插入77bool

BST<E,K>::Insert(constE&e1,BSTNode<E,K>*&ptr){if(ptr==NULL)

{

//新結點作為葉結點插入

ptr=newBstNode<E,K>(e1); //創(chuàng)建新結點

if(ptr==NULL)

{cerr<<"Outofspace"<<endl;exit(1);} returntrue;

}elseif(e1<ptr->data)Insert(e1,ptr->left); //左子樹插入

elseif(e1>ptr->data)Insert(e1,ptr->right);//右子樹插入

elsereturnfalse; //x已在樹中,不再插入};78

注意參數表中引用型指針參數ptr的使用。利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。

79（1）被刪除的結點是葉子；（2）被刪除的結點只有左子樹或者只有右子樹；（3）被刪除的結點既有左子樹，也有右子樹。4．二叉排序樹的刪除算法可分三種情況討論：和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結點之后，仍然保持二叉排序樹的特性。8050308020908540358832（1）被刪除的結點是葉子結點例如:被刪關鍵字=2088其雙親結點中相應指針域的值改為“空”8150308020908540358832（2）被刪除的結點只有左子樹或者只有右子樹其雙親結點的相應指針域的值改為“指向被刪除結點的左子樹或右子樹”。被刪關鍵字=40808250308020908540358832（3）被刪除的結點既有左子樹，也有右子樹4040以其前驅替代之，然后再刪除該前驅結點被刪結點前驅結點被刪關鍵字=5083二叉搜索樹的刪除算法template<classE,classK>bool

BST<E,K>::Remove(constKx,

BstNode<E,K>*&ptr){//在以ptr

為根的二叉搜索樹中刪除含x的結點

BstNode<E,K>*temp;if(ptr!=NULL){if(x<ptr->data)Remove(x,ptr->left);

//在左子樹中執(zhí)行刪除

elseif(x>ptr->data)Remove(x,ptr->right);

//在右子樹中執(zhí)行刪除84

elseif(ptr->left!=NULL&&ptr->right!=NULL)

{//ptr指示關鍵碼為x的結點，它有兩個子女

temp=ptr->right;

//到右子樹搜尋中序下第一個結點

while(temp->left!=NULL)temp=temp->left;

ptr->data=temp->data;

//用該結點數據代替根結點數據

Remove(ptr->data,ptr->right);} else{ //ptr指示關鍵碼為x的結點有一個子女或者零個子女85

temp=ptr; if(ptr->left==NULL)ptr=ptr->right;elseptr=ptr->left;deletetemp;returntrue;} } returnfalse;};注意在刪除算法參數表引用型指針參數的使用。865．查找性能的分析

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關鍵字，構造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。87由關鍵字序列3，1，2，5，4構造而得的二叉排序樹，由關鍵字序列1，2，3，4，5構造而得的二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.288

下面討論平均情況:

不失一般性，假設長度為

n

的序列中有k

個關鍵字小于第一個關鍵字，則必有n-k-1

個關鍵字大于第一個關鍵字,由它構造的二叉排序樹：n-k-1k的平均查找長度是n

和k的函數P(n,k)(0kn-1)。89

假設n個關鍵字可能出現的n!種排列的可能性相同，則含n個關鍵字的二叉排序樹的平均查找長度：在等概率查找的情況下，9091由此可類似于解差分方程，此遞歸方程有解：92二、二叉平衡樹何謂“二叉平衡樹”？二叉平衡樹的查找性能分析如何構造“二叉平衡樹”93

二叉平衡樹是二叉查找樹的另一種形式，其特點為：樹中每個結點的左、右子樹深度之差的絕對值不大于1。例如:548254821是平衡樹不是平衡樹94

構造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉技術。例如:依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉一次先向右旋轉再向左旋轉95426589642895向左旋轉一次繼續(xù)插入關鍵字996右單旋轉左單旋轉

左右雙旋轉右左雙旋轉97插入左單旋轉ACEBDhhh-1h-1100BACEDhhh-1h211BhhCEAD00h-1h1左單旋轉98右單旋轉BACEDhhh-1h-2-1-1h插入hhh-1h-1ABDCE-100hhh-1BCEAD-100h99插入hhACEDh-1h-1BFG-100E左單旋轉GACDBFhhh-1h1-1-2

左右雙旋轉100右單旋轉AEhhCDh-1hBFG0-2-2FGDhAh-1CEB00-1hh101插入hhh-1h-1ACEDBFG100右單旋轉ACEBFGDhhhh-1102右左雙旋轉102ACEDBFGhhh-1h00-1hhh-1h左單旋轉ACEBFGD022103例如，輸入關鍵碼序列為{16,3,7,11,9,26,18,14,15}，插入和調整過程如下。160163-10左右雙旋731600073110-1116右單旋37169000111163701-273161190-1-223711269160112104右左雙旋0左單旋181600732611900031609171126183-1-17161426911127390182611-11611051518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程106

在平衡樹上進行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進行比較的關鍵字的個數不超過平衡樹的深度。平衡樹的查找性能分析：問：含n

個關鍵字的二叉平衡樹可能達到的最大深度是多少？107因此，在二叉平衡樹上進行查找時，查找過程中和給定值進行比較的關鍵字的個數和

log2(n)

相當。含有n

個結點的二叉平衡樹能達到的最大深度hn=log(5(n+1))-2。108

一、哈希表是什么？二、哈希函數的構造方法

三、處理沖突的方法

四、哈希表的查找7.3哈希表109以上兩節(jié)討論一、哈希表是什么？查找的過程為給定值依次和關鍵字集合中各個關鍵字進行比較，

查找的效率取決于和給定值進行比較的關鍵字個數。

用這類方法表示的查找表，其平均查找長度都不為零。110只有一個辦法：預先知道所查關鍵字在表中的位置，對于頻繁使用的查找表，希望ASL=0。即，要求：記錄在表中位置和其關鍵字之間存在一種確定的關系。111若以下標為000~999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關鍵字為學號，其值的范圍為xx000~xx999(前兩位為年份)。則查找過程可以簡單進行：取給定值（學號）的后三位，不需要經過比較便可直接從順序表中找到待查關鍵字。112上例在關鍵字與記錄在表中的存儲位置之間建立了一個函數關系，以f(key)作為關鍵字為key的記錄在表中的位置，通常稱這個函數f(key)為哈希函數。113{Zhao,Qian,

Sun,Li,Wu,Chen,Han,Ye,Dei}

例如：對于如下9個關鍵字設

哈希函數f(key)=

(Ord(第一個字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDei問題:

若添加關鍵字Zhou,怎么辦？能否找到另一個哈希函數？1141)哈希函數是一個映象，即：

將關鍵字的集合映射到某個地址集合上，

它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可；從這個例子可見：2)在一般情況下，很容易產生“沖突”現象，即：key1key2，而f(key1)=f(key2)。1153)很難找到一個不產生沖突的哈希函數。一般情況下，只能選擇恰當的哈希函數，使沖突盡可能少地產生。因此，在構造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產生沖突)的哈希函數之外；還需要找到一種“處理沖突”

的方法。116哈希表的定義：根據設定的哈希函數H(key)

和所選中的處理沖突的方法，將一組關鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關鍵字在地址集中的“象”作為相應記錄在表中的存儲位置，如此構造所得的查找表稱之為“哈希表”。117二、構造哈希函數的方法對數字的關鍵字可有下列構造方法：若是非數字關鍵字，則需先對其進行數字化處理。1.

直接定址法3.平方取中法5.除留余數法4.折疊法6.隨機數法2.數字分析法118哈希函數為關鍵字的線性函數

H(key)=key

或者

H(key)=akey+b1.

直接定址法此法僅適合于：地址集合的大小==關鍵字集合的大小119此方法僅適合于：

能預先估計出全體關鍵字的每一位上各種數字出現的頻度。2.

數字分析法假設關鍵字集合中的每個關鍵字都是由s位數字組成(u1,u2,…,us)，分析關鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。120

以關鍵字的平方值的中間幾位作為存儲地址。求“關鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關鍵字中各位的影響。3.平方取中法

此方法適合于:

關鍵字中的每一位都有某些數字重復出現頻度很高的現象。121

將關鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。4.折疊法此方法適合于:

關鍵字的數字位數特別多。1225.除留余數法

設定哈希函數為:H(key)=keyMODp1236.隨機數法設定哈希函數為:H(key)=Random(key)其中，Random為偽隨機函數

通常，此方法用于對長度不等的關鍵字構造哈希函數。124

實際造表時，采用何種構造哈希函數的方法取決于建表的關鍵字集合的情況(包括關鍵字的范圍和形態(tài))，總的原則是使產生沖突的可能性降到盡可能地小。125三、處理沖突的方法

“處理沖突”

的實際含義是：為產生沖突的地址尋找下一個哈希地址。1.開放定址法（閉散列）2.鏈地址法（開散列）126當沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)MODm，i=1,2,……k(km-1)其中：H(key)——哈希函數

m——哈希表表長

di——增量序列1.開放定址法127對增量

di

有三種取法：1)線性探測再散列

di=1,2,3,……m-12)二次探測再散列

di=12,-12,22,-22,…,±k2

km/23)隨機探測再散列

di

是一組偽隨機數列或者

di=i×H2(key)(又稱雙散列函數探測)128例如:

關鍵字集合

{19,01,23,14,55,68,11,82,36}設定哈希函數H(key)=keyMOD11(表長=11)1901231455681901231468若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突11823655118236112136251129用線性探查法組織的散列表的類定義

constint

DefaultSize=100;enum

KindOfStatus{Active,Empty,Deleted};

//元素分類(活動/空/刪)template<classE,classK>classHashTable{ //散列表類定義public:

HashTable(constint

d,int

sz=DefaultSize);

//構造函數

～HashTable(){delete[]ht;delete[]info;}

//析構函數

130

HashTable<E,K>&operator=

(constHashTable<E,K>&ht2);//表賦值

bool

Search(K

k1,E&e1)const; //搜索k1

bool

Insert(constE&e1); //插入e1

bool

Remove(constE&e1); //刪除e1voidmakeEmpty(); //置表空private:

int

divitor; //散列函數的除數

int

n,TableSize; //當前桶數及最大桶數

E*ht; //散列表存儲數組

KindOfStatus*info; //狀態(tài)數組

int

FindPos(Kk1)const; //散列函數

131

intoperator==(E&e1){return*this==e1;} //重載函數：元素判等

intoperator!=(E&e1){return*this!=e1;} //重載函數：元素判不等};132template<classE,classK> //構造函數HashTable<E,K>::HashTable(int

d,int

sz){

divitor=d; //除數

TableSize=sz;n=0; //表長

ht=new

E[TableSize]; //表存儲空間

info=newKindOfstatus[TableSize];for(int

i=0;i<TableSize;i++)

info[i]=empty;};133

template<classE,classK>int

HashTable<E,K>::FindPos(K

k1)const{//搜索在一個散列表中關鍵碼與k1匹配的元素，//搜索成功，則函數返回該元素的位置，否則返回//插入點（如果有足夠的空間）

int

i=k1%

divitor;

//計算初始桶號

int

j=i;

//j是檢測下一空桶下標使用線性探查法的搜索算法134

do{if(info[j]==Empty||info[j]==Active&&

ht[j]==k1)returnj; //找到初始桶號

j=(j+1)%TableSize; //找下一個空桶

}while(j!=i);returnj; //轉一圈回到開始點,表已滿,失敗};135

bool

HashTable<E,K>::Search(Kk1,E&e1){//使用線性探查法在散列表ht(每個桶容納一個元素)//中搜索k1

inti=FindPos(k1)；

//搜索

if(info[i]!=Active||ht[i]!=k1)returnfalse;

e1=ht[i];returntrue;};136在閉散列情形下不能真正刪除表中已有表項。刪除表項會影響其他表項的搜索。例如，若把關鍵碼為Broad的表項真正刪除，把它所在位置的info域置為Empty，以后在搜索關鍵碼為Blum和Alton的表項時就查不下去，會錯誤地判斷表中沒有關鍵碼為Blum和Alton的表項。137若想刪除一個表項,只能給它做一個刪除標記deleted進行邏輯刪除,不能把它真正刪去。邏輯刪除的副作用是：在執(zhí)行多次刪除后,表面上看起來散列表很滿,實際上有許多位置沒有利用。138template<classE,classK>bool

HashTable<E,K>::Insert(Kk1,

constE&e1){//在ht表中搜索k1。若找到則不再插入,若未找到,//但找到位置的標志是Empty或Deleted,x插入

使用線性探查法的其他操作139

int

i=FindPos(k1); //用散列函數計算桶號

if(info[i]!=Active){ //該桶空,存放新元素

ht[i]=e1;info[i]=Active;

n++;returntrue;}if(info[i]==Active&&ht[i]==e1)

cout<<“表中已有此元素，不能插入！\n”;elsecout<<“表已滿，不能插入！\n”;returnfalse;};140template<classE,classK>bool

HashTable<E,K>::Remove(Kk1,E&e1){//在ht表中刪除元素key,并在引用參數e1中得到它

int

i=FindPos(k1);if(info[i]==Active){

//找到要刪元素,且是活動元素

info[i]=Deleted;n--;

//做邏輯刪除標志,并不真正物理刪除

returntrue;} elsereturnfalse;};141線性探查方法容易產生“堆積”,不同探查序列的關鍵碼占據可用的空桶,為尋找某一關鍵碼需要經歷不同的探查序列,導致搜索時間增加。142將所有哈希地址相同的記錄都鏈接在同一鏈表中。

2.鏈地址法0123456140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:關鍵字集合{19,01,23,14,55,68,11,82,36}，哈希函數為H(key)=keyMOD7143使用開散列法的散列表類定義

#include<assert.h>constint

defaultSize=100;template<classE,classK>struct

ChainNode{

//各桶中同義詞子表的鏈結點定義

Edata; //元素

ChainNode<E,K>*link; //鏈指針};template<classE,classK>classHashTable{ //散列表(表頭指針向量)定義144public:

HashTable(int