哈希表的設(shè)計(jì)與實(shí)現(xiàn)

1、令膽 嗲 院計(jì)算機(jī)科 嗲 b 練 水 系課程設(shè)計(jì)報(bào)告20072008 學(xué)年第2學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課 程 設(shè) 計(jì) 名 稱哈希表的設(shè)計(jì)與實(shí)現(xiàn)學(xué)生姓名學(xué)號0604011026專業(yè)班級06 計(jì)科（1)指導(dǎo)教師2008年9月課程設(shè)計(jì)題目：（哈希表的設(shè)計(jì)與實(shí)現(xiàn)的問題 設(shè)計(jì)哈希表實(shí)現(xiàn)電話號碼查詢系統(tǒng)。設(shè)計(jì)程序完成以下 要求 ：(1） 設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號碼、用戶名、地址：（2） 從鍵盤輸入各記錄 ， 分別以電話號碼和用戶名為關(guān)鍵字建立晗希表 ；(3） 采用再哈希法解決沖突；（4） 查找并 顯示給定電話號碼的記錄 ：（5） 查找并顯示給定用戶的記錄。一、 問題分析和任務(wù)定義1、問題分析要完成如下

2、要求 ：設(shè)計(jì)晗希表實(shí)現(xiàn)電話號碼查詢系統(tǒng)。 實(shí)現(xiàn)本程序需要解決以下幾個(gè)問題：(1)如何設(shè)計(jì)一個(gè)結(jié)點(diǎn)使該結(jié)點(diǎn)包括電話號碼、用戶名、地址。(2)如何分別以 電話號碼和用戶名為關(guān)鍵字建立哈希表 。(3)如何利用再晗希法解決沖突。(4)如何實(shí)現(xiàn)用晗希法查找并顯示給定電話號碼的記錄 。(5)如何查找并顯示給定用戶的記錄 。2、任務(wù)定義由問題分析知，本設(shè)計(jì)主要要求分別以電話號碼和用戶名為關(guān)鍵字建立晗希表 ，并實(shí)現(xiàn) 查找功能 。所以本設(shè)計(jì)的核心問題是如何解決散列的問題，亦即設(shè)計(jì)一個(gè)良好的哈希表。由 于結(jié)點(diǎn)的個(gè)數(shù)無法確認(rèn)，并且如果采用線性探測法散列算法 ，刪除結(jié)點(diǎn)會引起 “信息丟失” 的問題。所以采用鏈地址法散

3、列算法 。采用鏈地址法 ，當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表結(jié)構(gòu) 把同義詞鏈接在一起，即同義詞的存儲地址不是散列表中其他的空地址 。首先，解決的是定義鏈表結(jié)點(diǎn)，在鏈地址法中，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè) 域組成，而由于該程序需要分別用電話號碼和用戶名為關(guān)鍵字建立晗希表 ，所以該鏈表結(jié)點(diǎn) 它是由四個(gè)域組成.name8 、num ll 和 address20 都是 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)對應(yīng)由散列函 數(shù)求出的散列地址。拉鏈法處理沖

4、突 的散列表結(jié)構(gòu)： 3、主程序分析本題目最主要的要求是設(shè)計(jì)散列 函數(shù)，本程序需要設(shè)計(jì)兩個(gè)散列函數(shù)才能解決問題，程序需 要分別為以 電話號碼和用戶名為關(guān)鍵字建立哈希表 。所以要分別以用戶名、號碼為關(guān)鍵字建 立兩個(gè)散列畫數(shù)，具體思路為 ：對于以號碼為關(guān)鍵字的散列函數(shù)，是將十一個(gè)數(shù)字全部相加，然后對 20 求余。得到的 數(shù)作為地址 。對于以用戶名為關(guān)鍵字的散列函 數(shù)，是將所有字母的ASCLL 碼值相加 ，然后對 20 求余。要添加用戶信息，即要有實(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è)必不可少的

