课程设计报告--数据哈希表应用

1、. 兰州商学院陇桥学院 工学系课程设计报告设 计 题 目：数据哈希表应用 系 别：工学系 专 业 (方 向)：网络工程班 年 级、 班：2012级计算机科学与技术 学 生 姓 名：李妮 学 生 学 号：20120661116 指 导 教 师：王万玉 2013年 12 月 24 日目录二、需求分析：1三、算法思想：1四、概要设计：2五系统的设计与实现2六、总结3七、附件（代码、部分图表）4;哈希表应用一、问题描述哈希表应用设计：设哈希表长为13，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表的查找、插入、删除、显示和退出系统的算法。二、需求分析：

2、1、功能需求用户能够自定义输入数据，存入哈希表里；用户能够对当前哈希表进行管理。操作内容包括：显示当前哈希表、查询某个数据、插入某个数据、删除表中某个数据、退出该系统。程序有良好的交互界面，有操作提示和出错提示，方便用户使用和进出入程序。2、程序约束哈希表的散列方法为除留余数法，处理冲突的办法为线性探测在散列。使用C/C+语言编写，程序模块化设计。程序可实现用户与计算机的交互过程。在计算机显示提示信息后，可由用户键入运算命令以实现对应的功能，包含表的建立、数据的查找、插入、删除、显示、退出等功能。本程序旨在实现哈希函数的构造与处理存储冲突，因而指定哈希表存储的数据类型为简单的整型数字，在实用性

3、上还有所欠缺。但根据用户需求的变化，可以对程序的基本数据类型进行改造，以实现更为丰富的功能，进而体现哈希表在查找数据时的优越性。三、算法思想：在设定哈希表的抽象数据类型时，要有查找数据元素的操作。另外，插入操作和删除操作也要用到查找数据元素操作，以查看该数据元素是否存在，因此可以设计查找元素操作包括插入和删除操作的查找。因此，查找操作就有两种情况：一种情况是插入操作时寻找空闲单元的查找；另一种情况是在查找和删除操作时寻找该元素是否在哈希表中已存在的查找。插入操作时寻找空闲单元查找的特征是哈希表中不存在该对象，设计此时查找函数返回该空闲单元位置的“正”值；查找和删除操作时寻找该元素是否在哈希表中

4、已存在的特征是哈希表中已存在该数据元素，设计此时查找函数返回该数据单元位置的“负”值。进而执行后续操作。为了区分哈希表中每一个表元素的当前状态，为每一个表元素设置一个“标志”定为tag。tag=0表示该元素为空；tag=1表示该元素以存放有数据元素；tag=-1表示该元素中存放的数据元素已被删除。判断当tag为0或-1时都可以进行插入操作。四、概要设计：哈希表抽象数据类型的定义：ADT HashTable 数据对象：D=ai|aiElemSet, i=1,2,.n, n0 数据关系：R1=<ai-1,ai>|ai-1D, i=1,2,.n 基本操作：Initiate( &h

5、 ) 操作结果：构造一个空的哈希表h。SearchHash( h, x, p ) 初始条件：哈希表h已存在；p为除留余数法中除数，由用户指定。 操作结果：查找表中元素与指定数据x比较。元素已存在时返回其所在位置的负数下标、不存在时返回其位置的正数下标、遍历哈希表后未查找到时返回表长。Insert( &h, x, p ) 初始条件：哈希表h已存在。 操作结果：查找操作后插入元素x至哈希表。若元素已存在或哈希表已满时插入操作失败，返回值为0。Delete(&h, x, p ) 初始条件：哈希表h已存在。 操作结果：查找操作后从哈希表中删除元素x。若元素不在表中时删除操作失败，返回值

6、为0。Print( h ) 初始条件：哈希表h已存在。 操作结果：显示哈希表中元素及存储状态。五系统的设计与实现int Hash(T key); /计算哈希地址void Collision(int &s);/冲突,计算下一个地址int Search(T key,int &s);/哈希查找int Insert(ElemType<T> e);/元素插入int Delete(ElemType<T> e); /元素删除void Display(); /显示哈希表template <class T>int LHSearch<T>:Inser

7、t(ElemType<T> e)/插入元素int s;if(count=size) 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; 1、

