文章目录
栈基础知识：【数据结构】栈 顺序栈 链栈（共享栈 创建 进栈 出栈 读取）完整代码+解析
队列基础知识：【数据结构】队列 循环队列 双端队列——顺序队列+链式队列完整代码
3.栈的应用
3.1 括号匹配问题
-
问题阐述
-
匹配流程：
-
算法流程：
#include<stdio.h>
#include<stdlib.h>
#define ElemType char
#define MaxSize 9
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack& Q) {
Q.top = -1;
}
bool isEmpty(SqStack& Q) {
if (Q.top == -1)
return true;
else
return false;
}
bool Push(SqStack& Q, ElemType x) {
if (Q.top + 1 == MaxSize)return false;
Q.data[++Q.top] = x;
return true;
}
bool Pop(SqStack& Q, ElemType& x) {
if (Q.top == -1)return false;
x = Q.data[Q.top--];
return true;
}
//括号匹配算法
bool bracketCheck(char s[],int length) {
SqStack Q;
InitStack(Q);
char topElem;
for (int i = 0; i < length; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
Push(Q, s[i]);
}
else {
Pop(Q, topElem);
if (s[i] == ')' && topElem == '(' || s[i] == ']' && topElem == '[' || s[i] == '}' && topElem == '{')
continue;
else
return false;
}
}
if (!isEmpty(Q))return false;
return true;
}
int main() {
char s1[6] = { '(','(','[',']',')' };
char s2[4] = { '(','{',']' };
char s3[7] = { '(','[','{','}',']',')'};
printf("%d\n",bracketCheck(s1, 5));
printf("%d\n", bracketCheck(s2, 3));
printf("%d\n", bracketCheck(s3, 6));
}
3.2 表达式求值
3.2.1 三种算术表达式
-
中缀表达式
-
后缀表达式（逆波兰式）
-
前缀表达式（波兰式）
3.2.2 后缀表达式
A.中缀转后缀
-
手算方法
-
机算
-
中缀转后缀完整代码
#include<stdio.h> #include<string.h> #define ElemType char #define MaxSize 99 typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack& Q) { Q.top = -1; } bool isEmpty(SqStack& Q) { if (Q.top == -1) return true; else return false; } bool Push(SqStack& Q, ElemType x) { if (Q.top + 1 >= MaxSize)return false; Q.data[++Q.top] = x; return true; } bool Pop(SqStack& Q, ElemType& x) { if (Q.top == -1)return false; x=Q.data[Q.top--]; return true; } //运算符优先级判断 int Priority(char x) { if (x == '-' || x == '+') return 1; else if (x == '*' || x == '/') return 2; else if (x == '(') return 0; return -1; } //中缀转后缀 //in是待转换的中缀表达式，suf是转换后的前缀表达式 void in2suf(char in[], char suf[]) { //初始化一个栈 SqStack Q; InitStack(Q); int isuf = 0;//suf数组下标 char x; //从左往右遍历各元素 for (int i = 0; i < strlen(in); i++) { if (in[i] >= '0' && in[i] <= '9') //遇到操作数。 { suf[isuf++] = in[i]; //直接加入后缀表达式 } else if (in[i] == '(') //遇到‘（’ { Push(Q, in[i]); //直接入栈 } else if (in[i] == ')') //遇到‘）’ { Pop(Q, x); //依次弹出栈内运算符 while (x != '(') { suf[isuf++] = x; //并加入后缀表达式 Pop(Q, x); } } else //遇到运算符 { //依次弹出栈中优先级高于或等于当前运算符的所有运算符 while (!isEmpty(Q)&&Priority(in[i]) <= Priority(Q.data[Q.top])) { if (Q.data[Q.top] == '(')break; //若碰到‘（’或栈空停止 Pop(Q, x); suf[isuf++] = x; //加入后缀表达式 } Push(Q, in[i]); //当前运算符入栈 } } while (!isEmpty(Q)){ Pop(Q, x); suf[isuf++] = x; } suf[isuf] = '\0'; } int main() { char in[] = "1+5*(2+3)/(4-2)+3*1"; char suf[MaxSize]; in2suf(in, suf); printf("%s\n", in); printf("%s\n\n", suf); return 0; }
B.后缀表达式的计算
-
手算
-
机算
-
后缀表达式求值 完整代码
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #define ElemType int #define MaxSize 99 typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack& Q) { Q.top = -1; } bool isEmpty(SqStack& Q) { if (Q.top == -1) return true; else return false; } bool Push(SqStack& Q, ElemType x) { if (Q.top + 1 >= MaxSize)return false; Q.data[++Q.top] = x; return true; } bool Pop(SqStack& Q, ElemType& x) { if (Q.top == -1)return false; x = Q.data[Q.top--]; return true; } //后缀表达式求值 int Computed_suf(char suf[]) { SqStack Q; InitStack(Q); int a, b,c; //从左往右扫描下一个元素，直到处理完所有元素 for (int i = 0; i < strlen(suf); i++) { if (suf[i] >= '0' && suf[i] <= '9') { //若扫描到操作数则压入栈 Push(Q, suf[i]-'0'); } else { //若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶 Pop(Q, b); Pop(Q, a); if (suf[i] == '+') { c = a + b; } else if (suf[i] == '-') { c = a - b; } else if (suf[i] == '*') { c = a * b; } else if (suf[i] == '/') { c = a / b; } Push(Q, c); } } return Q.data[Q.top]; } int main() { char s[] = "1523+*72-/+31*+"; //1+5*(2+3)/(7-2)+3*1=9 printf("%d", Computed_suf(s)); return 0; }
3.2.3 前缀表达式
A.中缀转前缀
-
手算
B.前缀表达式的计算
3.2.4 中缀表达式的求值
-
方法
3.3 递归中栈的应用
-
函数调用特点
-
调用函数时，需要用一个栈存储：
-
递归的精髓：
-
在计算机中，用栈来解决函数的递归调用
4.队列的应用
-
树的层次遍历、图的广度优先遍历
-
队列在计算机系统中的应用