題目（7）

散列表的設計與實現1、任務：設計散列表實現電話號碼查找系統。2、設計要求：1)設每個記錄有下列數據項：電話號碼、用戶名、地址；2)

從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表；3)

采用一定的方法解決沖突；4)

查找并顯示給定電話號碼的記錄；5)

查找并顯示給定用戶名的記錄。#include<stdio.h>#include<iostream.h>#include<stdlib.h>#include<string>#include<windows.h>#defineMAXSIZE20//電話薄記錄數量#defineMAX_SIZE20//人名的最大長度#defineHASHSIZE53//定義表長#defineSUCCESS1#defineUNSUCCESS-1#defineLENsizeof(HashTable)typedefintStatus;typedefcharNA[MAX_SIZE];typedefstruct//記錄{NAname;NAtel;NAadd;}Record;typedefstruct//哈希表{Record*elem[HASHSIZE];//數據元素存儲基址intcount;//當前數據元素個數intsize;//當前容量}HashTable;Statuseq(NAx,NAy)//關鍵字比較，相等返回SUCCESS；否則返回UNSUCCESS{if(strcmp(x,y)==0)returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER;//記錄的個數voidgetin(Record*a)//鍵盤輸入各人的信息{cout<<"輸入要添加的個數：\n";cin>>NUM_BER;inti;for(i=0;i<NUM_BER;i++){cout<<"請輸入第"<<i+1<<"個記錄的用戶名:\n";cin>>a[i].name;cout<<"請輸入第"<<i+1<<"個記錄的電話號碼:\n";cin>>a[i].tel;cout<<"請輸入第"<<i+1<<"個記錄的地址:\n";cin>>a[i].add;}}voidShowInformation(Record*a)//顯示輸入的用戶信息{inti;for(i=0;i<NUM_BER;i++)cout<<"\n第"<<i+1<<"個用戶信息:\n姓名："<<a[i].name<<"\n電話號碼："<<a[i].tel<<"\n聯系地址："<<a[i].add<<"\n";}voidCls(Record*a){cout<<"*";system("cls");}longfold(NAs)//人名的折疊處理{char*p;longsum=0;NAss;strcpy(ss,s);//復制字符串，不改變原字符串的大小寫strupr(ss);//將字符串ss轉換為大寫形式p=ss;while(*p!='\0')sum+=*p++;cout<<"\nsum===================="<<sum;returnsum;}intHash1(NAstr)//哈希函數{longn;intm;n=fold(str);//先將用戶名進行折疊處理m=n%HASHSIZE;//折疊處理后的數，用除留余數法構造哈希函數returnm;//并返回模值}intHash2(NAstr)//哈希函數{longn;intm;n=atoi(str);//把字符串轉換成整型數.m=n%HASHSIZE;//用除留余數法構造哈希函數returnm;//并返回模值}Statuscollision(intp,int&c)//沖突處理函數，采用二次探測再散列法解決沖突{inti,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0)returnq;elsei=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0)returnq;elsei=c/2+1;}}returnUNSUCCESS;}voidbenGetTime();voidCreateHash1(HashTable*H,Record*a){//建表，以人的姓名為關鍵字，建立相應的散列表//若哈希地址沖突，進行沖突處理benGetTime();inti,p=-1,c,pp;for(i=0;i<NUM_BER;i++){c=0;p=Hash1(a[i].name);pp=p;while(H->elem[pp]!=NULL){pp=collision(p,c);if(pp<0){cout<<"第"<<i+1<<"記錄無法解決沖突";//需要顯示沖突次數時輸出continue;}//無法解決沖突，跳入下一循環}H->elem[pp]=&(a[i]);//求得哈希地址，將信息存入H->count++;cout<<"第"<<i+1<<"個記錄沖突次數為"<<c<<".\n";//需要顯示沖突次數時輸出}cout<<"\n建表完成!\n此哈希表容量為"<<HASHSIZE<<",當前表內存儲的記錄個數為"<<H->count<<".\n";benGetTime();}voidSearchHash1(HashTable*H,int&c){//在通訊錄里查找姓名關鍵字，若查找成功，顯示信息//c用來記錄沖突次數,查找成功時顯示沖突次數benGetTime();NAstr;cout<<"\n請輸入要查找記錄的姓名：\n";cin>>str;intp,pp;p=Hash1(str);pp=p;while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))pp=collision(p,c);if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1){cout<<"\n查找成功！\n查找過程沖突次數為"<<c<<"．以下是您需要要查找的信息：\n\n";cout<<"姓名："<<H->elem[pp]->name<<"\n電話號碼："<<H->elem[pp]->tel<<"\n聯系地址："<<H->elem[pp]->add<<"\n";}elsecout<<"\n此人不存在，查找不成功!\n";benGetTime();}voidbenGetTime(){SYSTEMTIMEsys;GetLocalTime(&sys);cout<<sys.wYear<<sys.wMonth<<sys.wDay<<sys.wHour<<sys.wMinute<<sys.wSecond<<sys.wMilliseconds;}voidCreateHash2(HashTable*H,Record*a){//建表，以電話號碼為關鍵字，建立相應的散列表//若哈希地址沖突，進行沖突處理benGetTime();inti,p=-1,c,pp;for(i=0;i<NUM_BER;i++){c=0;p=Hash2(a[i].tel);pp=p;while(H->elem[pp]!=NULL){pp=collision(p,c);if(pp<0){cout<<"第"<<i+1<<"記錄無法解決沖突";//需要顯示沖突次數時輸出continue;}//無法解決沖突，跳入下一循環}H->elem[pp]=&(a[i]);//求得哈希地址，將信息存入H->count++;cout<<"第"<<i+1<<"個記錄沖突次數為"<<c<<"。\n";//需要顯示沖突次數時輸出}cout<<"\n建表完成!\n此哈希表容量為"<<HASHSIZE<<",當前表內存儲的記錄個數為"<<H->count<<".\n";benGetTime();}voidSearchHash2(HashTable*H,int&c){//在通訊錄里查找電話號碼關鍵字，若查找成功，顯示信息//c用來記錄沖突次數,查找成功時顯示沖突次數benGetTime();NAtele;cout<<"\n請輸入要查找記錄的電話號碼：\n";cin>>tele;intp,pp;p=Hash2(tele);pp=p;while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1))pp=collision(p,c);if(H->elem[pp]!=NULL&&eq(tele,H->elem[pp]->tel)==1){cout<<"\n查找成功！\n查找過程沖突次數為"<<c<<"．以下是您需要要查找的信息：\n\n";cout<<"姓名："<<H->elem[pp]->name<<"\n電話號碼："<<H->elem[pp]->tel<<"\n聯系地址："<<H->elem[pp]->add<<"\n";}elsecout<<"\n此人不存在，查找不成功!\n";benGetTime();}voidSave(){FILE*fp;if((fp=fopen("c:\test.txt","w"))==NULL){printf("\nERRORopeningcustometfile");}fclose(fp);}intmain(intargc,char*argv[]){intc,flag=1;HashTable*H;H=(HashTable*)malloc(LEN);for(inti=0;i<HASHSIZE;i++)H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;Recorda[MAXSIZE];while(1){cout<<"\n┏━━━━━━━━━━━━━┓";cout<<"\n┃歡迎使用電話號碼查找系統┃";cout<<"\n┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓";cout<<"\n┃★★★★★★★哈希表的設計與實現★★★★★★★┃";cout<<"\n┃【1】.添加用戶信息┃";cout<<"\n┃【2】.讀取所有用戶信息┃";cout<<"\n┃【3】.以姓名建立哈希表(再哈希法解決沖突)┃";cout<<"\n┃【4】.以電話號碼建立哈希表(再哈希法解決沖突)┃";cout<<"\n┃【5】.查找并顯示給定用戶名的記錄┃";cout<<"\n┃【6】.查找并顯示給定電話號碼的記錄┃";cout<<"\n┃【7】.清屏┃";cout<<"\n┃【8】.保存┃";cout<<"\n┃【9】.退出程序┃";cout<<"\n┃溫馨提示：┃";cout<<"\n┃Ⅰ.進行5操作前請先輸出3┃";cout<<"\n┃Ⅱ.進行6操作前請先輸出4┃";cout<<"\n┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛";cout<<"