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

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