20172328 2018—2019《Java软件结构与数据结构》第二周学习总结
概述 Generalization
本周学习了第三章集合概述——栈和第四章链式结构——栈。主要讨论了集合以及用于实现集合的基本数据结构，以及集合设计的相关问题和目标。本章内容以栈为例展示与集合的设计、实现和使用等有关的问题。
教材学习内容总结 A summary of textbook
- 3.1集合
- 集合是一种聚集、组织了其他对象的对象。集合可以分为两大类：线性集合和非线性集合。
- 线性集合：一种其元素按照直线方式组织的集合。
- 非线性集合：一种其元素按某种非直线方式组织的集合。
- 集合中元素的彼此之间的组织形式通常由元素添加到集合的次序和元素自身的一些内在关系决定。
- 抽象数据类型（ADT）：是一种在程序设计语言中尚未定义其值和操作的数据结构类型。ADT的抽象性体现在，ADT必须对实现细节进行定义，且这些对用户是不可见的。
- Java集合API(应用程序编程接口)：一个类集，表示了一些特定类型的集合，这些类的实现方式各不相同。
- 3.2栈集合
- 栈（STACK）是一种线性集合，其元素的添加和删除都是在同一端进行的。其遵循后进先出（LIFO）原则，可颠倒顺序。
栈的基本操作
- 3.3主要的面向对象概念
- 利用多态引用和继承，可以创建可以储存任意类型的对象的集合。
- 多态引用是一个引用变量，他可以在不同地点引用不同类型的对象。术语“多态性”可定义为“具有多种形式”。通过多态引用调用的某个方法，在每次调用的时候都可以发生变化。
- 继承可用于创建一个类层次，一个引用变量可用于指向与之相关的任意对象。继承就是从已有类派生出一个新类的过程。新类自动地含有初始类的部分和全部变量和方法。
- 泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。
- 3.4使用栈计算后缀表达式
- 由栈提供的操作与后缀表达式计算过程有着很好的一致性。使用栈来计算后缀表达式的算法描述如下：从左到右扫描表达式，依次识别出每个符号（操作符或操作数）。如果是操作数，就将其压入（push）栈中。若是操作符，则从栈中弹出（pop）两个操作数，并把先弹出数放在符号右侧，后弹出数放在符号左侧进行计算，然后把计算结果压入（push）到栈中，循环往复，当进行到表达式的末尾时，栈中所剩余的元素便是该表达式的结果。
- javadoc注释（为Java添加注释的官方标准）:以/**开始、以 */结束。Javadoc可用于创建关于类集的在线的HTML文档，在线的JavaAPI文档就是例子。
- 3.5异常（略）
- 3.6栈ADT
- Java接口定义了一个抽象方法集，有助于把抽象数据类型的概念与其实现分开。
public interface stackADT <T> - 3.7用数组实现栈
- 数组中的单元数量称为容量，该值储存在数组的length常量中，数组一旦创建好，其容量是不能改变的。
- 3.8ArrayStack类
- 泛型（包括泛型数组）不能被实例化。所以我们必须创建一个存储Object引用的数组，然后把他转换成泛型数组。
- 创建一个泛型数组:
stack = （T[])(new Object[initialCapiry]) - 在将Object数组转换成泛型数组时一定会出现未检验类型转换警告，所以加上
@SuppressWarnings（“unchecked”）即可。 - push、pop、peek、isEmpty、size等方法的具体使用。（作业实践中有，此处不再详细叙述）
- 4.1链接作为引用
对象引用变量可以用来创建链式结构。链式结构是一种数据结构，主要使用对象引用变量来创建对象之间的链接。介绍了自引用，在链表中存储的对象通常称为该链表的结点。
- 4.2管理链表
- 访问链表元素的唯一方式是，从第一个元素开始，顺着链表往下进行。
- 使用链表时，我们要维护指向链表第一个元素的指针。
- 插入结点和删除结点需要注意不能丢失数据，有时需要创建一个结点来暂时保存一下。
- 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
- 4.3无链接的元素
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接向后和直接向前。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的头结点和尾结点。
- 4.4JavaAPI中的栈
- java.util.Stack类是从Vector派生而来的，它带给了栈一些不恰当的操作。
- 4.5使用栈来穿越迷宫
- 可以使用栈来模拟递归处理，以跟踪恰当的数据。
- 4.6用链表来实现栈
主要是通过代码体现。
教材学习中的问题和解决过程 Problem and countermeasure
- 1.不明白泛型是什么且如何使用。
- 问题1的解答:
假定我们有这样一个需求：写一个排序方法，能够对整型数组、字符串数组甚至其他任何类型的数组进行排序，该如何实现？
答案是可以使用 Java 泛型。使用 Java泛型的概念，我们可以写一个泛型方法来对一个对象数组排序。然后，调用该泛型方法来对整型数组、浮点数数组、字符串数组等进行排序。
- 定义泛型方法的规则：
- 所有泛型方法声明都有一个类型参数声明部分（由尖括号分隔），该类型参数声明部分在方法返回类型之前（在下面例子中的）。
- 每一个类型参数声明部分包含一个或多个类型参数，参数间用逗号隔开。一个泛型参数，也被称为一个类型变量，是用于指定一个泛型类型名称的标识符。
- 类型参数能被用来声明返回值类型，并且能作为泛型方法得到的实际参数类型的占位符。
- 泛型方法体的声明和其他方法一样。注意类型参数只能代表引用型类型，不能是原始类型（像int,double,char等）.
课后习题代码实践遇到的问题和解决 Exercise
- 问题1:理解pp3.2和pp3.8的不同。刚开始的时候我在做两个题目的时候觉得很相似。所以在成功吧pp3.2做出来后就将两个入栈出栈循环复制到了pp3.8中，当时试验的例子是中文“我想你”，出来的是“你想我”，所以就很放心的交了作业。直到上自习的时候听到同学们讨论，我才意识到pp3.8是元素集的相反，虽然在中文单独的字上体现不出来，但是在英文表述上就很有问题。
问题1解决：我将pp3.8的charAt方法换成split方法，用空格把语句分开，然后再循环入栈、循环出栈。这样就可以达到“I love Java”变成“Java love I”！但是，我的中文若是不带空格，就会直接被看成一个元素集，然后纹丝不动的抛回给我。所以我就想用条件语句做两段语句，先用if语句看看语句索引第二位置是否是空格，然后决定用哪种方法。（具体实现代码可去码云查看。）
- 问题2：不明白选择排序、冒泡排序、插入排序到底分别指什么？虽然上学期学过了，但印象只有方法的实际实现、却没有对应上相应的名字。所以在做蓝墨云班课上的训练时显得很生疏。
- 问题2解决：
- 冒泡排序（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），但是由于细节比较或是循环问题，速度上体现为：插入排序>选择排序>冒泡排序。
- 在了解了这三种排序之后开始做蓝墨云上的作业。要对链表进行排序还是很考验思维逻辑的。
- 首先说给链表冒泡排序。冒泡排序的思维是最简单的，但是代码实现起来也非手到擒来。当时用循环来比较的时候，就一直要把链表的节点向后推，但要用一个中间变量temp来保存前面的数字，然后做数字交换，最后把遍历的起始节点重指向头结点。
其次是给链表选择排序。选择排序需要的变量更加多，因为要遍历n-1次，且每次都要挑出最小的数字来和当前参与比较的第一个数字调换位置。所以要设两个整型变量min和temp和三个结点来指向位置。
码云链接
代码量
上周测试活动错题改正 Correction
- 1.Software that is easily portable, can be moved from one computing environment to another with little or no effort.
A .True
B .Flase - 改正：当时理解的题目意思是：软件很好移植！！当时觉得使用Java语言才可以很好移植。结果今天再看题目，人家的意思是：可移植性好的软件，可以毫不费力或费力很少的从一个计算机上移植到另一个计算机上。
对不起大哭，英语没学好。 - 2.An efficient system handles problems gracefully
A .True
B .Flase - 改正：高效的系统处理软件会很优雅。暂时不知道到底该选择什么。暂且认为：效率表明软件实现其目标而无浪费资源，所以很利索？！
- 3.Software systems need only to work to support the work of developers, maintainers, and users.
A .True
B .Flase - 改正：本题是不全面的说法，软件系统需要尽量的完美符合所有人的需求。
- 4.Which Growth function has the highest order?
A .O(n log n)
B .O(n^2)
C .O(2^n)
D .O(log n) - 改正：好的，是它的题目没有弄清楚，我帮它补上去了，2n和2^n是有很大差别的。速率大小排序是：
n^3>2^n>n^2>nlogn>logn>n - 5.Which of the following has the smallest time complexity?
A .3n+5+2n
B .logn+2
C .3n+4
D .nlogn - 改正：看错了，人家问的是最慢的。
- 6.If the algorithm is inefficient, a faster processor will help.
A .True
B .Flase - 改正：有帮助，但是帮助很小，所以关键还是在于算法的复杂度（运行速率），尤其是在要处理的问题巨大的时候，使用更快的处理器也无济于事。
结对及互评Group Estimate
点评模板：
- 博客中值得学习的或问题：
- 20172301：教材问题和实践问题很详细，教材内容总结简明扼要，博客风格较上学期有所改变。虽然我知道你最近超级忙，就如同我上学期那样，但是对你学的最好的一门课（大概是你最喜欢的？）还是多赐予点精力吧！
- 20172304：这学期的博客真的很让我开心，真的和以前有了很大区别。虽然我很早很早之前就知道我的小伙伴很聪明，但是在学习态度上真的是由以前的率性而为变得认真负责，很开心能在Java学习的道路上一同成长，继续加油！
- 第二周结对任务落实的不太到位，很多问题都是我们三个自己解决自己的，可能是有点忙啦(#^.^#)。不过不过我相信，下一周我们三个一定会继续独立思考、但在问题上共同攻难克险！
其他（感悟、思考等，可选）Else
一个假期没翻书的结果就是让我现在得多翻书
。
很多时候面临问题我总是倒在畏惧脚下，“我不会”、“我不能”、还是“我不行”，其实都是懦弱两手一摊不作为的我。匆匆从指缝溜走的都是最珍贵的年轻生命。既然十九年又开始新的轮回，那就勇敢一点、再勇敢一点吧！
如果一辈子没有茶不思，饭不想的想要一件东西，本身就是一件很遗憾的事。人生难得本就是痴迷。 dust yourself off
学习进度条Learning List
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | |
|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 |
| 第一周 | 0/0 | 1/1 | 8/8 |
| 第二周 | 621/621 | 1/2 | 14/22 |
参考资料Reference
- [Java软件结构与数据结构]（第四版）
- Java泛型
- 方法重载和方法重写的区别
- 基础排序总结
- Java链表