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

课程实验报告
课程名称：数据结构
实验项目名称：散列表
专业班级：
姓名：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".
测试数据
输入:
4
a
ans
and
hellocpp
9
a
b
an
as
ans
and
ande
hellocbb
hellocpp
输出:
YES
NO
NO
NO
YES
YES
NO
NO
YES
实现提示
（1）冲突处理方法为：顺次循环后移到下一个位置,寻找空位插入.
（2)BKDE 字符串哈希
unsigned int hash_BKDE（char ＊str)
{
/* 初始种子 seed 可取31 131 1313 13131 131313 etc。. ＊/
unsigned int seed = 131；
unsigned int hash = 0；
while （＊str)
｛
hash = hash * seed + （＊str++）;
｝
return (hash ＆ 0x7FFFFFFF）;
}
将字符串哈希到小于2^31的整数 t，再将t用随机数哈希法映射到 2^15以内的数。
选做内容
每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，采用折叠法构造一个四位数的哈希函数。
课后题目
实现文本LZW压缩和解压缩。
源代码
＃include〈iostream〉
＃include
#includesh = 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=（int）n；
return seed；
｝
unsigned int Hash(char＊str）
{
return hash_rand（hash_BKDE（str）);
｝
class HashTable
{
public：
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；i<64;i++）
｛
Arr［i］=new char[100];
Arr［i]=NULL；
}
}
HashTable：:~HashTable（）
｛
for（int i=0；i〈64;i++）
delete［］Arr[i]；
delete ［]Arr；
｝
void HashTable:：insert(char＊c）
｛
unsigned int pos=Hash（c）;
while（Arr［pos］!=NULL)
pos=(pos+1）；
Arr[pos］=c；
}
bool HashTable::find（char＊c）
{
unsigned int pos=Hash（c）；
while（Arr[pos］!=NULL）
｛
if（Arr［pos］==c）return true；
pos=(pos+1);
｝
return false;
}
int main（)
｛
bool a［20];
char *c1=new char［100］；
HashTable H;
cout〈〈”输入字符串个数n：\n"
int n；
cin>>n；
cout<<”输入n个字符串：\n"；
for（int i=1；i〈=n；i++）
｛
cin>>c1；
H.insert(c1);
｝
cout〈<”输入待查的字符串个数m：\n”；
int m；
cin>>m；
cout〈〈”输入要查找的字符串：”<〈endl;
for（int j=0;jc1；
a［j]=H.find（c1）；
｝
cout<〈”查找结果（yes表示存在，no表示不存在):\n"；
for(int k=0；k〈m;k++）
if(a［k]）
cout<<”YES\n”;
else
cout<<”No\n"；
system("pause")；
return 0；
｝
实验结果：
运行结果与要求相符，程序无误。