Home DS复习 Part 2
Post
Cancel

DS复习 Part 2

Stack

操作受限的线性表 (正因为是线性表所以肯定就有“顺序”和“链式”这两种存储方式). 只能在一端进行操作. LIFO.

数学性质: Catalan 数. n 个不同元素进栈, 出栈元素的不同排列的个数为 $\dfrac{1}{n+1}C_{2n}^n$.

答题时可以直接“调用”的函数:

  • void InitStack(&S)
  • bool StackEmpty(S)
  • bool Push(&S, x)
  • bool Pop(&S, &x)
  • bool GetTop(S, &x)
  • void DestroyStack(&S)

顺序栈

数组存放, 用 int top 指示栈顶下标.

1
2
3
4
5
#define MAXSIZE 100
typedef struct {
    ElemType data[MAXSIZE];
    int top;
} SqStack;

S.top 处是存储元素的. 数组从下标 0 开始存储.

  • S.top = -1 时为空栈.
  • S.top = MAXSIZE - 1 时为满栈.
  • 栈长: S.top + 1.
  • 初始: S.top = -1.
  • 入栈: S.data[++S.top] = x.
  • 出栈: x = S.data[S.top--].

共享栈

利用了栈底位置相对不变的特点. 两个栈共享一个数组, 栈底设在数组两端, 栈顶向中间增长.

1
2
3
4
5
typedef struct {
    ElemType data[MAXSIZE];
    int top1;
    int top2;
} ShStack;
  • top1 = -1 时栈 1 为空栈.
  • top2 = MAXSIZE 时栈 2 为空栈.
  • top1 + 1 = top2 时为满栈.
  • 入栈: S.data[++S.top1] = xS.data[--S.top2] = x.
  • 出栈: x = S.data[S.top1--]x = S.data[S.top2++].

链栈

Lhead 指向栈顶元素.

1
2
3
4
5
6
7
8
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {
    LinkNode *top;
    // int count;
} LinkStack;

需要注意的问题

采用非递归方式实现递归程序, 不一定非要用栈, 也可用循环, 如斐波那契数列.

栈中元素一定保持其输入顺序. 因此出栈时只可能是输入顺序的逆序.

Queue

操作受限的线性表. 只能在两端进行操作. FIFO.

队头: front, 允许删除. 队尾: rear, 允许插入.

答题时可以直接“调用”的函数:

  • void InitQueue(&Q)
  • bool QueueEmpty(Q)
  • bool EnQueue(&Q, x)
  • bool DeQueue(&Q, &x)
  • bool GetHead(Q, &x)

顺序队列

数组存放.

front 指向队头元素, rear 指向队尾元素的下一个位置.

1
2
3
4
5
6
#define MAXSIZE 100
typedef struct {
    ElemType data[MAXSIZE];
    int front;
    int rear;
} SqQueue;
  • 初始时: Q.front = Q.rear = 0.
  • 判空: Q.front == Q.rear.
  • 插入: Q.data[Q.rear++] = x;.
  • 删除: x = Q.data[Q.front++];.

存在「假溢出」, 也就是说数组中明明有位置存储, 却因 front 指针移动到数组末尾而导致无法继续插入.

改进: 循环队列.

循环队列

  • 初始时: Q.front = Q.rear = 0.
  • 插入: Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MAXSIZE.
  • 删除: x = Q.data[Q.front]; Q.front = (Q.front + 1) % MAXSIZE.
  • 元素个数: (Q.rear - Q.front + MAXSIZE) % MAXSIZE.

三种情况:

  1. 牺牲一个存储单元来区分队空和队满.
    • 队满: (Q.rear + 1) % MAXSIZE == Q.front.
    • 队空: Q.front == Q.rear.
    • 元素个数: (Q.rear - Q.front + MAXSIZE) % MAXSIZE.
  2. 类型中增加一个 Q.size 记录元素个数, 用来区分队空和队满.
    • 队满: Q.size == MAXSIZE.
    • 队空: Q.size == 0.
    • 元素个数: Q.size.
  3. 类型中增加一个 Q.tag 记录队列状态, 用来区分队空和队满.
    • 每次 EnQueue 成功后令 Q.tag = 1, DeQueue 成功后令 Q.tag = 0.
    • DeQueue 为例, 先令 Q.tag = 0, 然后执行 Q.front = (Q.front + 1) % MAXSIZE. 此时调用 QueueEmpty(Q) 进行判空: 如果 Q.front == Q.rear && Q.tag = 0, 则队列为空. 同理, 如果 Q.front == Q.rear && Q.tag = 1, 则队列为满.
    • 因此这里的 tag 实际上是表示“上一次执行”的是插入还是删除操作. 如果是执行过一次插入操作后导致的 Q.front == Q.rear, 则队列为满; 如果是执行过一次删除操作后导致的 Q.front == Q.rear, 则队列为空. 因此每调用一次 EnQueueDeQueue, 都要更新 tag.

双端队列

允许在两端进行插入和删除操作 (出队和入队) 的队列. 队列的两端分别称为前端后端.

逻辑结构是线性结构.

