408数据结构-线性表

1. 相关概念

线性表特点：

• 元素的数据类型相同。每个元素都占有相同大小的存储空间。

• 元素个数有限。

• 具有逻辑上的顺序性，元素有先后次序。

• 表中每个元素都是数据元素。

• 每个元素都是单个元素。

• 表中元素具有抽象性，仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容。

线性表是逻辑结构。顺序表和链表是存储结构。

线性表中元素的位序从 $1$ 开始，而数组中元素的下标从 $0$ 开始。

注意，栈和队列是操作受限的线性表，不是任何对线性表的操作都可以作为栈和队列的操作。比如不可以随便读取栈和队列中间的某个数据。

2. 存储结构

2.1 顺序表

顺序表的特点是，表中元素的逻辑顺序与其存储的物理顺序相同。

位序：$i$ 为元素 $a_i$ 在顺序表中的位序。

顺序表可以是静态分配的，也可以是动态分配的。动态分配时，如果顺序表空间用满了，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间。

插入操作平均需要移动 $\frac{n}{2}$ 个元素，删除操作平均需要移动 $\frac{n-1}{2}$ 个元素。

顺序表需要分配一块连续的存储空间，不够灵活。

$O(1)$ 空间复杂度原地逆置

可以将全部 $m+n$ 个元素先原地逆置，变成 $\left( b_n,b_{n-1},\dots,b_1,a_m,a_{m-1},\dots,a_1 \right)$，然后再分别对前 $n$ 个元素和后 $m$ 个元素分别进行原地逆置。这样可以做到空间复杂度 $O(1)$。

类似于上面那个题，先对整个序列进行原地逆置，然后再把前 $n-p$ 个元素原地逆置，后 $p$ 个元素原地逆置，做到 $O(1)$ 的空间复杂度。

$O(n)$ 时间复杂度删除所有的指定元素

可以维护两个指针，一个指针指向第一个为 $x$ 的元素，然后另一个指针去找非 $x$ 元素，找到之后就把这两个指针指向的元素交换。

2.2 链表

408 的代码题中，如果要用到链表的长度信息，那么一般要自己写代码遍历链表计算长度。

2.2.1 单链表

data 为数据域，next 为指针域。

单链表由于附加了指针域，因此也存在浪费存储空间的缺点。

是非随机存取的存储结构。

通常用头指针来标识一个单链表，头指针为 NULL 时表示一个空表。

为了操作上的方便，也可以在单链表第一个结点之前附加一个结点，称为头结点，头结点的数据域可以不设任何信息，也可以记录表长。

• 引入了头结点之后，头结点就是链表中的第一个结点了。但是单链表长度不包括头结点。
• 没有头结点的话，链表的插入和删除都需要特判。而有头结点的话就不需要。

用 ^ 符号表示指针域为 NULL。

删除结点时需要记得 free(p)。

$O(1)$ 时间复杂度对某一结点进行前插

如果给定链表中某个结点的指针，现在要在该结点前面插入元素，且需要时间复杂度为 $O(1)$。一个做法是，先直接把结点插入到后面，然后再把两个结点的数据域交换一下。

$O(1)$ 删除结点后继

直接删除结点的话需要知道目标结点的前驱。有一种不需要知道前驱也能直接删除的办法：先将被删除结点的后继的数据域复制到被删除结点，然后再把后继删除。

$O(1)$ 原地逆置

法一：枚举链表中每个结点，然后把每个结点摘下，再头插。

法二：相当于把所有结点的指针域从指向后继改为指向前驱：

$O(n)$ 找出两个单链表的公共结点

给定两个单链表，我们可以先遍历一下这两个单链表，算出他们的长度 $len_1$ 和 $len_2$。

首先判定两个链表是否有公共结点。注意到，如果两个链表存在一个公共结点，那么该结点往后的结点也全都是公共结点。因此我们遍历两个链表后，看一下最后的尾结点是否相同即可。

假设 $len_1 > len_2$，那么我们可以先在链表一上遍历 $len_1-len_2$ 个结点，然后再继续同时遍历链表一和链表二，如果发现遍历到相同结点则说明有公共结点。

$O(n)$ 判环

如果单链表中的尾结点的指针域指向了链表中的其他结点，那么我们就说这个单链表是有环的。

使用快慢指针的方法来判断：设置两个指针，快指针每次走两步，慢指针每次走一步。如果存在环的话，必定存在一个时刻，使得两个指针在环上相遇。

对称结点问题

对于结点 $i$，令其对称结点为 $n-i+1$。现在我们想在单链表上快速地对每个结点找到其对称结点。或者，对于单链表，我们经常要用到从链表两侧同时向中间靠近的这种遍历，这种也属于对称结点问题。

做法仍然是使用快慢指针。快指针每次走两步，慢指针每次走一步，这样快指针跑到最后的时候，慢指针刚好到链表的中间，然后我们将单链表的后半部分原地置逆，这样前半部分第 $i$ 个结点和后半部分第 $i$ 个结点就是对称结点了。

