課程設(shè)計(jì)試驗(yàn)報(bào)告哈希表的設(shè)計(jì)與實(shí)現(xiàn)[共25頁(yè)]

《課程設(shè)計(jì)試驗(yàn)報(bào)告哈希表的設(shè)計(jì)與實(shí)現(xiàn)[共25頁(yè)]》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《課程設(shè)計(jì)試驗(yàn)報(bào)告哈希表的設(shè)計(jì)與實(shí)現(xiàn)[共25頁(yè)]（25頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 哈希表的設(shè)計(jì)與實(shí)現(xiàn) 作 者 院 系 信息工程學(xué)院 專(zhuān) 業(yè) 信息管理與信息系統(tǒng) 學(xué) 號(hào) 1514210117 指導(dǎo)老師 張 慧 答辯時(shí)間 2016年12月18日 目錄 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 0 1系統(tǒng)需求分析 2 1.1用戶(hù)需求分析 3 1.2功能需求

2、分析 3 1.3數(shù)據(jù)需求分析 3 1.4 小結(jié) 4 2系統(tǒng)設(shè)計(jì) 4 2.1設(shè)計(jì)內(nèi)容及要求 4 2.2總體設(shè)計(jì)思路 4 2.3程序詳細(xì)設(shè)計(jì)流程圖 5 2.31以姓名為關(guān)鍵字的Hash()函數(shù)流程圖 5 2.32添加結(jié)點(diǎn)信息流程圖: 7 2.33按姓名查找流程圖: 7 2.34按號(hào)碼查找流程圖 8 2.35主程序流程圖 9 2.4詳細(xì)設(shè)計(jì)編碼 11 2.41建立節(jié)點(diǎn) 11 2.42對(duì)哈希函數(shù)的定義 11 2.43哈希查找 12 2.44主函數(shù) 12 3系統(tǒng)測(cè)試 13 3.1上機(jī)調(diào)試 13 3.2調(diào)試結(jié)果與分析 14 4總結(jié) 18 5附錄 18 1

3、系統(tǒng)需求分析 在信息化時(shí)代的今天，計(jì)算機(jī)技術(shù)已經(jīng)是發(fā)展到一個(gè)很可觀的地步了，特別是面向窗口的操作系統(tǒng)的出現(xiàn)，使得程序設(shè)計(jì)更加的容易了。在過(guò)去計(jì)算機(jī)內(nèi)存容量小，CPU計(jì)算速度慢，關(guān)于程序設(shè)計(jì)中的數(shù)據(jù)結(jié)構(gòu)也因此提出來(lái)很多的關(guān)于解決這方面的問(wèn)題。哈希表就是其中之一，哈希表是一個(gè)由關(guān)鍵字與值組成的特殊的一種數(shù)據(jù)結(jié)構(gòu)。它的出現(xiàn)主要是為了解決在結(jié)構(gòu)中查找記錄時(shí)需要進(jìn)行一系列和關(guān)鍵字的比較,這一類(lèi)查找方法是建立在“比較”的基礎(chǔ)上的，在順序等的查找中，查找的效率是依賴(lài)于查找過(guò)程中所比較的次數(shù)。 理想的情況是希望不經(jīng)過(guò)任何的比較一次存取便能得到所查記錄，那就必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的

4、對(duì)應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系找到給定的值的像。若結(jié)構(gòu)中存在關(guān)鍵字和該值相等的記錄，則所要查找的數(shù)就必定就是這個(gè)所查找到的記錄。 哈希函數(shù)是建立哈希表的一個(gè)重要的成員，它的構(gòu)造方法分為以下幾種： 直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機(jī)數(shù)法。 本程序中主要用的是除余取留法,除留取余法主要是取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p出后所得余數(shù)為哈希地址即:H(key)=key MOD p, p<=m，這是一種最簡(jiǎn)單，也是一種最常用的構(gòu)造函數(shù)的方法，它不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方中等運(yùn)算之后取模。

