收藏 分销(赏)

数据结构实验-散列表实验报告优质资料.doc

上传人:二*** 文档编号:4514864 上传时间:2024-09-26 格式:DOC 页数:8 大小:274.04KB 下载积分:5 金币
下载 相关 举报
数据结构实验-散列表实验报告优质资料.doc_第1页
第1页 / 共8页
本文档共8页,全文阅读请下载到手机保存,查看更方便
资源描述
数据结构实验 散列表实验报告优质资料 (可以直接使用,可编辑 优质资料,欢迎下载) 课程实验报告 课程名称:数据结构 实验项目名称:散列表 专业班级: 姓名: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; } 实验结果: 运行结果与要求相符,程序无误。
展开阅读全文

开通  VIP会员、SVIP会员  优惠大
下载10份以上建议开通VIP会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 学术论文 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        抽奖活动

©2010-2025 宁波自信网络信息技术有限公司  版权所有

客服电话:4009-655-100  投诉/维权电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服