1、哈希表（散列表）的設計與實現【問題描述】 設計哈希表實現電話號碼查找系統。【基本要求】 (1) 設每個記錄有下列數據項：電話號碼、用戶名、地址； (2) 從鍵盤輸入各記錄，分別以電話號碼為關鍵字建立散列表； (3)采用拉鏈法解決沖突； (4)查找并顯示給定電話號碼的記錄； (5) 查找并顯示給定用戶名的記錄。【選做內容】 (1)系統功能的完善； (2)設計不同的散列函數，比較沖突率； (3)在散列函數確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。地址嫌麻煩沒加，使用的時候要先新建一個空白的data.txt文件。/ hash.cpp : 定義控制臺應用程序的入口點。/#i

2、nclude stdafx.h#include#includeusing namespace std;#define p 100#define z 97#define max 100struct datachar name15;/存放姓名long num;/存放電話號碼;typedef struct hashdatachar name15;long num;hashdata *next;*linklist;data hmax;hashdata nhashmax;hashdata nahashmax;unsigned int bkdrhash(char *str)/字符串哈希值生成函數 unsi

3、gned int seed = 31; / 31 131 1313 13131 131313 etc. unsigned int hash = 0; while (*str) hash = hash * seed + (*str+); return (hash & 0x7fffffff);unsigned int aphash(char *str)/字符串哈希值生成函數 unsigned int hash = 0; int i; for (i=0; *str; i+) if (i & 1) = 0) hash = (hash 3); else hash = (hash 5); return (

4、hash & 0x7fffffff);int datanum(int j)/統計hmax數組中有多少數據for(j=0;jp&hj.num!=null;j+)return j;void wdata()/新建電話簿數據文件for(int i=0;i1;i+)scanf(%s%d,&,&hi.num);file *fp;fp=fopen(data.txt,wb);fwrite(h,sizeof(struct data),1,fp);fclose(fp);void wpdata()/將hmax的數據寫入到文件當中int j=datanum(j);file *fp;fp=fopen(da

5、ta.txt,wb);fwrite(h,sizeof(struct data),j,fp);fclose(fp);void adata()/在電話簿中添加數據并寫入文件for(int i=0;i1;i+)scanf(%s%d,&,&hi.num);file *fp;fp=fopen(data.txt,ab);fwrite(h,sizeof(struct data),1,fp);fclose(fp);void rdata()/讀取文件中的電話簿數據file *fp;fp=fopen(data.txt,rb);fread(h,sizeof(struct data),p,fp);int

6、 j=datanum(j);printf(n編號 姓 名 電 話nn);for(int i=0;ij;i+)printf(%4d ,i+1);printf(%10s %10dn,,hi.num);fclose(fp);void ldata()/載入文件到hmax數組當中file *fp;fp=fopen(data.txt,rb);fread(h,sizeof(struct data),p,fp);fclose(fp);void ddata(int n)/刪除電話簿中數據if(n=0)return;ldata();int j=datanum(j),i;for(i=n;ij;i+)s

7、trcpy(,);hi-1.num=hi.num;hj-1.num=null;wpdata();void numhash(struct data smax)/按電話號碼生成哈希表int k=0;int j=datanum(j);for(int i=0;iname,);p-num=si.num;p-next=nhashk.next;nhashk.next=p;void fnumhash(long n)/按電話號碼在哈希表中查找數據int k=0;k=n%z;linklist p;p=&nhashk;if(p-num=n) printf(n姓 名 電

8、話n);printf(%6s %10dnn,p-name,p-num);elsewhile(p!=null)if(p-num=n)printf(n姓 名 電 話n);printf(%6s %10dnn,p-name,p-num);break;elseif(p-next=null)printf(n該號碼不存在！nn);p=p-next;void namehash(data smax)/按姓名生成哈希表int k=0;int j=datanum(j);for(int i=0;iname,);p-num=si.num;p-next=nahashk.next;nahashk.next=p

9、;void fnamehash(char str3)/按姓名在哈希表中查找數據int k=0;k=bkdrhash(str);k=k%z;linklist p;p=&nahashk;if(aphash(str)=aphash() printf(n姓 名 電 話n);printf(%6s %10dnn,p-name,p-num);elsewhile(p!=null)if(aphash(str)=aphash(p-name)printf(n姓 名 電 話n);printf(%6s %10dnn,p-name,p-num);break;elseif(p-next=null)p

10、rintf(n該姓名不存在！nn);p=p-next;void rnumhash()/輸出按電話號碼生成的哈希表printf(n編號 姓 名 電 話nn);for(int i=0;inext;while(p!=null)printf( -%10s %10d,p-name,p-num);p=p-next;printf(n);elseprintf(%4d,i);printf(%10s %10dn,,nhashi.num);elseprintf(%4d,i);printf(n);void rnamehash()/生成按姓名生成的哈希表printf(n編號 姓 名 電 話nn);

11、for(int i=0;inext;while(p!=null)printf( -%10s %10d,p-name,p-num);p=p-next;printf(n);elseprintf(%4d,i);printf(%10s %10dn,,nahashi.num);elseprintf(%4d,i);printf(n);int _tmain(int argc, _tchar* argv)int m;ldata();numhash(h);namehash(h);cout*電話號碼查詢系統*endlendl;printf(tttt1.電 話 簿ntttt2.按電話查找nt

12、ttt3.按姓名查找ntttt4.顯示哈希表ntttt0.退 出nn);cout*endl;while(scanf(%d,&m)&m!=0)switch(m)case 1:int n;printf(n1.新 建n2.添 加n3.顯 示n4.刪 除n0.退 出n);while(scanf(%d,&n)&n!=0)switch(n)case 1: printf(n姓 名 電 話n);wdata();break;case 2: printf(n姓 名 電 話n);adata();break;case 3:rdata();break;case 4:int n;rdata();printf(n請輸入編號

13、(0.退出刪除):);scanf(%d,&n);ddata(n);break;printf(n1.新 建n2.添 加n3.顯 示n4.刪 除n0.退 出n);break;case 2:int num;/rnumhash();/ldata();/numhash(h);printf(請輸入一個電話號碼:);scanf(%d,&num);fnumhash(num);break;case 3:char name3;/rnamehash();/ldata();/namehash(h);printf(請輸入一個姓名:);scanf(%s,name);fnamehash(name);break;case 4:int