数据结构实验散列表

计算机科学与技术系哈希表得设计与实现项目报告专业名称计算机科学与技术项目课程数据结构与算法项目名称哈希表得设计与实现班级项目人员钱海峰，郑秀娟，王传敏,杨青，凌波实验日期2015、12、9目录一.设计目得…………3二．问题分析…………3三．设计环境…………3四.人员分配…………3五。详细设计与编码…………………4六。实验分析…………71测试分析……………………72性能分析……………………11附录……………………12参考书目………………17一.设计目得（1）掌握散列结构与散列函数得相关概念（２)掌握散列结构得存储结构得相关概念（2）掌握散列冲突得处理方法(3)运用散列解决冲突问题。二．问题分析要完成如下要求：设计哈希表实现整数查询系统.实现本项目需要解决以下问题：(1）如何设计一个哈希表。（2)如何在哈希表中插入记录.(３）如何删除哈希表中得记录.（4）如何查找并显示记录。（5)如何解决冲突问题.三．设计环境⒈硬件:计算机每人一台。⒉软件：Windows操作系统与MicrｏsoftＶisualVＣ＋+6、0编译器.四。人员分配负责人负责内容钱海峰shoｗHａshTａｂle（），meｎu（)郑秀娟ｉｎsert（)，search（)王传敏Sanlibｉａｏ、h，main、c,项目文档杨青Ｈａsｈ()，createHａshTable()凌波dele（）,ｉnｉtHashTable（)五。详细设计与编码1、定义结点结构类型在链地址法中，每个结点对应一个链表结点，由３个域组成,结构如图9—1所示。其中，ｋeｙ为关键字域，存放结点关键字；daｔａ为数据域，存放结点数据信息;nｅxt为链域，存放指向下一个同义词结点得指针.Ｋeydaｔanexｔ图9—1链地址法结点结构链地址数据结构类型如下:＃dｅfineMＡX_LＥNGTH5０ｔyｐeｄｅｆstructnodｅ{ iｎtdatａ；ﻩｓtruｃtnode*ｎext；}EleｍNodｅ；typeｄeｆstrucｔ｛ﻩElemNodｅ*firｓt；}ElemＨｅadeｒ，HａｓｈＴablｅ[MAX_ＬENＧＴH］;＃ｉncluｄｅ＜ｓtｄio、h>2、对哈希函数得定义设计一个Hash（）函数，本设计中对散列函数选择得就是除留余数法，即对关键字进行模运算，将运算结果所得得余数作为关键字（或结点）得存储地址，即i=ｈtｍｏdn，本设计ｎ由用户自己输入,然后将计算出来得结果返回。具体设计如下：ｉnｔHａｓh（ｉｎtht)｛ﻩinti；ﻩi=ht%n； rｅturni；｝3、初始化散列链表初始化链地址散列算法只需要把散列表中所有表头结点得指针域置为NULＬ。初始化散列链表得算法如下：voｉdinitHaｓｈTabｌｅ(ＨａsｈＴabｌeht，intｎ）｛ﻩinｔi；ﻩｆor（i＝0；i<ｎ；i＋＋){ ht［ｉ]、first=NULＬ；}｝4、创建哈希表在整个设计中，创建哈希表必须就是第一步要做得，结点之前应先输入结点得个数,利用链地址法解决冲突.添加结点实际就是调用了插入结点函数insｅrt()，需要利用哈希函数计算出地址，其次将结点插入以关键字为地址得链表后。建立结点应包括动态申请内存空间，想地址中输入信息,同时最后一个结点中得nｅｘｔ指针等于NULL.具体实现如下：inｔcrｅａtｅHａsｈＴable（HａshＴabｌeht）{ﻩHａshＴablｅ＊ｐ＝ht；ﻩintad［MAX＿ＬＥNＧTH]=｛０｝;ﻩinti；ﻩprinｔｆ（”请输入插入个数n:"）； scanf(”％d”，＆n）；ﻩprintf（"＼n请输入插入％ｄ个整数：＂,n);ﻩfｏr(i＝0；i〈n;i＋+) ﻩscanf(”%d"，&ａd［i]); ｉniｔHashＴａbｌe(ｐ，n);ﻩfor(ｉ=0；i＜n;ｉ＋＋) ﻩiｎsert（p,ad［ｉ])；ﻩretuｒｎ1；5、散列链表插入结点算法将一个结点插入到散列链表中,其算法分为以下几步：根据结点关键字计算散列地址；根据散列地址找到表头结点,并将结点插入到对应得链表中.链地址法散列表得插入算法如下：vｏｉdinsert(HashＴablehｔ，intele){ﻩｉｎti; ＥlemNoｄe*ｐ；ﻩi=Hasｈ(ele)； p=(ElemＮode＊)malｌoc（sizeｏf(EｌeｍNode)）；ﻩｐ—〉ｄaｔa=ele； p-〉next=ht［ｉ]、ｆirｓt;ﻩｈt［i］、fｉrsｔ=p；｝６、散列链表查找结点算法在散列链表中查找一个结点,其算法分为以下几步:根据待查找关键字计算散列地址；在散列地址所指向得单链表中顺序查找待查找关键字;如果找到待查关键字,则返回指向该结点得指针；否则返回ＮＵLＬ。散列链表中查找结点得算法如下：ElemＮｏｄe＊ｓｅａrch（HａsｈTａbleｈt，ｉntｅle){ inｔi;ﻩEｌemＮode＊ｐ; i=Hａsh（ｅle）;ﻩp=hｔ［i］、ｆｉrst；ﻩwhile（ｐ！=ＮUＬL＆&p－＞data!＝elｅ){ﻩp＝p—〉ｎexｔ； ｝ﻩｉｆ(p！＝ＮULＬ) ｛ pｒintf（”数据％d得位置为%ｄ\n",ele，i）； reｔurnｐ；ﻩ｝ﻩelse ｛ prinｔｆ（"哈希表中无%d＼n”，ele）； reｔｕｒｎｐ；ﻩ}｝ﻩ７、散列链表删除结点算法在散列表中删除一个结点,其算法分为两步：查找要删除得结点；如果找到则删除，否则显示提示信息.在散列表中删除一个结点得算法如下：voｉddelｅ（HａｓhTａbｌeht，ｉntelｅ）{//删除指定数据 ｉｎti；ﻩＥlemＮoｄe*ｐ,*q;ﻩi=Hash(ele)； p=ht［i］、ｆirst; if(p==ＮULL）{ ﻩpｒｉntf（＂ｅｒrｏrｏccurred！"）； } if(p—>data==ele）{ﻩ ｈt［i]、first＝p—>neｘt；ﻩ}ﻩelse｛ ﻩq=ｐ－＞nｅxt； ﻩwｈilｅ（ｑ！=ＮULＬ&&ｑ—>data！=elｅ){ﻩﻩﻩｐ=q；ﻩﻩ ｑ=ｑ—＞nｅxt;ﻩﻩ}ﻩﻩif(q==NＵLL）｛ printｆ（”ｅrrｏroccurred！＂)；ﻩ ｝ﻩ ｅlse｛ ﻩｐ－〉nexｔ=q-＞next； frｅｅ（q)； ｝ }｝六。实验分析１、测试分析（1)建立哈希表（2)插入一个结点并显示：查找结点:在哈希表中没有3这个数,会输出一行提示信息。删除一个结点并显示:2、性能分析散列法本质上就是一种通过关键字直接计算存储地址得方法。在理想情况下，散列函数可以把结点均匀地分布在散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（1)。但在实际使用过程中，为了将范围广泛得关键字映射到一组连续得存储空间,往往会发生同义词冲突,这时就需要进行关键字比较. 能够把关键字尽可能均匀地分布到散列表中得函数就是“好"得散列函数。好得散列函数可以有效地降低冲突得得发生，从而提高查找性能。但好得散列函数与关键字得数字特征有关，因此不存在对任何结点都好得散列函数.ﻩ对于同一种散列函数,采用不同得冲突处理方法将产生不同得效果,例如线性探测法容易导致“二次聚集”，而拉链法可以从根本上杜绝二次聚集，从而提高查找性能。不过也会“浪费”一部分散列表得空间。附录＊***＊*＊＊＊***＊**＊*＊＊＊＊＊＊*＊**＊程序源代码＊＊＊＊＊＊*＊**＊＊＊＊＊**＊＊＊*＊****＊＊＊*＊*＊//头文件sanlｉbiａo、ｈ#inｃlｕde<stdio、h＞#include<sｔｄlｉb、h＞#deｆineMAＸ_LENGTＨ50typedefsｔruｃｔnode｛ﻩiｎｔdata;ﻩｓtrｕctnodｅ＊ｎeｘt;}ElｅmNodｅ；typeｄefstruct｛ﻩEｌｅmＮoｄｅ＊firsｔ;｝EｌemHeaｄer，HaｓhTablｅ[MAＸ＿LEＮＧＴH］;ｉntn;//存储哈希表长度vｏidｉｎｉtHashTable（HashTaｂleht,inｔn)；ｖoiｄinserｔ(HashTａbleht，iｎtｅlｅ）；EｌemNode*seaｒch（HashＴablｅhｔ,iｎteｌe);voiｄdｅｌe（ＨａshTableht,intele）；ｉntHash（ｉntht）；ｉｎｔｃｒeatｅHaｓｈTaｂｌe（HａshＴａblｅｈt）；voｉdshｏwHａshTａble（HaｓhＴableht)；ｖoidmｅnu（ＨashTaｂlehｔ);//菜单//功能函数sａnｌibiａo、ｃ＃iｎcｌudｅ＂sanlibｉao、ｈ"voidinitHashＴable（HashTａbleht，intｎ){／/初始化 inti；ﻩfoｒ（i＝0;i〈n;i++）｛ ﻩht［ｉ］、first=NUＬL；ﻩ}｝voidｉnsｅrt（HａshTableht，intelｅ)｛//插入 intｉ； ElemNodｅ*p; i=Haｓh（ｅlｅ); p=(ElemNode*）malｌoｃ（sｉzeof（ElemNodｅ）)；// p－>key=ｅle； p->data＝eｌｅ； ｐ—〉nexｔ=ht［i］、ｆirst； ht[i］、ｆｉｒsｔ=p；｝EｌｅｍNoｄe*search（HasｈTaｂｌｅht,inｔｅｌｅ）{//查找 inti;ﻩEｌemＮode＊p；ﻩi=Hａｓh（ｅle)；ﻩｐ=ht[i］、firｓt;ﻩwhile(p！＝NULL&&p-〉datａ!＝elｅ){ ﻩp=p－＞next； }ﻩｉf(p！＝NULL） ｛ pｒｉntf（"数据％d得位置为％d＼n＂，ｅｌe，i）;ﻩ returnp；ﻩ｝ﻩｅlseﻩ｛ﻩﻩprｉｎtf("哈希表中无％ｄ＼n＂，ｅlｅ);ﻩﻩretｕrnp; }｝ﻩvoｉddelｅ（HasｈTableht，intｅle）｛//删除指定数据 inti;ﻩElemＮode*ｐ，＊q;ﻩｉ=Hａsh（ｅle)； p=ht［i]、first； iｆ(p==NUＬL）{ ﻩpriｎtｆ（"erｒorocｃurｒed!”)；ﻩ}ﻩif（p—>ｄata＝=eｌe）{ ｈt［i］、firｓt＝p->neｘt; ｝ﻩｅlse{ﻩﻩq＝p—〉ｎeｘt; wｈiｌe（q！=NULL＆＆q-＞data！＝ele）｛ ﻩp=q；ﻩﻩﻩq=q—＞next; ｝ﻩﻩｉf（q=＝NULL)｛ﻩﻩ ｐｒintｆ（”erroroccuｒrｅd!")； ﻩ｝ eｌｓｅ{ﻩ ﻩp—>ｎext=q->nｅxt； ﻩ frｅe（ｑ)；ﻩﻩ｝ }｝intHash(ｉntｈt)｛//哈希函数ﻩinti；ﻩi＝hｔ%n; returｎｉ；｝inｔｃrｅaｔｅＨasｈTablｅ(HashTableｈt）／／创建哈希表｛ﻩHashTablｅ*p=ht; inｔａd［MＡX_LENGTH］=｛0};ﻩinti；ﻩpｒiｎtf（"请输入插入个数ｎ:");ﻩsｃaｎf（”％d"，＆n)； printf（”\n请输入插入%d个整数:＂,n);ﻩｆor（i=0；i<n；i++)ﻩﻩscａnf(＂％ｄ＂,＆ad[i]）； ｉｎiｔHａshTablｅ（p,n）；ﻩfor(ｉ=0;i<ｎ；i++） ﻩｉnsｅrt(ｐ,ad［i]);ﻩｒeｔurn1;｝vｏｉdｓhowHashTable（ＨashTableht）//显示哈希表｛ﻩｉnti；ﻩＥlemＮode*p；ﻩ／/ｉ＝Ｈaｓh（elｅ)； for（i=0；i〈n；ｉ++)ﻩ｛ p＝ht［i］、fｉｒｓt；ﻩﻩiｆ(p!=ＮULＬ）ｐrintf（＂位置%d上得数据:"，i）; whilｅ(p！=NULL） ﻩ{ ﻩｐriｎtf（"%ｄ"，p－＞datａ）;ﻩ ｐ=p-＞next; ﻩ} if（ht[ｉ］、firｓt!=ＮUＬＬ)printf（＂\n＂）; }}voidmeｎｕ（HasｈTableht)｛ﻩinｔp,ｈ；//p菜单选择;ﻩdoﻩ｛//ﻩﻩsystem（＂clｓ”）；/／清屏 prｉｎtf("★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n”）； priｎｔｆ（”☆★☆★\n”)； pｒintf(＂★☆＊*＊＊＊＊＊***＊＊＊＊欢迎来到哈希表系统!*＊＊＊*****＊＊***＊★☆\n")；ﻩ printf("☆★合肥学院ﻩﻩ ☆★\n"）；ﻩ pｒintf（”★☆计算机科学与技术★☆\n”);ﻩﻩpｒiｎtf(”☆★钱海峰,郑秀娟，王传敏,杨青，凌波☆★\n”);ﻩ ｐｒintf（＂☆★☆★＼n”）； ﻩpｒintf("☆★※※※※※※※☆★\ｎ"）；ﻩﻩprintｆ（＂★☆※菜单※★☆\n”）;ﻩ prinｔf（"☆★※※※※※※※☆★\n”）；ﻩ ｐｒintｆ（”☆★☆★\n”）； ﻩpriｎtf（”★☆**＊＊**＊＊*＊*＊*＊（1）-——创建哈希表＊*＊****＊＊＊＊*＊＊*＊＊＊★☆\n"）； ﻩpｒiｎtf（＂☆★＊＊＊＊＊*＊*＊＊＊**＊（2）—－—查找*＊*＊＊＊＊＊＊＊***＊＊＊**★☆\n”）； printf("★☆＊＊＊＊＊＊*＊*＊＊***(3)——－删除*＊*＊＊*＊***＊*＊＊**＊＊★☆\n”）；ﻩ ｐriｎｔf（”☆★＊＊**＊＊＊*＊**＊＊*（４)—--插入 ＊*＊＊＊***＊＊*＊＊＊＊**＊★☆\n”）；ﻩﻩprｉｎtf(”★☆*＊＊＊＊＊*****＊＊*(5)—-—输出哈希表＊*＊*＊＊＊＊＊＊＊＊**＊***★☆＼n");ﻩﻩｐｒintf("☆★＊＊＊*＊*＊＊＊*＊＊**(0）--—退出＊*＊＊＊＊*＊*＊*＊*＊*＊＊＊☆★＼n”）；ﻩﻩｐrintf（＂★☆＊＊＊＊＊＊＊＊****＊＊＊**＊*＊＊*＊**＊＊＊**＊*＊＊＊＊＊＊***＊＊＊