哈希表實驗報告

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