數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 8

第八章查找表★基本概念★靜態(tài)查找表★動態(tài)查找表★Hash法NorthChinaElectricPowerUniversity查找表：是一種以集合為邏輯結(jié)構(gòu)，以查找為核心運(yùn)算，同時(shí)包括其他運(yùn)算的數(shù)據(jù)結(jié)構(gòu)。關(guān)鍵字：用來標(biāo)識數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，簡稱鍵?！?.1基本概念

主關(guān)鍵字：可以唯一標(biāo)識一個(gè)數(shù)據(jù)元素的關(guān)鍵字。次關(guān)鍵字：可以標(biāo)識若干數(shù)據(jù)元素的關(guān)鍵字。

查找：根據(jù)某個(gè)給定的K值，在查找表中尋找一個(gè)鍵值等于K的元素，若找到這樣的元素，則稱查找成功，此時(shí)的運(yùn)算結(jié)果為該數(shù)據(jù)元素在查找表中的位置，否則稱查找不成功，運(yùn)算結(jié)果為一特殊標(biāo)志。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity查找表靜態(tài)查找表動態(tài)查找表1.建表：Create(st)2.查找：Search(st,k)3.讀表元：Get(st,pos)2.查找：Search(st,k)3.讀表元：Get(st,pos)1.初始化：Initiate(st)4.插入：Insert(st,k)5.刪除：Delete(st,k)NorthChinaElectricPowerUniversity★8.2靜態(tài)查找表1)順序表上的查找：以順序表作為存儲結(jié)構(gòu)，然后在這個(gè)存儲結(jié)構(gòu)上實(shí)現(xiàn)靜態(tài)查找表的基本運(yùn)算。順序表類型定義如下：#definemaxsize

靜態(tài)查找表的表長typedef

struct

{

keytypekey;//關(guān)鍵字

………//其他域}rec;typedef

struct

recsqtable[maxsize+1];intn;//最后一個(gè)數(shù)據(jù)元素的下標(biāo)順序查找過程：假定該查找表有n個(gè)記錄，首先將要查找的那個(gè)關(guān)鍵字賦給實(shí)際上并不存在的第n+1個(gè)記錄的關(guān)鍵字域，然后從頭開始一個(gè)一個(gè)的向下查找，用i來計(jì)數(shù),查到就送出來看i是第幾個(gè)，若i<=n，則查找成功，若i=n+1則查找失敗。NorthChinaElectricPowerUniversityvoidseqsrch(sqtabler，keytypek){//在長度為n的表r中查找關(guān)鍵字為k的元素，r[n]為表尾的擴(kuò)充;i指示查找結(jié)果

r[n].key=k;i=0;//給監(jiān)督哨賦值

while(r[i].key!=k)i++;if(i<n)

printf(“succ,i=%d”,i);//查找成功，i指示待查元素在表中位置

else

printf(“unsucc”);//i=n時(shí)表明查找不成功}NorthChinaElectricPowerUniversity平均查找長度：為確定某元素在表中某位置所進(jìn)行的比較次數(shù)的期望值。在長度為n的表中找某一元素，查找成功的平均查找長度:

ASL=∑PiCiPi:為查找表中第i個(gè)元素的概率Ci

:為查到表中第i個(gè)元素時(shí)已經(jīng)進(jìn)行的比較次數(shù)NorthChinaElectricPowerUniversity在順序查找時(shí)，Ci取決于所查元素在表中的位置，

Ci=i,設(shè)每個(gè)元素的查找概率相等，即Pi=1/n,則:

ASL=∑PiCi=(n+1)/2查找不成功的查找長度為n+1。順序查找表的優(yōu)點(diǎn)：算法簡單且適應(yīng)面廣，對表的結(jié)構(gòu)無任何要求，無論元素是否按關(guān)鍵字有序都可應(yīng)用。順序查找表的缺點(diǎn)：平均查找長度比較大，特別是當(dāng)n較大時(shí)，查找效率較低。NorthChinaElectricPowerUniversity2)折半查找(有序表上進(jìn)行查找)：基本思想：設(shè)三個(gè)指針low,high和mid分別指示待查有序表的表頭，表尾和中間元素，在開始查找時(shí)，三個(gè)指針的初值分別為：low=1;high=n;mid=(low+high)div2。折半查找是從表的中間元素開始，用待查元素的關(guān)鍵字k和r[mid].key比較，此時(shí)有三種情況(假設(shè)該查找表按關(guān)鍵字的非遞減次序排列)：1)若r[mid].key=k，則查找成功；2)若r[mid].key>k，則k必在較低標(biāo)號的那一半表中，令high=mid-13)若r[mid].key<k，則k必在較高標(biāo)號的那一半表中，令low=mid+14)再取中間項(xiàng)進(jìn)行比較，直到查找成功或low>high(查找失敗)為止。NorthChinaElectricPowerUniversity例：給出表元素關(guān)鍵字為：{05,13,19,21,37,56,64,75,80,88,92}1.查找關(guān)鍵字k=21的情況(1)low=1;high=11;mid=(1+11)div2=60513192137566475808892lowmidhigh因?yàn)閞[mid].key>k，所以向左找，令high=mid-1=5(2)low=1;high=5;mid=(1+5)div2=30513192137566475808892lowmidhigh因?yàn)閞[mid].key<k，所以向右找，令low=mid+1=4(3)low=4;high=5;mid=(4+5)div2=40513192137566475808892lowmidhigh因?yàn)閞[mid].key=k，查找成功，所查元素在表中的序號為mid的值NorthChinaElectricPowerUniversity(1)low=1;high=11;mid=(1+11)div2=6因?yàn)閞[mid].key<k，所以向右找，令low=mid+1=7(2)low=7;high=11;mid=(7+11)div2=90513192137566475808892lowmidhigh因?yàn)閞[mid].key<k，所以向右找，令low=mid+1=10(3)low=10;high=11;mid=(10+11)div2=100513192137566475808892lowmidhigh因?yàn)閞[mid].key>k，所以向左找，high=mid-1=92.查找關(guān)鍵字k=85的情況0513192137566475808892lowmidhigh因?yàn)閘ow>high，所以查找失敗NorthChinaElectricPowerUniversityvoidBinsrch(sqtabler，keytypek)//在長度為n的有序表r中查找關(guān)鍵字為k的元素，查到后輸出{low=1；high=n；//置初值