5、 在哈希表的建立中，很容易出現(xiàn)同義詞，這些同義詞的出現(xiàn)也導(dǎo)致了建立哈希表時(shí)沖突的出現(xiàn)，如果不解決這些沖突那么建立好的哈希表與預(yù)料的哈希表不同。關(guān)于處理沖突的方法主要有：開(kāi)放定址法、再哈希法、鏈地址法。本程序中主要用的就是鏈地址法萊解決沖突的。 1.1用戶(hù)需求分析 設(shè)計(jì)一個(gè)程序能夠使用哈希表實(shí)現(xiàn)電話(huà)號(hào)碼查詢(xún)系統(tǒng)。該系統(tǒng)能夠從鍵盤(pán)輸入各記錄，分別以電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字建立哈希表，能夠從輸入記錄中查找并顯示給定用戶(hù)的記錄，最后并且能夠進(jìn)行清除記錄和退出功能。 1.2功能需求分析 （1）設(shè)計(jì)一個(gè)結(jié)點(diǎn)使該結(jié)點(diǎn)包括電話(huà)號(hào)碼、用戶(hù)名、地址。 （2）利用用戶(hù)名和電話(huà)號(hào)碼為

6、關(guān)鍵字建立哈希表，哈希函數(shù)用除留余數(shù)法構(gòu)照。 （3）利用鏈表法處理沖突問(wèn)題。 （4）查找并顯示給定用戶(hù)名，地址，電話(huà)號(hào)碼的記錄。 （5）顯示哈希表中的給定用戶(hù)的記錄。 （6）當(dāng)完成操作后，可以退出系統(tǒng)。 1.3數(shù)據(jù)需求分析 由問(wèn)題分析知，本設(shè)計(jì)主要要求分別以電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字建立哈希表，并實(shí)現(xiàn)查找功能。所以本設(shè)計(jì)的核心問(wèn)題是如何解決散列的問(wèn)題，亦即設(shè)計(jì)一個(gè)良好的哈希表。由于結(jié)點(diǎn)的個(gè)數(shù)無(wú)法確認(rèn)，并且如果采用線(xiàn)性探測(cè)法散列算法，刪除結(jié)點(diǎn)會(huì)引起“信息丟失”的問(wèn)題。所以采用鏈地址法散列算法。采用鏈地址法，當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲(chǔ)地址不

7、是散列表中其他的空地址。 首先，解決的是定義鏈表結(jié)點(diǎn)，在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成.name[8] 、num[11]和address[20]都是char浮點(diǎn)型，輸入輸出都只能是浮點(diǎn)型的。 采用鏈地址法，其中的所有同義詞構(gòu)成一個(gè)單鏈表，再由一個(gè)表頭結(jié)點(diǎn)指向這個(gè)單鏈表的第一個(gè)結(jié)點(diǎn)。這些表頭結(jié)點(diǎn)組成一個(gè)一維數(shù)組，即哈希表。數(shù)組元素的下標(biāo)對(duì)應(yīng)由散列函數(shù)求出的散列地址。 1.4 小結(jié) 通過(guò)以上需求分析，知道了設(shè)計(jì)一個(gè)哈希表的目的和能夠“實(shí)現(xiàn)什么功能”，為接下來(lái)的操作明確方向，羅列了

8、需要運(yùn)用到的知識(shí)，自己應(yīng)該在接下來(lái)的程序設(shè)計(jì)和實(shí)現(xiàn)應(yīng)該怎么做。 2系統(tǒng)設(shè)計(jì) 2.1設(shè)計(jì)內(nèi)容及要求 本設(shè)計(jì)主要要求分別以電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字建立哈希表，并實(shí)現(xiàn)查找功能。本程序的要求是設(shè)計(jì)散列函數(shù)，亦即設(shè)計(jì)一個(gè)良好的哈希表。本程序需要設(shè)計(jì)兩個(gè)散列函數(shù)才能解決問(wèn)題，程序需要分別為以電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字建立哈希表。所以要分別以用戶(hù)名、號(hào)碼為關(guān)鍵字建立兩個(gè)散列函數(shù)，要添加用戶(hù)信息，即要有實(shí)現(xiàn)添加結(jié)點(diǎn)的功能的函數(shù)，所以要設(shè)計(jì)一個(gè)必須包括一個(gè)輸入結(jié)點(diǎn)信息、添加結(jié)點(diǎn)的函數(shù)； 要實(shí)現(xiàn)查找函數(shù)，則必須包括一個(gè)查找結(jié)點(diǎn)的函數(shù)； 另外還有一個(gè)必不可少的就是運(yùn)行之后要有一個(gè)主菜單，即要設(shè)計(jì)一個(gè)