后端插入的可以从前端删除, 也可以从后端删除.

双端队列也是操作受限的线性表: 只允许两端插入、两端删除.

栈和队列都是双端队列的退化. 因此双端队列可以实现栈和队列的功能.

双端队列也有两个变种: (至于是哪一端其实不重要, 因为是等价的)

  • 输入受限的双端队列: 一端插入、两端删除.
  • 输出受限的双端队列: 两端插入、一端删除.

如果输入没有受限, 则双端队列中的元素不需要按照输入顺序排列.

如果输出没有受限, 则双端队列中的元素不需要按照输入顺序输出.

链式队列

链表存放.

1
2
3
4
5
6
7
8
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {
    LinkNode *front;
    LinkNode *rear;
} LinkQueue;

Stack 和 Queue 的应用

Stack:

  • 括号匹配
  • 表达式求值: 中缀表达式转后缀表达式, 后缀表达式求值
    • 中缀表达式就是 A+B*(C-D)-E/F, 写成表达式树后进行后序遍历, 就得到了后缀表达式 ABCD-*+EF/-.
    • 给出后缀表达式, 可以用栈来计算表达式的值.
    • 算法: 顺序扫描后序表达式的每一项, 如果是操作数就入栈, 如果是操作符就从栈中弹出两个操作数, 进行运算, 然后将结果入栈. 最后栈中只剩下一个元素, 就是表达式的值.
  • 递归

Queue:

  • 层次遍历
  • 计算机系统:
    • 缓冲区
    • 竞争资源的使用队列

数组

术语: 下标、维界 (下标的取值范围).

特殊矩阵的压缩存储

  • 特殊矩阵: 有大量的零元素或相同非零元素的矩阵. 如对称矩阵、上 (下) 三角矩阵、对角矩阵.
  • 压缩存储: 多个值相同的元素只存储一次.

对称矩阵

a[n*n] 的对称矩阵: 只存放半个三角形. 假设将下三角区 (a11,a21,a22,a31,a32,a33,…) 存放在一维数组 b[n(n+1)/2] 中, 则 a[i][j]b 中的位置是 b[i*(i-1)/2+j].

i>j 属于下三角区, i=j 属于主对角线, i<j 属于上三角区.

三角矩阵

三角矩阵是这样的 (以下三角矩阵为例):

1
2
3
4
5
6
7
a[n][n]={
    a11,a12,a13,...,a1n,
    c,  a22,a23,...,a2n,
    c,  c,  a33,...,a3n,
    ...,
    c,  c,  c,  ...,ann
}

这里的 c 是常数, 不一定是 0, 和线性代数里的定义不太一样.

a[n*n] 的上三角矩阵: 存放在一维数组 b[n(n+1)/2+1] 中, a[i][j], i>=jb 中的位置是 b[j*(j-1)/2+i], a[i][j], i<jb 中的位置是 b[n*(n+1)/2].

三对角矩阵

也称为带状矩阵.

三对角矩阵是这样的:

1
2
3
4
5
6
a[1][1], a[1][2], 0, 0, ..., 0,
a[2][1], a[2][2], a[2][3], 0, ..., 0,
0, a[3][2], a[3][3], a[3][4], ..., 0,
...,
0, 0, ..., a[n-1][n-2], a[n-1][n-1], a[n-1][n],
0,  0,  0,  ...,a[n][n-1],a[n][n]

可看作是有三条对角线.

存储方式: 以行优先存储.

1
a[1][1], a[1][2], a[2][1], a[2][2], a[2][3], a[3][2], a[3][3], a[3][4], ..., a[n-1][n-2], a[n-1][n-1], a[n-1][n], a[n][n-1], a[n][n]

a[i][j] 存储于 b[2i+j-3].

b[k] 对应的 a[i][j] 是 $i=\lfloor\dfrac{k+1}{3}+1\rfloor,j=k-2i+3$.

推导: 对于 a[i][j], 前面有 i-1 行, 其中第 1 行有 2 个元素, 第 2 到 i-1 行有 3 个元素, 总共有 2+3(i-2)=3i-4 个元素; 在第 i 行, 它的前面有 i-2 个 0, 它自己位于第 j 个位置, 因此是第 i 行的第 j-(i-2) 个非零元素. 于是, a[i][j]b 中是第 3i-4+j-(i-2)=2i+j-2 个元素. 如果 b 从 0 开始存储, 则位于下标 2i+j-3 处.

逆推也很简单: 已知 k, 那么就是 b 中的第 k+1 个元素. 由于除了第一行以外全都是 3 个元素, 只有第一行是 2 个, 所以暂时先从第 i 行移动一个元素补到第一行, 因此 i-1=(k+1)/3. 这里的除法按照 C++ 标准默认向下取整了, 也可以写得规范一些. i 求出来了, 再通过 k=2i+j-3 就可以求出 j 了.

稀疏矩阵

稀疏矩阵是指矩阵中大部分元素都是 0 的矩阵.

用三元组 (行, 列, 值) 存储.

十字链表法: 用两个链表存储, 一个链表存储行, 一个链表存储列.

This post is licensed under CC BY 4.0 by the author.