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

1、WORD格式計(jì)算機(jī)科學(xué)與技術(shù)系哈希表的設(shè)計(jì)與實(shí)現(xiàn)工程報(bào)告專業(yè)資料整理WORD格式專業(yè)名稱工程課程工程名稱計(jì)算機(jī)科學(xué)與技術(shù)數(shù)據(jù)構(gòu)造與算法哈希表的設(shè)計(jì)與實(shí)現(xiàn)專業(yè)資料整理WORD格式班級(jí)專業(yè)資料整理WORD格式工程人員錢海峰, X秀娟, 王傳敏,楊青,凌波專業(yè)資料整理WORD格式實(shí)驗(yàn)日期2021 .12.9專業(yè)資料整理WORD格式目錄一設(shè)計(jì)目的 ,3二問(wèn)題分析 ,3三設(shè)計(jì)環(huán)境 ,3四人員分配 ,3五詳細(xì)設(shè)計(jì)和編碼 ,4六實(shí)驗(yàn)分析 ,71 測(cè)試分析 ,72 性能分析 ,11附錄 ,12參考書目 ,17專業(yè)資料整理WORD格式2專業(yè)資料整理WORD格式一設(shè)計(jì)目的（ 1掌握散列構(gòu)造和散列函數(shù)的相關(guān)概念（

2、2掌握散列構(gòu)造的存儲(chǔ)構(gòu)造的相關(guān)概念（ 2掌握散列沖突的處理方法（ 3運(yùn)用散列解決沖突問(wèn)題。二問(wèn)題分析要完成如下要求：設(shè)計(jì)哈希表實(shí)現(xiàn)整數(shù)查詢系統(tǒng)。實(shí)現(xiàn)本工程需要解決以下問(wèn)題：（ 1如何設(shè)計(jì)一個(gè)哈希表。（ 2如何在哈希表中插入記錄。（ 3如何刪除哈希表中的記錄。（ 4如何查找并顯示記錄。（ 5如何解決沖突問(wèn)題。三設(shè)計(jì)環(huán)境 硬件：計(jì)算機(jī)每人一臺(tái)。軟件： Windows操作系統(tǒng)和Microsoft Visual VC+6.0編譯器。四人員分配負(fù)責(zé)人負(fù)責(zé)內(nèi)容錢海峰showHashTable() , menu()X秀娟insert()，search()王傳敏Sanlibiao.h , main.c ,工程

3、文檔楊青Hash() ， createHashTable()凌波dele() ,initHashTable()專業(yè)資料整理WORD格式3專業(yè)資料整理WORD格式五詳細(xì)設(shè)計(jì)和編碼1. 定義結(jié)點(diǎn)構(gòu)造類型在鏈地址法中， 每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)， 由 3 個(gè)域組成， 構(gòu)造如圖 9-1 所示。 其中， key 為關(guān)鍵字域，存放結(jié)點(diǎn)關(guān)鍵字； data 為數(shù)據(jù)域，存放結(jié)點(diǎn)數(shù)據(jù)信息； next 為鏈域，存放指向下一個(gè)同義詞結(jié)點(diǎn)的指針。Keydatanext圖 9-1鏈地址法結(jié)點(diǎn)構(gòu)造鏈地址數(shù)據(jù)構(gòu)造類型如下：#define MAX_LENGTH 50typedef struct nodeint data;str

4、uct node *next;ElemNode;typedef structElemNode *first;ElemHeader,HashTableMAX_LENGTH;#include <stdio.h>2. 對(duì)哈希函數(shù)的定義設(shè)計(jì)一個(gè)Hash函數(shù)，本設(shè)計(jì)中對(duì)散列函數(shù)選擇的是除留余數(shù)法，即對(duì)關(guān)鍵字進(jìn)展模運(yùn)算，將運(yùn)算結(jié)果所得的余數(shù)作為關(guān)鍵字或結(jié)點(diǎn)的存儲(chǔ)地址，即i=ht mod n,本設(shè)計(jì) n 由用戶自己輸入，然后將計(jì)算出來(lái)的結(jié)果返回。具體設(shè)計(jì)如下：int Hash(int ht)int i;i = ht%n;return i;3. 初始化散列鏈表初始化鏈地址散列算法只需要把散列表中所

