1、数据结构实验 散列表实验报告优质资料(可以直接使用,可编辑 优质资料,欢迎下载)课程实验报告课程名称:数据结构实验项目名称:散列表专业班级:姓名:XXX学号:完成时间: 2021 年 06月13日背景散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。在理想情况下,查找、插入、删除操作的时间均为O(1),是一种高效的动态集合结构。例1:计算机程序设计语言的编译程序需要维护一个符号表,其中元素的关键值为任意字符串,与语
2、言中的标识符对应。该符号表常采用散列表。例2:为了节约空间,常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一,该方法采用了散列。问题描述我们希望在浩瀚的图书中,去发现一本书是否存在。我们不知道书的编号,只知道它的书名。(其实这已经不错了.)。通过书名,来查询它是否存在。为了简化问题,我们假设每本书的书名都是一组小写字母组成,长度不超过100字符。基本要求(1) 根据输入建立图书名称表,采用散列表实现该表,散列函数选用BKDE 字符串哈希。(2)数据的输入输出格式:输入分为两部分第一部分,第一行是行数n,n = 5000。余下n行,每行一个字符串。表示已存在的
3、图书记录。第二部分,第一行是行数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. */ u
4、nsigned int seed = 131;unsigned int hash = 0;while (*str)hash = hash * seed + (*str+);return (hash & 0x7FFFFFFF);将字符串哈希到小于231的整数 t,再将t用随机数哈希法映射到 215以内的数。选做内容每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,采用折叠法构造一个四位数的哈希函数。课后题目实现文本LZW压缩和解压缩。源代码#include#include#include using namespa
5、ce std;unsigned int hash_BKDE(char *str) unsigned int seed = 131; unsigned int hash = 0; while (*str) hash = hash * seed + (*str+); return (hash & 0x7FFFFFFF); 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=(i
6、nt)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
7、; 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; H.insert(c1); coutm; cout输入要查找的字符串:endl; for(int j=0;jc1; aj=H.find(c1); cout查找结果(yes表示存在,no表示不存在):n; for(int k=0;km;k+) if(ak) coutYESn; else coutNon; system(pause); return 0;实验结果:运行结果与要求相符,程序无误。