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

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

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

3、行，每行一个字符串。表示要查询的图书记录。输出：输出为m行，如果被查的记录存在，则输出"YES”如果不存在则输出"N0”。测试数据输入：4aansandhellocppabanasansandandehellocbbhellocpp输出：YESNONONOYESYESNONOYES实现提示(1)冲突处理方法为：顺次循环后移到下一个位置，寻找空位插入。(2)BKDE字符串哈希unsignedinthash_BKDE(char*str)/*初始种子seed可取31131131313131131313etc.*/unsignedintseed=131;unsignedinthas

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

5、;unsignedinthash_BKDE(char*str)unsignedintseed=131;unsignedinthash=0;while(*str)hash=hash*seed+(*str+);return(hash&0x7FFFFFFF);doublek=(double)(rand()%999)/1000;unsignedinthash_rand(unsignedintvalue)doublea=k*value;doublen=(a-(int)a)*64;unsignedintseed=(int)n;returnseed;unsignedintHash(char*str)

6、returnhash_rand(hash_BKDE(str);classHashTablepublic:HashTable();HashTable();voidinsert(char*c);boolfind(char*c);private:char*Arr;intArrSize;HashTable:HashTable()ArrSize=32768;Arr=newchar*64;for(inti=0;i<64;i+)Arri=newchar100;Arri=NULL;HashTable:HashTable()for(inti=0;i<64;i+)deleteArri;deleteAr

7、r;voidHashTable:insert(char*c)unsignedintpos=Hash(c);while(Arrpos!=NULL)pos=(pos+1);Arrpos=c;boolHashTable:find(char*c)unsignedintpos=Hash(c);while(Arrpos!=NULL)if(Arrpos=c)returntrue;pos=(pos+1);returnfalse;intmain()boola20;char*c1=newchar100;HashTableH;cout<<"输入字符串个数n：n"intn;cin>>n;cout<<"输入n个字符串：n”;for(inti=1;i<=n;i+)cin>>c1;(c1);cout<<"输入待查的字符串个数m:n"intm;cin>>m;cout<<"输入要查找的字符串："<<endl;for(intj=0;j<m;j+)cin>>c1;aj=(c1);cout<<"查找结果(yes表示存在，no表示不存在)：n"for(intk=0;k<