while(low<=high){mid=(low+high)/2；

if(k==r[mid].key){printf("succi=%d\n"，mid)；break；}elseif(k>r[mid].key)low=mid+1；//向右找

elsehigh=mid-1；//向左找

}if(low>high)

printf("no

succ\n")；//low>high，查找不成功}NorthChinaElectricPowerUniversityVoidBinSearch(sqtabler;keytypek;intl,h){low=l;high=h;ifhigh<low{printf("no

succ\n");break；}mid=(low+high)div2;

Switch(k){casek>r[mid].key:low=mid+1;BinSearch(r,k,low,high);break;casek=r[mid].key:

printf("succi=%d\n"，mid)；break;casek<r[mid].key:high:=mid-1;BinSearch(r,k,low,high);break;default;}}遞歸算法描述如下：算法的性能分析：NorthChinaElectricPowerUniversity以上面的11個(gè)元素的查找表為例，找到第6個(gè)元素僅需比較1次；找到第3個(gè)和第9個(gè)元素需比較2次；找到第1,4,7和10個(gè)元素需比較3次；找到第2,5,8和11個(gè)元素需比較4次。上面的查找過程可以用下圖所示的一棵二叉樹來表示。6391471011258樹中每一個(gè)結(jié)點(diǎn)表示表中的一個(gè)數(shù)據(jù)元素，結(jié)點(diǎn)中的值為該元素在表中的位置折半查找的平均查找長度為log2(n+1)-1找到元素的過程：正好是從根節(jié)點(diǎn)一直走到某個(gè)葉子節(jié)點(diǎn)的路徑，因此所用的比較次數(shù)最多等于樹的深度。由此看來，無論元素找到或找不到,查找某一元素的比較次數(shù)最多等于樹的深度.即log2n。

那么引出一個(gè)問題，折半查找的平均查找長度是多少?ASLnS=∑CiPi=1/n∑j*2j-1

i=1nj=1n=(n+1/n)*log2(n+1)-1NorthChinaElectricPowerUniversity那么表的長度一定為n=2h-1,我們假定表中每個(gè)元素的查找概率相等.(Pi=1/n),則平均查找長度為:我們用深度為h的滿二叉樹描述折半查找來進(jìn)行分析。滿二叉樹的特點(diǎn)是：層次為1的結(jié)點(diǎn)有1個(gè);

層次為2的結(jié)點(diǎn)有2個(gè);…,

層次為h的結(jié)點(diǎn)為2h-1

