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

实习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=\ NameTable[1].py=\ NameTable[2].py=\ NameTable[3].py=\ NameTable[4].py=\ NameTable[5].py=\ NameTable[6].py=\ NameTable[7].py=\ NameTable[8].py=\ NameTable[9].py=\ NameTable[10].py=\ NameTable[11].py=\ NameTable[12].py=\ NameTable[13].py=\ NameTable[14].py=\ NameTable[15].py=\ NameTable[16].py=\

NameTable[17].py=\ NameTable[18].py=\ NameTable[19].py=\

NameTable[20].py=\ NameTable[21].py=\ NameTable[22].py=\ NameTable[23].py=\ NameTable[24].py=\ NameTable[25].py=\ NameTable[26].py=\ NameTable[27].py=\ NameTable[28].py=\ NameTable[29].py=\

NameTable[30].py=\

for (i=0;i

int s=0;

char *p=NameTable[i].py; for (j=0;*(p+j)!='\\0';j++) s+=toascii(*(p+j)); NameTable[i].m=s; } }

void CreateHashTable() {//建立哈希表

for(i=0;i

{

HashTable[i].py=\ HashTable[i].m =0; HashTable[i].si=0; }

for(i=0;i

int sum=1,j=0;

int adr=(NameTable[i].m)%P; //除留余数法 H(key)=key MOD p,p<=m if(HashTable[adr].si==0) //如果不冲突，将姓名表赋值给哈希表 {

HashTable[adr].m =NameTable[i].m; HashTable[adr].py=NameTable[i].py; HashTable[adr].si=1; }

else //如果冲突 {

while(HashTable[adr].si!=0) {

adr=(adr+d[j++])%HASH_LEN; //伪随机探测再散列法处理冲突

sum=sum+1; //查找次数加1 }

HashTable[adr].m =NameTable[i].m; //将姓名表复制给哈希表对应的位置上

HashTable[adr].py=NameTable[i].py; HashTable[adr].si=sum; } } }

void DisplayNameTable() {//显示姓名表

printf(\地址 \\t\\t 姓名 \\t\\t 关键字\\n\ for (i=0;i

printf(\ %d \\n\}

void DisplayHashTable() {// 显示哈希表

float asl=0.0;

printf(\地址 \\t\\t 姓名 \\t\\t 关键字 \\t 搜索长度\\n\显示的格式 for (i=0;i

printf(\ %d

\\t\\t %d\\n\ asl+=HashTable[i].si; }

asl/=NAME_LEN;//求得ASL

printf(\平均查找长度：ASL(%d)=%f \\n\}

void FindName()

{//查找

char name[20]={0}; int s=0,sum=1,adr;

printf(\请输入想要查找的姓名的拼音:\

scanf(\getchar();

for (j=0;j<20;j++)//求出姓名的拼音所对应的ASCII作为关键字 s+=toascii(name[j]);

adr=s%P; //除留余数法 j=0;

if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name)) //分3种情况进行判断，并输出超找结果

printf(\姓名:%s 关键字:%d 查找长度为: 1\\n\ else if (HashTable[adr].m==0)

printf(\没有想要查找的人!\\n\ else {

while(1) {

adr=(adr+d[j++])%HASH_LEN;//伪随机探测再散列法处理冲突 sum=sum+1; //查找次数加1 if(HashTable[adr].m==0) {

printf(\没有想要查找的人!\\n\ break; }

if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name)) {

printf(\姓名:%s 关键字:%d 查找长度为:%d\\n\ break; } } } }

int main() {//主函数 char c; int a=1;

srand((int)time(0));

for(i=0;i<30;i++)//用随机函数求得伪随机数列d[i]（在1到50之间） d[i]=1+(int)(HASH_LEN*rand()/(RAND_MAX+1.0)); InitNameTable(); CreateHashTable();

printf(\ printf(\ *\\n\ printf(\ 哈希表设计 *\\n\ printf(\ *\\n\ printf(\ A: 显示姓名表 B: 显示哈希表 *\\n\ printf(\ *\\n\ printf(\ C: 查找 D: 退出 *\\n\ printf(\ *\\n\

printf(\ while(a) {

printf(\请选择:\ scanf(\ getchar();

switch(c)//根据选择进行判断，直到选择退出时才可以退出 {

case 'A': case 'a':

DisplayNameTable(); break; case 'B': case 'b':

DisplayHashTable(); break; case 'C': case 'c':

FindName(); break; case 'D': case 'd': a=0; break; default:

printf(\请输入正确的选择!\\n\ break; } }

return 0; }

四、调试分析

编译环境为CodeBlocks。