抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

🔑数据结构_第三章：栈、队列和数组

编程

发布于：2023年3月11日

🔑数据结构_第三章：栈、队列和数组

第三章：栈、队列和数组

（一）栈

1、什么是栈

  • 栈是只允许在一端进行插入或删除的线性表。

    • 栈顶top：线性表允许进行插入删除的那一端。

    • 栈底buttom：固定的，不允许插入和删除的那一端。

    • 空栈：不含任何元素的空表。

    • 特性：先进后出。

    • 栈的数学性质：n个不同元素进栈，出栈元素不同的排列个数为：
      $$
      \frac{1}{n+1}C^n_{2n}
      $$
      这个公式称为卡特兰数，可用数学归纳法证明，有兴趣的同学可以自己动手试试()。

2、栈的基本操作

  • InitStack(&s)：初始化一个空栈。
  • StackEmpty(s)：判空，空则返回true，否则返回false。
  • Push(&S, x)：进栈/入栈，若栈S未满，则将x加入使之成为新栈项。
  • Pop(&S, &x)：出栈/弹栈，若栈非空则弹出栈顶元素并用x返回。
  • GetTop(&S, &x)：读栈顶元素，若栈非空则用x返回栈顶元素。
  • DestroyStack(&S)：销毁栈，并释放掉栈S所占用的存储空间。

在解答算法题时，若题干未做出函数限制，则可以直接使用这些基本的操作函数。

3、用顺序存储结构实现栈——顺序栈

（1）栈的定义

用一组地址连续的存储单元存放所有元素，同时附设一个指针top指示当前栈顶元素的位置。

1
2
3
4
5
#define Maxsize 50				//定义栈中元素的最大个数
typedef struct{
    ElementType data[Maxsize];	//用一个数组存放栈中元素
    int top;					//栈顶“指针”
} SqStack;
  • 注：栈顶指针初始化时默认值可以是-1也可以是0，若为-1，那么data[top]就是用索引值来访问元素，若为0，那么data[top]就是用位序值来访问。
  • 我们可以用data[top]访问当前栈顶元素，用data[Maxsize-1]定位到元素数组末尾（判满能用得到）。
（2）初始化操作

初始化时设置S.top=-1，栈顶元素S.data[S.top]。

1
2
3
void InitStack(SqStack &S){
    S.top = -1;
}
（3）判空
1
2
3
bool StackEmpty(SqStack S){
    return (S.top == -1);
}
（4）进栈

栈不满时，栈顶指针先+1，再将入栈元素放进去，最后返回操作成功与否。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool Push(SqStack &S, ElemType x){
    //先判栈满
    if(S.top == Maxsize-1)
        return false;
    //不满再入栈
    S.top++;
    S.data[S.top] = x;
    /*
    大佬写的代码：
    S.data[++S.top] = x;
    */
    return true;
}
（5）出栈

先判空，再执行。

先取栈顶元素值，再指针自减一。

