飞鸿踏雪

《数据结构》栈、队列和数组

栈

逻辑结构知识点

栈 只允许在一段进行插入或删除操作的线性表
栈顶 线性表允许进行插入删除的那一段
栈底 线性表允许进行插入删除的那一段
操作特性 先进后出
数学性质 n个不同元素进栈，出栈元素的不同排列的个数为$\frac{1}{n+1}C^n_{2n}$(卡特兰数)

存储结构知识点

栈的顺序存储结构

顺序栈的定义

  • 采用顺序存储的栈

  • 利用一组地址连续的存储单元存放字栈底到栈顶的数据元素

顺序栈的实现
1
2
3
4
5
6
7
8


#define Maxsize 50
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


Void InitStack(SqStack &S)
{
    S.top = -1;
}

判栈空

1
2
3
4
5
6
7
8


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

进栈

1
2
3
4
5
6
7
8


bool Push(SqStack &S,ElemType x)
{
    if(S.top == Maxsize -1)//栈满
        return false;
    S.data[++S.top] = x ;
    return true;
}

出栈

1
2
3
4
5
6
7
8


bool Pop(SqStack &S,ElemType x)
{
    if(S.top == -1)//栈空
        return false;
    S.data[S.top--] = x;
    return true;
}

读栈顶元素

1
2
3
4
5
6
7
8


bool GetTop(SqStack S,ElemType x)
{
    if(S.top==-1)//栈空
        return false;
    x = S.data[S.top]
    return true;
}
共享栈
  • 定义
    • 利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间
    • 将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
  • 特点
  • 目的
    • 更有效地利用存储空间
    • 两个栈的空间相互调节，只有在整个存储空间都被占满时才发生上溢
栈的链式存储结构
  • 概念
    • 采用链式存储的栈
  • 优点
    • 便于多个栈共享空间和提高其效率，且不存在栈满上溢的情况
  • 特点
    • 通常采用单链表实现，并规定所有操作都在单链表的表头进行的
    • 规定链栈没有头结点，Lhead指向栈顶元素

链式栈实现

1
2
3
4
5
6
7


typedef struct Linknode
{
    Elemtype data;//存放栈中元素
    struct Linknode *next;//栈顶指针

}* LiStack;

栈的运算/操作

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

栈的应用

括号匹配

  • 初始设置一个空栈，顺序读入括号
  • 若是右括号，置于栈顶
  • 若是左括号，压入栈中
  • 算法结束时，栈为空，否则括号序列不匹配

表达式求值

后缀表达式和正常表达式的相互转换

中缀到后缀表达式转换的过程

递归

  • 在递归调用的过程，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储
  • 递归次数过多容易造成栈溢出
  • 将递归算法转换为非递归算法，通常需要借助栈来实现这种转换，消除递归不一定需要栈
  • 效率不高，原因是递归调用过程中包含很多重复的计算
  • 代码简单，容易理解

队列

逻辑结构知识点

队列 操作受限的线性表
队头 允许删除的一端
队尾 允许插入的一端
操作特性 先进先出

存储结构知识点

队列的顺序存储结构

顺序队列的定义
  • 分配一块连续的存储单元存放队列中的元素
  • 设两个指针
    • 队头指针front指向队头元素
    • 队尾指针rear指向队尾元素的下一个位置
顺序队列的实现

1
2
3
4
5
6
7


#define MaxSize 50
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;
初始状态 Q.front ==Q.rear = 0
队满操作 Q.rear == MaxSize不能作为队列满的条件
只有一个元素仍满足该条件（假溢出）
进队操作 队不满时，先送值到队尾元素，再将队尾指针加1
出队操作 队不空时，先取队头元素值，再将队头指针加1
循环队列的定义
  • 把存储队列元素的表从逻辑上视为一个环
循环队列的实现

区分循环队列队空还是队满
方法一 方法二 方法三
定义 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，约定以队头指针在队尾指针的下一位置为作为队满的标志 类型中增设表示元素个数的数据成员 类型中增设tag数据成员，以区分是队满还是队空
队空条件 Q.front == Q.rear Q.size==0 tag=0且因删除导致Q.front == Q.rear
队满条件 (Q.rear+1)%MaxSize == Q.front Q.size == MaxSize tag=0且因插入导致Q.front==Q.rear
元素个数 (Q.rear - Q.front + MaxSize)%MaxSize
循环队列的操作代码

初始化

1
2
3
4
5


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

判队空

