基于Hash表的班级成员管理数据结构课程设计报告书

1、沈阳航空航天大学课 程 设 计 报 告课程设计名称： 数据结构课程设计课程设计题目：基于 Hash 表的班级成员管理院（系）：计算机学院专业：班级：学号：姓名：指导教师：目录1 题目介绍和功能要求 . 11.1题目介绍 . 11.2功能要求 . 11.3基本功能 . 12 系统功能模块结构图 . 32.1 系统功能结构框图 . 32.2 系统主要模块的功能说明. 33 使用的数据结构的描述. 53.1数据结构设计 . 53.2数据结构用法说明 . 64 函数的描述 . 74.1主要函数设计 . 74.2 主要函数流程图 . 75程序测试和运行的结果.105.1 程序测试 . 105.2 运行结

2、果 . 116参考文献 .13附录（关键部分程序清单）.141 题目介绍和功能要求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 系统功能结构框图图 2.1 系统功能结构框图2.2 系统主要模块的功能说明1.哈希模块CreateHashList()； （adr 为哈希地址）初始化 Hash 表，并创建 Hash

4、函数，并将用户姓名添加至Hash 表中。1) 除留取余法：adr=(DATALISTi.k)%M;（将 DATALISTi.k所存的ASCII 码除以 M 取余所得的哈希地址赋给adr ）2) 随机函数法 : srand(DATALISTi.k); 创建 Hash表哈希函数模块 （除留取余）哈希函数模块（随机数法）哈希函数模块（分割法）冲突处理模块冲突处理模块冲突处理模块冲突处理模块查找模块冲突处理模块冲突处理模块查找模块查找模块int adr=rand()%L;(将 DATALISTi.k所存的 ASCII 码作为种子传入至 srand函数中，并用rand函数产生 L以内的随机值为哈希地址赋

5、给adr) 3) 分割法 : change(DATALIST,A,i); int adr=A1*10+A2;( DATALISTi.k所存的 ASCII 码利用 change() 函数分割开， 并去第二个数字和第三个数字作为哈希地址赋给 adr) 2.冲突处理模块1) srand( 姓名 ASCII 码); d=(d+rand()%L)%M; 伪随机探测再散列2) d=d+1; 线性探测再散列3.查找模块SearchHash(); 查找用户输入姓名是否在Hash 表中；给出该姓名的查找长度和该Hash 函数的平均查找长度。3 使用的数据结构的描述3.1 数据结构设计建立一个确定的对应关系f，使

6、每个关键字和结构中的一个唯一的存储位置相对应。在查找时，只要根据这个对应关系f 找到给定值 K 的像 f（K）为存储地址的结构体数组即为哈希表。哈希表举例（平方取中法） ：A B C Z 0 1 2 9 01 02 03 32 60 61 62 71 记录关键字(关键字）2 哈希地址（ 217-29）A I J I0 P1 P2 Q1 Q2 Q3 0100 1100 1200 1160 2061 2062 2161 2162 2163 0010000 1210000 1440000 1370400 4310541 4314704 4734741 4741304 4745651 010 210

7、440 370 310 314 734 741 745 表 3.1 哈希表3.2 数据结构用法说明取关键字平方后的中间几位为哈希地址。这是一种比较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随即分布的关键字得到的哈希地址也是随即的。取的位数由表长决定。如表3.1 列出了一些标识符及它们的哈希地址。4 函数的描述4.1主要函数设计1. Input () ；作用：将用户姓名换算成ASCII 码。2. CreateHashList()；作用：将用户名输入至哈希表中，并用两种冲突处理方法进行冲

8、突处理。3. SearchHash(); 作用：将用户输入的用户名在哈希表中进行查找，并给出查找结果和查找长度，和该函数的平均查找长度。4. Print () ；作用：打印出程序的主菜单和界面。5. Change(); 作用: 将用户姓名的 ASCII 码分割为多个数字并存入数组中。4.2 主要函数流程图1.CreateHashList()；开始Num哈希表初始化哈希函数处理线性探测再散列冲突处理后将数据导入哈希表中判断冲突将数据导入哈希表中YN1哈希表初始化哈希函数处理判断冲突将数据导入哈希表中YN伪随机数探测再散列冲突处理后将数据导入哈希表中2结束图 4.2.1创建函数流程图2.Searc

9、hHash(); 开始将姓名转化为ASCII 码判断是否一样和哈希表中的数据Return SUCCESSY冲突处理N判断是否一样和哈希表中的数据Return SUCCESSYReturn UNSUCCESSN结束图 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) 除留取余法：(一)线性探测再散列：

10、(二)伪随机数探测再散列：2) 随机数法：(一)线性探测再散列：(二)伪随机数探测再散列：3) 分割法：(一)线性探测再散列：(二)伪随机数探测再散列：2. 数据 2：1) 除留取余法：(一)线性探测再散列：(二)伪随机数探测再散列：2) 随机数法：(一)线性探测再散列：(二)伪随机数探测再散列：3) 分割法：(一)线性探测再散列：(二)伪随机数探测再散列：3. 数据 3：1) 除留取余法：(一)线性探测再散列：(二)伪随机数探测再散列：2) 随机数法：(一)线性探测再散列：(二)伪随机数探测再散列：3) 分割法：(一)线性探测再散列：(二)伪随机数探测再散列：结论： 经比较可知，分割法所建立

11、的哈希函数平均查找长度最短。6 参考文献1 高富平，张楚. 电子商务法 M. 北京：北京大学出版社， 2002 2 Huang S C，Huang Y M，Shieh S MVibration and stability of a rotating shaft containing a transerse crack J , J Sound and Vibration，1993 ，162 （3） ：387 401 3谭浩强著 . C 程序设计（第三版） . 北京: 清华大学出版社 ,2005 4数据结构 : C 语言版 / 严蔚敏 ,吴伟明编著 .北京 :清华大学出版社 ,2007 附录（关键

12、部分程序清单）#include #include #include #define L 50 / 哈希表的长度#define RAND_MAX 10 /随机数范围#define M 47 /除留取余数值#define NAME_NO 29 / 人名的个数#define SUCCESS 1 #define UNSUCESS 0 #define ElemType char typedef struct Hash / 哈希表 ElemType *data; int s; / 查找长度int k; / 当前姓名的ASCII码Hash;Hash hlistL; typedef struct DATE /

13、 班级成员 char *data; / 姓名int k; / 姓名 ASCII 码DATA;DATE DATALISTNAME_NO; void input() /姓名（结构体数组）初始化 char *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=so

14、ngchongyuan; DATALIST8.data=xiejinhua; DATALIST9.data=mashuangmin; DATALIST10.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=liushux

15、in; DATALIST19.data=fengkunkun; DATALIST20.data=suzheng; DATALIST21.data=sunjianwei; 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;

16、 m=DATALISTi.data; for(r=0;*(m+r)!=0;r+) s0=*(m+r)+s0; DATALISTi.k=s0; int CreateHashList() /建立哈希表 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;

17、int adr=(DATALISTi.k)%M; / 哈希函数（除留取余）if(i=NAME_NO) break; int d=adr; if(hlistadr.s=0) hlistadr.k=DATALISTi.k; 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; ret

18、urn 1; break; case 2: for(i=0;iL;i+) /哈希表的初始化 hlisti.data=; hlisti.k=0; hlisti.s=0; for(i=0;iL|strlen(hlistadr.data)=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为

19、初始查找长度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; else while(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 k;int i=1; /m判断选择探测方法floa