數(shù)據(jù)結(jié)構(gòu)實驗散列表

數(shù)據(jù)結(jié)構(gòu)實驗散列表數(shù)據(jù)結(jié)構(gòu)實驗散列表數(shù)據(jù)結(jié)構(gòu)實驗散列表數(shù)據(jù)結(jié)構(gòu)實驗散列表編制僅供參考審核批準生效日期地址：電話：傳真:郵編:計算機科學與技術(shù)系哈希表的設(shè)計與實現(xiàn)項目報告專業(yè)名稱計算機科學與技術(shù)項目課程數(shù)據(jù)結(jié)構(gòu)與算法項目名稱哈希表的設(shè)計與實現(xiàn)班級項目人員錢海峰,鄭秀娟,王傳敏,楊青,凌波實驗日期目錄一．設(shè)計目的…………3二．問題分析…………3三．設(shè)計環(huán)境…………3四．人員分配…………3五．詳細設(shè)計和編碼…………………4六．實驗分析…………71測試分析……………………72性能分析……………………11附錄……………………12參考書目………………17一．設(shè)計目的（1）掌握散列結(jié)構(gòu)和散列函數(shù)的相關(guān)概念（2）掌握散列結(jié)構(gòu)的存儲結(jié)構(gòu)的相關(guān)概念（2）掌握散列沖突的處理方法（3）運用散列解決沖突問題。二．問題分析要完成如下要求：設(shè)計哈希表實現(xiàn)整數(shù)查詢系統(tǒng)。實現(xiàn)本項目需要解決以下問題：（1）如何設(shè)計一個哈希表。（2）如何在哈希表中插入記錄。（3）如何刪除哈希表中的記錄。（4）如何查找并顯示記錄。（5）如何解決沖突問題。三．設(shè)計環(huán)境⒈硬件：計算機每人一臺。⒉軟件：Windows操作系統(tǒng)和MicrosoftVisualVC++編譯器。四．人員分配負責人負責內(nèi)容錢海峰showHashTable(),menu()鄭秀娟insert()，search()王傳敏,,項目文檔楊青Hash()，createHashTable()凌波dele(),initHashTable()五．詳細設(shè)計和編碼1.定義結(jié)點結(jié)構(gòu)類型在鏈地址法中，每個結(jié)點對應(yīng)一個鏈表結(jié)點，由3個域組成，結(jié)構(gòu)如圖9-1所示。其中，key為關(guān)鍵字域，存放結(jié)點關(guān)鍵字；data為數(shù)據(jù)域，存放結(jié)點數(shù)據(jù)信息；next為鏈域，存放指向下一個同義詞結(jié)點的指針。Keydatanext圖9-1鏈地址法結(jié)點結(jié)構(gòu)鏈地址數(shù)據(jù)結(jié)構(gòu)類型如下：#defineMAX_LENGTH50typedefstructnode{ intdata; structnode*next;}ElemNode;typedefstruct{ ElemNode*first;}ElemHeader,HashTable[MAX_LENGTH];#include<>2.對哈希函數(shù)的定義設(shè)計一個Hash（）函數(shù)，本設(shè)計中對散列函數(shù)選擇的是除留余數(shù)法，即對關(guān)鍵字進行模運算，將運算結(jié)果所得的余數(shù)作為關(guān)鍵字（或結(jié)點）的存儲地址，即i=htmodn,本設(shè)計n由用戶自己輸入，然后將計算出來的結(jié)果返回。具體設(shè)計如下：intHash(intht){ inti; i=ht%n; returni;}3.初始化散列鏈表初始化鏈地址散列算法只需要把散列表中所有表頭結(jié)點的指針域置為NULL。初始化散列鏈表的算法如下：voidinitHashTable(HashTableht,intn){ inti; for(i=0;i<n;i++){ ht[i].first=NULL;}}4.創(chuàng)建哈希表在整個設(shè)計中，創(chuàng)建哈希表必須是第一步要做的，結(jié)點之前應(yīng)先輸入結(jié)點的個數(shù)，利用鏈地址法解決沖突。添加結(jié)點實際是調(diào)用了插入結(jié)點函數(shù)insert（），需要利用哈希函數(shù)計算出地址，其次將結(jié)點插入以關(guān)鍵字為地址的鏈表后。建立結(jié)點應(yīng)包括動態(tài)申請內(nèi)存空間，想地址中輸入信息，同時最后一個結(jié)點中的next指針等于NULL。具體實現(xiàn)如下：intcreateHashTable(HashTableht){ HashTable*p=ht; intad[MAX_LENGTH]={0}; inti; printf("請輸入插入個數(shù)n:"); scanf("%d",&n); printf("\n請輸入插入%d個整數(shù):",n); for(i=0;i<n;i++) scanf("%d",&ad[i]); initHashTable(p,n); for(i=0;i<n;i++) insert(p,ad[i]); return1;5.散列鏈表插入結(jié)點算法將一個結(jié)點插入到散列鏈表中，其算法分為以下幾步：根據(jù)結(jié)點關(guān)鍵字計算散列地址；根據(jù)散列地址找到表頭結(jié)點，并將結(jié)點插入到對應(yīng)的鏈表中。鏈地址法散列表的插入算法如下：voidinsert(HashTableht,intele){ inti; ElemNode*p; i=Hash(ele); p=(ElemNode*)malloc(sizeof(ElemNode)); p->data=ele; p->next=ht[i].first; ht[i].first=p;}6.散列鏈表查找結(jié)點算法在散列鏈表中查找一個結(jié)點，其算法分為以下幾步：根據(jù)待查找關(guān)鍵字計算散列地址；在散列地址所指向的單鏈表中順序查找待查找關(guān)鍵字；如果找到待查關(guān)鍵字，則返回指向該結(jié)點的指針；否則返回NULL。散列鏈表中查找結(jié)點的算法如下：ElemNode*search(HashTableht,intele){ inti; ElemNode*p; i=Hash(ele); p=ht[i].first; while(p!=NULL&&p->data!=ele){ p=p->next; } if(p!=NULL) { printf("數(shù)據(jù)%d的位置為%d\n",ele,i); returnp; } else { printf("哈希表中無%d\n",ele); returnp; }} 7.散列鏈表刪除結(jié)點算法在散列表中刪除一個結(jié)點，其算法分為兩步：查找要刪除的結(jié)點；如果找到則刪除，否則顯示提示信息。在散列表中刪除一個結(jié)點的算法如下：voiddele(HashTableht,intele){irst; if(p==NULL){ printf("erroroccurred!"); } if(p->data==ele){ ht[i].first=p->next; } else{ q=p->next; while(q!=NULL&&q->data!=ele){ p=q; q=q->next; } if(q==NULL){ printf("erroroccurred!"); } else{ p->next=q->next; free(q); } }}六．實驗分析1.測試分析（1）建立哈希表（2）插入一個結(jié)點并顯示：查找結(jié)點：在哈希表中沒有3這個數(shù)，會輸出一行提示信息。刪除一個結(jié)點并顯示：2.性能分析散列法本質(zhì)上是一種通過關(guān)鍵字直接計算存儲地址的方法。在理想情況下，散列函數(shù)可以把結(jié)點均勻地分布在散列表中，不發(fā)生沖突，則查找過程無需比較，其時間復雜度O（1）。但在實際使用過程中，為了將范圍廣泛的關(guān)鍵字映射到一組連續(xù)的存儲空間，往往會發(fā)生同義詞沖突，這時就需要進行關(guān)鍵字比較。 能夠把關(guān)鍵字盡可能均勻地分布到散列表中的函數(shù)是“好”的散列函數(shù)。好的散列函數(shù)可以有效地降低沖突的的發(fā)生，從而提高查找性能。但好的散列函數(shù)和關(guān)鍵字的數(shù)字特征有關(guān)，因此不存在對任何結(jié)點都好的散列函數(shù)。 對于同一種散列函數(shù)，采用不同的沖突處理方法將產(chǎn)生不同的效果，例如線性探測法容易導致“二次聚集”，而拉鏈法可以從根本上杜絕二次聚集，從而提高查找性能。不過也會“浪費”一部分散列表的空間。附錄****************************程序源代碼*********************************irst=NULL; }}voidinsert(HashTableht,intele){irst; ht[i].first=p;}ElemNode*search(HashTableht,intele){irst; while(p!=NULL&&p->data!=ele){ p=p->next; } if(p!=NULL) { printf("數(shù)據(jù)%d的位置為%d\n",ele,i); returnp; } else { printf("哈希表中無%d\n",ele); returnp; }} voiddele(HashTableht,intele){irst; if(p==NULL){ printf("erroroccurred!"); } if(p->data==ele){ ht[i].first=p->next; } else{ q=p->next; while(q!=NULL&&q->data!=ele){ p=q; q=q->next; } if(q==NULL){ printf("erroroccurred!"); } else{ p->next=q->next; free(q); } }}intHash(intht){irst; if(p!=NULL)printf("位置%d上的數(shù)據(jù)：",i); while(p!=NULL) { printf("%d",p->data); p=p->next; } if(ht[i].first!=NULL)printf("\n"); }}voidmenu(HashTableht){ intp,h;//p菜單選擇； do {// system("cls");//清屏 printf("★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n"); printf("☆★☆★\n"); printf("★☆**************歡迎來到哈希表系統(tǒng)!***************★☆\n"); printf("☆★合肥學院 ☆★\n"); printf("★☆計算機科學與技術(shù)★☆\n"); printf("☆★錢海峰,鄭秀娟,王傳敏,楊青,凌波☆★\n"); printf("☆★☆★\n"); printf("☆★※※※※※※※☆★\n"); printf("★☆※菜單※★☆\n"); printf("☆★※※※※※※※☆★\n"); printf("☆★☆★\n"); printf("★☆**************(1)---創(chuàng)建哈希表******************★☆\n"); printf("☆★**************(2)---查找******************★☆\n"); printf("★☆**************(3)---刪除******************★☆\n"); printf("☆★**************(4)---插入 ******************★☆\n"); printf("★☆**************(5)---輸出哈希表******************★☆\n"); printf("☆★**************(0)---退出******************☆★\n"); printf("★☆****************************************************★☆\n"); printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★\n"); printf("\n請在上述序號中選擇一個并輸入："); scanf(