1、.計算機科學與技術系哈希表的設計與實現(xiàn)項目報告專業(yè)名稱 計算機科學與技術 項目課程 數(shù)據(jù)結構與算法 項目名稱 哈希表的設計與實現(xiàn) 班 級項目人員 錢海峰,鄭秀娟,王傳敏,楊青,凌波 實驗日期 2015.12.9 目錄一設計目的3二問題分析3三設計環(huán)境3四人員分配3五詳細設計和編碼4六實驗分析71測試分析72性能分析11附錄12參考書目17一設計目的（1）掌握散列結構和散列函數(shù)的相關概念（2）掌握散列結構的存儲結構的相關概念（2）掌握散列沖突的處理方法（3）運用散列解決沖突問題。二問題分析要完成如下要求：設計哈希表實現(xiàn)整數(shù)查詢系統(tǒng)。實現(xiàn)本項目需要解決以下問題：（1）如何設計一個哈希表。（2）如何

2、在哈希表中插入記錄。（3）如何刪除哈希表中的記錄。（4）如何查找并顯示記錄。（5）如何解決沖突問題。三設計環(huán)境硬件：計算機每人一臺。軟件：Windows操作系統(tǒng)和Microsoft Visual VC+6.0編譯器。四人員分配負責人負責內(nèi)容錢海峰showHashTable(),menu()鄭秀娟insert()，search()王傳敏Sanlibiao.h, main.c , 項目文檔 青Hash()，createHashTable()凌 波dele() ,initHashTable()五詳細設計和編碼1.定義結點結構類型在鏈地址法中，每個結點對應一個鏈表結點，由3個域組成，結構如圖9-1所示

3、。其中，key為關鍵字域，存放結點關鍵字；data為數(shù)據(jù)域，存放結點數(shù)據(jù)信息；next為鏈域，存放指向下一個同義詞結點的指針。Keydatanext圖9-1 鏈地址法結點結構鏈地址數(shù)據(jù)結構類型如下：*define MAX_LENGTH 50typedef struct nodeint data;struct node *next;ElemNode;typedef structElemNode *first;ElemHeader,HashTableMAX_LENGTH;*include <stdio.h>2.對哈希函數(shù)的定義設計一個Hash（）函數(shù)，本設計中對散列函數(shù)選擇的是除留余數(shù)

4、法，即對關鍵字進行模運算，將運算結果所得的余數(shù)作為關鍵字（或結點）的存儲地址，即i=ht mod n,本設計n由用戶自己輸入，然后將計算出來的結果返回。具體設計如下：int Hash(int ht)int i;i = ht%n;return i;3.初始化散列鏈表初始化鏈地址散列算法只需要把散列表中所有表頭結點的指針域置為NULL。初始化散列鏈表的算法如下：void initHashTable(HashTable ht,int n)int i;for(i =0;i<n;i+)hti.first= NULL;4.創(chuàng)建哈希表在整個設計中，創(chuàng)建哈希表必須是第一步要做的，結點之前應先輸入結點的個

5、數(shù)，利用鏈地址法解決沖突。添加結點實際是調(diào)用了插入結點函數(shù)insert（），需要利用哈希函數(shù)計算出地址，其次將結點插入以關鍵字為地址的鏈表后。建立結點應包括動態(tài)申請內(nèi)存空間，想地址中輸入信息，同時最后一個結點中的next指針等于NULL。具體實現(xiàn)如下：int createHashTable(HashTable ht)HashTable *p=ht;int adMAX_LENGTH=0;int i;printf("請輸入插入個數(shù)n:");scanf("%d",&n);printf("n請輸入插入%d個整數(shù):",n);for(i=

6、0;i<n;i+)scanf("%d",&adi);initHashTable(p,n);for(i=0;i<n;i+)insert(p,adi);return 1;5.散列鏈表插入結點算法將一個結點插入到散列鏈表中，其算法分為以下幾步：（1） 根據(jù)結點關鍵字計算散列地址；（2） 根據(jù)散列地址找到表頭結點，并將結點插入到對應的鏈表中。鏈地址法散列表的插入算法如下：void insert(HashTable ht,int ele)int i;ElemNode *p;i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNo

7、de);p->data = ele;p->next = hti.first;hti.first = p;6.散列鏈表查找結點算法在散列鏈表中查找一個結點，其算法分為以下幾步：（1） 根據(jù)待查找關鍵字計算散列地址；（2） 在散列地址所指向的單鏈表中順序查找待查找關鍵字；（3） 如果找到待查關鍵字，則返回指向該結點的指針；否則返回NULL。散列鏈表中查找結點的算法如下：ElemNode* search(HashTable ht,int ele)int i;ElemNode *p;i = Hash(ele);p=hti.first;while(p!=NULL && p-&

8、gt;data != ele)p = p->next;if(p!=NULL)printf("數(shù)據(jù)%d的位置為%dn",ele,i);return p;else printf("哈希表中無%dn",ele);return p;7.散列鏈表刪除結點算法在散列表中刪除一個結點，其算法分為兩步：（1） 查找要刪除的結點；（2） 如果找到則刪除，否則顯示提示信息。在散列表中刪除一個結點的算法如下：void dele(HashTable ht,int ele)/刪除指定數(shù)據(jù)int i;ElemNode *p,*q;i = Hash(ele);p=hti.fir