5、有表頭結(jié)點(diǎn)的指針域置為NULL。初始化散列鏈表的算法如下：void initHashTable(HashTable ht,int n)int i;for(i =0;i<n;i+)hti.first= NULL; 4. 創(chuàng)立哈希表在整個(gè)設(shè)計(jì)中， 創(chuàng)立哈希表必須是第一步要做的，結(jié)點(diǎn)之前應(yīng)先輸入結(jié)點(diǎn)的個(gè)數(shù)，利用鏈地址法解決沖突。添加結(jié)點(diǎn)實(shí)際是調(diào)用了插入結(jié)點(diǎn)函數(shù)insert，需要利用哈希函數(shù)計(jì)算出專業(yè)資料整理WORD格式4專業(yè)資料整理WORD格式地址， 其次將結(jié)點(diǎn)插入以關(guān)鍵字為地址的鏈表后。建立結(jié)點(diǎn)應(yīng)包括動(dòng)態(tài)申請(qǐng)內(nèi)存空間，想地址中輸入信息，同時(shí)最后一個(gè)結(jié)點(diǎn)中的next 指針等于NULL。具體實(shí)現(xiàn)

6、如下：int createHashTable(HashTable ht)HashTable *p=ht;int adMAX_LENGTH=0;int i;printf("請(qǐng)輸入插入個(gè)數(shù)n:");scanf("%d",&n);printf("n請(qǐng)輸入插入 %d個(gè)整數(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;5. 散列鏈表插入結(jié)點(diǎn)算法將一個(gè)結(jié)點(diǎn)

7、插入到散列鏈表中，其算法分為以下幾步：（ 1 根據(jù)結(jié)點(diǎn)關(guān)鍵字計(jì)算散列地址；（ 2 根據(jù)散列地址找到表頭結(jié)點(diǎn)，并將結(jié)點(diǎn)插入到對(duì)應(yīng)的鏈表中。鏈地址法散列表的插入算法如下：void insert(HashTable ht,int ele)int i;ElemNode *p;i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNode);p->data = ele;p->next = hti.first;hti.first = p;6. 散列鏈表查找結(jié)點(diǎn)算法在散列鏈表中查找一個(gè)結(jié)點(diǎn)，其算法分為以下幾步：1根據(jù)待查找關(guān)鍵字計(jì)算散列地址；2在散列地址所指向的

8、單鏈表中順序查找待查找關(guān)鍵字；3如果找到待查關(guān)鍵字，那么返回指向該結(jié)點(diǎn)的指針；否那么返回NULL。散列鏈表中查找結(jié)點(diǎn)的算法如下：ElemNode* search(HashTable ht,int ele)int i;ElemNode *p;i = Hash(ele);專業(yè)資料整理WORD格式5專業(yè)資料整理WORD格式p=hti.first;while(p!=NULL && p->data != ele)p = p->next;if(p!=NULL)printf(" 數(shù)據(jù) %d的位置為 %dn",ele,i); return p;elseprint

9、f(" 哈希表中無(wú) %dn",ele); return p;7. 散列鏈表刪除結(jié)點(diǎn)算法在散列表中刪除一個(gè)結(jié)點(diǎn)，其算法分為兩步：（ 1 查找要?jiǎng)h除的結(jié)點(diǎn)；（ 2 如果找到那么刪除，否那么顯示提示信息。在散列表中刪除一個(gè)結(jié)點(diǎn)的算法如下：void dele(HashTable ht,int ele)/刪除指定數(shù)據(jù)int i;ElemNode *p,*q;i = Hash(ele);p=hti.first;if(p = NULL)printf("error occurred! ");if(p->data = ele)hti.first = p->ne

10、xt;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);專業(yè)資料整理WORD格式6專業(yè)資料整理WORD格式六實(shí)驗(yàn)分析1. 測(cè)試分析1建立哈希表專業(yè)資料整理WORD格式7專業(yè)資料整理WORD格式2插入一個(gè)結(jié)點(diǎn)并顯示：專業(yè)資料整理WORD格式8專業(yè)資料整理WORD格式3查找結(jié)點(diǎn)：在哈希表中沒(méi)有3 這個(gè)數(shù)，會(huì)輸出一行提示信

