线性表

问题导入

如何存储一个多项式？

采用数组，每个元素的 Index 代表指数，对应的 value 代表系数；
- 优点：操作方便，直接用遍历相加每个元素即可；
- 缺点：对于稀疏向量的表示，浪费存储空间，例如 $x^{2000} + 2x$
采用结构数组，每个元素有两个值，一个是指数，一个是系数；
- 优点：只表示非零项，节省空间；
- 缺点：操作稍微复杂一点，数组需要按照指数大小有序的保存；
采用链表：同上；

什么是线性表

相同类型的 数据元素 构成 有序序列 的线性结构

类型名称：线性表（List）数据对象集：线性表 $n$ 个元素构成的有序序列操作集：

表长
表头、表尾

注意：线性表是一种逻辑结构，而顺序表和链表指存储结构，两者的概念层次不同，不能混淆；

线性表的基本操作

包括：

初始化表
求表长
按值查找
按位查找
插入操作
删除操作
输出操作
判空操作
销毁操作

线性表的两种物理实现

顺序表
链表

顺序表

静态分配
动态分配

特点：

逻辑顺序和物理顺序相同；
随机访问，通过首地址和元素序号可以在 $O(1)$ 时间内找到指定元素；
存储密度高；
删除和插入需要大量移动元素；

插入

bool ListInsert(SqList &L, int i, ElemType e) {
  if (i<1 || i>L.length+1)
    return false;
  if (L.length>=MaxSize)
    return false;
  for (int j=L.length;j>=i;i--)
    L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}

复杂度分析：最好：从表尾插入， $O(1)$ 最坏：从表头插入， $O(n)$ 平均：每个位置插入概率相等，平均下来是 $O(n)$

删除

bool ListDelete(SqList  &L, int i, ElemType &e) {
  if (i<1 || i>L.length)
    return false;
  e=L.data[i-1];
  for (int j=i;j<L.length;j++)
    L.data[j-1]=L.data[j];
  L.length++;
  return true;
}

复杂度分析：同插入

按值查找（顺序表）

int LocatteElem(SqList L, ElemType e) {
  int i;
  for (i=0;i<L.length;i++)
    if （L.data[i]==e)
      return i+;
  return 0;
}

复杂度分析：同上

链表

每个节点都有一个指针数据域，指向下一个节点，这是单链表。 头指针 为 NULL 表示一个空链表； 头节点 data 数据区域为 null 的节点。可有可无，但头指针一定有。一般为了操作的实现方便，会带有头结点；

有无头结点在链表操作的实现上会产生差别。这种差别主要来源于第一个节点的判断。有头结点的链表，头指针会指向 head ，我们可以通过改变 head.next 指向下一节点来添加新节点，无论链表是否为空都是如此实现的；而没有头节点的空链表由于头指针指向 null 所以我们无法像非空链表那样，使用 head.next = node 来添加节点，所以每次插入时都需要一个特殊情况的判断，实现起来会麻烦一点。删除同理。

头插法

尾插法

按序号查找

按值查找（链表）

插入节点（前插/后插）

删除节点操作

求表长

双向链表

克服了单链表无法反向查找前驱节点的弱点。

循环链表

与单链表不同，循环链表结尾的指针不是 NULL，而是头结点。

循环双链表

头节点的前驱是尾结点，尾结点的后继是头结点；

静态链表

结合了顺序表和链表，需要一段连续的内存空间。链表的指针域存放的是这段连续的内存空间的下标。

广义表

数据域不一定是单元素，可能是另一个线性表

多重链表

一个结点不止隶属于一个链表，有多个指针域，树和网通常使用多重链表实现

十字链表

常用于存储稀疏矩阵，只存储非零元素，避免了大量零元素占据存储空间。数据域有：横坐标、纵坐标、值；指针域有：右指针和下指针；

栈

先进后出(FILO)

卡特兰数： $n$ 个不同的元素入栈，出栈元素的不同排列个数为 $\dfrac{1}{n+1} C^n_{2n}$

顺序栈

存储空间预先确定，拥有最大长度，元素之间连续。

共享栈

顺序表的两侧分别为两个栈的栈底，从两端插入到中间，使得存储空间真正被利用到；栈满条件：两个栈的栈顶指针碰撞了就是满了；

链式栈

队列

先进先出(FIFO)

顺序存储

连续存储单元，是在尾指针插入，头指针输出队列空条件：头指针等于尾指针等于零

缺陷：当队列的尾指针到达了顺序表的最大长度，就无法插入了，但是如果队列内的元素通过头指针全都取出了，队列其实还有空间，但是无法插入了，这种情况叫做“上溢出”，这也是顺序队列的缺点；

循环队列

为了解决这个缺点，我们构造循环队列，让头部和尾部连接起来；队列判空条件：头指针等于尾指针等于零队列满条件：

牺牲一个存储单元，当队头指针在队尾指针的下一个的时候，判断队满；
增加表示队列元素个数的数据成员；
增加 tag 数据成员，用以区分队满还是队空；

链式存储

不带头结点的队列的操作往往比较麻烦，通常使用带头结点的链式队列，统一空和非空的插入和删除操作。

链式存储不会产生不合理的“溢出问题”也不会出现分配不合理的情况；

双端队列

两端都可以插入删除的队列
输出受限的双端队列（有一端只能插入）
输入受限的双端队列（有一端只能删除）

可以当作是栈和队列的组合；

栈和队列的应用

栈
- 括号匹配
- 表达式求值（中缀式转后缀式）
- 递归
队列
- 层次遍历
- 计算机系统内的应用（缓冲区、任务队列、消息/请求队列）