8、本次课程设计采用的是除留余数法构造了哈希表，除数的选择很重要。如果选得不好，会造成很多冲突，浪费时间和空间代价。例如，本次设计的哈希表最大长度为11，余数如果取得较小，会使得一部分元素容易形成堆积，平均搜索长度变大，而且取余的时间也会更长。2、本次设计处理冲突采用了线性探测再散列的办法。相比起同时闭散列方法的二次探测再散列来说，优点在于功能简单易操作性；缺点是当数据量逐渐加大时，前者的平均查找长度会逐渐比后者大。六、总结哈希表作为一种存储与查找的优化方式，通过把关键码值映射到数表中一个位置来访问数据，以加快查找速度。在日常生活中，哈希函数的应用也是随处可见。当今十分流行的P2P数据传输技术中一

9、系列的压缩、打包以及积分标准都应用到了hash算法设置。可见利用哈希函数用途之广。本次程序设计中利用“除留余数法”构造哈希函数，并用“开放定址法”中的“线性探测再散列”方式处理冲突，选取较为简单的整型数字作为存储数据。通过此次实验，我对哈希表抽象数据类型的定义以及构造方法有了初步的认识和了解，也为今后编写更复杂的应用程序提供了新的思想方法与实现基础。七、附件（代码、部分图表）#include<stdio.h>#define SUCCESS 1;#define UNSUCCESS 0;#define NULLKEY -1;#define TableLength 13;#define

10、p 13; / H(key)=key % p typedef int T;template <class T>struct ElemTypeT key;/关键字;template <class T>class LHSearchprivate:ElemType<T> *HT; /开放定址哈希表int count; /当前数据元素个数int size; /哈希表长度public:LHSearch(); / LHSearch(); / void InitHashTable(int n);/ int Hash(T key); /计算哈希地址void Collisio

11、n(int &s);/冲突,计算下一个地址int Search(T key,int &s);/哈希查找int Insert(ElemType<T> e);/元素插入int Delete(ElemType<T> e); /元素删除void Display(); /显示哈希表;template <class T>LHSearch<T>:LHSearch()HT=NULL;size=0;count=0;template <class T>LHSearch<T>:LHSearch() delete HT;count

12、=0;template <class T>int LHSearch<T>:Hash(T key) /由哈希函数求哈希地址return key%p;template <class T>void LHSearch<T>:Collision(int &s)/开放定址法解决冲突s=s+;template <class T>int LHSearch<T>:Search(T key,int &s)/查找，找到返回/int s;s=Hash(key);while(HTs.key!=-1) && (key!

13、=HTs.key) Collision(s);if(HTs.key=key) return 1;else return 0;template <class T>int LHSearch<T>:Insert(ElemType<T> e)/插入元素int s;if(count=size) printf("表满，不能插入!n"); return UNSUCCESS;else s=Hash(e.key); int f; f=Search(e.key,s); if(f) /表中已有和e的关键字相同的元素,不进行插入操作 printf("该

14、元素已存在，不能插入!n"); return UNSUCCESS; else HTs.key=e.key; printf("插入成功!n"); count+; return SUCCESS; template <class T>int LHSearch<T>:Delete(ElemType<T> e)/删除元素int s;if(count=NULL) printf("表空，不能删除!n"); return UNSUCCESS;else s=Hash(e.key); int f; if(f) HTs.key=e

15、.key; printf("删除成功!n"); count-; return SUCCESS; /表中已有和e的关键字相同的元素,不进行插入操作 else printf("该元素不存在，不能删除!n"); return UNSUCCESS; template<class T>void LHSearch<T>:InitHashTable(int n)size=n;HT=new ElemType<T>size;for(int i=0;i<size;i+) /初始化，把哈希表置空 HTi.key=NULLKEY;tem

16、plate<class T>void LHSearch<T>:Display()for(int i=0;i<size;i+) printf("%dn",i); if(HTi.key!=-1) printf("%dn",HTi.key); else printf("t"); printf("n");void main()int m;T key;int s=0;ElemType<int> e;LHSearch<int> a;printf("输入相应代码，必

17、须先创建哈希表n");do printf ("t|=|tn"); printf ("t| |tn"); printf ("t| 哈希表应用 |tn"); printf ("t| |tn"); printf ("t|=|tn"); printf ("ntt【1】->建立!t【2】->插入!t【3】->删除!n");printf ("ntt【4】->查找!t【5】->显示!t【6】->退出!n"); printf

18、("请选择操作:"); scanf("%d",&m); switch(m) case 1:/创建查找表 printf("请输入表容量：n"); scanf("%d",&m); a.InitHashTable(m); printf("依次输入表元素，-1结束:n"); for(scanf("%d",&e.key) ;e.key!=-1;scanf("%d",&e.key) a.Insert(e); break; case 2: /插入元素 printf("输入要插入的元素:n"); scanf("%d",&e.key); a.Insert(e); break; case 3: /删除元素 printf("输入要删除的元素:n"); scanf("%d&q