數(shù)據(jù)結(jié)構(gòu)課程設計-散列法的研究

數(shù)據(jù)結(jié)構(gòu)課程設計說明書學院：信息科學與工程學院班級：計算機科學與技術(shù)完成人：姓名：學號：指導教師：山東科技大學2013年12月25日課程設計任務書一、課程設計題目：散列法的實驗研究二、課程設計應解決的主要問題：（1）數(shù)據(jù)元素的輸入和輸出（2）線性再散列法建立哈希表（3）二次探測再散列法建立哈希表（4）鏈地址法建立哈希表（5）線性再散列法進行數(shù)據(jù)查找（6）二次探測再散列法進行數(shù)據(jù)查找（7）鏈地址法進行數(shù)據(jù)查找（8）退出系統(tǒng)三、任務發(fā)出日期：2013-10-01課程設計完成日期：2013-12-20小組分工說明小組編號7題目：散列法的實驗研究小組分工情況：一人獨立完成所有工作。組長簽字：2013年12月31日指導教師對課程設計的評價成績：指導教師簽字：年月日1．需求分析說明-32．概要設計說明3．詳細設計說明4．調(diào)試分析-4-5-75．用戶使用說明6．課程設計總結(jié)7．測試結(jié)果-8-10-10-128．參考書目需求分析說明內(nèi)部排序教學軟件的總體功能要求：散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對于幾種典型的散列函數(shù)構(gòu)造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響?；竟δ苋缦拢海?）界面友好，易與操作。采用菜單方式進行選擇。（2）實現(xiàn)三種方法進行哈希表的構(gòu)造。包括線性再散列法、二次探測再散列法和鏈地址法。（3）根據(jù)三種構(gòu)造方法分別進行數(shù)據(jù)元素的查找，若查找成功，則同時輸出探查/沖突次數(shù)。以下是各功能模塊的功能描述：1．主函數(shù)模塊本模塊的主要功能是初始化圖形界面，調(diào)用各模塊，實現(xiàn)功能。2．構(gòu)造哈希表子模塊本模塊的主要功能是采用線性再散列法、二次探測再散列法、鏈地址法三種方法構(gòu)造哈希表。3．查找功能及輸出子模塊本模塊的主要功能是在采用線性再散列法、二次探測再散列法、鏈地址法三種方法構(gòu)造哈希表后，采用相應的方法對鍵入的數(shù)據(jù)進行查找，并計算探查/沖突次數(shù)。4．輸入子模塊本模塊的主要功能是從鍵盤中輸入數(shù)據(jù)元素用于構(gòu)造哈希表。5.輸出子模塊本模塊的主要功能是將數(shù)據(jù)元素顯示在屏幕上。概要設計說明模塊調(diào)用圖：各種構(gòu)造方法的哈希表數(shù)據(jù)類型定義為：typedefstruct{intkey;/*關(guān)鍵字*/intsi;/*插入成功時的次數(shù)*/}HashTable1;/*哈希表線性探測再散列數(shù)據(jù)類型定義*/typedefstructHa{intelem;/*數(shù)據(jù)項*/structHa*next2;/*指向下一個結(jié)點的指針*/}HashTable2;/*哈希表鏈地址法數(shù)據(jù)類型定義*/typedefstruct{intelem[HashSize];/*表中儲存數(shù)據(jù)元素的數(shù)組*/intcount;/*表中儲存數(shù)據(jù)元素的個數(shù)*//*哈希表的尺寸*/intsize;}HashTable3;/*哈希表二次探測再散列法數(shù)據(jù)類型定義*/#defineHashSize53/*哈希表最大長度*/intnum;/*輸入數(shù)據(jù)的個數(shù)*/voidGetIn(int*a)/*從鍵盤輸入數(shù)據(jù)*/voidGetOut(int*a)/*在屏幕上輸出數(shù)據(jù)*/voidCreateHashTable1(HashTable1*H,int*a,intnum)/*線性探測在散列哈希表*/voidSearchHash1(HashTable1*h,intdata)/*線性探測在散列法查找*/voidCreateHashTable2(HashTable2*H,int*a,intnum)/*哈希表鏈地址*/intSearchHash2(HashTable2*h,intdata,intnum)/*鏈地址法查找*/voidCreateHash3(HashTable3*h,int*a,intnum)/*二次探索表*/intCollision(intp,intc)/*二次探測再散列法解決沖突*/voidSearchHash3(HashTable3*h,intdata)/*哈希表二次探索再散列查找*/intsystem(constchar*string)/*清屏*/詳細設計說明1．主函數(shù)模塊首先構(gòu)造三種類型的哈希表，并對哈希表進行初始化。進入循環(huán)后在屏幕上輸出相應的操作指示，然后通過輸入0-8調(diào)用所選擇的函數(shù)進行相應操作。主函數(shù)代碼如下：intmain(){intdata,i;HashTable1hash1[HashSize];HashTable2hash2[HashSize];HashTable3*ha;/*定義三種類型的哈希表*/ha=(HashTable3*)malloc(sizeof(HashTable3));for(i=0;i<HashSize;i++)ha->elem[i]=0;ha->count=0;ha->size=HashSize;inta[HashSize];a[0]=0;/*哈希表的初始化*/while(1){printf("\nprintf("\n┏━━━━━━━━━━━━━━━┓");┃");┃歡迎使用本系統(tǒng)printf("\n┏〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒┓");printf("\n┃★★★★★★散列法的實驗研究★★★★★┃");printf("\n┃【1】.添加數(shù)據(jù)信息┃");printf("\n┃printf("\n┃printf("\n┃【2】.數(shù)據(jù)的輸出┃");【3】.建立哈希表(線性再散列)┃");┃");【4】.建立哈希表(二次探測再散列)printf("\n┃printf("\n┃printf("\n┃printf("\n┃printf("\n┃【5】.建立哈希表(鏈地址法)【6】.線性再散列法查找【7】.二次探測再散列法查找【8】.鏈地址法查找┃");┃");┃");┃");┃");【0】.退出程序printf("\n┗〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒┛");printf("\n");printf("\n");printf("請輸入一個任務選項>>>");intx;scanf("%d",&x);switch(x){case1:GetIn(a);break;/*調(diào)用輸入函數(shù)，從鍵盤鍵入需要添加的數(shù)據(jù)*//*若已有數(shù)據(jù)輸入，則調(diào)用數(shù)據(jù)輸出函數(shù)*/case2:if(a[0]==0)printf("您還沒有輸入任何數(shù)據(jù)!\n");elseGetOut(a);break;case3:/*調(diào)用函數(shù)用線性再散列法構(gòu)造哈希表*/if(a[0]==0)printf("您還沒有輸入任何數(shù)據(jù)!\n");elseCreateHashTable1(hash1,a,num);break;case4:/*調(diào)用函數(shù)用二次探測再散列法構(gòu)造哈希表*/if(a[0]==0)printf("您還沒有輸入任何數(shù)據(jù)!\n");elseCreateHash3(ha,a,num);break;case5:/*調(diào)用函數(shù)用鏈地址法構(gòu)造哈希表*/if(a[0]==0)printf("您還沒有輸入任何數(shù)據(jù)!\n");elseCreateHashTable2(hash2,a,num);break;case6:/*調(diào)用函數(shù)用線性再散列法查找*/if(a[0]==0)printf("您還沒有輸入任何數(shù)據(jù)!\n");else{printf("請輸入你查找的數(shù)據(jù)");scanf("%d",&data);SearchHash1(hash1,data);}break;case7:if(a[0]==0)/*調(diào)用函數(shù)用二次探測再散列法查找*/printf("您還沒有輸入任何數(shù)據(jù)!\n");else{printf("請輸入你查找的數(shù)據(jù)");scanf("%d",&data);SearchHash3(ha,data);}break;case8:/*調(diào)用函數(shù)用鏈地址法查找*/if(a[0]==0)printf("您還沒有輸入任何數(shù)據(jù)!\n");else{printf("請輸入你查找的數(shù)據(jù)");scanf("%d",&data);SearchHash2(hash2,data,num);}break;case0:/*退出系統(tǒng)*/exit(-1);break;}getchar();printf("\n請按回車鍵返回\n");getchar();system("cls");/*清屏*/}}2．查找功能及輸出子模塊根據(jù)題目要求，可將這個系統(tǒng)分為以下幾個模塊：1.線性再散列法建立哈希表：構(gòu)造哈希函數(shù)h(x)=h(key)%HashSize，當沖突發(fā)生時，地址增量di依次取1,2,···,HashSize-1自然數(shù)列,即di=1,2,···,HashSize-1。代碼如下：voidCreateHashTable1(HashTable1*H,int*a,intnum)//哈希表線性探測再散列{inti,d,cnt;for(i=0;i<HashSize;i++)/*給新哈希表初始化數(shù)據(jù)*/{H[i].key=0;H[i].si=0;}for(i=0;i<num;i++){cnt=1;d=a[i]%HashSize;/*構(gòu)造哈希函數(shù)*/if(H[d].key==0)/*無沖突時，直接插入數(shù)據(jù)*/{H[d].key=a[i];H[d].si=cnt;}Else/*有沖突時，進行沖突處理后再插入*/{do{d=(d+1)%HashSize;cnt++;}while(H[d].key!=0);H[d].key=a[i];H[d].si=cnt;}}printf("\n線性再探索哈希表已建成!");}2.二次探測再散列法建立哈希表：構(gòu)造哈希函數(shù)h(x)=h(key)%HashSize，當沖突發(fā)生時，地址增量di依次取,,···,數(shù)列,即di=,,···,。代碼如下：typedefstruct{intelem[HashSize];/*表中儲存數(shù)據(jù)元素的數(shù)組*/intcount;/*表中儲存數(shù)據(jù)元素的個數(shù)*//*哈希表的尺寸*/intsize;}HashTable3;intCollision(intp,intc)/*二次探測再散列法解決沖突*/{inti,q;i=c/2+1;while(i<HashSize){if(c%2==0)/*增量為正數(shù)時*/{c++;q=(p+i*i)%HashSize;if(q>=0)returnq;elsei=c/2+1;}else{/*增量為負數(shù)時*/q=(p-i*i)%HashSize;c++;if(q>=0)returnq;elsei=c/2+1;}}return(-1);}voidCreateHash3(HashTable3*h,int*a,intnum)//二次探測再散列構(gòu)造哈希表{inti,p=-1,c,pp;for(i=0;i<num;i++){c=0;p=a[i]%HashSize;/*哈希函數(shù)*/pp=p;while(h->elem[pp]!=0)/*發(fā)生沖突*/{pp=Collision(p,c);c++;if(pp<0)/*沖突無法處理*/{printf("第%d個記錄無法解決沖突\n",i+1);continue;}}h->elem[pp]=a[i];h->count++;printf("第%d個記錄沖突次數(shù)為%d\n",i+1,c);}printf("\n建表完成\n此哈希表容量為%d,當前表內(nèi)存儲的記錄個數(shù)%d.\n",num,h->count);}3.鏈地址法建立哈希表：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。在鏈表中插入位置可以為表頭或表尾，也可以在中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。（本程序采用在表尾插入）代碼如下：typedefstructHa{intelem;/*數(shù)據(jù)項*/structHa*next2;/*指向下一個結(jié)點的指針*/}HashTable2;voidCreateHashTable2(HashTable2*H,int*a,intnum)//哈希表鏈地址構(gòu)造法{intkey,i;HashTable2*q,*qq;q=NULL;for(i=0;i<HashSize;i++)/*對哈希表進行初始化*/{H[i].elem=0;H[i].next2=NULL;}for(i=0;i<num;i++){key=a[i]%HashSize;if(H[key].elem==0)H[key].elem=a[i];else{if(q!=NULL)/*若該位置已有數(shù)據(jù)*/{qq=q;q=q+1;q->elem=a[i];/*添加到已存在的結(jié)點后面*/q->next2=qq->next2;qq->next2=q;}else{q=(HashTable2*)malloc(sizeof(HashTable2));if(!q){printf("申請內(nèi)存失敗!請重新運行程序\n");exit(1);}q->elem=a[i];/*添加到首結(jié)點后面*/q->next2=H[key].next2;H[key].next2=q;}}}printf("鏈表探索哈希表已建成!\n");}4.線性再散列法進行查找：根據(jù)線性再散列法的構(gòu)造方式進行相應查找。代碼如下：voidSearchHash1(HashTable1*h,intdata){intd,i;d=data%HashSize;/*哈希函數(shù)*/i=d;if(h[d].key==data)/*一次查找成功*/printf("數(shù)字%d的探查次數(shù)為%d\n",h[d].key,h[d].si);else{while(i<HashSize&&h[d].key!=data){d=(d+1)%HashSize;i+=1;}if(i<HashSize)printf("數(shù)字%d的探查次數(shù)為%d.\n",h[d].key,h[d].si);elseprintf("沒有查找到你所輸入的數(shù)\n");}}5.二次探測再散列法進行查找：根據(jù)二次探測再散列法的構(gòu)造方式進行相應查找。代碼如下：voidSearchHash3(HashTable3*h,intdata)//哈希表二次探索再散列查找{intc=0,p,pp;p=data%HashSize;pp=p;while((h->elem[pp])!=data&&pp!=-1){pp=Collision(p,c);c++;}if((h->elem[pp]!=0)&&(h->elem[pp])==data)printf("\n查找成功!\n查找沖突次數(shù)為%d.",c);elseprintf("\n沒有查到此數(shù)!\n");}6.鏈地址法進行查找：根據(jù)鏈地址法的構(gòu)造方式進行相應查找。代碼如下：intSearchHash2(HashTable2*h,intdata,intnum){intd,cnt=1;HashTable2*q;d=data%HashSize;q=&h[d];/*哈希函數(shù)*/if(q->elem==0){/*該位置上沒有數(shù)據(jù)元素*/printf("沒有找到你要查找的那個數(shù)\n");return0;}while(q!=NULL){if(q->elem==data){printf("數(shù)字%d的查找次數(shù)為%d\n",data,cnt);return0;}elseif(q->next2!=NULL){q=q->next2;cnt++;}else{printf("沒有找到你要查找的那個數(shù)\n");return0;}}return0;}7.輸入函數(shù)：從鍵盤中鍵入數(shù)據(jù)。代碼如下：voidGetIn(int*a){//輸入數(shù)據(jù)函數(shù)printf("輸入添加的個數(shù)");scanf("%d",&num);inti;for(i=0;i<num;i++)scanf("%d",&a[i]);printf("數(shù)據(jù)已經(jīng)輸入完畢!\n");}8.輸出函數(shù)：在屏幕上輸出數(shù)據(jù)。代碼如下：voidGetOut(int*a){inti;printf("你所輸入的數(shù)據(jù)");for(i=0;i<num-1;i++)printf("%d,",a[i]);printf("%d.",a[num-1]);printf("\n輸出已完畢!");}調(diào)試分析我遇到的問題：●鏈地址法查找時，原設計在有沖突時表尾插入，寫出的程序卻是在表頭進行插入。在加入了一個判斷語句和移動指針位置的語句后問題得到解決。●圖形界面下輸入數(shù)據(jù)●在程序顯示結(jié)果后無法返