Fabian备忘录

人类资格证考核中

三、栈、队列、数组

发表于 更新于 分类于 ，
本文字数： 12k

栈

逻辑结构

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

几个术语：

  • 栈顶：线性表允许插入删除的那一端；
  • 栈底：固定的、不允许进行插入和删除的那一端；
  • 空栈：不含任何元素的空表；
  • 特点：后进先出（LIFO）

栈的常考题型：给定进栈顺序，判断有哪些合法的出栈顺序？n个不同元素进栈，出栈元素不同的排列顺序为，称为卡特兰数。

存储结构

顺序存储

顺序栈的实现

1
2
3
4
5
6
#define MaxSize 10   //栈的最大个数
typedef struct{   
    ElemType data[MaxSize];   //静态数组存放栈的元素
    int top;                  //栈顶指针(数组下标)
}SqStack;

  • 栈顶指针：S.top，指向栈顶元素，可以理解为数组下标，初始时S.top=-1，栈顶元素表示为S.data[S.top]
  • 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素；
  • 出栈操作：栈非空时，先找栈顶元素值，再将栈顶指针减1；
  • 栈空条件：S.top==-1
  • 栈满条件：S.top == MaxSize-1;栈长S.top+1;

基本运算代码

栈的基本运算的时间复杂度都是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//初始化
void InitStack(SqStack &S)
{
    S.top = -1;
}

//判空
bool StackEmpty(SqStack S)
{
    if(S.top == -1)
        return true;
    else
        return false;
}

//进栈
bool Push(SqStack &S, ElemType x)
{
    if(S.top == MaxSize -1)    //栈满了
        return false;

    S.top = S.top + 1;       //指针先+1
    S.data[S.top] = x;       //新元素再入栈
    return true;
}

//出栈  
//注意，出栈操作只是逻辑上被删除出栈了，但数据依旧残留在内存中
bool Pop(SqStack &S, ElemType &x)
{
    if(S.top == -1)    //栈空
        return false;

    x = S.data[S.top];    //栈顶元素先出栈
    S.top = S.top - 1;     //指针再减1
    return true;
}

//读栈顶元素
bool GetTop(SqStack S, ElemType &x)
{
    if(S.top == -1)
        return false;
    x = S.data[S.top];
    return true;
}

上述设计都是栈顶指针初始化为-1，即指向当前栈顶位置，此时入栈和出栈都需要先变更指针再操作数据；如果栈顶指针初始化为0，即指向下一个操作数的位置，那么正好相反，入栈和出栈需要先操作数据，再变更指针。

顺序栈的缺点：用静态数组存放元素，栈的大小不可改变。但如果我们一开始就分配非常大的地址空间，那么又会造成资源浪费。所以我们可以利用相对栈底位置不变的特性，让两个顺序栈公用一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延申。这个就是共享栈

1
2
3
4
5
6
7
8
9
10
11
12
13
#define Max 50
typedef struct{
    ElemType data[MaxSize];
    int top0;           //0号栈顶指针
    int top1;           //1号栈顶指针
}

//初始化
void InitStack(ShStack &S){
    S.top0 = -1;
    S.top1 = MaxSize;
}

  • top0=-1时，0号栈为空；top1=MaxSize时，1号栈为空；
  • 栈满条件：top0 + 1 == top1
  • 0号栈进栈时，top0先加1再赋值；1号栈进栈时，top1先减1再赋值；

共享栈目的：

  • 更好的利用存储空间；
  • 两个栈互相调节，只有再整个存储空间都被占满时才发生上溢；

链式存储

链式存储方式完全可以类比链表操作，只是规定了只能在链表的一端（表头）进行操作。一般规定链栈没有头结点，LHead直接指向栈顶元素。

1
2
3
4
5
typedef struct Linknode
{
    ElemType data;            //数据域
    struct Linknode* next;    //指针域
}*LiStack;