個(gè)。若是滿二叉樹則節(jié)點(diǎn)數(shù)n=2h-1NorthChinaElectricPowerUniversity3)分塊查找:這種查找方法是表里的元素均勻的分成若干塊，塊與塊之間是有序的，塊中的元素是無序的，這種查找方法又稱為索引順序查找。在分塊查找中對每一塊建立一個(gè)索引項(xiàng)，其中包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)(其值為最大關(guān)鍵字或最小關(guān)鍵字)和指針項(xiàng)(指示該塊的第1個(gè)記錄在表中的位置)。索引表按關(guān)鍵字有序，表分塊有序。分塊有序：指第二塊中所有記錄的關(guān)鍵字均大于(或小于)第一塊中最大(或最小)關(guān)鍵字，第三塊中的所有關(guān)鍵字均大于(或小于)第二塊中的最大(或最小)關(guān)鍵字…,以此類推。例:有一個(gè)表,各元素的關(guān)鍵字為:｛22,12,13,9,8,33,42,44,38,24,48,60,58,74,47}

把它平均分成三塊，按上升的次序排列，如下圖所示：NorthChinaElectricPowerUniversity2212139833424438244860587447123456789101112131415第一塊第二塊第三塊1611224474關(guān)鍵字表小大指針表:應(yīng)該指向各塊的第一個(gè)關(guān)鍵字。分成三塊每塊5個(gè)關(guān)鍵字分塊查找的方法:1)由于索引表按關(guān)鍵字有序，則確定k在哪一塊的查找可以用順序查找，也可用折半查找。

分塊查找的平均查找長度應(yīng)該是前兩者之和：即：ASLbs=Lb+Lw用順序查找方法,確定所在的塊,則Lb=1/b∑j

j=1b用順序查找方法,查找的元素所在位置,則Lw=1/s∑ii=1s

已知表的長度為n,分成b小塊,每塊有s個(gè)元素,那么b=n/s.若表中各元素的查找概率相等,那么每塊的查找概率為1/b,塊中每個(gè)元素的查找概率為1/s.

Lb:為查找所在塊的平均查找長度。

Lw:為塊中查找元素的平均查找長度。

2)塊中的記錄是任意排列的，則在塊中只能用順序查找。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityASLbs=1/b∑j+1/s∑i=(b+1)/2+(s+1)/2=1/2(n/s+s+2)=1/2(n/s+s)+1

j=1bi=1s可以證明:當(dāng)s=時(shí)，平均查找長度最小=+1由上式可以看出，分塊查找的平均查找長度不僅和表的長度n有關(guān)，而且和每一塊中的元素個(gè)數(shù)s有關(guān)。nn用折半查找確定所在的塊，則分塊查找的平均查找長度為ASLbs=log2(b+1)-1+(s+1)/2=log2(n/s+1)+(s-1)/2NorthChinaElectricPowerUniversity三種查找方法的比較:

就平均查找長度而言，折半查找最小，分塊查找次之，順序查找最大。就表的結(jié)構(gòu)而言，順序查找對有序表和無序表均可應(yīng)用，折半查找僅適用有序表，而分塊查找要求表中數(shù)據(jù)是分塊有序的，即需要把表分成若干塊，塊與塊之間的記錄按關(guān)鍵字有序。就表的存儲結(jié)構(gòu)而言，順序查找和分塊查找對兩種存儲結(jié)構(gòu)--向量和鏈表均適用，而折半查找只適用于以向量做存儲結(jié)構(gòu)的的表，這就要求表中的元素基本不變，否則，當(dāng)進(jìn)行插入和刪除運(yùn)算時(shí)為保持表的有序性，便要移動元素，這在一定程度上降低折半查找的效率?！?.3動態(tài)查找表二叉排序樹：或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

1)若它的左子樹不空，則它的左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

2)若它的右子樹不為空，則它的右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；

3)它的左、右子樹均為二叉排序樹。NorthChinaElectricPowerUniversity二叉排序樹的構(gòu)造方法：設(shè)R={R1,R2,…,Rn}為一數(shù)列,按下面的原則建立二叉樹：

1)令R1為二叉樹的根；

2)若R2<R1，則令R2為R1的左子樹的根結(jié)點(diǎn)，否則令

R2為R1的右子樹的根結(jié)點(diǎn)；

