20172319 2018.10.19《Java程序设计教程》第7周课堂实践（补写博客）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了20172319 2018.10.19《Java程序设计教程》第7周课堂实践（补写博客），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3904字，纯文字阅读大概需要6分钟。
内容图文
20172319 2018.10.19 《Java程序设计教程》第7周课堂实践
- 课程:《程序设计与数据结构》
- 班级：1723
- 学生：唐才铭
- 学号：20172319
- 指导老师：王志强
- 日期：2018.10.19
- 必修/选修：必修
目录
测试内容
- 三种查找算法练习：
- 给定关键字序列：11,78,10,1,3,2,4,21，试分别用顺序查找 、折半查找 、散列查找 （用线性探查法和链地址法）来实现查找。试画出它们的对应存储形式（顺序查找的顺序表，二分查找的顺序表，两种散列查找的散列表），并求出每一种查找的成功平均查找长度。其中，散列函数H（k） = k%11。
（本次作业6分，每种算法2分，包括画出存储形式和ASL的计算。）
测试要求
完成蓝墨云班课上的三种查找算法练习任务；并截图（类代码，测试代码，运行结果代码）发送至蓝墨云
实验步骤
需求分析
- 需要了解、掌握与三种查找相关的知识。
- 需要了解、掌握散列查找在发生冲突时的解决方法。
- 了解ASL是什么？
相关知识
顺序查找 、折半查找 及ASL 此前在第五周学习总结及第6周课堂实践中阐述过，这里不再做多余的叙述。
散列查找：
- 哈希表（Hash table，也叫散列表），根据关键码值（Key value）而直接进行访问的数据结构。即通过将关键码值映射到表中的一个位置来访问记录，以加快查找的速度。 。 映射函数称为散列函数 ， 存放记录的数组称为 散列表 。
- 例如：
- 散列函数为：H（key）= key mod p （p = 11）
- 对于元素： 17,21,41，38,25。
- 可通过散列函数来确定其在表中的位置，如对于元素25，H（25）= 25%11 = 3，即其在表中处于第3位。
索引 0 1 2 3 4 5 6 7 8 9 10 11 12 元素 25 38 17 41 21 - 而有些时候会发生这样一种情况：H（key1）= H（key2），key1≠key2。
- 即在表中发生了冲突 ，这是不可避免的。
- 介绍几个与其相关的因素：
- 装填因子（Loading Factor）：设散列表空间大小为m，填入表中元素个数是n，则称a=n/m为散列表的填装因子，一般情况下0.6<a<0.9为宜，a越大越有可能发生冲突。
p：一般为素数，设散列表空间大小为n，则1.1n<p<1.7n为宜，这样可以尽可能避免发生冲突。
处理冲突的几种方法 ：
- 举例：在长度为12的哈希表中已填有关键字分别为17,60,29的记录，（哈希函数H（key）= key MOD 11）,现有第四个记录，其关键字为38，由哈希函数得到哈希地址为5，发生冲突。
索引 0 1 2 3 4 5 6 7 8 9 10 元素 60 17 29
开发地址法：给元素换个位置。
- 一旦产生冲突（该地址已有其他元素），就按照某种规则去寻找另一个空地址。
- 若发生了第i 次冲突，试探的下一个地址将增加dⅰ ，
- hⅰ （key） = （h（key）+ dⅰ ） mod TableSize （1< i < TableSize ） 。
dⅰ 决定了不同的解决冲突方案：
线性探测法：
- dⅰ = i ；
- 以增量序列1,2,3 …… （TableSize - 1）循环试探下一个存储地址。
索引 0 1 2 3 4 5 6 7 8 9 10 元素 60 17 29 38 二次探测法：
- dⅰ = i 2 ；
- 以增量序列1 2 ,-1 2 ,2 2,-2 2 ,3 2 ，-3 2 …… q 2 ，-q 2 循环试探下一个存储地址；q≦【TableSize/2】。
索引 0 1 2 3 4 5 6 7 8 9 10 元素 38 60 17 29 伪随机探测再散列：
- dⅰ = 伪随机数序列 ；
- 以伪随机数序列循环试探下一个存储地址。
索引 0 1 2 3 4 5 6 7 8 9 10 元素 38 60 17 29
链地址法：
- 开发地址法利用的是表中的剩余空间，如果空间不足，那其将无法处理冲突也无法插入数据，因此此刻需要装填因子≧1。
原理：遇到冲突时，会在原地址新建一个空间，然后以链表节点的形式插入到该空间里。
索引 元素 0 1 2 3 4 5 60 → 38 6 17 7 29 8 9 10
实现及解释
- 关键字序列：11,78,10,1,3,2,4,21。
散列函数： H（k） = k%11。
线性查找：
索引 0 1 2 3 4 5 6 7 元素 11 78 10 1 3 2 4 21 查找次数 1 2 3 4 5 6 7 8 ASL = （1 +2 +3 +4 +5 +6 +7 +8）/ 8 = 4.5
折半查找：
索引 0 1 2 3 4 5 6 7 元素 11 78 10 1 3 2 4 21 索引 0 1 2 3 4 5 6 7 元素 1 2 3 4 10 11 21 78 查找次数 3 2 3 1 3 2 3 4 - 因为所查找的元素为偶数，所以中值元素为4或10，无论是4还是10，不影响查找的结果。
- 这里把4当成中值，判定树如下：
ASL = (1x1 + 2x2 + 4x3 + 1x4) / 8 = 2.625
散列查找：
- 开发地址法：
索引 0 1 2 3 4 5 6 7 8 9 10 元素 11 78 1 3 2 4 21 10 查找次数 1 1 2 1 3 2 8 1 ASL = (1 + 1 + 2 + 1 + 3 + 2 + 8 + 1 ) / 8 = 2.375
链地址法：
查找次数(头) 查找次数（节点） 索引 元素 1 0 11 1 2 1 78 → 1 1 2 2 1 3 3 1 4 4 5 6 7 8 9 1 2 10 10 → 21 ASL = （6x1 + 2x2）/8 = 1.25
错误分析
已提交至蓝墨云上的错误：
- 除余错误：21%11=9.。。。?(º﹃º?)
- 索引标识错误。
- 查找错误：在开发地址中先放置好相应元素，再对有冲突元素进行处理；如当11、78、10处在了其相应位置后，对冲突元素1不做处理，直接放3，接着对冲突元素2不做处理，直接放4.
参考资料
内容总结
以上是互联网集市为您收集整理的20172319 2018.10.19《Java程序设计教程》第7周课堂实践（补写博客）全部内容，希望文章能够帮你解决20172319 2018.10.19《Java程序设计教程》第7周课堂实践（补写博客）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。