数据结构实验散列表

《数据结构实验散列表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机科学与技术系哈希表的设计与实现项目报告专业名称计算机科学与技术项目课程数据结构与算法项目名称哈希表的设计与实现班级项目人员钱海峰,郑秀娟,王传敏,杨青,凌波实验日期2015.12.916目录一．设计目的…………………………………………………………3二．问题分析…………………………………………………………3三．设计环境…………………………………………………………3四．人员分配…………………………………………………………3五．详细设计和编码…………………………………………………4六．实验分析…………………………………………………

2、………71测试分析……………………………………………………72性能分析……………………………………………………11附录……………………………………………………………………12参考书目………………………………………………………………1716一．设计目的（1）掌握散列结构和散列函数的相关概念（2）掌握散列结构的存储结构的相关概念（2）掌握散列冲突的处理方法（3）运用散列解决冲突问题。二．问题分析要完成如下要求：设计哈希表实现整数查询系统。实现本项目需要解决以下问题：（1）如何设计一个哈希表。（2）如何在哈希表中插入记录。（3）如何删除

3、哈希表中的记录。（4）如何查找并显示记录。（5）如何解决冲突问题。三．设计环境⒈硬件：计算机每人一台。⒉软件：Windows操作系统和MicrosoftVisualVC++6.0编译器。四．人员分配负责人负责内容钱海峰showHashTable(),menu()郑秀娟insert()，search()王传敏Sanlibiao.h,main.c,项目文档杨青Hash()，createHashTable()凌波dele(),initHashTable()16五．详细设计和编码1.定义结点结构类型在链地址法中，每个结点对应一个链表结点，

4、由3个域组成，结构如图9-1所示。其中，key为关键字域，存放结点关键字；data为数据域，存放结点数据信息；next为链域，存放指向下一个同义词结点的指针。Keydatanext图9-1链地址法结点结构链地址数据结构类型如下：#defineMAX_LENGTH50typedefstructnode{intdata;structnode*next;}ElemNode;typedefstruct{ElemNode*first;}ElemHeader,HashTable[MAX_LENGTH];#include2.对

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

6、{ht[i].first=NULL;}}4.创建哈希表在整个设计中，创建哈希表必须是第一步要做的，结点之前应先输入结点的个数，利用链地址法解决冲突。添加结点实际是调用了插入结点函数insert16（），需要利用哈希函数计算出地址，其次将结点插入以关键字为地址的链表后。建立结点应包括动态申请内存空间，想地址中输入信息，同时最后一个结点中的next指针等于NULL。具体实现如下：intcreateHashTable(HashTableht){HashTable*p=ht;intad[MAX_LENGTH]={0};inti;print

7、f("请输入插入个数n:");scanf("%d",&n);printf("请输入插入%d个整数:",n);for(i=0;i

8、ht,intele){inti;ElemNode*p;i=Hash(ele);p=(ElemNode*)malloc(sizeof(ElemNode));p->data=ele;p->next=ht[i].first;ht[i].first=p;}