散列表实验报告篇一：数据结构实验散列表实验报告课程实验报告课程名称：实验项目名称：专业班级：姓名：学号：完成时间：月背景散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。
也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。
例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。
该符号表常采用散列表。
例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。
LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。
问题描述我们希望在浩瀚的图书中，去发现一本书是否存在。
我们不知道书的编号，只知道它的书名。
（其实这已经不错了...）。
通过书名，来查询它是否存在。
为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。
基本要求（1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。
（2）数据的输入输出格式：输入分为两部分第一部分，第一行是行数n，n 第二部分，第一行是行数m，m 输出：输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。
测试数据输入：4aansandhellocppabanansandandehellocbbhellocpp输出：YESNONONOYESYESNONOYES实现提示（1）冲突处理方法为：顺次循环后移到下一个位置，寻找空位插入。
（2）BKDE 字符串哈希unsigned i(转载自：小草范文网:散列表实验报告)nt hash_BKDE(char *str)/* 初始种子 seed 可取31 131 1313 13131 131313 etc.. */while (*str) { hash = hash * seed + (*str++); unsigned int seed = 131; unsigned int hash = 0;} return (hash & 0x7FFFFFFF);将字符串哈希到小于2^31的整数 t，再将t用随机数哈希法映射到 2^15以内的数。
选做内容每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，采用折叠法构造一个四位数的哈希函数。
课后题目实现文本LZW压缩和解压缩。
源代码#include#include#includeusing 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 {Arr[i]=new char[100]; Arr[i]=NULL;}}HashTable::~HashTable(){for(int i=0;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) {篇二：哈希表实验报告定稿数据结构课程设计报告设计题目：哈希表的设计与实现专业通信工程班级__________________ 学生__________________ 学号___________________ 指导教师起止时间 XXXXXX学院年学期目录一．设计要求------------------------------------------------------------------1二．数据结构选择与概要设计2.1 数据结构选择-------------------------------------------------------12.2 流程图--------------------------------------------------------------2以号码为关键字哈希流程----------------------------------2以姓名为关键字哈希流程----------------------------------3添加信息节点流程图----------------------------------------4姓名查找流程图----------------------------------------------5号码查询流程图----------------------------------------------6 三．设计算法3.1 建立节点------------------------------------------------------------73.2 哈希函数的定义---------------------------------------------------73.3 哈希查找------------------------------------------------------------8四．测试结果4.1 操作说明------------------------------------------------------------84.2 主菜单截图---------------------------------------------------------94.3 添加记录截图------------------------------------------------------94.4 散列结果截图-----------------------------------------------------104.5 查找记录截图-----------------------------------------------------104.5 清空记录截图-----------------------------------------------------11五．程序源代码及实验心得5.1 源代码----------------------------------------------------------11~205.2 实验心得-----------------------------------------------------------20一．设计要求【问题描述】设计哈希表实现电话号码查询系统。
设计程序完成以下要求：【基本要求】：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。
（6）在哈希函数确定的前提下，尝试各种不同类型冲突吃力方法（至少两种），考察平均查找长度思路：（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。
得到的数作为地址。
对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。
（2）要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数；（3）要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数（main()）。
（4）测试数据的选择最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，这里选择的测试数据为：1.姓名：郑治华；电话：；地址：湖北蕲春；2.姓名：蔡翔；电话：；地址：江苏宿迁；3.姓名：朱利庆；电话：；地址：湖北阳新；二．数据结构选择与概要设计2.1数据结构选择本设计涉及到的数据结构为：哈希表。
要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。
在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链接地址法结点结构如图：其中name[8]和num[11]是分别为以电话号码和用户名为关键字域，存放关键字（key）；address[20](data)为结点的数据域，用来存储用户的地址。
Next指针是用来指向下一个结点的地址。
2.2流程图Hash函数流程图以号码为关键字的hash函数流程图以姓名为关键字的hash函数流程图。