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

1、课程实验报告课程名称:数据结构实验项目名称:散列表专业班级：姓名:XXX学号：完成时间： 2015 年 06月13日背景散列表（Hash table,也叫哈希表）,是根据关键码值(Key value）而直接进行访问的数据结构.也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1），是一种高效的动态集合结构。例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串,与语言中的标识符对应。该符号表常采用散列表。例2：为了节约空间，常常需要把文本文件采

2、用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一,该方法采用了散列。问题描述我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。(其实这已经不错了。.。）.通过书名，来查询它是否存在。为了简化问题,我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。基本要求（1） 根据输入建立图书名称表,采用散列表实现该表,散列函数选用BKDE 字符串哈希.（2）数据的输入输出格式：输入分为两部分第一部分，第一行是行数n,n <= 5000.余下n行，每行一个字符串。表示已存在的图书记录。第二部分，第一行是行数m，m = 1000.余下m行，每行

3、一个字符串.表示要查询的图书记录.输出:输出为m行，如果被查的记录存在，则输出"YES”,如果不存在则输出”NO”.测试数据输入：4aansandhellocpp9abanasansandandehellocbbhellocpp输出：YESNONONOYESYESNONOYES实现提示（1)冲突处理方法为：顺次循环后移到下一个位置，寻找空位插入。(2）BKDE 字符串哈希unsigned int hash_BKDE（char str） / 初始种子 seed 可取31 131 1313 13131 131313 etc。. / unsigned int seed = 131；unsi

4、gned int hash = 0；while (str)hash = hash seed + (*str+);return （hash 0x7FFFFFFF）;将字符串哈希到小于231的整数 t，再将t用随机数哈希法映射到 215以内的数.选做内容每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10，000时，采用折叠法构造一个四位数的哈希函数。课后题目实现文本LZW压缩和解压缩。源代码include<iostream#includecstdlibincludectime using namespace std；uns

5、igned 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=kvalue； double n=（a(int）a）64; unsigned int seed=（int）n； return seed; un

6、signed int Hash(charstr) return hash_rand（hash_BKDE(str）; class HashTablepublic: HashTable（）; HashTable（)； void insert（charc); bool find（charc）；private： char*Arr； int ArrSize；;HashTable：HashTable（） ArrSize=32768； Arr=new char*64； for（int i=0;i<64;i+） Arri=new char100； Arri=NULL； HashTable：:HashTa

7、ble（） 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（charc） 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; cout<"输入字符串个数n:n" int n； cinn; cout<”输入n个字符串:n”； for（int i=1；i=n；i+） cin>>c1; H.insert(c1）； cout”输入待查的字符串个数m:n”； int m; cinm； cout"输入要查找的字符串：”endl; for（int j=0；jm;j+） cinc1； aj=H。find（c1）; cout”查找结果（yes表示存在,no表示不存在)：n&