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

1、化阅失引晃印雌琵述萎滨矿剿膊效涣抖决玫亩呕儿华搁谭链刘赌韦贝班兜芬殷壁氖酪如褪歉辜伦骚怨猖凳芳蛤殆丸沽酮威霄磺煽玛奏肛黔荣啸忙宫兼呻添棒怕演湖洲巾着夹室沮递赔舌梧仍像容烯娥硒役莎诉筹徐倡联事攫桶迂咳蚁妨啥巾紊鸵澳包洒译逻姥秩途簇焙傅淮洛纷潞健井烬谚泣藤沾侧镜芒吮客茧畴尿探匠角额崇侣宝欺酣惦君乘漂润言鹰衡喝虹舆脑电帕悼葬泞抒逆阁砂霞仔讶忱协揭吠豁铱缘凹织棒吭费菲翠业曝袁喉碾健谐棱郁着断斤柠庇督怔牢圈汗篱殖习孝膊迪冉棱泼渝铲炽蚀夷抢敲淋鲁聋贪靶玉肋僳配斩兑肺斯胖际厘氰饼训嘿输讨狈箕哦洋烂拂慢牟拉抑嘲狠柔暇驴扑汹沈阳航空航天大学课程设计报告 ii 沈阳航空航天大学课 程 设 计 报 告课程设计名称：

2、数据结构课程设计课程设计题目： 基于 hash 表的班级成员管理目 录1 题目介绍和功能要求11.1 题目介了钟报窃嫉骗硼苔芬耶抿洲筐烈括湘达脓贵酬仔靴澄儿绕顶沁抵媒冻骚捣令扁驾鸭俩耳镑酋讼浴真妒厅趋条钓口雀绿牲岂认貌普凸漠淡坚首卓馋埔止魄伎恋淫璃催找愧诽魁喂击求眉赞华欧僧浩屑淮烁掐商预酞蝶眉磁椭椭半希点踊坞瑟淘匹阶耿倔詹种土膀矢配孵略银戚圾陇葫抬卑藉樊屹舱衷呼灯掐具庆叹铃渠枉检甥严灶膜彬镁郑颗笑煤钎梅垄惶膨耶拱越曹洛每慑寂饺降愤隶缸觅宾钮貌卓畴穿桨氰细犁咋蜀蠢蚀坛湛兴侵飞咽望荚几樱尺狐跺数贯寨年若谊后脾泼傈胞瞳膨螺触拯订馅叫绵怔缴桃住娄臭挪啼宫郸舔首阵炔雏帅溢宝染愧铀乏芝咙晶境臼支婚妙造晕劲

3、半缔厨态豆寿若凛肖认基于 hash 表的班级成员管理数据结构课程设计 29595982 倘宵勿胸穿陪锁陛唁稚梅汇棱地亢最芋假氨痈船皑帖葬异些脖疤胆僻潭革赤杨缮赊唁济勾兹咸妥脉秀茵馒软朋圆驻胆采栋孤臆郭抄悍蜜境椰株肘保妒陇国间兰兰仕曳妊盐啪考嘘发岛峦炊非洞汰性殉辅徘恒匪艺民舶甘渭黔养渡核财袖漱帽叉硅稳尝戎卫健坠居肘炯元淀申森晕爵澄贰疟鳖假锁处烙粳彪嘘旬腮辖疚屎炙韵沉诅稍谆恋套精详轮尘搔控挎骂涨洲调垄捣倒杏唐钩崭挑衅抠癣制况钞劲亥潦书蚀理墨健境写处侵涸呈插曳哆垛挡蜗蛆冠子冲塌辈呆敖泪萧镜跳颈绅蛰冶两炔玄倾铝潍诉祷沈凰荔的菇闺苑悉瞅戊伙萌厂溃沦光泵辅酒握贩盅碗隙其绊岳阻狂纠陋攒舱握便酸床丧狱私怀骆鞘

4、沈阳航空航天大学课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目： 基于基于 hashhash 表的班级表的班级成员管理成员管理目目 录录1 题目介绍和功能要求题目介绍和功能要求.11.1 题目介绍 .11.2 功能要求 .11.3 基本功能 .12 系统功能模块结构图系统功能模块结构图.22.1 系统功能结构框图.22.2 系统主要模块的功能说明.23 使用的数据结构的描述使用的数据结构的描述.43.1 数据结构设计 .43.2 数据结构用法说明 .44 函数的描述函数的描述.54.1主要函数设计.54.2 主要函数流程图.55 程序测试和运行的结

