哈希表實(shí)現(xiàn)通訊錄

合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2023～2023學(xué)年第1學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱哈希表實(shí)現(xiàn)通訊錄學(xué)生姓名張寶軍學(xué)號(hào)0604011009專業(yè)班級(jí)06計(jì)科(1)指導(dǎo)教師王昆侖/胡春玲2023年9月題目：〔哈希表的設(shè)計(jì)與實(shí)現(xiàn)的問(wèn)題〕設(shè)計(jì)哈希表實(shí)現(xiàn)號(hào)碼查詢系統(tǒng)。設(shè)計(jì)程序完成以下要求：〔1〕設(shè)每個(gè)記錄有以下數(shù)據(jù)項(xiàng)：號(hào)碼、用戶名、地址；〔2〕從鍵盤輸入各記錄，分別以號(hào)碼和用戶名為關(guān)鍵字建立哈希表；〔3〕采用再哈希法解決沖突；〔4〕查找并顯示給定號(hào)碼的記錄；〔5〕查找并顯示給定用戶的記錄。一、 問(wèn)題分析和任務(wù)定義此程序需要完成如下要求：設(shè)計(jì)哈希表實(shí)現(xiàn)號(hào)碼查詢系統(tǒng)。實(shí)現(xiàn)本程序需要解決以下幾個(gè)問(wèn)題：〔1〕 設(shè)計(jì)結(jié)點(diǎn)使該結(jié)點(diǎn)包括號(hào)碼、用戶名、地址?！?〕 利用再哈希法解決沖突?！?〕 分別以號(hào)碼和用戶名為關(guān)鍵字建立哈希表?！?〕 實(shí)現(xiàn)查找并顯示給定號(hào)碼的記錄?！?〕 查找并顯示給定用戶的記錄。本問(wèn)題的關(guān)鍵和難點(diǎn)在于如何解決哈希的問(wèn)題。由于結(jié)點(diǎn)的個(gè)數(shù)無(wú)法的知，并且如果采用線性探測(cè)法哈希算法，刪除結(jié)點(diǎn)會(huì)引起“信息喪失〞的問(wèn)題。所以采用鏈地址法哈希算法。采用拉鏈法，當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲(chǔ)地址不是哈希表中其他的空地址。首先，解決的是定義鏈表結(jié)點(diǎn)，在拉鏈法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用號(hào)碼和用戶名為關(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ù)求出的哈希地址。其次，設(shè)計(jì)哈希函數(shù)，本程序需要設(shè)計(jì)兩個(gè)哈希函數(shù)才能解決問(wèn)題，程序需要分別為以號(hào)碼和用戶名為關(guān)鍵字建立哈希表。所以要分別以用戶名、號(hào)碼為關(guān)鍵字建立兩個(gè)哈希函數(shù)，對(duì)于以號(hào)碼為關(guān)鍵字的哈希函數(shù)，是將十一個(gè)數(shù)字全部相加，然后對(duì)20求余。得到的數(shù)作為地址。對(duì)于以用戶名為關(guān)鍵字的哈希函數(shù)，是將所有字母的ASCLL碼值相加，然后對(duì)20求余。再次，需要實(shí)現(xiàn)添加結(jié)點(diǎn)的功能，那么其中必須包括一個(gè)輸入結(jié)點(diǎn)信息、添加結(jié)點(diǎn)的函數(shù)；需要實(shí)現(xiàn)查找函數(shù)，那么必須包括一個(gè)查找結(jié)點(diǎn)的函數(shù)；需要對(duì)文件進(jìn)行保存，那么必需要包括保存文件函數(shù)。還需要包括一個(gè)主菜單和一個(gè)主函數(shù)。最后，當(dāng)程序設(shè)計(jì)出來(lái)后的測(cè)試數(shù)據(jù)為：二、概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)選擇在拉鏈法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用號(hào)碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成，鏈地址法結(jié)點(diǎn)結(jié)構(gòu)如圖：name[8] num[11] address[20] next其中name[8]和num[11]是分別為以號(hào)碼和用戶名為關(guān)鍵字域，存放關(guān)鍵字；address[20]為結(jié)點(diǎn)的數(shù)據(jù)域，用來(lái)存儲(chǔ)用戶的地址。Next指針是用來(lái)指向下一個(gè)結(jié)點(diǎn)的地址。主要算法的流程圖如下：初始化哈希鏈表〔1〕并為其動(dòng)態(tài)分配內(nèi)存空間初始化哈希鏈表〔2〕并為其動(dòng)態(tài)分配內(nèi)存空間INPUT：開始開始建立新結(jié)點(diǎn)temp把temp→next賦為空輸入信息結(jié)束LIST開始開始i=0i<20p-phone[i]→nextp!=null輸入結(jié)點(diǎn)信息p=p→next結(jié)束i++Hash：開始開始取整型num[i]給key從3開始取i值Num[i]!=0Key=key+(int)num[i]i++Key=key%20結(jié)束HASH2：開始開始取整型name[0]給key2從0開始取i值name[i]!=0Key2+=name[i]i++Key2=key2%20結(jié)束Apend()開始開始申請(qǐng)新的結(jié)點(diǎn)newphonenewnameNewphone=input()Newname指向newphone調(diào)用HASH函數(shù)調(diào)用HASH2函數(shù)拉鏈法處理沖突用戶名為關(guān)鍵字輸入信息結(jié)束Find：開始開始申請(qǐng)新結(jié)點(diǎn)q指向phone[key]nextq不為空q=q→nextq不為空輸出記錄輸出結(jié)點(diǎn)信息結(jié)束調(diào)用HASH函數(shù)N三、詳細(xì)設(shè)計(jì)和編碼首先定義結(jié)點(diǎn)結(jié)構(gòu)體類型，在拉鏈法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用號(hào)碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成，鏈地址法結(jié)點(diǎn)結(jié)構(gòu)如圖：name[8] num[11] address[20] next其中name[8]和num[11]是分別為以號(hào)碼和用戶名為關(guān)鍵字域，存放關(guān)鍵字；address[20]為結(jié)點(diǎn)的數(shù)據(jù)域，用來(lái)存儲(chǔ)用戶的地址。next指針是用來(lái)指向下一個(gè)結(jié)點(diǎn)的地址。#include<fstream>用來(lái)輸入/輸出文件流類包含的文件是fstream。unsignedintkey和unsignedintkey2由于題目要求分別以號(hào)碼和用戶名為關(guān)鍵字，所以在此設(shè)計(jì)兩個(gè)關(guān)鍵字。其次，設(shè)計(jì)兩個(gè)hash〔〕函數(shù)，以號(hào)碼為關(guān)鍵字建立哈希函數(shù)hash(charnum[11])。哈希函數(shù)的主旨是將號(hào)碼的十一位數(shù)字全部加起來(lái)，然后在對(duì)20求余。將計(jì)算出來(lái)的數(shù)作為該結(jié)點(diǎn)的地址賦給key。以用戶名為關(guān)鍵字建立哈希函數(shù)hash2(charname[8])。利用強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù)。將計(jì)算出來(lái)的數(shù)作為該結(jié)點(diǎn)的地址賦給key2。再次，建立結(jié)點(diǎn)，并添加結(jié)點(diǎn)，利用拉鏈法解決沖突。建立結(jié)點(diǎn)應(yīng)包括動(dòng)態(tài)申請(qǐng)內(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)然由于分別以用戶名和號(hào)碼為關(guān)鍵字，所以分兩種情況，如果以用戶名為關(guān)鍵字那么調(diào)用voidhash2(charname[8])函數(shù)，并且將結(jié)點(diǎn)插入對(duì)應(yīng)的哈希鏈表中，如果以號(hào)碼為關(guān)鍵字那么調(diào)用voidhash(charnum[11])函數(shù)，并且將結(jié)點(diǎn)插入對(duì)應(yīng)的哈希鏈表中。并且，需要兩個(gè)建立哈希鏈表的函數(shù)，分別動(dòng)態(tài)申請(qǐng)一定的空間，用于動(dòng)態(tài)申請(qǐng)哈希鏈表。voidcreate()用來(lái)動(dòng)態(tài)創(chuàng)立以號(hào)碼為關(guān)鍵字的鏈表數(shù)組，voidcreate2()用來(lái)動(dòng)態(tài)創(chuàng)立以用戶名為關(guān)鍵字的鏈表數(shù)組。同樣，需要兩個(gè)顯示鏈表的函數(shù)，利用for循環(huán)和while語(yǔ)句將表中信息按要求輸出來(lái)。想要實(shí)現(xiàn)查找功能，同樣需要兩個(gè)查找函數(shù)，無(wú)論以用戶名還是以號(hào)碼為關(guān)鍵字，首先，都需要利用hash函數(shù)來(lái)計(jì)算出地址。再依次比照，如果是以號(hào)碼為關(guān)鍵字，比擬其號(hào)碼是否相同，如果相同那么輸出該結(jié)點(diǎn)的所有信息，如果以用戶名為關(guān)鍵字，那么比擬用戶名是否相同，如果相同那么輸出該結(jié)點(diǎn)的所有信息。如果找不到與之對(duì)應(yīng)相同的，那么輸出“無(wú)記錄〞。同時(shí)需要一個(gè)保存文件的函數(shù)，利用一個(gè)for循環(huán)，當(dāng)用hash函數(shù)計(jì)算的地址，在鏈表的動(dòng)態(tài)申請(qǐng)的數(shù)組范圍之內(nèi)，那么創(chuàng)立一個(gè)文件流對(duì)象，并將結(jié)點(diǎn)信息保存在該文件中。最后，需要?jiǎng)?chuàng)立一個(gè)主菜單和一個(gè)主函數(shù)，主菜單便于用戶的使用，主函數(shù)中，包括所有功能對(duì)應(yīng)的數(shù)值，使之和主菜單相吻合。當(dāng)程序設(shè)計(jì)出來(lái)后的測(cè)試數(shù)據(jù)為：可以首先，實(shí)現(xiàn)添加結(jié)點(diǎn)，將1中的的信息從鍵盤輸入，然后在主菜單中選擇保存文件，再將2信息從鍵盤輸入，然后在主菜單中，選擇保存文。到此已實(shí)現(xiàn)了對(duì)信息的儲(chǔ)存?？稍谥鞑藛沃校x擇哈希、查找等功能。四、上機(jī)調(diào)試1、語(yǔ)法錯(cuò)誤及修改：由于本算法使用了鏈表結(jié)構(gòu)和拉鏈法解決沖突的問(wèn)題，所以程序可以相對(duì)來(lái)說(shuō)得到簡(jiǎn)化，語(yǔ)句相對(duì)簡(jiǎn)潔。并且沖突得到很好的解決。所以出現(xiàn)的語(yǔ)法問(wèn)題主要在于子函數(shù)和變量的定義，括號(hào)的配對(duì)，關(guān)鍵字和函數(shù)名稱的書寫，以及一些庫(kù)函數(shù)的標(biāo)準(zhǔn)使用。這些問(wèn)題均可以根據(jù)編譯器的警告提示，對(duì)應(yīng)的將其解決。2、邏輯問(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ò)。 3、時(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ù)、沖突處理方法和填充因子。拉鏈法可以從根本上杜絕二次聚集，從而提高哈希表的均勻度，提高查找性能。當(dāng)哈希函數(shù)和沖突處理方法固定時(shí)，哈希法的查找性能就取決于哈希表的填充因子。填充因子a=表中已有的結(jié)點(diǎn)數(shù)/表的長(zhǎng)度。填充因子a標(biāo)志表的添滿程度。很顯然，a越小那么發(fā)生沖突的時(shí)機(jī)就越??；反之，a越大沖突的時(shí)機(jī)就越大，查找的性能也就越低。哈希表鏈地址法查找成功的平均查找長(zhǎng)度SNc=1+a/2。鏈地址法查找不成功的平均查找長(zhǎng)度Un滿足：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)。 4、經(jīng)驗(yàn)和體會(huì)：最初拿到這個(gè)問(wèn)題，因?yàn)橐郧霸谧鯟++語(yǔ)言課程設(shè)計(jì)的時(shí)候拿到的也是這個(gè)題目，所以很熟悉，但是數(shù)據(jù)結(jié)構(gòu)課上多用的是C，所以用C++來(lái)設(shè)計(jì)并且參考了以前做的題目，聯(lián)系了數(shù)據(jù)結(jié)構(gòu)課本上和題目要求做出了設(shè)計(jì)。剛開始想到的是號(hào)碼的存儲(chǔ)肯定不是固定的一成不變的，所以需要建立動(dòng)態(tài)鏈表，并且如果采用線性探測(cè)法哈希算法解決沖突問(wèn)題，刪除結(jié)點(diǎn)會(huì)引起“信息喪失〞的問(wèn)題。因?yàn)樵诰€性探測(cè)哈希法中，我請(qǐng)教了同學(xué)，處理沖突的方式是把同義詞放到哈希表中的下一個(gè)空地址，而查找是沿著同一個(gè)路徑進(jìn)行的。因此當(dāng)刪除了一個(gè)結(jié)點(diǎn)后，由于標(biāo)志數(shù)組被更新，其后的同義詞也將不再被查找到。而采用拉鏈法，當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲(chǔ)地址不是哈希表中其他的空地址。因此需要進(jìn)行詳細(xì)的分析來(lái)發(fā)現(xiàn)和解決這些情況。這也是一個(gè)對(duì)問(wèn)題從認(rèn)識(shí)到建立模型，之后提出方法，修改方法，最終解決問(wèn)題的過(guò)程。五、使用說(shuō)明 本程序運(yùn)行過(guò)程時(shí)帶有提示性語(yǔ)句，由于address[20]、name[8]和num[11]可以看出地址可輸入的最大字符數(shù)是20，姓名可輸入的最大字符數(shù)是8，號(hào)碼都為11位。在輸入的時(shí)候，用戶特別注意號(hào)碼的位數(shù)。實(shí)現(xiàn)添加結(jié)點(diǎn)，將信息從鍵盤輸入，然后在主菜單中選擇保存文件，再將其它信息從鍵盤輸入，然后在主菜單中，選擇保存文。到此已實(shí)現(xiàn)了對(duì)信息的儲(chǔ)存?？稍谥鞑藛沃校x擇哈希、查找等功能。六、測(cè)試結(jié)果主截面：輸入并存儲(chǔ)結(jié)點(diǎn)信息：按姓名查找：按查找：退出：七、參考書目2007年6月第一版王昆侖李紅《數(shù)據(jù)結(jié)構(gòu)與算法》中國(guó)鐵道出版社2007年5月第十五次版鄭莉董淵張瑞豐C++語(yǔ)言程序設(shè)計(jì)〔第3版〕八、附錄#include<iostream>#include<string>#include<fstream>usingnamespacestd;#defineNULL0unsignedintkey;//用來(lái)輸入/輸出文件流類unsignedintkey2;//key和key2分別是用做了號(hào)碼和姓名的關(guān)鍵字int*p;structnode//新建節(jié)點(diǎn)〔用戶姓名、地址、號(hào)碼、指向下一個(gè)結(jié)點(diǎn)的指針〕{charname[8],address[20];charnum[11];node*next;};typedefnode*pnode;typedefnode*mingzi;//聲明了名字和兩個(gè)指針node**phone;node**nam;node*a;voidhash(charnum[11])//以號(hào)碼為關(guān)鍵字建立哈希函數(shù){inti=3;key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%20;}voidhash2(charname[8])//姓名為關(guān)鍵字建立哈希函數(shù){inti=1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;}//強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù)node*input()//輸入節(jié)點(diǎn)信息，建立結(jié)點(diǎn)，并將結(jié)點(diǎn)的next指針指空{(diào)node*temp;temp=newnode;temp->next=NULL;cout<<"輸入姓名："<<endl;cin>>temp->name;cout<<"輸入地址："<<endl;cin>>temp->address;cout<<"輸入："<<endl;cin>>temp->num;returntemp;}//對(duì)于指針類型返回的是地址intapend()//添加節(jié)點(diǎn){node*newphone;node*newname;newphone=input();newname=newphone;newphone->next=NULL;newname->next=NULL;hash(newphone->num);//利用哈希函數(shù)計(jì)算出對(duì)應(yīng)關(guān)鍵字的存儲(chǔ)地址hash2(newname->name);newphone->next=phone[key]->next;//利用號(hào)碼為關(guān)鍵字插入phone[key]->next=newphone;//是采用鏈地址法，拉鏈法處理沖突的哈希表結(jié)構(gòu)newname->next=nam[key2]->next;//利用用戶名為關(guān)鍵字插入nam[key2]->next=newname;return0;}voidcreate()//新建節(jié)點(diǎn){inti;phone=newpnode[20];//動(dòng)態(tài)創(chuàng)立對(duì)象數(shù)組，C++課本P188頁(yè)for(i=0;i<20;i++){phone[i]=newnode;phone[i]->next=NULL;}}voidcreate2()//新建節(jié)點(diǎn){inti;nam=newmingzi[20];for(i=0;i<20;i++){nam[i]=newnode;nam[i]->next=NULL;}}voidlist()//顯示列表{inti;node*p;for(i=0;i<20;i++){p=phone[i]->next;while(p){cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;p=p->next;}}}voidlist2()//顯示列表{inti;node*p;for(i=0;i<20;i++){p=nam[i]->next;while(p){cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;p=p->next;}}}voidfind(charnum[11])//在以號(hào)碼為關(guān)鍵字的哈希表中查找用戶信息{hash(num);node*q=phone[key]->next;while(q!=NULL){if(strcmp(num,q->num)==0)break;q=q->next;}if(q)cout<<q->name<<"_"<<q->address<<"_"<<q->num<<endl;elsecout<<"無(wú)此記錄"<<endl;}voidfind2(charname[8])//在以用戶名為關(guān)鍵字的哈希表中查找用戶信息{hash2(name);node*q=nam[key2]->next;while(q!=NULL){if(strcmp(name,q->name)==0)break;q=q->next;}if(q)cout<<q->name<<"_"<<q->address<<"_"<<q->num<<endl;elsecout<<"無(wú)此記錄"<<endl;}voidsave()//保存用戶信息{inti;node*p;for(i=0;i<20;i++){p=phone[i]->next;while(p){fstreamiiout("out.txt",ios::out);//創(chuàng)立一個(gè)文件流對(duì)象：iioutiiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl;//將信息存如文件p=p->next;}}}voidmenu()//菜單{cout<<"哈希表通訊錄"<<endl;cout<<"0.添加記錄"<<endl;cout<<"2.姓名哈希"<<endl;cout<<"3.查找記錄"<<endl;co