5、就是運(yùn) 行之后要有一個(gè)主菜單 ，即要設(shè)計(jì)一個(gè)主函數(shù)(main（） ）。4、測試數(shù)據(jù)的選擇最后，程序完成后要對程序進(jìn)行 編譯調(diào)試，執(zhí)行后要選擇數(shù)據(jù)進(jìn)行測試，這里選擇的測試數(shù) 據(jù)為：l、姓名：張三 電話號碼： 地址：合肥2、姓名：Jack 電話號碼： 地址：Shanghai三、概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)選擇本設(shè)計(jì)涉及到的數(shù)據(jù)結(jié)構(gòu)為 ：哈希表。要求輸入電話號碼、用戶名、地址三個(gè)信息，并 要求分別以電話號碼和用戶名為關(guān)鍵字進(jìn)行查找，所以本問題要用到兩個(gè)晗希函數(shù)，進(jìn)行哈 希查找。在鏈地址法中，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別 用電話號碼和用戶名為關(guān)鍵字建立哈希表 ，所以該鏈表結(jié)點(diǎn)它

6、是由 四個(gè)域組成 ，鏈地址法結(jié) 點(diǎn)結(jié)構(gòu)如圖： 陽e8 I 川口J l a抽出s 20 I next其中 name8和 numll 是分別為以電話號碼和用戶名為關(guān)鍵字域 ，存放關(guān)鍵字 （key ) ; address20(data）為結(jié)點(diǎn)的數(shù)據(jù)域，用來存儲用戶的地址。Next 指針是用來指 向下一個(gè)結(jié)點(diǎn) 的地址。主要算法的流程 圖如下：以號碼為關(guān)鍵字的 Hash（）函數(shù)流程圖開始取整型 num2賦給 keyi從 3 開始取 Key=key+(int) numii+Key=key%20結(jié)束以姓名為關(guān)鍵字的 HashO函數(shù)流程圖開始取整型nameO賦給 key2i從 0 開始取Key2+=namei

7、i+Key2:key%20結(jié)束添加結(jié)點(diǎn)信息流程圖：開始申請新的結(jié)點(diǎn) newphone,newname 即新的號碼和名字Newphone=input()Newname 指向 newphone調(diào)用 hash（）函數(shù)調(diào)用 hash（）函數(shù)拉鏈法處理沖突利用用戶名為關(guān)鍵字插入結(jié)束按姓名查找流程圖：開始調(diào)用 hash（）函數(shù)中新結(jié)點(diǎn) q 指向phonekey->nextq=q->next輸 出無 記 錄q 不為 空輸 出相 應(yīng)記錄結(jié)束按號碼查找流程圖：開始 調(diào)用 bash2（）函數(shù)中新結(jié)點(diǎn) q 指向pbonekey->nextq=q->next輸 出無 記 錄q 不為空輸 出相

8、應(yīng) 記錄結(jié)束初始化散列鏈表 (1） 并為其動態(tài)分配內(nèi)存空 間初始化散列鏈表 （ 2） 并為其動態(tài)分配內(nèi)存空 間主程序流程圖Menu （） 主 菜單進(jìn)行姓名散1 list2()添加記錄 apend()進(jìn)行號碼散列 list()號碼散列結(jié)果清空 creat();creat2()列表己清空退出系統(tǒng) return O結(jié)束四、詳細(xì)設(shè)計(jì)和編碼首先定義結(jié)點(diǎn)結(jié)構(gòu)體類型，在鏈地址法 中，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組 成，而由于該程序需要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表 ，所以該鏈表結(jié)點(diǎn)它是 由四個(gè)域組成 ，鏈地址法結(jié)點(diǎn)結(jié)構(gòu)如圖：I n棚e s I 川其中 name8和 num ll是分別為以電

9、話號碼和用戶名為關(guān)鍵 字域 （key） ，存放關(guān)鍵字： address20為結(jié)點(diǎn)的數(shù)據(jù)域（data），用來存儲用戶的地址信息。next 指針是用來指向下一個(gè)結(jié) 點(diǎn)的地址。unsigned int key 和 unsigned int key2 分別被定義為電話號碼和用戶名關(guān)鍵字。程序的主要模 塊如下：串程序部分源代碼中串串串串串豐1、建立節(jié)點(diǎn)struct node H建節(jié)點(diǎn)char name8,address20礦節(jié)點(diǎn)中要包含用戶名，用戶地址，電話號碼以及指向下一個(gè)結(jié)點(diǎn)的指針char num(ll; node * next;typedef node* pnode; /typedef 可以為一個(gè)

10、己有的數(shù)據(jù)類型聲明多個(gè)別名，這里為該類型聲明了兩 個(gè)指針typedef node* mingzi; node *phone ;node 肺nam; node *a;2、對哈希函數(shù)的定義本程序要設(shè)計(jì)兩個(gè) hash O 函數(shù)，分別對應(yīng)電話號碼和用戶名。本設(shè)計(jì)中對散列函數(shù) 選擇的是除留余數(shù)法，即對關(guān)鍵字進(jìn)行模運(yùn)算，將運(yùn)算結(jié)果所得的余數(shù)作為關(guān)鍵字（或 結(jié)點(diǎn) 的存儲地址，即 H (key) =key mod p，本設(shè)計(jì)中p 取 20，然后將計(jì)算出來的數(shù)作為該結(jié) 點(diǎn)的地 址賦給 key。具體方法如下：以電話號碼為關(guān)鍵字建立哈希函數(shù) hash(char num11） 。以用戶 名為關(guān)鍵字建立哈希 函數(shù)bas

11、h2(char name8） 。利用強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母 的ASCLL 碼值相加并且除以20 后的余數(shù)。將計(jì)算出來的數(shù)作為該結(jié) 點(diǎn)的地址賦給 key2 。程序部分源代碼牢牢牢牢牢牢牢牢牢牢串串串串串串串 串本本中a),oid hash(char numll) II以電話號碼為關(guān)鍵字建立哈希函數(shù)key=(int)num 2;while(numi!=NULL)key+=(int)numi;1+;key=key %20;b)void bash2(char name8) II以用戶名為關(guān)鍵字建立晗希函數(shù)int i = 1; key2=(int)nameO;while(namei!=NUL

12、L)key2+=(int)namei;；key2=key2%20;然后，建立結(jié)點(diǎn) ，并添加結(jié)點(diǎn) ，利用鏈地址法解決沖突 。建立結(jié)點(diǎn)應(yīng)包括動態(tài)申請內(nèi) 存空間。向結(jié)點(diǎn)中輸入信息。同時(shí)將結(jié)點(diǎn)中的 next 指針等于 null 。添加結(jié)點(diǎn)，首先需要利用 晗希函數(shù)計(jì)算出地址即關(guān)鍵字，其次將該結(jié)點(diǎn)插入以關(guān)鍵字為地址的鏈表后 ，當(dāng)然由于分別 以用戶名和電話號碼為關(guān)鍵字 ，所以分兩種情況 ，如果以用戶名為關(guān)鍵字則調(diào)用 void hash2(char name8）函數(shù)，并且將結(jié)點(diǎn)插入對應(yīng)的散列鏈表中，如果以電話號碼為關(guān)鍵字則 調(diào)用 void hash(char numll）函數(shù)，并且將結(jié)點(diǎn)插入對應(yīng)的散列鏈表中

13、。并且，需要兩個(gè)建立散列鏈表的函數(shù) ，分別動態(tài)申請一定的空間 ，用于動態(tài)申請散列 鏈表。void creat（）用來動態(tài)創(chuàng)建以電話號碼為關(guān)鍵字的鏈表數(shù)組，void create2（）用來動態(tài)創(chuàng) 建以用戶名為關(guān)鍵字的鏈表數(shù)組。串串程序部分源代碼串串豐void create() II新建號碼節(jié)點(diǎn)phonei=new node; phonei->next=NULL;int i;phone=new pnode20; fl動態(tài)創(chuàng)建對象數(shù)組for(i=O;i<20;i+)void create2() II新建姓名節(jié)點(diǎn)nami=new node;int i;nami->next=NULL

14、;nam=new mingzi20; for(i=O;i<20;i叫同樣，需要兩個(gè)顯示鏈表的函數(shù)，利用 for 循環(huán)和 while 語句將表中信息按要求輸出來 。3. 哈希查找想要實(shí)現(xiàn)查找功能，同樣需要兩個(gè)查找函數(shù)，無論以用戶名還是以電話號碼為關(guān)鍵字 ， 首先，都需要利用 hash 函數(shù)來計(jì)算出地址。再通過比對 ，如果是以電話號碼為關(guān)鍵字 ，比 較其電話號碼是否相同，如果相同則輸出該結(jié)點(diǎn)的所有信息，如果以用戶名為關(guān)鍵字，則比 較用戶名是否相同，如果相同則輸出該結(jié)點(diǎn)的所有信息。如果找不到與之對應(yīng)相同的，則輸 出 “無此記錄，。程序部分源代碼串串a(chǎn)）、void find(char numll

15、） 施以電話號碼為關(guān)鍵字的哈希表中查 找用戶信息hash(num);node *q=phonekey->next; while(q!= NULL)if(strcmp(num,q->num)=O) break;q=q->next;if(q)printf（”%s_%s_%sn",q->name,q->addre邸 q->num); else printf （ 無J1t記錄飛n");b）、void fmd2(char nameS) II 在以用戶名為關(guān)鍵字的哈希表中查找用戶信息hash2(name);node *q=namkey2->ne

16、xt; while(q!= NULL)if(strcmp(name,q->name)=O) break;q=q->next;if(q)printf（”%s_%s_%s惱”，q->name,q->address,q->nUJD); else printf （ 無此記錄飛n");3、主函數(shù)本程序需要?jiǎng)?chuàng)建一個(gè)主菜單和一個(gè)主函 數(shù)，主菜單便于用戶的使用，主函數(shù)中，包括所有 功能對應(yīng)的數(shù)值，使之和主菜單相對應(yīng) 。主函數(shù)界面設(shè)計(jì)如下0.添加記錄1.查找記錄2.姓名散列3.號碼散列4.清空記錄5.退出系統(tǒng)4、程序數(shù)據(jù)測試當(dāng)程序設(shè)計(jì)出來后的測試數(shù)據(jù)為 ：1、姓名：張三

17、電話號碼： 地址：合肥2、姓名：Jack 電話號碼： 地址：Shanghai首先鍵入 0，添加結(jié)點(diǎn)信息，然后按 1 進(jìn)行查找，分別進(jìn)行號碼和姓名查找，最后可在主菜單 中，選擇號碼散列和姓名散列，由此查看程序運(yùn)行結(jié)果 。至此，就解決了哈希表的設(shè)計(jì)與實(shí)現(xiàn)算法可能出現(xiàn)的各種問 題，那么根據(jù)以上思路以及對問 題的分析和對出現(xiàn)情況的解決則可以寫出源程序 。五、上機(jī)調(diào)試1、語法錯(cuò)誤及修改 ：程序是分塊寫的，調(diào)試時(shí)可以使用分步調(diào)試的方式進(jìn)行，以便能查 找看程序是在哪出錯(cuò)了。本算法使用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問題，在以姓名為關(guān) 鍵字的哈希表中要注意涉及 ASCLL 碼的類型轉(zhuǎn)換，要注意輸出不能是%d ”

18、，否則不能輸出 結(jié)果。編寫程序時(shí)要多注意程序中各種指針的使用，還有各類變量的定義，函數(shù)的使用。這 些問題均可以根據(jù)編譯器的警告提示，對應(yīng)的將其解決。2、邏輯問題修改和調(diào)整：鏈表結(jié)構(gòu)方法雖然方便了運(yùn)行，但是增加了對算法過程的認(rèn) 識難度。在本程序中每一個(gè)函數(shù)中都需要涉及到指針的操作。所以需要仔細(xì)分析函數(shù)中的指 針指向。在插入結(jié)點(diǎn)，查找結(jié)點(diǎn)時(shí)尤為突出。對于主菜單和主函數(shù)的對應(yīng)，一定要一致，這 樣才能保證運(yùn)行時(shí)不會出錯(cuò)。3、時(shí)間，空間性能分析：散列法本質(zhì)上是一種通過關(guān)鍵字直接計(jì)算存儲地址的方法 。 在理想情況下，散列函數(shù)可以把結(jié)點(diǎn)均勻地分布到散列表 中，不發(fā)生沖突，則查找過程無需 比較，其時(shí)間復(fù)雜度

19、0 (n) =1。但在實(shí)際使用過程中，為了將范圍廣泛的關(guān)鍵宇映射到一 組連續(xù)的存儲空間 ，往往會發(fā)生同義詞沖突，這時(shí)在查找過程中就需要進(jìn)行關(guān)鍵字比較 。因 此散列法的查找性能取決于 3 個(gè)因素：散列函數(shù)、沖突處理方法和填充因子。采用鏈地址法 ，可以從根本上杜絕 “二次聚集” 的發(fā)生，從而提高散列表的均勻度，提高查找性能，不過也 會 “浪費(fèi)” 一部分散列表的空間 。當(dāng)散列函數(shù)和沖突處理辦法固定時(shí)，散列法的查找性能就 取決于散列表的填充因子。填充因子 a 表中已有的結(jié)點(diǎn)數(shù)表的長度。填充困子 a 標(biāo)志表的 添滿程度。很顯然，a 越小則發(fā)生沖突的機(jī)會就越小 ；反之，a 越大沖突的機(jī)會就越大，查 找的性

20、能也就越低。哈希表鏈地址法查找成功的平均查找長度 SNc= l+a/2 。鏈地址法查找不 成功的平均查找長度 Un 滿足：Un =a 由以上可以看出，散列表的平均查找長度是填充困 子的函數(shù)，和散列表的長度沒有關(guān)系，因此在實(shí)際應(yīng)用 中，我們應(yīng)該選擇一個(gè)適當(dāng)?shù)奶畛湟?子，以便把平均查找長度控制在一個(gè)盡 量小的范圍內(nèi)。4、經(jīng)驗(yàn)和體會 ：本設(shè)計(jì)用到的數(shù)據(jù)結(jié)構(gòu)是哈希表，并且要實(shí)現(xiàn)查找功能，在剛拿到本 問題時(shí)，我首先想到的查找方法是順序查找，這就沒有用到哈希表 ，而本設(shè)計(jì)要求必需使用 晗希表這一存儲結(jié)構(gòu)，另外本設(shè)計(jì)也可以用 C中的類來解決，可以用類來設(shè)計(jì)晗希表 。六、用戶使用說明本程序運(yùn)行過程時(shí)帶有提示性

21、語句，由于 address20 、name8和 numll可以看出地址 可輸入的最大字符數(shù)是 20，姓名可輸入的最大字符數(shù)是 8，電話號碼都為 11 位。在輸入的 時(shí)候，用戶特別注意 電話號碼的位數(shù)。實(shí)現(xiàn)添加結(jié)點(diǎn) ，將信息從鍵盤輸入 ，然后根據(jù)屏幕的提示進(jìn)行操作，由此，本設(shè)計(jì)的要 求就可以被用戶實(shí)現(xiàn)了。七、測試結(jié)果程序主菜單：添加記錄：E 圃C:Userstige叭Desktop飛課程酣咱希褒酣吃酒 hxb飛Debughxb劇理分別按電話號碼和姓名查找：國C:Users飛回ge叭Des戰(zhàn)op課程齒，鴨精裝源代碼飛hxb飛' Debughxb.exeA坦J到分別輸出按姓名和號碼散列的結(jié)果

22、：國C飛U”“飛liger飛Desktop課程酶，叭晗幫褒漂代碼飛hxb飛Debug飛hxb劇e國C:Users句e叭Desktop飛漂穰副科始每蒙漂代碼，hxbDebughxb刷e清空記錄：廣me:飛Userstige 飛Des陽op幌程設(shè) t'飛始幫褻漂代碼hxbDebug飛hxb刷e八、參考書 目i草浩強(qiáng)，C 語言程序設(shè)計(jì)，北京：清華大學(xué)出版社 ，2005 年 7 月第 3 版。 王昆侖，李紅，數(shù)據(jù)結(jié)構(gòu)與算法，中國鐵道出版社 ，2007 年 6 月第 1版。 李春碟，數(shù)據(jù)結(jié)構(gòu)題集，北京：清華大學(xué)出版社 ，1992 年 2 月第一版。九、附錄程序源代碼牢牢牢牢牢牢牢牢牢牢牢牢牢牢牢

23、牢牢 本本本本#include<s tdio. h>#include<s tring. h>#def ine M兒L 0unsigned int key ；定義兩個(gè)關(guān)鍵字unsigned int key2;int *P ,struct node 建節(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)包括用戶姓名、地址、電話號碼、以及指向下一個(gè)結(jié)點(diǎn)的指針char name 町，address 20 , char numll ;node * next ;typedef node* pnode; / typedef 可以為一個(gè)已有的數(shù)據(jù)類型聲明多個(gè)別名，這里為該類型聲明了兩個(gè)指針typedef node* min

24、gz i; node *phone;node *n創(chuàng)o; node 亂，void hash(char num ll) 哈希函數(shù) ，以電話號碼為關(guān)鍵字建立哈希函數(shù)晗希函數(shù)的主旨是將電話號碼的十一位數(shù)字全部加起來int i = 3;key= (int) num 2 ;while (numi ！陽LL)key+= (int) num i ; 1+;key=key%20;void hash2 (char name 8) 哈希函數(shù) 以用戶名為關(guān)鍵字建立哈希函數(shù)除以 20 后的余數(shù)int i = l ;key2= (int) n棚eO ; while (name i！陽LL)key2+= (int) na

25、me i; 1+ ;key2=key2%20 ;利用強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母的ASCLL 碼值相加并且node* input () 輸入節(jié)點(diǎn)信息 ，建立結(jié)點(diǎn)，并將結(jié)點(diǎn)的 next 指針指空node *temp ;temp = new node; /new 的功能是動態(tài)分配內(nèi)存，語法形式 ：new 類型，名 T （初借列表temp->next=NU LL ;printf （請輸入姓名：n勺 ， scanf （%sH, temp->name) , printf （輸入地址：nH) ; scanf （%s，temp->address) ; printf （輸入電話：n&q

26、uot;) ; scanf （飛s，temp->num) ,return temp ；對于指針類型，返回的是地址int apend O II添加節(jié)點(diǎn)node *newphone ; node *newname ; newphone=inpu t () ; newname=newphone;newphone->next 肌兒L ;newname->next=NULL ;hash (newphone->num) ;利用哈希函數(shù)計(jì)算出對應(yīng)關(guān)鍵字的存儲地址hash2 (newname->name) ;newphone->next = phone key) ->