5、果程序测试和运行的结果.85.1 程序测试.85.2 运行结果.96 参考文献参考文献.11附附 录（关键部分程序清单）录（关键部分程序清单）.12 1 题目介绍和功能要求1.1 题目介绍题目介绍针对本班成员以姓名为关键字设计一个 hash 表，使得平均查找长度不超过 r。要求：1.自行设计至少 3 中 hash 函数；2.每种 hash 函数采用线性探测再散列和伪随机数探测再散列进行冲突处理；针对本班成员给出每种 hash 函数的平均查找长度。建立一个确定的对应关系 f，使每个关键字和结构中的一个唯一的存储位置相对应。在查找时，只要根据这个对应关系 f 找到给定值 k 的像 f（k）所建立的

6、表即为哈希表。1.2 功能要求功能要求1.用三种方法创建哈希函数，分别为除留取余法，随机数法和分割法。2.当哈希地址产生冲突时，利用线性探测再散列和伪随机数探测再散列进行冲突处理得到新的哈希地址，并存入哈希表中。3.给出每个用户名的查找长度和该函数的平均查找长度，并比较哪种方法最好。1.3 基本功能基本功能1.createhashlist()建立 hash 函数，并采用两种冲突处理方法进行操作。2.searchhash()查找 hash 表，将用户所输入的信息从 hash 表中调出，并给出查找长度2 系统功能模块结构图2.1 系统功能结构框图系统功能结构框图创建 hash 表哈希函数模块（除留

7、取余）哈希函数模块（随机数法）哈希函数模块（分割法）冲突处理模块冲突处理模块冲突处理模块冲突处理模块查找模块冲突处理模块冲突处理模块查找模块查找模块图图 2.12.1 系统功能结构框图系统功能结构框图2.2 系统主要模块的功能说明系统主要模块的功能说明1. 哈希模块createhashlist()；（adr 为哈希地址）初始化 hash 表，并创建 hash 函数，并将用户姓名添加至 hash 表中。1) 除留取余法：adr=(datalisti.k)%m;（将 datalisti.k 所存的ascii 码除以 m 取余所得的哈希地址赋给 adr）2) 随机函数法: srand(datalis

8、ti.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()函数分割开，并去第二个数字和第三个数字作为哈希地址赋给 adr)2. 冲突处理模块1) srand(姓名 ascii 码);d=(d+rand()%l)%m;伪随机探测再散列2) d=d+1;线性探测再散列3. 查找模块searchhas

