数据结构实验散列表

1、WORD格式计算机科学与技术系哈希表的设计与实现工程报告专业资料整理WORD格式专业名称工程课程工程名称计算机科学与技术数据构造与算法哈希表的设计与实现专业资料整理WORD格式班级专业资料整理WORD格式工程人员钱海峰, X秀娟, 王传敏,杨青,凌波专业资料整理WORD格式实验日期2021 .12.9专业资料整理WORD格式目录一设计目的 ,3二问题分析 ,3三设计环境 ,3四人员分配 ,3五详细设计和编码 ,4六实验分析 ,71 测试分析 ,72 性能分析 ,11附录 ,12参考书目 ,17专业资料整理WORD格式2专业资料整理WORD格式一设计目的（ 1掌握散列构造和散列函数的相关概念（

2、2掌握散列构造的存储构造的相关概念（ 2掌握散列冲突的处理方法（ 3运用散列解决冲突问题。二问题分析要完成如下要求：设计哈希表实现整数查询系统。实现本工程需要解决以下问题：（ 1如何设计一个哈希表。（ 2如何在哈希表中插入记录。（ 3如何删除哈希表中的记录。（ 4如何查找并显示记录。（ 5如何解决冲突问题。三设计环境 硬件：计算机每人一台。软件： Windows操作系统和Microsoft Visual VC+6.0编译器。四人员分配负责人负责内容钱海峰showHashTable() , menu()X秀娟insert()，search()王传敏Sanlibiao.h , main.c ,工程

3、文档杨青Hash() ， createHashTable()凌波dele() ,initHashTable()专业资料整理WORD格式3专业资料整理WORD格式五详细设计和编码1. 定义结点构造类型在链地址法中， 每个结点对应一个链表结点， 由 3 个域组成， 构造如图 9-1 所示。 其中， key 为关键字域，存放结点关键字； data 为数据域，存放结点数据信息； next 为链域，存放指向下一个同义词结点的指针。Keydatanext图 9-1链地址法结点构造链地址数据构造类型如下：#define MAX_LENGTH 50typedef struct nodeint data;str

4、uct node *next;ElemNode;typedef structElemNode *first;ElemHeader,HashTableMAX_LENGTH;#include <stdio.h>2. 对哈希函数的定义设计一个Hash函数，本设计中对散列函数选择的是除留余数法，即对关键字进展模运算，将运算结果所得的余数作为关键字或结点的存储地址，即i=ht mod n,本设计 n 由用户自己输入，然后将计算出来的结果返回。具体设计如下：int Hash(int ht)int i;i = ht%n;return i;3. 初始化散列链表初始化链地址散列算法只需要把散列表中所

5、有表头结点的指针域置为NULL。初始化散列链表的算法如下：void initHashTable(HashTable ht,int n)int i;for(i =0;i<n;i+)hti.first= NULL; 4. 创立哈希表在整个设计中， 创立哈希表必须是第一步要做的，结点之前应先输入结点的个数，利用链地址法解决冲突。添加结点实际是调用了插入结点函数insert，需要利用哈希函数计算出专业资料整理WORD格式4专业资料整理WORD格式地址， 其次将结点插入以关键字为地址的链表后。建立结点应包括动态申请内存空间，想地址中输入信息，同时最后一个结点中的next 指针等于NULL。具体实现

