数据结构实验散列表.doc

计算机科学与技术系哈希表的设计与实现项目报告专业名称计算机科学与技术项目课程数据结构与算法项目名称哈希表的设计与实现班级项目人员钱海峰,郑秀娟,王传敏,杨青,………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………71测试分析……………………………………………………72性能分析……………………………………………………11附录……………………………………………………………………12参考书目………………………………………………………………(1)掌握散列结构和散列函数的相关概念(2)掌握散列结构的存储结构的相关概念(2)掌握散列冲突的处理方法(3)运用散列解决冲突问题。:设计哈希表实现整数查询系统。实现本项目需要解决以下问题:(1)如何设计一个哈希表。(2)如何在哈希表中插入记录。(3)如何删除哈希表中的记录。(4)如何查找并显示记录。(5)如何解决冲突问题。⒈硬件:计算机每人一台。⒉软件:Windows操作系统和MicrosoftVisualVC++。(),menu()郑秀娟insert(),search(),,项目文档杨青Hash(),createHashTable()凌波dele(),initHashTable(),每个结点对应一个链表结点,由3个域组成,结构如图9-1所示。其中,key为关键字域,存放结点关键字;data为数据域,存放结点数据信息;next为链域,存放指向下一个同义词结点的指针。Keydatanext图9-1链地址法结点结构链地址数据结构类型如下:#defineMAX_LENGTH50typedefstructnode{ intdata; structnode*next;}ElemNode;typedefstruct{ ElemNode*first;}ElemHeader,HashTable[MAX_LENGTH];#include<>()函数,本设计中对散列函数选择的是除留余数法,即对关键字进行模运算,将运算结果所得的余数作为关键字(或结点)的存储地址,即i=htmodn,本设计n由用户自己输入,然后将计算出来的结果返回。具体设计如下:intHash(intht){ inti; i=ht%n; returni;}。初始化散列链表的算法如下:voidinitHashTable(HashTableht,intn){ inti; for(i=0;i<n;i++){ ht[i].first=NULL;}},创建哈希表必须是第一步要做的,结点之前应先输入结点的个数,利用链地址法解决冲突。添加结点实际是调用了插入结点函数insert(),需要利用哈希函数计算出地址,其次将结点插入以关键字为地址的链表后。建立结点应包括动态申请内存空间,想地址中输入信息,同时最后一个结点中的next指针等于NULL。具体实现如下:intcreateHashTable(HashTableht){ HashTable*p=ht; intad[MAX_LENGTH]={0}; inti; printf("请输入插入个数n:"); scanf("%d",&n); printf("\n请输入插入%d个整数:",n); for(i=0;i<n;i++) scanf("%d",&ad[i]); initHashTable(p,n); for(i=0;i<n;i++) insert(p,ad[i]); return1;,其算法分为以下几步:根据结点关键字计算散列地址;根据散列地址找到表头结点,并将结点插入到对应的链表中。链地址法散列表的插入算法如下:voidinsert(HashTableht,intele){ inti; ElemNode*p; i=Hash(ele); p=(ElemNode*)malloc(sizeof(ElemNode)); p->data=ele; p->next=ht[i].first; h