9、st;if(p = NULL)printf("error occurred! ");if(p->data = ele)hti.first = p->next;else q= p->next; while(q!=NULL && q->data != ele)p=q;q = q->next;if(q = NULL)printf("error occurred! ");elsep->next = q->next;free(q);六實驗分析1.測試分析（1）建立哈希表（2）插入一個結點并顯示：（3） 查找

10、結點：在哈希表中沒有3這個數(shù)，會輸出一行提示信息。（4） 刪除一個結點并顯示：2.性能分析散列法本質(zhì)上是一種通過關鍵字直接計算存儲地址的方法。在理想情況下，散列函數(shù)可以把結點均勻地分布在散列表中，不發(fā)生沖突，則查找過程無需比較，其時間復雜度O（1）。但在實際使用過程中，為了將范圍廣泛的關鍵字映射到一組連續(xù)的存儲空間，往往會發(fā)生同義詞沖突，這時就需要進行關鍵字比較。能夠把關鍵字盡可能均勻地分布到散列表中的函數(shù)是“好”的散列函數(shù)。好的散列函數(shù)可以有效地降低沖突的的發(fā)生，從而提高查找性能。但好的散列函數(shù)和關鍵字的數(shù)字特征有關，因此不存在對任何結點都好的散列函數(shù)。對于同一種散列函數(shù)，采用不同的沖突處理

11、方法將產(chǎn)生不同的效果，例如線性探測法容易導致“二次聚集”，而拉鏈法可以從根本上杜絕二次聚集，從而提高查找性能。不過也會“浪費”一部分散列表的空間。附錄*程序源代碼*/頭文件sanlibiao.h*include <stdio.h>*include <stdlib.h>*define MAX_LENGTH 50typedef struct nodeint data;struct node *next;ElemNode;typedef structElemNode *first;ElemHeader,HashTableMAX_LENGTH;int n;/存儲哈希表長度voi

12、d initHashTable(HashTable ht,int n);void insert(HashTable ht,int ele);ElemNode* search(HashTable ht,int ele);void dele(HashTable ht,int ele);int Hash(int ht);int createHashTable(HashTable ht);void showHashTable(HashTable ht);void menu(HashTable ht);/菜單/功能函數(shù)sanlibiao.c*include"sanlibiao.h"v

13、oid initHashTable(HashTable ht,int n)/初始化int i;for(i =0;i<n;i+)hti.first= NULL;void insert(HashTable ht,int ele)/插入int i;ElemNode *p;i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNode);/p->key = ele;p->data = ele;p->next = hti.first;hti.first = p;ElemNode* search(HashTable ht,int ele)/查找in

14、t i;ElemNode *p;i = Hash(ele);p=hti.first;while(p!=NULL && p->data != ele)p = p->next;if(p!=NULL)printf("數(shù)據(jù)%d的位置為%dn",ele,i);return p;else printf("哈希表中無%dn",ele);return p;void dele(HashTable ht,int ele)/刪除指定數(shù)據(jù)int i;ElemNode *p,*q;i = Hash(ele);p=hti.first;if(p = NUL

15、L)printf("error occurred! ");if(p->data = ele)hti.first = p->next;else q= p->next; while(q!=NULL && q->data != ele)p=q;q = q->next;if(q = NULL)printf("error occurred! ");elsep->next = q->next;free(q);int Hash(int ht)/哈希函數(shù)int i;i = ht%n;return i;int cr

16、eateHashTable(HashTable ht)/創(chuàng)建哈希表HashTable *p=ht;int adMAX_LENGTH=0;int i;printf("請輸入插入個數(shù)n:");scanf("%d",&n);printf("n請輸入插入%d個整數(shù):",n);for(i=0;i<n;i+)scanf("%d",&adi);initHashTable(p,n);for(i=0;i<n;i+)insert(p,adi);return 1;void showHashTable(Hash

17、Table ht)/顯示哈希表int i;ElemNode *p;/i = Hash(ele);for(i=0;i<n;i+)p=hti.first;if(p!=NULL)printf("位置%d上的數(shù)據(jù)：",i);while(p!=NULL)printf("%d ",p->data);p = p->next;if(hti.first!=NULL)printf("n");void menu(HashTable ht)int p,h; /p 菜單選擇；do /system("cls");/清屏pri

18、ntf("n"); printf("n");printf("* 歡迎來到哈希表系統(tǒng)! *n"); printf(" 合肥學院n"); printf(" 計算機科學與技術 n");printf(" 錢海峰,鄭秀娟,王傳敏,楊青,凌波 n"); printf("n");printf("n");printf(" 菜 單 n");printf("n");printf("n");prin

19、tf("* (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("%d",&p); switch(p) case 1:createHashTable(ht);break; case 2:pr