11、息。專業(yè)資料整理WORD格式9專業(yè)資料整理WORD格式4刪除一個(gè)結(jié)點(diǎn)并顯示：專業(yè)資料整理WORD格式10專業(yè)資料整理WORD格式2. 性能分析散列法本質(zhì)上是一種通過(guò)關(guān)鍵字直接計(jì)算存儲(chǔ)地址的方法。在理想情況下， 散列函數(shù)可以把結(jié)點(diǎn)均勻地分布在散列表中，不發(fā)生沖突，那么查找過(guò)程無(wú)需比較，其時(shí)間復(fù)雜度O1。但在實(shí)際使用過(guò)程中，為了將X圍廣泛的關(guān)鍵字映射到一組連續(xù)的存儲(chǔ)空間，往往會(huì)發(fā)生同義詞沖突，這時(shí)就需要進(jìn)展關(guān)鍵字比較。能夠把關(guān)鍵字盡可能均勻地分布到散列表中的函數(shù)是“好 的散列函數(shù)。 好的散列函數(shù)可以有效地降低沖突的的發(fā)生， 從而提高查找性能。 但好的散列函數(shù)和關(guān)鍵字的數(shù)字特征有關(guān)，因此不存在對(duì)任何

12、結(jié)點(diǎn)都好的散列函數(shù)。對(duì)于同一種散列函數(shù)，采用不同的沖突處理方法將產(chǎn)生不同的效果，例如線性探測(cè)法容易導(dǎo)致“二次聚集 ，而拉鏈法可以從根本上杜絕二次聚集，從而提高查找性能。不過(guò)也會(huì)“浪費(fèi)一局部散列表的空間。專業(yè)資料整理WORD格式11專業(yè)資料整理WORD格式附錄*程序源代碼 */ 頭文件 sanlibiao.h #include <stdio.h> #include <stdlib.h>#define MAX_LENGTH 50typedef struct nodeint data;struct node *next;ElemNode;typedef structElemN

13、ode *first;ElemHeader,HashTableMAX_LENGTH;int n;/存儲(chǔ)哈希表長(zhǎng)度void 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(HashTa

14、ble ht);/菜單/ 功能函數(shù)sanlibiao.c#include"sanlibiao.h"void 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;專業(yè)資料整理WORD格式12專業(yè)資料整理WORD格式i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNode);/p->key = ele;p->data

15、= ele;p->next = hti.first;hti.first = p;ElemNode* search(HashTable ht,int ele)/查找int 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;elseprintf("哈希表中無(wú) %dn",ele);return p;void de

16、le(HashTable ht,int ele)/刪除指定數(shù)據(jù)int i;ElemNode *p,*q;i = Hash(ele);p=hti.first;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;專業(yè)資料整理WORD格式13專業(yè)資料整理WORD格式if(q = NULL)printf(&quo

17、t;error occurred! ");elsep->next = q->next;free(q);int Hash(int ht)/哈希函數(shù)int i;i = ht%n;return i;int createHashTable(HashTable ht)/創(chuàng)立哈希表HashTable *p=ht;int adMAX_LENGTH=0;int i;printf("請(qǐng)輸入插入個(gè)數(shù)n:");scanf("%d",&n);printf("n請(qǐng)輸入插入 %d個(gè)整數(shù) :",n);for(i=0;i<n;i+

18、)scanf("%d",&adi);initHashTable(p,n);for(i=0;i<n;i+)insert(p,adi);return 1;void showHashTable(HashTable 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)專業(yè)資料整理WORD格式14專業(yè)資料整理WORD格式printf("%d "

19、,p->data);p = p->next;if(hti.first!=NULL)printf("n");void menu(HashTable ht)int p,h; /p菜單項(xiàng)選擇擇；do/system("cls");/清屏printf("n");printf("n");printf(" *歡迎來(lái)到哈希表系統(tǒng)! *n");printf("*學(xué)院 n");printf("計(jì)算機(jī)科學(xué)與技術(shù)n");printf("錢海峰 , X秀娟 ,

20、 王傳敏 ,楊青, 凌波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");專業(yè)資料整理WORD格式15專業(yè)資料整理WORD格式printf(" * (5)-輸出哈希表*n");printf(" * (0)-退出*n");printf(" * n");printf("n");printf("n請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入：");scanf("%d",&p);switch(p)case 1:createHashTable(ht);break;case2:printf("請(qǐng)輸入要查找的