數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言9課件

1第8章查找

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

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

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

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

取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址，即

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

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

對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址。

比如：取學(xué)號(hào)某些位排定學(xué)生宿舍號(hào)。

110611201

樓號(hào)層號(hào)房間號(hào)【特點(diǎn)】

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

6092H(key)=6092間界疊加5.除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即

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

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

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

di=偽隨機(jī)數(shù)序列例表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，

H(key)=keyMOD11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為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沖突設(shè)偽隨機(jī)數(shù)序列為9，則：

H1=(5+9)MOD11=3不沖突382.再哈希法方法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，計(jì)算下一個(gè)哈希地址，即：

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

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

用鏈地址法處理沖突0123456789101112

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

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

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

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

哈希表長(zhǎng)為m=16，

設(shè)每個(gè)記錄的查找概率相等(1)用線性探測(cè)再散列處理沖突，即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關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)8.4.5哈希表算法實(shí)現(xiàn) 1線性探測(cè)哈希表的建立2線性探測(cè)哈希表的查找3拉鏈哈希表的建立4拉鏈哈希表的查找5哈希表的刪除1線性探測(cè)哈希表的建立voidCreateSeqHTbl(datetypeSeqHTbl[],intm,datatype*eptr){/*用線性探測(cè)法處理沖突建立散列表SeqHTbl*//*eptr為待放入散列表中的數(shù)據(jù)基址*//*Hash()為散列函數(shù)，m為散列表的長(zhǎng)度*/

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

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

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

定義散列表（指針向量或指針數(shù)組）：

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

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

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

intd;HNode*q;

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

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

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