1
2
3
4
5
6
bool Pop(SqStack &S, ElemType x){
    if(S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}
（6）读取栈顶元素

先判栈空，再执行。

1
2
3
4
5
6
7
//使用调用者的x记录读取元素的值：
bool GetTop(SqStack S, ElemType &x){
    if(S.top == Maxsize-1)
        return false;
    x = S.data[S.top];
    return true;
}
（7）*共享栈
  • 就是把两个栈，栈顶对栈顶放在同一片连续的存储空间里（比如数组），各自的栈底都处在空间的两头，空间的占用是从两头向中间延伸，只有当整个存储空间存满时才会发生上溢。
  • 存取数据的时间复杂度为O(1)，所以对存取效率没什么影响。
image29d8c9c0929031aa.png

4、用链式存储结构实现栈——链栈

  • 采用连式存储的栈，称为链栈。

  • 优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况。

  • 通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

  • 栈的链式存储类型可描述为：

    1
    2
    3
    4
    typedef struct Linknode{
        ElemType data;				//数据域
        struct Linknode *next;		//指针域
    } *LiStack;						//栈类型定义

  • 基本操作的实现与单链表基本相同，只不过链栈的插入删除等只在表头进行，因此代码实现需要的方法更少更简单而已。

  • 同样，对于带头结点和不带头结点的链栈，实现起来同链表一样需要考虑头结点。

（二）队列

1、队列的基本概念

（1）定义
  • 队列简称队，也是一种操作受限的线性表。它只允许在表的一端插入、另一端删除。
  • 插入元素称为入队或进队，删除元素称为出队或离队。
  • 特点：先进先出，后进后出，尾进头出。
  • 以下代码演示中，我们用front表示队首指针，用rear表示队尾指针，并且规定，队首指针始终指向第一个数据域，队尾指针指向最后一个数据域的下一个位置，而初始化队空时，俩指针都指向初始位置（当然也可以规定尾指针rear指向最后一个元素本身的位置，怎么习惯怎么来）。
（2）常见基本操作
  • InitQueue(&Q)：初始化队列，构造一个空队列。
  • QueueEmpty(Q)：判空。
  • EnQueue(&Q, x)：入队，若队Q未满，则将x加入使之成为新队尾。
  • DeQueue(&Q, &x)：出队，若队非空，则将队头元素赋值给x，再将队头元素删除。
  • GetHead(Q, &x)：读队头元素，若队非空，则将队头元素赋值给x。

2、队列的实现——顺序存储结构

（1）普通顺序存储

  • 定义

    1
    2
    3
    4
    5
    #define Maxsize 50						//定义最大个数
    typedef struct {
        ElemType data[Maxsize];				//用数组存储元素
        int front, rear;					//定义队头指针和队尾指针
    } SqQueue;

  • 初始化

    1
    Q.front = Q.rear = 0;

  • 进队：若队不满，先送值到队尾元素，再将队尾指针+1。

  • 出队：若队非空，先取队头元素值，再将队头指针+1。

  • 出现的问题：俩指针挪到队尾就G了，前头的空间没使用，出现假溢出的情况。解决方法——使用循环队列。

（2）循环队列

解决队首指针挪到队尾就动不了的方法：当队首指针到达队尾——即Q.front = Maxsize-1时，重置指针Q.front = 0。

  • 初始化

    1
    2
    3
    void InitQueue(SqQueue &Q){
        Q.front = Q.rear = 0;
    }

  • 判队空

    • 当循环队列存满时，尾指针rear指向尾元素的下一个元素——头元素，此时头尾指针相同，我们无法判断队列状态为空还是满。

    • 对此，我们有三种解决方案：

      • 少用一个存储单元，不让它真正的存满，这样子队尾指针永远在最后一个元素的下一位置，且不会和队首指针重合。这也是较为普遍的一种做法：

        1
        2
        3
        4
        5
        //队满条件：
        (Q.rear+1)%Maxsize == Q.front;

        //队空条件：
        Q.rear == Q.front;

      • 结构体中增设元素个数标识Q.size，初始化值为0，每次入队Q.size++，每次出队Q.size--，这样队满队空只需判断Q.size的值即可：

        1
        2
        3
        4
        5
        //队满：
        Q.size == Maxsize;

        //队空：
        Q.size == 0;

        后面的算法我都用这种方法来实现！

      • 结构体中增设队满队空标识Q.tag，初始值为0。

        每次入队前先将tag值赋为1，每次出队前赋为0。

        tag等于0时，若因出队导致Q.front == Q.rear，则为队空；tag等于1时，若因入队导致Q.front == Q.rear，则为队满。

        1
        2
        3
        4
        5
        6
        7
        //出队前判空
        Q.tag = 0;
        Q.front++;
        if(Q.front==Q.rear && tag==0)
            return false;

        //入队前判满

        不行，没搞懂

  • 入队（从队尾）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool EnQueue(SqQueue &Q, ElemType x){
        //入队前判满
        if(Q.size == Maxsize-1)
            return false;
        //未满，入队
        Q.data[Q.rear++] = x;
        //更改Q.size
        Q.size++;
        return true;
    }

  • 出队（从队首）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool DeQueue(SqQueue Q, ElemType &x){
        //出队前判空
        if(Q.size == 0)
            return false;
        //不空，出队
        x = Q.data[Q.front--];
        //更改Q.size
        Q.size--;
    }

3、队列的实现——链式存储结构

（1）定义

队列的链式存储称为链队列，实际上是一个同时带有头指针和尾指针的单链表，头指针指向第一个结点，尾指针指向尾结点而不是尾结点之后的区域，入队从尾指针操作，出队从头指针操作。

以下演示均为带头结点的栈队列。

1
2
3
4
5
6
7
8
9
10
//定义结点——经典的链表节点
typedef struct LinkNode{
    ElemType data;				//经典数据域data
    struct LinkNode *next;		//经典链表指针域next
}*LinkNode;

//定义链队列
typedef struct{
    LinkNode *front, *rear;
}*LinkQueue;
（2）初始化
1
2
3
4
5
6
void InitQueue(LinkQueue &Q){
    //建立头结点
    Q.front = Q.rear = (LinkQueue*)malloc(sizeof(LinkNode));
    //头结点指针域默认为空
    Q.front->next = NULL;
}
（3）判空

因为链队列空间是动态分配的，所以一般不用考虑空间溢出的问题，且当Q.rear = Q.front时表示队列空。

1
2
3
bool IsEmpty(LinkQueue Q){
    return (Q.front == Q.rear);
}
（4）入队

队尾入队，不用判满，直接创建结点→更改队尾指针即可。

1
2
3
4
5
6
7
8
void EnQueue(LinkQueue &Q, ElemType x){
    //创建结点
    LinkQueue *s = (LinkQueue*)malloc(sizeof(LinkNode));
    //插入队列
    Q.rear->next = s;
    Q.rear = s;
    s->next = NULL;
}
（5）出队

队首位置操作出队，需要先判空，将出队内容返还给调用者提供的x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(IsEmpty(Q))
        return true;
    x = Q.front->data;
    LinkQueue *p = Q.front->next;
    Q.front->next = p->next;
    /*
    到这一步还需判断我们删除的结点是不是唯一的一个结点（不算头结点），
    如果是，那么还得更改尾指针rear = front，否则free掉空间后队空了但是尾指针不等于front，野了！
    */
    if(p == Q.rear)
        Q.rear = Q.front;
    free(p);
    return true;
}