9、主函數(shù)（main()）。 2.2總體設(shè)計(jì)思路 本設(shè)計(jì)涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入電話(huà)號(hào)碼、用戶(hù)名、地址三個(gè)信息，并要求分別以電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字進(jìn)行查找，所以本問(wèn)題要用到兩個(gè)哈希函數(shù)，進(jìn)行哈希查找。 在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成，鏈地址法結(jié)點(diǎn)結(jié)構(gòu)如圖： name[8] num[11] address[20] next 其中name[8]和num[11]是分別為以電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字域，存放關(guān)鍵字（key）；address[20](data

10、)為結(jié)點(diǎn)的數(shù)據(jù)域，用來(lái)存儲(chǔ)用戶(hù)的地址。Next指針是用來(lái)指向下一個(gè)結(jié)點(diǎn)的地址。 2.3程序詳細(xì)設(shè)計(jì)流程圖 2.31以姓名為關(guān)鍵字的Hash()函數(shù)流程圖 結(jié)束 Key2=key%20 name[i]不為空 開(kāi)始 i從0開(kāi)始取 取整型name[0]賦給key2 Key2+=name[i] i++ 1-1 姓名為關(guān)鍵字的Hash()函數(shù)流程圖 2.32添加結(jié)點(diǎn)信息流程圖: 利用用戶(hù)名為關(guān)鍵字插入 拉鏈法處理沖突 調(diào)用hash()函數(shù) 調(diào)用hash()函數(shù) Newname指向

11、newphone Newphone=input() 結(jié)束 申請(qǐng)新的結(jié)點(diǎn)newphone,newname即新的號(hào)碼和名字 開(kāi)始 1-2添加結(jié)點(diǎn)信息流程圖: 2.33按姓名查找流程圖: q不為空 結(jié)束 輸出無(wú)記錄 輸出相應(yīng)記錄 q=q->next q 不為空 調(diào)用hash()函數(shù)中新結(jié)點(diǎn)q指向phone[key

12、]->next 開(kāi)始 2.34按號(hào)碼查找流程圖 開(kāi)始 調(diào)用hash2()函數(shù)中新結(jié)點(diǎn)q指向phone[key]->next q 不為空 q=q->next q不為空 輸出無(wú)記錄 輸出相應(yīng)記錄 結(jié)束 2.35主程序流程圖 開(kāi) 始 Main () 初始化散列鏈表（1）并為其動(dòng)態(tài)分配內(nèi)存空間 初始化散列鏈

13、表（2）并為其動(dòng)態(tài)分配內(nèi)存空間 Menu（）主菜單 輸入選擇 選擇1 選６ 選7 查找號(hào)碼find() 查找用戶(hù) find2() 輸出結(jié)果 輸出結(jié)果 選擇2 選擇0 選擇3 選擇4 選擇5 進(jìn)行姓名散列l(wèi)ist2() 姓名散列結(jié)果 添加記錄 apend() 退出系統(tǒng)return 0 進(jìn)行號(hào)碼散列 list() 清空creat();creat2() 列表已清空 號(hào)碼散列結(jié)果 結(jié) 束 2.4詳細(xì)設(shè)計(jì)編碼 2.41建立節(jié)點(diǎn) struct node //建節(jié)點(diǎn) { char name[8],address[2

14、0];//節(jié)點(diǎn)中要包含用戶(hù)名，用戶(hù)地址，電話(huà)號(hào)碼以及指向下一個(gè)結(jié)點(diǎn)的指針 char num[11]; node * next; }; typedef node* pnode; //typedef可以為一個(gè)已有的數(shù)據(jù)類(lèi)型聲明多個(gè)別名，這里為該類(lèi)型聲明了兩個(gè)指針 typedef node* mingzi; node **phone; node **nam; node *a; 2.42對(duì)哈希函數(shù)的定義 void hash(char num[11]) //以電話(huà)號(hào)碼為關(guān)鍵字建立哈希函數(shù) { key=(int)num[2]

