《2022年基于Hash表的班级成员管理_数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《2022年基于Hash表的班级成员管理_数据结构课程设计.docx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 参考文献 .1.1.附 录（关键
2、部分程序清单）12欢迎下载精品学习资源1 题目介绍和功能要求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 表哈希函数模块（除留取余）哈希函数模块（随机数法）哈希函数模块（分割法）冲突处理模块冲突处理模块冲突处理模块冲突查处找理模模块块冲突查处找理模模块块
4、冲突查处找理模模块块图 2.1 系统功能结构框图2.2 系统主要模块地功能说明1. 哈希模块CreateHashList ；（ adr 为哈希地址）初始化 Hash 表，并创建 Hash 函数，并将用户姓名添加至Hash 表中 .1) 除留取余法： adr=DA TALISTi.k%M；（将 DATALISTi.k所存地 ASCII 码除以 M 取余所得地哈希地址赋给adr）2) 随机函数法 : srandDATALISTi.k；int adr=rand%L ；将 DA TALISTi.k所存地 ASCII 码作为种子传入至 srand 函数中，并用rand 函数产生L 以内地随机值为哈希地址
5、赋给 adr欢迎下载精品学习资源3) 分割法 : changeDATALIST,A,i；int adr=A1*10+A2； DATALISTi.k所存地 ASCII 码利用 change欢迎下载精品学习资源2. 冲突处理模块函数分割开，并去其次个数字和第三个数字作为哈希地址赋给adr欢迎下载精品学习资源1) srand姓名 ASCII 码；d=d+rand%L%M ；伪随机探测再散列2) d=d+1 ；线性探测再散列3. 查找模块SearchHash；查找用户输入姓名是否在Hash 表中；给出该姓名地查找长度和该Hash 函数地平均查找长度 .欢迎下载精品学习资源3 使用地数据结构地描述3.1
6、 数据结构设计建立一个确定地对应关系f，使每个关键字和结构中地一个唯独地储备位置相对应.在查找时，只要依据这个对应关系f 找到给定值 K 地像 f（ K）为储备地址地结构体数组即为哈希表 .哈希表举例（平方取中法）：ABCZ0129记录关键字关键字） 2哈希地址（ 217-29 ）0102 0332 60 61 6271A01000010000010I11001210000210J12001440000440I011601370400370P120614310541310P220624314704314Q121614734741734Q221624741304741Q3216347456517
7、45表 3.1 哈希表3.2 数据结构用法说明取关键字平方后地中间几位为哈希地址.这是一种比较常用地构造哈希函数地方法.通常在选定哈希函数时不肯定能知道关键字地全部情形，取其中哪几位也不肯定合适，而一个数平方后地中间几位数和数地每一位都相关，由此使立即分布地关键字得到地哈希地址也是立即地 .取位置数由表长打算 .如表 3.1 列出了一些标识符及它们地哈希地址.欢迎下载精品学习资源4 函数地描述4.1 主要函数设计1. Input ；作用：将用户姓名换算成ASCII 码.2. CreateHashList ；作用：将用户名输入至哈希表中，并用两种冲突处理方法进行冲突处理.3. SearchHas
8、h；作用：将用户输入地用户名在哈希表中进行查找，并给出查找结果和查找长度，和该函数地平均查找长度.4. Print ；作用：打印出程序地主菜单和界面.5. Change；作用 : 将用户姓名地ASCII 码分割为多个数字并存入数组中.4.2 主要函数流程图1. CreateHashList ；欢迎下载精品学习资源开头12Num哈希表初始化哈希表初始化哈希函数处理哈希函数处理判定冲突判定冲突NNYY线性探测再散列冲突处理后将数据导入哈希表中将数据导入哈希表中伪随机数探测再散列冲突处理后将数据导入哈希表中将数据导入哈希表中终止图 4.2.1 创建函数流程图2. SearchHash；欢迎下载精品学
9、习资源开头将姓名转化为ASCII 码Y判定是否一样和哈希表中的数据NReturn SUCCESS冲突处理Y判定是否一样和哈希表中的数据NReturn SUCCESSReturn UNSUCCESS终止图 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 . 北京：北京高校出版社，20022 Huang S C ， Huang Y M ， Shieh S M Vibration and stability of a rotating shaft containing a transerse crack J , J Sound and Vibration ，1993， 162（ 3）： 387 4013 谭浩强著 . C 程序设计（ 第三版
12、） . 北京 : 清华高校出版社 ,20054 数据结构 : C 语言版 /严蔚敏 ,吴伟明编著 . 北京: 清华高校出版社 ,2007欢迎下载精品学习资源附 录（关键部分程序清单）#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 chartypedef structHash/哈希表ElemType *data
13、 ；int s；/ 查找长度int k ；/ 当前姓名地ASCII 码Hash ；Hash hlistL ；typedef structDATE/ 班级成员char *data ；/ 姓名int k ；/ 姓名 ASCII码DATA ；DATE DA TALISTNAME_NO；void input / 姓名（结构体数组）初始化char *m ；int r,s0,i ；DATALIST0.data=hudi；DATALIST1.data=lijing；DATALIST2.data=peiting；DATALIST3.data=yinhang；DATALIST4.data=liulu；DATAL
14、IST5.data=lishengnan；DATALIST6.data=cuililong；DATALIST7.data=songchongyuan；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.dat
15、a=zhangxinglei；DATALIST17.data=liuyang；DATALIST18.data=liushuxin；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
16、；DATALIST28.data=yangjun；fori=0 ；iNAME_NO；i+s0=0；m=DATALISTi.data；forr=0 ； *m+r.=0 ；r+s0=*m+r+s0 ；DATALISTi.k=s0；int CreateHashList / 建立哈希表int i,num,sum ；printf 请挑选冲突处理方法 n ；printf1. 线性探测再散列 n ；printf2. 伪随机数探测再散列 n ；scanf%d,&num ；switchnumcase 1:fori=0 ；iL ；i+/ 哈希表地初始化hlisti.data=；hlisti.k=0 ；hlisti
17、.s=0 ；fori=0 ；iL ；i+sum=0 ；int adr=DATALISTi.k%M； /哈希函数（除留取余）欢迎下载精品学习资源ifi=NAME_NObreak；int d=adr ；ifhlistadr.s=0欢迎下载精品学习资源据else/ 线性探测再散列法处理冲突加 1hlistadr.k=DATALISTi.k；hlistadr.data=DATALISTi.data；hlistadr.s=1 ；/ 此处已有数dod=d+1 ；sum=sum+1；/ 查找次数while hlistd.s.=0；hlistd.k=DATALISTi.k；hlistd.data=DATALI
18、STi.data；hlistd.s=sum+1 ；欢迎下载精品学习资源case 2:break ；return 1 ；fori=0 ；iL ；i+/ 哈希表地初始化欢迎下载精品学习资源hlisti.data= ；hlisti.k=0 ；hlisti.s=0 ；fori=0 ；iL|strlenhlistadr.data=0 return UNSUCESS ；adr=adr+1 ；n+ ；欢迎下载精品学习资源ifstricmphlistadr.data,name=0*k=hlistadr.s ；return SUCCESS ；int SearchHash2char *name,Hash hlis
19、t,int *k /k为查找次数 ,伪随机数探测查找int s0=0,r,n=1 ；/n 为初始查找长度forr=0 ； *name+r.=0 ；r+s0=*name+r+s0 ；int adr=s0%M ；ifstricmphlistadr.data,name=0欢迎下载精品学习资源else*k=hlistadr.s ；return SUCCESS ；while1欢迎下载精品学习资源ifnL|strlenhlistadr.data=0 return UNSUCESS ；srands0；adr=adr+rand%L%M；n+ ；ifstricmphlistadr.data,name=0欢迎下载
20、精品学习资源void print*k=hlistadr.s ；return SUCCESS ；printf%*nprintf*n；printf*n；printf*哈希表*n；欢迎下载精品学习资源printf*n；printf*n；printf*n；printf*n；void mainchar name20 ；int result=0,m,n ；int k ；int i=1 ； /m 判定挑选探测方法float c=0,d ；while1lp:print ；printf 请挑选： n ；input ；m=CreateHashList ；printf 请挑选： n ；printf1. 查找姓名 n
21、 ；printf2. 显示该哈希函数地平均查找长度n ；printf3. 退到上级 n ；scanf%d,&n ；switchncase 1:欢迎下载精品学习资源ifm=1printf 请输入姓名 n ；scanf%s,name ；result=SearchHash1name,hlist,&k ；ifresult=1欢迎下载精品学习资源ifm=2elseprintf 查找胜利 n ；printf 查找长度为 %dn,k ；printf 查找失败 n ；欢迎下载精品学习资源printf 请输入姓名 n ；scanf%s,name ；result=SearchHash2name,hlist,&k ；ifresult=1欢迎下载精品学习资源欢迎下载精品学习资源elseprintf 查找胜利 n ；printf 查找长度为 %dn,k ；printf 查找失败 n ；欢迎下载精品学习资源欢迎下载精品学习资源case 2:case 3:break ；break ；break ；d=0 ；fori=0 ；iL ；i+d+=hlisti.s ；c=d/NAME_NO；printf 平均查找长度为 %fn,c ；systemcls ；goto lp ；欢迎下载精品学习资源课程设计总结：指导老师评语：指导老师 签字：年 月日课程设计成果欢迎下载精品学习资源欢迎下载