第1章 需求分析 ……………………………………………………
第2章 概要设计 ……………………………………………………
第3章 详细设计 ……………………………………………………
第4章 调试分析……………………………………..........................
第5章 核心源程序清单和执行结果……………………………....
第6章 设计体会………………………………………….................
第7章 附录…………………………………………………...........
第1章 需求分析
1.问题描述：针对某个集体（比如你所在的班级）中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序；
2.人名为中国人姓名的汉语拼音，人名有30个，平均查找长度的上限为2；
3.用伪随机探测再散列法处理冲突；
4.输入为所要查询的人姓名（拼音）；输出为该关键字的查找信息；
5.测试数据：
输入：lihaojie
输出：姓名：lihaojie 关键字：837 查找长度：1
输入：wangzhou
输出：姓名：wangzhou 关键字： 查找长度：3
输入：d
输出：显示哈希表
6.本程序用C++语言编写，在vc++6.0环境下运行。
第2章 概要设计
2.1算法思想：
1 定义：
哈希表是为了便于快速搜索而组织的键/值组合的集合。Hash Table是一种数组，可以用任意简单变量值来访问其元素，这种数组叫哈希表。
2 优点：
哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
3 基本原理：
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）存在一一对应的关系，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字为每一个元素“分类”。
4哈希表的不可避免冲突(collision)现象：
对不同的关键字可能得到同一个哈希地址 即key1≠key2，而f(key1)=f(key2)。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。用伪随机探测法。求下一个开放地址的公式为：Hi = (H(k)+di) MOD m
注意：Di=伪随机数序列；
2.2关于程序设计的基本操作：
1.对哈希表的操作
InitNameList()
操作结果：姓名（结构体数组）初始化
CreateHashList()
操作结果：建立哈希表
FindList()
操作结果：在哈希表中查找
Display()
操作结果：显示哈希表
2.主程序
int main()
{
初始化；
InitNameList()；
CreateHashList()；
do {
接受命令；
处理命令；
}while（“命令”=“退出”）；
return 0;
}
3.本程序包含的模块
}
1）初始化操作，结构体定义；
2）姓名结构体建立模块；
3）建立哈希表模块；
4）查找模块；
5）显示哈希表模块；
4）主程序模块
4 程序流程图
主程序
初始化姓名
建立哈希表
查找
显示哈希表表
第3章 详细设计
主要功能模块：
模块一：建立哈希表
void CreateHashList() //建立哈希表
{ int i;
for(i=0; i HashList[i].k=0; HashList[i].si=0; } for(i=0;i int adr=(NameList[i].k)%M; //哈希函数 int d=adr; if(HashList[adr].si==0) //如果不冲突 { HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1; } else //冲突 { do { d=(d+NameList[i].k%10+1)%M; //伪随机探测再散列法处理冲突 sum=sum+1; //查找次数加1 }while (HashList[d].k!=0); HashList[d].k=NameList[i].k; HashList[d].py=NameList[i].py; HashList[d].si=sum+1; } } } 模块二：查找 void FindList() //查找 { char name[20]={0}; int s0=0,r,sum=1,adr,d; printf("请输入姓名的拼音:"); scanf("%s",name); for(r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字) s0+=name[r]; adr=s0%M; //使用哈希函数 d=adr; if(HashList[adr].k==s0) //分3种情况进行判断 printf("\\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0); else if (HashList[adr].k==0) printf("无此记录!"); else { int g=0; do { d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突 sum=sum+1; if(HashList[d].k==0) { printf("无此记录! "); g=1; } if(HashList[d].k==s0) { printf("\\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum); g=1; } }while(g==0); } } 模块三：显示哈希表 void Display() // 显示哈希表 { int i; float average=0; printf("\\n地址\t关键字\t\搜索长度\tH(key)\ 姓名\n"); //显示的格式 for(i=0; i<50; i++) { printf("%d ",i); printf("\%d ",HashList[i].k); printf("\\%d ",HashList[i].si); printf("\\%d ",HashList[i].k%M); printf("\ %s ",HashList[i].py); printf("\\n"); } for(i=0;i average/=NAME_NO; printf("\\n平均查找长度：ASL(%d)=%f \\n",NAME_NO,average); } 第4章 调试分析 由于本程序的思路较简单，主要是对哈希表的建立，查找和输出，在写程序时最重要的是正确书写哈希函数和选择合适的处理冲突方法，可以有效减少查找长度，提高程序运行效率。 下面本人就针对哈希函数的选择以及冲突方法的选择做一下简单的论述： 4.1哈希函数的选择 本人设计了如下几种哈希函数： 1.利用人名首字母的ASCII值-97作为该人名的关键字，而后后建立哈希函数hash(k)=k 分析：利用此类哈希函数的优点是比较简单，可行而且易于想到，但是其也有比较明显的缺点，就是产生冲突的几率比较的大，因为可能有很多人的人名的首字母是相同的，因此此种方法要求建立的hash冲突比较完善实用。 2.将人名所有的字母的ASCII码值进行相加作为关键字，而后建立哈希函数hash(k)=k%m[m为其随机数] 分析：此类哈希函数的思想相对来说比较的复杂，利用所有字母的ASCII码值的相加作为其关键字，但是其有一个很好的优点，就是产生冲突的几率比较的少，从而可以有效的减少信息的查找长度。 3.去掉姓氏，利用人名的首字母的ASCII码值-97作为关键字，而后建立哈希函数 hash(k)=k 分析：这种hash函数的建立是根据第一种函数改进而来的，它弥补了以前的不足：即产生冲突的几率比较的大，但同时它又极大的增加了此程序的复杂度。增加了程序运行的时间。 4.去掉姓氏，将人名的所有字母的ASCII码值进行相加作为关键字，而后建立哈希函数hash(k)=k%m [m为其随机数] 分析：此种哈希函数综合了第二，第三种hash函数，它的思想比较复杂不易想到，但是其可以将hash地址冲突率减少到一个很低的概率。极大的提高查找的效率，但是由于程序的复杂度较大，所以它所需要的运行时间也是很大的。 4.2关于冲突处理的选择 本人设计了如下几种冲突方法： 1.针对于第一，第三种hash函数，本人认为可以利用双hash函数探测法来处 理冲突：即是略去第一个字母从下一个字母开始寻找关键字，建立hash函数，来处理冲突。 分析：此种冲突处理方法比较简单，而且的确可行性比较的高，但是由于hash函数的关系，此种冲突处理方法并不怎么使用。 2.针对于第二，第四种hash函数，本人认为可以利用伪随机数线性探测法来处 理冲突：即是利用公式(k%m+1)%m来处理冲突。 分析：此种冲突处理方法操作起来相对的比较麻烦，而且还需要一个随机数，但是其有一个比较好的优点，它的处理后的冲突率几乎为零，同时能有效的减少哈希表设计的长度。 第5章 核心源程序清单和执行结果 1.源程序代码： #include #include using namespace std; #define HASH_LENGTH 50 //哈希表的长度 #define M 47 //取余随机数 #define NAME_NO 30 //人名的个数 typedef struct { char *py; //名字的拼音 int k; //名字所对应的关键字 }NAME; NAME NameList[HASH_LENGTH]; //全局变量NAME typedef struct //哈希表 { char *py; //名字的拼音 int k; //拼音所对应的整数 int si; //查找长度 }HASH; HASH HashList[HASH_LENGTH]; //全局变量HASH /*姓名（结构体数组）初始化 */ void InitNameList() { char *f; int r,s0,i; for (i=0; i NameList[i].py = new char[]; NameList[i].py[0] = 0; } strcpy(NameList[0].py, "lihaojie"); strcpy(NameList[1].py, "zhaona"); strcpy(NameList[2].py, "shangqingfu"); strcpy(NameList[3].py, "changqiongfang"); strcpy(NameList[4].py, "liaobangyu"); strcpy(NameList[5].py, "fenghao"); strcpy(NameList[6].py, "huangtianyuan"); strcpy(NameList[7].py, "luxiwu"); strcpy(NameList[8].py, "huangxinglong"); strcpy(NameList[9].py, "jiangxiaojia"); strcpy(NameList[10].py, "guojie"); strcpy(NameList[11].py, "liyexiao"); strcpy(NameList[12].py, "lidaohui"); strcpy(NameList[13].py, "lijue"); strcpy(NameList[14].py, "lizhuoqun"); strcpy(NameList[15].py, "linfujun"); strcpy(NameList[16].py, "luobingbiao"); strcpy(NameList[17].py, "luokeqing"); strcpy(NameList[18].py, "nichao"); strcpy(NameList[19].py, "panhuafeng"); strcpy(NameList[20].py, "lixiaolong"); strcpy(NameList[21].py, "songzhanhui"); strcpy(NameList[22].py, "lichao"); strcpy(NameList[23].py, "wanghaofeng"); strcpy(NameList[24].py, "wangzhou"); strcpy(NameList[25].py, "wangqinde"); strcpy(NameList[26].py, "wangzejun"); strcpy(NameList[27].py, "wangkeke"); strcpy(NameList[28].py, "weixing"); strcpy(NameList[29].py, "wurenke"); for(i=0;i s0=0; f=NameList[i].py; for(r=0;*(f+r)!='\\0';r++) /* 方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/ s0=*(f+r)+s0; NameList[i].k=s0; } } /*建立哈希表*/ void CreateHashList() { int i; for(i=0; i HashList[i].py=new char[]; HashList[i].py[0] = 0; HashList[i].k=0; HashList[i].si=0; } for(i=0;i int sum=0; int adr=(NameList[i].k)%M; //哈希函数 int d=adr; if(HashList[adr].si==0) //如果不冲突 { HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1; } else //冲突 { while (HashList[d].k!=0) { d=(d+NameList[i].k%10+1)%M; //处理冲突 sum=sum+1; //查找次数加1 }; HashList[d].k=NameList[i].k; HashList[d].py=NameList[i].py; HashList[d].si=sum+1; } } } /*查找模块*/ void FindList() { string name; int s0=0,r,sum=1,adr,d; cout<<"请输入姓名的拼音:"< for(r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字) s0+=name[r]; adr=s0%M; //使用哈希函数 d=adr; if(HashList[adr].k==s0) //分3种情况进行判断 cout<<"姓名:"< cout<<"无此记录!"< { int g=0; while(g==0) { d=(d+s0%10+1)%M; //处理冲突 sum=sum+1; if(HashList[d].k==0) { cout<<"无此记录!"< } if(HashList[d].k==s0) { cout<<"姓名:"< } }; } } /* 显示哈希表 */ void Display() { int i; float average=0; cout<<"\\n地址\t关键字\t\搜索长度\tH(key)\ 姓名\n"; //显示的格式 for(i=0; i<50; i++) { cout< cout<<"\ "< } for(i=0;i average/=NAME_NO; cout<<"平均查找长度：ASL("< /*主函数，调用其他功能函数*/ int main() { char x; InitNameList(); CreateHashList (); cout<<"d. 显示哈希表 f. 查找 任意键退出 请选择："< { if(x=='d') { Display(); cout< else if(x=='f') { FindList(); cout< else break; } for (int i=0; i free(NameList[i].py); free(HashList[i].py); } return 0; } 2.运行结果展示： 主界面显示： 进行操作d,显示哈希表中的所有信息： 进行操作f,查找姓名：lihaojie 进行操作f,查找姓名：huangxinglong 进行操作f,查找姓名：lizhuoqun 进行操作f,查找姓名：wangzejun 第6章 设计体会 做了一个星期的程序设计终于做完了，在这次程序设计课中，我选择的课题是哈希表的设计。此次的课程设计真是让我获益匪浅，我突然发现写程序还挺有意思的。 由于上学期的C语言跟这学期的数据结构都算不上真正的懂，对于书上的稍微难点的知识就是是而非的，所以我只是对老师的程序理解，我也试着去改变了一些变量，自己也尽量多的去理解老师做程序的思路。当我第一天坐在那里的时候，我就不知道该做些什么，后来我只有下来自己看了一遍书来熟悉下以前学过的知识。 通过这次的程序设计，发现一个程序设计就是算法与数据结构的结合体，自己也开始对程序产生了前所未有的兴趣，以前偷工减料的学习也不可能一下子写出一个程序出来，于是我就认真看老师写的程序，发现我们看懂了一个程序其实不难，难的是对于一个程序的思想的理解，我们要掌握一个算法，不仅仅限于读懂，主要的是要理解老师的思路，学习老师的解决问题的方法。 这次试验中，我发现书本上的知识是一个基础，但是我基础都没掌握，更别说写出一个整整的程序了。自己在写程序的时候，也发现自己的知识太少了，特别是基础知识很多都是模模糊糊的一个概念，没有落实到真正的程序，所以自己写的时候也感到万分痛苦，基本上涉及一个知识我就会去看看书，对于书本上的知识没掌握好。在饭后闲暇时间我也总结了一下，自己以前上课也认真的听了，但是还是写不出来，这主要归结于自己的练习太少了，而且也总是半懂就不管了。在改写老师的程序中也出现了很多的问题，不断的修改就是不断的学习过程，当我们全身心的投入其中时，实际上是一件很有乐趣的事情。 对于以后的学习有了几点总结： 第1、熟记各种数据结构类型，定义、特点、基本运算（分开点一点也没多少东西，难度不大，但是基本）； 第2、第二、各种常用的排序算法，如冒泡排序、堆排序……，这些是必考的内容，分数不会少于20%； 第3、多做习题，看题型，针对题型来有选择复习；数据结构看上去很复杂，但你静下心来把书扫上几遍，分解各个知识点，这一下来，学数据结构的思路就会很清晰了。下载本文
