2022年数据结构实验散列表推荐 .pdf

《2022年数据结构实验散列表推荐 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验散列表推荐 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机科学与技术系哈希表的设计与实现项目报告专业名称计算机科学与技术项目课程数据结构与算法项目名称哈希表的设计与实现班级项目人员钱海峰 , 郑秀娟 , 王传敏 , 杨青 , 凌波实验日期 2015.12.9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 2 目录一设计目的 ,3 二问题分析 ,3 三设计环境 ,3四人员分配 ,3五详细设计和编码 ,4 六实验分析 ,7 1 测试分析 ,7 2 性能分析 ,11 附录,12参考

2、书目 ,17名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 3 一设计目的（1）掌握散列结构和散列函数的相关概念（2）掌握散列结构的存储结构的相关概念（2）掌握散列冲突的处理方法（3）运用散列解决冲突问题。二问题分析要完成如下要求：设计哈希表实现整数查询系统。实现本项目需要解决以下问题：（1）如何设计一个哈希表。（2）如何在哈希表中插入记录。（3）如何删除哈希表中的记录。（4）如何查找并显示记录。（5）如何解决冲突问题。三设计

3、环境 硬件：计算机每人一台。 软件： Windows操作系统和Microsoft Visual VC+6.0编译器。四人员分配负责人负责内容钱海峰showHashTable() , menu() 郑秀娟insert()，search() 王传敏Sanlibiao.h , main.c , 项目文档杨青Hash() ，createHashTable() 凌波dele() ,initHashTable() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - -

4、- - - - - - 4 五详细设计和编码1. 定义结点结构类型在链地址法中， 每个结点对应一个链表结点，由 3 个域组成， 结构如图 9-1 所示。 其中，key为关键字域，存放结点关键字；data 为数据域，存放结点数据信息；next 为链域，存放指向下一个同义词结点的指针。Key data next 图 9-1 链地址法结点结构链地址数据结构类型如下：#define MAX_LENGTH 50 typedef struct node int data; struct node *next; ElemNode; typedef struct ElemNode *first; ElemHe

5、ader,HashTableMAX_LENGTH;#include 2. 对哈希函数的定义设计一个Hash（）函数，本设计中对散列函数选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或结点）的存储地址，即i=ht mod n,本设计 n 由用户自己输入，然后将计算出来的结果返回。具体设计如下：int Hash(int ht) int i; i = ht%n; return i; 3. 初始化散列链表初始化链地址散列算法只需要把散列表中所有表头结点的指针域置为NULL 。初始化散列链表的算法如下：void initHashTable(HashTable ht,int n

6、) int i; for(i =0;in;i+) hti.first= NULL; 4. 创建哈希表在整个设计中， 创建哈希表必须是第一步要做的，结点之前应先输入结点的个数，利用链地址法解决冲突。添加结点实际是调用了插入结点函数insert（） ，需要利用哈希函数计算出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 5 地址， 其次将结点插入以关键字为地址的链表后。建立结点应包括动态申请内存空间，想地址中输入信息，同时最后一个

7、结点中的next 指针等于NULL 。具体实现如下：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;in;i+) scanf(%d,&adi); initHashTable(p,n); for(i=0;idata = ele; p-next = hti.first; hti.first = p; 6. 散列链表查找结点算法在散列链表中查找一个结点，其算法分

8、为以下几步：（1）根据待查找关键字计算散列地址；（2）在散列地址所指向的单链表中顺序查找待查找关键字；（3）如果找到待查关键字，则返回指向该结点的指针；否则返回NULL 。散列链表中查找结点的算法如下：ElemNode* search(HashTable ht,int ele) int i; ElemNode *p; i = Hash(ele); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - 6 p=hti.first; w

9、hile(p!=NULL & p-data != ele) p = p-next; if(p!=NULL) printf(数据 %d的位置为 %dn,ele,i); return p; else printf(哈希表中无 %dn,ele); return p; 7. 散列链表删除结点算法在散列表中删除一个结点，其算法分为两步：（1）查找要删除的结点；（2）如果找到则删除，否则显示提示信息。在散列表中删除一个结点的算法如下：void dele(HashTable ht,int ele)/删除指定数据int i; ElemNode *p,*q; i = Hash(ele); p=hti.first

10、; 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! ); else p-next = q-next; free(q); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17