一遍扫描找到链表中倒数第 $k$ 个结点

追求一遍扫描的原因是，某年 408 的代码题要求一遍扫描，如果做两遍扫描的话就会扣 5 分。

但是做法仍然非常巧妙：首先设置两个指针 $p$ 和 $q$，然后 $p$ 指针先往前走 $k$ 个结点，接着 $q$ 和 $p$ 同步向前移动，当 $p$ 到达尾结点时，$q$ 恰好就是倒数第 $k$ 个结点了。

2.2.2 双链表

2.2.3 循环链表

• 循环单链表

链表中最后一个结点的指针域指向头结点。

循环单链表也分带头结点和不带头结点两种类型。

对于带头结点的循环单链表，判断链表为空要判断头结点的指针域是否指向自身。

一般用循环单链表的尾指针来表示整个链表。因为通过尾指针还能获得链表的头指针，这样的话无论是从头部插入还是从尾部插入都是 $O(1)$ 的。

• 循环双链表

最后结点的后继指针指向头结点，头结点的前驱指针指向最后结点。

2.2.4 静态链表

用数组来描述线性表的链式结构。

用在数组中的下标表示普通链表的指针。

上图中用 -1 这个特殊下标表示空指针。

主要用于一些不支持指针的高级语言（如 Basic）。

3. 栈

当 $n$ 个不同元素进栈时，出栈元素的不同排列的个数为 $\frac{1}{n+1}C_{2n}^n$。也就是卡特兰数。

3.1 存储结构

3.1.1 顺序栈

采用顺序存储的栈称为顺序栈。

当S.top==-1 的时候栈空，S.top==MaxSize-1 的时候栈满，S.top+1 为栈长。

3.1.2 共享栈

基于顺序栈。

利用栈底位置相对不变的特性，让两个顺序栈共享一个顺序表。

3.1.3 链栈

不存在栈满上溢的情况。

通常采用单链表实现。

入栈和出栈都在链表的表头进行。

3.2 应用

3.2.1 模拟队列

使用两个栈 S1 和 S2 来模拟队列。

• 对 S2 的出栈操作用做出队，如果 S2 为空则先将 S1 中的所有元素送入 S2。
• 对 S1 的入栈操作用做入队。

S1 中的元素的顺序是反的，所以借用 S2 再把顺序再给调正。

3.2.2 算术表达式

中缀表达式转后缀表达式

后缀表达式又被称为逆波兰表达式。

比如对于中缀表达式 A+B*(C-D)-E/F

手算方法：

• 首先先加括号：((A+(B*(C-D)))-(E/F))
• 然后把运算符移至对应括号的后面：((A(B(CD)-)*)+(EF)/)-
• 去除括号，得到后缀表达式：ABCD-*+EF/-

使用栈：从前往后扫描中缀表达式

• 遇到操作数时，直接加入后缀表达式
• 遇到 ( 时，直接入栈；遇到 ) 时，依次弹出栈中的运算符，并加入后缀表达式，直到弹出 ( 为止。括号本身不加入后缀表达式中。
• 遇到运算符时，不断进行下面的操作，直到当前运算符放入栈顶
  • 如果栈顶运算符的优先级大于当前运算符，则将栈顶运算符弹出，放入后缀表达式。
  • 如果栈顶运算符的优先级小于当前运算符，则将当前运算符放入栈顶。
  • 如果栈顶运算符的优先级等于当前运算符，则继续讨论当前运算符的结合性：
    • 如果是左结合的，则将栈顶运算符弹出，放入后缀表达式。
    • 如果是右结合的，则将当前运算符放入栈顶。

主要思想是，确保栈中时刻满足，( 分割出来的部分，每个部分中的运算符的优先级都是单调不降的。

中缀表达式转前缀表达式

使用栈，和转后缀表达式相同，主要区别：

• 改为从后往前扫描中缀表达式
• 遇到 ) 时，直接入栈；遇到 ( 时，依次弹出栈中的运算符，并加入后缀表达式，直到弹出 ) 为止。
• 确保栈中时刻满足，) 分割出来的部分，每个部分中的运算符的优先级都是单调不增的。

后缀表达式求值

遇到操作数时，将操作数压入栈中。遇到运算符时，从栈顶中取出两个操作数，进行运算后把运算结果再压入栈顶。

注意运算顺序。比如，当前栈中内容为 A B C D，取栈顶操作数 C 和 D，计算 C - D 而不是 D - C。

4. 队列

4.1 顺序存储

队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。（不同教材的定义是不同的，有的教材可能会令 rear 指向队尾元素）

初始时 Q.front = Q.rear = 0。

当 Q.front = Q.rear 时队列为空。

