数据结构课程设计----线性开型寻址散列查找、插入、删除

1、山东大学软件学院数据结构课程设计报告设计题目：线性开型寻址散列查找、 插入、删除学号姓名年级专业班级学期11-12学年第二学期日期：2012年 月曰一、需求描述1.1散列表的研究意义：一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之 间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的 情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建 立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若

2、结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的 表为散列表(哈希表)。1.2散列表的定义散列(Hash ):根据记录的关键字的值来确定其存储地址。建立散列表，要在 记录的存储地址和它的关键字之间建立一个确定的对应关系。散列函数(Hash function):在记录的关键字和记录的存储地址之间建立的一种对应关系。散列函数是一种映像，是从关键字空间到存储地址空间的映像，可表示为Add (ai)=H(keyi)其中：ai是表中的一个记录，add(ai) 是ai的存储地址，keyi是ai的关键 字

3、。冲突(collisio n):不同的关键字经过散列函数计算后得到相同的地址，也就是说key1工key2，但是H(key1)=H(key2)的现象叫做冲突。具有相同函数值的几个关键字就称为该散列函数的同义词。一般情况下，冲突只能减少，并不 可避免。当冲突发生时，就要设定一种处理冲突的办法。散列表(Hash table ):应用散列函数和处理冲突的办法将一组关键字映像到一个有限的地址集上，并以关键字在地址集上的像作为记录在地址中的存储地 址。这种表叫散列表。1.3 散列表设计要求1. 结合课程学习内容和自己理解设计功能，准确演示算法思想。支持演示中间 过程。 能单步演示。2. 软件要易用。3.

4、软件可以对输入用例案例重复演示。4. 输入的用例数据可编辑。5. 软件要健壮，对非法的输入能给出合适的提示，不能直接导致软件崩溃。二、实现思想本程序以除留余数法作为散列函数， 线性探测法处理冲突， 用 java 实现相关 的建表，插入，查找，删除等操作。散列函数的构造方法1 直接 定址 法： 取关 键 字或 关键字 的 某个 线性 函数值为散 列地 址。即 H(key)=key 或 H(key) = a ?key + b ，其中 a 和 b 为常数(这种散列函数 叫做自身函数)2 数字分析法： 对关键字进行分析， 取关键字的若干位作为哈希地址， 通常适 于事先知道表中关键字的情况。3 平方取中

5、法：取关键字平方后的中间几位作为散列地址。4 折叠法： 如果关键字位数较多，可将关键字分割成位数相同的几部分，然 后取这几部分的叠加和去做散列地址。5 除留余数法：除留余数法：取关键字被某个不大于散列表表长m 的数 p 除后所得的余数为散列地址。即 H(key) = key MOD p, p=m 。不仅可以对关 键字直接取模， 也可在折叠、平方取中等运算之后取模。对 p 的选择很重要，一 般取素数或m,若p选的不好，容易产生同义词。处理冲突的方法中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：1. di=1,2,3,m-1 ，称线性探测再散列；2. di=1A2,(-

6、1)A2,2A2,(-2)A2,(3)A2, (k)A2,(k=m/2)称二次探测再散列；2.再散列法：Hi=RHi(key), i=1,2,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法 不易产生“聚集”，但增加了计算时间。三、数据结构设计1.创建了一个数组用于存储元素。数组长度可变public class Mainexte ndsHashTable barrel ht ;/创建数组 HTintLen gth ;Main( int D) super (D);/ TODO Auto-ge nerated con structor stu

