數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說(shuō)明書-哈希表設(shè)計(jì)

PAGEPAGE1數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說(shuō)明書

學(xué)院、系：軟件學(xué)院專業(yè)軟件工程設(shè)計(jì)題目：哈希表設(shè)計(jì)

需求分析（1）針對(duì)某個(gè)集體中的人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建立和查表程序。（2）人名為漢語(yǔ)拼音形式，最長(zhǎng)不超過(guò)19個(gè)字符(如：莊雙雙zhuangshuangshuang)。（3）假設(shè)待填入哈希表的人名有30個(gè)，平均查找長(zhǎng)度的上限為2。哈希表用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)在散列法處理沖突。（4）如果隨機(jī)函數(shù)自行構(gòu)造，則應(yīng)首先調(diào)整好隨機(jī)函數(shù)，使其分布均勻。字符的取碼方法可直接利用C語(yǔ)言中的toascii函數(shù)，并可對(duì)過(guò)長(zhǎng)人名先進(jìn)行折疊處理。（5）查找成功時(shí)，顯示姓名及關(guān)鍵字，并計(jì)算和輸出查找成功的平均查找長(zhǎng)度?；静僮鞲鶕?jù)哈希函數(shù)可唯一確定一個(gè)記錄的地址，在理想情況下，記錄就可以按照這個(gè)存儲(chǔ)地址進(jìn)行存儲(chǔ)。因此哈希表的存儲(chǔ)結(jié)構(gòu)可以是鏈表和線性表，但一般情況下選擇線性表進(jìn)行存儲(chǔ)。本次課程設(shè)計(jì)用到的存儲(chǔ)結(jié)構(gòu)如下：typedefstruct{char*name;//名字的拼音intk;//名字拼音所對(duì)應(yīng)的關(guān)鍵字}NAME;//結(jié)構(gòu)體NEMA，存放名字列表typedefstruct//哈希表{char*name;//名字的拼音intk;//名字拼音所對(duì)應(yīng)的關(guān)鍵字intsi;//名字的查找長(zhǎng)度}HASH;//結(jié)構(gòu)體HASH，哈希表首先定義兩個(gè)結(jié)構(gòu)體數(shù)組：NAMENameList[HASH_LENGTH];//全局變量NAME，存儲(chǔ)原始姓名HASHHashList[HASH_LENGTH];//全局變量HASH，存儲(chǔ)哈希表中的姓名主要函數(shù)原型及功能：voidInitNameList()功能：主要完成初始化姓名列表，并且將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)作為哈希表的關(guān)鍵字。以便利用關(guān)鍵字和除留余數(shù)法得到每個(gè)姓名的哈希地址。voidCreateHashList()功能：構(gòu)建一個(gè)哈希表并進(jìn)行初始化；利用各個(gè)姓名的關(guān)鍵字得到哈希地址，將各個(gè)姓名按哈希地址進(jìn)行存儲(chǔ)，如果發(fā)生沖突，則利用偽隨機(jī)探測(cè)再序列解決沖突，最終將姓名全部存放在哈希表中。voidFindList()功能：對(duì)用戶輸入的姓名進(jìn)行查找；查找結(jié)果分兩種情況：（1）查找成功，則輸出姓名、關(guān)鍵字和查找長(zhǎng)度；（2）查找失敗，則返回相應(yīng)的失敗信息。查找時(shí)關(guān)鍵字的求法和處理沖突的方法與函數(shù)InitNameList()、CreateHashList()中的相關(guān)算法一致。voidShowHash()功能：完成度已經(jīng)建立好的哈希表進(jìn)行輸出顯示，并輸出平均查找長(zhǎng)度。voidmain()功能：完成對(duì)個(gè)函數(shù)的調(diào)用和與用戶的交互。函數(shù)voidInitNameList()的實(shí)現(xiàn)（以班級(jí)30人的人名作為初始值）：voidInitNameList()//姓名（結(jié)構(gòu)體數(shù)組）初始化{char*f;intr,s0,i;NameList[0].name="fanxu";NameList[1].name="jiangyong";NameList[2].name="guyuze";NameList[3].name="liuzhenhai";NameList[4].name="chenang";NameList[5].name="caoyandong";NameList[6].name="yangchenchen";NameList[7].name="shenjin";NameList[8].name="puping";NameList[9].name="luhaibo";NameList[10].name="renchao";NameList[11].name="wangshichuang";NameList[12].name="guoqihui";NameList[13].name="chengkang";NameList[14].name="wangyuesong";NameList[15].name="liangfangping";NameList[16].name="wangxufeng";NameList[17].name="hejie";NameList[18].name="yangyiming";NameList[19].name="wushengping";NameList[20].name="yangchaoqin";NameList[21].name="wulinfeng";NameList[22].name="xiehongwei";NameList[23].name="liushuo";NameList[24].name="yijiabin";NameList[25].name="xuhaiyang";NameList[26].name="yangwenjuan";NameList[27].name="chenjunyan"；NameList[28].name="wangjiaxin";NameList[29].name="chenwan";for(i=0;i<NAME_NO;i++) {s0=0;f=NameList[i].name;for(r=0;*(f+r)!='\0';r++)/*哈希地址方法：將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)作為哈希表的關(guān)鍵字*/s0=*(f+r)+s0;NameList[i].k=s0; }}用除留余數(shù)法構(gòu)建哈希函數(shù)用偽隨機(jī)探測(cè)再散列法處理沖突構(gòu)建哈希函數(shù)voidCreateHashList()的實(shí)現(xiàn)：voidCreateHashList(){ inti;for(i=0;i<HASH_LENGTH;i++) {HashList[i].py="";HashList[i].k=0;HashList[i].si=0; }for(i=0;i<HASH_LENGTH;i++) {intsum=0;intadr=(NameList[i].k)%M;//哈希函數(shù)intd=adr;if(HashList[adr].si==0)//如果不沖突 {HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1; }else//沖突 {do {d=(d+NameList[i].k%10+1)%M;//偽隨機(jī)探測(cè)再散列法處理沖突sum=sum+1;//查找次數(shù)加1 }while(HashList[d].k!=0);HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1; } }}查找哈希表若查找成功，則輸出姓名、關(guān)鍵字和查找長(zhǎng)度；查找失敗，則返回相應(yīng)的失敗信息。查找函數(shù)voidFindList()的實(shí)現(xiàn)：voidFindList()//查找{ charname[20]={0};ints0=0,r,sum=1,adr,d;printf("請(qǐng)輸入姓名的拼音:");scanf("%s",name);for(r=0;r<20;r++)//求出姓名的拼音所對(duì)應(yīng)的整數(shù)(關(guān)鍵字)s0+=name[r];adr=s0%M;//使用哈希函數(shù)d=adr;if(HashList[adr].k==s0)//分3種情況進(jìn)行判斷printf("\n姓名:%s關(guān)鍵字:%d查找長(zhǎng)度為:1",HashList[d].py,s0);elseif(HashList[adr].k==0)printf("無(wú)此記錄!");else {intg=0;do {d=(d+s0%10+1)%M;//偽隨機(jī)探測(cè)再散列法處理沖突sum=sum+1;if(HashList[d].k==0) {printf("無(wú)此記錄!");g=1; }if(HashList[d].k==s0) {printf("\n姓名:%s關(guān)鍵字:%d查找長(zhǎng)度為:%d",HashList[d].py,s0,sum);g=1; } }while(g==0); }}顯示哈希表顯示哈希表的的格式：\n地址\t關(guān)鍵字\t\t搜索長(zhǎng)度\tH(key)\t姓名\n顯示哈希表的函數(shù)voidDisplay()的：voidDisplay()//顯示{ inti;floataverage=0;printf("\n地址\t關(guān)鍵字\t\t搜索長(zhǎng)度\tH(key)\t姓名\n");//顯示的格式for(i=0;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"); }for(i=0;i<HASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;printf("\n平均查找長(zhǎng)度：ASL(%d)=%f\n",NAME_NO,average);}主函數(shù)設(shè)計(jì)voidmain(){ charch1; InitNameList();CreateHashList(); do { printf("D.顯示哈希表\nF.查找\nQ.退出\n請(qǐng)選擇："); cin>>&ch1; switch(ch1) { case'D':Display();cout<<endl;break; case'F':FindList();cout<<endl;break; case'Q':exit(0); } cout<<"comeon!(y/n):"; cin>>&ch1; }while(ch1!='n');}3程序流程圖開始開始選擇操作S、F、Q顯示哈希表查找哈希表SFQ退出程序、繼續(xù)Y退出NYN結(jié)束4調(diào)試報(bào)告經(jīng)過(guò)對(duì)哈希表的研究后，即進(jìn)行程序的設(shè)計(jì)和編碼；將原程序編好后，經(jīng)過(guò)編譯，有如下幾個(gè)問(wèn)題：在聲明了結(jié)構(gòu)體NAME后，最開始結(jié)構(gòu)體內(nèi)的charname[20]用來(lái)存放姓名拼音，最長(zhǎng)為20位；經(jīng)分析，name表示所存姓名拼音的首地址，無(wú)需再申明具體的數(shù)組長(zhǎng)度來(lái)存放姓名拼音，這樣增加了系統(tǒng)的開銷，最后改成char*name，對(duì)存放姓名拼音時(shí)直接對(duì)name賦值，系統(tǒng)直接按照字符數(shù)組來(lái)存放姓名拼音，而存放長(zhǎng)度沒有固定。建立哈希表的函數(shù)：voidCreateHashList()中，如果遇到?jīng)_突后，在do{}while()；語(yǔ)句中，利用偽隨機(jī)探測(cè)再散列法處理沖突，沒執(zhí)行一次就要將記錄查找長(zhǎng)度的sum增加一次，在這個(gè)循環(huán)執(zhí)行完后，即找到一個(gè)不沖突的地址來(lái)存放姓名拼音，經(jīng)過(guò)自習(xí)分析，此時(shí)的查找長(zhǎng)度需要加1，即將原來(lái)的語(yǔ)句HashList[d].si=sum;改成HashList[d].si=sum+1;此時(shí)的HashList[d].si才是正確的查找長(zhǎng)度。main函數(shù)中的do{}while()語(yǔ)句中，最開始while()語(yǔ)句是：while(a!='N'||a!='n')經(jīng)過(guò)分析，在用戶需要退出時(shí)，不論輸入a=N還是a=n，都將繼續(xù)循環(huán)；經(jīng)過(guò)自習(xí)思考，最終將while()語(yǔ)句改成：while(a=='Y'||a=='y')，這樣就實(shí)現(xiàn)了用戶的選擇。5程序代碼#include<stdio.h>#include<time.h>//time用到的頭文件#include<stdlib.h>//隨機(jī)數(shù)用到的頭文件#include<ctype.h>//toascii()用到的頭文件#include<string.h>//查找姓名時(shí)比較用的頭文件#defineHASH_LEN50//哈希表的長(zhǎng)度#defineP47//小于哈希表長(zhǎng)度的P#defineNAME_LEN30//姓名表的長(zhǎng)度typedefstruct//姓名表{char*py;//名字的拼音intm;//拼音所對(duì)應(yīng)的}NAME;NAMENameTable[HASH_LEN];//全局定義姓名表typedefstruct//哈希表{char*py;//名字的拼音intm;//拼音所對(duì)應(yīng)的ASCII總和intsi;//查找長(zhǎng)度}HASH;HASHHashTable[HASH_LEN];//全局定義哈希表intd[30],i,j;//全局定義隨機(jī)數(shù),循環(huán)用的i、jvoidInitNameTable()//姓名表的初始化{NameTable[0].py="louyuhong";NameTable[1].py="shenyinghong";NameTable[2].py="wangqi";NameTable[3].py="zhuxiaotong";NameTable[4].py="zhataotao";NameTable[5].py="chenbinjie";NameTable[6].py="chenchaoqun";NameTable[7].py="chencheng";NameTable[8].py="chenjie";NameTable[9].py="chenweida";NameTable[10].py="shanjianfeng";NameTable[11].py="fangyixin";NameTable[12].py="houfeng";NameTable[13].py="hujiaming";NameTable[14].py="huangjiaju";NameTable[15].py="huanqingsong";NameTable[16].py="jianghe";NameTable[17].py="jinleicheng";NameTable[18].py="libiao";NameTable[19].py="liqi";NameTable[20].py="lirenhua";NameTable[21].py="liukai";NameTable[22].py="louhanglin";NameTable[23].py="luchaoming";NameTable[24].py="luqiuwei";NameTable[25].py="panhaijian";NameTable[26].py="shuxiang";NameTable[27].py="suxiaolei";NameTable[28].py="sunyubo";NameTable[29].py="wangwei";for(i=0;i<NAME_LEN;i++)//將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字{ints=0;char*p=NameTable[i].py;for(j=0;*(p+j)!='\0';j++)s+=toascii(*(p+j));NameTable[i].m=s;}}voidCreateHashTable()//建立哈希表{for(i=0;i<HASH_LEN;i++){HashTable[i].py="\0";HashTable[i].m=0;HashTable[i].si=0;}for(i=0;i<NAME_LEN;i++){intsum=1,j=0;intadr=(NameTable[i].m)%P;//除留余數(shù)法H(key)=keyMODp,p<=mif(HashTable[adr].si==0)//如果不沖突，將姓名表賦值給哈希表{HashTable[adr].m=NameTable[i].m;HashTable[adr].py=NameTable[i].py;HashTable[adr].si=1;}else//如果沖突{while(HashTable[adr].si!=0){adr=(adr+d[j++])%HASH_LEN;//偽隨機(jī)探測(cè)再散列法處理沖突sum=sum+1;//查找次數(shù)加1}HashTable[adr].m=NameTable[i].m;//將姓名表復(fù)制給哈希表對(duì)應(yīng)的位置上HashTable[adr].py=NameTable[i].py;HashTable[adr].si=sum;}}}voidDisplayNameTable()//顯示姓名表{printf("\n地址\t\t姓名\t\t關(guān)鍵字\n");for(i=0;i<NAME_LEN;i++)printf("%2d%18s\t\t%d\n",i,NameTable[i].py,NameTable[i].m);}voidDisplayHashTable()//顯示哈希表{floatasl=0.0;printf("\n\n地址\t\t姓名\t\t關(guān)鍵字\t搜索長(zhǎng)度\n");//顯示的格式for(i=0;i<HASH_LEN;i++){printf("%2d%18s\t\t%d\t\t%d\n",i,HashTable[i].py,HashTable[i].m,HashTable[i].si);asl+=HashTable[i].si;}asl/=NAME_LEN;//求得ASLprintf("\n\n平均查找長(zhǎng)度：ASL(%d)=%f\n",NAME_LEN,asl);}voidFindName()//查找{charname[20]={0};ints=0,sum=1,adr;printf("\n請(qǐng)輸入想要查找的姓名的拼音:");scanf("%s",name);for(j=0;j<20;j++)//求出姓名的拼音所對(duì)應(yīng)的ASCII作為關(guān)鍵字s+=toascii(name[j]);adr=s%P;//除留余數(shù)法j=0;if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name))//分3種情況進(jìn)行判斷，并輸出超找結(jié)果printf("\n姓名:%s關(guān)鍵字:%d查找長(zhǎng)度為:1\n",HashTable[adr].py,s);elseif(HashTable[adr].m==0)printf("沒有想要查找的人!\n");else{while(1){adr=(adr+d[j++])%HASH_LEN;//偽隨機(jī)探測(cè)再散列法處理沖突sum=sum+1;//查找次數(shù)加1if(HashTable[adr].m==0){printf("沒有想要查找的人!\n");break;}if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name)){printf("\n姓名:%s關(guān)鍵字:%d查找長(zhǎng)度為:%d\n",HashTable[adr].py,s,sum);break;}}}}intmain()//主函數(shù){chara;srand((int)time(0));for(i=0;i<30;i++)//用隨機(jī)函數(shù)求得偽隨機(jī)數(shù)列d[i]（在1到50之間）d[i]=1+(int)(HASH_LEN*rand()/(RAND_MAX+1.0));InitNameTable();CreateHashTable();puts("哈希表設(shè)計(jì)");//顯示菜單欄start:puts("\n*菜單欄*");puts("\t\t\t1.顯示姓名表");puts("\t\t\t2.顯示哈希表");puts("\t\t\t3.查找");puts("\t\t\t4.退出");puts("*