当 Q.rear == MaxSize 时，队列出现了上溢出，上溢出是一种假溢出，因为可能此时数组中仍然存在可以存放元素的空位置。

4.2 循环队列

也是顺序存储。

队首指针和队尾指针在加一之后，再对 MaxSize 取模。

队列长度为 (Q.rear - Q.front + MaxSize) % MaxSize。

队列为空的条件是 Q.front == Q.rear。但是队列为满时，也有可能出现这种情况。于是有如下三种处理方法：

• 牺牲一个存储单元来区分队空和队满，这也是一种较为普遍的做法。此时，队满的条件为 (Q.rear + 1) % MaxSize == Q.front。
• 队列的结构体中多维护一个 size 成员，表示元素个数。
• 队列的结构体中多维护一个 tag 成员，区分队满还是队空。删除成功则置 tag = 0，若导致 Q.front == Q.rear 则队列为空。插入成功则置 tag = 1，若导致 Q.front == Q.rear，则队列为满。

4.3 链队列

队列的链式表示称为链队列。

实际上是一个同时有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。

如果使用单链表，一定是要把队头设在链表的链头，否则设在队尾的话，队头删除元素时维护的时间复杂度就不对了。

对于不带头结点的链式队列，当 Q.front == NULL 且 Q.rear == NULL 时，链式队列为空。

为了实现方便，一般将链式队列设计成带头结点的单链表。

但是无论是带不带头结点，在进行删除操作时，需要特判删除后队列是否为空，是的话还需要修改尾指针。

4.4 双端队列

队列两边都可以进行插入和删除操作：

有一端受限的类型：

5. 数组和矩阵

5.1 数组

数组中的元素数据类型均相同。

数组是线性表的推广，一维数组可视为一个线性表，二维数组可视为元素是定长数组的线性表。且数组一旦被定义，维数和维界就不再改变。

对于二维数组，有两种映射方法：按行优先和按列优先。

5.2 特殊矩阵

对于特殊矩阵可以进行压缩，为多个值相同的元素只分配一个存储空间，对零元素不分配空间。

5.2.1 对称矩阵

对角线两侧的元素是对称的。

5.2.2 三角矩阵

如下图，空白部分的所有元素均为同一常量。

存储时和对称矩阵大致类似，只存上三角/下三角，然后再在最后存储常数项。

5.2.3 三对角矩阵

可以按行或者是按列优先存储在一维数组中。

5.3 稀疏矩阵

如果矩阵中非零元素个数远小于零元素个数，则称之为稀疏矩阵。

可以存储非零元素的行下标，列下标，值的三元组：

同时还需要存储稀疏矩阵的行数和列数。

6. 错题

顺序表和一维数组并不是一个逻辑结构（虽然我个人认为是一个，都是线性结构。或者说，顺序表算是一个存储结构，一维数组是一个逻辑结构，一维数组可以用顺序表实现，这样的一个关系。）

栈和队列的逻辑结构相同，都是线性结构。不同之处在于它们对数据的运算不同。

如果是无序的话，需要使用散列来做到 $O(n)$。

答案的 $O(\log_2n)$ 的做法有点抽象，没看懂。。。

不过考虑最后肯定是 A 前缀一部分和 B 前缀一部分共 $n$ 个元素。我们可以二分套二分去寻找这个情形，做到 $O(\log_2n\log_2n)$ 的复杂度。

不过貌似也可以优化成单 log。在一个序列上二分位置 $i$ 时，由于我们希望两序列前缀元素数量总共是 $n$，那么可以直接得到在另一个序列上的位置 $j=n-i$，然后判断一下是否可以满足 $A_i\le B_{j+1}$ 且 $B_j\le A_{i+1}$ （这 $n$ 个元素全都小于等于其他 $n$ 个元素）。

注意到，$n$ 个数的 mex 最大也就是 $n+1$，那么我们可以开桶来记录，做到时间复杂度 $O(n)$，空间复杂度 $O(n)$。

Ⅱ：链式存储用指针表示逻辑结构，而指针的设置是任意的，因此比顺序存储结构能更方便地表示各种逻辑结构。

注意“结点内”。

A：诚然，在单链表和顺序表上实现的时间复杂度都为 $O(n)$，但是在顺序表上实现的话需要移动很多元素，因此相比之下单链表效率稍微好一点。

这里的 L 本身就是指针了。

这里说“元素”，那么指的是 data 字段，而并非是结点的指针。

题目没说哪个链表接在前面，哪个接在后面，所以两个链表都需要 $O(1)$ 找到头结点和尾结点。

线性表长度为 0 的时候，head->next->next==head 也是可以成立的。

A：还会受到内存的限制。

其实并不需要额外记录节点是否为空，因为空闲节点一定集中在队尾。队列的队尾指针只需要指向最后一个非空闲节点就好了，入队的时候直接看后继节点是不是头节点。

这里 "C 语言的一维数组" 就表明数组从下标 $0$ 开始。