20172319 2018.10.19《Java程序设计教程》第7周课堂实践（补写博客）

时间：2020-12-01 15:12:39

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的计算。）

测试要求

  • 完成蓝墨云班课上的三种查找算法练习任务；并截图（类代码，测试代码，运行结果代码）发送至蓝墨云

  • 返回目录

实验步骤

需求分析

  1. 需要了解、掌握与三种查找相关的知识。
  2. 需要了解、掌握散列查找在发生冲突时的解决方法。
  3. 了解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当成中值，判定树如下：
  • 20172319 2018.10.19《Java程序设计教程》第7周课堂实践（补写博客）

  • 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

  • 返回目录

错误分析

已提交至蓝墨云上的错误：

  1. 除余错误：21%11=9.。。。٩(º﹃º٩)
  2. 索引标识错误。
  3. 查找错误：在开发地址中先放置好相应元素，再对有冲突元素进行处理；如当11、78、10处在了其相应位置后，对冲突元素1不做处理，直接放3，接着对冲突元素2不做处理，直接放4.

参考资料

相关文章