20172314 2017-2018-2 《程序设计与数据结构》第十周学习总结

教材学习内容总结

  • 集合与数据结构
    集合是一种对象，可以专用于保存元素并提供增添、删除等管理所保存元素的服务。

  • 集合的同构与异构

    • 同构：意味着保存类型全部相同的对象。
    • 异构：集合可以保存各种类型的对象。

  • 分离接口与实现

    • 抽象数据类型（ADT）：数据和在该数据上所实施的具体操作构成的集合。一个ADT有名称、值域、和一组允许执行的操作。ArrayList提供一个抽象数据类型。
    • 集合和ADT是可以互换的等同概念。
    • 对象具有定义良好的接口，从而成为一种实现集合的完善机制。

  • 数据结构的动态表示

    • 动态结构

      • 扩容不是扩展现有空间，而是重新申请空间并将已有的元素复制过去，这样会造成空间的浪费。
      • 一个动态数据结构用链来实现，利用对象引用作为连接对象间的链。
      • 动态数据结构的大小规模随需要增长和收缩。
      • 通过保存和更新对象引用来实现一个链表管理，实例化两个Node对象，使一个对象的next指向另一个对象，从而将两个对象链接在一起。第二个对象的引用变量又可指向第三个Node对象，以此类推。其中第一个节点可单独用一个变量来引用（如list），最后一个的引用变量next设为null，链表结束。

      • 对象引用是一个存储对象地址的变量，引用也被称为指针。对象引用常用于创建对象间的链接，可以创建链式结构，如链表。

    • 动态链接的列表

      • 链表中插入一个节点

      • 链表中删除一个节点

    • 其他的动态列表

      • 双向链表中，每个节点不仅含有一个指向后一节点的引用，而且还有一个指向前一节点的引用。

      • 双向链表使在链表中向前向后移动的操作很方便。

  • 线性数据结构

    • 线性数据结构是顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

    • 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列（但实际上不一定必须是相同数据类型）

    • 队列

      • 先进先出方式管理数据
      • 相关方法

    • 堆栈

      • 堆栈元素后进先出方式管理数据。
      • 相关方法

  • 非线性数据结构

    • 树
      树由一个根节点和构成层次结构的多个节点组成。除根节点以外的称内部结点，没有子节点的称叶节点。根节点在树的顶层，叶节点在底层。
      • 图
        • 图是一种非线性数据结构，使用边来连接节点，且边是双向的，连接的两个点可以相互追溯。
        • 有向图的每条边有特定的方向。
        • 可以用数组和动态链实现图，但常使用后者。

  • Java集合类API

    • Java集合类API定义了几种以不同方式实现的集合类。
    • 泛型
      • Java集合类API中的类定义为泛型，指一个集合所管理的对象类型要在实例化改集合对象时才确定。
      • 泛型保证了集合中对象类型的兼容性。
        * 指定集合中的对象储存类型保证只有适当类型的对象可以添加到集合中，并且由于集合中对象类型已经建立，因此将一个对象移出集合时不需要类型转换。

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

  • 问题一：节点是什么意思。

  • 问题一解决：可以说是结构体，节点就是一个带有指针指向的结构体，把相邻的点关联起来，可以把链表想象成火车，节点就是其中一节节的车厢，通过通道和前后车厢相连。节点的具体使用例如：

    private Node(String data,Node next){  
this.data = data;  
this.next = next;  
}  

private void addToHead(String data){  
Node n = new Node(data,null);  
n.next = this.head;  
this.head = n;  
}

    上述代码的意思是Node n = new Node(data,null); 一个新进来的节点，没有next。n.next = this.head; 新节点的next设置成head 。 this.head = n; 把当前节点设置成head 。

  • 问题二：看不懂书上例13.2MagazineList类的add方法。

  • 问题二解决：参考理解

    public void add(Magazine mag)//这方法应该是添加对象到当前表
{
	MagazineNode node =new MagazineNode(mag);//通过mag初始化MagazineNode对象
	MagazineNode current;//新建一个指示当前对象的Node实例。
	
	if(list ==null)//如果当前表为空，当前对象为表头。
	list = node;//对表头赋值。
	
	else//若当前表不为空。
		{
			current = list;//置current为表头。
			while(current.next !=null)//寻找表尾。
			{
			current = current.next;//current后移。
			}//循环退出，current记录当前表尾。
	current.next = node;//将新结点加入到当前表末尾。
	}
}

  • 问题三：为什么对象特别适于实现抽象数据类型。

  • 问题三解决：书上的解释是：抽象数据类型是一个包含数据和施加在这些数据上的操作的集合。对象实际上就是将变量和相关的方法封装在一起的事体。对象隐藏了ADT背后的实现细节，并且将接口和底层的实现相分离，使得实现发生变化后不影不影响接口。我感觉解释比较抽象,参考了网上的解释，觉得要通俗一点。抽象数据类型和面向对象是什么关系？