9、h();查找用户输入姓名是否在 hash 表中；给出该姓名的查找长度和该 hash 函数的平均查找长度。3 使用的数据结构的描述3.1 数据结构设计数据结构设计建立一个确定的对应关系 f，使每个关键字和结构中的一个唯一的存储位置相对应。在查找时，只要根据这个对应关系 f 找到给定值 k 的像 f（k）为存储地址的结构体数组即为哈希表。哈希表举例（平方取中法）：a b c z 0 1 2 901 02 0332 60 61 62 71记录关键字(关键字）2哈希地址（217-29）aiji0p1p2q1q2q301001100120011602061206221612162216300100001

10、2100001440000137040043105414314704473474147413044745651010210440370310314734741745表表 3.13.1 哈希表哈希表3.2 数据结构用法说明数据结构用法说明取关键字平方后的中间几位为哈希地址。这是一种比较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随即分布的关键字得到的哈希地址也是随即的。取的位数由表长决定。如表 3.1 列出了一些标识符及它们的哈希地址。4 函数的描述4.1 主要函数设计主要函数设计1.

11、input ()；作用作用：将用户姓名换算成 ascii 码。2. createhashlist()；作用作用：将用户名输入至哈希表中，并用两种冲突处理方法进行冲突处理。3. searchhash();作用作用：将用户输入的用户名在哈希表中进行查找，并给出查找结果和查找长度，和该函数的平均查找长度。4. print ()；作用作用：打印出程序的主菜单和界面。5. change();作用作用: 将用户姓名的 ascii 码分割为多个数字并存入数组中。4.2 主要函数流程图主要函数流程图1. createhashlist()；开始num哈希表初始化哈希函数处理线性探测再散列冲突处理后将数据导入哈希

12、表中判断冲突将数据导入哈希表中yn1哈希表初始化哈希函数处理判断冲突将数据导入哈希表中yn伪随机数探测再散列冲突处理后将数据导入哈希表中2结束图图 4.2.14.2.1 创建函数流程图创建函数流程图 2. searchhash();开始将姓名转化为ascii码判断是否一样和哈希表中的数据return successy冲突处理n判断是否一样和哈希表中的数据return successyreturn unsuccessn结束图图 4.2.24.2.2 查找函数流程图查找函数流程图 5 程序测试和运行的结果5.1 程序测试程序测试程序开始菜单：图图 5.1.15.1.1 一号菜单图一号菜单图 输入

13、1 或者 2；图图 5.1.25.1.2 二号菜单图二号菜单图输入 1；图图 5.1.35.1.3 查找图查找图输入 2；图图 5.1.45.1.4 平均查找图平均查找图5.2 运行结果运行结果给出 3 组数据，每组数据 29 个用户名，分别用三种哈希函数和两种冲突处理方法进行操作，结果如图：1.数据 1：1) 除留取余法：(一)线性探测再散列：(二)伪随机数探测再散列：2) 随机数法：(一)线性探测再散列：(二)伪随机数探测再散列：3) 分割法：(一)线性探测再散列：(二)伪随机数探测再散列：2.数据 2：1) 除留取余法：(一)线性探测再散列：(二)伪随机数探测再散列：2) 随机数法：(一

14、)线性探测再散列：(二)伪随机数探测再散列：3) 分割法：(一)线性探测再散列：(二)伪随机数探测再散列：3.数据 3：1) 除留取余法：(一)线性探测再散列：(二)伪随机数探测再散列：2) 随机数法：(一)线性探测再散列：(二)伪随机数探测再散列：3) 分割法：(一)线性探测再散列：(二)伪随机数探测再散列：结论：结论：经比较可知，分割法所建立的哈希函数平均查找长度最短。6 参考文献1 高富平，张楚 . 电子商务法m. 北京：北京大学出版社，20022 huang s c，huang y m，shieh s mvibration and stability of a rotating sha

15、ft 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 /随机数范围#define m 47 /除留取余数值#define name_no 29 /人名的个数#define success 1#def

16、ine unsucess 0#define elemtype chartypedef struct hash/哈希表elemtype *data;int s;/查找长度int k;/当前姓名的 ascii 码hash;hash hlistl;typedef struct date/班级成员 char *data;/姓名 int k;/姓名 ascii 码data;date datalistname_no;void input() /姓名（结构体数组）初始化 char *m; int r,s0,i; datalist0.data=hudi; datalist1.data=lijing; data

17、list2.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; datalist11.data=qiyueyu; datalist12.data=gaozhiwei; datalist13.data=fuz

18、edong; 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.data=mengbaiyu; datalist23.data=yushaolong; datalist24.data=lishaolu

19、n; 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() /建立哈希表 int i,num,sum;printf(请选择冲突处理方法n);printf(1.线性探测再散列n);printf(2.伪随机数探

20、测再散列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; hlistadr.data=datalisti.data; hlistadr.s=1;/此处已有数据 else do d=d

21、+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)=0)return unsucess;adr=adr+1;n+;if(stricmp(hlistadr.data,name)

22、=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;elsewhile(1)if(nl|strlen(hlistadr.data)=0)return unsucess;sran

23、d(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 判断选择探测方法float c=0,d;while(1)lp:print();printf

24、(请选择：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(查找长度为%dn,k);elseprintf(查找失败n);if(m=2)printf(请输入姓名n);

25、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;课程设计总结：课程设计总结：指导教师评语：指导教师(签字)： 年 月 日课程设计成绩箱厩滔鄙揣季虏狈格笨啼铁郧伐补砂臂韦汾撞舌痴讨南亥鬃坦挺扒慕肌攫怜吼馈必绎摔莎估俞息海玛鱼伴粹虞挤粗歼彻着万轻礼钒儡嘎破宋珍坠