15、; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%20; } b) void hash2(char name[8]) //以用戶(hù)名為關(guān)鍵字建立哈希函數(shù) { int i = 1; key2=(int)name[0]; while(name[i]!=NULL) { key2+=(int)name[i]; i++; } key2=key2%20; } 2.43哈希查找 void find(char num

16、[11]) //在以電話(huà)號(hào)碼為關(guān)鍵字的哈希表中查找用戶(hù)信息 { hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無(wú)此記錄\n"); } b)、void find2(char name[8]) // 在以用戶(hù)名為關(guān)鍵字的哈希表中查找用戶(hù)信息 { ha

17、sh2(name); node *q=nam[key2]->next; while(q!= NULL) { if(strcmp(name,q->name)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無(wú)此記錄\n"); } 2.44主函數(shù) 主函數(shù) 本程序需要?jiǎng)?chuàng)建一個(gè)主菜單和一個(gè)主函數(shù)，主菜單便于用戶(hù)的使用，主函數(shù)中，包括所有功能對(duì)應(yīng)的數(shù)值，使之和主菜單相對(duì)應(yīng)。 ***********************

18、****主函數(shù)界面設(shè)計(jì)如下************************ 0添加記錄 1查找記錄 2姓名散列 3號(hào)碼散列 4清空記錄 5退出系統(tǒng) void menu() //菜單 { system("color 2d"); printf("*

19、*******************************************************************************\n"); printf("\t\t\t***********歡迎使用***********\t\t\t\n"); printf("\n"); printf("\t\t\t\t 0.添加記錄\t\t\t\t\n"); printf("\t\t\t\t 1.查找記錄\t\t\t\t\n"); printf("\t\t\t\t 2.姓名散列\(zhòng)t\t\t\t\n"); printf("\t\t\t\t 3.號(hào)碼散列\(zhòng)t\t\t

20、\t\n"); printf("\t\t\t\t 4.清空記錄\t\t\t\t\n"); printf("\t\t\t\t 5.退出系統(tǒng)\t\t\t\t\n"); } 3系統(tǒng)測(cè)試 3.1上機(jī)調(diào)試 1首先鍵入0,添加結(jié)點(diǎn)信息,然后按1進(jìn)行查找,分別進(jìn)行號(hào)碼和姓名查找,最后可在主菜單中，選擇號(hào)碼散列和姓名散列,由此查看程序運(yùn)行結(jié)果。 2語(yǔ)法錯(cuò)誤及修改：程序是分塊寫(xiě)的,調(diào)試時(shí)可以使用分步調(diào)試的方式進(jìn)行,以便能查找看程序是在哪出錯(cuò)了。本算法使用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問(wèn)題，在以姓名為關(guān)鍵字的哈希表中要注意涉及ASCLL碼的類(lèi)型轉(zhuǎn)換，要注意輸出不能是“%d”，

21、否則不能輸出結(jié)果。編寫(xiě)程序時(shí)要多注意程序中各種指針的使用，還有各類(lèi)變量的定義，函數(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。但

22、在實(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)志表的添滿(mǎn)程度。很顯然，a越小則發(fā)生沖突的機(jī)會(huì)就越小；反之，a越大沖突的機(jī)會(huì)就越大，查找的性能也就越低。哈希表鏈地址法查找成功的平均查找長(zhǎng)度SNc=1+a

23、/2。鏈地址法查找不成功的平均查找長(zhǎng)度Un滿(mǎn)足：Unc=a+e-a.由以上可以看出，散列表的平均查找長(zhǎng)度是填充因子的函數(shù)，和散列表的長(zhǎng)度沒(méi)有關(guān)系，因此在實(shí)際應(yīng)用中，我們應(yīng)該選擇一個(gè)適當(dāng)?shù)奶畛湟蜃?，以便把平均查找長(zhǎng)度控制在一個(gè)盡量小的范圍內(nèi)。 3.2調(diào)試結(jié)果與分析 程序主菜單 添加記錄: 分別按電話(huà)號(hào)碼和姓名查找: 分別輸出按姓名和號(hào)碼散列的結(jié)果: 清空記錄: 4總結(jié) 經(jīng)過(guò)為期兩周的課程設(shè)計(jì)，此次課程設(shè)計(jì)時(shí)間雖然比較短暫，但是我通過(guò)這次實(shí)踐學(xué)到了很多知識(shí)，也了解了自己的

24、很多的不足之處。我是一名信息工程學(xué)院的學(xué)生，數(shù)據(jù)結(jié)構(gòu)對(duì)于我來(lái)說(shuō)就顯得尤為重要，這也是我必須認(rèn)真學(xué)懂的一門(mén)課程。在課程設(shè)計(jì)之前，我們已經(jīng)學(xué)習(xí)C語(yǔ)言這門(mén)課程已經(jīng)一個(gè)學(xué)期，對(duì)其有了一定的了解，但是更多的還是停留在學(xué)習(xí)了解的范圍，對(duì)里面的好多東西還是很陌生，并不是很熟練，有著許多欠缺，更多的在運(yùn)用起來(lái)的時(shí)候還是感到很不好動(dòng)手。C語(yǔ)言課堂上許多關(guān)于C語(yǔ)言的語(yǔ)法規(guī)則，聽(tīng)起來(lái)十分枯燥無(wú)味，也不容易記住，死記硬背是不可取的。然而要使用C語(yǔ)言這個(gè)工具解決實(shí)際問(wèn)題，又必須掌握它。通過(guò)多次上機(jī)練習(xí)，對(duì)于語(yǔ)法知識(shí)有了感性的認(rèn)識(shí)，加深對(duì)它的理解，在理解的基礎(chǔ)上就會(huì)自然而然地掌握C語(yǔ)言的語(yǔ)法規(guī)定。對(duì)于一些內(nèi)容自己認(rèn)為在課

25、堂上聽(tīng)懂了，但上機(jī)實(shí)踐中會(huì)發(fā)現(xiàn)原來(lái)理解的偏差，更加鞏固了學(xué)過(guò)的知識(shí)，而且在設(shè)計(jì)的時(shí)候?qū)W要系統(tǒng)的知識(shí)，也是一個(gè)較大的挑戰(zhàn)，某一方面知識(shí)的欠缺都將影響到整個(gè)程序的設(shè)計(jì)。我從原來(lái)的對(duì)這門(mén)課程的不懂，到目前的能夠獨(dú)立完成一個(gè)小型程序。 這次課程設(shè)計(jì)，重溫了和學(xué)習(xí)了許多有關(guān)c語(yǔ)言的知識(shí)，還掌握了一些現(xiàn)實(shí)中編程的一些小技巧，實(shí)際的編程能力也得到了歷練，本次課程設(shè)計(jì)對(duì)我?guī)椭芏唷? 5附錄 ************************程序源代碼************************** #include #include #

