哈希表實(shí)驗(yàn)報(bào)告

第第頁(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告院系：專(zhuān)業(yè)：班級(jí)：學(xué)號(hào)：姓名：教師：時(shí)間：目錄一、設(shè)計(jì)要求3=1\*GB4㈠、問(wèn)題描述3=2\*GB4㈡、需求分析3概要設(shè)計(jì)3=1\*GB4㈠、存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)3=2\*GB4㈡、系統(tǒng)功能設(shè)計(jì)4三、模塊設(shè)計(jì)6=1\*GB4㈠、模塊設(shè)計(jì)6=2\*GB4㈡、系統(tǒng)子程序及功能設(shè)計(jì)6=3\*GB4㈢、函數(shù)主要調(diào)用關(guān)系圖6四、詳細(xì)設(shè)計(jì)7五、系統(tǒng)實(shí)現(xiàn)13=1\*GB4㈠、源代碼13=2\*GB4㈡、調(diào)試分析31=3\*GB4㈢、輸出界面45六、設(shè)計(jì)總結(jié)46解決沖突：開(kāi)始開(kāi)始i=c/2+1i=c/2+1NNi<HASHSIZEi<HASHSIZEYYN沖突次數(shù)是否為偶數(shù)？N沖突次數(shù)是否為偶數(shù)？Y Y沖突次數(shù)加一計(jì)算哈希地址（沖突次數(shù)加一計(jì)算哈希地址（-i*i）沖突次數(shù)加一計(jì)算哈希地址（+i*i）NN發(fā)生沖突，重置i發(fā)生沖突，重置i哈希地址>=0 YY返回False返回False返回哈希地址結(jié)束結(jié)束開(kāi)始哈希查找：開(kāi)始輸入要查詢(xún)的電話(huà)號(hào)碼或者姓名輸入要查詢(xún)的電話(huà)號(hào)碼或者姓名通過(guò)哈希函數(shù)獲得關(guān)鍵字的通過(guò)哈希函數(shù)獲得關(guān)鍵字的KEY哈希表哈希表KEY不為空且與關(guān)鍵字不同Y解決沖突返回沖突次數(shù)和Y解決沖突返回沖突次數(shù)和KEY地址NN結(jié)束結(jié)束Y哈希表Y哈希表KEY為空且關(guān)鍵字相同輸出聯(lián)系人信息輸出聯(lián)系人信息輸出查無(wú)此人輸出查無(wú)此人NN三、模塊設(shè)計(jì)=1\*GB4㈠、模塊設(shè)計(jì)本程序共用包含三個(gè)模塊：主程序模塊、創(chuàng)建哈希表模塊和增刪改除運(yùn)算模塊。其調(diào)用關(guān)系如圖：主程序模塊主程序模塊創(chuàng)建哈希表模塊創(chuàng)建哈希表模塊 增刪改除模塊增刪改除模塊=2\*GB4㈡、系統(tǒng)子程序及功能設(shè)計(jì)本程序共設(shè)置17個(gè)子程序，各子程序的函數(shù)名及功能說(shuō)明如下;1、voidMenu();//菜單2、voidCreate(Record*record);//創(chuàng)建新的通訊錄3、voidCreateHash1(HashTable*H,Record*record);//以姓名為關(guān)鍵字，建立相應(yīng)的哈希表4、voidCreateHash2(HashTable*H,Record*record);//以姓名為關(guān)鍵字，建立相應(yīng)的哈希表5、intHash1(charname[]);//哈希函數(shù)(姓名)6、intHash2(chartele[]);//哈希函數(shù)(電話(huà)號(hào)碼)7、voidAdd(Record*record);//添加聯(lián)系人8、voidDelete(HashTable*H,int&c);//刪除聯(lián)系人9、voidAlter(HashTable*H,int&c);//修改聯(lián)系人10、voidSearchHash1(HashTable*H,int&c);//在通訊錄里查找姓名關(guān)鍵字，并打印出來(lái)11、voidSearchHash2(HashTable*H,int&c);//在通訊錄里查找電話(huà)號(hào)碼關(guān)鍵字，并打印出來(lái)12、intcollision(intp,int&c);//沖突處理函數(shù)，用于解決沖突13、inteq(charx[],chary[]);//關(guān)鍵字比較14、voidShow(Record*record);//顯示通訊錄15、voidLoad();//讀取通訊錄16、voidSave(HashTable*H);//保存通訊錄17、voidQuit();//退出=3\*GB4㈢函數(shù)主要調(diào)用關(guān)系圖所有子函數(shù)Main()Menu()所有子函數(shù)Main()Menu()四、詳細(xì)設(shè)計(jì)系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)(1)主函數(shù)設(shè)計(jì)模塊intmain(intargc,char*argv[]){ while(en!=11) { switch(en) { 調(diào)用相應(yīng)函數(shù)執(zhí)行相應(yīng)操作，并輸出操作結(jié)果 } }判斷哈希表是否滿(mǎn)，若滿(mǎn)則擴(kuò)容 return0;}(2)創(chuàng)建通訊錄voidCreate(Record*record){ system("CLS");//調(diào)用DOS命令CLS能夠清屏 FILE*fp1,*fp2;//定義指向文件的指針 if((fp1=fopen("record.txt","r"))!=NULL)//如果存在文件，打開(kāi)文件，只讀 {fclose(fp1);}//關(guān)閉文件 else{//如果不存在文件，創(chuàng)建一個(gè)record.txt文件 fp2=fopen("record.txt","w");//以寫(xiě)的方式打開(kāi)文件 fclose(fp2);}//關(guān)閉文件 cout<<"\t\t通訊錄創(chuàng)建成功！"<<endl;cout<<"\t\t輸入要添加的個(gè)數(shù)："; cin>>num; for(inti=0;i<num;i++){//從鍵盤(pán)輸入聯(lián)系人信息 intii=0; cout<<"\n\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的姓名（不超過(guò)4個(gè)字）："; cin>>record[i].name;//保存在record結(jié)構(gòu)體數(shù)組中 for(intj=0;j<i&&i>0;j++){//每次輸入姓名后判斷是否重復(fù) if(eq(record[j].name,record[i].name)==1){ cout<<"\t\t第"<<j+1<<"個(gè)和第"<<i+1<<"個(gè)聯(lián)系人重復(fù)！請(qǐng)重新輸入："; cout<<endl;//一旦重復(fù)，提示重復(fù)并請(qǐng)求重新輸入 ii=1;//標(biāo)示有重復(fù)，中斷其余的信息輸入 i--;} }//同時(shí)刪去剛剛輸入的信息 if(ii==0){//表示沒(méi)有重復(fù)元素，可以繼續(xù)輸入 cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的電話(huà)號(hào)碼（不超過(guò)12個(gè)數(shù)字）："; cin>>record[i].tele; cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的地址（不超過(guò)10個(gè)字）："; cin>>record[i].add;} } cout<<"\t\t添加成功！"<<endl;}(3)建立哈希表voidCreateHash1(HashTable*H,Record*record){//以姓名為關(guān)鍵字，建立相應(yīng)的哈希表 system("CLS");//調(diào)用DOS命令CLS能夠清屏 inti,p=-1,c,pp; for(i=0;i<num;i++){ c=0;//定義沖突次數(shù)初值為0 p=Hash1(record[i].name);//獲得關(guān)鍵字的哈希表地址 pp=p; while(H->elem[pp]!=NULL){//若哈希表地址不為空 pp=collision(p,c);//解決沖突 if(pp<0){//返回值為負(fù)，沖突無(wú)法解決cout<<"第"<<i+1<<"記錄無(wú)法解決沖突"<<endl;//顯示第幾次沖突無(wú)法解決 continue;//無(wú)法解決沖突，跳入下一循環(huán) }} H->elem[pp]=&(record[i]);//求得哈希地址，將信息存入哈希表中 H->count++;//同時(shí)哈希表計(jì)數(shù)器加一cout<<"第"<<i+1<<"個(gè)記錄沖突次數(shù)為"<<c<<".\n";}//需要顯示沖突次數(shù)時(shí)輸出 cout<<"哈希表（姓名）組建完成！"<<endl; cout<<"此哈希表容量為"<<HASHSIZE<<endl; cout<<"當(dāng)前哈希表存儲(chǔ)記錄個(gè)數(shù)為"<<H->count<<endl; cout<<"\n請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl;}(4)解決沖突intcollision(intp,int&c)//參數(shù)p為哈希表中的存儲(chǔ)位置，&c為二次探測(cè)增量地址，每次不變?yōu)?{//沖突處理函數(shù)，采用二次探測(cè)再散列法解決沖突 inti,q; i=c/2+1; while(i<HASHSIZE){ if(c%2==0)//偶數(shù)加上i的平方 {c++; q=(p+i*i)%HASHSIZE; if(q>=0) returnq;//返回哈希地址 else i=c/2+1;//發(fā)生沖突，重置i } else//奇數(shù)減去i的平方 {q=(p-i*i)%HASHSIZE; c++; if(q>=0) returnq;//返回哈希地址 else i=c/2+1;//發(fā)生沖突，重置i } } returnFAILURE;//無(wú)法解決沖突，返回failure}查找voidSearchHash1(HashTable*H,int&c){//在通訊錄里查找姓名關(guān)鍵字，若查找成功，顯示信息 system("CLS"); charname[10]; cout<<"\n\t\t請(qǐng)輸入要查找記錄的姓名："; cin>>name; intp,pp; p=Hash1(name);//將關(guān)鍵字轉(zhuǎn)換得到其哈希地址 pp=p; while((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==0)) pp=collision(p,c);//如果此哈希地址不為空且姓名不相同，則繼續(xù)尋找直到哈希地址為空或者姓名相同 if((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==1)){//哈希地址不為空且姓名相同，說(shuō)明找到了 cout<<"\t\t查找成功！\n\t\t查找過(guò)程沖突次數(shù)為"<<c<<"．\n\n\t\t以下是您需要要查找的信息：\n"; cout<<"\t\t姓名："<<H->elem[pp]->name<<endl; cout<<"\t\t電話(huà)號(hào)碼："<<H->elem[pp]->tele<<endl; cout<<"\t\t聯(lián)系地址："<<H->elem[pp]->add<<endl;} else//否則此哈希地址為空或者姓名都不相同，說(shuō)明查無(wú)此人cout<<"\n\t\t此人不存在，查找不成功!\n"; cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; }(6)添加voidAdd(Record*record){ system("CLS");//調(diào)用DOS命令CLS能夠清屏 cout<<"\n\t\t輸入要添加的個(gè)數(shù)："; cin>>m; for(inti=num;i<m+num;i++){//鍵盤(pán)輸入信息 intii=0; cout<<"\n\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的姓名："; cin>>record[i].name;//將數(shù)據(jù)輸入record數(shù)組中 for(intj=0;j<i&&i>0;j++){//判斷是否重復(fù) if(eq(record[j].name,record[i].name)==1){//若兩個(gè)字符串相等則重復(fù) cout<<"\t\t第"<<j+1<<"個(gè)和第"<<i+1<<"個(gè)聯(lián)系人重復(fù)！請(qǐng)重新輸入："; cout<<endl; ii=1;//提示重復(fù)，i--刪去輸入的信息 i--;} } if(ii==0){//沒(méi)有重復(fù)項(xiàng) cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的電話(huà)號(hào)碼："; cin>>record[i].tele; cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的地址："; cin>>record[i].add;}} num=num+m;//統(tǒng)計(jì)總?cè)藬?shù)=創(chuàng)建人數(shù)+添加人數(shù) cout<<"\t\t添加成功！"<<endl; cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl;}刪除voidDelete(HashTable*H,int&c){//在通訊錄里查找電話(huà)號(hào)碼關(guān)鍵字，若查找成功，顯示信息然后刪除 system("CLS");//調(diào)用DOS命令CLS能夠清屏 chartele[12]; charname[10]; chartem='Y',tem2=NULL,tem3='y',tem4=NULL; while(tem=='Y'||(tem3=='y')||(tem3=='Y')) { system("CLS");//調(diào)用DOS命令CLS能夠清屏 cout<<"\n\t\t┏━━━━━━━━━━━━━━━━━━━━━┓";cout<<"\n\t\t┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃";cout<<"\n\t\t┗━━━━━━━━━━━━━━━━━━━━━┛"; cout<<"\n\t\t輸入電話(huà)號(hào)碼——1，輸入姓名——2\n"; cout<<"\t\t請(qǐng)輸入要?jiǎng)h除記錄的電話(huà)號(hào)碼或者姓名："; cin>>tem; if((tem=='1')&&((tem3=='Y')||(tem3=='y'))) { cout<<"\t\t請(qǐng)輸入要?jiǎng)h除記錄的電話(huà)號(hào)碼："; cin>>tele; intp,pp; p=Hash2(tele); pp=p; while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==0))//沒(méi)有找到 pp=collision(p,c);//解決沖突 if((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==1)){//找到了 cout<<"\t\t以下是您需要?jiǎng)h除的信息："<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t姓名電話(huà)地址"<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t"<<H->elem[pp]->name<<""<<H->elem[pp]->tele<<""<<H->elem[pp]->add<<endl; cout<<"\t\t______________________________"<<endl; do { cout<<"\t\t是否確認(rèn)刪除（Y/N）："; cin>>tem2; if((tem2=='Y')||(tem2=='y')) { //H->elem[pp]=NULL; H->elem[pp]->name[0]='\0'; H->elem[pp]->tele[0]='\0'; H->elem[pp]->add[0]='\0'; cout<<"\t\t恭喜您！刪除聯(lián)系人成功！"; m++;//記錄刪除聯(lián)系人個(gè)數(shù) } if((tem2=='N')||(tem2=='n')) { cout<<"\t\t已撤銷(xiāo)刪除！"; } tem4=NULL; if((tem2!='y')&&(tem2!='Y')&&(tem2!='n')&&(tem2!='N')) { cout<<"\t\t輸入錯(cuò)誤！\n\t\t是否重新輸入（Y/N）："; cin>>tem4; } }while((tem4=='Y')||(tem4=='y')); } else cout<<"\t\t此人不存在，刪除失??！╭(╯3╰)╮"; } if((tem=='2')&&((tem3=='Y')||(tem3=='y'))) { cout<<"\t\t請(qǐng)輸入要?jiǎng)h除記錄的姓名："; cin>>name; intp,pp; p=Hash1(name); pp=p; while((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==0)) pp=collision(p,c); if((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==1)) { cout<<"\t\t以下是您需要修改的信息："<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t姓名電話(huà)地址"<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t"<<H->elem[pp]->name<<""<<H->elem[pp]->tele<<""<<H->elem[pp]->add<<endl; cout<<"\t\t______________________________"<<endl; do { cout<<"\t\t是否確認(rèn)刪除（Y/N）："; cin>>tem2; if((tem2=='Y')||(tem2=='y')) { H->elem[pp]->name[0]='\0'; H->elem[pp]->tele[0]='\0'; H->elem[pp]->add[0]='\0'; cout<<"\t\t恭喜您！刪除聯(lián)系人成功！"; m++;//記錄刪除聯(lián)系人個(gè)數(shù) } if((tem2=='N')||(tem2=='n')) { cout<<"\t\t已撤銷(xiāo)刪除！"; } tem4=NULL; if((tem2!='y')&&(tem2!='Y')&&(tem2!='n')&&(tem2!='N')) {cout<<"\t\t輸入錯(cuò)誤！\n\t\t是否重新輸入（Y/N）："; cin>>tem4;} }while((tem4=='Y')||(tem4=='y'));//重新輸入是否確認(rèn)刪除 } elsecout<<"\t\t此人不存在，刪除失?。〃q(╯3╰)╮"<<endl; } else cout<<"\n\t\t輸入錯(cuò)誤！"; if((tem4!='Y')&&(tem4!='y')){ cout<<"\n\n\t\t是否繼續(xù)刪除？（Y/N）"; cin>>tem3; }} num=num-m;//統(tǒng)計(jì)刪除后聯(lián)系表總?cè)藬?shù) cout<<"\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl;getchar();}五、系統(tǒng)實(shí)現(xiàn)=1\*GB4㈠、源代碼#include<stdio.h>#include<stdlib.h>#include<fstream>#include<iostream>#include<string>usingnamespacestd;#defineHASHSIZE20//哈希表長(zhǎng)#defineMAXSIZE20//通訊錄記錄表長(zhǎng)#defineFAILURE0#defineSUCCESS1#defineMax_name10#defineMax_tele12#defineMax_add10typedefstructpepole{ charname[Max_name];//姓名 chartele[Max_tele];//電話(huà) charadd[Max_add];//地址}Record;typedefstruct{Record*elem[HASHSIZE];//數(shù)據(jù)元素存儲(chǔ)地址 intsize;//哈希表容量 intcount;//哈希表當(dāng)前存儲(chǔ)量}HashTable;intnum=0;//記錄聯(lián)系人個(gè)數(shù)intm=0;//統(tǒng)計(jì)增加刪除人數(shù)//函數(shù)聲明voidMenu();//菜單voidCreate(Record*record);//創(chuàng)建新的通訊錄voidCreateHash1(HashTable*H,Record*record);//以姓名為關(guān)鍵字，建立相應(yīng)的哈希表voidCreateHash2(HashTable*H,Record*record);//以電話(huà)號(hào)碼為關(guān)鍵字，建立相應(yīng)的哈希表intHash1(charname[]);//哈希函數(shù)(姓名)intHash2(chartele[]);//哈希函數(shù)(電話(huà)號(hào)碼)voidAdd(Record*record);//添加聯(lián)系人voidDelete(HashTable*H,int&c);//刪除聯(lián)系人voidAlter(HashTable*H,int&c);//修改聯(lián)系人voidSearchHash1(HashTable*H,int&c);//在通訊錄里查找姓名關(guān)鍵字，并打印出來(lái)voidSearchHash2(HashTable*H,int&c);//在通訊錄里查找電話(huà)號(hào)碼關(guān)鍵字，并打印出來(lái)intcollision(intp,int&c);//沖突處理函數(shù)，用于解決沖突inteq(charx[],chary[]);//關(guān)鍵字比較voidShow(Record*record);//顯示通訊錄voidLoad();//讀取通訊錄voidSave(HashTable*H);//保存通訊錄voidQuit();//退出//菜單voidMenu(){ system("CLS");//調(diào)用DOS命令CLS能夠清屏cout<<"\n┏━━━━━━━━━━━━━━━━━━━━━┓"; cout<<"\n┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃"; cout<<"\n┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓"; cout<<"\n┃★★★★★★★哈希表的設(shè)計(jì)與實(shí)現(xiàn)★★★★★★★┃"; cout<<"\n┃【0】.創(chuàng)建聯(lián)系人┃"; cout<<"\n┃【1】.添加聯(lián)系人┃"; cout<<"\n┃【2】.刪除聯(lián)系人┃"; cout<<"\n┃【3】.修改聯(lián)系人┃"; cout<<"\n┃【4】.建立姓名哈希表┃"; cout<<"\n┃【5】.建立電話(huà)號(hào)碼哈希表┃"; cout<<"\n┃【6】.查找聯(lián)系人（用姓名查找）┃"; cout<<"\n┃【7】.查找聯(lián)系人（用電話(huà)查找）┃"; cout<<"\n┃【8】.顯示通訊錄┃"; cout<<"\n┃【9】.保存通訊錄┃"; cout<<"\n┃【10】.讀取通訊錄┃"; cout<<"\n┃【11】.退出系統(tǒng)┃"; cout<<"\n┃溫馨提示：┃"; cout<<"\n┃@.進(jìn)行6操作前請(qǐng)先輸出4┃"; cout<<"\n┃@.進(jìn)行7操作前請(qǐng)先輸出3┃"; cout<<"\n┃@.進(jìn)行1、2、3操作前請(qǐng)先輸出3、4┃"; cout<<"\n┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛";}//創(chuàng)建新的通訊錄voidCreate(Record*record){ system("CLS");//調(diào)用DOS命令CLS能夠清屏 FILE*fp1,*fp2; if((fp1=fopen("record.txt","r"))!=NULL)//打開(kāi)文件，只讀 { fclose(fp1);//關(guān)閉文件 } else { fp2=fopen("record.txt","w"); fclose(fp2); } cout<<"\n\t\t┏━━━━━━━━━━━━━━━━━━━━━┓"; cout<<"\n\t\t┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃"; cout<<"\n\t\t┗━━━━━━━━━━━━━━━━━━━━━┛"; cout<<"\t\t\t通訊錄創(chuàng)建成功！"<<endl;cout<<"\t\t輸入要添加的個(gè)數(shù)："; cin>>num; for(inti=0;i<num;i++) { intii=0; cout<<"\n\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的姓名（不超過(guò)4個(gè)字）："; cin>>record[i].name; for(intj=0;j<i&&i>0;j++) { if(eq(record[j].name,record[i].name)==1) { cout<<"\t\t第"<<j+1<<"個(gè)和第"<<i+1<<"個(gè)聯(lián)系人重復(fù)！請(qǐng)重新輸入："; cout<<endl; ii=1; i--; } } if(ii==0) { cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的電話(huà)號(hào)碼（不超過(guò)12個(gè)數(shù)字）："; cin>>record[i].tele; cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的地址（不超過(guò)10個(gè)字）："; cin>>record[i].add; } }getchar(); cout<<"\t\t添加成功！"<<endl; cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; getchar();}//創(chuàng)建姓名哈希表voidCreateHash1(HashTable*H,Record*record)//以姓名為關(guān)鍵字，建立相應(yīng)的哈希表{ system("CLS");//調(diào)用DOS命令CLS能夠清屏 cout<<"\n┏━━━━━━━━━━━━━━━━━━━━━┓"; cout<<"\n┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃"; cout<<"\n┗━━━━━━━━━━━━━━━━━━━━━┛"; getchar(); inti,p=-1,c,pp; for(i=0;i<num;i++) { c=0; p=Hash1(record[i].name); pp=p; while(H->elem[pp]!=NULL) { pp=collision(p,c); if(pp<0) { cout<<"\n\t\t┏━━━━━━━━━━━━━━━━━━━━━┓"; cout<<"\n\t\t┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃"; cout<<"\n\t\t┗━━━━━━━━━━━━━━━━━━━━━┛"; cout<<"\t\t第"<<i+1<<"記錄無(wú)法解決沖突"<<endl;//需要顯示沖突次數(shù)時(shí)輸出 continue; }//無(wú)法解決沖突，跳入下一循環(huán) } H->elem[pp]=&(record[i]);//求得哈希地址，將信息存入 H->count++; cout<<endl; cout<<"\t\t第"<<i+1<<"個(gè)記錄沖突次數(shù)為"<<c<<".\n";//需要顯示沖突次數(shù)時(shí)輸出 } cout<<"\n\t\t哈希表（姓名）組建完成！"<<endl; cout<<"\t\t此哈希表容量為"<<HASHSIZE<<endl; cout<<"\t\t當(dāng)前哈希表存儲(chǔ)記錄個(gè)數(shù)為"<<H->count<<endl; cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; getchar();}//創(chuàng)建電話(huà)號(hào)碼哈希表voidCreateHash2(HashTable*H,Record*record)//以電話(huà)號(hào)碼為關(guān)鍵字，建立相應(yīng)的哈希表{ system("CLS");//調(diào)用DOS命令CLS能夠清屏 cout<<"\n┏━━━━━━━━━━━━━━━━━━━━━┓"; cout<<"\n┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃"; cout<<"\n┗━━━━━━━━━━━━━━━━━━━━━┛"; getchar(); inti,p=-1,c,pp; for(i=0;i<num;i++) { c=0; p=Hash2(record[i].tele); pp=p; while(H->elem[pp]!=NULL) {pp=collision(p,c);//若哈希地址沖突，進(jìn)行沖突處理if(pp<0) { cout<<"\n\t\t┏━━━━━━━━━━━━━━━━━━━━━┓";cout<<"\n\t\t┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃";cout<<"\n\t\t┗━━━━━━━━━━━━━━━━━━━━━┛"; cout<<"\t\t第"<<i+1<<"條記錄無(wú)法解決沖突"<<endl;//需要顯示沖突次數(shù)時(shí)輸出continue; }//無(wú)法解決沖突，跳入下一循環(huán) } H->elem[pp]=&(record[i]);//求得哈希地址，將信息存入 H->count++; cout<<endl; cout<<"\t\t第"<<i+1<<"個(gè)記錄沖突次數(shù)為"<<c<<".\n";//需要顯示沖突次數(shù)時(shí)輸出 } cout<<"\n\t\t哈希表（電話(huà)號(hào)碼）組建完成！"<<endl; cout<<"\t\t此哈希表容量為"<<HASHSIZE<<endl; cout<<"\t\t當(dāng)前哈希表存儲(chǔ)記錄個(gè)數(shù)為"<<H->count<<endl; cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; getchar();}//哈希函數(shù)intHash1(charname[]){//哈希函數(shù)(姓名) longn; intm; n=atoi(name);//把字符串轉(zhuǎn)換成整型數(shù) m=n%HASHSIZE;//用除留余數(shù)法構(gòu)造哈希函數(shù) returnm;//并返回模值}intHash2(chartele[]){//哈希函數(shù)(電話(huà)) longn; intm; n=atoi(tele);//把字符串轉(zhuǎn)換成整型數(shù). m=n%HASHSIZE;//用除留余數(shù)法構(gòu)造哈希函數(shù) returnm;//并返回模值}//添加聯(lián)系人voidAdd(Record*record)//鍵盤(pán)輸入信息{ system("CLS");//調(diào)用DOS命令CLS能夠清屏 cout<<"\n\t\t┏━━━━━━━━━━━━━━━━━━━━━┓"; cout<<"\n\t\t┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃"; cout<<"\n\t\t┗━━━━━━━━━━━━━━━━━━━━━┛"; cout<<"\n\t\t輸入要添加的個(gè)數(shù)："; cin>>m; for(inti=num;i<m+num;i++) { intii=0; cout<<"\n\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的姓名："; cin>>record[i].name; for(intj=0;j<i&&i>0;j++) { if(eq(record[j].name,record[i].name)==1) { cout<<"\t\t第"<<j+1<<"個(gè)和第"<<i+1<<"個(gè)聯(lián)系人重復(fù)！請(qǐng)重新輸入："; cout<<endl; ii=1; i--; } } if(ii==0) { cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的電話(huà)號(hào)碼："; cin>>record[i].tele; cout<<"\t\t請(qǐng)輸入第"<<i+1<<"個(gè)記錄的地址："; cin>>record[i].add; } } num=num+m; getchar(); cout<<"\t\t添加成功！"<<endl; cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; getchar();}//刪除聯(lián)系人voidDelete(HashTable*H,int&c){//在通訊錄里查找電話(huà)號(hào)碼關(guān)鍵字，若查找成功，顯示信息然后刪除 system("CLS");//調(diào)用DOS命令CLS能夠清屏 chartele[12] charname[10]; chartem='Y',tem2=NULL,tem3='y',tem4=NULL; while(tem=='Y'||(tem3=='y')||(tem3=='Y')) { system("CLS");//調(diào)用DOS命令CLS能夠清屏cout<<"\n\t\t┏━━━━━━━━━━━━━━━━━━━━━┓";cout<<"\n\t\t┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃";cout<<"\n\t\t┗━━━━━━━━━━━━━━━━━━━━━┛"; cout<<"\n\t\t輸入電話(huà)號(hào)碼——1，輸入姓名——2\n"; cout<<"\t\t請(qǐng)輸入要?jiǎng)h除記錄的電話(huà)號(hào)碼或者姓名："; cin>>tem; if((tem=='1')&&((tem3=='Y')||(tem3=='y'))) { cout<<"\t\t請(qǐng)輸入要?jiǎng)h除記錄的電話(huà)號(hào)碼："; cin>>tele; intp,pp; p=Hash2(tele); pp=p; while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==0))//沒(méi)有找到 pp=collision(p,c);//解決沖突 if((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==1)){//找到了 cout<<"\t\t以下是您需要?jiǎng)h除的信息："<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t姓名電話(huà)地址"<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t"<<H->elem[pp]->name<<""<<H->elem[pp]->tele<<""<<H->elem[pp]->add<<endl; cout<<"\t\t______________________________"<<endl; do { cout<<"\t\t是否確認(rèn)刪除（Y/N）："; cin>>tem2; if((tem2=='Y')||(tem2=='y')) { //H->elem[pp]=NULL; H->elem[pp]->name[0]='\0'; H->elem[pp]->tele[0]='\0'; H->elem[pp]->add[0]='\0'; cout<<"\t\t恭喜您！刪除聯(lián)系人成功！"; m++;//記錄刪除聯(lián)系人個(gè)數(shù) } if((tem2=='N')||(tem2=='n')) { cout<<"\t\t已撤銷(xiāo)刪除！"; } tem4=NULL; if((tem2!='y')&&(tem2!='Y')&&(tem2!='n')&&(tem2!='N')) { cout<<"\t\t輸入錯(cuò)誤！\n\t\t是否重新輸入（Y/N）："; cin>>tem4; } }while((tem4=='Y')||(tem4=='y')); } else cout<<"\t\t此人不存在，刪除失??！╭(╯3╰)╮"; } if((tem=='2')&&((tem3=='Y')||(tem3=='y'))) { cout<<"\t\t請(qǐng)輸入要?jiǎng)h除記錄的姓名："; cin>>name; intp,pp; p=Hash1(name); pp=p; while((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==0)) pp=collision(p,c); if((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==1)) { cout<<"\t\t以下是您需要修改的信息："<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t姓名電話(huà)地址"<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t"<<H->elem[pp]->name<<""<<H->elem[pp]->tele<<""<<H->elem[pp]->add<<endl; cout<<"\t\t______________________________"<<endl; do { cout<<"\t\t是否確認(rèn)刪除（Y/N）："; cin>>tem2; if((tem2=='Y')||(tem2=='y')) { H->elem[pp]->name[0]='\0'; H->elem[pp]->tele[0]='\0'; H->elem[pp]->add[0]='\0'; cout<<"\t\t恭喜您！刪除聯(lián)系人成功！"; m++;//記錄刪除聯(lián)系人個(gè)數(shù) } if((tem2=='N')||(tem2=='n')) { cout<<"\t\t已撤銷(xiāo)刪除！"; } tem4=NULL; if((tem2!='y')&&(tem2!='Y')&&(tem2!='n')&&(tem2!='N')) { cout<<"\t\t輸入錯(cuò)誤！\n\t\t是否重新輸入（Y/N）："; cin>>tem4; } }while((tem4=='Y')||(tem4=='y')); } else cout<<"\t\t此人不存在，刪除失?。〃q(╯3╰)╮"<<endl; } else cout<<"\n\t\t輸入錯(cuò)誤！"; if((tem4!='Y')&&(tem4!='y')) { cout<<"\n\n\t\t是否繼續(xù)刪除？（Y/N）"; cin>>tem3; } } num=num-m;//統(tǒng)計(jì)刪除后聯(lián)系表總?cè)藬?shù) cout<<"\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl;getchar();}//修改聯(lián)系人voidAlter(HashTable*H,int&c)//在通訊錄里修改某人信息{ chartele[12]; charname[10]; chartem='Y'; while(tem=='Y'||tem=='y') { system("CLS"); cout<<"\n\t\t┏━━━━━━━━━━━━━━━━━━━━━┓";cout<<"\n\t\t┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃";cout<<"\n\t\t┗━━━━━━━━━━━━━━━━━━━━━┛"; cout<<"\n\t\t輸入電話(huà)號(hào)碼——1，輸入姓名——2\n\t\t請(qǐng)輸入要修改記錄的電話(huà)號(hào)碼或者姓名:"; cin>>tem; intii=0; if(tem=='1') { cout<<"\t\t請(qǐng)輸入要修改記錄的電話(huà)號(hào)碼："; cin>>tele; intp,pp; p=Hash2(tele); pp=p; while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==0)) pp=collision(p,c); if((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==1)) { cout<<"\t\t以下是您需要修改的信息："<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t姓名電話(huà)地址"<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t"<<H->elem[pp]->name<<""<<H->elem[pp]->tele<<""<<H->elem[pp]->add<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t請(qǐng)輸入修改后記錄的用戶(hù)名:"; cin>>name; for(intj=0;j<HASHSIZE&&ii==0;j++) { if(H->elem[j]!=NULL&&pp!=j) { if(eq(H->elem[j]->name,name)==1) { cout<<"\n\t\t聯(lián)系人重復(fù)！請(qǐng)重新修改！"; ii=1; } } } if(ii==0) { strcpy(H->elem[pp]->name,name); cout<<"\t\t請(qǐng)輸入修改后記錄的電話(huà)號(hào)碼:"; cin>>H->elem[pp]->tele; cout<<"\t\t請(qǐng)輸入修改后記錄的地址:"; cin>>H->elem[pp]->add; cout<<"\t\t修改成功!!!"<<endl; } } else { cout<<"\t\t此人不存在，修改失敗！╭(╯3╰)╮"<<endl; } } if(tem=='2') { cout<<"\t\t請(qǐng)輸入要修改記錄的姓名："; cin>>name; intp,pp; p=Hash1(name); pp=p; while((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==0)) pp=collision(p,c); if((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==1)) { cout<<"\t\t以下是您需要修改的信息："<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t姓名電話(huà)地址"<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t"<<H->elem[pp]->name<<""<<H->elem[pp]->tele<<""<<H->elem[pp]->add<<endl; cout<<"\t\t______________________________"<<endl; cout<<"\t\t請(qǐng)輸入修改后記錄的用戶(hù)名:"; cin>>name; for(intj=0;j<HASHSIZE&&ii==0;j++) { if(H->elem[j]!=NULL&&j!=pp)//這里修改時(shí)，與原來(lái)一樣時(shí)，應(yīng)該判為可以修改，但是運(yùn)行結(jié)果不對(duì) { if(eq(H->elem[j]->name,name)==1) { cout<<"\n\t\t聯(lián)系人重復(fù)！請(qǐng)重新修改！"; ii=1; } } } if(ii==0) { strcpy(H->elem[pp]->name,name); cout<<"\t\t請(qǐng)輸入修改后記錄的電話(huà)號(hào)碼:"; cin>>H->elem[pp]->tele; cout<<"\t\t請(qǐng)輸入修改后記錄的地址:"; cin>>H->elem[pp]->add; cout<<"\t\t修改成功!!!"<<endl; } } else { cout<<"\n\t\t此人不存在，修改失??！╭(╯3╰)╮"<<endl; } } if(tem!='1'&&tem!='2') cout<<"\n\t\t輸入錯(cuò)誤！"; cout<<"\n\t\t是否繼續(xù)修改？（Y/N）"; cin>>tem; } getchar();}//查找聯(lián)系人voidSearchHash1(HashTable*H,int&c){//在通訊錄里查找姓名關(guān)鍵字，若查找成功，顯示信息 system("CLS"); cout<<"\n┏━━━━━━━━━━━━━━━━━━━━━┓";cout<<"\n┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃";cout<<"\n┗━━━━━━━━━━━━━━━━━━━━━┛"; charname[10]; cout<<"\n\t\t請(qǐng)輸入要查找記錄的姓名："; cin>>name; intp,pp; p=Hash1(name); pp=p; while((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==0)) pp=collision(p,c); if((H->elem[pp]!=NULL)&&(eq(name,H->elem[pp]->name)==1)) { cout<<"\t\t查找成功！\n\t\t查找過(guò)程沖突次數(shù)為"<<c<<"．\n\n\t\t以下是您需要要查找的信息：\n"; cout<<"\t\t姓名："<<H->elem[pp]->name<<endl; cout<<"\t\t電話(huà)號(hào)碼："<<H->elem[pp]->tele<<endl; cout<<"\t\t聯(lián)系地址："<<H->elem[pp]->add<<endl; } else cout<<"\n\t\t此人不存在，查找不成功!\n"; getchar(); cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; getchar();}voidSearchHash2(HashTable*H,int&c){//在通訊錄里查找電話(huà)號(hào)碼關(guān)鍵字，若查找成功，顯示信息 system("CLS"); cout<<"\n┏━━━━━━━━━━━━━━━━━━━━━┓";cout<<"\n┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃";cout<<"\n┗━━━━━━━━━━━━━━━━━━━━━┛"; chartele[12]; cout<<"\n\t\t請(qǐng)輸入要查找記錄的電話(huà)號(hào)碼："; cin>>tele; intp,pp; p=Hash2(tele); pp=p; while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==0)) pp=collision(p,c); if((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tele)==1)) { cout<<"\t\t查找成功！\n\t\t查找過(guò)程沖突次數(shù)為"<<c<<"．\n\n\t\t以下是您需要要查找的信息：\n"; cout<<"\t\t姓名："<<H->elem[pp]->name<<endl; cout<<"\t\t電話(huà)號(hào)碼："<<H->elem[pp]->tele<<endl; cout<<"\t\t聯(lián)系地址："<<H->elem[pp]->add<<endl; } else cout<<"\n\t\t此人不存在，查找不成功!\n"; getchar(); cout<<"\n\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; getchar();}//沖突處理函數(shù)，用于解決沖突intcollision(intp,int&c)//參數(shù)p為哈希表中的存儲(chǔ)位置，c用來(lái)記錄沖突次數(shù),查找成功時(shí)顯示沖突次數(shù){//沖突處理函數(shù)，采用二次探測(cè)再散列法解決沖突 inti,q; i=c/2+1; while(i<HASHSIZE) { if(c%2==0)//偶數(shù)加上i的平方 { c++; q=(p+i*i)%HASHSIZE; if(q>=0) returnq;//返回哈希地址 else i=c/2+1;//發(fā)生沖突，重置i } else//奇數(shù)減去i的平方 { q=(p-i*i)%HASHSIZE; c++; if(q>=0) returnq;//返回哈希地址 else i=c/2+1;//發(fā)生沖突，重置i } } returnFAILURE;//無(wú)法解決沖突，返回failure}//關(guān)鍵字比較inteq(charx[],chary[])//關(guān)鍵字比較，相等返回SUCCESS；否則返回UNSUCCESS{ if(strcmp(x,y)==0)//當(dāng)s1<s2時(shí)，返回為負(fù)數(shù)不是-1 {//當(dāng)s1==s2時(shí)，返回值=0returnSUCCESS;//當(dāng)s1>s2時(shí)，返回正數(shù)不是1 } elsereturnFAILURE;}//顯示通訊錄voidShow(Record*record)//顯示通訊錄中所有記錄{ inti;system("CLS");//調(diào)用DOS命令CLS能夠清屏 cout<<"\n┏━━━━━━━━━━━━━━━━━━━━━┓";cout<<"\n┃歡迎使用電話(huà)號(hào)碼查找系統(tǒng)┃";cout<<"\n┗━━━━━━━━━━━━━━━━━━━━━┛";if(record!=NULL) { cout<<"\n\t\t______________________________"<<endl; cout<<"\t\t姓名\t電話(huà)\t\t地址"<<endl; cout<<"\t\t______________________________"<<endl; for(i=0;i<num+m;i++) { if(record[i].name[0]!='\0') { cout<<"\t\t"<<record[i].name<<"\t"<<record[i].tele<<"\t"<<record[i].add<<endl; cout<<"\t\t______________________________"<<endl; } } } else { cout<<"\t\t不好意思！您還未存入任何聯(lián)系人！O(∩_∩)O~"<<endl; } getchar(); cout<<"\t\t請(qǐng)按ENTER進(jìn)入添加通訊錄菜單"<<endl; getchar();}//讀取通訊錄voidLoad(){//從record.txt文件中讀取通訊錄 system("CLS"); ifstreaminFile; inFile.open("record.txt");//打開(kāi)文件 stringstr;//行字符串緩存 getchar(); if(inFile.is_open())//若成功打開(kāi)文件 { while(!inFile.eof())//若未到文件結(jié)束 { getline(inFile,str,'\n');//讀取一行內(nèi)容，并存入緩存str中，'\n'表示一行結(jié)束的回車(chē)符 cout<<str<<endl;//把緩存內(nèi)容輸出到屏幕 } getchar(); cout<<""; } inFile.close();}//保存通訊錄voidSave(HashTable*H)//將記錄保存到指定文件{ system("CLS"); FILE*fp; if((fp=fopen("record.txt","w"))!=NULL) { fprintf(fp,"#############################################################\n"); fprintf(fp,"====================→用戶(hù)信息記錄表←===================\n"); fprintf(fp,"#############################################################\n"); for(inti=