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

兰州商学院陇桥学院兰州商学院陇桥学院 工学系课程设计报告工学系课程设计报告 设设 计计 题题 目：目：数据哈希表应用数据哈希表应用 系系 别：别：工学系工学系 专专 业业 ( (方方 向向) )：网络工程班网络工程班 年年 级、级、 班：班：20122012 级计算机科学与技术级计算机科学与技术 学学 生生 姓姓 名：名：李妮李妮 学学 生生 学学 号：号：20120661116 指指 导导 教教 师：师：王万玉王万玉 2013 年 12 月 24 日 目录目录 二、需求分析：二、需求分析：.1 三、算法思想：三、算法思想：.1 四、概要设计：四、概要设计：.2 五系统的设计与实现五系统的设计与实现.2 六、总结六、总结.3 七、附件（代码、部分图表）七、附件（代码、部分图表）.4 0 哈希表应用哈希表应用 一、一、问题描述问题描述 哈希表应用设计：设哈希表长为 13，用除留余数法构造一个哈希函数，以开放定 址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表的查找、插入、删 除、显示和退出系统的算法。 二、需求分析：二、需求分析： 1、功能需求功能需求 用户能够自定义输入数据，存入哈希表里； 用户能够对当前哈希表进行管理。操作内容包括：显示当前哈希表、查询某 个数据、插入某个数据、删除表中某个数据、退出该系统。 程序有良好的交互界面，有操作提示和出错提示，方便用户使用和进出入程 序。 2、程序约束程序约束 哈希表的散列方法为除留余数法，处理冲突的办法为线性探测在散列。 使用 C/C+语言编写，程序模块化设计。程序可实现用户与计算机的交互过 程。在计算机显示提示信息后，可由用户键入运算命令以实现对应的功能，包含表的 建立、数据的查找、插入、删除、显示、退出等功能。 本程序旨在实现哈希函数的构造与处理存储冲突，因而指定哈希表存储的数据类 型为简单的整型数字，在实用性上还有所欠缺。但根据用户需求的变化，可以对程序 的基本数据类型进行改造，以实现更为丰富的功能，进而体现哈希表在查找数据时的 优越性。 三、算法思想：三、算法思想： 在设定哈希表的抽象数据类型时，要有查找数据元素的操作。另外，插入操作和 删除操作也要用到查找数据元素操作，以查看该数据元素是否存在，因此可以设计查 找元素操作包括插入和删除操作的查找。 因此，查找操作就有两种情况：一种情况是插入操作时寻找空闲单元的查找；另 一种情况是在查找和删除操作时寻找该元素是否在哈希表中已存在的查找。插入操作 时寻找空闲单元查找的特征是哈希表中不存在该对象，设计此时查找函数返回该空闲 单元位置的“正”值；查找和删除操作时寻找该元素是否在哈希表中已存在的特征是 哈希表中已存在该数据元素，设计此时查找函数返回该数据单元位置的“负”值。进 而执行后续操作。 为了区分哈希表中每一个表元素的当前状态，为每一个表元素设置一个“标志” 定为 tag。tag=0 表示该元素为空；tag=1 表示该元素以存放有数据元素；tag=-1 表示该 元素中存放的数据元素已被删除。判断当 tag 为 0 或-1 时都可以进行插入操作。 1 四、概要设计：四、概要设计： 哈希表抽象数据类型的定义： 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 Delete(ElemType e); /元素删除 void Display(); /显示哈希表 template int LHSearch:Insert(ElemType e) /插入元素 int s; if(count=size) 2 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、本次课程设计采用的是除留余数法构造了哈希表，除数的选择很重 要。如果选得不好，会造成很多冲突，浪费时间和空间代价。例如，本次 设计的哈希表最大长度为 11，余数如果取得较小，会使得一部分元素容易 形成堆积，平均搜索长度变大，而且取余的时间也会更长。 2、本次设计处理冲突采用了线性探测再散列的办法。相比起同时闭散 列方法的二次探测再散列来说，优点在于功能简单易操作性；缺点是当数 据量逐渐加大时，前者的平均查找长度会逐渐比后者大。 六、总结六、总结 哈希表作为一种存储与查找的优化方式，通过把关键码值映射到数表 3 中一个位置来访问数据，以加快查找速度。在日常生活中，哈希函数的应 用也是随处可见。当今十分流行的 P2P 数据传输技术中一系列的压缩、打 包以及积分标准都应用到了 hash 算法设置。可见利用哈希函数用途之广。 本次程序设计中利用“除留余数法”构造哈希函数，并用“开放定址 法”中的“线性探测再散列”方式处理冲突，选取较为简单的整型数字作 为存储数据。通过此次实验，我对哈希表抽象数据类型的定义以及构造方 法有了初步的认识和了解，也为今后编写更复杂的应用程序提供了新的思 想方法与实现基础。 七、附件（代码、部分图表）七、附件（代码、部分图表） #include #define SUCCESS 1; #define UNSUCCESS 0; #define NULLKEY -1; #define TableLength 13; #define p 13; / H(key)=key % p typedef int T; template struct ElemType T key;/关键字 ; template class LHSearch private: ElemType *HT; /开放定址哈希表 int count; /当前数据元素个数 int size; /哈希表长度 public: LHSearch(); / LHSearch(); / 4 void InitHashTable(int n);/ int Hash(T key); /计算哈希地址 void Collision(int /冲突,计算下一个地址 int Search(T key,int /哈希查找 int Insert(ElemType e);/元素插入 int Delete(ElemType e); /元素删除 void Display(); /显示哈希表 ; template LHSearch:LHSearch() HT=NULL; size=0; count=0; template LHSearch:LHSearch() delete HT; count=0; template int LHSearch:Hash(T key) /由哈希函数求哈希地址 return key%p; template void LHSearch:Collision(int template int LHSearch:Search(T key,int s=Hash(key); while(HTs.key!=-1) if(HTs.key=key) return 1; 5 else return 0; template int LHSearch:Insert(ElemType 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; template int LHSearch:Delete(ElemType e) /删除元素 int s; if(count=NULL) printf(“表空，不能删除!n“); return UNSUCCESS; else s=Hash(e.key); int f; 6 if(f) HTs.key=e.key; printf(“删除成功!n“); count-; return SUCCESS; /表中已有和 e 的关键字相同的元素,不进行插入操作 else printf(“该元素不存在，不能删除!n“); return UNSUCCESS; template void LHSearch:InitHashTable(int n) size=n; HT=new ElemTypesize; for(int i=0;i void LHSearch:Display() for(int i=0;i e; LHSearch a; printf(“输入相应代码，必须先创建哈希表n“); 7 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 (“请选择操作:“); scanf(“%d“, switch(m) case 1:/创建查找表 printf(“请输入表容量：n“); scanf(“%d“, a.InitHashTable(m); printf(“依次输入表元素，-1 结束:n“); for(scanf(“%d“,e.key!=-1;scanf(“%d“, break; case 2: /插入元素 printf(“输入要插入的元素:n“); scanf(“%d“, a.Insert(e); break; case 3: /删除元素 printf(“输入要删除的元素:n“); s