3)對R3,R4,…Rn重復(fù)上述步驟2)；NorthChinaElectricPowerUniversity例：給定R={10,18,3,8,12,2,7,3}按上面的原則構(gòu)造二叉排序樹如下：R4R7R2R2R2比R1大1018R3R3<R110183R4<R1左邊R4>R3右邊101838R5R5>R1右邊R5<R2左邊10183812R6R6<R1左邊R6<R3左邊101838122R1為根節(jié)點(diǎn)R1101018381227R7<R1左邊R7>R3右邊R&<R4左邊10183812273R8R8<R1左邊R8>R3右邊R8<R4左邊R8<R7左邊NorthChinaElectricPowerUniversity二叉排序樹的類型:structtree{intdata;

structtree*lchild;

structtree*rchild;};typedef

structtreetreenode;typedef

treenode*btree;NorthChinaElectricPowerUniversityvoidbsinsert(treenodes，btreet)//將指針s所指結(jié)點(diǎn)插入到根指針為t的二叉樹排序樹中去{if(t==NULL)t=s;elseif(s->data<t->data)

bsinsert(s，t->Lchild);else

bsinsert(s，t->Rchild);}//bsinsertvoidsortree(m,r[m],p)//建立一個(gè)有m個(gè)結(jié)點(diǎn)r[i](0<=i<=m-1)的二叉排序樹，p為指向二叉樹根的指針{q=malloc(sizeof(treenode));q->data=r[0];q->Lchild=NULL;q->Rchild=NULL;p=q;

for(i=1;i<m;i++){q=malloc(sizeof(treenode));q->data=r[i];q->Lchild=NULL;q->Rchild=NULL;

bsinsert(q，p);}}//sorttreeNorthChinaElectricPowerUniversity二叉排序樹的查找已知要找的那個(gè)記錄的關(guān)鍵字k,從根結(jié)點(diǎn)的關(guān)鍵字開始比較，有下列三種情況：

1)若兩者相等,則說明查找成功,根結(jié)點(diǎn)的記錄為所找記錄;2)若k小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)查找左子樹;3)若k大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)查找右子樹;4)若二叉樹為空，則查找失敗。NorthChinaElectricPowerUniversityvoidsortsrch(bitreptr

t,ElemTypek)//在指針t所指的二叉排序樹中，查找關(guān)鍵字為k的結(jié)點(diǎn){ift==NULL

printf(“unsucc”);//樹已空查找不成功

elseif(k==t->key){printf(“succ”);

outdata();//查找成功，并輸出信息

}elseif(k<t->key)

sortsrch(t->Lchild,k);else

sortsrch(t->Rchild,k);}NorthChinaElectricPowerUniversity非遞歸算法如下：voidsearch(bitreptr

I,bitreptrt,ElemTypek)//在二叉排序樹t中查找k。每個(gè)結(jié)點(diǎn)有三個(gè)字段：Lchild，key，Rchild。若k不//在t中，則送回B=1。否則送回i，結(jié)果i->key=k。//設(shè)Lchild（空二叉樹）=Rchild（空二叉樹）=0{i=t;B=1;//當(dāng)B=0時(shí)，查找成功，否則失敗

while((i!=NULL)&&(B==1)){if(k<i->key)i=i->Lchild;//查找左子樹

elseif(k=i->key){B=0;

printf(“succ%d”,i);}elsei=i->Rchild;//查找右子樹

}}//searchNorthChinaElectricPowerUniversity二叉排序樹在查找過程中的插入、刪除1)二叉排序樹的插入：給定關(guān)鍵字x,如果x在二叉排序樹中，送出指向x所在結(jié)點(diǎn)的指針，否則將x插入到二叉排序樹的合適位置上。voidBST(bitreptr

t,bitreptr

j,ElemTypex)//在二叉排序樹中查找一個(gè)結(jié)點(diǎn)的關(guān)鍵字x，若x已不在表中，則將它放在適當(dāng)?shù)奈恢?。?dāng)B=0時(shí)，查找成功，否則沒查到{j=t;B=1;p=NULL;

while((j!=NULL)&&(B==1)){if(x<j->key){p=j;j=j->Lchild;}elseif(x==j->key){B=0;printf(“succ，%d”，j);}else{p=j;j=j->Rchild;}}

NorthChinaElectricPowerUniversityif(B==1){j=(bitreptr)malloc(sizeof(btnode));j->key=x;j->Lchild=NULL;j->Rchild=NULL;if(t==NULL)t=j;elseif(x<p->key)p->Lchild=j;elseif(x>p->key)p->Rchild=j;}}NorthChinaElectricPowerUniversity2)二叉排序樹的刪除：在二叉排序中刪除某個(gè)結(jié)點(diǎn)，刪除此結(jié)點(diǎn)后仍保持二叉排序樹的性質(zhì)。下面這棵二叉排序樹，我們要?jiǎng)h除結(jié)點(diǎn)2：