抽象数据类型是类的基础. 废话一点就是抽象出来的数据类型. 面向对象就是以对象的方式实现数据的抽象.但是使用不好, 对象有可能不是"抽象数据类型", 只是一堆杂乱的方法和数据属性的堆砌. 比如 class Dog{ leg legs[4]; void run()}算是adt, 但是 class Utils { void log(string info), string getBaseDir()} 这种完全算不上adt.

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

  • 问题一：在做13.3遇到问题。

  • 问题一解决：最开始想到使用Scanner类让用户输入整数建立一个链表，然后对其进行排序。

    但是没有将其继续实现。然后套用课堂测试的修改过的Magazine类进行修改，但在输出时却出现了输出三次的问题，且为竖列，只有中间一段是排过序的，

    发现是在排序后有多余的一条指令System.out.println(sort);并将println换为print，toString语句中的“ ”换为“ ”即可。


  • 问题二：想要实现链表的删除操作时，总是输出同样的结果显示无法删除。

  • 问题二解决：在多次检查代码没有发现问题后，进行了调试，发现进入delete方法后，直接执行完

if( !current.magazine.equals(delNode) && current.next == null) {  
    System.out.println("找不到节点，删除失败！");//最后一个也不是要插入的地方  
}

这一步操作就结束进程。在询问了助教之后，发现原因在于current.magazine与delNode不可以直接比较，要加上.toString。改为如下即可

if( !current.magazine.toString().equals(delNode.toString()) && current.next == null) {  
    System.out.println("找不到节点，删除失败！");//最后一个也不是要插入的地方  
}

代码托管实验代码

上周考试错题总结

  • 错题一：

  • 错题一解决：我认为是因为递归调用会使问题远离基本情况，答案是因为递归调用不会使参数更接近基本情况。如果一开始n就符合情况大于0，那么他返回的递归仍然是正确的，所以无限递归。那我的答案和正确答案的意思的区别就在于我的是使问题远离，但是递归是一直停留在原地的，所以选择不会更接近更贴切一点。

结对及互评

点评：

  • 博客中值得学习的或问题：
    * 王禹涵的博客问题记录非常详细，很认真，错题总结细致，博客中图文并茂。
    * 谭鑫的博客在教材内容总结中加入了图片解释，对于问题的描述细致，解决问题的过程记录详细，思路明晰。

  • 基于评分标准，我给谭鑫的博客打分：9分。得分情况如下：

    • 进度条中记录学习时间与改进情况的加1分
    • 代码Commit Message规范的加1分
    • 错题学习深入的加1分
    • 结对学习情况真实可信的加1分
    • 问题加分5分
  • 基于评分标准，我给王禹涵的博客打分：10分。得分情况如下：
    • 排版精美的加一分
    • 有动手写新代码的加1分
    • 代码Commit Message规范的加1分
    • 错题学习深入的加1分
    • 结对学习情况真实可信的加1分
    • 问题加分5分

点评过的同学博客和代码

  • 阅读13章节
  • 代码托管到git@OSC，参考一下使用开源中国托管代码
  • 完成课后自测题，并参考答案学习
  • 完成课后练习题
  • 完成程序设计项目：至少完成PP13.1、PP13.3.

其他

这周学习了这本书的最后一章，感觉这本书学的很快，自己就是过了一遍，没有特别深入学习，并且有些知识已有遗忘。但是这周把四则运算结束后顿时感觉轻松了一点，之后的学习中还是要更加努力去完成的。

学习进度条

代码行数（新增/累积） 博客量（新增/累积） 学习时间（新增/累积）
目标 5000行 30篇 400小时
第一周 200/200 2/2 20/20
第二周 300/500 2/4 18/38
第三周 500/1000 3/7 22/60
第四周 300/1300 2/9 30/90
第五周 795/2407 1/6 30/120
第六周 1117/2921 1/7 30/150
第七周 703/3511 1/8 40/190
第八周 1139/4701 2/10 40/230
第九周 681/5382 2/12 40/270
第十周 1977/7359 2/14 30/300

参考：

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/YiYiYi/p/9063859.html