山东科技大学学生课程设计 实习6、哈希表设计 一、 需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过 R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有 30 个，取平均查找长度的上限为 2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30 个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19 个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C 语言中的toascii 函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D 是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关 键 字。 数据关 系 R：数据元素同属 一个集合。 InitNameTable() 操 作结 果：初 始 化 姓名表。 CreateHashTable() 操 作结 果：建立 哈希表。 DisplayNameTable() 操 作结 果：显 示姓名表。 DisplayHashTable() 操 作结 果：显 示哈希表。 FindName() 操 作结 果：查找姓名。 }ADT Hash 三 、详 细 设计（源 代 码） （使用 C 语言） #include #include//time 用到 的头 文 件 #include//随机数用到 的头 文 件 #include//toascii()用到 的头 文 件 #include//查找姓名时 比较用的头 文 件 #define HASH_LEN 50//哈希表的长度 #define P 47//小 于 哈希表长度的P #define NAME_LEN 30//姓名表的长度 typedef struct {//姓名表 char *py; //名字的拼音 int m; //拼音所对应的 }NAME; NAME NameTable[HASH_LEN]; //全 局 定 义 姓名表 typedef struct {//哈希表 char *py; //名字的拼音 山东科技大学学生课程设计 int m; //拼音所对应的ASCII 总和 int si; //查找长度 }HASH; HASH HashTable[HASH_LEN]; //全局定义哈希表 int d[30],i,j; //全局定义随机数,循环用的i、j void InitNameTable() {//姓名表的初始化 NameTable[0].py="caowukui"; NameTable[1].py="langzhijie"; NameTable[2].py="dongshuliang"; NameTable[3].py="qiuhouyang"; NameT...
