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

教材学习内容总结

• 集合

1. 集合是收集并组织其他对象的对象
2. 集合中的元素一般由加入集合的次序或元素之间某些固有的关系而组织
3. 集合是隐藏其实现细节的一个抽象名称
4. 数据结构是用来实现集合的基本程序设计结构

• 栈

1. 栈以LIFO的方式处理元素，最后进入的元素最先离开
2. Java接口定义了一组抽象方法，能用来抽象数据类型概念与它的实现分开
3. 通过使用接口名作为返回值类型，接口机制可让方法实现栈的具体的类分开
4. 栈是计算后缀表达式时使用的理想数据类型
5. 错误和异常代表不常见或不正常的处理
6. 处理异常情形的方式，决定是集合还是集合的使用者来控制具体的行为
7. 考虑到效率，数组实现的栈将栈底放到下标为0的位置

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

• 问题1：时间复杂度
• 问题1解决方案：若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。

记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。

渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

• 问题2：如何推导出时间复杂度？
• 问题2解决方案：

1. 如果运行时间是常数量级，用常数1表示；

2. 只保留时间函数中的最高阶项；

3. 如果最高阶项存在，则省去最高阶项前面的系数。

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

• 问题1：选择排序、冒泡排序、插入排序到底分别指什么？
• 问题1解决方案：冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
  选择排序（Select Sorting）：的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R{1}~R[n-1]中选取最小值，与R[1]交换，....， 第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
  插入排序（Insertion Sorting）：局部有序，先把第一个数据看成一个有序数组，然后把第二个数据插入到这个“有序数组”中，形成具有两个数据的有序数组，依次类推，直至最后一个数据插入到具有 N-1 个数据的有序数组中，完成排序。插入过程：获取当前数据，并标记当前数据与下标，与之前有序数据的最后一个作比较，若小于最后一个数据则将最后一个数据进行后移操作，然后再与倒数第二个数据进行比较，重复刚才的操作，若不小于则终止操作。
  三种排序的比较：其时间复杂度都是O（n^2），但是由于细节比较或是循环问题，速度上体现为：插入排序>选择排序>冒泡排序。

代码托管

上周考试错题总结

七周无考试，无错题

结对及互评

点评：

• 博客中值得学习的或问题：
  • 对课本，代码进行多方位的思考。
  • 认真寻找自己的不足之处。
  • 举例说明问题。
• 代码中值得学习的或问题：
• 基于评分标准，我给本博客打分：14分。得分情况如下：
  • 感想，体会不假大空的加1分
  • 排版精美的加一分
  • 结对学习情况真实可信的加1分
  • 正确使用Markdown语法
  • 模板中的要素齐全（加1分）
  • 错题学习深入的加1分
  • 点评认真，能指出博客和代码中的问题的加1分
  • 教材学习中的问题和解决过程, 加5分
  • 代码调试中的问题和解决过程,加2分

点评过的同学博客和代码

• 本周结对学习情况
  • 赵沛凝20182301

  • 结对照片
    

  • 结对学习内容
    • 时间复杂度的计算
• 上周博客互评情况
  • 20182301

其他（感悟）

学习进度条

• 实际学习时间:8小时

参考资料

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

• 《Java程序设计与数据结构教程（第二版）》学习指导
• 使用开源中国(码云)托管代码 - 娄老师 - 博客园

• Java子类与父类之间的类型转换 - 壮壮大学渣 - 博客园

原文：https://www.cnblogs.com/20182326lyj/p/11788898.html