6、如下：int createHashTable(HashTable ht)HashTable *p=ht;int adMAX_LENGTH=0;int i;printf("请输入插入个数n:");scanf("%d",&n);printf("n请输入插入 %d个整数 :",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. 散列链表插入结点算法将一个结点

7、插入到散列链表中，其算法分为以下几步：（ 1 根据结点关键字计算散列地址；（ 2 根据散列地址找到表头结点，并将结点插入到对应的链表中。链地址法散列表的插入算法如下：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. 散列链表查找结点算法在散列链表中查找一个结点，其算法分为以下几步：1根据待查找关键字计算散列地址；2在散列地址所指向的

8、单链表中顺序查找待查找关键字；3如果找到待查关键字，那么返回指向该结点的指针；否那么返回NULL。散列链表中查找结点的算法如下：ElemNode* search(HashTable ht,int ele)int i;ElemNode *p;i = Hash(ele);专业资料整理WORD格式5专业资料整理WORD格式p=hti.first;while(p!=NULL && p->data != ele)p = p->next;if(p!=NULL)printf(" 数据 %d的位置为 %dn",ele,i); return p;elseprint

9、f(" 哈希表中无 %dn",ele); return p;7. 散列链表删除结点算法在散列表中删除一个结点，其算法分为两步：（ 1 查找要删除的结点；（ 2 如果找到那么删除，否那么显示提示信息。在散列表中删除一个结点的算法如下：void dele(HashTable ht,int ele)/删除指定数据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);专业资料整理WORD格式6专业资料整理WORD格式六实验分析1. 测试分析1建立哈希表专业资料整理WORD格式7专业资料整理WORD格式2插入一个结点并显示：专业资料整理WORD格式8专业资料整理WORD格式3查找结点：在哈希表中没有3 这个数，会输出一行提示信

11、息。专业资料整理WORD格式9专业资料整理WORD格式4删除一个结点并显示：专业资料整理WORD格式10专业资料整理WORD格式2. 性能分析散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下， 散列函数可以把结点均匀地分布在散列表中，不发生冲突，那么查找过程无需比较，其时间复杂度O1。但在实际使用过程中，为了将X围广泛的关键字映射到一组连续的存储空间，往往会发生同义词冲突，这时就需要进展关键字比较。能够把关键字尽可能均匀地分布到散列表中的函数是“好 的散列函数。 好的散列函数可以有效地降低冲突的的发生， 从而提高查找性能。 但好的散列函数和关键字的数字特征有关，因此不存在对任何

12、结点都好的散列函数。对于同一种散列函数，采用不同的冲突处理方法将产生不同的效果，例如线性探测法容易导致“二次聚集 ，而拉链法可以从根本上杜绝二次聚集，从而提高查找性能。不过也会“浪费一局部散列表的空间。专业资料整理WORD格式11专业资料整理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;/存储哈希表长度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);/菜单/ 功能函数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;专业资料整理WORD格式12专业资料整理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("数据 %d的位置为 %dn",ele,i);return p;elseprintf("哈希表中无 %dn",ele);return p;void de

16、le(HashTable ht,int ele)/删除指定数据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;专业资料整理WORD格式13专业资料整理WORD格式if(q = NULL)printf(&quo

17、t;error occurred! ");elsep->next = q->next;free(q);int Hash(int ht)/哈希函数int i;i = ht%n;return i;int createHashTable(HashTable ht)/创立哈希表HashTable *p=ht;int adMAX_LENGTH=0;int i;printf("请输入插入个数n:");scanf("%d",&n);printf("n请输入插入 %d个整数 :",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上的数据： ",i);while(p!=NULL)专业资料整理WORD格式14专业资料整理WORD格式printf("%d "

19、,p->data);p = p->next;if(hti.first!=NULL)printf("n");void menu(HashTable ht)int p,h; /p菜单项选择择；do/system("cls");/清屏printf("n");printf("n");printf(" *欢迎来到哈希表系统! *n");printf("*学院 n");printf("计算机科学与技术n");printf("钱海峰 , X秀娟 ,

20、 王传敏 ,杨青, 凌波n");printf("n");printf("n");printf(" 菜 单n");printf("n");printf("n");printf(" * (1)-创立哈希表*n");printf(" * (2)-查找*n");printf(" * (3)-删除*n");printf(" * (4)-插入* n");专业资料整理WORD格式15专业资料整理WORD格式printf(" * (5)-输出哈希表*n");printf(" * (0)-退出*n");printf(" * n");printf("n");printf("n请在上述序号中选择一个并输入：");scanf("%d",&p);switch(p)case 1:createHashTable(ht);break;case2:printf("请输入要查找的