REST

线性表（6学时）

1. 线性表(线性表的定义，顺序存储结构，链式存储结构)

   1. 线性结构的数据元素序列满足
      1. 除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；
      2. 第一个数据元素没有前驱数据元素；
      3. 最后一个数据元素没有后继数据元素。

      4. 本章至第5章讨论的线性表、堆栈、队列、串和数组都属于线性结构。

   2. 线性表是一种可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0, a1,…, an-1组成的线性结构。
   3. 一个有n个数据元素a0, a1,…, an-1的线性表通常用符号（a0, a1,…, an-1）表示，其中符号ai（0≤i≤n-1）表示第i个抽象数据元素。
   4. 空线性表用符号()表示。
   5. 线性表抽象数据类型(复习：抽象数据类型(Abstract Data Type, ADT)：一个逻辑概念上的类型和这个类型上的操作集合。)
      1. 数据集合:序列 a0, a1, … , an-1 ，ai的数据类型为任意的类类型。
      2. 操作集合:
         1. 求当前数据元素个数size()
         2. 插入数据元素insert(i, obj)
         3. 删除数据元素delete(i)
         4. 取数据元素getData(i)
         5. 线性表是否空isEmpty()
      3. 线性表抽象数据类型的Java接口定义

2. 顺序表(顺序表类的设计方法，顺序表插入和删除操作的实现方法，顺序表插入和删除操作的时间复杂度)

   1. 顺序表：顺序存储结构的线性表。
   2. 实现顺序存储结构的方法是使用数组。
   3. 数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。
   4. 数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。
   5. 顺序表类
      1. 类包含成员变量和成员函数。
      2. 类的成员变量用来表示抽象数据类型的数据集合，
      3. 类的成员函数用来表示抽象数据类型的操作集合。
      4. 顺序表类实现接口List。
      5. 顺序表类的public成员函数主要是接口List中定义的成员函数。
   6. 顺序表的效率分析
      1. 算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作(最深层语句频度) :T(n)= O(移动元素次数)
      2. 而移动元素的个数取决于插入或删除元素的位置i
      3. 插入和删除是顺序表中时间复杂度最高的成员函数。
      4. 插入时，主要的耗时部分是循环移动数据元素部分，循环移动数据元素的效率和插入的位置i有关
         1. 若i=size，则根本无需移动（特别快）；
         2. 若i=0，则表中元素全部要后移（特别慢）；
         3. 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。
         4. 此处PPT02，p12对时间复杂度进行了计算，结论如下：
      5. 顺序表中的其余操作都和数据元素个数n无关，
         1. 在顺序表中插入和删除一个数据元素成员函数的时间复杂度为O(n),
         2. 其余成员函数的时间复杂度都为O(1)
   7. 优缺点
      1. 主要优点：算法简单，支持随机读取，内存空间单元利用率高；
      2. 主要缺点：需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。
      3. 思考：顺序表适用场合

3. 单链表LinList(单链表类的设计方法，单链表插入和删除操作的实现方法，单链表插入和删除操作的时间复杂度，顺序表和单链表的特点对比)

   1. 基础知识
      1. 指针表示一个数据元素逻辑意义上的存储位置。
      2. 链式存储结构是基于指针实现的。
      3. 把一个数据元素和一个指针称为一个结点。
      4. 链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。
      5. 链式存储结构的线性表称为链表。
      6. 根据结点构造链的方法不同，链表主要有单链表、单循环链表和循环双向链表三种。这样，一个数据元素集就可以用链式存储结构来存储。
   2. 单链表的结构
      1. 单链表中构成链表的结点只有一个指向直接后继结点的指针域。
      2. 其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。
      3. 结点结构图示p17
         1. 数据域：存储元素数值数据
         2. 指针域：存储直接后继的存储位置
      4. 带头结点的单链表结构多了个头指针
         1. 头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；
         2. 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。
         3. 首元结点是指链表中存储线性表第一个数据元素a０的结点。
      5. 带头结点单链表和不带头结点单链表的比较****区别
         1. 当选用带头结点的单链表时，在第一个结点前插入结点时，不会改变头指针head的值，改变的是head所指的头结点的指针域值，当临时指针变量p等于head时，改变的是p.next的值，这和在其他结点前插入结点的过程相同；
         2. 若选用不带头结点的单链表，在第一个结点前插入结点时，头指针head的值将改变为新插入的结点的指针，而在其他结点前插入结点时head的值不会改变，改变的是p.next的值；
         3. 删除操作也存在相同的问题。

   3. 结点类Node设计见教材

   4. 单链表类LinList的定义见教材P27

   5. 单链表的效率分析
      1. 单链表插入和删除操作的时间复杂度均为O(n)。
      2. 单链表取数据元素操作的时间复杂度也为O(n)。
   6. 单链表和顺序表相比区别
      1. 主要优点：不需要预先确定数据元素的最大个数，插入和删除操作不需要移动数据元素；
      2. 主要缺点：每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。

      3. 思考：单链表适用场合

4. 循环单链表(循环单链表和循环双向链表的结构和特点)

   1. 结构特点：
      1. 循环单链表是单链表的另一种形式
      2. 结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。
      3. 优点：
         1. 从链尾到链头比较方便。
         2. 当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。
      4. 循环单链表也有带头结点和不带头结点两种结构
   2. 带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅在于：区别
      1. 在构造函数中，要加一条head.next = head 语句，把初始时的带头结点的循环单链表设计成图2-11(a)所示的状态。
      2. 在index(i)成员函数中，把循环结束判断条件current != null改为current != head。

      3. 循环单链表类CLinkList实现见补充教材P25

      4. 约瑟夫（丢手绢）问题见补充教材P28

5. 双向链表

   1. 双向链表是每个结点除后继指针域外还有一个前驱指针域，
   2. 它有带头结点和不带头结点，带头结点的双向链表更为常用；
   3. 双向链表也可以有循环和非循环结构，循环结构的双向链表更为常用。
   4. 双向链表是解决查找前驱结点问题的有效途径。
   5. 结构：
      1. 在双向链表中，每个结点包括三个域，分别是element域、next域和prior域，
      2. 其中element域为数据元素域，
      3. next域为指向后继结点的对象 引用，
      4. prior域为指向前驱结点的对象引用。
      5. p40双向链表结点的图示结构。

6. 仿真链表

   1. 结构
      1. 在链式存储结构中，实现数据元素之间的次序关系依靠指针。
      2. 也可以用数组来构造仿真链表。
      3. 方法是在数组中增加一个（或两个）int类型的变量域，这些变量用来表示后一个（或前一个）数据元素在数组中的下标。
      4. 这些int类型变量构造的指针是仿真指针。可以用仿真指针构造仿真的单链表（或仿真的双向链表）。
      5. p47，结构图

7. 面向对象的软件设计方法

   1. 面向对象软件设计方法是一种和人类认识事物、分析事物方法一致的软件设计方法。
   2. 面向对象设计方法的模块化软件、数据封装、信息隐藏等特点，还可以使软件设计可以像其他工业产品一样，可以大规模协作开发。
   3. 模块化软件设计的基本思想是：把基础软件设计成可重复使用的模块，这些模块提供外部调用的接口，其他程序通过接口使用这些基础软件模块。
   4. 这样，软件工业将摆脱了小作坊工作方式，像现代的其他工业一样，可以进行大规模的协作生产或开发。

8. 举例设计

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。