--- title: "《数据结构》栈、队列和数组" date: 2023-07-30T14:53:00+08:00 --- ## 栈 ### 逻辑结构知识点 |栈|只允许在一段进行插入或删除操作的线性表| |---|---| |栈顶|线性表允许进行插入删除的那一段| |栈底|线性表允许进行插入删除的那一段| |操作特性|先进后出| |数学性质|n个不同元素进栈，出栈元素的不同排列的个数为$\frac{1}{n+1}C^n_{2n}$(卡特兰数) ### 存储结构知识点 #### 栈的顺序存储结构 ##### 顺序栈的定义 * 采用顺序存储的栈 * 利用一组地址连续的存储单元存放字栈底到栈顶的数据元素 ##### 顺序栈的实现 ```c #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| ##### 顺序栈基本运算代码 初始化 ```c Void InitStack(SqStack &S) { S.top = -1; } ``` ---- 判栈空 ```c bool StackEmpty(SqStack S) { if (S.top == -1)//栈空 return true; else return false; } ``` --- 进栈 ```c bool Push(SqStack &S,ElemType x) { if(S.top == Maxsize -1)//栈满 return false; S.data[++S.top] = x ; return true; } ``` --- 出栈 ```c bool Pop(SqStack &S,ElemType x) { if(S.top == -1)//栈空 return false; S.data[S.top--] = x; return true; } ``` --- 读栈顶元素 ```c bool GetTop(SqStack S,ElemType x) { if(S.top==-1)//栈空 return false; x = S.data[S.top] return true; } ``` ##### 共享栈 * 定义 * 利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间 * 将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸 * 特点 * ![](../../images/408/《数据结构》栈、队列和数组/共享栈特点.jpg) * 目的 * 更有效地利用存储空间 * 两个栈的空间相互调节，只有在整个存储空间都被占满时才发生上溢 ##### 栈的链式存储结构 * 概念 * 采用链式存储的栈 * 优点 * 便于多个栈共享空间和提高其效率，且不存在栈满上溢的情况 * 特点 * 通常采用单链表实现，并规定所有操作都在单链表的表头进行的 * 规定链栈没有头结点，Lhead指向栈顶元素 链式栈实现 ```c 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占用的存储空间| ### 栈的应用 #### 括号匹配 * 初始设置一个空栈，顺序读入括号 * 若是右括号，置于栈顶 * 若是左括号，压入栈中 * 算法结束时，栈为空，否则括号序列不匹配 #### 表达式求值 后缀表达式和正常表达式的相互转换 ![](../../images/408/《数据结构》栈、队列和数组/后缀表达式和正常表达式的相互转换.jpg) --- 中缀到后缀表达式转换的过程 ![](../../images/408/《数据结构》栈、队列和数组/中缀到后缀表达式转换的过程.jpg) #### 递归 * 在递归调用的过程，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储 * 递归次数过多容易造成栈溢出 * 将递归算法转换为非递归算法，通常需要借助栈来实现这种转换，消除递归不一定需要栈 * 效率不高，原因是递归调用过程中包含很多重复的计算 * 代码简单，容易理解 ## 队列 ### 逻辑结构知识点 |队列|操作受限的线性表| |---|---| |队头|允许删除的一端| |队尾|允许插入的一端| |操作特性|先进先出| ### 存储结构知识点 #### 队列的顺序存储结构 ##### 顺序队列的定义 * 分配一块连续的存储单元存放队列中的元素 * 设两个指针 * 队头指针front指向队头元素 * 队尾指针rear指向队尾元素的下一个位置 ##### 顺序队列的实现 ![](../../images/408/《数据结构》栈、队列和数组/顺序队列的实现.jpg) ```c #define MaxSize 50 typedef struct { ElemType data[MaxSize]; int front,rear; }SqQueue; ``` |初始状态|Q.front ==Q.rear = 0| |---|---| |队满操作|Q.rear == MaxSize不能作为队列满的条件
只有一个元素仍满足该条件（假溢出）| |进队操作|队不满时，先送值到队尾元素，再将队尾指针加1| |出队操作|队不空时，先取队头元素值，再将队头指针加1| ##### 循环队列的定义 * 把存储队列元素的表从逻辑上视为一个环 ##### 循环队列的实现 ![](../../images/408/《数据结构》栈、队列和数组/循环队列的实现.jpg) ##### 区分循环队列队空还是队满 ||方法一|方法二|方法三| |---|---|---|---| |定义|牺牲一个单元来区分队空和队满，入队时少用一个队列单元，约定以队头指针在队尾指针的下一位置为作为队满的标志|类型中增设表示元素个数的数据成员|类型中增设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||| ##### 循环队列的操作代码 初始化 ```c void InitQueue(SqQueue &Q) { Q.rear = Q.front =0; } ``` --- 判队空 ```c bool isEmpty(SqQueue Q) { if(Q.rear == Q.front) return true; else return false; } ``` --- 入队 ```c 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; } ``` --- 出队 ```c 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 ##### 链式队列的实现 ```c typedef struct LinkNode { ElemType data; struct LinkNode *next; }LinkNode; typedef struct { LinkNode * front,*rear; }LinkNode; ``` ##### 链式队列的操作代码 初始化 ```c void InitQueue(LinkQueue &Q) { Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode)); Q.front ->next = NULL; } ``` --- 判队空 ```c bool isEmpty(LinkQueue Q) { if(Q.rear == Q.front) return true; else return false; } ``` --- 入队 ```c 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; } ``` --- 出错 ```c 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| ### 队列的应用 #### 层次遍历 使用队列是为了保存下一步的处理顺序 ![](../../images/408/《计网》应用层/层次域名空间.png) #### 计算机系统中的应用 * 解决主机与外部设备之间速度不匹配的问题 * 解决由多用户引起的资源竞争问题 * 页面替换算法（FIFO算法） ## 数组和特殊矩阵 * 重点 * 如何将矩阵更有效地存储在内存中，并能方便地提取矩阵的元素 * 定义 * 由n个相同类型的数据元素构成的有限序列 * 特点 * 数组一旦被定义，其维数和维界就不再改变 * 除结构的初始化和销毁外，数组只会由存取元素和修改元素的操作 * 数组的数据结构 * 一个数组的所有元素在内存中占用一段连续的存储空间 * 多维数组有两种映射方法 * 按行优先 * 先行后列，先存储行号较小的元素，行号相等先存储列好较小的元素 * 按列优先 * 先列后行，先存储列号较小的元素，列号相等先存储行号较小的元素 * 特殊矩阵相关概念 * 压缩存储 * 为多个值相同的元素只分配一个空间，对零元素不分配存储空间，其目的是节省存储空间 * 特殊矩阵 * 具有许多相同矩阵元素或者零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵 * 常见的特殊矩阵有对称矩阵、三角矩阵（第一行和最后一行两个元素，其余行3个元素）、对角矩阵 * 常考某个值对应的行和列（特殊法代指就好，可用线代知识解决） * 特殊矩阵的压缩存储方法 * 找到特殊矩阵中值相同的矩阵元素的分布规律 * 把这些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中 * 稀疏矩阵的定义 * 非0元素非常少的矩阵 * 稀疏矩阵的特点 * 稀疏矩阵压缩存储后便失去了随机存取特性 * 可以使用三元组表和十字链表法压缩存储稀疏矩阵