数据结构课程设计哈希表的设计与实现.doc

课程名称：数据结构 XXXXXXXX本科学生课程设计（论文）题 目 哈希表的设计与实现 姓 名 XXX 学 号 XXXXXXXXXXXX 学 部 计算机科学与技术 专业、年级 计算机科学与技术 大二 指 导 教 师 XX 2010 年 11月 28日摘 要随着信息技术的发展，关于各种程序中的数据结构也是层出不穷，对于项目某一方面的计算或者是某一方面的研究，出现了专门的数据结构，哈希表就是其中之一，哈希表作为另类的一种数据结构，其作用也是区别于其它同类的数据结构的，它是由两部分组成的：键(key)和值，通过键可以迅速的查找到你需要的值。常见的构造哈希函数的方法有直接定址法 除留余数法 平方取中法 数字分析法等。一般创建哈希表时可能会出现很多的冲突，常用的处理冲突的方法为开放定址法 再哈希法 链地址法 建立一个公共溢出区。关键词: 数据结构；哈希表；键(key)；目 录第1章前言与系统实现21.1前言21.2系统实现31.2.1 开发环境31.2.2 Visual C+环境的安装3第2章 系统功能分析42.1 系统功能需求分析42.2 任务定义4第3章 总体设计53.1系统数据结构53.2主要算法流程图63.2.1 以姓名为关键字的CreateHashList()函数流程图63.2.2 哈希表查找算法流程图73.2.3主程序流程图8第4章 详细设计和编码94.1节点的建立94.2 对哈希函数的定义94.3 创建哈希表算法、代码如下所示:104.3.1 算法104.3.2代码104.4哈希查找114.5显示哈希表144.6主菜单设计164.7 主函数设计16第5章 程序运行测试195.1程序主界面195.2哈希表初始化195.3按姓名查找记录215.4显示哈希表全部记录22总结23参考文献24 第1章 前言与系统实现1.1前言在信息化时代的今天，计算机技术已经是发展到一个很可观的地步了，特别是面向窗口的操作系统的出现，使得程序设计更加的容易了。在过去计算机内存容量小，CPU计算速度慢，关于程序设计中的数据结构也因此提出来很多的关于解决这方面的问题。哈希表就是其中之一，哈希表是一个由关键字与值组成的特殊的一种数据结构。它的出现主要是为了解决在结构中查找记录时需要进行一系列和关键字的比较,这一类查找方法是建立在“比较”的基础上的，在顺序等的查找中，查找的效率是依赖于查找过程中所比较的次数。理想的情况是希望不经过任何的比较一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时只要根据这个对应关系找到给定的值的像。若结构中存在关键字和该值相等的记录，则所要查找的数就必定就是这个所查找到的记录。哈希函数是建立哈希表的一个重要的成员，它的构造方法分为以下几种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。本程序中主要用的是除余取留法,除留取余法主要是取关键字被某个不大于哈希表表长m的数p出后所得余数为哈希地址即:H(key)=key MOD p, p<=m，这是一种最简单，也是一种最常用的构造函数的方法，它不仅可以对关键字直接取模，也可在折叠、平方中等运算之后取模。 在哈希表的建立中，很容易出现同义词，这些同义词的出现也导致了建立哈希表时冲突的出现，如果不解决这些冲突那么建立好的哈希表与预料的哈希表不同。关于处理冲突的方法主要有：开放定址法、再哈希法、链地址法。本程序中主要用的就是链地址法莱解决冲突的。1.2系统实现本程序是在Vc+6.0环境下编写 测试运行的。1.2.1 开发环境表1-1列出了系统硬件配置，表6-2列出了系统软件配置。设备名称配置CPUE1200 2.6GHz内存128MB硬盘40GB 表1.1 组装台式机配置设备名称版本操作系统Windows XP sp3开发环境Visual Studio C+ 6.0设计工具VC+表1.2 软件环境1.2.2 Visual C+环境的安装在计算机中安装Visual C+安装程序，Visual C+应用程序的开发主要有两种模式，一种是WIN API方式，另一种则是MFC方式，传统的WIN API开发方式比较繁琐，而MFC则是对WIN API再次封装，所以MFC相对于WIN API开发更具备效率优势。本软件中因为程序主要是为了实现某个算法所以这里没有用到MFC。第2章 系统功能分析2.1 系统功能需求分析实现本程序需要解决以下几个问题：1. 设计一个结点使该结点包括电话号码、用户名、QQ等结点信息。2. 利用用户名为关键字建立哈希表，哈希函数用除留余数法构照。3. 利用链表法处理冲突问题。4. 实现用哈希法查找并显示给定姓名的记录。5. 显示哈希表中的全部记录。2.2 任务定义由功能需求分析知，本设计主要要求以用户名为关键字建立哈希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。根据题目的要求采用链地址法散列算法。当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由六个域组成，而由于该程序需要用用户名为关键字建立哈希表，所以该链表结点它是char strName20;char strClass20;char strPhone11;char strqq10; int num; char strAddress 六个数据域和struct Name *next 一个地址域组成。构造哈希表的函数主要是用除留取余法来构造哈希函数的。冲突的解决采用链地址法，具体的实现思想是，所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。 第3章 总体设计3.1系统数据结构本设计涉及到的数据结构为：哈希表。程序中建立了两个结构体，要求输入电话号码、用户名、QQ、地址、四个信息，给struct Name结构体变量，在创建哈希表时哈希函数用除留余数法构照，并把struct Name结构体中的数据赋值给哈希表结构体。在链地址法中，每个结点对应一个链表结点，它由六个域组成，链地址法结点结构如表：strName20numstrAddress30strPhone11strClass20Nqqnext表 3.1其中哈希表是以用户名为关键字 next指针是用来指向下一个结点的地址。具体的存储结构如下图所示: 图3.1数据结构存储图3.2主要算法流程图3.2.1 以姓名为关键字的CreateHashList()函数流程图 建立第一个结点开始结束初始化结构体指针域为NULL定义i=0i<30int adr=(NameListi.num)%M;HashListadr.next！=NULLi+解决冲突结点的建立struct Hlist *q;pName *p,*m;q指向所要插入结点的地址，m指向所要插入结点指针的下一地址查找该地址的最后一个地址图 3.23.2.2 哈希表查找算法流程图 查找到的数据结束开始输出查找到的信息定义数组name 整型变量adr =0,s=0,r=0 r<20adr=s%M;输入查找姓名s+=namer;r+HashListadr.next!=NULL无该记录判断记录的关键字与s相等HashListadr.next)->next=NULL地址中单链表的循环遍历查找图 3.33.2.3主程序流程图Main ()定义int变量i,f=0InitNameList(); Menu（）主菜单开始无限循环输入选择1-4选择1选择2选择3选择4defaultCreateHashList(); CreateHashList();f=1f=1f=1哈希表未初始化哈希表未初始化Display();SearchList();return 0选择错误，请从新输入结束图 3.4第4章 详细设计和编码4.1节点的建立定义结构体如下所示:typedef struct Namechar strName20;/姓名 char strClass20;/班级char strPhone11;/手机号码char strAddress30;/地址char Nqq10;/QQint num;/关键字struct Name *next;pName;pName NameListHASH_LEN;pName k;struct HlistpName *next;HashListHASH_LEN;4.2 对哈希函数的定义本程序设计一个hash()函数，本设计中按照题意要求知对散列函数选择的是除留余数法，即对关键字进行模运算，将计算结果所得的余数作为关键字（或结点）的存储地址，即H(key)=key mod p,在程序中p取的值为范围内的最大的素数，以用户名为关键字建立哈希函数CreateHash()，利用强制类型转换将用户名的每一个字母的ASCLL码值相加并且除以范围内最大的素数，将计算出来的数作为该结点的地址赋给adr。然后通过以下几种方式就可以完成哈希表程序的设计了。4.3 创建哈希表算法、代码如下所示:4.3.1 算法建立结点，并添加结点，利用链地址法解决冲突。建立结点应包括动态申请内存空间。向结点中输入信息。同时将结点中的next指针等于null。添加结点，首先需要利用哈希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后。4.3.2代码void CreateHashList()int i; for(i=0; i<HASH_LEN; i+)HashListi.next=NULL;for(i=0; i<2; i+)struct Hlist *q;pName *p,*m;int adr=(NameListi.num)%M;/哈希函数if(HashListadr.next=NULL)/表明不冲突 HashListadr.next=&NameListi;else/表明冲突q=&HashListadr;m=q->next;while(m->next!=NULL) m=m->next;p=(pName *)malloc(sizeof(pName); strcpy(p->strName,NameListi.strName);strcpy(p->strPhone, NameListi.strPhone);strcpy(p->strAddress,NameListi.strAddress);strcpy(p->Nqq, NameListi.Nqq);p->num=NameListi.num; m->next=p;/单链表向后指4.4哈希查找想要实现查找功能，需要一个查找函数，以用户名为关键字来实现查找，首先，需要利用hash函数来计算出地址。再通过比对，如果该地址中的用户名拼音字符相加的num与查找的相同则输出该结点的所有信息，否则输出“无此记录”。具体实现代码如下所示:void SearchList()system("cls");char *f;printf("nn请输入你要查找姓名（拼音）");/输入姓名char name20;scanf("%s",name);f=name;int s=0, r;for(r=0; *(f+r)!='0' r+)/求出姓名的拼音所对应的整数也就是关键字s+=(int)*(f+r);/利用字符与整数的自动转换相加字符的ASCII码int adr=s%M;/使用哈希函数if(HashListadr.next=NULL)/通过指针的指向判断一个单链表中是否存在要查找的数printf("无该记录");elseif(HashListadr.next)->next=NULL) if(HashListadr.next)->num=s) int i=1; printf(“n姓名:%s”, (HashListadr.next)->strName); printf(“班级:%s”, (HashListadr.next)->strClass); printf(“电话:%s”, (HashListadr.next)->strPhone); printf(“QQ:%s”, HashListadr.next)->Nqq); printf(“地址: %sn”, (HashListadr.next)->strAddress); printf(“关键字:%d”, (HashListadr.next)->num); printf(“查找长度:%d”, i);else pName *m; int i=1; m=HashListadr.next; while(m->next!=NULL)/循环该单链表查找出你所要查找的数据并把他们输出 if(m->num=s) Printf(“n姓名:%s”, m->strName); Printf(“班级:%s”, m->strClass); Printf(“电话:%s”, m->strPhone); Printf(“QQ：%s”, m->Nqq);Printf(“地址: %s”, m->strAddress);Printf(“关键字:%d”, m->num); printf("查找长度:%d", i); break; m=m->next; i+;4.5显示哈希表 通过姓名关键字，循环查找有值的下标并输出来,具体设计代码如下：void Display() system("cls");int i, s, j, adr, n=0;char *f;struct Hlist *m;struct Name *k;char name20;printf("nn下标地址t关键字tH(key)t拼音 班级 QQ 地址 电话 n"); /显示的格式for(i=0; i<2; i+)s=0;strcpy(name,NameListi.strName);f=name;for(j=0; *(f+j)!='0' j+) s+=(int)*(f+j);adr=s%M;m=&HashListadr;if(m->next!=NULL) k=m->next; n+=1; while(k->next!=NULL) printf("下标地址:%d",i); printf("t%d ",k->num); printf("t%d ",(k->num)%M); printf("t %s ",k->strName); printf(" %s",k->strClass);printf(" %s",k->Nqq);printf(" %s",k->strAddress);printf(" %s",k->strPhone); printf("n"); k=k->next; printf("下标地址:%d",i);printf("t%d ",k->num); printf("t%d ",(k->num)%M); printf("t %s ",k->strName); printf(" %s",k->strClass); printf(" %s",k->Nqq); printf(" %s",k->strAddress); printf(" %s",k->strPhone); printf("n"); 4.6主菜单设计 根据题目中的要求我们只要写出哈希表的初始化 查找 显示三个功能，代码如下所示:void Menu() printf("n-哈希表的建立和查找操作-"); printf("nn"); printf(" 1. 哈希表初始化n"); printf(" 2. 显示哈希表n"); printf(" 3. 查找n"); printf(" 4. 退出n");4.7 主函数设计 主函数是一个软件运行的入口，其通过调用自定义函数来完成相应的功能,其实现代码如下所示:int main(int argc, char *argv) int i,f=0; while(1) Menu(); scanf("%d",&i); switch(i) case 1: InitNameList(); CreateHashList(); f=1;break; case 2: if(f=1) Display(); break; else printf("哈希表未初始化请先初始化再操作"); break; case 3: if(f=1) SearchList(); elseprintf("哈希表未初始化请先初始化再操作"); break; case 4:return 0; default:printf("请输入正确的选项"); break; 第5章 程序运行测试5.1程序主界面图5.1 程序主界面5.2哈希表初始化 测试数据(正确): 姓名:kaluo班级:305电话:123456789 地址:长沙涉外 QQ:282265478 姓名:tianxia  班级:306 电话:987654321 地址:长沙理工 QQ:974562228 姓名:xiantu  班级:3076 电话:987654322 地址:长沙学院 QQ:974562222 测试数据(错误): 姓名:张三(否拼音)  班级:3077 电话:987654322 地址:长沙学院 QQ:974562222姓名:李四(否拼音)  班级:3078电话:987654322 地址:长沙学院 QQ:974562222图5.2 哈希表正确初始化图5.3 哈希表的错误初始化图5.4 哈希表初始化5.3按姓名查找记录图5.5 输入查找条件 图5.6 查找结果 5.4显示哈希表全部记录图5.7 显示表中全部记录总结1、语法错误及修改：程序是分块写的,调试时可以使用分步调试的方式进行,以便能查找看程序是在哪出错了。程序中使用了链表结构和链地址法解决冲突的问题，以姓名为关键字的哈希表中要注意涉及ASCLL码的类型转换。2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指针指向。3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（n）=1。但在实际使用过程中，为了将范围广泛的关键字映射到一组连续的存储空间，往往会发生同义词冲突，这时在查找过程中就需要进行关键字比较。因此散列法的查找性能取决于3个因素：散列函数、冲突处理方法和填充因子。采用链地址法，可以从根本上杜绝“二次聚集”的发生，从而提高散列表的均匀度，提高查找性能，不过也会“浪费”一部分散列表的空间。当散列函数和冲突处理办法固定时，散列法的查找性能就取决于散列表的填充因子。填充因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然，a越小则发生冲突的机会就越小；反之，a越大冲突的机会就越大，查找的性能也就越低。哈希表链地址法查找成功的平均查找长度SNc=1+a/2。链地址法查找不成功的平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表的平均查找长度是填充因子的函数，和散列表的长度没有关系，因此在实际应用中，我们应该选择一个适当的填充因子，以便把平均查找长度控制在一个尽量小的范围内。参考文献1（美）佛罗赞(Forouzan).计算机科学导论M.北京：机械工业出版社,2004.2172192 严蔚敏 吴伟民.数据结构M.北京：清华大学出版社,1997.2512593 王昆仑 李红.数据结构与算法M.北京：中国铁道出版社,2007.64 李春葆.数据结构题集M.北京：清华大学出版社，1992.25 武马群 缪春池 吕峻闽.C语言程序设计.北京：北京工业大学出版社,2006.5