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

1、课 程 设 计 课程名称 数据结构 题目名称 哈希表设计 学生学院 计算机学院 专业班级 10级网络工程1班 学 号 3210006470 学生姓名 指导教师 2012 年 6 月 17 日一问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。二.基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。三. 需求分析 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。人名为汉语拼音形式，最长

2、不超过19个字符(如：庄双双 zhuangshuangshuang)。 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。 在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。四程序设计1 .存储结构设计typedef struct char *py; int k; NAME;NAME NameListHASH_LEN; typedef struct char *py; int k; int si; HASH; 2 .源代码#include<

3、stdio.h>#include<iostream>#include<conio.h>using namespace std;#define HASH_LEN 50 #define M 47 int NAME_NO=30; HASH HashListHASH_LEN; void InitNameList() char *f; int r,s0,i; NameList0.py="caizenghua" NameList1.py="chenjiachuang" NameList2.py="chenquanzhong&q

4、uot; NameList3.py="chenxuebin" NameList4.py="chenzhongchao" NameList5.py="chenzifan" NameList6.py="dengchenhua" NameList7.py="duweihao" NameList8.py="fangjiatai" NameList9.py="heguoliang" NameList10.py="hongzexin" NameLi

5、st11.py="huangjinbiao" NameList12.py="huangliquan" NameList13.py="huangmiaojie" NameList14.py="huangrong hao" NameList15.py="huangyonghao" NameList16.py="liguangxi" NameList17.py="lilangzheng" NameList18.py="liangcailin"

6、 NameList19.py="linjiewen" NameList20.py="liufurupeng" NameList21.py="liuliang" NameList22.py="luohaoheng" NameList23.py="luowenchao" NameList24.py="sunwenhong" NameList25.py="tanzeming" NameList26.py="wangjian" NameList

7、27.py="wangkaibin" NameList28.py="wangyixin" NameList29.py="wenduke" for (i=0;i<NAME_NO;i+) s0=0; f=NameListi.py; for (r=0;*(f+r)!='0'r+) s0=*(f+r)+s0; NameListi.k=s0; void CreateHashList() int i; for (i=0; i<NAME_NO;i+) HashListi.py="" HashListi

8、.k=0; HashListi.si=0; for (i=0;i<HASH_LEN;i+) int sum=0; int adr=(NameListi.k)%M; int d=adr; if(HashListadr.si=0) HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else do d=(d+NameListi.k%10+1)%M; sum=sum+1; while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=Na

9、meListi.py; HashListd.si=sum+1; int FindList() char name20=0; int s0=0,r,sum=1,adr,d; printf("n请输入人物名称:"); scanf("%s",name); for (r=0;r<20;r+) s0+=namer; adr=s0%M; d=adr; if(HashListadr.k=s0) printf("n名称:%s 关键字:%d 查找长度为: 1",HashListd.py,s0); cout<<endl; return

10、0; else if (HashListadr.k=0) printf("无此记录!"); cout<<endl; return 1; else int g=0; do d=(d+s0%10+1)%M; sum=sum+1; if (HashListd.k=0) printf("无此记录! "); cout<<endl; g=1; return 1; if (HashListd.k=s0) printf("n名称:%s 关键字:%d 查找长度为:%d",HashListd.py,s0,sum); cout<

11、;<endl; g=1; return 0; while(g=0); void Display() int i; float average=0; for(i=0; i<NAME_NO; i+) if(HashListi.k%M=0) HashListi.py="" printf("nn地址t关键字tt搜索长度tH(key)t 名称n"); for(i=0; i<NAME_NO; i+) printf("%d ",i); printf("t%d ",HashListi.k); printf(&qu

12、ot;tt%d ",HashListi.si); printf("tt%d ",HashListi.k%M); printf("t %s ",HashListi.py); printf("n"); for (i=0;i<HASH_LEN;i+) average+=HashListi.si; average/=NAME_NO; printf("nn平均查找长度：ASL(%d)=%f nn",NAME_NO,average); void DeleteList() char name20=0; int s

13、0=0,r,sum=1,adr,d; printf("n请输入人名拼音:"); scanf("%s",name); for (r=0;r<20;r+) s0+=namer; adr=s0%M; d=adr; if(HashListadr.k=s0) printf("n名称:%s 关键字:%d 查找长度为: 1",HashListd.py,s0); cout<<endl; cout<<"删除成功！"<<endl; s0=0; HashListd.py=""

14、 HashListd.k=0; HashListd.si=0; else if (HashListadr.k=0) printf("无此记录!无法执行删除操作!"); else int g=0; do d=(d+s0%10+1)%M; sum=sum+1; if (HashListd.k=0) printf("无此记录!无法执行删除操作!"); g=1; if (HashListd.k=s0) printf("n名称:%s 关键字:%d 查找长度为:%d",HashListd.py,s0,sum); cout<<endl;

15、 cout<<"已删除成功！"<<endl; s0=0; HashListd.py="" HashListd.k=0; HashListd.si=0; g=1; while(g=0); void EnterList() char st20; 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

16、; adr=s0%M; d=adr; if(HashListadr.k=s0) printf("n名称:%s 关键字:%d 查找长度为: 1",HashListd.py,s0); cout<<endl; cout<<"已存在于表中，无需插入！"<<endl; else if (HashListd.k=0) printf("插入成功！"); HashListd.py=xin; HashListd.k=s0; HashListd.si=1; h=1; cout<<endl; else int

17、 g=0,h=0; do d=(d+s0%10+1)%M; sum=sum+1; if (HashListd.k=0) printf("插入成功！"); HashListd.py=xin; HashListd.k=s0; HashListd.si=sum; h=1; cout<<endl; g=1; if (HashListd.k=s0) printf("n名称:%s 关键字:%d 查找长度为:%d",HashListd.py,s0,sum); cout<<endl; cout<<"已存在于表中，无需插入！&

18、quot;<<endl; g=1; while(g=0); if(h=0) return; else NAME_NO+; NameListNAME_NO-1.py=xin; int sum=0; int adr=(NameListNAME_NO-1.k)%M; int d=adr; if(HashListadr.si=0) HashListadr.k=NameListNAME_NO-1.k; HashListadr.py=NameListNAME_NO-1.py; HashListadr.si=1; else do d=(d+NameListNAME_NO-1.k%10+1)%M;

19、 sum=sum+1; while (HashListd.k!=0); HashListd.k=NameListNAME_NO-1.k; HashListd.py=NameListNAME_NO-1.py; HashListd.si=sum+1; void main() char ch1; printf("n 哈希表n"); printf(" *-*n"); printf(" | A. 显示哈希表 |n"); printf(" | B. 查找 |n"); printf(" | C. 删除 |n"

20、); 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') EnterLi