26、define NULL 0 unsigned int key; //定義兩個(gè)關(guān)鍵字 unsigned int key2; int *p; struct node //建節(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)包括用戶(hù)姓名、地址、電話(huà)號(hào)碼、以及指向下一個(gè)結(jié)點(diǎn)的指針 { char name[8],address[20]; char num[11]; node * next; }; typedef node* pnode; //typedef可以為一個(gè)已有的數(shù)據(jù)類(lèi)型聲明多個(gè)別名，這里為該類(lèi)型聲明了兩個(gè)指針 typedef node* mingzi; node **phone;

27、 node **nam; node *a; void hash(char num[11]) //哈希函數(shù) ，以電話(huà)號(hào)碼為關(guān)鍵字建立哈希函數(shù) //哈希函數(shù)的主旨是將電話(huà)號(hào)碼的十一位數(shù)字全部加起來(lái) { int i = 3; key=(int)num[2]; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%20; } void hash2(char name[8]) //哈希函數(shù) 以用戶(hù)名為關(guān)鍵字建立哈希函數(shù) //利用強(qiáng)

28、制類(lèi)型轉(zhuǎn)換，將用戶(hù)名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù) { int i = 1; key2=(int)name[0]; while(name[i]!=NULL) { key2+=(int)name[i]; i++; } key2=key2%20; } node* input() //輸入節(jié)點(diǎn)信息 ，建立結(jié)點(diǎn)，并將結(jié)點(diǎn)的next指針指空 { node *temp; temp = new node; //new的功能是動(dòng)態(tài)分配內(nèi)存，語(yǔ)法形式：new 類(lèi)型名T（初值列表 temp->next=NULL; print