基本操作

  • InitStack(&s) ：初始化一个空栈；
  • StackEmpty(s):判断是否为空；
  • Push(&s,x):进栈；
  • Pop(&s,&x):出栈；
  • GetTop(s,&x):读栈顶元素
  • DestroyStack(&s):销毁栈并释放存储空间

栈的应用

括号匹配

计算机输入时，需要检查"()"、"[]"、"{}"这些括号是否都匹配出现。

由上图可知，连续输入左括号1、2、3，输入4的时候，3就被匹配了。即最后输入的左括号最先被匹配，正好符合后进先出的特性。可以用一个栈，遇到左括号就入栈，遇到右括号就弹出一个左括号。

算法思想：依次扫描所有字符，遇到左括号就入栈，遇到右括号则弹出栈顶元素检查是否匹配。

匹配失败的情况：

  1. 左括号单身
  2. 右括号单身
  3. 左右括号不匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//考试时用顺序栈即可，实际开发要用链栈
#define MaxSize 10
typedef struct{
    char data[MaxSize];
    int top;
}SqStack;

//考试时可以直接使用基本操作，简要说明下接口即可
void InitStack(SqStack &S);   //初始化栈
bool StackEmpty(SqStack S);   //判断是否为空
bool Push(SqStack &S, char x);  //入栈
bool Pop(SqStack &S, char &x); //出栈

//括号检测，数组内为括号序列，length为数组长度
bool BracketCheck(char str[], int length)
{
    SqStack S;
    InitStack(S);

    for(int i =0; i < length; i++){
        if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
            Push(S, str[i]);  //遇到左括号就入栈
        }
        else{
            if(StackEmpty(S))
                return false;   //扫描到右括号时栈为空，则是非法输入

            char topElem;
            Pop(S, topElem); //栈顶元素出栈

            //检测括号是否匹配
            if(str[i] == ')' && topElem != '(')
                return false;
            if(str[i] == ']' && topElem != '{')
                return false;
            if(str[i] == '}' && topElem != '{')
                return false;
        }
    }

    return StackEmpty(S);  //全部检索完成后，如果栈空才是匹配成功
}

表达式求值

上面的式子称为中缀表达式，由操作数、运算符、界限符组成。其中界限符（括号）是必不可少的，反映了计算的先后顺序，如果去掉界限符，那么整个式子的计算顺序就会发生改变。为了不用界限符也可以无歧义的表达运算顺序，产生了后缀表达式（逆波兰表达式）和前缀表达式（波兰表达式）。

  • 中缀表达式：运算符在两个操作数中间；
  • 后缀表达式：运算符在两个操作数后面；
  • 前缀表达式：运算符在两个操作数前面
中缀表达式 后缀表达式 前缀表达式
a+b ab+ +ab
a+b-c ab+c- -+abc

 

 

中缀转后缀的手算方法：

  1. 确定中缀表达式中各个运算符的运算顺序，由于运算顺序不唯一，所以后缀表达式也不是唯一的；
  2. 选择下一个运算符，按照【左操作数 右操作数 运算符】的方式组合成一个新的操作数
  3. 如果还有运算符没被处理，继续执行2

 

手算方法可能得到的后缀表达式不唯一，但对于计算机程序来说，算法的输出都是确定的。为了保证输出唯一，确定一个左优先原则：只要左边的运算符能先计算，那就优先计算左边的。

 

 

后缀表达式的手算方法：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，然后合体为一个操作数继续扫描。

可以看到，最后出现的操作数最先被运算，和栈的特性相符。

  1. 从左往右扫描下一个元素，直到处理完所有的元素；
  2. 若扫描到操作数则压入栈，并回到1，否则执行3；
  3. 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到1；
  4. 最后剩下的数就是最终的结果；

 

 

中缀转前缀的手算方法：

  1. 确定中缀表达式中各个运算符的运算顺序；
  2. 选择下一个运算符，按照【运算符 左操作数 右操作数】的方式组合成一个新的操作数；
  3. 如果还有运算符没被处理，就继续2；

右优先原则：只要右边的运算符能优先计算，就优先计算右边的。

 

