哈希表设计-数据结构课程设计报告书.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语言#include<stdio.h>#include<time.h>/time用到的头文件#include<stdlib.h>/随机数用到的头文件#include<ctype.h>/toascii()用到的头文件#include<string.h>/查找时比拟用的头文件#define HASH_LEN 50/哈希表的长度#define P 47/小于哈希表长度的P#define NAME_LEN 30/表的长度typedef struct/表 char *py; /名字的拼音 int m; /拼音所对应的NAME;NAME NameTableHASH_LEN; /全局定义表typedef struct/哈希表 char *py; /名字的拼音 int m; /拼音所对应的ASCII总和 int si; /查找长度HASH;HASH HashTableHASH_LEN; /全局定义哈希表int d30,i,j; /全局定义随机数,循环用的i、jvoid InitNameTable()/表的初始化 NameTable0.py="caowukui" NameTable1.py="langzhijie" NameTable2.py="dongshuliang" NameTable3.py="qiuhouyang" NameTable4.py="zhangxu" NameTable5.py="duhuan" NameTable6.py="fanqing" NameTable7.py="songxiaofei" NameTable8.py="dutongtong" NameTable9.py="sunhaohao" NameTable10.py="shanjianfeng" NameTable11.py="wangbaoshan" NameTable12.py="houfeng" NameTable13.py="hujiaming" NameTable14.py="jiangkaiqiang" NameTable15.py="xuyang" NameTable16.py="lvdelu" NameTable17.py="shenjinfeng" NameTable18.py="xuhui" NameTable19.py="hanle" NameTable20.py="xunwenwen" NameTable21.py="chenhongcong" NameTable22.py="zhangyanyan" NameTable23.py="nieyanshun" NameTable24.py="haopengcheng" NameTable25.py="yuhaiyuan" NameTable26.py="shuxiang" NameTable27.py="sunyingjie" NameTable28.py="wangbo" NameTable29.py="zhaoqing" NameTable30.py="zhangshengqian"for (i=0;i<NAME_LEN;i+) /将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 int s=0; char *p=NameTablei.py; for (j=0;*(p+j)!='0'j+) s+=toascii(*(p+j); NameTablei.m=s;void CreateHashTable()/建立哈希表 for(i=0;i<HASH_LEN;i+) HashTablei.py="0" HashTablei.m =0; HashTablei.si=0; for(i=0;i<NAME_LEN;i+) int sum=1,j=0; int adr=(NameTablei.m)%P; /除留余数法 H(key)=key MOD p,p<=m if(HashTableadr.si=0) /如果不冲突，将表赋值给哈希表 HashTableadr.m =NameTablei.m; HashTableadr.py=NameTablei.py; HashTableadr.si=1; else /如果冲突 while(HashTableadr.si!=0) adr=(adr+dj+)%HASH_LEN; /伪随机探测再散列法处理冲突 sum=sum+1; /查找次数加1 HashTableadr.m =NameTablei.m; /将表复制给哈希表对应的位置上 HashTableadr.py=NameTablei.py; HashTableadr.si=sum; void DisplayNameTable()/显示表 printf("n地址 tt tt 关键字n"); for (i=0;i<NAME_LEN;i+) printf("%2d %18s tt %d n",i,NameTablei.py,NameTablei.m);void DisplayHashTable()/ 显示哈希表 float asl=0.0; printf("nn 地址 tt tt 关键字 t 搜索长度n"); /显示的格式 for (i=0;i<HASH_LEN;i+) printf("%2d %18s tt %d tt %dn",i,HashTablei.py,HashTablei.m,HashTablei.si); asl+=HashTablei.si; asl/=NAME_LEN;/求得ASL printf("nn平均查找长度：ASL(%d)=%f n",NAME_LEN,asl);void FindName()/查找 char name20=0; int s=0,sum=1,adr; printf("n请输入想要查找的的拼音:");scanf("%s",name);getchar(); for (j=0;j<20;j+)/求出的拼音所对应的ASCII作为关键字 s+=toascii(namej); adr=s%P; /除留余数法 j=0; if(HashTableadr.m=s&&!strcmp(HashTableadr.py,name) /分3种情况进展判断，并输出超找结果 printf("n:%s 关键字:%d 查找长度为: 1n",HashTableadr.py,s); else if (HashTableadr.m=0) printf("没有想要查找的人!n"); else while(1) adr=(adr+dj+)%HASH_LEN;/伪随机探测再散列法处理冲突 sum=sum+1; /查找次数加1 if(HashTableadr.m=0) printf("没有想要查找的人!n"); break; if(HashTableadr.m=s&&!strcmp(HashTableadr.py,name) printf("n:%s 关键字:%d 查找长度为:%dn",HashTableadr.py,s,sum); break; int main()/主函数 char c; int a=1; srand(int)time(0); for(i=0;i<30;i+)/用随机函数求得伪随机数列di在1到50之间 di=1+(int)(HASH_LEN*rand()/(RAND_MAX+1.0); InitNameTable(); CreateHashTable(); printf("*n"); printf("* *n"); printf("* 哈希表设计 *n"); printf("* *n"); printf("* A: 显示表 B: 显示哈希表 *n"); printf("* *n"); printf("* C: 查找 D: 退出 *n"); printf("* *n"); printf("*n"); while(a) printf("n请选择:"); scanf("%c",&c); 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请输入正确的选择!n"); break; return 0;四、调试分析编译环境为CodeBlocks。8 / 8