20172307 2017-2018-1 《程序设计与数据结构》第5周学习总结

教材学习内容总结(第十四章 栈)

概述

• 本章是在讲集合及实现集合所用的数据结构
• 介绍的集合称为栈，用栈说明集合的设计、实现及使用

14.1 集合的介绍

• 集合：是收集并组织其他对象的对象
• 分类：主要分为线性和非线性
• 非线性集合：没有任何组织方式，不是像线性集合那样将元素排成一行

14.1.1 抽象数据类型

• 抽象数据类型：简单来讲就是 数据元素（不仅限于一般的数据元素）＋对其的操作（不太严谨但有助于理解）
• 抽象数据类型（abstract data type, 简称ADT）
• 抽象数据类型可以使用一个三元组来表示：
  ADT = (D, S, P)
  其中D 是数据对象，S 是D 上的关系集，P 是加在D 上的一组操作。
  在定义抽象数据类型时，我们使用以下格式：
  ADT 抽象数据类型名{
  数据对象：
  数据关系：
  基本操作：
  }

14.2 栈集合

• 栈是一个线性集合，其元素的添加及删除都在一段进行。
• 栈的处理方式：后进先出
• push：将元素添加到栈顶
• pop：删除栈顶元素
• peek：查看栈顶元素
• isEmpty：判定栈是否为空
• size：判定栈中元素个数

14.3 继承、多态和泛型

• 多态引用使用对象的类型而不是引用的类型来判定要调用的是哪个方法

14.4 栈的ADT

• Java接口定义了一组抽象方法，能用来将抽象数据类型概念与它的实现分析
• 通过使用接口名作为返回值类型，接口机制可让方法与实现栈的具体的类分开

14.5 使用栈：计算后缀表达式

• 栈是计算后缀表达式时使用的理想数据结构

  public class PostfixEvaluator {
      private final char ADD ='+',SUBTRACT='-';
      private final char MULTIPLY='*',DIVIDE='/';
      private LinkedStack<Integer> stack;
  
      public PostfixEvaluator ()
      {
          stack=new LinkedStack <Integer> ();
      }
  
      public int evaluate (String expr)
      {
          int op1,op2,result=0;
          String token;
          Scanner tokenizer = new Scanner ( expr );
  
          while (tokenizer.hasNext ()){
              token=tokenizer.next ();
              if (isOperator(token)){
                  op2=(stack.pop ()).intValue ();
                  op1=(stack.pop ()).intValue ();
                  result=evalSingleOp(token.charAt ( 0 ),op1,op2);
                  stack.push ( result );
              }
              else
                  stack.push ( Integer.parseInt ( token ) );
  
          }
          return result;
      }
  
      private boolean isOperator(String token){
          return (token.equals ( "+" )||token.equals ( "-" )||token.equals ( "*" )||token.equals ( "/" ));
      }
  
      private int evalSingleOp(char operation,int op1,int op2){
          int result=0;
          switch (operation){
              case ADD:
                  result=op1+op2;
                  break;
  
              case SUBTRACT:
                  result=op1-op2;
                  break;
  
              case MULTIPLY:
                  result=op1*op2;
                  break;
  
              case DIVIDE:
                  result=op1/op2;
  
          }
          return result;
      }
  }

14.6 异常

• 错误和异常代表不常见或不正确的处理

14.7 使用数组实现栈

• 集合操作的实现细节不应该影响使用者与集合进行交互的方式
• 处理异常情形的方式，决定是集合还是集合的使用者来控制具体的行为

14.8 ArrayStack类

• 考虑到效率，数组实现的栈将栈底放在下标为0的位置

14.9 将引用作为链

• 可用对象引用变量来创建链式结构
• 链表由对象组成，其中每个对象指向表中的下一个对象
• 链表根据需要动态变大，本质上没有容量限制

14.10 管理链表

• 访问元素，插入结点，删除结点
• 处理链表中的第一个结点通常需要特殊处理

14.11没有链的元素

• 保存在集合中的对象不能包含所用数据结构的任何实现细节

14.12 使用链实现

• 有效实现了相关操作的集合的任何一种实现方案都能用来解决方案
• 栈的链式实现方案在链表的一端添加和删除元素

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

抽象数据类型

• 在14.1.1 抽象数据类型中看到对于抽象数据类型是这样定义的：抽象数据类型是其值和操作都没有在程序设计语言中定义的一种数据类型。它是抽象的，因为其实现细节必须要定义，而且要对用户隐藏。这个对于抽象数据类型的定义，我没有懂，所以去上网上查
• 之前在刚刚开始学习Java的时候就学习了基本数据类型，有byte，short，int，long，float，double，boolean，String。

• 用代码来理解

  /**
           * 为数据结构线性表自定义的抽象数据类型
           * 在Java中，抽象数据类可以使用接口来描述
           * 线性表接口LList，描泛型参数T表示数据元素的数据类型
           */
      public interface LList<T>     //线性表接口，泛型参数T表示线性表中的数据元素的数据类型
          {
              boolean isEmpty();        //判断线性表是否空
              int length();             //返回线性表长度
              T get(int i);             //返回第i（i≥0）个元素
              void set(int i, T x);     //设置第i个元素值为x
              void insert(int i, T x);  //插入x作为第i个元素
              void append(T x);         //在线性表最后插入x元素
              T remove(int i);          //删除第i个元素并返回被删除对象
              void removeAll();         //删除线性表所有元素
              T search(T key);          //查找，返回首次出现的关键字为key元素
          String toString();        //返回显示线性表所有元素值对应的字符串
          }

• 抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部的实现无关，即无论它的内部结构如何变化，只要它的逻辑特性不变，都不会影响到它的使用。其内部的变化（抽象数据类型实现的变化）只是可能会对外部在使用它解决问题时的效率上产生影响，因此我们的一个重要任务就是如何简单、高效地实现抽象数据类型。很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型具体表示的选择将是不同的。在这个意义下，数据模型的具体表示又依赖于数据模型上定义的那些运算。特别是，当不同运算的效率互相制约时，还必须事先将所有的运算的相应使用频度排序，让所选择的数据模型的具体表示优先保证使用频度较高的运算有较高的效率。

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

问题一

• 当程序Postfix运行的时候，输入的是String类的数据类型，想让最后显示输入的为字符，怎么弄

• 加入此段代码

  if (expression != null && expression.matches("^[0.0-100.0]+$"))  {// [0-100]没办法识别小数，[0.0-100.0]可以识别小数和整数
              System.out.println("输入是数字！");
              double num = Double.parseDouble(expression);
              System.out.println(num);
          } else {
              System.out.println("输入值为字符！");

代码托管

上周考试错题总结

结对及互评

本周结对学习情况

- [20162303](http://www.cnblogs.com/syx390234975/)
- 结对学习内容
    - 学习第十四章
    - 研究上课时讲的ppt

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

一定好好学习java！！
前一段时间有点忙，现在不怎么忙，我要专心学习

学习进度条

尝试一下记录「计划学习时间」和「实际学习时间」，到期末看看能不能改进自己的计划能力。这个工作学习中很重要，也很有用。
耗时估计的公式
：Y=X+X/N ，Y=X-X/N，训练次数多了，X、Y就接近了。

参考：软件工程软件的估计为什么这么难，软件工程 估计方法

• 计划学习时间:20小时

• 实际学习时间:20小时

(有空多看看现代软件工程 课件
软件工程师能力自我评价表)

参考资料

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

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

• JDK帮助文档

• java集合类详解