用栈实现前缀表达式的计算：

  1. 从右往左扫描下一个元素，直到处理完所有元素；
  2. 若扫描到操作数则压入栈，并回到1；否则执行3；
  3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，结果压回栈顶，回到1；

 

 

1
2
3
4
5
6
7
8
9
10
11
12
//中缀表达式转后缀表达式代码

/*
从左到右处理各个元素时可能遇到的三种情况：
1、遇到操作数：直接加入后缀表达式
2、遇到界限符：遇到“(”直接入栈，遇到")"则依次弹出栈内运算符并加入后缀表达式，直到弹出"("为止，注意，"("不加入后缀表达式
3、遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到"("或栈空则停止。之后再把当前运算符入栈。

按照上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
*/


1
2
3
4
5
6
7
8
//中缀表达式的计算

/*
初始化两个栈，代表操作数栈和运算符栈（中缀转后缀+后缀表达式求值 两个算法的结合）
若扫描到操作数，则压入操作数栈
若扫描到运算符或界限符，则按照中缀转后缀相同的逻辑压入运算符栈（期间也会弹出运算符，每弹出
一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应的运算，运算结果再压回操作数栈）
*/

递归

函数调用的过程本身就符合栈的特性：最后调用的函数总是最先执行结束。真实函数执行的时候，本身也是用一个栈来存储：1、调用返回地址；2、实参；3、局部变量；

面对问题时，如果我们可以把原始问题转换为属性相同，但规模较小的问题时，就可以使用递归算法。

递归调用时，函数调用栈称为“递归工作栈”。每进入一层递归，就会将递归调用所需要的信息压入栈顶；每退出一次递归，就从栈顶弹出相应信息。所以递归层数一旦变多就可能导致栈溢出。

递归的另一个缺点是效率不高，因为递归调用中可能包含很多重复的计算。

队列

逻辑结构

队列是只允许在一端进行插入，在另一端进行删除的线性表

  • 队头：允许删除的一端
  • 队尾：允许插入的一端
  • 特点：先进先出（FIFO）

存储结构

顺序存储结构

顺序存储实现

分配一块连续的存储单元存放队列中的元素，并设置两个指针指向队头和队尾的下一个位置；

1
2
3
4
5
6
7
8
9
10
11
#define MAXSzie 10
typedef struct{
    ElemType data[MaxSize];   //静态数组存放队列元素
    int front,rear;           //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;    //初始化时，队头和队尾指针都指向0
}

上图指出了顺序队列的的操作：

  • 初始状态：front和rear都是0；
  • 入队操作：队列不满时，先将值送入队尾，然后队尾指针+1；
  • 出队操作：队不空时，先取头元素值，再将队头指针+1；
  • 判空条件：Q.front == Q.rear = 0;

注意，不能使用【Q.rear == MaxSize】来判断队列是否已满，可以看到上图虽然已经出队了，哪怕只剩最后一个元素，但此时Q.rear还是等于MaxSize，这种情况是假溢出（上溢出）。

循环队列

普通的顺序队列可能存在上溢出的情况，所以可以使用循环队列，把顺序队列臆造为一个环状空间。

  • 初始状态：Q.front = Q.rear = 0;
  • 入队操作，队尾+1取模：Q.rear = (Q.rear+1) % MaxSize
  • 出队操作，队头+1取模：Q.front = (Q.front + 1) % MaxSize
  • 获取队列长度：(rear + MaxSize - front) % MaxSize
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//队列判空
bool QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front){
        return true;
    }
    else{
        return false;
    }
}

//入队操作
bool EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear + 1) % MaxSize == Q.front)   //判断队满的条件:队尾指针的下一个位置就是队头
        return false;
    Q.data[Q.rear] = x;   //新元素插入队尾
    Q.rear = (Q.rear+1) % MaxSize;    //队尾元素+1后取模，这样可以实现循环
    return true;
}

//出队操作
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front){   //队列为空
        return false;
    }

    x = Q.data[Q.front];   //取队头
    Q.front = (Q.front + 1) % MaxSize;   //队头指针后移
    return true;
}

