散列表实验报告doc

散列表实验报告

篇一：数据结构实验散列表实验报告

课程实验报告

课程名称：实验项目名称：专业班级：姓名：学号：完成时间：月

背景

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。

例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。

例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。

问题描述

我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。（其实这已经不错了...）。通过书名，来查询它是否存在。

为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。

基本要求

（1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串

哈希。

（2）数据的输入输出格式：

输入分为两部分

第一部分，第一行是行数n，n 第二部分，第一行是行数m，m 输出：

输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。

测试数据

输入：

4

a

ans

and

hellocpp

a

b

an