1
2
3
4
5
6
7
8


bool isEmpty(SqQueue Q)
{
    if(Q.rear == Q.front)
        return true;
    else
        return false;
}

入队

1
2
3
4
5
6
7
8
9


bool EnEmpty(SqQueue &Q,ElemType x)
{
    if ((Q.rear + 1)% MaxSize == Q.front)
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

出队

1
2
3
4
5
6
7
8
9


bool DeEmpty(SqQueue &Q,ElemType &x)
{
    if(Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.font + 1) % MaxSize;
    return true; 
}

队列的链式存储结构

链式队列的定义
  • 实质是一个同时有队头指针和队尾指针的单链表
  • 头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个节点
  • 删除操作时，通常仅需要修改头指针
  • 当队列只有一个元素时，删除后队列为空，修改尾指针为rear = front
链式队列的实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


typedef struct LinkNode
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct
{
    LinkNode * front,*rear;
}LinkNode;
链式队列的操作代码

初始化

1
2
3
4
5
6


void InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
    Q.front ->next = NULL;
}

判队空

1
2
3
4
5
6
7
8


bool isEmpty(LinkQueue Q)
{
    if(Q.rear == Q.front)
        return true;
    else
        return false;
}

入队

1
2
3
4
5
6
7
8
9


bool EnEmpty(LinkQueue &Q,ElemType x)
{
    LinkNode *s = (LinkNode * )malloc(sizeof(LinkNode));
    s->data =x;
    s->next = NULL;
    Q.rear->next =s;
    Q.rear = s;
}

出错

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


bool DeEmpty(LinkQueue &Q,ElemType &x)
{
    if(Q.rear == Q.front)
        return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return true;
}
双端队列
  • 定义
    • 允许两端都可以进行入队和出队操作的队列
    • 将队列的两端分别称为前端和后端
  • 特点
    • 其元素的逻辑结构仍是线性结构
  • 分类
    • 输出受限的双端队列
      • 允许在一段进行插入和删除，但在另一端只允许插入的双端队列
      • 输出固定，看输入
    • 输入受限的双端队列
      • 允许在一段进行插入和删除，但在另一端只允许删除的双端队列
      • 输入固定，看输出

队列的运算/操作

InitQueue(&Q) 初始化队列 构造一个空队列Q
QueueEmpty(Q) 判队列为空 空则返回True
EnQueue(&Q,x) 入队 若队列未满，将x加入，使之成为新的队尾
DeQueue(&Q,&x) 出队 若队列非空，删除表头元素，并用x返回
GetHead(Q,&x) 读队头元素 若队列非空，则将队头元素赋值给x

队列的应用

层序遍历

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

计算机系统中的应用

  • 解决主机与外部设备之间速度不匹配的问题
  • 解决由多用户引起的资源竞争问题
  • 页面替换算法（FIFO算法）

数组和特殊矩阵

  • 重点
    • 如何将矩阵更有效地存储在内存中，并能方便地提取矩阵的元素
  • 定义
    • 由n个相同类型的数据元素构成的有限序列
  • 特点
    • 数组一旦被定义，其维数和维界就不再改变
    • 除结构的初始化和销毁外，数组只会由存取元素和修改元素的操作
  • 数组的数据结构
    • 一个数组的所有元素在内存中占用一段连续的存储空间
    • 多维数组有两种映射方法
      • 按行优先
        • 先行后列，先存储行号较小的元素，行号相等先存储列好较小的元素
      • 按列优先
        • 先列后行，先存储列号较小的元素，列号相等先存储行号较小的元素
  • 特殊矩阵相关概念
    • 压缩存储
      • 为多个值相同的元素只分配一个空间，对零元素不分配存储空间，其目的是节省存储空间
    • 特殊矩阵
      • 具有许多相同矩阵元素或者零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵
      • 常见的特殊矩阵有对称矩阵、三角矩阵（第一行和最后一行两个元素，其余行3个元素）、对角矩阵
      • 常考某个值对应的行和列（特殊法代指就好，可用线代知识解决）
  • 特殊矩阵的压缩存储方法
    • 找到特殊矩阵中值相同的矩阵元素的分布规律
    • 把这些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中
  • 稀疏矩阵的定义
    • 非0元素非常少的矩阵
  • 稀疏矩阵的特点
    • 稀疏矩阵压缩存储后便失去了随机存取特性
    • 可以使用三元组表和十字链表法压缩存储稀疏矩阵