哈希表的设计-数据结构课程的设计.docx

山东科技大学学生课程设计 实习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语言） #includestdio.h #includetime.h//time用到的头文件 #includestdlib.h//随机数用到的头文件 #includectype.h//toascii()用到的头文件 #includestring.h//查找姓名时比较用的头文件 #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; NameTable[4].py=zhangxu; NameTable[5].py=duhuan; NameTable[6].py=fanqing; NameTable[7].py=songxiaofei; NameTable[8].py=dutongtong; NameTable[9].py=sunhaohao; NameTable[10].py=shanjianfeng; NameTable[11].py=wangbaoshan; NameTable[12].py=houfeng; NameTable[13].py=hujiaming; NameTable[14].py=jiangkaiqiang; NameTable[15].py=xuyang; NameTable[16].py=lvdelu; NameTable[17].py=shenjinfeng; NameTable[18].py=xuhui; NameTable[19].py=hanle; NameTable[20].py=xunwenwen; NameTable[21].py=chenhongcong; NameTable[22].py=zhangyanyan; NameTable[23].py=nieyanshun; NameTable[24].py=haopengcheng; NameTable[25].py=yuhaiyuan; NameTable[26].py=