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

课 程 设 计

课程名称 数据结构 题目名称 哈希表设计 学生学院 计算机学院 专业班级 10级网络工程1班 学 号 ********** 学生姓名 指导教师

2012 年 6 月 17 日

一．问题描述

针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

二.基本要求

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。

三. 需求分析

针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。 在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。

四．程序设计 1 .存储结构设计

typedef struct {

char *py; int k; }NAME;

NAME NameList[HASH_LEN]; typedef struct {

char *py; int k; int si; }HASH;

2 .源代码

#include #include #include

using namespace std;

#define HASH_LEN 50

#define M 47

int NAME_NO=30;

HASH HashList[HASH_LEN];

void InitNameList() {

char *f; int r,s0,i;

NameList[0].py=\"caizenghua\"; NameList[1].py=\"chenjiachuang\"; NameList[2].py=\"chenquanzhong\"; NameList[3].py=\"chenxuebin\"; NameList[4].py=\"chenzhongchao\"; NameList[5].py=\"chenzifan\"; NameList[6].py=\"dengchenhua\"; NameList[7].py=\"duweihao\"; NameList[8].py=\"fangjiatai\"; NameList[9].py=\"heguoliang\"; NameList[10].py=\"hongzexin\"; NameList[11].py=\"huangjinbiao\"; NameList[12].py=\"huangliquan\"; NameList[13].py=\"huangmiaojie\"; NameList[14].py=\"huangrong hao\"; NameList[15].py=\"huangyonghao\"; NameList[16].py=\"liguangxi\"; NameList[17].py=\"lilangzheng\"; NameList[18].py=\"liangcailin\"; NameList[19].py=\"linjiewen\"; NameList[20].py=\"liufurupeng\"; NameList[21].py=\"liuliang\"; NameList[22].py=\"luohaoheng\"; NameList[23].py=\"luowenchao\"; NameList[24].py=\"sunwenhong\"; NameList[25].py=\"tanzeming\"; NameList[26].py=\"wangjian\"; NameList[27].py=\"wangkaibin\"; NameList[28].py=\"wangyixin\"; NameList[29].py=\"wenduke\"; for (i=0;is0=0;

f=NameList[i].py;

for (r=0;*(f+r)!='\\0';r++) s0=*(f+r)+s0; NameList[i].k=s0; } }

