20172313 2018-2019-1 《程序设计与数据结构》第四周学习总结

教材学习内容总结

• 列表集合
  • 有序列表： 其元素按照元素的某种内在特性进行排序。（有序列表中的元素具有内在关联，这种关联定义了元素之间的顺序）
  • 无序列表： 其元素间不具有内在顺序，元素按照它们在列表中的位置进行排序。（无序列表中的元素按使用者所选择的任意方式排序）
  • 索引列表： 其元素可以用数字索引来引用。（索引列表为它的元素维护一段连续的数字索引值）
• Java集合API中的列表

• 列表ADT

• 使用数组实现列表
  • 一般的的列表可以从两端添加或删除元素，但它们还有从列表的中间插入或删除元素。因此无法避免要移动元素。可以使用环形数组方法，但当从列表中间插入或删除元素时，仍需要移动元素。
  • 重载equals方法以及实现Comparable接口是展示面向对象设计的极好示例。我们可以创建集合的实现来处理各种还没有设计的对象，只要这些对象具有相同的定义和（或）类中提供对象间的某种作比较的方法。
  • 将向ArrayList类中诸如find之类的private方法独立出来有多种益处。首先，它使得本已复杂的remove方法的定义变得非常简单。第二，它使得我们能够利用find方法来实现contains操作以及ArrayUnorderedList的addAfter方法。注意，find方法不会抛出ElementNotFound异常，它只是简单地返回值（1）以表明元素未找到。通过这种方法，调用程序可以决定如何处理元素未找到的情况。在remove方法中，这意味着抛出一个异常。而在contains方法中，这意味着返回false。
  • 在进行remove操作的时候，如果要删除的元素是列表的最后一个元素，在这种情况下，需要进行n次比较操作。事实证明，这种删除操作的实现正好需要n次比较和平移操作，因此该操作的复杂度为O(n)。如果使用的是环形数组实现，他只是提高了删除第一元素这样一种特殊情况下的性能。
  • 进行contains操作时，由于该方法执行的是列表的线性查找，因此最坏的情况是所查找的元素不在列表中，在这种情况下需要n个比较操作，因而该操作的复杂度为O(n)。
  • 与remove一样，每次运行add操作时需要进行那次比较和平移操作，因此该操作的复杂度为O(n)。
• 使用链表实现列表
  • 进行remove操作时，与数组实现的人move操作不同，链表实现的remove操作不需要评议元素来填补空袭。但是，在最坏的情况下，仍需要进行n次操作，已确定目标元素不在列表中，因此remove操作的复杂度仍为O(n)。

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

• 问题1：我们可以分别使用数组和链表实现列表，那么使用数组实现的ArrayList和使用链表实现的LinkedList在空间复杂度和时间复杂度上的区别在哪？
• 问题1解决方法：每个对象插入到列表中时，链表实现需要更多的空间。LinkedList类实际上是一个双向链表，因此其引用需要两倍的空间。ArrayList类在空间管理上比基于数组的实现方式更高效。这是因为，ArrayList集合是可变大小的，因此按所需动态分配空间。所以，无需一次申请大量的空间而造成浪费。列表是在需要时才增加空间。两者间最大的区别发生在访问列表中特定索引位置时。如果已知索引值，ArrayList实现能够在相同的时间内访问列表中的任意元素。LinkedList实现需要从一端或另一端起对列表进行遍历，以到达特定索引值。
• 问题2：在学习书上代码时，有这样一段话：ProgramOfStudy和Course类实现了Serializable接口。为了是某个对象能使用串行化进行存储，其类必须实现Serializable。在erializable中没有任何方法，它只是表明，该对象可以转换为串行化表示形式。 我对于Serializable接口了解的不多，也不太明白串行化在这里表示的是什么意思。

• 问题2解决方法：

  什么是Serializable接口？
  一个对象序列化的接口，一个类只有实现了Serializable接口，它的对象才能被序列化
  什么是序列化？
  将对象的状态信息转换为可以存储或传输的形式的过程，在序列化期间，对象将其当前状态写入到临时存储区或持久性存储区，之后，便可以通过从存储区中读取或反序列化对象的状态信息，来重新创建该对象
  什么情况下需要序列化？
  当我们需要把对象的状态信息通过网络进行传输，或者需要将对象的状态信息持久化，以便将来使用时都需要把对象进行序列化
  Serializable主要用来支持两种主要的特性：
  1、Java的RMI（remote method invocation），RMI允许像在本机上一样操作远程机器上的对象，当发送消息给远程对象时，就需要用到序列化机制来发送参数和接受返回值
  2、Java的JavaBean，Bean的状态信息通常是在设计时配置的，Bean的状态信息必须被保存下来，以便当程序运行时能恢复这些状态信息，这也需要序Serializable机制

