《数据结构课程设计报告哈希表设计.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告哈希表设计.doc（18页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计报告题 目： 哈希表设计 院 （系）： 计算机工程学院 专 业： 计算机科学与技术 班 级： 嵌入式1091 学 生： 指导教师： 2010年 12月目 录一、设计目的1二、设计内容1三、程序设计步骤2四、调试分析11五、测试结果11六、课程设计小结16一、设计目的1、学会根据实际问题建立哈希表，并实现其查找功能。2、理解哈希表的思想就是以借点的关键字K为变量，通过一个确定的函数关系f，计算出对应的函数值f（k），把这个函数值解释为结点的存储地址，将该结点存入f（k）所指示的存储位置上，这样建立的表称为哈希表。3、学会使用除留余数法获得哈希地址。4、学会使用再地址方法解决哈希冲
2、突问题。5、学会查阅书籍，自我思考，解决实际问题。二、设计内容1、系统名称：哈希表设计 针对自己班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。2、要求：(1)设计一个哈希表，用来存放30个人名。(2)要求人名为中国姓名的汉语拼音形式。(3)要求用除留余数法构造哈希函数，用线性探查法解决哈希冲突。(4)本设计实现的功能： 建立哈希表并且将其显示出来。 通过要查找的关键字用哈希函数计算出相应的地址来查找人名。三、程序设计步骤1）查找功能分析说明： 本实验最关键的是实现哈希表的查找功能，因为元素的地址可能存在同义词，所以便会存在查找冲突，关键的就是解决这种冲突
3、问题。哈希中解决冲突的方法有很多种，这里采用线性探查法解决冲突。通过构造函数d=（d+Hash（key）%p，若数据元素在存储地址d发生冲突，则放到存储地址（d1k）%m；若又发生冲突则放到存储地址（d2k）%m；若再发生冲突则放到存储地址（d3k）%m；直到碰到第一个为空的存储地址（dik）%m，则将数据元素存放在该存储空间。 查找的功能分析说明图如下：开始输入要查找的姓名判断是否冲突线性探查法输出否是是否冲突否是2）代码分析：#include #define HASH_LEN 50 /* 哈希表长度 */#define M 47 /* 定义P值 */#define NAME_NO 30 /
4、* 人名个数 */typedef struct NAME char *py; /* 名字拼音 */ int k; /* 拼音所对应的整数 */NAME;NAME NameListHASH_LEN; typedef struct hterm /* 哈希表 */ char *py; /* 名字的拼音 */ int k; /* 拼音所对应的整数 */ int si; /* 查找长度 */HASH;HASH HashListHASH_LEN; /*-姓名（结构体数组）初始化-*/void InitNameList() int i; char *f; int r,s0; NameList0.py=bia
5、nshan; NameList1.py=dengtao; NameList2.py=dingjun; NameList3.py=fanyongliang; NameList4.py=wangchen; NameList5.py=wangrong; NameList6.py=zhouyu; NameList7.py=liuyuanlong; NameList8.py=wuliang; NameList9.py=wulingjie; NameList10.py=wangzhaocai; NameList11.py=yujia; NameList12.py=zhangzhefu; NameList1
6、3.py=zhangnannan; NameList14.py=zhoujie; NameList15.py=yuanhunan; NameList16.py=lichunfeng; NameList17.py=lishiyan; NameList18.py=zhouxiaoqing; NameList19.py=liuwei; NameList20.py=niliquan; NameList21.py=qinyao; NameList22.py=zhuchengwei; NameList23.py=lvshuai; NameList24.py=qiuyan; NameList25.py=gu
7、tianyun; NameList26.py=zhoupei; NameList27.py=chenjinmei; NameList28.py=zhouxu; NameList29.py=zhaoliping; for (i=0;iNAME_NO;i+)/* *求出各个姓名的拼音所对应的整数 */ s0=0; f=NameListi.py; for (r=0;*(f+r) != 0;r+) /* 方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 */ s0=*(f+r)+s0; NameListi.k=s0; /*-建立哈希表-*/void CreateHashL
8、ist() int i; for ( i=0; iHASH_LEN;i+)/* 哈希表的初始化 */ HashListi.py=; HashListi.k=0; HashListi.si=0; for (i=0;iNAME_NO;i+) int sum=0; int adr=(NameListi.k) % M; /* 除留余数法构造哈希函数 */ int d=adr; if(HashListadr.si=0) /* 如果不冲突 */ HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /*
9、 冲突 */ do d=(d+(NameListi.k)%M; /* 线性探查法 */ sum=sum+1; /* 查找次数加1 */ while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; /*-查找-*/void FindList() int r; char name20=0; int s0=0; int sum=1; int adr;int d; printf(nnname spell: ); /* 输入姓名 */ scanf(%s,name); for
10、 ( r=0;rHASH_LEN)LON=HASH_LEN; gotoxy(1,1);printf(HashTable: ); gotoxy(1,2);printf(address: ); for(i=0;iLON;i+) gotoxy(1,i+3); printf(%-3d,i); ; gotoxy(9,2);printf(the H(key) : ); for(i=0;iLON;i+) gotoxy(10,i+3); printf(%-6d,HashListi.k); ; gotoxy(25,2);printf(the lenth: ); for(i=0;iLON;i+) gotoxy(2
11、6,3+i); printf(%2d,HashListi.si); ; gotoxy(37,2);printf(spell: ); for(i=0;iLON;i+) gotoxy(38,i+3); printf(%s,HashListi.py); ; gotoxy(50,2);printf(H(key): ); for(i=0;iLON;i+) gotoxy(51,i+3); printf(%2d,(HashListi.k)%M); ; average=0; for (i=0;i15) system(cls); if (LONHASH_LEN-15)LON=HASH_LEN-15; gotox
12、y(1,1);printf(HashTable: ); gotoxy(1,2);printf(address: ); for(i=0;iLON;i+) gotoxy(1,i+3); printf(%-3d,i+15); ; gotoxy(9,2);printf(the H(key) : ); for(i=0;iLON;i+) gotoxy(10,i+3); printf(%-6d,HashListi+15.k); ; gotoxy(25,2);printf(the lenth: ); for(i=0;iLON;i+) gotoxy(26,3+i); printf(%2d,HashListi+1
13、5.si); ; gotoxy(37,2);printf(spell: ); for(i=0;iLON;i+) gotoxy(38,i+3); printf(%s,HashListi+15.py); ; gotoxy(50,2);printf(H(key):); for(i=0;iLON;i+) gotoxy(51,i+3); printf(%2d,(HashListi+15.k)%M); ; average=0; for (i=0;i30) system(cls); if (LONHASH_LEN-30)LON=HASH_LEN-30; gotoxy(1,1);printf(HashTabl
14、e: ); gotoxy(1,2);printf(address: ); for(i=0;iLON;i+) gotoxy(1,i+3); printf(%-3d,i+30); ; gotoxy(9,2);printf(the H(key) : ); for(i=0;iLON;i+) gotoxy(10,i+3); printf(%-6d,HashListi+30.k); ; gotoxy(25,2);printf(the lenth: ); for(i=0;iLON;i+) gotoxy(26,3+i); printf(%2d,HashListi+30.si); ; gotoxy(37,2);
15、printf(spell: ); for(i=0;iLON;i+) gotoxy(38,i+3); printf(%s,HashListi+30.py); ; gotoxy(50,2);printf(H(key):); for(i=0;iLON;i+) gotoxy(51,i+3); printf(%2d,(HashListi+30.k)%M); ; average=0; for (i=0;i45) system(cls); if (LONHASH_LEN-45)LON=HASH_LEN-45; gotoxy(1,1);printf(HashTable: ); gotoxy(1,2);prin
16、tf(address: ); for(i=0;iLON;i+) gotoxy(1,i+3); printf(%-3d,i+45); ; gotoxy(9,2);printf(the H(key) : ); for(i=0;iLON;i+) gotoxy(10,i+3); printf(%-6d,HashListi+45.k); ; gotoxy(25,2);printf(the lenth: ); for(i=0;iLON;i+) gotoxy(26,3+i); printf(%2d,HashListi+45.si); ; gotoxy(37,2);printf(spell: ); for(i
17、=0;iLON;i+) gotoxy(38,i+3); printf(%s,HashListi+45.py); ; gotoxy(50,2);printf(H(key):); for(i=0;iLON;i+) gotoxy(51,i+3); printf(%2d,(HashListi+45.k)%M); ; average=0; for (i=0;iHASH_LEN;i+) average=average+HashListi.si; average=average/NAME_NO; gotoxy(10,23); printf(ASL:ASL(%d)=%f,NAME_NO,average); g
18、otoxy(20,24); printf(any key to pass! ); getch(); ;/*-主函数-*/void main() printf(n-build hash and reserach-); InitNameList(); CreateHashList (); while(1) char ch1; printf(nn); printf( 1. hashn); printf( 2. researchn); printf( 3. exitn); err: scanf(%c,&ch1); if (ch1=1) dhash(); else if (ch1=2) FindList
19、(); else if (ch1=3) return; else printf(nplese inter ); goto err; 四、调试分析测试用的30个人名已随着哈希表的建立一并输入，所以无需再输入人名。通过“清屏”使得显示时屏幕实现滚动，方便又快捷。哈希表显示采用对应坐标方法，这样容易排版。由于我用的是TC，此软件无法编译汉字，所以只能使用英文。五、测试结果1：演示程序，进入主界面2：输入1，进入哈希表显示界面，地址0163：按下任意键，进入哈希表的下一页，地址15314：按下任意键，进入哈希表下一页，地址30465：按下任意键，进入哈希表最后一页，地址45496：在主界面输入2，进入
20、查找人名7：查找一没有冲突的人名8：查找一存在冲突的人名六、课程设计小结：通过这一周的课程设计，加深了我对数据结构这门课程所学内容的进一步的理解与掌握；同时，通过对哈希表的设计，使得我将计算机课程所学知识与实际问题很好地相联接在了一起。在这次课程设计中，培养了我开发一个中小型程序的能力。这次的哈希表课程设计中，我为了简化代码，使30个人名为自己事先输入，省去了输入名字，再建立哈希表的功能，但尽管如此，总的代码还是很长，主要是哈希表我采用的是坐标输出显示的方法，那部分代码繁琐了了些，但是显示出来却是方便而又快捷，直接清屏滚动显示哈希表，否则可能50个地址要一个一个显示，不利于总的概览。但是其显示
21、和查找功能都得到了实现，而且哈希表中最重要的冲突问题也得到了解决。这次设计使我更清晰的了解哈希表的建立与实现，让我了解了一种快速而又便捷的查找方式。课程设计能让我们受益良多的，它能让我们建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验。同时，充分弥补了课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助从全局角度把握课程体系，并且可以将理论与实际联系。在课程设计的过程中我遇到了许多课外的知识，这便促使我去查阅更多的课外资料来充实自己的内容，同时学会在面对困难时要耐心得分析它细心得解决它以及通过合作更完美得深入了解剖析它以便得到提高。细心、耐心、求知，是我这次课程设计最大的收获。