void CreateHashList() { int i;

for (i=0; iHashList[i].py=\"\"; HashList[i].k=0; HashList[i].si=0; }

for (i=0;iint sum=0;

int adr=(NameList[i].k)%M; int d=adr;

if(HashList[adr].si==0) {

HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1; }

else { do {

d=(d+NameList[i].k%10+1)%M; sum=sum+1;

}while (HashList[d].k!=0); HashList[d].k=NameList[i].k;

HashList[d].py=NameList[i].py; HashList[d].si=sum+1; } } }

int FindList()

{ char name[20]={0}; int s0=0,r,sum=1,adr,d;

printf(\"\\n请输入人物名称:\"); scanf(\"%s\ for (r=0;r<20;r++) s0+=name[r]; adr=s0%M; d=adr;

if(HashList[adr].k==s0) {

printf(\"\\n名称:%s 关键字:%d 查找长度为: 1\ cout<else if (HashList[adr].k==0)

{

printf(\"无此记录!\"); cout<else {

int g=0; do {

d=(d+s0%10+1)%M; sum=sum+1;

if (HashList[d].k==0) {

printf(\"无此记录! \"); cout<if (HashList[d].k==s0) {

printf(\"\\n名称:%s 关键字:%d 查找长度为:%d\ cout<}while(g==0); } }

void Display() { int i;

float average=0;

for(i=0; iif(HashList[i].k%M==0) HashList[i].py=\"\"; }

printf(\"\\n\\n地址\关键字\\搜索长度\H(key)\ 名称\\n\"); for(i=0; iprintf(\"%d \

printf(\"\%d \ printf(\"\\%d \ printf(\"\\%d \ printf(\"\ %s \

printf(\"\\n\"); }

for (i=0;iprintf(\"\\n\\n平均查找长度：ASL(%d)=%f \\n\\n\ }

void DeleteList() {

char name[20]={0}; int s0=0,r,sum=1,adr,d;

printf(\"\\n请输入人名拼音:\"); scanf(\"%s\ for (r=0;r<20;r++) s0+=name[r]; adr=s0%M; d=adr;

if(HashList[adr].k==s0) {

printf(\"\\n名称:%s 关键字:%d 查找长度为: 1\ cout<cout<<\"删除成功！\"<HashList[d].py=\"\"; HashList[d].k=0; HashList[d].si=0; }

else if (HashList[adr].k==0)

printf(\"无此记录!无法执行删除操作!\"); else {

int g=0; do {

d=(d+s0%10+1)%M; sum=sum+1;

if (HashList[d].k==0) {

printf(\"无此记录!无法执行删除操作!\"); g=1; }

if (HashList[d].k==s0) {

printf(\"\\n名称:%s 关键字:%d 查找长度为:%d\ cout<cout<<\"已删除成功！\"<s0=0;

HashList[d].py=\"\"; HashList[d].k=0; HashList[d].si=0; g=1; }

}while(g==0); } }

void EnterList() {

char st[20]; char *xin; xin=st;

int s0=0,r,sum=1,adr,d,h;

printf(\"\\n请输入人名的拼音:\"); cin>>xin;

for (r=0;*(xin+r)!='\\0';r++) {

s0=(int)(*(xin+r))+s0; }

adr=s0%M; d=adr;

if(HashList[adr].k==s0) {

printf(\"\\n名称:%s 关键字:%d 查找长度为: 1\ cout<cout<<\"已存在于表中，无需插入！\"<else if (HashList[d].k==0) {

printf(\"插入成功！\"); HashList[d].py=xin; HashList[d].k=s0; HashList[d].si=1; h=1;

cout<int g=0,h=0; do {

d=(d+s0%10+1)%M; sum=sum+1;

if (HashList[d].k==0)

{

printf(\"插入成功！\"); HashList[d].py=xin;

HashList[d].k=s0; HashList[d].si=sum; h=1;

cout<if (HashList[d].k==s0) {

printf(\"\\n名称:%s 关键字:%d 查找长度为:%d\ cout<cout<<\"已存在于表中，无需插入！\"<if(h==0) return; else {

NAME_NO++;

NameList[NAME_NO-1].py=xin; int sum=0;

int adr=(NameList[NAME_NO-1].k)%M; int d=adr;

if(HashList[adr].si==0) {

HashList[adr].k=NameList[NAME_NO-1].k; HashList[adr].py=NameList[NAME_NO-1].py; HashList[adr].si=1; }

else { do {

d=(d+NameList[NAME_NO-1].k%10+1)%M; sum=sum+1;

}while (HashList[d].k!=0);

HashList[d].k=NameList[NAME_NO-1].k;

HashList[d].py=NameList[NAME_NO-1].py; HashList[d].si=sum+1; } } }

void main() {

char ch1;

printf(\"\\n 哈希表\\n\");

printf(\" *-------------------------------------------*\\n\");

printf(\" | A. 显示哈希表 |\\n\"); printf(\" | B. 查找 |\\n\"); printf(\" | C. 删除 |\\n\"); printf(\" | D. 插入 |\\n\"); printf(\" | E. 退出 |\\n\"); printf(\" *-------------------------------------------*\\n\"); InitNameList(); CreateHashList (); while(1) {

printf(\"\\n请输入执行命令:\"); fflush(stdin); ch1=getchar();

if (ch1=='A'||ch1=='a') Display();

else if (ch1=='B'||ch1=='b') FindList();

else if (ch1=='C'||ch1=='c') DeleteList();

else if (ch1=='D'||ch1=='d') EnterList();

else if (ch1=='E'||ch1=='e') return; else {

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

五.实验使用环境（本实验所使用的平台和相关的软件）

Microsoft Visual C++ 6.0

六.测试

程序运行初显示如下:

从中选择需要做的操作，输入对应的操作A、B、C、D、E，并按回车，输入错误时，会显示“无此记录！”;正确时，显示姓名，关键字以及查找长度。

程序运行后显示如下:

（1）选择A查找 ， 显示哈希表和平均查找长度，其中平均查找长度小于2，符合题目要求:

（2） 选择B 查找， 输入要查找的人的姓名，若存在则显示名字和对应的关键字以及查找长度；若不存在则显示无此记录：

（3）选择C删除，输入要删除的人的姓名，然后删除后显示删除成功。

（4）选择D查找， 输入要插入的人的姓名，若原先不存在则显示插入成功，若存在则显示已存在表中，无需插入。

（5）选择E退出。 六．实验心得

这段时间的课程设计，我认识到数据结构是一门比较难的课程，需要花很多的时间去练习和实践，要想把这门课程学好学精不是一件容易的事。

这次课程设计的学习，我明白了编写程序的思路是很重要的。如果你的脑袋里面没有思路，根本就不可能编出好的程序。在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。虽然一开始会有很多错误，但只要理解错误的原因，细心观察细节，理解总体的思路，问题就能迎刃而解。