11、 页 - - - - - - - - - 7 六实验分析1. 测试分析（1）建立哈希表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 8 （2）插入一个结点并显示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 9 （3）查找结点：在哈希表中没有3 这个数，会

12、输出一行提示信息。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - 10 （4）删除一个结点并显示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - 11 2. 性能分析散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下， 散列函数可以把结点均匀地

13、分布在散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O （1） 。但在实际使用过程中，为了将范围广泛的关键字映射到一组连续的存储空间，往往会发生同义词冲突，这时就需要进行关键字比较。能够把关键字尽可能均匀地分布到散列表中的函数是“好” 的散列函数。 好的散列函数可以有效地降低冲突的的发生，从而提高查找性能。但好的散列函数和关键字的数字特征有关，因此不存在对任何结点都好的散列函数。对于同一种散列函数，采用不同的冲突处理方法将产生不同的效果，例如线性探测法容易导致“二次聚集” ，而拉链法可以从根本上杜绝二次聚集，从而提高查找性能。不过也会“浪费”一部分散列表的空间。名师资料总结 - - -

14、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - 12 附录*程序源代码 * / 头文件 sanlibiao.h #include #include #define MAX_LENGTH 50 typedef struct node int data; struct node *next; ElemNode; typedef struct ElemNode *first; ElemHeader,HashTableMAX_LENGTH; int n;/

15、存储哈希表长度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(HashTable ht);/菜单/ 功能函数 sanlibiao.c #includesanl

16、ibiao.h void initHashTable(HashTable ht,int n)/初始化int i; for(i =0;ikey = ele; p-data = 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);

17、return p; else printf(哈希表中无 %dn,ele); return p; 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-next; else q= p-next; while(q!=NULL & q-data != ele) p=q; q = q-next; 名师资料总结 - - -精品资料欢迎下载 -

18、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 14 if(q = NULL) printf(error occurred! ); else p-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(请

19、输入插入个数n:); scanf(%d,&n); printf(n请输入插入 %d个整数 :,n); for(i=0;in;i+) scanf(%d,&adi); initHashTable(p,n); for(i=0;in;i+) insert(p,adi); return 1; void showHashTable(HashTable ht)/显示哈希表 int i; ElemNode *p; /i = Hash(ele); for(i=0;idata); p = p-next; if(hti.first!=NULL)printf(n); void menu(HashTable ht) i

20、nt p,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

21、); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 16 printf( * (5)-输出哈希表 *n); printf( * (0)-退出 *n); printf( * n); printf(n); printf(n请在上述序号中选择一个并输入： ); scanf(%d,&p); switch(p) case 1:createHashTable(ht);break; case 2:printf(请输入要查找的数：n);s

22、canf(%d,&h);search(ht,h);break; case 3:printf(请输入要删除的数：n);scanf(%d,&h);dele(ht,h);printf(n);break; case 4:printf(请输入要插入的数：n);scanf(%d,&h);insert(ht,h);printf(n);break; case 5:showHashTable(ht);printf(n);break; case 0: break; /退出default:printf(输入错误 ! 请重新输入 !n);break; /system(pause);/系统暂停，提示按任意键继续。 。

23、。while(p!=0); /for do / 主函数 mian.c #include sanlibiao.h int main() HashTable ht; menu(ht);/进入菜单循环return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 17 参考书目王昆仑，李红， 数据结构与算法 ，中国铁道出版社，2007 年 6 月第一版。谭浩强，C语言程序设计 ，北京：清华大学出版社，2005 年 7 月第三版。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -