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

目录

教材学习内容总结

Chapter12 算法分析

1. 三个公式
   

• 程序 = 数据结构＋算法
  
• 软件 = 程序 + 软件工程
  
• 软件企业 = 软件 + 商业模式

1. 数据结构的三个组成部分
   

• 逻辑结构：数据元素之间逻辑关系的描述
• 存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
• 数据操作： 对数据要进行的运算
  

1. 算法效率度量

• 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作T(n)=O(f(n))，称作算法的渐近时间复杂度，简称时间复杂度。一般常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。
  

• 空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度。

Chapter14 栈

• 集合
  • 定义：一种聚集、组织了其他对象的对象。
    
  • 分类
    按保存的类型分：
    同构：集合中保存的类型全部相同。
    异构：集合中可以保存全部的类型。
    按组织的方式分（组织形式由元素添加到集合的次序或元素自身之间的一些内在关系）：
    线性集合：集合中的元素按直线方式组织。如：队列集合、栈集合。
    非线性集合：集合中的元素不按直线方式组织。如：树集
    
• 抽象数据类型(Abstract Data Type, 简称ADT)
  ADT是一种在程序设计语言中尚未定义其值和操作的数据类型。
  ADT的抽象性：ADT要对其实现的细节进行定义，而这些定义对于用户是不可见的。
  集合是由对象创建的，对象的内部对于系统其它部分来说是封装的，因此集合是一种抽象数据类型。
  
• 泛型
  • 一种可以存储、操作和管理在实例化之前没有指定类型的对象的一个类，通常用作为标识符。
  • 泛型不能被实例化，它只是一个占位符，允许我们去定义管理特定类型的对象的类。
    
• 栈
  • 栈是一种线性数据结构，采用后进先出(Last in,first out。简称LIFO)的方法处理元素
• 链式结构
  一种使用对象引用变量来创建对象之间的链接的数据结构。
  对象引用变量:对象引用变量存放的是对象的地址，表示对象的存储位置。通常而言，对象引用变量存放的地址是无关紧要的，其最重要的目的是用于访问对象。
  
• 链表
  • 定义：链表是链式结构的一种。（链表≠链式结构）
  • 类型：单链表、双向链表、循环链表
    在链表中，对象引用变量也可称为指针，链表中存储的对象泛称为结点。
    
  • 结构：
    链表需要一个单独的引用变量来作为链表的首结点。
    同时，链表需要一个从一个对象到另一个对象的引用变量，又称作自引用的，通常用next来定义。
    链表终止于其next引用为空的结点。
    
• 管理链表
  • 访问元素：访问元素的唯一方法是从第一个元素开始，遍历整个链表直至找到所需元素。
    

  //以Person类为例  
  Person current = first;
  for(int i = 0; i < n(指定整数);i++){
      current = current.next;//遍历列表
   }

  • 插入结点：插入结点需要先设置一个临时的结点用来防止指针丢失，改变引用顺序是其关键。
    

  //以Student类为例
  public static void InsertNode(Student head,Student node1,Student node3){
       Student point = head;
       while((point.number != node1.number) && point != null){
           point = point.next;
       }
       if (point.number == node1.number){
           //此处的两句绝对不能够换位置，不然可能会造成NullPointerException
           node3.next = point.next;
           point.next = node3;
       }
   }

  • 删除节点：只要使被删除结点的前一个指针指向被删除结点的后一个指针即可。

  //Student类为例
  public static void DeleteNode(Student head,Student node){
       Student pre = head, current = head;
       while (current != null){
           if (current.number != node.number){
               pre = current;
               current = current.next;
           }
       }
       pre.next = current.next;//关键步骤
   }

• ArrayStack&LinkedStack
  • ArrayStack是基于动态数组的数据结构，LinkedStack基于链表的数据结构。
    
  • 对于随机访问和改变操作集合中的元素，ArrayStack要优于LinkedStack，因为LinkedStack要移动指针。
    
  • 对于新增和删除操作，LinedStack比较占优势，因为ArrayStack要移动数据。但这一点要看实际情况的。若只对单条数据插入或删除，ArrayStack的速度反而优于LinkedStack。但若是批量随机的插入删除数据，LinkedStack的速度大大优于ArrayStack。因为ArrayStack每插入一条数据，要移动插入点及之后的所有数据。

Chapter15 队列

• 队列
  • 元素处理方式：先进先出（First In First Out,FIFO)，第一个进入的元素也将是第一个退出的元素。
  • 队头(front或head)：取出数据元素的一端。
  • 队尾(rear或tail)：插入数据元素的一端。
    队列的操作
  • enqueue(也称add或insert)：向队列末端添加一个元素
  • dequeue(也称remove或serve)：从队列前端删除一个元素
  • first(也称front)：考察队列前端的那个元素
  • isEmpty：判断队列是否为空
  • size：判断队列中的元素数目
  • toString：返回队列的字符串表示
    
• 队列的类型
  • 顺序队列
  • 循环队列
• 用链表实现队列
  • 用链表进行实现时，要设置两个引用，一个指向链表首元素的引用（head），一个指向链表末尾元素的引用（tail）。
  • enqueue()——将新元素放到链表末端

  public void enqueue(T element)
   {
       LinearNode<T> node = new LinearNode<T>(element);
       if (isEmpty()) {
           head = node;
       } 
       else {
           tail.setNext(node);
       }
       tail = node;
       count++;
   }

  • dequeue操作——从链表前端删除元素

  public T dequeue() throws EmptyCollectionException
   {
       if (isEmpty()) {
           throw new EmptyCollectionException("queue");
       }
  
       T result = head.getElement();
       head = head.getNext();
       count--;
  
       if (isEmpty()) {
           tail = null;
       }
  
       return result;
   }

• 用数组实现队列
  将队列的某一端固定在数组的索引0处。如果是单向列表，在删除元素时要移动元素，使得操作的效率很低，所以这种情况下可以使用环形数组来实现队列。
  • enqueue()

  public void enqueue(T element) {
       if (size() == queue.length) {
           expandCapacity();
       }
       queue[rear] = element;
       rear = (rear + 1) % queue.length;//关键代码：用于正确更新rear的值
       count++;
   }

  • dequeue()

  public T dequeue() throws EmptyCollectionException {
       if (isEmpty()) {
           throw new EmptyCollectionException("queue");
       }
       T result = queue[front];
       queue[rear] = null;
       front = (front + 1) % queue.length;
       count--;
       return result;
   }

  

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

• 问题1：对Java集合类API和泛型的理解
• 问题1解决方案：
  • API：API(Application Programming Interface,应用程序编程接口)是一些预先定义的函数，目的是提供应用程序与开发人员基于某软件或硬件的以访问一组例程的能力，而又无需访问源码，或理解内部工作机制的细节。运行Java程序时，虚拟机装载程序的class文件所使用的Java API class文件。所有被装载的class文件(包括从应用程序中和从Java API中提取的)和所有已经装载的动态库(包含本地方法)共同组成了在Java虚拟机上运行的整个程序。
  • 泛型类定义的泛型，在整个类中有效，如果被方法使用，那么泛型类对象明确要操作的具体数据类型后，所有要操作的类型就已经固定了。即泛型类中明确好具体类型后，整个泛型类中的所以方法都是这个类型。
  • 集合框架
    
• 问题2：ArrayList&LinkedList&Vector
• 问题2解决方案：都是List的子集
  • ArrayList：底层的数据结构使用的是数组结构。特点：查询速度快，但是删除稍慢，线程不同步。
  • LinkedList：底层使用的是链表数据结构。特点：增删速度很快，查询稍慢。
  • Vector：底层使用的是数组数据结构。特点：线程同步，被ArrayList替代了。

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

• 问题1：Android实现过程中的事件和监听器代码

• 问题1解决方案：
  监听器是一个存在于View类下的接口.
  监听器的三种实现方法：
• 方法一：在Activity中定义一个内部类继承监听器接口（这里是OnClickListener）。常见的继承方法如下：

class MyListener implements View.OnClickListener{
  @Override
  public void onClick(View v) {
      Toast.makeText(MainActivity.this,"you have clicked Button2",Toast.LENGTH_SHORT).show();
  }
}

• 方法二：实现匿名内部类。这种方法适合只希望对监听器进行一次性使用的情况，在该代码块运行完毕之后，该监听器也就不复存在了。

bt1.setOnClickListener(new View.OnClickListener() {
      @Override
      public void onClick(View v) {
          Toast.makeText(MainActivity.this,"you have clicked Button1",Toast.LENGTH_SHORT).show();
      }
  });

• 方法三：利用布局文件中的onClick属性，并在实现文件中实现该方法。注意的是这里的方法名应该和布局文件中onClick属性的方法名相同，该方法必须是public方法。

// 方法三，注意需要public方法
public void onButtonClick (View view){
  Toast.makeText(MainActivity.this,"you have clicked Button3",Toast.LENGTH_SHORT).show();
}
}

代码托管

Chapter14
Chapter15

上周考试错题总结

无考试

学习进度条

• 计划学习时间:25小时

• 实际学习时间:25小时

参考资料

• java 泛型详解-绝对是对泛型方法讲解最详细的，没有之一

• Java基础：集合类、泛型

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

原文：https://www.cnblogs.com/zdyyy/p/11787804.html