4、双端队列

（1）普通双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，如下图，其元素的逻辑结构仍是线性结构。

image29d8c9c0929031aa.png

将队列的两端分别称为前端和后端，两端都可以入队和出队。

入队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。

出队时，无论前端还是后端，先出的元素排列在后出的元素的前面。

（2）受限的双端队列
①输出受限的双端队列

允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。

②输入受限的双端队列

允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。

若我们限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就成了两个栈底相邻接的栈。

实际双端队列的考题不会很复杂，通常仅判断序列是否满足题设条件，带入验证即可。

（三）栈和队列的应用

1、在括号匹配中的应用

多个大小括号组合在一起，输入左括号相当于压栈，输入右括号，如果与栈顶左括号匹配，那直接消解弹栈，如果不匹配则说明输入非法， 报错。

1
2
3
4
5
6
//基本算法思想
/*
1.初始一个空栈，顺序读入括号;
2.若是左括号，则压栈，若是右括号，则判断与栈顶括号能否匹配消解，能则消消乐，不能则报错;
3.算法结束时，栈为空，否则括号序列不匹配。
*/

2、栈在表达式求值中的应用

书本此处讲的主要是针对*后缀表达式*的求值操作。

后缀表达式：后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

从左到右遍历进栈，一直到最终获得结果。遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

  • eg：中缀表达式A+B*(C-D)-E/F写成后缀表达式为ABCD-*+EF/-，它的运算过程详细如下：

    步 扫描项 项类型 动作 栈中内容
    1 初始化空栈 空
    2 A 操作数 进栈 A
    3 B 操作数 进栈 A、B
    4 C 操作数 进栈 A、B、C
    5 D 操作数 进栈 A、B、C、D
    6 - 运算符 C、D出栈，计算C-D，计算结果R1进栈 A、B、R1
    7 * 运算符 B、R1出栈，计算B*R1，计算结果R2入栈 A、R2
    8 + 运算符 A、R2出栈，计算A+R2，计算结果R3入栈 R3
    9 E 操作数 进栈 R3、E
    10 F 操作数 进栈 R3、E、F
    11 / 运算符 E、F出栈，计算E/F，计算结果R4入栈 R3、R4
    12 - 运算符 R3、R4出栈，计算R3-R4，计算结果R5入栈 R5

