1、 工学系课程设计报告工学系课程设计报告 设设 计计 题题 目：目：数据哈希表应用数据哈希表应用 系系 别：别：工学系工学系 专专 业业 ( (方方 向向) )：网络工程班网络工程班 年年 级、级、 班：班：20122012 级计算机科学与技术级计算机科学与技术 学学 生生 姓姓 名：名： 学学 生生 学学 号：号： 指指 导导 教教 师：师： 2013 年 12 月 24 日 目录目录 二、需求分析：二、需求分析：1 三、算法思想：三、算法思想：1 四、概要设计：四、概要设计：2 五系统的设计与实现五系统的设计与实现 2 六、总结六、总结 .3 七、附件（代码、部分图表）七、附件（代码、部分图
2、表） .4 1 哈希表应用哈希表应用 一、问题描述一、问题描述 哈希表应用设计：设哈希表长为 13，用除留余数法构造一个哈希函数，以开放定址 法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表的查找、插入、删除、 显示和退出系统的算法。 二、需求分析：二、需求分析： 1、功能需求、功能需求 用户能够自定义输入数据，存入哈希表里； 用户能够对当前哈希表进行管理。操作内容包括：显示当前哈希表、查询某个 数据、插入某个数据、删除表中某个数据、退出该系统。 程序有良好的交互界面，有操作提示和出错提示，方便用户使用和进出入程序。 2、程序约束、程序约束 哈希表的散列方法为除留余数法，处理冲突的办法
3、为线性探测在散列。 使用 C/C+语言编写，程序模块化设计。程序可实现用户与计算机的交互过程。 在计算机显示提示信息后，可由用户键入运算命令以实现对应的功能，包含表的建立、 数据的查找、插入、删除、显示、退出等功能。 本程序旨在实现哈希函数的构造与处理存储冲突，因而指定哈希表存储的数据类型 为简单的整型数字，在实用性上还有所欠缺。但根据用户需求的变化，可以对程序的基 本数据类型进行改造， 以实现更为丰富的功能， 进而体现哈希表在查找数据时的优越性。 三、算法思想：三、算法思想： 在设定哈希表的抽象数据类型时，要有查找数据元素的操作。另外，插入操作和删 除操作也要用到查找数据元素操作，以查看该数
4、据元素是否存在，因此可以设计查找元 素操作包括插入和删除操作的查找。 因此，查找操作就有两种情况：一种情况是插入操作时寻找空闲单元的查找；另一 种情况是在查找和删除操作时寻找该元素是否在哈希表中已存在的查找。插入操作时寻 找空闲单元查找的特征是哈希表中不存在该对象，设计此时查找函数返回该空闲单元位 置的“正”值；查找和删除操作时寻找该元素是否在哈希表中已存在的特征是哈希表中 已存在该数据元素，设计此时查找函数返回该数据单元位置的“负”值。进而执行后续 操作。 为了区分哈希表中每一个表元素的当前状态，为每一个表元素设置一个“标志”定 为 tag。tag=0 表示该元素为空；tag=1 表示该元素
5、以存放有数据元素；tag=-1 表示该元 素中存放的数据元素已被删除。判断当 tag为 0 或-1 时都可以进行插入操作。 2 四、概要设计：四、概要设计： 哈希表抽象数据类型的定义： ADT HashTable 数据对象：数据对象：D=ai|aiElemSet, i=1,2,.n, n0 数据关系：数据关系：R1=|ai-1D, i=1,2,.n 基本操作：基本操作： Initiate( /计算哈希地址 void Collision(int /冲突,计算下一个地址 int Search(T key,int /哈希查找 int Insert(ElemType e);/元素插入 int Dele
6、te(ElemType e); /元素删除 void Display(); /显示哈希表 template int LHSearch:Insert(ElemType e) /插入元素 int s; if(count=size) 3 printf(“表满，不能插入!n“); return UNSUCCESS; else s=Hash(e.key); int f; f=Search(e.key,s); if(f) /表中已有和 e 的关键字相同的元素,不进行插入操作 printf(“该元素已存在，不能插入!n“); return UNSUCCESS; else HTs.key=e.key; printf(“插入成功!n“); count+; return SUCCESS;
