数据结构实验散列表

《数据结构实验散列表》由会员分享，可在线阅读，更多相关《数据结构实验散列表（17页珍藏版）》请在装配图网上搜索。

1、资料范本本资料为word版本，可以直接编辑和打印，感谢您的下载数据结构实验散列表地点：时间：说明：本资料适用于约定双方经过谈判，协商而共同承认，共同遵守的责任与 义务，仅供参考，文档可直接下载或修改，不需要的部分可直接删除，使用时 请详细阅读内容计算机科学与技术系哈希表的设计与实现项目报告专业名称计算机科学与技术项目课程数据结构与算法项目名称 哈希表的设计与实现班 级项目人员 钱海峰，郑秀娟,王传敏，杨青，凌波实验日期2015.12.9目录一. 设计目的3二. 问题分析3三. 设计环境3四. 人员分配3五. 详细设计和编码4六. 实验分析71测试分析72性能分析11附录12参考书目17一. 设

2、计目的(1) 掌握散列结构和散列函数的相关概念(2) 掌握散列结构的存储结构的相关概念(2)掌握散列冲突的处理方法(3) 运用散列解决冲突问题。二. 问题分析要完成如下要求：设计哈希表实现整数查询系统。实现本项目需要解决以下问题：(1) 如何设计一个哈希表。(2) 如何在哈希表中插入记录。(3) 如何删除哈希表中的记录。(4) 如何查找并显示记录。(5) 如何解决冲突问题。三. 设计环境1. 硬件：计算机每人一台。2. 软件：Windows 操作系统和 Microsoft Visual VC+6.0 编译器。四. 人员分配五. 详细设计和编码1. 定义结点结构类型在链地址法中，每个结点对应一个

3、链表结点，由3个域组成，结构如图9- 1所示。其中，key为关键字域，存放结点关键字；data为数据域，存放结点 数据信息；next为链域，存放指向下一个同义词结点的指针。图9-1链地址法结点结构链地址数据结构类型如下：#define MAX_LENGTH 50typedef struct node(int data;struct node *next;ElemNode;typedef struct(ElemNode *first;ElemHeader,HashTableMAX_LENGTH;#include 2. 对哈希函数的定义设计一个Hash()函数，本设计中对散列函数选择的是除留余数法

4、，即对 关键字进行模运算，将运算结果所得的余数作为关键字(或结点)的存储地 址，即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. 创建哈希表在整个设计中，创建哈希表必须是第一步要做的，结点之前应先

5、输入结点 的个数，利用链地址法解决冲突。添加结点实际是调用了插入结点函数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);initH

6、ashTable(p,n);for(i=0;idata = ele;p-next = hti.first;hti.first = p;6. 散列链表查找结点算法在散列链表中查找一个结点，其算法分为以下几步：根据待查找关键字计算散列地址；在散列地址所指向的单链表中顺序查找待查找关键字；如果找到待查关键字，则返回指向该结点的指针；否则返回NULL。散列链表中查找结点的算法如下：ElemNode* search(HashTable ht,int ele)( int i;ElemNode *p;i = Hash(ele);p=hti.first;while(p!=NULL & p-data != el

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

8、);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);六.实验分析1. 测试分析(1) 建立哈希表(2) 插入一个结点并显示：查找结点：在哈希表中没有3这个数，会输出一行提示信息。删除一个结点并显示：2. 性能分析散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况 下，散列函数可以把结点均匀地分布在散列表中，

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

10、ibiao.h#include #include #define MAX_LENGTH 50typedef struct node(int data;struct node *next;ElemNode;typedef struct(ElemNode *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(

11、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(

12、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)(prin

13、tf(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);int Hash(int ht)(/哈希函数int i;i = ht%n;return i;int createHashTable(HashTable ht)/创建哈希表(HashTable *p=ht;int adMAX_LENG

14、TH=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

15、)int p, h; p菜单选择;dosystem(cls)；/清屏printfprintf (* 欢迎来到哈希表系统!*、/)；printf (printf (printf (n)；printf (n)；printf (n)；printf (n)；printf (n)；合肥学院、!);计算机科学与技术钱海峰，郑秀娟,王传敏，杨青，凌波淤菜单淤printf(* (1)创建哈希表 *、/)；printf(* (2)查找 *、/)；printf(* (3)删除 *、/)；printf(* (4)插入 *、/);printf(* (5)输出哈希表 *、/);printf(* (0)退出 *、/);U

16、linTI(MM* n);。土 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;case 0:break; /退出default:printf(输入错误!请重新输入！n);break;/system(pause);/系统暂停，提示按任意键继续。while(p!=0); /for do/主函数mian.c#include sanlibiao.h”int main()(HashTable ht;menu(ht);/进入菜单循环return 0;参考书目王昆仑，李红，数据结构与算法，中国铁道出版社，2007年6月第一 版。谭浩强，C语言程序设计，北京：清华大学出版社，2005年7月第三 版。