//获取队头
bool GetHead(SqQueue Q, ElemType &x){
    if(Q.rear == Q.front){
        return false;
    }
    x = Q.data[Q.front];
    return true;
}

上面的判断队是否满的操作，是通过牺牲一个存储单元，入队时少使用一个存储单元，判断队尾的下一个元素是否为队头，这个判断方法很常用，但也有其他的方法。

可以再定义一个元素size，来表示队列当前的长度，size初始化为0，每入队一次，size++，每出队一次，size--

1
2
3
4
5
6
#define MAXSzie 10
typedef struct{
    ElemType data[MaxSize];   //静态数组存放队列元素
    int front,rear;           //队头指针和队尾指针
    int size;                 //队列长度
}SqQueue;

也可以设置一个变量tag，标记上一次的操作，删除为0，插入为1。已知只有删除操作才可能导致队空，只有插入操作才可能导致队满

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAXSzie 10
typedef struct{
    ElemType data[MaxSize];   //静态数组存放队列元素
    int front,rear;           //队头指针和队尾指针
    int tag;                 //队列长度
}SqQueue;

//队满的条件：
front == rear && tag == 1;  //头尾指针相遇且上次操作为插入

//队空的条件
front == rear && tag == 0;  //头尾指针相遇且上次操作为删除

 

 

 

上述都是假定队尾元素指向的是下一个应该插入的位置，假设题目说的是队尾指针指向的就是尾元素，插入操作前应该先让队尾指针前移一位,再写入数据元素，初始化时，尾指针也应该指向MaxSize-1这个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
//初始化
front = 0;
rear = MaxSize - 1;

//插入
Q.rear = (Q.rear + 1) % MaxSize;
Q.data[Q.rear] = x;

//判空:队尾下一个就是队头
(Q.rear + 1) % MaxSize == Q.front;

//判满,牺牲一个存储单元的方法
(Q.rear + 2) % MaxSize == Q.front;

链式存储

本质上就是一个同时带有队头指针和队尾指针的单链表。也有带头结点的和不带头结点的。

1
2
3
4
5
6
7
8
9
10
//链式队列结点
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

//链式队列
typedef struct{
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

链式存储实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//带头结点

//初始化
void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));  //初始化时，front和rear都指向头结点
    Q.front->next = NULL;
}

//判空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear){
        return true;
    }
    else{
        return false;
    }
}

//入队
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;   //开辟空间，初始化值
    s->next = NULL;   //创造出来的其实就是链表的尾
    Q.rear->next = s;  //新结点插入到rear之后
    Q.rear = s;        //修改表尾指针
}

//出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear){  //队列判空
        return false;
    }

    LinkNode* p = Q.front->next; //对于带头结点的队列来说，front指向的是头，要删除的其实是头结点的下一个元素
    x = p->data;
    Q.front->next = p->next;  //修改头结点next指针
    if(Q.rear == p){
        //如果删除的是最后一个元素，还需要让尾结点也指向头结点
        Q.rear = Q.front;
    }
    free(p);
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//不带头结点

//初始化
void InitQueue(LinkQueue &Q){
    Q.front = NULL;
    Q.rear = NULL;
}

//判空
bool IsEmpty(LinkQueue Q){
    if(Q.front == NULL){
        return true;
    }
    else{
        return false;
    }
}

//入队
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;

    if(Q.front == NULL){
        //不带头结点的话，需要单独处理第一次插入的场景，因为初始化时头尾都是NULL
        Q.front = s;
        Q.rear = s;
    }
    else{
        Q.rear->next = s;   //新结点插入rear之后
        Q.rear = s;         //修改rear指针
    }
}

//出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == NULL)
        return false;  //空队
    LinkNode* p = Q.front;   //p指向出队的结点
    x = p->data;
    Q.front = p->next;   //修改front指针
    if(Q.rear == p){
        //需要判断删除的是否为最后一个
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(p);
    return true;
}

链式存储操作除非内存不足，否则不存在队满的情况。

