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

教材学习内容总结

算法分析的要点就是弄清楚我们需要解决什么问题、并且怎样做才能更简单地解决问题。要尽量减少无用的代码，减少不必要的运算。
栈的本质是先进后出，栈作为一种集合，可以使用多态进行实现。后缀表达式就是基于栈的思想进行运算的一种计算机思维进行的运算。栈有数组实现栈、链表实现栈的方法。
结点是各种栈中都非常重要的一个概念，如果没有结点，栈将无法建立，除非使用数组。然而数组实现的栈泛用性不足。

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

• 问题1：队列和栈存在哪些不同，哪些相同的地方，它们的用处分别是什么？
• 问题1解决方案：事实上两者的用处是相近的，只是功能和概念有不同的地方。两者都可以用数组、链表等方式来实现，不过队列是先进先出的集合，而栈则是先进后出的集合。队列就像我们正常认知中的排队，而栈就像在箱子里叠东西。
• 问题2：在实现栈的两种方式——链和数组之间存在着那些差别呢？
• 问题2解决方案：链表没有容量限制，不过数组是有的。和C语言当中不一样的是，C语言当中数组本质上就是指针，然而在Java当中，链表类似于使用指针访问，必须一次一个元素地移动才能找到目标单位；而数组就可以直接通过下标，来访问要寻找的目标单位。同时，使用链表的时候，因为没有容量限制，反过来也可以说“只有需要的时候才分配空间”，灵活性更大一些；而数组的存储空间就和容量一样，是定死的，一般也只用于保存对象。
• 问题3：什么是哨兵结点或者虚位结点？在双向链表里面设定哨兵结点的作用是什么？
• 问题3解决方案：这两种结点也可以认为是一个中转量，相当于C语言中常用的temp。在双向链表的表头和表尾设置两个虚位结点，可以解决处理第一个、最后一个元素的特殊情况的问题。

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

• 问题1：在一些查找方法的实现过程中，如果需要排序（比如折半查找法就需要我们先对数组进行排序），并且不方便把之前自己敲的代码复制粘贴到这个类中或是引用这个类，我应该怎么做呢？
• 问题1解决方案：经过网上百度得知，JDK的数组计算自带这种功能。对数组进行.sort的操作，这个数组就会自然地按从小到大进行排序了。在需要进行折半查找法的代码实现，又不想手敲一遍排序方法的时候，就可以这样操作。
• 问题2：在排序的过程中，如果担心数组中的数据被覆盖，用什么方法比较好呢？（在不方便用temp的中间量）
  问题2解决方案：虽然新建一个数组来存储排序后的数组并不是太高效，但是在这种情况下这也是唯一的办法。但是也不能直接创建一个空的数组，要不然就会报错。我会根据我需要排序的数组有多少个数，比如王Sir给我们的课后实践，需要我们进行查找的那个数组有十二个数，那么我在折半查找法之前先排序数组，就会选择先新建一个容量为12的数组，里面存了12个0，防止编译系统觉得它是一个NULL而无法存入。

代码托管

上周考试错题总结

上周没有考试。

点评过的同学博客和代码

• 本周结对学习情况
  • 20182312
  • 结对学习内容
    这两周的学习重点并不在于代码上了，而是在于对数据结构的各种构成，比如链表、栈、队列等等东西的概念。同时一起学习了ASL和四种查找方式，我和他在某次实践中都是需要选择排序，我和他交流了
    一下如何用代码实现选择排序。
• 上周博客互评情况
  • 20182312

其他

1、数据结构部分内容的学习和前面不太一样，许多东西是需要理解更多一点，然而才能开始操作。而且代码的实现和概念的理解完全是两回事，但不得不说想要实现确实得建立在理解之上。之前我们在C语言当中也做过类似的事情。现在看来理解并不算太难的事情，用代码实现却是十分困难的。如何处理数据、变量，考虑它们的变量类型，考虑到各种类之间功能的调用，而且也要考虑return了什么东西，等等此类。
2、和纯粹敲代码的日子不一样，学习数据结构因为有许多理论性的东西，所以不少东西是不能在计算机上操作、而是应该重新回归课本和练习纸。

学习进度条

• 计划学习时间:45小时

• 实际学习时间:42小时

• 改进情况：因为数据结构很多东西都是十分理论性的，所以需要花一些时间在纸上进行操作。

参考资料

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

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

20182308 华罗晗 2019-2020-1 《数据结构与面向对象程序设计》第七周学习总结

原文：https://www.cnblogs.com/77599aa/p/11748164.html