资源描述
数据结构实验 散列表实验报告优质资料
(可以直接使用,可编辑 优质资料,欢迎下载)
课程实验报告
课程名称:数据结构
实验项目名称:散列表
专业班级:
姓名:XXX
学号:
完成时间: 2021 年 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<cstdlib>
#include<ctime>
using namespace 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=(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;j<m;j++)
{
cin>>c1;
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;
}
实验结果:
运行结果与要求相符,程序无误。
展开阅读全文