7、b/散列表初始化，长度重置为0。public void In itiate() Len gth = 0;ht = new barrel D;System. out .println(散列初始化完毕);基本操作：Hash (key )(即 F (k)初始条件：数据元素key已存在操作结果：根据散列函数计算地址，并返回地址基本操作：search1 (HashTable &H,初始条件：表已存在 操作结果：单步查找关键值为 key的元素，若查找成功，则success否则为-1.基本操作：in sert (HashTable & H,)初始条件：表已存在操作结果：查找不成功时插入数据元素e到开放定址散

8、列表H中，并返回SUCCESS;否则输出已有此数！插入失败！并返回-1。基本操作：delete(HashTable & H,i nt e)初始条件：表已存在操作结果：通过散列函数查找相应的元素，然后查看是否有元素存在，有 则进行删除操作，删除后还要对表进行调整。2模块构成本程序包括如下功能模块：哈希函数模块，冲突处理模块，哈希表初始化模 块，哈希表创建模块，哈希表显示模块，按关键字查找模块，插入模块，删除模 块和主程序模块。搜索流程图如下:插入流程图如下:次模块用来插入元素e,输入一个元素e,如果存在此元素，则显示“已有 此数！ ” “查找失败”。若不存在次数，则插入，并显示“插入成功”四、功

9、能设计通过java程序实现对散列表的建表、插入、删除、搜索等操作。1建表操作。散列表初始化public void In itiate() 散列初始化完毕);ht = new barrel D;System. out .println(Show();2插入操作：插入操作做2个方法search1用于插入单个元素，且表中已经存在的元素不能再插入。Search2用作插入多元素。如果存在冲突，则处理冲突后再重新计 算地址。publicboolea nIn sert1(int k) if ( this .Search1(k) != -1) System. out .println(对不起，你输入的元素已经

10、存在。)；return false ;System. out .println(插入元素 + k + ” );int in dex = Search2(k);if (in dex = -1)return false ;ht index = new barrel();ht index.setNum(k);Len gth +;System. out .println(将元素+ k + ” 插入+ index +号桶)；Show(i ndex);return true ;3搜索操作通过key值计算地址，若地址为空，查找失败。若标记相同，则查找成功， 否则，按照建表的处理冲突的办法重新计算地址。循环执

11、行，直到查找成功或失 败。public int Search1( | int k) System. out .println(查找元素 + k + ”在散列表中的所在位置： ”)；int in dex;in dex = F(k);/ 寻找起始位置int i = 1;while ( ht index !=null & i != D) /到达一个空桶或又回到f(k) 桶号桶“); ifelseSystem. out .println( Show(i ndex);(ht index.getNum() = k) System. out .println(ifreturn in dex;else in

12、dex = (in dex + 1) %查找+ index +号桶“);找到元素“+ k + 所在位置：+ index +D; /线性探测再哈希 i+;ht index !=System.outnull.println(遇到空桶-+ in dex +号桶-停止搜索“);System.return -1;.println(表中不含元素out/表中不含有关键值为k的元素+ k +);4删除操作删除元素值为key的元素,删除之前先进性查找操作,查找成功则删除元素,之后对后面的元素进行调整。public boolea n Delete2(intSystem. out .println( int in

13、dex;in dex = Search1(k);k) 删除元素+ k +);if (in dex = -1)return falseDelete1(i ndex);in dex = (in dex + 1) % while ( ht index !=System. out .println(/ Show();/单步显示/ ht(i ndex+D-1)%D=hti ndex; int x = ht index.getNum(); Delete1(i ndex);In sert1(x);in dex = (in dex + 1) %D;null ) 检查+ index +号桶“)；/当下处理的桶号

14、D;Len gthreturn true五、运行环境说明编程所用的语言是java，运行环境java虚拟机jdk是1.6版本的，编程平台是 exclipse| 比 Problems Javadoc 禽 Deck ration 貝 Console 上Mai n (2 Jiva A.pplication CiProgiram Fi 1 esJavajre6biaivaw.exe (20请输入散列表的长度；r玉M散列初绐化完毕L ： L （J JI （） ： ： ： 1 ：愉入操止偉号（1.SA/2.查找/3剧曉/4退出/5重墨）2进行插入操作1初始化散列表六、操作说明辐入換作序号（1. SA/2 -

15、查找#3删除/4 .退出/5 重赛I *1責住貢散列的插入：请谕入要插入的元素3进行搜索操作输入操作序号* 插入.查找/3.m/4.退岀炸-重羞） *散列的查找； 请输入要查找的元素4进行删除操作输入操作序号d 插入查找人刪除退出佔重羞）I |-q散列的删除: 请输入要删除的元素5进行重置操作输入操作库号（1-插入查找/3.洲隐H.退出.重置！散列初始化完毕女佥】输入操作庙号（i-ffiX/2.查TV? 刑嗓八.退岀.重羞6退出系统散列初始化完毕*承*少）输入操作斥号tl-ffiA/2-i找/3. 嗓八.退出丿5.重置七、系统测试用例实例：插入3个数字，依次为11、22、12,然后进行查找和

16、删除操作。查找数字1和22,删除13和22.1初始化散列表并输出散列表C Probsms ：冊avadoc 禺 Declarationrvwp H (输入操作序号.插入推.查找心-刪陰-退出/ 5 .重置】女a負負負散列的mA： “女m仑X 请输入要插入的元素*查找元素丁旷在散列表中的所在位羞；:查找0号桶(丄)】【】表中不含元素2盯*盘表仪插入元素竟茂仓齋寻找元秦讣厂曲插人位盖：責检査起始桶。号桶I】1 【1【】。号桶木为5,检香丄寻箱( 1 1 T 1 1丄号桶対空将元耒陀厂插？U号桶11)(221( r 1t J H H ) 1 ()输入操作倉号(1. JSA/z.査找归廟除退出/S.5

17、M插入元素12rtJ-J-I1 l J 1 1 1 1 1 It 1 L I L J I J I （saiM作浄号口培入a.查找心.删矗退出重置） 丄散列的插入；;请输入要插入的元素負佥査找元素T旷在散列表中的所在位蛊：查找号桶11 C2?H H （ H 11 H I 1 表中不合元素T旷插入元素壮K也食直寻我元臺、y*插入位羞土負倉致检查起始桶1号桶11 （22） H H H 【1 珂 1 1 【丄号桶不为空检查2号捅Ell 22j （ H H 【JI 】（【2号桶为空将元寮旷插入彳号福二苗门壮2口 II 3 】【J I H 输入操作岸号门插入杳K/3.111/1.退由/5 重置 3搜索功能

18、测试。搜索111 22（12H 1 L ! 1 谕入操作厚署查亦.删除/氏退出重羞）負立*心*!列的查抡負总仑立*仑 请输入要查找的元素查找元素t在散列表中的所在位耆：查如号楠11 H22H 12 I JI ）1 11 H 1查找工号桶11（2212【】羔中木含元素输入操作席号.插入/ 2 .查找丿詡.删除“.退出/ 5 .重気）搜索2211 22M(12)J f H I H 表中不含元素叱输人接作序号口.插入煜.查找心-删除.退岀川.重藍仓女右佥戏散列的查找：佥食白佥女 请输入要查我的元素 查找元素弩在散列表早的所在&S：查找0号桶(11)2212查找丄号桶11)1(22(12 I 3 IC

19、 H H ) H J我到元素7厂所SfeS : 1号桶输入操作序号门插入煜查找心删除退出心重蚤J 4删除功能测试。删除1311 I 122 12 找到元素7旷所在fcS： 1号桶输入揉作序号(插入查找删除退岀/重曙 上散列的删除上也責;请输入亜刪除的元素叶删除元素盘显查扶元素壮厂在散列表中的所在位墨：查找2号桶11【廿!丄(丄印H 1 J I 1 t 1 t L 1表中不含元素T3输入操作序号(3插入A 查找”刑除退出/5 重置 删除22Ell 22_f (12) I H J表中不含元素73输入操作序号口.插入强.查找删除丿4 .退出/5.重置)散列的删除；負情输人SJBM的元素22总*删际元

20、毒弟少八糞滋上查我元茅”往散列表中的所在位蛊i衣立 查找。号桶(H) 21 12 I 1 H 1 ： 1 I 杳找丄号桶11 CC22) 12找到元畚 y 所柱鉉置=号桶删除1号桶內元素11t 12 H ) 1 I H 1捡查?号箱删除2号桶内元素11 H C H 1 K H ) H 責宴找元素口旷在散列恚中的所在位贵：食負 袁中不含元素沁少命插入 元診辽 責 寻找元索T2由需人位墨；检查起始桶丄号桶11tt H 9 C I H H J H 1号桶为空將元素叮計描入丄号桶I1CC12I H H t t C H 1输入操作序号仕.插入72 .查找/乳删除门.退出/5.重置 5重置功能测试。ipnri2)i H)【】【】【】输入操作厚=(1.插入z.查找门.删除.退出门.重羞)散列初始化完毕L H H H 1( L 1 L H E 愉入燥作序号匸.插入.查/a-m/4.