双端队列

双端队列是两端都可以进行入队和出队操作的线性表。

  • 输入受限的双端队列：只允许一端插入，两端删除的线性表，做题时输入固定，看输出；
  • 输出首先的双端队列：只允许两端插入，一端删除的线性表，做题时输出固定，看输入；

基本操作

  • InitQueue(&Q):初始化队列，构造一个空队列；
  • DestroyQueue(&Q):销毁队列，释放空间；
  • EnQueue(&Q,x):入队；
  • DeQueue(&Q,&x):出队；
  • GetHead(Q,&x):读队头元素，队列的使用场景中，大多数只访问队头元素
  • QueueEmpty(Q):判断队列是否为空

队列的应用

树的层次遍历

使用队列是为了保存下一步的处理顺序：

  1. 根节点入队
  2. 若队空，则结束遍历，否则重复3
  3. 队列中第一个结点出队并访问。若有左孩则左孩入队，若有右孩则右孩入队；返回2

操作系统中的应用

  1. 系统中多个进程争抢使用有限的系统资源时，FCFS（First Come First Service）是一种常用的策略，符合队列场景；
  2. 解决主机与外部设备之间速度不匹配的问题
  3. 页面替换算法

数组

数据结构

数组定义：由n个相同类型的数据元素构成的有限序列。

一维数组：数组元素a[i]的存放地址 = 起始地址+i*sizeof(ElemType);除非题目特别说明，否则数组下标默认从0开始。

二维数组：有两种地址映射方法：

  1. 行优先存储：连续地址空间内先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素；M行N列数组中b[i][j]地址=起始地址+(i*N+j)*sizeof(ElemType)
  2. 列优先存储：连续地址空间内先列后行，先存储列号较小的元素，列号相等先存储行号较小的元素；M行N列数组中b[i][j]地址=起始地址+(j*M+i)*sizeof(ElemType)

矩阵存储

  • 普通矩阵 可用二维数组来存储普通的矩阵。注意描述矩阵的时候，行、列号通常从1开始，而数组下标通常从0开始。

 

  • 对称矩阵的压缩存储

压缩存储策略：只存储主对角线+下三角区。方法就是按照行优先原则将各个元素存入一维数组中。

一维数组分配的的大小为等差数列求和：

需要实现一个“映射”函数，把矩阵下标映射到一维数组下标中。核心思想：按照行优先原则，需要判断是第几个元素.

当ij时，可知前面有行列，则它前面有个元素，即个元素，由于数组下标从0开始，则数组下标为。

当i<j时，可以利用对称矩阵性质，把转化为.

 

  • 三角矩阵的压缩存储

例如下三角矩阵：除了对角线和下三角区外，其余元素都相同。也可以按照行优先原则，先将下三角区域的元素存入一维数组，并在最后一个位置存储常量c。

一维数组分配的的大小：

映射函数和对称矩阵相似，只是当ij时，直接取数组最后一个元素。

 

  • 三对角矩阵的压缩存储

三对角矩阵，又称带状矩阵：当时，有

压缩存储策略：按照行优先原则，只存储袋装部分即可。除了第一行和最后一行外，每一行只存3个元素，总共存储个元素。

对于来说，前行一共有个元素，是第i行第j-i+2个元素，则是第个元素

 

  • 稀疏矩阵的压缩存储

稀疏矩阵：非零元素个数远远少于矩阵元素个数。

方法1：三元组法。定义一个三元组<行，列，值>，保存矩阵中的非零元素。可以定义一个struct，然后用一维数组存储这些值。用这种方法存储后就失去了随机存取的特性。

方法2：十字链表法。定义两个数组，分别代表矩阵的行(向右域)和列(向下域)。数组中存放的是指针，向下域中每个数组项指向当前列的第一个元素，向右域中每个数组项指向当前行的第一个元素。每一个非零元素对应一个结点，结点值域中存<行，列，值>这样的三元组，同时结点中还有两个指针，分别指向当前行和当前列的下一个结点。