數據結構c語言9課件

1第8章查找

8.1基本概念與基本運算8.2靜態(tài)查找表8.3動態(tài)查找表1——樹表8.4動態(tài)查找表2——哈希表查找

回顧1靜態(tài)查找表查找的ASL是？對應的時間復雜度2動態(tài)樹表查找的ASL，對應的時間復雜度3一個查找算法最理想的的時間復雜度應該是什么？4在數組中按編號查找某個元素的時間復雜度是？5對給定的查找表（數據元素的集合）能否把它們采用特別的方法組織到數組中呢？把數據元素的關鍵碼通過某種計算方法直接確它在數組中的存儲位置這樣構造的數組就是哈希表0m–1h(k1)h(k4)h(k3)U(universeofkeys)k1k2k3k5k43哈希表應用哈希函數，由記錄的關鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構成的表叫哈希表(數組的推廣）。4.哈希查找又叫散列查找，利用哈希函數進行查找的過程叫哈希查找。(注意到哈希表建立的時候用哈希函數）例30個地區(qū)的各民族人口統計表編號地區(qū)總人口漢族回族…...1北京2上海…...…...以編號作關鍵字，構造哈希函數：H(key)=keyH(1)=1H(2)=2以地區(qū)作關鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數：H(Beijing)=2H(Shanghai)=19H(Shenyang)=195.沖突

k1k2，但H(k1)=H(k2)的現象叫沖突(Collision)，映射到同一哈希地址上的關鍵碼稱為“同義詞”。

0m–1h(k1)h(k4)h(k3)U(universeofkeys)k1k2k3k5k48.4.2哈希函數的構造方法1.直接定址法【構造】

取關鍵字或關鍵字的某個線性函數作哈希地址，即

H(key)=key或H(key)=a·key+b

比如：統計1-100歲的人口，用年齡做關鍵字，哈希函授可以就取關鍵字本身?！咎攸c】直接定址法所得地址集合與關鍵字集合大小相等，不會發(fā)生沖突實際中能用這種哈希函數的情況很少2.數字分析法【構造】

對關鍵字進行分析，取關鍵字的若干位或其組合作哈希地址。

比如：取學號某些位排定學生宿舍號。

110611201

樓號層號房間號【特點】

適于關鍵字位數比哈希地址位數大，且可能出現的關鍵字事先知道的情況。例有80個記錄，關鍵字為8位十進制數，哈希地址為2位十進制數，怎么取合適？8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址4.折疊法構造：將關鍵字分割成位數相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加適于關鍵字位數很多，且每一位上數字分布大致均勻情況例關鍵字為：0442205864，哈希地址位數為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加5.除留余數法構造：取關鍵字被某個不大于哈希表表長m的數p除后所得余數作哈希地址，即

H(key)=keyMODp，pm特點簡單、常用，可與上述幾種方法結合使用p的選取很重要；p選的不好，容易產生同義詞6.隨機數法構造：取關鍵字的隨機函數值作哈希地址，即H(key)=random(key)適于關鍵字長度不等的情況【選取哈希函數應考慮的因素】計算哈希函數所需時間關鍵字長度哈希表長度（哈希地址范圍）關鍵字分布情況記錄的查找頻率8.4.3處理沖突的方法1開放定址法2再哈希方法3拉鏈方法4建立公共溢出區(qū)【分類】線性探測再散列：

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

di=12,-12,22,-22,32,……±k2(km/2)偽隨機探測再散列：

di=偽隨機數序列例表長為11的哈希表中已填有關鍵字為17，60，29的記錄，

H(key)=keyMOD11,現有第4個記錄，其關鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突

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

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

H3=(5+3)MOD11=8不沖突

38(2)H(38)=38MOD11=5沖突

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

H2=(5-12)MOD11=4不沖突38(3)H(38)=38MOD11=5沖突設偽隨機數序列為9，則：

H1=(5+9)MOD11=3不沖突382.再哈希法方法：構造若干個哈希函數，當發(fā)生沖突時，計算下一個哈希地址，即：

Hi=Rhi(key)i=1,2,……k其中：Rhi——不同的哈希函數特點：計算時間增加例已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函數為：H(key)=keyMOD13,

用鏈地址法處理沖突0123456789101112

14^127796855198420231011^^^^^^^^^^^^4.建立一個公共溢出區(qū)

設哈希函數產生的哈希地址集為[0，m-1]，則分配兩個表：一個基本表，每個單元只能存放一個元素；一個溢出表。只要關鍵碼對應的哈希地址在基本表上產生沖突，則所有這樣的元素一律存入溢出表中。查找時，對給定值通過哈希函數計算出哈希地址，先與基本表的單元比較，若相等，查找成功；否則，再到溢出表中進行查找。

例已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函數為：H(key)=keyMOD13,

哈希表長為m=16，

設每個記錄的查找概率相等(1)用線性探測再散列處理沖突，即Hi=(H(key)+di)MODmH(55)=3沖突，H1=(3+1)MOD16=4

沖突，H2=(3+2)MOD16=5H(79)=1沖突，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)MOD16=8

沖突，H8=(1+8)MOD16=90123456789101112131415ASL=(1*6+2+3*3+4+9)/12=2.514

168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1沖突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6沖突，H1=(6+1)MOD16=7

沖突，H2=(6+2)MOD16=8H(27)=1沖突，H1=(1+1)MOD16=2

沖突，H2=(1+2)MOD16=3

沖突，H3=(1+3)MOD16=4H(11)=11H(10)=10沖突，H1=(10+1)MOD16=11

沖突，H2=(10+2)MOD16=12(2)用鏈地址法處理沖突0123456789101112

14^127796855198420231011^^^^^^^^^^^^ASL=(1*6+2*4+3+4)/12=1.75關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)8.4.5哈希表算法實現 1線性探測哈希表的建立2線性探測哈希表的查找3拉鏈哈希表的建立4拉鏈哈希表的查找5哈希表的刪除1線性探測哈希表的建立voidCreateSeqHTbl(datetypeSeqHTbl[],intm,datatype*eptr){/*用線性探測法處理沖突建立散列表SeqHTbl*//*eptr為待放入散列表中的數據基址*//*Hash()為散列函數，m為散列表的長度*/

intd;for(i=0;i<m;i++)SeqHTbl[i]=0;/*散列表初始化，設0表示空*/while(eptr->data.key!=0){/*待放入散列表的元素，其關鍵碼0表示結束*/d=Hash(eptr->data.key);/*求當前元素的散列地址*/ while(SeqHTbl[d]!=0)d=(d+1)%m;SeqHTbl[d]=*eptr;/*找到空單元，填裝結點*/eptr++;} }2以線性探測法處理沖突構造的散列表中的查找intReSeqHTbl(datetypeSeqHTbl[],intm,keytypekey){/*SeqHTbl散列表，散列函數Hash()，m為散列表的長度*//*查找關鍵碼為key的元素，成功返回其地址，否則返回-1*/intd,begin;/*求當前元素的散列地址，并將起始點記錄在begin中*/begin=d=Hash(key);while(SeqHTbl[d].key!=0&&SeqHTbl[d].key!=key){d=(d+1)%m; if(d==begin){d=-1;break;}/*表滿且查找失敗*/

}if(SeqHTbl[d].key==0)d=-1;/*找到空單元，查找失敗*/returnd;/*查找成功返回的是地址，不成功為-1*/}3拉鏈法哈希表的建立存儲結構：

typedefstructhnode{datatypedata; /*關鍵字*/… /*其它信息*/structhnode*next;/*指向下一個同義詞的指針*/}HNode;

定義散列表（指針向量或指針數組）：

#definem…/*m為散列表的容量*/HNode*HashTbl[m];

以拉鏈法構造散列表的算法voidCreateLHTbl(HNode*LHashTbl[m],datatype*eptr){

/*用拉鏈法處理沖突建立散列表LHashTbl*//*eptr為待放入散列表中的數據基址，Hash()為散列函數*/

intd;HNode*q;

for(i=0;i<m;i++)LHashTbl[i]=NULL;/*散列表初始化*/

while(eptr->data.key!=0) {/*待放入散列表的元素，其關鍵碼0表示結束*/d=Hash(eptr->data.key);/*求當前元素的散列地址*/ q=(HNode*)malloc(sizeof(HNode));/*申請新結點*/ q->data.key=eptr->data.key; /*填裝結點信息*/…;

q->next=LHashTbl[d];/*插入到同義詞的鏈表*/LHashTbl[d]=q; //注意是向前插入 eptr++; /*指向下一個元素*/ }}