文章目录
- 1. 栈
- 1.1 栈的基本概念
- 1.2 栈的基本操作
- 1.3 栈的顺序存储实现
- 1.4 栈的链式存储实现
- 2. 队列
- 2.1 队列的基本概念
- 2.2 队列的基本操作
- 2.3. 队列的顺序存储实现
- 2.4 队列的链式存储实现
- 2.5 双端队列
- 3. 栈与队列的应用
- 3.1 栈在括号匹配中的应用
- 3.2 栈在表达式求值中的应用
- 3.3 栈在递归中的应用
- 3.4 队列的应用
- 4. 特殊矩阵的压缩存储
1. 栈
1.1 栈的基本概念
- 栈是特殊的线性表：只允许在一端进行插入或删除操作，其逻辑结构与普通线性表相同。
- 栈顶：允许进行插入和删除的一端 （最上面的为栈顶元素）。
- 栈底：不允许进行插入和删除的一端 （最下面的为栈底元素）。
- 空栈：不含任何元素的空表。
特点：后进先出（后进栈的元素先出栈）、LIFO（Last In First Out）。
缺点：栈的大小不可变，解决方法：共享栈。
1.2 栈的基本操作
- InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
- DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
- Push(&S, x)：进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。
- Pop(&S, &x)：出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回。
- GetTop(S, &x)：读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
- StackEmpty(S)：判空。断一个栈 S 是否为空，若 S 为空，则返回 true，否则返回 false。
1.3 栈的顺序存储实现
顺序栈的定义：
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶元素
}SqStack;
void testStack(){
SqStack S; //声明一个顺序栈(分配空间)
}
顺序栈的初始化：
#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
// 初始化栈
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[++S.top] = x;
return true;
}
// 出栈
bool Pop(SqStack &x, 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];
return true;
}
共享栈（两个栈共享同一片空间）：
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
}ShStack;
// 初始化栈
void InitSqStack(ShStack &S){
S.top0 = -1;
S.top1 = MaxSize;
}
1.4 栈的链式存储实现
链栈的定义：
typedef struct Linknode{
ElemType data; //数据域
Linknode *next; //指针域
}Linknode,*LiStack;
void testStack(){
LiStack L; //声明一个链栈
}
链栈的初始化：
typedef struct Linknode{
ElemType data;
Linknode *next;
}Linknode,*LiStack;
// 初始化栈
bool InitStack(LiStack &L){
L = (Linknode *)malloc(sizeof(Linknode));
if(L == NULL)
return false;
L->next = NULL;
return true;
}
// 判断栈是否为空
bool isEmpty(LiStack &L){
if(L->next == NULL)
return true;
else
return false;
}
入栈出栈：
// 新元素入栈
bool pushStack(LiStack &L,ElemType x){
Linknode *s = (Linknode *)malloc(sizeof(Linknode));
if(s == NULL)
return false;
s->data = x;
// 头插法
s->next = L->next;
L->next = s;
return true;
}
// 出栈
bool popStack(LiStack &L, int &x){
// 栈空不能出栈
if(L->next == NULL)
return false;
Linknode *s = L->next;
x = s->data;
L->next = s->next;
free(s);
return true;
}
2. 队列
2.1 队列的基本概念
- 队列是操作受限的线性表：只允许在一端进行插入 (入队)，另一端进行删除 (出队)。
- 队头：允许删除的一端。
- 队尾：允许插入的一端。
- 空队列：不含任何元素的空表。
特点：先进先出（先入队的元素先出队）、FIFO（First In First Out）
2.2 队列的基本操作
- InitQueue(&Q)：初始化队列。构造一个空队列 Q。
- DestroyQueue(&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。
- EnQueue(&Q, x)：入队。若队列 Q 未满，将 x 加入，使之成为新的队尾。
- DeQueue(&Q, &x)：出队。若队列 Q 非空，删除队头元素，并用 x 返回。
- GetHead(Q,&x)：读队头元素。若队列 Q 非空，则将队头元素赋值给 x。
- QueueEmpty(Q)：判空。若队列 Q 为空，则返回 true。
2.3. 队列的顺序存储实现
顺序队列的定义：
#define MaxSize 10; //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //用静态数组存放队列元素
int front, rear; //队头指针和队尾指针
}SqQueue;
void test{
SqQueue Q; //声明一个队列
}
顺序队列的初始化：
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
// 初始化时，队头、队尾指针指向0
// 队尾指针指向的是即将插入数据的数组下标
// 队头指针指向的是队头元素的数组下标
Q.rear = Q.front = 0;
}
// 判断队列是否为空
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;
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;
}
获得队头元素：
// 获取队头元素并存入x
bool GetHead(SqQueue &Q, ElemType &x){
if(Q.rear == Q.front)
return false;
x = Q.data[Q.front];
return true;
}
注意：循环队列不能使用Q.rear == Q.front作为判空的条件，因为当队列已满时也符合该条件，会与判空发生冲突！
- 解决方法一：牺牲一个单元来区分队空和队满，即将(Q.rear+1)%MaxSize == Q.front作为判断队列是否已满的条件。（主流方法）
- 解决方法二：设置 size 变量记录队列长度。
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
int size;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0;
Q.size = 0;
}
// 判断队列是否为空
bool QueueEmpty(SqQueue 0){
if(Q.size == 0)
return true;
else
return false;
}
// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){
if(Q.size == MaxSize)
return false;
Q.size++;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.size == 0)
return false;
Q.size--;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}
- 解决方法三：设置 tag 变量记录队列最近的操作。（tag=0：最近进行的是删除操作；tag=1 ：最近进行的是插入操作）
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
int tag;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0;
Q.tag = 0;
}
// 判断队列是否为空
bool QueueEmpty(SqQueue 0){
if(Q.front == Q.rear && Q.tag == 0)
return true;
else
return false;
}
// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){
if(Q.rear == Q.front && tag == 1)
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
Q.tag = 1;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.rear == Q.front && tag == 0)
return false;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
Q.tag = 0;
return true;
}
2.4 队列的链式存储实现
链队列的定义：
// 链式队列结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}
// 链式队列
typedef struct{
// 头指针和尾指针
LinkNode *front, *rear;
}LinkQueue;
链队列的初始化（带头结点）：
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q){
// 初始化时，front、rear都指向头结点
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
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;
Q.rear = s;
}
// 队头元素出队
bool 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;
// 如果p是最后一个结点，则将队头指针也指向NULL
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return true;
}
以上是带头结点的链队列，下面是不带头结点的操作：
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q){
// 不带头结点的链队列初始化，头指针和尾指针都指向NULL
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){
Q.front = s;
Q.rear = s;
}else{
Q.rear->next = s;
Q.rear = s;
}
}
//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
if(Q.front == NULL)
return false;
LinkNode *s = Q.front;
x = s->data;
if(Q.front == Q.rear){
Q.front = Q.rear = NULL;
}else{
Q.front = Q.front->next;
}
free(s);
return true;
}
2.5 双端队列
定义：
- 双端队列是允许从两端插入、两端删除的线性表。
- 如果只使用其中一端的插入、删除操作，则等同于栈。
- 输入受限的双端队列：允许一端插入，两端删除的线性表。
- 输出受限的双端队列：允许两端插入，一端删除的线性表。
考点：判断输出序列的合法化
例：数据元素输入序列为 1，2，3，4，判断 4! = 24 个输出序列的合法性
栈中合法的序列，双端队列中一定也合法ZS
| 栈 | 输入受限的双端队列 | 输出受限的双端队列 |
|---|---|---|
| 14个合法 | 只有4213和4231不合法 | 只有4231和4132不合法 |
3. 栈与队列的应用
3.1 栈在括号匹配中的应用
- 用栈实现括号匹配：
- 最后出现的左括号最先被匹配 （栈的特性——LIFO）。
- 遇到左括号就入栈。
- 遇到右括号，就“消耗”一个左括号（出栈）。
- 匹配失败情况：
- 扫描到右括号且栈空，则该右括号单身。
- 扫描完所有括号后，栈非空，则该左括号单身。
- 左右括号不匹配。
#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的字符串str中的括号是否匹配
bool bracketCheck(char str[], int length){
SqStack S;
InitStack(S);
// 遍历str
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;
// 用topElem接收栈顶元素
Pop(S, topElem);
// 括号不匹配
if(str[i] == ')' && topElem != '(' )
return false;
if(str[i] == ']' && topElem != '[' )
return false;
if(str[i] == '}' && topElem != '{' )
return false; }
}
// 扫描完毕若栈空则说明字符串str中括号匹配
return StackEmpty(S);
}
3.2 栈在表达式求值中的应用
- 中缀表达式：中缀表达式是一种通用的算术或逻辑公式表示方法，运算符以中缀形式处于操作数的中间。对于计算机来说中缀表达式是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
- 前缀表达式（波兰表达式）：前缀表达式的运算符位于两个操作数之前。
- 后缀表达式（逆波兰表达式）：后缀表达式的运算符位于两个操作数之后。
- 中缀转后缀的手算方法：
确定中缀表达式中各个运算符的运算顺序。
选择下一个运算符，按照左操作数 右操作数 运算符的方式组合成一个新的操作数。
如果还有运算符没被处理，就继续执行。- 确定中缀表达式中各个运算符的运算顺序。
- 选择下一个运算符，按照==「左操作数 右操作数 运算符」==的方式组合成一个新的操作数。
- 如果还有运算符没被处理，就继续执行。
中缀转后缀要遵循“左优先”原则：只要左边的运算符能先计算，就优先计算左边的。
- 后缀表达式的手算方法： 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算， 合体为一个操作数。
- 后缀表达式的机算方法：
1. 从左往右扫描下一个元素，直到处理完所有元素。
2. 若扫描到操作数则压入栈，并回到第一步；否则执行第三步。
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步。
弹出栈顶元素时，先出栈的是“右操作数”。
- 中缀转前缀的手算方法：
1. 确定中缀表达式中各个运算符的运算顺序。
2. 选择下一个运算符，按照==「运算符 左操作数 右操作数」==的方式组合成一个新的操作数。
3. 如果还有运算符没被处理，就继续执行第二步。
中缀转前缀遵循“右优先”原则：只要右边的运算符能先计算，就优先算右边的。
- 前缀表达式的计算方法：
1. 从右往左扫描下一个元素，直到处理完所有元素。
2. 若扫描到操作数则压入栈，并回到第一步；否则执行第三步。
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步。 - 中缀转后缀的机算方法： 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况：
1. 遇到操作数：直接加入后缀表达式。
2. 遇到界限符：遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到 弹出“(”为止。注意：“(”不加入后缀表达式。
3. 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式， 若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
#define MaxSize 40
typedef struct{
char data[MaxSize];
int top;
}SqStack;
typedef struct{
char data[MaxSize];
int front,rear;
}SqQueue;
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);
void InitQueue(SqQueue &Q);
bool EnQueue(LQueue &Q, char x);
bool DeQueue(LQueue &Q, char &x);
bool QueueEmpty(SqQueue Q);
// 判断元素ch是否入栈
int JudgeEnStack(SqStack &S, char ch){
char tp = S.data[S->top];
// 如果ch是a~z则返回-1
if(ch >= 'a' && ch <= 'z')
return -1;
// 如果ch是+、-、*、/且栈顶元素优先级大于等于ch则返回0
else if(ch == '+' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))
return 0;
else if(ch == '-' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))
return 0;
else if(ch == '*' && (tp == '*' || tp == '/'))
return 0;
else if(ch == '/' && (tp == '*' || tp == '/'))
return 0;
// 如果ch是右括号则返回2
else if(ch == ')')
return 2;
// 其他情况ch入栈，返回1
else return 1;
}
// 中缀表达式转后缀表达式
int main(int argc, char const *argv[]) {
SqStack S;
SqQueue Q;
InitStack(S);
InitQueue(Q);
char ch;
printf("请输入表达式，以“#”结束：");
scanf("%c", &ch);
while (ch != '#'){
// 当栈为空时
if(StackEmpty(&S)){
// 如果输入的是数即a~z，直接入队
if(ch >= 'a' && ch <= 'z')
EnQueue(Q, ch);
// 如果输入的是运算符，直接入栈
else
Puch(S, ch);
}else{
// 当栈非空时，判断ch是否需要入栈
int n = JudgeEnStack(S, ch);
// 当输入是数字时直接入队
if(n == -1){
EnQueue(Q, ch);
}else if(n == 0){
// 当输入是运算符且运算符优先级不高于栈顶元素时
while (1){
// 取栈顶元素入队
char tp;
Pop(S, tp);
EnQueue(Q, tp);
// 再次判断是否需要入栈
n = JudgeEnStack(S, ch);
// 当栈头优先级低于输入运算符或者栈头为‘)’时，入栈并跳出循环
if(n != 0){
EnStack(S, ch);
break;
}
}
}else if(n == 2){
// 当出现‘)’时 将()中间的运算符全部出栈入队
while(1){
char tp;
Pop(S, tp);
if(tp == '(')
break;
else
EnQueue(Q, tp);
}
}else{
// 当运算符优先级高于栈顶元素或出现‘(’时直接入栈
Push(S, ch);
}
}
scanf("%c", &ch);
}
// 将最后栈中剩余的运算符出栈入队
while (!StackEmpty(S)){
char tp;
Pop(S, tp);
EnQueue(Q, tp);
}
// 输出队中元素
while (!QueueEmpety(Q)){
printf("%c ", DeQueue(Q));
}
return 0;
}
- 中缀表达式的机算方法： 中缀转后缀 + 后缀表达式的求值（两个算法的结合）
初始化两个栈，（操作数栈和运算符栈），若扫描到操作数，压入操作数栈；若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算， 运算结果再压回操作数栈）。
3.3 栈在递归中的应用
-
函数调用的特点：最后被调用的函数最先执行结束（LIFO）。
-
函数调用时，需要用一个“函数调用栈” 存储：
- 调用返回地址
- 实参
- 局部变量
-
递归调用时，函数调用栈可称为“递归工作栈” 。每进入一层递归，就将递归调用所需信息压入栈顶；每退出一层递归，就从栈顶弹出相应信息。
-
缺点： 效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算。
-
可以自定义栈将递归算法改造成非递归算法。
3.4 队列的应用
- 树的层次遍历
- 图的广度优先遍历
- 操作系统中多个进程争抢着使用有限的系统资源时，先来先服务算法（First Come First Service）是是一种常用策略。
4. 特殊矩阵的压缩存储
除非题目特别说明，否则数组下标默认从0开始。
-
一维数组的存储：各数组元素大小相同，且物理上连续存放。设起始地址为 LOC，则数组元素 a [ i ] a[i]a[i] 的存放地址 = LOC + i * sizeof(ElemType) (0≤i<10)
-
二维数组的存储：
- M 行 N 列的二维数组 b [ M ] [ N ] 中，设起始地址为 LOC，若按行优先存储，则 b [ i ] [ j ] 的存储地址 = LOC + (iN + j) * sizeof(ElemType)
2. M行N列的二维数组 b [ M ] [ N ] 中，设起始地址为 LOC，若按列优先存储，则 b [ i ] [ j ] 的存储地址 = LOC + (jM + i) * sizeof(ElemType)
- M 行 N 列的二维数组 b [ M ] [ N ] 中，设起始地址为 LOC，若按行优先存储，则 b [ i ] [ j ] 的存储地址 = LOC + (iN + j) * sizeof(ElemType)
-
对称矩阵的压缩存储
-
三角矩阵的压缩存储
1. 下三角矩阵：处理主对角线和下三角区，其余元素都相同
2. 上三角矩阵：处理主对角线和上三角区，其余元素都相同
3. 压缩存储策略：按行优先原则将主对角线+下三角区存入一维数组中，并在最后一个位置存储常量。 -
三对角矩阵的压缩存储： 三对角矩阵，又称带状矩阵
-
稀疏矩阵的压缩存储： 稀疏矩阵的非零元素远远少于矩阵元素的个数。压缩存储策略：
- 顺序存储：三元组 <行，列，值>
- 链式存储：十字链表法
