1、完美升级版基于Hash表的班级成员管理数据结构毕业论文(此文档为word格式，下载后您可任意编辑修改！)沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目： 基于Hash表的班级成员管理院（系）：计算机学院专 业： 班 级：学 号： 姓 名： 指导教师： 目 录1 题目介绍和功能要求 11.1 题目介绍 11.2 功能要求 11.3 基本功能 12 系统功能模块结构图 22.1 系统功能结构框图 22.2 系统主要模块的功能说明 23 使用的数据结构的描述 43.1 数据结构设计 43.2 数据结构用法说明 44 函数的描述 54.1 主要函数设计 54.2 主要
2、函数流程图 55程序测试和运行的结果 85.1 程序测试 85.2 运行结果 96参考文献 11附 录（关键部分程序清单） 12 1 题目介绍和功能要求1.1 题目介绍针对本班成员以姓名为关键字设计一个Hash表，使得平均查找长度不超过R。要求：1. 自行设计至少3中Hash函数；2. 每种Hash函数采用线性探测再散列和伪随机数探测再散列进行冲突处理；针对本班成员给出每种Hash函数的平均查找长度。建立一个确定的对应关系f，使每个关键字和结构中的一个唯一的存储位置相对应。在查找时，只要根据这个对应关系f找到给定值K的像f（K）所建立的表即为哈希表。1.2 功能要求1. 用三种方法创建哈希函数
3、，分别为除留取余法，随机数法和分割法。2. 当哈希地址产生冲突时，利用线性探测再散列和伪随机数探测再散列进行冲突处理得到新的哈希地址，并存入哈希表中。3. 给出每个用户名的查找长度和该函数的平均查找长度，并比较哪种方法最好。1.3 基本功能1. CreateHashList() 建立Hash函数，并采用两种冲突处理方法进行操作。2. SearchHash() 查找Hash表，将用户所输入的信息从Hash表中调出，并给出查找长度2 系统功能模块结构图2.1 系统功能结构框图图2.1 系统功能结构框图2.2 系统主要模块的功能说明1. 哈希模块CreateHashList()；（adr为哈希地址）
4、初始化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码利用change()函数分割开，
5、并去第二个数字和第三个数字作为哈希地址赋给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 2 901 02 03
6、32 60 61 62 71记录关键字(关键字）2哈希地址（217-29）AIJI0P1P2Q1Q2Q3010011001200116020612062216121622163010210440370310314734741745表3.1 哈希表3.2 数据结构用法说明取关键字平方后的中间几位为哈希地址。这是一种比较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随即分布的关键字得到的哈希地址也是随即的。取的位数由表长决定。如表3.1列出了一些标识符及它们的哈希地址。 4 函数的描述4.1
7、 主要函数设计1. Input ()；作用：将用户姓名换算成ASCII码。2. CreateHashList()；作用：将用户名输入至哈希表中，并用两种冲突处理方法进行冲突处理。3. SearchHash();作用：将用户输入的用户名在哈希表中进行查找，并给出查找结果和查找长度，和该函数的平均查找长度。4. Print ()；作用：打印出程序的主菜单和界面。5. Change();作用: 将用户姓名的ASCII码分割为多个数字并存入数组中。4.2 主要函数流程图1. CreateHashList()；图4.2.1创建函数流程图 2. SearchHash();图4.2.2查找函数流程图 5程序
8、测试和运行的结果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) 分割法：(一) 线性探测再散列：(二) 伪随机数探测再散列：2. 数据2：1) 除留取余法：(一) 线性探测再散列：(二) 伪随机数探测再散列：2) 随机数法：(一)
9、线性探测再散列：(二) 伪随机数探测再散列：3) 分割法：(一) 线性探测再散列：(二) 伪随机数探测再散列：3. 数据3：1) 除留取余法：(一) 线性探测再散列：(二) 伪随机数探测再散列：2) 随机数法：(一) 线性探测再散列：(二) 伪随机数探测再散列：3) 分割法：(一) 线性探测再散列：(二) 伪随机数探测再散列：结论：经比较可知，分割法所建立的哈希函数平均查找长度最短。 6参考文献1 高富平，张楚 . 电子商务法M. 北京：北京大学出版社，20022 Huang S C，Huang Y M，Shieh S MVibration and stability of a rotatin
10、g shaft containing a transerse crackJ, J Sound and Vibration，1993，162（3）：3874013谭浩强著. C程序设计（ 第三版）. 北京: 清华大学出版社,20054数据结构: C语言版 严蔚敏,吴伟明编著.北京:清华大学出版社,2007附 录（关键部分程序清单）#includestdio.; DATALIST6.data=cuililong; DATALIST7.data=songchongyuan; DATALIST8.data=xiejinhua; DATALIST9.data=mashuangmin; DATALIST1
11、0.data=wangjing; DATALIST11.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=sun
12、jianwei; DATALIST22.data=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 C
13、reateHashList() 建立哈希表 int i,num,sum; printf(请选择冲突处理方法n); printf(1.线性探测再散列n); printf(2.伪随机数探测再散列n); scanf(%d,&num); switch(num) case 1: for(i=0;iL;i+) 哈希表的初始化 1; break; case 2: for(i=0;iL|strlen( UNSUCESS; adr=adr+1; n+; if(stricmp( SUCCESS; int SearchHash2(char *name,Hash =1; n为初始查找长度 for(r=0;*(name
14、+r)!=0;r+) s0=*(name+r)+s0; int adr=s0%M; if(stricmp( SUCCESS; else while(1) if(nL|strlen( UNSUCESS; srand(s0); adr=(adr+rand()%L)%M; n+; if(stricmp( SUCCESS; void print() printf(%*n); printf(* *n); printf(* *n); printf(* 哈希表 *n); printf(* *n); printf(* *n); printf(* *n); printf(*n);void main() char
15、 name20;int result=0,m,n;int 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,); printf(查找长度为%dn,k); else printf(查找失败n); if(m=2) printf(请输入姓名n); scanf(%s,name); result=SearchHash2(name,); printf(查找长度为%dn,k); else printf(查找失败n); break; case 2: d=0; for(i=0;iL;i+) d+=,c); break; case 3: system(cls); goto lp; break; 课程设计总结：指导教师评语：指导教师(签字)： 年 月 日课程设计成绩
