数据结构实验 散列表实验报告.pdf

课程实验报告课程 名 称：数据结构实验项目名称：散列表专业 班 级：姓名：XXX学号：完 成 时 间：2015年06月13日背景背景散列表（Hash table，也叫哈希表） ，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为 O(1)，是一种高效的动态集合结构。例 1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。例 2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。 LZW 是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。问题描述问题描述我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。 （其实这已经不错了.） 。通过书名，来查询它是否存在。为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100 字符。基本要求基本要求（1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用 BKDE 字符串哈希。（2）数据的输入输出格式：输入分为两部分第一部分，第一行是行数n，n = 5000。余下 n 行，每行一个字符串。表示已存在的图书记录。第二部分，第一行是行数m，m = 1000。余下m 行，每行一个字符串。表示要查询的图书记录。输出：输出为 m 行，如果被查的记录存在，则输出YES,如果不存在则输出NO。测试数据测试数据输入：4aansandhellocpp9abanasansandandehellocbbhellocpp输出：YESNONONOYESYESNONOYES实现提示实现提示（1）冲突处理方法为：顺次循环后移到下一个位置，寻找空位插入。（2）BKDE 字符串哈希unsigned int hash_BKDE(char *str)/* 初始种子 seed 可取 31 131 1313 13131 131313 etc. */while (*str)hash = hash * seed + (*str+);unsigned int seed = 131;unsigned int hash = 0;return (hash & 0 x7FFFFFFF);将字符串哈希到小于 231 的整数 t，再将 t 用随机数哈希法映射到 215 以内的数。选做内容选做内容每一种西文图书都有一个国际标准图书编号，它是一个10 位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到 10,000 时，采用折叠法构造一个四位数的哈希函数。课后题目课后题目实现文本 LZW 压缩和解压缩。源代码源代码#include#include#includeusing namespace std;unsigned int hash_BKDE(char *str)unsigned int seed = 131;unsigned int hash = 0;while (*str)hash = hash * seed + (*str+);return (hash & 0 x7FFFFFFF);double k=(double)(rand()%999)/1000;unsigned int hash_rand(unsigned int value)double a=k*value;double n=(a-(int)a)*64;unsigned int seed=(int)n;return seed;unsigned int Hash(char*str)return hash_rand(hash_BKDE(str);class HashTablepublic:HashTable();HashTable();void insert(char*c);bool find(char*c);private:char*Arr;int ArrSize;HashTable:HashTable()ArrSize=32768;Arr=new char*64;for(int i=0;i64;i+)Arri=new char100;Arri=NULL;HashTable:HashTable()for(int i=0;i64;i+)deleteArri;delete Arr;void HashTable:insert(char*c)unsigned int pos=Hash(c);while(Arrpos!=NULL)pos=(pos+1);Arrpos=c;bool HashTable:find(char*c)unsigned int pos=Hash(c);while(Arrpos!=NULL)if(Arrpos=c)return true;pos=(pos+1);return false;int main()bool a20;char *c1=new char100;HashTable H;coutn;cout输入 n 个字符串：n;for(int i=1;ic1;(c1);coutm;cout输入要查找的字符串:endl;for(int j=0;jc1;aj=(c1);cout查找结果(yes 表示存在，no 表示不存在)：n;for(int k=0;km;k+)if(ak)coutYESn;elsecoutNon;system(pause);return 0;实验结果实验结果: :运行结果与要求相符，程序无误。