第三章-栈和队列
2022年7月28日大约 5 分钟
3.1 栈 Stack
1.栈的基本概念
- a.栈的定义
- 栈是只允许在一端进行插入或删除操作的线性表
- b.特性：后进先出 Last In First Out, LIFO
- c.栈的数学性质：卡特兰数 Catalan Number
| | <-- 栈顶（top)
| |
| ... |
| b |
| a | <-- 栈底（bottom）
+-----+
2.栈的基本操作
- InitStack(&S)：初始化操作
- DestroyStack(&S)：销毁栈操作 []
- StackEmpty(S)：判定 S 是否为空栈
- StackLength(S)：求栈的长度 cpp::std::stack::size
- GetTop(S, &e)：取栈顶元素 cpp::std::stack::top
- ClearStack(&S)：栈置空操作 cpp::std::stack::empty
- Push(&S, e)：入栈操作（压栈）cpp::std::stack::push
- Pop(&S, &e)：出栈操作（弹栈）
3.栈的顺序存储结构
- 1.结点的类型定义
#define MAXSIZE 100
typedef struct {
ElemType data[MAXSIZE];
int top; // 栈顶指针
} SqStack;
- 2.顺序栈的基本运算
- 初始化
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.data [++top] == x; return true; }- 出栈
bool Pop(SqStack &S,ElemType &x) { if(S.top == -1) return false; x = S.data[S.top--]; return true; }- 读栈顶元素
bool GetTop(SqStack &S,ElemType &x) { if(S.top == -1) return false; x = S.data[S.top]; } - 3.共享栈
- 两个顺序栈共享一个一维数组空间
- 栈底在两端，栈顶向中间拓展
4.栈的链式存储结构
- 1.结点的类型定义
- 链栈没有头结点
typedef struct StackNode {
SElemType data;
struct StackNode *next;
} StackNode, *LinkStack;
3.2 队列 Queue
1.队列的定义
- 队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除
- 向队列中插入元素称为入队或进队
- 删除元素称为出队或离队
- 特性：先进先出 First In First Out, FIFO
2.队列常见的基本操作
- InitQueue(&Q)：初始化队列
- DestoryQueue(&Q)：销毁队列
- ClearQueue(&Q)：清空队列
- QueueLength(Q)：求队列长度
- GetHead(Q,&e)：得到队头元素
- EnQueue(&Q, e)：插入元素
- DeQueue(&Q, &e)：删除元素
3.队列的顺序存储结构
- a. 结点类型定义
#define MaxSize 100 // 最大队列长度
typedef struct{
ElemType data[MaxSize]; // 初始化的动态分配存储空间
int front; // 队头指针
int rear; // 队尾指针
} SqQueue;
4.循环队列
- 利用模运算（%）
- 为了区分是队空还是队满，有三种处理方式
- 牺牲一个单元来区分队空和队满
- 类型中增设表示元素个数的数据成员
- 类型中增设 tag 数据成员
5.循环队列的操作
- 1.初始化
void InitQueue(SqQueue &Q){
Q.front = Q.rear = 0;
}
- 2.判队空
bool isEmpty(SqQueue Q){
if(Q.rear == Q.front) return true; // 队空
else return false;
}
- 3.入队
bool EnQueue(SqQueue &Q, ElemType e){
if((Q.rear+1) % MAXSIZE == Q.front) return false; // 队满
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return true;
}
- 4.出队
bool DeQueue(SqQueue &Q, QElemType &e){
if(Q.rear == Q.front) return false; // 队空
e = Q.data[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return true;
}
6.队列的链式存储结构
- a. 结点类型定义
typedef struct {
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
7.链式队列的基本操作
- 1.初始化
void InitQueue(LinkQueue &Q){
Q.front = Q.rear = (LinkQueue*)malloc(sizeof(LinkNode)); //建立头结点
Q.front -> next = NULL;
}
- 2.判队空
bool isEmpty(LinkQueue Q){
if(Q.front == Q.rear)
return true;
else return false;
- 3.入队
void EnQueue(LinkQueue &Q, ElemType x){
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s; //核心 物理连接
Q.rear = s; //队尾指针改变
}
- 4.出队
void DeQueue(LinkQueue &Q, ElemType &x){
if(Q.front == Q.rear)
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;
}
8.双端队列
- 双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构
- 将队列的两端分别称为前端和后端，两端都可以入队和出队
- 输出受限的双端队列：允许在一端进行插入和删除，另一端只允许插入
- 输入受限的双端队列：允许在一端进行插入和删除，另一端只允许删除
3.3 栈和队列的应用
- 1.栈在括号匹配中的应用
- 2.栈在表达式求值中的应用
- 前缀表达式
- 中缀表达式
- 后缀表达式
- 3.栈在递归中的应用
- 斐波那契数列
// 斐波那契数列的实现
int Fib(int n){
if(n==0) return 0; // 边界条件
if(n==1) return 1; // 边界条件
return Fib(n-1) + Fib(n-2); // 递归表达式
}
- 4.递归模型必须满足下列两个条件
- 递归表达式（递归体）
- 边界条件（递归出口）
- 队列在层次遍历中的应用
- 队列在计算机系统中的应用
3.4 特殊矩阵和压缩存储
- 数组的定义
- 数组是由 n 个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素
- 类型定义
typedef elemtype array2[m][n];
// or
typedef elemtype array1[n];
typedef array1 array2[m];
举例说明
int array[3][3] = {1, 2, 3, 4}
结论
- 线性表结构是数组结构的一个特例
- 而数组结构又是线性表结构的扩展
特点
- 结构固定：定义后，维数和维界不再改变
基本操作
- 除了结构的初始化和销毁之外，只有取元素和修改元素值的操作
数组的存储结构
- 压缩存储
- 特殊矩阵
- 对称矩阵
- 三角矩阵
- 三对角矩阵
稀疏矩阵(三元组)
- 数组存储
- 十字链表法存储
Loading...