20182331 2019-2020-1 《数据结构与面向对象程序设计》第8周学习总结

教材学习内容总结

• 查找

  • 常见查找方式：线性查找，折半查找，哈希表查找，分块查找。

  • 哈希函数构造方法：直接定址法，数字分析法，平方取中法，折叠法，除留余数法。

  • 解决冲突的办法：开放定址法，再哈希法，链地址法。

  • 查找目标：高效地完成查找，用最小化比较操作。通常查找池中项目数目定义了该问题的大小。

  • 静态方法（类方法）：可通过类名激活

  • 在方法声明中，通过static修饰符就可以把它声明为静态的。

  • 泛型方法：与泛型类相似，不是创建引用泛型参数的类，而是创建一个引用泛型的方法。

  • 线性查找：从表头开始依次比较每个值，直到找到该目标元素。

  • 二分查找将利用查池已是排序的这一事实，每次比较都会删除一半的可行候选项。

  • 线性查找时间复杂度是O（n），二分查找时间复杂度为log2n，所以n值较大时，二分查找要快的多。

• 排序
  • 排序算法通常也分为两类：选择排序，插入排序，冒泡排序，快速排序，归并排序，

  • 选择排序法：

    • 初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
    • selectionSort方法实现两个循环，外层循环控制下一个最小值存储在那个位置，内层循环通过扫描所有大于等于外层循环指定索引的位置来找出剩余列表的最小值

  • 插入排序法：

    • 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
    • insertionSort方法使用了两个循环来对某个对象数组进行排序，外层循环控制下一个插入值在数组中的索引，内层循环将前插入值和储存在更小索引处的值进行比较。
  • 冒泡排序法：
    • 它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
    • bubbleSort方法中的外层for循环表示n-1轮数据遍历，内层for循环将从头至尾扫描该数据，对相邻数据进行成对比较，如果必要将其交换。

  • 快速排序法：

    • 快速排序算法通过将列表分区，然后对这两个分区进行递归式排序，从而完成对整个列表的排序。
    • quicksort方法非常依赖partition方法，起初用其将排序区域分开。partition方法的两个内层while循环用于寻找位于错误分区的交换元素。第一个循环从左边扫描到右边，以寻找大于分区元素的元素，第二个循环从右边扫描到左边，以寻找小于分区元素的元素。
  • 归并排序法：
    • 归并排序算法通过将列表递归式分成两半直至每个子列表都含有一个元素，然后将这些子列表归并到一个排序顺序中，从而完成对列表的排序。
    • 归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。
  • 基数排序法
    • 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后,从最低位开始,依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

教材学习中的问题和解决过程

问题1：@SuppressWarnings是什么？它怎么用？

问题1解决方案：
1.指示应该在注释元素（以及包含在该注释元素中的所有程序元素）中取消显示指定的编译器警告。注意，在给定元素中取消显示的警告集是所有包含元素中取消显示的警告的超集。例如，如果注释一个类来取消显示某个警告，同时注释一个方法来取消显示另一个警告，那么将在此方法中同时取消显示这两个警告。
2.根据风格不同，程序员应该始终在最里层的嵌套元素上使用此注释，在那里使用才有效。如果要在特定的方法中取消显示某个警告，则应该注释该方法而不是注释它的类。

代码调试中的问题和解决过程

问题1：对于归并排序和快速排序的循环次数该如何计算。
问题1解决方案：有两种方法可以解决，一种是直接通过引入times,来在循环中通过计算最后times相加的和。还有一种是设一个变量，循坏执行一次，变量自增一次。

代码托管

上周考试错题总结

• 上周无测试

结对及互评

• 博客中值得学习的或问题：
  • 学习深刻，自己有方法
  • 代码中值得学习的或问题：
  • 使用继承减少代码的重复编写
  • 基于评分标准，我给本博客打分：8分。得分情况如下：
    
  • 正确使用Markdown语法（加1分）
  • 模板中的要素齐全（加1分）
  • 教材学习中的问题和解决过程, 一个问题加1分
  • 代码调试中的问题和解决过程, 一个问题加1分
  • 有动手写新代码的加1分
  • 结对学习情况真实可信的加1分

点评过的同学博客和代码

• 本周结对学习情况
• 20182309
  • 结对学习内容
    • 阅读教材第13章章节内容
    • 代码托管到码云上
    • 完成课后自测题，并参考答案学习
    • 完成课后练习题
    • 完成程序设计项目，至少完成pp13.2，pp13.6

学习进度条

参考资料

• 《Java程序设计与数据结构教程（第二版）》

• 《Java程序设计与数据结构教程（第二版）》学习指导