数据结构实验散列表.doc

计算机科学与技术系哈希表的设计与实现项目报告 专业名称 计算机科学与技术 项目课程 数据结构与算法 项目名称 哈希表的设计与实现 班 级 项目人员 钱海峰,郑秀娟,王传敏,杨青,凌波 实验日期 2015.12.9 目录一设计目的3二问题分析3三设计环境3四人员分配3五详细设计和编码4六实验分析71测试分析72性能分析11附录12参考书目17一设计目的（1）掌握散列结构和散列函数的相关概念（2）掌握散列结构的存储结构的相关概念（2）掌握散列冲突的处理方法（3）运用散列解决冲突问题。二问题分析要完成如下要求：设计哈希表实现整数查询系统。实现本项目需要解决以下问题：（1）如何设计一个哈希表。（2）如何在哈希表中插入记录。（3）如何删除哈希表中的记录。（4）如何查找并显示记录。（5）如何解决冲突问题。三设计环境 硬件：计算机每人一台。 软件：Windows操作系统和Microsoft Visual VC+6.0编译器。四人员分配负责人负责内容钱海峰showHashTable() , menu()郑秀娟insert()，search()王传敏Sanlibiao.h , main.c , 项目文档杨 青Hash()，createHashTable()凌 波dele() , initHashTable()五详细设计和编码1.定义结点结构类型在链地址法中，每个结点对应一个链表结点，由3个域组成，结构如图9-1所示。其中，key为关键字域，存放结点关键字；data为数据域，存放结点数据信息；next为链域，存放指向下一个同义词结点的指针。Keydatanext图9-1 链地址法结点结构链地址数据结构类型如下：#define MAX_LENGTH 50typedef struct nodeint data;struct node *next;ElemNode;typedef structElemNode *first;ElemHeader,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)int i;for(i =0;in;i+)hti.first= NULL; 4.创建哈希表在整个设计中，创建哈希表必须是第一步要做的，结点之前应先输入结点的个数，利用链地址法解决冲突。添加结点实际是调用了插入结点函数insert（），需要利用哈希函数计算出地址，其次将结点插入以关键字为地址的链表后。建立结点应包括动态申请内存空间，想地址中输入信息，同时最后一个结点中的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.散列链表查找结点算法在散列链表中查找一个结点，其算法分为以下几步：（1） 根据待查找关键字计算散列地址；（2） 在散列地址所指向的单链表中顺序查找待查找关键字；（3） 如果找到待查关键字，则返回指向该结点的指针；否则返回NULL。散列链表中查找结点的算法如下：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;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;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! );elsep-next = q-next;free(q);六实验分析1.测试分析（1）建立哈希表（2）插入一个结点并显示：（3） 查找结点：在哈希表中没有3这个数，会输出一行提示信息。（4） 删除一个结点并显示：2.性能分析散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下，散列函数可以把结点均匀地分布在散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（1）。但在实际使用过程中，为了将范围广泛的关键字映射到一组连续的存储空间，往往会发生同义词冲突，这时就需要进行关键字比较。能够把关键字尽可能均匀地分布到散列表中的函数是“好”的散列函数。好的散列函数可以有效地降低冲突的的发生，从而提高查找性能。但好的散列函数和关键字的数字特征有关，因此不存在对任何结点都好的散列函数。对于同一种散列函数，采用不同的冲突处理方法将产生不同的效果，例如线性探测法容易导致“二次聚集”，而拉链法可以从根本上杜绝二次聚集，从而提高查找性能。不过也会“浪费”一部分散列表的空间。附录*程序源代码*/头文件sanlibiao.h#include #include #define MAX_LENGTH 50typedef struct nodeint data;struct node *next;ElemNode;typedef structElemNode *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(HashTable ht);/菜单/功能函数 sanlibiao.c#includesanlibiao.hvoid 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);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;if(q = NULL)printf(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;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)int 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);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);scanf(%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; cas