学号 20182315 《数据结构与面向对象程序设计》第10周学习总结

教材学习内容总结

第十周主要讲图的相关构成，因此我的学习思路是：依次学习图的类别，图得实现方法，图的遍历，最优图。

• 图的类别：图可分为有向图，无向图，带权图。顾名思义，无向图即为节点与节点之间没有方向。有向图的节点与节点之间有方向。带权图节点与节点之间的边有意义，其边有权值。
• 图得实现方法：图的实现方法有连接表，连接矩阵。连接矩阵本质上是一个二维数组，分为横向和纵向两个方向。可以以横向到纵向定义节点方向。连接表即为二维数组，数组头为每一个结点，后序结点为与数组头连接的结点。
  

• 图的遍历：图的遍历较为复杂，分为广度优先遍历与深度优先遍历。

  （1）广度优先遍历：广度优先遍历要用到队列知识存放结点和MashMap来确定是否访问过此结点，
  将起始点存入队列中，将其标记为以访问存入MashMap中。在将结点从队里取出，搜索该结点所连接的结点，将他们存入队中，设为以访问。再将他们依此取出进行上述操作，直到队列里没有需要操作的数字。

  （2）深度优先遍历：广度优先遍历用栈来代替队列，因为他有先进先出的特性，另外，深度优先遍历直到结点进入迭代器将其设为已访问。

• 图的连接性：图得连接性可通过遍历来体现，如果图是全部连接起来的，那无论通过哪个节点进行遍历，遍历结点的结果都是一样的。如果不连通，那必定有一个结点的遍历结果为1。

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

• 问题1：对遍历中用到的MashMap没有接触，也并不了解。
• 问题1解决方案：MashMap相当于一个库，存入数据时采用“键+值”得方式存入，通过键找到相关得位置存入数据，如果数据已经存在，就替换掉原值，代替为新值。如果空间用完了，会自动将空间设置为二倍进行存储。
  
• 问题2：对于课上讲的两种最小生成树理解不是很深刻
• 问题2解决方案：

Kruscal算法：该算法将所有点先画出，再将权值最小的两个结点连接起来。注意避开回路

Prim算法：随机选一个顶点，将顶点周围权值最小的边连起来，将连好的作为一个整体，在余下部分找权值最小的边。连起来。

二者的区别就是先写边还是先写点，并且注意要将已经写好的放在一起比较。

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

• 问题1：进行图的广度便利时，报错，进行参数更改以及定点测试后，找到错误部分，即在队列处出现问题。

public void enqueue(T element)
    {
        LinearNode<T> node = new LinearNode<T>(element);

        if (isEmpty())
            head = node;
        else

        tail = node;
        count++;
    }  

• 问题1解决方案：
  秉承强哥的“万物可调”思想，我对其进行了单步调试，发现数据内部是断开的，由于大意，我忘记将数据连接起来，须在else后添加tail.setNext(node);才可正常运行。
• 问题2：在对深度遍历的编写过程中遇到障碍，对于迭代理解不到位。
• 问题2解决方案：

逻辑实现：首先是把源节点放到栈里和set里，并打印，然后弹出源节点，如果遍历源节点的所有next节点，如果当前next节点没有加入到set里，那么把源节点重新加入到栈里，这个 *next加入到栈里，并加入set集合中，打印该next，并跳出循环，把当前next变为当前节点（也就是栈顶元素），重复上面的操作，就会的得到一个深度优先遍历的序列 。

代码托管

上周考试错题总结

无

结对及互评

• 基于评分标准，我给本博客打分：13分。得分情况如下：

1. 正确使用Markdown语法加1分：

2. 模板中的要素齐全加1分

3. 教材学习中的问题和解决过程, （加4分）

4. 代码调试中的问题和解决过程, （加2分）

5. 周五前发博客的加1分

6. 进度条中记录学习时间与改进情况的加1分

7. 错题学习深入的加1分

8. 结对学习情况真实可信的加1分

9. 感想，体会不假大空的加1分

点评过的同学博客和代码

• 本周结对学习情况
  • 20182323

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

图的学习更加困难，主要是在遍历上，书上的代码繁多复杂，猛地看看不大懂，但如果实现理解其思路，带着自己的想法去看代码，就会事半功倍。

学习进度条

• 计划学习时间:40时

• 实际学习时间:32

参考资料

• 图的遍历

• MashMap原理

20182315 第十周学习总结

原文：https://www.cnblogs.com/zjwbk/p/11964249.html