1、定义

零个或多个数据元素的有限序列。

2、抽象数据类型

  1. ADT 线性表 （List）
  2. Data
  3.     数据对象集合
  4. Operation
  5.     InitList(*L): 初始化，建立空的线性表L
  6.     ListEmpty(L): 判空，为空则为true，反之false
  7.     ClearList(*L): 清空线性表
  8.     GetElement(L,i,*e): 返回线性表L中的第i位置的元素返回给e
  9.     LocateElement(L,e): 查找与e相等的元素，如果查找成功，返回该元素的序号，否则，返回0。
  10.     ListInsert(*L,i,e): 插入新元素，将线性表L中的第i位置插入新元素e。
  11.     ListDelete(*L,i,*e): 删除线性表L中第i个位置的元素，并用e返回其值。
  12.     ListLength(L): 返回线性表L的元素个数。
  13. endADT

3、顺序存储结构

  • 定义

线性表的存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

  • 存储方式

一维数组来实现顺序存储结构

  1. 存储的空间的起始位置：数据data，它的存储位置就是存储空间的存储位置
  2. 线性表的最大存储容量：数组长度MaxSize
  3. 线性表的当前长度：length。
  • 数据长度与线性表长度的区别

（使用数组来表示线性表的顺序存储）
数据长度：存放线性表的存储空间的长度，存储分配后一般不变。
线性表长度：线性表数据中的元素个数

在任意时刻，线性表的长度应该小于或等于数组的长度。

  • 地址计算方法

地址：存储器中的每一个存储单元都有自己的编号。

由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC：表示获得存储位置的函数）： LOC(ai+1) = LOC(ai) + c 所以对于第i个数据元素ai的存储位置可以由ai推算得出： LOC(ai)= LOC(ai+1) + (i - 1) * c

4、顺序存储结构的插入与删除

  • 插入操作
    • 算法思路
      • 如果插入位置不合理，抛出异常
      • 如果线性表长度大于等于数组长度，抛出异常或扩大容量
      • 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
      • 将要插入的元素填入位置i处
      • 表长度加1
  • 删除操作
    • 算法思路
      • 如果删除位置不合理，抛出异常
      • 取出删除元素
      • 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
      • 表长减1
  • 线性表顺序存储结构的优缺点：
    • 优点：
      • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
      • 可以快速地存取表中任一位置的元素
    • 缺点：
      • 插入和删除操作需要移动大量元素
      • 当线性表长度变化较大时，难以确定存储空间的容量
      • 造成存储空间的碎片

5、线性表的链式存储结构

  • 链式定义

  • 头指针与头结点的异同

    • 头指针
      • 指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
      • 头指针具有标识作用，所以常用头指针冠以链表的名字
      • 无论链表是否为空，头指针均不为空。
      • 头指针是链表的必要元素
    • 头结点
      • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
      • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
      • 头结点不一定是链表必须要素

        6、单链表的读取，插入与删除

  • 单链表整表创建

    • 算法思路
      • 声明一结点p和计数器变量i
      • 初始化一空链表L
      • 让L的头结点的指针指向NULL
      • 循环
        • 生成一新结点赋值给p
        • 随机生成一数字赋值给p的数据域p->data
        • 将p插入到头结点与前一新结点之间
  • 单链表读取
    • 算法思路：
      • 声明一个结点p指向链表第一个结点，初始化j从1开始；
      • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
      • 若到链表末尾p为空，则说明第i个元素不存在
      • 否则查找成功，返回结点p的数据
  • 单链表插入
    • 算法思路
      • 声明一个结点p指向链表第一个结点，初始化j从1开始
      • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
      • 若到链表末尾p为空，则说明第i个元素不存在
      • 否则查找成功，在系统中生成一个空结点s
      • 将数据元素e赋值给s->data
      • 单链表的插入标准语句：s->next = p->next; p->next = s;
      • 返回成功
  • 单链表删除
    • 算法思路
      • 声明一结点p指向链表的第一个结点，初始化j从1开始
      • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
      • 若到链表末尾p为空，则说明第i个元素不存在
      • 否则查找成功，将欲删除的结点p->next赋值给q
      • 单链表的删除标准语句p->next = q->next
      • 将q结点中的数据赋值给e，作为返回
      • 释放q结点
      • 返回成功
  • 单链表整表创建
    • 算法思路
      • 声明一结点p和计数器变量i
      • 初始化一空链表L
      • 让L的头结点的指针指向NULL
      • 循环
        • 生成一新结点赋值给p
        • 随机生成一数字赋值给p的数据域p->data
        • 将p插入到头结点与前一新结点之间
  • 整表删除
    • 算法思路
      • 声明一结点p和q
      • 将第一个结点赋值给p
      • 循环
        • 将下一个结点赋值给q
        • 释放p
        • 将q赋值给p

          7、单链表结构与顺序存储结构优缺点

          | 存储分配方式 | 时间性能 | 空间性能 | | —- | —- | —- | |
          - 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
          - 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
          | 查找
          - 顺序存储结构O(1)
          - 单链表O(n)
          插入和删除
          - 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
          - 单链表在线出某位置的指针后，插入和删除时间仅为O(1)

          |
          - 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢出
          - 单链表不需要分配存储空间，只要有就可以分配，元素个数不受限制

          |

8、静态链表

  • 定义

用数组描述的链表叫做静态链表

首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每一个下表都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。

  • 插入

  • 删除

  • 静态链表的优缺点

    • 优点
      • 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点
    • 缺点
      • 没有解决连续存储分配带来的表长难以确定的问题
      • 失去了顺序存储结构随机存取的特性

        9、循环链表

  • 定义

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称为循环链表。

  • 操作

    10、双向链表

  • 定义

在单链表的每一个结点中，在设置一个指向其前驱结点的指针域。

  • 操作