散列表的设计实验报告 1 、题目： 散列表的设计:针对某个集体中人名设计一个散列表，使得平均查找长度不超过R,并完成相应的建表和查表程序。 2 、基本要求： 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共30 个，取平均查找长度上限为 2，哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。人名长度不超过 20 个字符。可先对过长的人名作折叠处理。 3 、设计思想： a.构造哈希函数的方法很多，常用的有(1)直接定址法(2)数字分析法;(3)平方取中法;(4)折叠法;( 5)除留余数法;(6)随机数法；本实验采用的是除留余数法:取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数为哈希地址 H(key)=key MOD p,p<=m. b.哈希函数可以减少冲突，但不能避免。通常用的处理冲突的方法有：（1）开放定址法，这种方法还包含三种形式，一种叫线性探测再散列，一种叫二次探测再散列，另一种叫伪随机探测再散列。本实验采用的是第三种伪随机探测再散列。求下一个开放地址的公式为： Hi=(H(k)+di)MOD m (Di=伪随机数序列) c.对哈希表的操作 InitNameList() 操作结果：姓名（结构体数组）初始化 CreateHashList() 操作结果：建立哈希表 FindList() 操作结果：在哈希表中查找 Display () 操作结果：显示哈希表 4 、程序结构图 主程序 初始化姓名 建立哈希表 显示哈希表 查找 5 、流程图 6、数据测试 7 、程序清单 #include #include using namespace std; #define HASH_LENGTH 50 #define M 47 #define NAME_NO 30 typedef struct { char *py; int k; }NAME; NAME NameList[HASH_LENGTH]; typedef struct { char *py; int k; int si;//查找长度 }HASH; HASH HashList[HASH_LENGTH]; void InitNameList() { char *f; int r,s0,i; for (i=0; i
VIP