2是根結(jié)點(diǎn)，它有左、右子樹，要?jiǎng)h除2,就要找一個(gè)新的根結(jié)點(diǎn)，從哪兒找呢?從左子樹，在左子樹中找一個(gè)值最大的結(jié)點(diǎn)，此結(jié)點(diǎn)僅次于根節(jié)點(diǎn)，比右子樹的所有結(jié)點(diǎn)都小，讓這個(gè)結(jié)點(diǎn)做為根結(jié)點(diǎn)。4261312416312pq,jsNorthChinaElectricPowerUniversity在算法中用了4個(gè)指針：

j:指向被刪除結(jié)點(diǎn);p:指向被刪除結(jié)點(diǎn)的雙親;

s:指向新選擇的根結(jié)點(diǎn);q:指向新選擇的根結(jié)點(diǎn)的雙親;

下面分四種情況進(jìn)行討論：

NorthChinaElectricPowerUniversity①被刪結(jié)點(diǎn)是葉子結(jié)點(diǎn)即j->lchild=Null;j->rchild=Null

s=Null為選擇的合適結(jié)點(diǎn)由于刪去葉子結(jié)點(diǎn)不影響二叉排序樹的結(jié)構(gòu)和性質(zhì)，所以只需修改其雙親結(jié)點(diǎn)的指針即可。若被刪結(jié)點(diǎn)是p

的左子樹，則s=p->lchild;若被刪結(jié)點(diǎn)是p的右子樹，則s=p->rchild。NorthChinaElectricPowerUniversity②被刪結(jié)點(diǎn)不是葉子，j無左，僅有右子樹，則

s=j->rchild,s做p的左(或右)子樹。41361243612③被刪結(jié)點(diǎn)不是葉子，j有左，無右子樹，則

s=j->lchild,s做p的左(或右)子樹pjs43261242612pjsNorthChinaElectricPowerUniversity④j既有左，又有右。則沿j的左子樹的右子樹方向找，一直找到按中序遍歷j的直接前趨結(jié)點(diǎn)。此結(jié)點(diǎn)作為新選的根結(jié)點(diǎn)s,然后做相應(yīng)的指針修改。2010306153913188pjqs20930615381318在上圖中，s->rchild=Null;s->lchild!=Null修改四個(gè)指針：1)s->rchild=j->rchild;2)q->rchild=s->lchild;3)s->lchild=j->lchild;4)p->lchild=s;NorthChinaElectricPowerUniversity201030615391318pjqs2093061531318在上圖中，s->rchild=s->lchild=Null,仍做前面的四個(gè)操作。2093061531318pj,qs206303151318上圖中，s->rchild=Nill,且q=j,修改兩個(gè)指針：

1)s->rchild=j->rchild;2)p->lchild=s;NorthChinaElectricPowerUniversity下面給出在二叉排序樹T中查找結(jié)點(diǎn)j,使j->key=x，如果x在T中，則刪除x結(jié)點(diǎn)，否則,送出B=1，說明此樹中無被刪結(jié)點(diǎn)的算法：voiddet(bitreptr

t,bitreptrj,ElemTypex)//j指向被刪結(jié)點(diǎn)，p指向其雙親，假設(shè)樹不空{(diào)j=t;B=1;

while((j!=NULL)&&(B==1)){if(x<j->key){p=j;j=j->Lchild;}elseif(x==j->key)B=0;elseif(x>j->key){p=j;j=j->Rchild;}}//以上過程是查找過程N(yùn)orthChinaElectricPowerUniversity

if(B==0){if(j->Lchild==NULL)//被刪結(jié)點(diǎn)無左子樹

s=j->Rchild;elseif(j->Rchild==NULL)//j有左，要判j是否有右

s=j->Lchild;else{q=j;s=q->Lchild;while(s->Rchild==NULL)//從左沿右找新結(jié)點(diǎn)

{q=s;s=s->Rchild;}s->Rchild=j->Rchild;if(q!=j){q->Rchild=s->Lchild;s->Lchild=j->Lchild;}}if(j==p->Lchild)p->Lchild=s;elsep->Rchild=s;//若被刪的結(jié)點(diǎn)是p的左，則讓s做為p的左，否則s做為p的右子樹

}}平衡二叉樹：或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。例:2-1=10-0=01-0=10-0=0平衡二叉樹2-3=-11-1=00-0=00-2=-21-0=10-0=0非平衡二叉樹ABCDABCDFG0-0=0ENorthChinaElectricPowerUniversity8.3.2平衡二叉樹(balancedbinarytree)平衡因子：二叉樹中任一結(jié)點(diǎn)的左子樹的深度與它的右子樹的深度之差稱為平衡因子。二叉排序樹的平衡化

