哈希表設(shè)計(jì)一．問題描述問題描述：針對某個(gè)集體中人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長度不超過R，并完成相應(yīng)的建表和查表程序?；疽螅杭僭O(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。二.需求分析（1）針對某個(gè)集體中的人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長度不超過R，完成相應(yīng)的建立和查表程序。（2）人名為漢語拼音形式，最長不超過19個(gè)字符(如：莊雙雙zhuangshuangshuang)。（3）假設(shè)待填入哈希表的人名有30個(gè)，平均查找長度的上限為2。哈希表用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測在散列法處理沖突。（4）在輸入人名過程中能自動識別非法輸入，并給與非法輸入的反饋信息要求重新輸入。（5）查找成功時(shí)，顯示姓名及關(guān)鍵字，并計(jì)算和輸出查找成功的平均查找長度三．概要設(shè)計(jì)1.為實(shí)現(xiàn)上述算法，需要順序的抽象數(shù)據(jù)類型。ADTHash｛數(shù)據(jù)對象D：D是具有相同特征的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識的數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系：數(shù)據(jù)元素同屬于一個(gè)集合?；静僮鱌：Creat（&ST，n）；操作結(jié)果：構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)查找表ST。Destroy（&ST）初始條件：靜態(tài)查找表ST存在。操作結(jié)果：銷毀表ST.Search：（ST,key）初始條件：靜態(tài)查找表ST存在，key為和關(guān)鍵字類型相同的定值。操作結(jié)果：若ST中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該數(shù)據(jù)元素的值或在表中的位置，否則為“空”。Insert（&h,key）初始條件：哈希表h存在。操作結(jié)果：若表中沒有key，則在h中插入key。Hash（h,&k）初始條件：哈希表h存在。操作結(jié)果：通過除留余數(shù)法得到地址用k返回。2.本程序有三個(gè)模塊：（1）主程序模塊Main()｛初始化；｛接受命令；顯示結(jié)果； ｝｝（2）創(chuàng)建hash表的模塊（3）查找hash表的模塊（4）顯示哈希表的模塊四．詳細(xì)設(shè)計(jì)#include<stdio.h>#include<malloc.h>#include<string.h>//#include#defineHASH_LEN50//哈希表的長度#defineM47#defineNAME_NO30//人名的個(gè)數(shù)typedefstructNAME{char*py;//名字的拼音intk;//拼音所對應(yīng)的整數(shù)}NAME;NAMENameList[HASH_LEN];typedefstructhterm//哈希表{char*py;//名字的拼音intk;//拼音所對應(yīng)的整數(shù)intsi;//查找長度}HASH;HASHHashList[HASH_LEN];/*-----------------------姓名（結(jié)構(gòu)體數(shù)組）初始化---------------------------------*/voidInitNameList(){NameList[0].py="baojianbo";for(intr=0;r<20;r++)//求出姓名的拼音所對應(yīng)的整數(shù)(關(guān)鍵字)s0+=name[r];intsum=1;intadr=s0%M;//使用哈希函數(shù)intd=adr;if(HashList[adr].k==s0)//分3種情況進(jìn)行判斷printf("\n姓名:%s關(guān)鍵字:%d查找長度為:1",HashList[d].py,s0);elseif(HashList[adr].k==0)printf("無該記錄!");else{intg=0;do{d=(d+s0%10+1)%M;//偽散列sum=sum+1;if(HashList[d].k==0){printf("無記錄!");g=1;}if(HashList[d].k==s0){printf("\n姓名:%s關(guān)鍵字:%d查找長度為:%d",HashList[d].py,s0,sum);g=1;}}while(g==0);}}/*--------------------------------顯示哈希表----------------------------*/voidDisplay(){printf("\n\n地址\t關(guān)鍵字\t\t搜索長度\tH(key)\t\t拼音\n");//顯示的格式for(inti=0;i<15;i++){printf("%d",i);printf("\t%d",HashList[i].k);printf("\t\t%d",HashList[i].si);printf("\t\t%d",(HashList[i].k)%M);printf("\t%s",HashList[i].py);printf("\n");}//printf("按任意鍵繼續(xù)顯示...\n");//由于數(shù)據(jù)比較多，所以分屏顯示（以便在Win9x／DOS下能看到所有的數(shù)據(jù)）//getch();for(i=15;i<30;i++){printf("%d",i);printf("\t%d",HashList[i].k);printf("\t\t%d",HashList[i].si);printf("\t\t%d",(HashList[i].k)%M);printf("\t%s",HashList[i].py);printf("\n");}//printf("按任意鍵繼續(xù)顯示...\n");//getch();for(i=30;i<40;i++){printf("%d",i);printf("\t%d",HashList[i].k);printf("\t\t%d",HashList[i].si);printf("\t\t%d",(HashList[i].k)%M);printf("\t%s",HashList[i].py);printf("\n");}//printf("按任意鍵繼續(xù)顯示...\n");//getch();for(i=40;i<50;i++){printf("%d",i);printf("\t%d",HashList[i].k);printf("\t\t%d",HashList[i].si);printf("\t\t%d",(HashList[i].k)%M);printf("\t%s",HashList[i].py);printf("\n");}floataverage=0;for(i=0;i<HASH_LEN;i++)average+=HashList[i].si;average/=NAME_NO;printf("\n\n平均查找長度：ASL(%d)=%f\n\n",NAME_NO,average);}/*--------------------------------主函數(shù)----------------------------*/voidmain(){/*::SetConsoleTitle("哈希表操作");//WindowsAPI函數(shù),設(shè)置控制臺窗口的標(biāo)題HANDLEhCon=::GetStdHandle(STD_OUTPUT_HANDLE);//獲得標(biāo)準(zhǔn)輸出設(shè)備的句柄::SetConsoleTextAttribute(hCon,10|0);//設(shè)置文本顏色*/printf("\n------------------------哈希表的建立和查找----------------------");InitNameList();CreateHashList();while(1){printf("\n\n");printf("1.顯示哈希表\n");printf("2.查找\n");printf("3.退出\n");err:charch1;scanf("%c",&ch1);if(ch1=='1')Display();elseif(ch1=='2')