29、f("請(qǐng)輸入姓名:\n"); scanf("%s",temp->name); printf("輸入地址： \n"); scanf("%s",temp->address); printf("輸入電話(huà)：\n"); scanf("%s",temp->num); return temp; //對(duì)于指針類(lèi)型返回的是地址 } int apend() //添加節(jié)點(diǎn) { node *newphone; node *newname; newphone=input(); newname=newphone; newphone->next=NULL; newna

30、me->next=NULL; hash(newphone->num); //利用哈希函數(shù)計(jì)算出對(duì)應(yīng)關(guān)鍵字的存儲(chǔ)地址 hash2(newname->name); newphone->next = phone[key]->next; //利用電話(huà)號(hào)碼為關(guān)鍵字插入 phone[key]->next=newphone; //是采用鏈地址法，拉鏈法處理沖突的散列表結(jié)構(gòu) newname->next = nam[key2]->next; //利用用戶(hù)名為關(guān)鍵字插入 nam[key2]->next=newname; return 0; } void create() //新建

31、節(jié)點(diǎn) { int i; phone=new pnode[20];//動(dòng)態(tài)創(chuàng)建對(duì)象數(shù)組 for(i=0;i<20;i++) { phone[i]=new node; phone[i]->next=NULL; } } void create2() //新建節(jié)點(diǎn) { int i; nam=new mingzi[20]; for(i=0;i<20;i++) { nam[i]=new node; nam[i]->next=NULL; } } void list() //顯示列表 { int i;

32、node *p; for(i=0;i<20;i++) { p=phone[i]->next; while(p) { printf("%s_%s_%s\n",p->name,p->address,p->num); p=p->next; } } } void list2() //顯示列表 { int i; node *p; for(i=0;i<20;i++) { p=nam[i]->next; while(p) { printf("%s_%s_%s\n",p->name,p->address,p->num);

33、p=p->next; } } } void find(char num[11]) //在以電話(huà)號(hào)碼為關(guān)鍵字的哈希表中查找用戶(hù)信息 { hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無(wú)此記錄\n"); } void find2(char

34、 name[8]) // 在以用戶(hù)名為關(guān)鍵字的哈希表中查找用戶(hù)信息 { hash2(name); node *q=nam[key2]->next; while(q!= NULL) { if(strcmp(name,q->name)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無(wú)此記錄\n"); } void menu() //菜單 { printf("0.添加記錄\n"); pri

35、ntf("1.查找記錄\n"); printf("2.姓名散列\(zhòng)n"); printf("3.號(hào)碼散列\(zhòng)n"); printf("4.清空記錄\n"); printf("5.退出系統(tǒng)\n"); } int main() { char num[11]; char name[8]; create(); create2() ; int sel; while(1) { menu(); scanf("%d",&sel); if(sel==1) { printf("6號(hào)碼查詢(xún)，7姓名查詢(xún)\n"); int

36、b; scanf("%d",&b); if(b==6) { printf("請(qǐng)輸入電話(huà)號(hào)碼:\n"); scanf("%s",num); printf("輸出查找的信息:\n"); find(num); } else { printf("請(qǐng)輸入姓名:\n"); scanf("%s",name); printf("輸出查找的信息:\n"); find2(name);}} if(sel==2) {printf("姓名散列結(jié)果:\n"); list2();} if(sel==0) {printf("請(qǐng)輸入要添加的內(nèi)容:\n"); apend();} if(sel==3) {printf("號(hào)碼散列結(jié)果:\n"); list(); } if(sel==4) {printf("列表已清空:\n"); create();create2();} if(sel==6) return 0; } return 0; }