假設(shè)表中的關(guān)鍵字序列為(13,24,37,90,53)①空樹和一個(gè)結(jié)點(diǎn)的二叉樹顯然是平衡二叉樹.②插入24后仍平衡131324-101324

2437RR型即逆時(shí)針旋轉(zhuǎn)

③插入后結(jié)點(diǎn)的平衡因子為0-2=-2，不平衡37130-1-2132437把從的右下側(cè)左轉(zhuǎn)到的右上側(cè)241313原來的左為的右,新的的左為24132413NorthChinaElectricPowerUniversity④插入90,53后,又失去平衡,可經(jīng)過下列步驟轉(zhuǎn)化為平衡二叉02_101324379053RL型的第一次旋轉(zhuǎn)(順時(shí)針)1324539037RL型的第二次旋轉(zhuǎn)(逆時(shí)針)第一次旋轉(zhuǎn)(順時(shí)針)以為軸心,把從的右上,轉(zhuǎn)到的右下,的右是,的右為,原的右變成新的左。53905353375353905390以為軸心,把從的左上轉(zhuǎn)到的左下,使得的左是;右是，原的左變成了的右。533753535337905337NorthChinaElectricPowerUniversity

一般情況下，假設(shè)由于二叉排序樹上插入結(jié)點(diǎn)而失去平衡的最小子樹的根結(jié)點(diǎn)指針為a（即a是離插入結(jié)點(diǎn)最近,且平衡因子絕對值超過1的祖先結(jié)點(diǎn)），則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為下列四種情況:⒈RR型平衡旋轉(zhuǎn):aba1b1

br-2-1hh-1h-1插入節(jié)點(diǎn)

把結(jié)點(diǎn)b從a的右下側(cè)逆時(shí)針(左轉(zhuǎn))轉(zhuǎn)到a的右上側(cè)，原b的左成為a的右，新b的左為a。NorthChinaElectricPowerUniversityba

bra1b1RR0hh-10h-12.LL型平衡旋轉(zhuǎn):LL21hh-1h-1ab

ar

brb1

把結(jié)點(diǎn)b從左下側(cè)順轉(zhuǎn)(右轉(zhuǎn))轉(zhuǎn)到a的左上側(cè),原b的右成為a的左,新b的右為a。3.RL型平衡旋轉(zhuǎn):RL(順時(shí)針)-21h-11h-1a1cc1

cr

brh-1h-2abNorthChinaElectricPowerUniversityab1

br

ar00bhh-1

c1

a1

cr

bracbh-1h-2h-1h-1-1-1-2

以c為軸心，把b從c的右上側(cè)順時(shí)針（右轉(zhuǎn))到c的右下側(cè)，從而a的右是c，c的右是b，原c的右變成b的左。

以c為軸心，把a(bǔ)從c的左上方，轉(zhuǎn)到c的左下方，使得c的左是a，右是b，原c的左子樹變成a的右。RL(逆時(shí)針)4.LR型平衡旋轉(zhuǎn):

以c為軸心把b從c的左上側(cè)，逆時(shí)針（左轉(zhuǎn)）到c的左下側(cè)，從而a的左是c,c的左是b，原c的左變成新b的右。NorthChinaElectricPowerUniversity

c1

a1

cr

bracbh-1h-2h-1h-1-1-1-2

c1

a1

cr

brcabh-1h-2h-1-100LR(逆時(shí)針)2-11h-1h-1h-2

arc1

crb1h-1LR(順時(shí)針)

再以c為軸心，把a(bǔ)從c的左上方轉(zhuǎn)到c的右下方，使得c的右是a，左是b，原c的右子樹變成a的左。abcNorthChinaElectricPowerUniversityc1

ar

cr

blacbh-1h-1h-2h-1022ac1

ar

cr

blcbh-1h-1h-2h-1022c1

ar

cr

