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