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