• 问题3：书上使用链表实现列表的remove操作示例中有下面这样的代码,我有些不太清楚这里if的判断条件是！found自身的boolean值还是当前found的值是否发生改变。

if(!found)
   throw new ElementNotFoundException("LinkedList");

• 问题3解决方案：!是一个一元运算符，运算对象是boolean类型的，若运算对象为true则返回false，若运算对象为true则返回false。!value的话value要是boolean值才可以进行运算。
  下面举的例子if(file!=null)就是如果file对象不为空，则执行if下面的语句。
  if(!value.equal("")) 显然value是一个string类型的，这里的!操作符并不是对value进行运算的，而是对value.equal("")进行运算的
  equal()方法返回的值是boolean类型的
  if(!value.equal(""))整个意思是如果value不为空字符串（注意哦，不是不为空，这是有区别的），则执行if下面的于语句。

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

• 问题1：在完成pp6_11编程项目的过程中，调用addAfter()方法后，会提示我出现了空指针。
  

• 问题1解决方法：在debug了之后，我发现我调用了addAfter()方法后，如果新添加的数位于该列表的末尾，这时候我对tail这个尾部指针是没有进行任何操作的，tail此时并没有真正指向该列表的尾部。在这之后在调用removeLast()方法，就不能对尾部的节点进行正确的操作，会出现空指针的情况。
  
  

• 问题2：在完成pp6_17编程项目的过程中，当我调用contains()方法来判断某节点是否存在时，我发现我明明删掉的节点在判断的时候依旧为true。
  
  

• 问题2解决方法：令我奇怪的时，当我打印输出整个列表时，我已经删掉的这个节点是不会出现的，我调用Last()方法打印该列表的最后一个节点所保存的元素发现也是没有问题的。我又更换了几组节点进行判断是否存在，更让我奇怪的事情发生了，只有当判断的节点是最后一个并且该节点被删除时才会出现问题。我进行了debug操作，在判断到我所认为的列表的末尾时，它竟然还会继续循环下去，指向那个我原本以为删除的节点！我终于发现了问题所在，在删除末尾节点的时候虽然将tail指向了它前面的节点，但并未将tail指向空，所以在循环的时候指针依旧是指向那个本要删除的节点的。如下图所示，我只要把tail再指向null就行了。
  
  

代码托管

上周考试错题总结

• 错题1:：A reference variable can refer to any object created from any class related to it by inheritance.
  A . true
  B . false
• 错题分析：这题翻译过来就很直接明了了，子类通过继承父类能够调用父类的所有方法，在测试的时候对英语不是很懂什么意思，导致做错。
• 错题2：A well-defined interface masks the implementation of the collection.
  A . true
  B . false
• 错题分析：一个定义良好的接口能够更好的帮助集合的实现，测试时没有好好理解题目的意思。
• 错题3：Common features should be located as low in a class hierarchy as is reasonable, minimizing maintenance efforts.
  A . true
  B . false
• 错题分析：公共特征应该在合理的层次结构中尽可能高，从而最大限度地减少维护工作。

结对及互评

• 博客中值得学习的或问题：
  • 排版精美，对于问题研究得很细致，解答也很周全。
• 代码中值得学习的或问题：
  • 代码写的很规范，思路很清晰，继续加油！

点评过的同学博客和代码

• 本周结对学习情况
  • 20172332
  • 20172326
  • 结对学习内容
    • 第6章 列表

其他（感悟、思考等，可选）

??不得不说，国庆七天假期内的学习效率是非常低的（不想学习！不想学习！不想学习！)。但还是硬撑着完成了编程任务、写完了博客。也没有花更多的功夫去进行拓展学习。总的来说，这七天的学习时间是不够的，希望在假期过去后，自己的学习状态有所回升，继续进步！

学习进度条

• 计划学习时间:15小时

• 实际学习时间:15小时

参考资料

• 某些java类为什么要实现Serializable接口
• java中!的用法

20172313 2018-2019-1 《程序设计与数据结构》第四周学习总结

原文：https://www.cnblogs.com/yu-kunpeng/p/9748658.html