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

正文

教材学习内容总结

教材第13章

• 查找
  • 线性查找：改进方法：设立哨兵，即将数组下标为0的内容设定为需要查找的数字，这样可以减少每次循环都对下标与最大值的比较，优化算法。
  • 折半查找：时间复杂度为O（log2n），效率高，但只能用于有序线性存储结构。
  • 哈希表查找：使用mod算法来实现数据的快速存取
    • 冲突：两个不同关键字对应同一个内存地址
    • 开放地址法：线性探测再散列，若关键字对应地址非空，向后移位直到找到空地址存入，查找步骤与之相同。
    • 链地址法：将存储空间定义为链表数组，每一个存储空间都代表一个链表的表头，若出现冲突，直接延长链表的长度，查找顺序与存入顺序相同。
  • 二叉排序树：通过在各个岔路口分流实现数据的排序。在实现过程中我使用了类似双向链表的数据结构，不过链表的两头只用来向下指左右子树，所以做出来的二叉树只能单向的读取数据，不能实现真正的“双向”。
• 排序
  • 衡量排序算法是否稳定的标准：相同元素排序后先后次序是否发生变化，
  • 插入排序：利用双重循环和插入，逐渐将整个表从前向后实现有序排列。
  • 折半插入排序：对插入排序的改良，将线性探索改为折半探索
  • 希尔排序
  • 快速排序：根任意元素划分表，再递归的对两个子表进行排序，从而完成一整组的排序。
  • 冒泡排序和选择排序
  • 归并排序：先递归的把表对分成每个子表只含一个元素，再将子表按序合并。
  • 基数排序
• ASL（平均查找性能分析）：查找所有元素需要进行的比较次数之和/元素总个数。

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

• 问题1：==，equals和compareTo的区别？
• ==：一般比较两个变量的值，返回true和false，比较对象的地址，不比较对象的内容
• equals：比较两个对象的内容，一般用于比较字符串。
• compareTo：在API中，java.lang包下面的基本数据类型（Integer,Float,Byte,Short,Character 等）的封装类都实现了对应的compareTo方法。例如对应Interger实现了数值大小判断；对应String按照字典排序实现字符串的判断，返回的是字符串长度差或者是字符间在码表上的差距。compareTo返回int值，大于返回大于0的整数，等于返回0，小于返回小于0的整数。
• 问题2：comparable不是接口吗，为什么好像当作一种数据类型来使用，声明数组类型？
• 问题2解决方案：comparable可用于表示实现comparable接口的对象类型。实现了comparable的对象类型，创建的对象数组使用arraysort时也课使用复写的compareTo方法。

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

• 问题1:使用二叉排序树找不到元素？
• 问题1解决方案：存入算法出现问题，查找也很繁杂。看了网上的博客后还是选择了递归方法，递归用于有顺序的数据结构的查找很方便。然后我做的二叉树差不多是这么个意思：
  

代码托管

结对及互评

点评过的同学博客和代码

• 本周结对学习情况

感悟

学排序查找算法不去看标准答案，而是自己先思考，虽然花费比别人数倍的时间，但是感觉收获会更多。但是还是感觉自己学的太潦草了...

学习进度条

参考链接

• 如何写一颗二叉树（递归）