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

课程实验报告课程名称：数据结构实验项目名称：散列表专业班级：姓名：XXX学号：完成时间： 2024 年 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".测试数据输入:4aansandhellocpp9abanasansandandehellocbbhellocpp输出:YESNONONOYESYESNONOYES实现提示（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 压缩和解压缩。源代码...