3、栈在递归中的应用

程序调用自身，用少量代码解决某些难题，但通常效率不是很高。

递归次数过多容易造成栈溢出。

书中以斐波那契数列为例：
$$
\begin{equation}
Fib(n)=
\left { \begin{aligned}
Fib(n-1)+Fib(n-2), n>1 \
1, n=1 \
0, n=0
\end{aligned} \right.
\end{equation}
$$
这是典型的一个递归的例子，用程序实现如下：

1
2
3
4
5
6
7
8
int Fib(int n){						//斐波那契数列的实现
    if(n==0)
        return 0;					//边界条件
    else if(n==1)
        return 1;					//边界条件
    else
        return Fib(n-1) + Fib(n-2);	//递归表达式
}

该递归执行过程：

graph TD
id01["Fib(5)"]
id02["Fib(4)"]
id03["Fib(3)"]
id04["Fib(3)"]
id05["Fib(2)"]
id06["Fib(2)"]
id07["Fib(1)"]
id08["Fib(2)"]
id09["Fib(1)"]
id10["Fib(1)"]
id11["Fib(0)"]
id12["Fib(1)"]
id13["Fib(0)"]
id14["Fib(1)"]
id15["Fib(0)"]
id01 --- id02 & id03
id02 --- id04 & id05
id04 --- id08 & id09
id08 --- id14 & id15
id05 --- id10 & id11
id03 --- id06 & id07
id06 --- id12 & id13

必须注意递归模型不能是循环定义的，其必须满足下面的两个条件：

  • 递归表达式(递归体)。
  • 边界条件(递归出口)。

递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。

可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。

4、队列在层次遍历中的应用

有时候我们需要对数据逐层操作，比如二叉树的逐层遍历，这时候可以用队列结构。

graph TD
A((A))-->B((B))
A((A))-->C((C))
    B((B))-->D((D))
        D((D))-->G((G))
    C((C))-->E((E))
        E((E))-->H((H))
        E((E))-->I((I))
    C((C))-->F((F))

该想法的逻辑：

  1. 根结点入队。
  2. 若队空（所有结点都已处理完毕），则结束遍历；否则重复操作3。
  3. 队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回操作2。

层次二叉树遍历的过程：

序 说明 队内 队外
1 A入 A
2 A出，B、C入 B、C A
3 B出，D入 C、D A、B
4 C出，E、F入 D、E、F A、B、C
5 D出，G入 E、F、G A、B、C、D
6 E出，H、I入 F、G、H、I A、B、C、D、E
7 F出 G、H、I A、B、C、D、E、F
8 G、H、I出 A、B、C、D、E、F、G、H、I

5、队列在计算机系统中的应用

队列在计算机系统中的应用场景很多，以下仅举例两处：

  1. 主机与打印机的通信

    主机发送文件的速度比打印机打印的速度要快得多，通常会设置一个打印数据缓冲区，主机很快地把数据发给打印机，然后扭头去做其他事让打印机慢慢处理，打印缓冲区中所存储的数据就是一个队列。

  2. CPU，操作系统通常按照每个请求在时间上的顺序，把它们排成一个队列，让CPU按照该队列完成各项请求。这样既可以满足不同程序或用户的请求，又能使CPU正常运行。

（四）数组和特殊矩阵

此处，我们研究如何将矩阵更有效地存储在内存中，并能方便的提取矩阵中的元素。

  • 什么是数组

    1. 数组（Array）是有序的元素序列。
    2. 若将有限个相同的类型变量的集合命名，那么这个名称称为数组名。
    3. 组成数组的各个变量称之为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分各个元素的数字下标称为元素下标或索引值（从0开始而不是1）。
    4. 这种有序排列的同类数据元素的集合称为数组。

  • 什么是矩阵

    1. 矩阵（Matrix）是一个按照长方阵排列的复数或实数集合，最早来自于方程组的系数及常数所构成的方阵。
    2. 矩阵是二维数据组成的。

  • 数组和矩阵的区别

    1. 数组中的元素可以是字符或字符串，而矩阵只能是数。
    2. 矩阵是二维的，而数组可以是n维的。
    3. 矩阵显示时元素之间无逗号，数组元素之间用逗号隔开。

1、简单数组的定义与存储结构

  • 定义：

    数组是由n个相同类型的元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称之为数组的维界。

    数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变，因此，除了数组结构的初始化和销毁外，数组只有存取元素和修改元素的操作。

存储结构：

大多数计算机语言都提供了数组数据类型，其物理结构与逻辑结构相同，一个数组的所有元素在内存中占用一段连续的存储空间。

（1）对于一维数组

以一维数组A[0...n-1]为例，其存储结构关系式为：
$$
LOC(a_i) = LOC(a_0) + i \times L，(0 \le i < n)
$$
其中，L是每个数组元素所占的存储单元（下同）。

（2）对于多维数组（包含普通矩阵）

对于多维数组的存储方式，有两种映射方法：按行优先存储和按列优先存储。

下面就以二维数组为例描述。

①按行优先存储

基本思想是先按照多维数组的行号来读取存储元素，先存储行号较小的元素，行号相同时先存储列号较小的元素。

设某二维数组的行下标与列下标的范围分别是[0,h1]与[0,h2]，则存储结构关系式为：
$$
LOC(a_{i,j}) = LOC(a_{0,0}) + \left [ i \times (h_2 + 1) + j \right ] \times L
$$
例如数组A[2][3]，它按行优先存储的结果如下图所示：

后文中的数组或矩阵若无特别说明则一致采取该存储方式。

②按列优先存储

同上，按列优先存储就是按列优先存储。其存储结果关系式为：
$$
LOC(a_{i,j}) = LOC(a_{0,0}) + \left [ j \times (h_1 + 1) + i \right ] \times L
$$
例如数组A[2][3]，它按列优先存储的结果如下图所示：

3、特殊矩阵的压缩存储

  • 压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，其目的是节省存储空间。

  • 特殊矩阵：指具有许多相同元素或零元素，并且这些相同矩阵元素或零元素的分布有一定的规律性的矩阵。

    常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。

  • 特殊矩阵的存储方法：

    找出特殊矩阵中值相同的元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩到一个存储空间中。

（1）对称矩阵
  • 是一个方阵，行数=列数！

  • 定义：若对一个n阶矩阵A中的任意一个元素ai,j的值，都有ai,j = aj,i（1<=i, j<=n），则称其为对称矩阵。

  • 其中的元素可以划分为三部分，即上三角区、主对角线和下三角区，如图：

对于n阶对称矩阵而言，上三角区和下三角区存放的对应数据是一样的，如果我们还采取多维数组存放所有数据元素的话那会浪费将近一半的存储空间，所以，我们只将主对角线元素和上三角区（或下三角区）的元素储存。

  • 数组大小应为多少：

    第一行存储一个元素，第二行两个，第三行三个……以此类推，第n行存储n个，那么数组总长应为1+2+3+...+n，即：
    $$
    \frac {(1+n) \times n}{2}
    $$

重点：我们还需要实现一个将某个元素的『矩阵内坐标』与『数组下标』对应转换的一个函数：

下面按照行优先存储、数组下标从0开始的情况实现：

①i,j→k

对于矩阵内元素ai,j，与他的数组B下标k对应：

ai,j在数组B中的下标k = ai,j之前的总元素个数 = 之前各行元素数量的和+自己所在的列数：
$$
k=1+2+…(n-1)+j-1\ \ \ \ \ →\ \ \ \ \ k=\frac{i(i-1)}{2}+j-1
$$

②k→i,j
（2）三角矩阵
image.png

与对称矩阵几乎无异，只是需要在数组最后加一个元素存储常量C而已，同时对位置映射函数稍加改动即可。

（3）三对角矩阵/带状矩阵

当|i-j|>1时，有ai,j=0，即只有对角线方向有三条线的数据。

5b86d03d229ecf995f590526b6bc59ce.png $$ k=2i+j-3\\ i \ge (k+2)/3，向上取整；或i \le (k+1)/3+1，向下取整\\ j=k-2i+3 $$
（4）稀疏矩阵

只有很少个元素的值不为0。

imagec9910ca2da777c04.png
①采用“三元组”压缩存储策略
imagebaa8901ba659a443.png

缺点：不能随机读写。

②十字链表法
image.png

**总结：

imagea08a64703c02e489.png

更新于：2024年5月13日

数据结构

算法

评论