blcbah-10h-2h-1-10例1將關(guān)鍵字集合K={60，40，49，23，25，13，95，196，85}6006040106040490-12604049000LR60404901123060404902223-1250602549001230400LR060254900123400602549012231400130LL602549002314013000602549-1-2231401300-295-21260RR9525490-2231401300-2126160085-1RL9525600-123149130001260400850縱觀以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)，有一個(gè)共同點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系，因此，查找的過程為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。因此，用這類方法表示的查找表，其平均查找長度都不為零，不同表示方法的差別僅在于：和給定值進(jìn)行比較的關(guān)鍵字的順序不同。對于頻繁使用的查找表，希望ASL=0。即不需要從“比較”的結(jié)果來確定查找成功，只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，也就是說，記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。★Hash法什么是Hash表？NorthChinaElectricPowerUniversity例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為xx000--xx999(前兩位為年份)。則可以下標(biāo)為000--999的順序表表示之。由于關(guān)鍵字和記錄在表中的序號相同，則不需要經(jīng)過比較即可確定待查關(guān)鍵字。但是，對于動態(tài)查找表而言，1)表長不確定；2)在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。因此，一般情況，需建立一個(gè)函數(shù)關(guān)系，以f(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個(gè)函數(shù)f(key)為哈希函數(shù)。(注意：這個(gè)函數(shù)并不一定是數(shù)學(xué)函數(shù))簡單地說，哈希表是基于哈希函數(shù)建立的一種查找表。NorthChinaElectricPowerUniversity例如：對于如下9個(gè)關(guān)鍵字{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}138961114122設(shè)

從這個(gè)例子可見，哈希函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可;由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1<>key2，而f(key1)=f(key2),并且，改進(jìn)哈希函數(shù)只能減少沖突，而不能避免沖突。NorthChinaElectricPowerUniversity因此，在設(shè)計(jì)哈希函數(shù)時(shí)，一方面要考慮選擇一個(gè)“好”的哈希函數(shù);另一方面要選擇一種處理沖突的方法。所謂“好”的哈希函數(shù)，指的是，對于集合中的任意一個(gè)關(guān)鍵字，經(jīng)哈希函數(shù)“映象”到地址集合中任何一個(gè)地址的概率是相同的。稱這類哈希函數(shù)為“均勻的”哈希函數(shù)。根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，這種表被稱為哈希表。Hash法的關(guān)鍵在于哈希表的構(gòu)造和沖突的處理NorthChinaElectricPowerUniversity哈希函數(shù)的構(gòu)造方法對數(shù)字的關(guān)鍵字可有下列哈希函數(shù)的構(gòu)造方法，若是非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理。例有一個(gè)從1到100歲的人口數(shù)字統(tǒng)計(jì)表,用年齡做關(guān)鍵字，它采用的hash函數(shù)是第一種H(K)=K,即j=k。地址010203…25262728…100年齡123…25262728…100人數(shù)300020005000…1020207070017200…10NorthChinaElectricPowerUniversity1.直接定址法

哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key或者H(key)=a*key+b

僅限于：地址集合的大小=關(guān)鍵字集合的大小2.數(shù)字分析法例有七個(gè)8位十進(jìn)制的關(guān)鍵字（有七個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字都具有八位十進(jìn)制數(shù)），將其散列在地址為10-90的表中。

①②③④⑤⑥⑦⑧地址

k1：5424224242k2：5428136783k3：5422281728k4：5423896739k5：5425415751k6：5426853765k7：5421935513僅限于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(k1,k2,…,kn)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。NorthChinaElectricPowerUniversity3.平方取中法若關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象，則先求關(guān)鍵字的平方值，以通過“平方”擴(kuò)大差別,同時(shí)平方值的中間幾位受到整個(gè)關(guān)鍵字中各位的影響。4.折迭法

若關(guān)鍵字的位數(shù)特別多，則可將其分割成幾部分，然后取它們的疊加和為哈希地址。相加的方法有移位法和折疊法。折疊法：把一關(guān)鍵字看承一張紙條，從一端向另一端沿邊界逐層折疊，再把相應(yīng)的位數(shù)加在一起。移位法：將各部分的最后一位對齊，然后相加。假定關(guān)鍵字:K=d1d2d3…drdr+1…d2rd2r+1…d3r允許有的存儲地址有r位。NorthChinaElectricPowerUniversity移位法：d1d2…drdr+1dr+2…d2r+d2r+1d2r+2…d3r高進(jìn)位不要了得到r位的存儲地址折疊法:d3rd3r-1…d2r+1dr+1dr+2…d2r+drdr-1…d1d1'd2'…dr'高進(jìn)位不要了得到r位的存儲地址例如：K=32834872，允許存儲地址為三位十進(jìn)制數(shù)。位移法：328折疊法：27348348

+72+8237481198H(K)=748H(K)=198NorthChinaElectricPowerUniversity5.除留余數(shù)法

實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。例有一組關(guān)鍵字從000001-859999，指定的存儲單元地址為1000000-1005999,即m=6000。選p=5999k=172148r=(172148)mod5999=4176(mod5999)f=1000000+r=1004176

在這里選擇p是關(guān)鍵步驟，若P為偶數(shù)，則凡是奇數(shù)的關(guān)鍵字，

都轉(zhuǎn)換為奇數(shù)地址，則凡是偶數(shù)的關(guān)鍵字地都轉(zhuǎn)換為偶數(shù)地址，顯然會出現(xiàn)沖突。一般情況：(1)P盡量接近m;(2)p為質(zhì)數(shù)。NorthChinaElectricPowerUniversity設(shè)給出關(guān)鍵字k，存儲單元數(shù)為m,則可選一數(shù)p(p<=m)去除k得到余數(shù)r(以p為模)，再用一線性函數(shù)f將r轉(zhuǎn)換為散列地址j,即r=(k)modp,j=f(r)§8.3.2處理沖突的方法

處理沖突的方法開放定址法鏈地址法線性探測再散列二次探測再散列偽隨機(jī)探測再散列探測：檢查關(guān)鍵字是否與hash向量元素相匹配。NorthChinaElectricPowerUniversity一、開放定址法假設(shè)哈?？臻g為T(0:m-1),哈希函數(shù)為j=H(key)。為求得下一個(gè)哈希地址，可取ji=(j+di)MODm，i=1,2,3,...,s(s≥1),其中m為哈希表的表長di為增量序列。1.當(dāng)取di=1,2,3,....,s時(shí)稱為線性探測再散列

例如：有一個(gè)關(guān)鍵字序列19,70，33，已存入長度為16的哈希表中。取哈希函數(shù)為除留余數(shù)法:j=kMOD13；NorthChinaElectricPowerUniversity01…45678…15……70193318現(xiàn)在要把關(guān)鍵字為18的記錄填入表中：j=18MOD13=5沖突1次j3=(5+3)MOD16=8不沖突Hash地址是否沖突沖突次數(shù)j1=(5+1)MOD16=6沖突2次j2=(5+2)MOD16=7沖突3次j=19MOD13=6；j=70MOD13=5；j=33MOD13=7NorthChinaElectricPowerUniversity

2.當(dāng)取di=12,-12,22,-22,…,n2,-n2

時(shí)稱為:

二次探測再散列仍以上例為例，70，19，33已填入哈希表中，再填入關(guān)鍵字為18的記錄:01…45678…15……70193318j=18MOD13=5沖突1次Hash地址是否沖突沖突次數(shù)j2=(5-1)MOD16=4不沖突

j1=(5+1)MOD16=62次沖突NorthChinaElectricPowerUniversity01…45678…15……70193323.當(dāng)取di=偽隨機(jī)序列時(shí)稱為偽隨機(jī)探測再散列偽隨機(jī)序列：隨機(jī)產(chǎn)生的n個(gè)隨機(jī)數(shù)，表示為

d1,d2,…,dn

偽隨機(jī)函數(shù)為:di

=(a*di-1+b)ModQ

j=18MOD13=5沖突1次18仍用上例為例，19，70，33已存入再填入18，若偽隨機(jī)數(shù)序列為13，15，7，2，35，…Hash地址是否沖突沖突次數(shù)j1=(5+13)MOD16=2不沖突NorthChinaElectricPowerUniversity說明：線性探測法可以探測到哈希表中的各個(gè)位置，但它容易產(chǎn)生“堆聚”現(xiàn)象。例如，關(guān)鍵字為21的記錄，由哈希函數(shù)得到哈希地址為8，則產(chǎn)生沖突。但是這種沖突不是由同義詞所引起的，而是在解決同義詞沖突的過程中又添加出的非同義詞沖突。這種現(xiàn)象會使探測次數(shù)增加，對查找極為不利。NorthChinaElectricPowerUniversity二次探測法可減少“堆聚”，但由于它不能保證探測到哈希表中的所有位置，所以即使哈希表未滿，也有可能探測不到“空”的位置。（只有當(dāng)m=4j+3(j=1,2,3...)時(shí)才能探測到整個(gè)哈希表空間。）

偽隨機(jī)探測法可較好地避免“堆聚”，但應(yīng)該要求所使用的偽隨機(jī)數(shù)序列能均勻地取[0:m-1]中的數(shù)。NorthChinaElectricPowerUniversi