哈希查找算法的源代碼 c語言

1、哈希查找算法的源代碼 c語言【問題描述】針對自己的班集體中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長度不超過R，完成相應(yīng)的建表和查表程序。基本要求假設(shè)人名為中國姓名的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)照，用鏈表法處理沖突。測試數(shù)據(jù)讀取熟悉的30個(gè)人的姓名。#include <fstream>#include <iostream>#include <cmath>using namespace std;#define Maxsize 57 struct record char name20;char tel

2、20;char add20;typedef record * precord;struct HashTable int elemMaxsize; /存放數(shù)組a的下標(biāo)int count; ;typedef HashTable * pHashTable;int Number; /統(tǒng)計(jì)當(dāng)前數(shù)組a中的記錄總數(shù)void Getdata(precord a) /從文件telphone.txt中讀取數(shù)據(jù)存放到數(shù)組a Number=0;ifstream infile("telphone.txt",ios:in|ios:binary);if(!infile) cout<<&quo

3、t;文件打開失敗!n" exit(1);while(!infile.eof() && infile.get()!=EOF) /文件不為空并且文件指針沒有指到結(jié)束符infile.seekg(Number*sizeof(aNumber),ios:beg); /定位文件指針infile.read(char *)&aNumber,sizeof(aNumber);Number+;infile.close();void Add(precord a) /添加記錄 int i,num;cout<<"當(dāng)前文件內(nèi)已有"<<Number&

4、lt;<"條記錄n"cout<<"請輸入添加的個(gè)數(shù):"cin>>num;ofstream ofile("telphone.txt",ios:app);if(! ofile) cout<<"文件打開失敗!" exit(1); for(i=0;i<num;i+) cout<<"請輸入第"<<Number+1<<"個(gè)人的姓名"<<endl;cin>>aN;

5、 cout<<"請輸入第"<<Number+1<<"個(gè)人的電話"<<endl;cin>>aNumber.tel; cout<<"請輸入第"<<Number+1<<"個(gè)人的地址"<<endl;cin>>aNumber.add; ofile.seekp(ios:end);ofile.write(char *)&aNumber,sizeof(aNumber);Number+;ofile.clos

6、e();void Print(precord a) /顯示所有記錄 int i;for(i=0;i<Number;i+)cout<<"第"<<i+1<<"個(gè)人的信息為:n"cout<<" 姓名:"<<<<endl;cout<<" 電話:"<<ai.tel<<endl;cout<<" 地址:"<<ai.add<<endl;int Has

7、h(char str) /除留取余 long val=0;char p20,*p1;strcpy(p,str);p1=p;while(*p1!='0')val=val+*p1+; /將字符串中的所有字符對應(yīng)的ASCII值相加return(val%Maxsize);int derter; /線性增量int Line_Sollution(int address) /采用線性探測解決沖突 derter+;if(derter=Maxsize) return(-1);else return(address+derter)%Maxsize);int n;int Square_Solluti

8、on(int address) /采用平方探測法解決沖突 int j;derter+;if(derter=Maxsize) return -1;n=n*(-1);j=(int(pow(derter,2)*n+address)%Maxsize;return(j);void Init_Hash(pHashTable h) /初始化哈希表 int i;for(i=0;i<Maxsize;i+)h->elemi=-1;int menu;void Creathash_Name(pHashTable h,precord a)/以用戶名為關(guān)鍵字創(chuàng)建哈希表 cout<<"-n

9、"cout<<" 1-以線性探測建表n"cout<<" 2-以平方探測建表n"cout<<"-n"int i,address;cin>>menu;Init_Hash(h);for(i=0;i<Number;i+) derter=0;n=-1;address=Hash();while(h->elemaddress!=-1)if(menu=1) address=Line_Sollution(address);else address=Square_Soll

10、ution(address);if(address=-1) break;if(address!=-1) h->elemaddress=i; h->count+;cout<<"姓名哈希表已成功建立!n"void Search_Name(pHashTable h,precord a) /查找并顯示指定姓名的記錄 cout<<"請輸入要查找的姓名:"char nam20;int address,i=1;cin>>nam;address=Hash(nam);derter=0;n=-1;while(h->ele

11、maddress!=-1 && strcmp(nam,ah->)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);i+;if(address=-1) break;if(h->elemaddress!=-1 && strcmp(nam,ah->)=0) cout<<"你要查找的信息為:n"cout<<" 姓名

12、:"<<ah-><<endl;cout<<" 電話:"<<ah->elemaddress.tel<<endl;cout<<" 地址:"<<ah->elemaddress.add<<endl;cout<<"比較次數(shù)為"<<i<<endl;else cout<<"無此姓名,查找失敗!"void Creathash_te

13、l(pHashTable h,precord a) /以電話號為關(guān)鍵字創(chuàng)建哈希表 cout<<"-n"cout<<" 1-以線性探測建表n"cout<<" 2-以平方探測建表n"cout<<"-n"int i,address;cin>>menu;Init_Hash(h);for(i=0;i<Number;i+) derter=0;n=-1;address=Hash(ai.tel);while(h->elemaddress!=-1)if(menu

14、=1) address=Line_Sollution(address);else address=Square_Sollution(address);if(address=-1) break;if(address!=-1) h->elemaddress=i; h->count+;cout<<"電話號哈希表已成功建立!n"void Search_tel(pHashTable h,precord a)/查找并顯示指定電話號的記錄 cout<<"請輸入要查找的電話:"char telphone20;int address,i

15、=1; /i統(tǒng)計(jì)比較次數(shù)cin>>telphone;address=Hash(telphone);derter=0; n=-1; /初始化線性增量while(h->elemaddress!=-1 && strcmp(telphone,ah->elemaddress.tel)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);i+;if(address=-1) break;if(h->elemaddress!=-1 &&a

16、mp; strcmp(telphone,ah->elemaddress.tel)=0) cout<<"你要查找的信息為:n"cout<<" 姓名:"<<ah-><<endl;cout<<" 電話:"<<ah->elemaddress.tel<<endl;cout<<" 地址:"<<ah->elemaddress.add<<endl;cout&

17、lt;<"比較次數(shù)為"<<i<<endl;else cout<<"無此電話,查找失敗!"void Menu() /功能菜單函數(shù)for(int i=1;i<=5;i+)cout<<endl;cout<<" 電話號碼查詢系統(tǒng)n"cout<<'n'cout<<" n"cout<<" 0-退出 n"cout<<" 1-添加 n"cout<<

18、;" 2-顯示所有 n" cout<<" 3-以性命建立哈希表 n"cout<<" 4-以電話建立哈希表 n"cout<<" 5-按用戶名查找 n"cout<<" 6-按電話號查找 n"cout<<" n"cout<<" 使用說明:n"cout<<" 1.添加新紀(jì)錄后,如要進(jìn)行查找請先進(jìn)行3或4操作n"cout<<" 2.按用戶名查

19、找之前,請先進(jìn)行3操作建立用戶名哈希表n"cout<<" 3.按用戶名查找之前,請先進(jìn)行4操作建立電話號哈希表n"void exit() int i;for(i=1;i<=4;i+)cout<<endl;cout<<" n"cout<<" n"cout<<" 電 話 號 碼 查 詢 系 統(tǒng) n"cout<<" n"cout<<" 謝 謝 您 的 使 用 ! n"cout<<" n"cout<<" n"int main() record aMaxsize;pHashTable H=new HashTable;Getdata(a); /將文件中的數(shù)據(jù)讀入到數(shù)組a中start:Menu();int menu1;cin>>menu1;switch(menu1) case 0:system(&q