# Ch3
LIFO
# 顺序栈的实现
定义1
2
3
4
5
| #define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
|
初始化1
2
3
| void InitStack(SqStack &S){
S.top = -1;
}
|
判断空1
2
3
4
5
6
| bool StackEmpty(SqStack S){
if(S.top == -1)
return true;
else
return false;
}
|
push1
2
3
4
5
6
| bool Push(SqStack &S,ElemType x){
if(S.top == MaxSize - 1)
return false;
S.data[++S.top] = x;
return true;
}
|
pop1
2
3
4
5
6
| bool Pop(SqStack &S,ElemType &x){
if(S.top == -1)
return false;
x = S.data[S.top--];
return true;
}
|
gettop1
2
3
4
5
6
| bool GetTop(SqStack S,ElemType &x){
if(S.top == -1)
return false;
x = S.data[S.top];
return true;
}
|
# 共享栈
同时从两边向中间压栈
# 链栈
定义1
2
3
4
| typedef struct Linknode{
ElemType data;
struct Linknode *next;
}LiStack;
|
# 队列
FIFO
# 顺序存储
队列的实现1
2
3
4
5
| #define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int front,rear;
}SqQueue;
|
初始状态：front = rear = 0
队列判空1
2
3
4
5
6
| bool QueueEmpty(SqQueue Q){
if(Q.front == Q.rear)
return true;
else
return false;
}
|
# 循环队列
初始化1
2
3
| void InitQueue(SqQueue &Q){
Q.front = Q.rear = 0;
}
|
队列判空1
2
3
4
5
6
| bool QueueEmpty(SqQueue Q){
if(Q.front == Q.rear)
return true;
else
return false;
}
|
队列判满1
2
3
4
5
6
| bool QueueFull(SqQueue Q){
if((Q.rear + 1) % MaxSize == Q.front)
return true;
else
return false;
}
|
入队1
2
3
4
5
6
7
| bool EnQueue(SqQueue &Q,ElemType x){
if(QueueFull(Q))
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
return true;
}
|
出队1
2
3
4
5
6
7
| bool DeQueue(SqQueue &Q,ElemType &x){
if(QueueEmpty(Q))
return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
|
求元素个数1
2
3
| int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MaxSize) % MaxSize;
}
|
# 链式存储
链队列的实现1
2
3
4
5
6
7
| typedef struct Linknode{
ElemType data;
struct Linknode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
|
一般设计成带头结点的链队列
初始化1
2
3
4
| void InitQueue(LinkQueue &Q){
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
|
队列判空1
2
3
4
5
6
| bool QueueEmpty(LinkQueue Q){
if(Q.front == Q.rear)
return true;
else
return false;
}
|
入队1
2
3
4
5
6
7
| bool EnQueue(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
| 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;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return true;
}
|
# 双端队列
- 输出受限的双端队列
允许在一端进行 push/pop 操作，另一端只能 push
- 输入受限的双端队列
允许在一端进行 push/pop 操作，另一端只能 pop
# 栈和队列的应用
# 表达式
- 括号匹配
左括号压栈，右括号出栈，判断是否匹配
- 算术表达式
中缀表达式：左根右
前缀表达式：根左右
后缀表达式：左右根
中缀转后缀
- 加括号
- 把运算符移到当前层的括号后面
- 去掉括号
用栈实现中缀转后缀：
- 遇到操作数直接加入后缀表达式
- 遇到括号，左括号入栈，右括号依次出栈加入后缀表达式直到遇到左括号位置，并删除左括号
- 遇到运算符，判断优先级，如果栈为空或者栈顶为 “（” 或者栈顶运算符优先级低于当前运算符，则入栈，否则依次出栈加入后缀表达式，直到栈为空或者栈顶运算符优先级低于当前运算符（优先级相同的也要出栈），最后将当前运算符入栈
所以栈里面只存运算符和括号
后缀表达式求值
从左到右扫描表达式，遇到操作数压栈，遇到操作符就弹出两个操作数，计算结果压入栈中
# 递归
# 队列
# 层次遍历
根左右入队，依次 pop
# 队列的应用
# 数组
特殊矩阵的压缩存储
- 对称矩阵
只存下三角的元素，存在一维数组里
- 三角矩阵
省略 0，摊平存在一维数组
- 三对角
同理省略 0，存在一维数组里
- 稀疏矩阵
行标，列标，值都成三元组，存储在线性表（数组或者十字链表），保存的同时要保存系数矩阵的行数、列数和非零元素的个数