27、next ; II利用電話號碼為關(guān)鍵字插入phone key) ->next=newphone; 是采用鏈地址法，拉鏈法處理沖突的散列表結(jié)構(gòu)newname->next = namkey2) ->next ; 利用用戶名為關(guān)鍵字插入nam key2 next=newn 劃1e; return 0:void create () 新建節(jié)點(diǎn)mt i .phone-1ew pnode 20 ；動態(tài)創(chuàng)建對象數(shù)紐 for(i=O; i<20 ; i÷）phone i=new node; phone i->next=NULL;void create20 新建節(jié)點(diǎn)int

28、i ;nam=new mingzi20 ；for (i=O; i<20; i+)na叫i=new node; nam (i->next=NULL ;void list （） 顯示列表int 1,node *p;for (i=O; i<20; i+)p=phone i->next; while (p)printf （如 %s_%sn，p->name, p->address, p->num) ; p=p-)next ;void list2 0 顯示列表mt i .node *p;for (i=O; i<20; i+)p=nami->next ; while (p)printf （如 %s_%sn，p->name, p->address, p->num) ; p=p-)nex t ;void f ind (char num ll) 在以電話號碼為關(guān)鍵字的哈希袋中查找用戶信息hash (num) ;node *q=phone key ->nex t ; while (q != Nl兒L)if (strcmp (num, q-)num) =O) break;q=q-)nex t ;if (q)printf （飛s_%s_%sn，q->na