《基于Hash表的班级成员管理数据结构课程设计1.doc》由会员分享，可在线阅读，更多相关《基于Hash表的班级成员管理数据结构课程设计1.doc（21页珍藏版）》请在三一办公上搜索。
1、沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目： 基于Hash表的班级成员管理院（系）：计算机学院专 业： 班 级：学 号： 姓 名： 指导教师： 目 录1 题目介绍和功能要求11.1 题目介绍11.2 功能要求11.3 基本功能12 系统功能模块结构图22.1 系统功能结构框图22.2 系统主要模块的功能说明23 使用的数据结构的描述43.1 数据结构设计43.2 数据结构用法说明44 函数的描述54.1主要函数设计54.2 主要函数流程图55程序测试和运行的结果85.1 程序测试85.2 运行结果96参考文献11附 录（关键部分程序清单）12 1 题目介绍
2、和功能要求1.1 题目介绍针对本班成员以姓名为关键字设计一个Hash表，使得平均查找长度不超过R。要求：1. 自行设计至少3中Hash函数；2. 每种Hash函数采用线性探测再散列和伪随机数探测再散列进行冲突处理；针对本班成员给出每种Hash函数的平均查找长度。建立一个确定的对应关系f，使每个关键字和结构中的一个唯一的存储位置相对应。在查找时，只要根据这个对应关系f找到给定值K的像f（K）所建立的表即为哈希表。1.2 功能要求1.用三种方法创建哈希函数，分别为除留取余法，随机数法和分割法。2.当哈希地址产生冲突时，利用线性探测再散列和伪随机数探测再散列进行冲突处理得到新的哈希地址，并存入哈希表
3、中。3.给出每个用户名的查找长度和该函数的平均查找长度，并比较哪种方法最好。1.3 基本功能1. CreateHashList()建立Hash函数，并采用两种冲突处理方法进行操作。2. SearchHash()查找Hash表，将用户所输入的信息从Hash表中调出，并给出查找长度2 系统功能模块结构图2.1 系统功能结构框图创建Hash表哈希函数模块（除留取余）哈希函数模块（随机数法）哈希函数模块（分割法）冲突处理模块冲突处理模块冲突处理模块冲突处理模块查找模块冲突处理模块冲突处理模块查找模块查找模块图2.1 系统功能结构框图2.2 系统主要模块的功能说明1. 哈希模块CreateHashLis
4、t()；（adr为哈希地址）初始化Hash表，并创建Hash函数，并将用户姓名添加至Hash表中。1) 除留取余法：adr=(DATALISTi.k)%M;（将DATALISTi.k所存的ASCII码除以M取余所得的哈希地址赋给adr）2) 随机函数法: srand(DATALISTi.k);int adr=rand()%L;(将DATALISTi.k所存的ASCII码作为种子传入至srand函数中，并用rand函数产生L以内的随机值为哈希地址赋给adr)3) 分割法: change(DATALIST,A,i);int adr=A1*10+A2;( DATALISTi.k所存的ASCII码利用
5、change()函数分割开，并去第二个数字和第三个数字作为哈希地址赋给adr)2. 冲突处理模块1) srand(姓名ASCII码);d=(d+rand()%L)%M;伪随机探测再散列2) d=d+1;线性探测再散列3. 查找模块SearchHash();查找用户输入姓名是否在Hash表中；给出该姓名的查找长度和该Hash函数的平均查找长度。3 使用的数据结构的描述3.1 数据结构设计建立一个确定的对应关系f，使每个关键字和结构中的一个唯一的存储位置相对应。在查找时，只要根据这个对应关系f找到给定值K的像f（K）为存储地址的结构体数组即为哈希表。哈希表举例（平方取中法）：A B C Z 0 1
6、 2 901 02 0332 60 61 62 71记录关键字(关键字）2哈希地址（217-29）AIJI0P1P2Q1Q2Q3010011001200116020612062216121622163001000012100001440000137040043105414314704473474147413044745651010210440370310314734741745表3.1 哈希表3.2 数据结构用法说明取关键字平方后的中间几位为哈希地址。这是一种比较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数
7、的每一位都相关，由此使随即分布的关键字得到的哈希地址也是随即的。取的位数由表长决定。如表3.1列出了一些标识符及它们的哈希地址。4 函数的描述4.1 主要函数设计1. Input ()；作用：将用户姓名换算成ASCII码。2. CreateHashList()；作用：将用户名输入至哈希表中，并用两种冲突处理方法进行冲突处理。3. SearchHash();作用：将用户输入的用户名在哈希表中进行查找，并给出查找结果和查找长度，和该函数的平均查找长度。4. Print ()；作用：打印出程序的主菜单和界面。5. Change();作用: 将用户姓名的ASCII码分割为多个数字并存入数组中。4.2
8、主要函数流程图1. CreateHashList()；图4.2.1创建函数流程图 2. SearchHash();图4.2.2查找函数流程图 5程序测试和运行的结果5.1 程序测试程序开始菜单：图5.1.1 一号菜单图 输入1或者2；图5.1.2 二号菜单图输入1；图5.1.3查找图输入2；图5.1.4平均查找图5.2 运行结果给出3组数据，每组数据29个用户名，分别用三种哈希函数和两种冲突处理方法进行操作，结果如图：1.数据1：1) 除留取余法：(一) 线性探测再散列：(二) 伪随机数探测再散列：2) 随机数法：(一) 线性探测再散列：(二) 伪随机数探测再散列：3) 分割法：(一) 线性探
9、测再散列：(二) 伪随机数探测再散列：2.数据2：1) 除留取余法：(一) 线性探测再散列：(二) 伪随机数探测再散列：2) 随机数法：(一) 线性探测再散列：(二) 伪随机数探测再散列：3) 分割法：(一) 线性探测再散列：(二) 伪随机数探测再散列：3.数据3：1) 除留取余法：(一) 线性探测再散列：(二) 伪随机数探测再散列：2) 随机数法：(一) 线性探测再散列：(二) 伪随机数探测再散列：3) 分割法：(一) 线性探测再散列：(二) 伪随机数探测再散列：结论：经比较可知，分割法所建立的哈希函数平均查找长度最短。6参考文献1 高富平，张楚 . 电子商务法M. 北京：北京大学出版社，2
10、0022 Huang S C，Huang Y M，Shieh S MVibration and stability of a rotating shaft containing a transerse crackJ, J Sound and Vibration，1993，162（3）：3874013谭浩强著. C程序设计（ 第三版）. 北京: 清华大学出版社,20054数据结构: C语言版 /严蔚敏,吴伟明编著.北京:清华大学出版社,2007附 录（关键部分程序清单）#include#include#include#define L 50 /哈希表的长度 #define RAND_MAX 10
11、 /随机数范围#define M 47 /除留取余数值#define NAME_NO 29 /人名的个数#define SUCCESS 1#define UNSUCESS 0#define ElemType chartypedef structHash/哈希表ElemType *data;int s;/查找长度int k;/当前姓名的ASCII码Hash;Hash hlistL;typedef structDATE/班级成员 char *data;/姓名 int k;/姓名ASCII码DATA;DATE DATALISTNAME_NO;void input() /姓名（结构体数组）初始化 ch
12、ar *m; int r,s0,i; DATALIST0.data=hudi; DATALIST1.data=lijing; DATALIST2.data=peiting; DATALIST3.data=yinhang; DATALIST4.data=liulu; DATALIST5.data=lishengnan; DATALIST6.data=cuililong; DATALIST7.data=songchongyuan; DATALIST8.data=xiejinhua; DATALIST9.data=mashuangmin; DATALIST10.data=wangjing; DATA
13、LIST11.data=qiyueyu; DATALIST12.data=gaozhiwei; DATALIST13.data=fuzedong; DATALIST14.data=shidailong; DATALIST15.data=sujun; DATALIST16.data=zhangxinglei; DATALIST17.data=liuyang; DATALIST18.data=liushuxin; DATALIST19.data=fengkunkun; DATALIST20.data=suzheng; DATALIST21.data=sunjianwei; DATALIST22.d
14、ata=mengbaiyu; DATALIST23.data=yushaolong; DATALIST24.data=lishaolun; DATALIST25.data=zhangkuo; DATALIST26.data=wangdanran; DATALIST27.data=lizhanying; DATALIST28.data=yangjun; for(i=0;iNAME_NO;i+) s0=0; m=DATALISTi.data; for(r=0;*(m+r)!=0;r+) s0=*(m+r)+s0;DATALISTi.k=s0; int CreateHashList() /建立哈希表
15、 int i,num,sum;printf(请选择冲突处理方法n);printf(1.线性探测再散列n);printf(2.伪随机数探测再散列n);scanf(%d,&num);switch(num)case 1: for(i=0;iL;i+)/哈希表的初始化 hlisti.data=; hlisti.k=0; hlisti.s=0; for(i=0;iL;i+) sum=0; int adr=(DATALISTi.k)%M; /哈希函数（除留取余） if(i=NAME_NO) break; int d=adr; if(hlistadr.s=0) hlistadr.k=DATALISTi.k;
16、 hlistadr.data=DATALISTi.data; hlistadr.s=1;/此处已有数据 else do d=d+1; /线性探测再散列法处理冲突 sum=sum+1; /查找次数加1 while (hlistd.s!=0); hlistd.k=DATALISTi.k; hlistd.data=DATALISTi.data; hlistd.s=sum+1; return 1; break;case 2:for(i=0;iL;i+)/哈希表的初始化 hlisti.data=;hlisti.k=0;hlisti.s=0;for(i=0;iL|strlen(hlistadr.data)
17、=0)return UNSUCESS;adr=adr+1;n+;if(stricmp(hlistadr.data,name)=0)*k=hlistadr.s;return SUCCESS;int SearchHash2(char *name,Hash hlist,int *k) /k为查找次数,伪随机数探测查找int s0=0,r,n=1; /n为初始查找长度 for(r=0;*(name+r)!=0;r+) s0=*(name+r)+s0;int adr=s0%M;if(stricmp(hlistadr.data,name)=0)*k=hlistadr.s;return SUCCESS;el
18、sewhile(1)if(nL|strlen(hlistadr.data)=0)return UNSUCESS;srand(s0);adr=(adr+rand()%L)%M;n+;if(stricmp(hlistadr.data,name)=0)*k=hlistadr.s;return SUCCESS;void print()printf(%*n);printf(*n);printf(*n);printf(*哈希表*n);printf(*n);printf(*n);printf(*n);printf(*n);void main()char name20;int result=0,m,n;int
19、 k;int i=1; /m判断选择探测方法float c=0,d;while(1)lp:print();printf(请选择：n);input();m=CreateHashList();printf(请选择：n);printf(1.查找姓名n);printf(2.显示该哈希函数的平均查找长度n);printf(3.退到上级n);scanf(%d,&n);switch(n)case 1:if(m=1)printf(请输入姓名n);scanf(%s,name);result=SearchHash1(name,hlist,&k);if(result=1)printf(查找成功n);printf(查
20、找长度为%dn,k);elseprintf(查找失败n);if(m=2)printf(请输入姓名n);scanf(%s,name);result=SearchHash2(name,hlist,&k);if(result=1)printf(查找成功n);printf(查找长度为%dn,k);elseprintf(查找失败n); break;case 2:d=0;for(i=0;iL;i+)d+=hlisti.s;c=d/NAME_NO;printf(平均查找长度为%fn,c); break;case 3:system(cls);goto lp; break;课程设计总结：指导教师评语：指导教师(签字)： 年 月 日课程设计成绩
