实验十一 散列表实验
- 格式：doc
- 大小：46.50 KB
- 文档页数：3
查找技术
实验十一散列表实验
1. 实验目的
⑴掌握散列查找的基本思想；
⑵掌握闭散列表的构造方法；
⑶掌握线性探测处理冲突的方法；
⑷掌握散列技术的查找性能。
2. 实验内容
⑴对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表；
⑵设计查找算法，验证查找性能。
3. 实现提示
假设散列表长为m，散列函数为除留余数法，即H(key)=key% p，m和p在主函数中由用户从键盘输入，待散列的数据也由用户从键盘输入，算法如下：
假设在已建立的散列表中进行静态查找，在查找过程中设置计数器count统计元素的比较次数，查找算法如下：
查找技术
选作内容：
闭散列表和开散列表查找性能的比较
1. 问题描述
对于给定的一组关键码，分别采用线性探测法和拉链法建立散列表，并且在这两种方法构建的散列表中查找关键码k，比较两种方法的时间性能和空间性能。
2. 基本要求
⑴用线性探测法处理冲突建立闭散列表；
⑵用拉链法处理冲突建立开散列表；
⑶设计合理的测试数据，比较二者的查找性能。
3. 设计思想
对于给定的一组关键码和相同的散列函数，如果处理冲突时采用的方法不同，建立散列表也不同，通常查找性能也不同。
采用线性探测法处理冲突建立闭散列表以及在闭散列表上进行查找的算法在教材中已做过实验，下面讨论拉链法处理冲突的方法。
首先定义开散列表的存储结构。
同义词子表中的结点即为单链表中的结点，其结点结构定义如下（本章假定数据域均为整数）：
struct Node
{
int data;
Node *next;
查找技术
};
每个同义词子表由一个头指针指示，将所有头指针存储在一个一维数组中，形成开散列表。
假设散列表长为m，则开散列表ht定义如下：
Node *ht[m];
采用拉链法建立开散列表，需将待散列的每个关键码按散列地址存储到相应的同义词子表中，算法如下：
在开散列表上进行查找，只需到相应的同义词子表中进行查找，为记载与关键码的比较次数，设置计数器count。
算法如下：。
