課程設(shè)計(jì)試驗(yàn)報(bào)告-哈希表的設(shè)計(jì)與實(shí)現(xiàn)(編輯修改稿)
2025-09-01 16:55 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 以電話號(hào)碼為關(guān)鍵字的哈希表中查找用戶信息 { hash(num)。 node *q=phone[key]next。 while(q!= NULL) { if(strcmp(num,qnum)==0) break。 q=qnext。 } if(q) printf(%s_%s_%s\n,qname,qaddress,qnum)。else printf(無(wú)此記錄\n)。 } b)、void find2(char name[8]) // 在以用戶名為關(guān)鍵字的哈希表中查找用戶信息{ hash2(name)。 node *q=nam[key2]next。 while(q!= NULL) { if(strcmp(name,qname)==0) break。 q=qnext。 } if(q) printf(%s_%s_%s\n,qname,qaddress,qnum)。else printf(無(wú)此記錄\n)。 }主函數(shù)本程序需要?jiǎng)?chuàng)建一個(gè)主菜單和一個(gè)主函數(shù)，主菜單便于用戶的使用，主函數(shù)中，包括所有功能對(duì)應(yīng)的數(shù)值，使之和主菜單相對(duì)應(yīng)。***************************主函數(shù)界面設(shè)計(jì)如下************************ 0添加記錄 1查找記錄 2姓名散列 3號(hào)碼散列 4清空記錄 5退出系統(tǒng)void menu() //菜單 { system(color 2d)。 printf(********************************************************************************\n)。printf(\t\t\t***********歡迎使用***********\t\t\t\n)。printf(\n)。printf(\t\t\t\t \t\t\t\t\n)。 printf(\t\t\t\t \t\t\t\t\n)。 printf(\t\t\t\t \t\t\t\t\n)。 printf(\t\t\t\t \t\t\t\t\n)。 printf(\t\t\t\t \t\t\t\t\n)。 printf(\t\t\t\t \t\t\t\t\n)。 } 3系統(tǒng)測(cè)試1首先鍵入0,添加結(jié)點(diǎn)信息,然后按1進(jìn)行查找,分別進(jìn)行號(hào)碼和姓名查找,最后可在主菜單中，選擇號(hào)碼散列和姓名散列,由此查看程序運(yùn)行結(jié)果。2語(yǔ)法錯(cuò)誤及修改：程序是分塊寫的,調(diào)試時(shí)可以使用分步調(diào)試的方式進(jìn)行,以便能查找看程序是在哪出錯(cuò)了。本算法使用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問(wèn)題，在以姓名為關(guān)鍵字的哈希表中要注意涉及ASCLL碼的類型轉(zhuǎn)換，要注意輸出不能是“%d”，否則不能輸出結(jié)果。編寫程序時(shí)要多注意程序中各種指針的使用，還有各類變量的定義，函數(shù)的使用。這些問(wèn)題均可以根據(jù)編譯器的警告提示，對(duì)應(yīng)的將其解決。3邏輯問(wèn)題修改和調(diào)整：鏈表結(jié)構(gòu)方法雖然方便了運(yùn)行，但是增加了對(duì)算法過(guò)程的認(rèn)識(shí)難度。在本程序中每一個(gè)函數(shù)中都需要涉及到指針的操作。所以需要仔細(xì)分析函數(shù)中的指針指向。在插入結(jié)點(diǎn)，查找結(jié)點(diǎn)時(shí)尤為突出。對(duì)于主菜單和主函數(shù)的對(duì)應(yīng)，一定要一致，這樣才能保證運(yùn)行時(shí)不會(huì)出錯(cuò)。 4時(shí)間，空間性能分析：散列法本質(zhì)上是一種通過(guò)關(guān)鍵字直接計(jì)算存儲(chǔ)地址的方法。在理想情況下，散列函數(shù)可以把結(jié)點(diǎn)均勻地分布到散列表中，不發(fā)生沖突，則查找過(guò)程無(wú)需比較，其時(shí)間復(fù)雜度O（n）=1。但在實(shí)際使用過(guò)程中，為了將范圍廣泛的關(guān)鍵字映射到一組連續(xù)的存儲(chǔ)空間，往往會(huì)發(fā)生同義詞沖突，這時(shí)在查找過(guò)程中就需要進(jìn)行關(guān)鍵字比較。因此散列法的查找性能取決于3個(gè)因素：散列函數(shù)、沖突處理方法和填充因子。采用鏈地址法，可以從根本上杜絕“二次聚集”的發(fā)生，從而提高散列表的均勻度，提高查找性能，不過(guò)也會(huì)“浪費(fèi)”一部分散列表的空間。當(dāng)散列函數(shù)和沖突處理辦法固定時(shí)，散列法的查找性能就取決于散列表的填充因子。填充因子a=表中已有的結(jié)點(diǎn)數(shù)/表的長(zhǎng)度。填充因子a標(biāo)志表的添滿程度。很顯然，a越小則發(fā)生沖突的機(jī)會(huì)就越??；反之，a越大沖突的機(jī)會(huì)就越大，查找的性能也就越低。哈希表鏈地址法查找成功的平均查找長(zhǎng)度SNc=1+a/2。鏈地址法查找不成功的平均查找長(zhǎng)度Un滿足：Unc=a+，散列表的平均查找長(zhǎng)度是填充因子的函數(shù)，和散列表的長(zhǎng)度沒(méi)有關(guān)系，因此在實(shí)際應(yīng)
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1