栈栈的基本概念定义栈是只允许在一端进行插入或删除操作的线性表栈顶：线性表允许进行插入删除的那一端栈底：固定的，不允许进行插入和删除的另一端空栈：不含任何元素特点：后进先出（LIFO）基本操作(&S)：初始化一个空栈(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶Pop(&S,%=&x)：出栈，若栈S非空，则用x返回栈顶元素(S,&x)：读栈顶元素，若栈S非空，则用x返回栈顶元素(&S)：销毁栈，并释放栈S占用的存储空间卡特兰数：n个不同元素进栈，出栈元素的不同排列的个数为$frac{1}{n+1}C^n_{2n}$栈的顺序存储结构顺序栈的定义1
10
11
# 10 //定义栈中元素的最大个数
{
data[]; //静态数组存放栈中元素
int top; //栈顶元素
};
void (){
S; //声明一个顺序栈(分配空间)
//连续的存储空间大小为 *()
}基本操作1
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# 10 //定义栈中元素的最大个数
{
data[]; //静态数组存放栈中元素
int top; //栈顶元素
};
//初始化栈
void ( &S){
= -1; //初始化栈顶指针
//判栈空
bool ( S){
if( == -1) //栈空
true;
else //栈不空
false;
//新元素进栈
bool Push( &S, x){
if( == – 1) //栈满
false;
= + 1; //指针先加1
S.data[] = x; //新元素入栈
/*
S.data[++] = x;
*/
true;
//出栈
bool Pop( &x, &x){
if( == -1) //栈空
false;
x = S.data[]; //先出栈
= – 1; //栈顶指针减1
true;
/*
x = S.data[–];
*/
//只是逻辑上的删除，数据依然残留在内存里
//读栈顶元素
bool ( S, &x){
if( == -1)
false;
x = S.data[]; //x记录栈顶元素
true;
void (){
S; //声明一个顺序栈(分配空间)
(S);
//…
}栈满条件：top==顺序栈的缺点：栈的大小不可变共享栈定义：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸栈的链式存储结构
与链表类似，入栈和出栈的操作都在链表的表头进行
队列队列的概念定义：队列是只允许在一端进行插入（入队），在另一端删除（出队）的线性表队头：允许删除的一端队尾：允许插入的一端空队列：不含任何元素的空表队列的特点：先进先出（FIFO）队列的基本操作(&Q): 初始化队列，构造一个空队列(&Q): 销毁队列，并释放队列Q所占用的内存空间(&Q, x): 入队，若队列Q未满，将x加入，使之成为新的队尾(&Q, &x): 出队，若队列Q非空，删除队头元素，并用x返回(Q,&x): 读队头元素，若队列Q非空，则将队头元素赋值给(Q): 判队列空，若队列Q为空，则返回true，否则返回false队列的顺序存储结构队列的顺序实现1
# 10; //定义队列中元素的最大个数
{
data[]; //用静态数组存放队列元素
int front, rear; //队头指针和队尾指针
};初始化操作1
10
11
12
13
//初始化队列
void ( &Q){
//初始化时，队头、队尾指针指向0
Q.rear = Q.front = 0;
// 判断队列是否为空
bool ( 0){
if(Q.rear == Q.front) //队空条件
true;
else
false;
}入队操作1
bool ( &Q, x){
if((Q.rear+1)% == Q.front) //队满
false; //队满报错
Q.data[Q.rear] = x; //将x插入队尾
Q.rear = (Q.rear + 1) % ; //队尾指针加1取模
true;
}出队操作1
//出队，删除一个队头元素，用x返回
bool ( &Q, &x){
if(Q.rear == Q.front) //队空报错
false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % ; //队头指针后移动
true;
}获得队头元素1
bool ( &Q, &x){
if(Q.rear == Q.front) //队空报错
false;
x = Q.data[Q.front];
true;
}判断队列已满/已空方案一：牺牲一个存储单元（实现代码同1）初始化时：rear=front=0;队空条件：Q.rear==Q.front;队满条件：(Q.rear+1)% == Q.front队列元素个数：(rear+-front)%;方案二实现1
# 10; //定义队列中元素的最大个数
{
data[]; //用静态数组存放队列元素
int front, rear; //队头指针和队尾指针
int size;
};初始化时1
rear=front=0;
size=0;插入成功：size++;删除成功：size–;队满条件：size==;队空条件：size==0;方案三实现1
# 10; //定义队列中元素的最大个数
{
data[]; //用静态数组存放队列元素
int front, rear; //队头指针和队尾指针
int tag; //最近进行的是删除/插入
};初始化时1
rear=front=0;
tag=0;插入成功：tag=1;删除成功：tag=0;队满条件：rear==front&&tag==1;队空条件：rear==front&&tag==0;队列的链式存储结构定义队列1
{ //链式队列结点
data;
*next;
{ //链式队列
*front, *rear; //队列的队头和队尾指针
};初始化带头结点1
10
11
12
13
void ( &Q){
//初始化时，front、rear都指向头结点
Q.front = Q.rear = (*)(());
Q.front -> next = NULL;
//判断队列是否为空
bool ( Q){
if(Q.front == Q.rear) //也可用 Q.front -> next == NULL
true;
else
false;
}不带头结点1
10
11
12
13
void ( &Q){
//初始化时，front、rear都指向NULL
Q.front = NULL;
Q.rear = NULL;
//判断队列是否为空
bool ( Q){
if(Q.front == NULL)
true;
else
false;
}入队带头结点1
//新元素入队 (表尾进行)
void ( &Q, x){
*s = ( *)(()); //申请一个新结点
s->data = x;
s->next = NULL; //s作为最后一个结点，指针域指向NULL
Q.rear->next = s; //新结点插入到当前的rear之后
Q.rear = s; //表尾指针指向新的表尾
}不带头结点1
10
11
12
13
//新元素入队
void ( &Q, x){
*s = ( *)(()); //申请一个新结点
s->data = x;
s->next = NULL;
if(Q.front==NULL){ //在空队列中插入第一个元素
Q.front=s; //修改队头队尾指针
Q.rear=s;
}else{
Q.rear->next=s; //新结点插入到rear结点之后
Q.rear=s; //修改rear指针
}出队带头结点1
10
11
12
13
14
//队头元素出队
bool ( &Q, &x){
if(Q.front == Q.rear)
false; //空队
*p = Q.front->next; //p指针指向即将删除的结点
x = p->data;
Q.front->next = p->next; //修改头结点的next指针
if(Q.rear == p) //此次是最后一个结点出队
Q.rear = Q.front; //修改rear指针
free(p); //释放结点空间
true;
}不带头结点1
10
11
12
13
14
15
//队头元素出队
bool ( &Q, &x){
if(Q.front == Q.rear)
false; //空队
*p = Q.front; //p指针指向即将删除的结点
x = p->data;
Q.front = p->next; //修改头结点的next指针
if(Q.rear == p){ //此次是最后一个结点出队
Q.rear==NULL:
Q.front==NULL;
free(p); //释放结点空间
true;
}双端队列定义：只允许从两端插入、两端删除的线性表输入受限的双端队列：允许一端插入，两端删除的线性表输出受限的双端队列：允许两端插入，一端删除的线性表栈和队列的应用栈在括号匹配中的应用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#define MaxSize 10
typedef struct{
char data[MaxSize];
int top;
} SqStack;
//初始化栈
InitStack(SqStack &S)
//判断栈是否为空
bool StackEmpty(SqStack &S)
//新元素入栈
bool Push(SqStack &S, char x)
//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x)
bool bracketCheck(char str[], int length){
SqStack S; //声明
InitStack(S); //初始化栈
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; //存储栈顶元素
Pop(S, topElem); //栈顶元素出栈
if(str[i] == ')' && topElem != '(' )
return false;
if(str[i] == ']' && topElem != '[' )
return false;
if(str[i] == '}' && topElem != '{' )
return false;
}
}
StackEmpty(S); //栈空说明匹配成功
}
栈在表达式值中的应用
中缀表达式
(需要界限符)
规则：运算符在两个操作数中间例a + ba + b – ca + b – c*d
后缀表达式 (逆波兰表达式)
规则：运算符在两个操作数后面例a b +ab+ c – / a bc- +ab+ cd* -中缀表达式转后缀表达式确定中缀表达式中各个运算符的运算顺序选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数如果还有运算符没被处理，继续步骤2
“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)
用栈实现中缀表达式转后缀表达式初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况遇到操作数: 直接加入后缀表达式遇到界限符: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘(’ 为止。注意: ‘(‘ 不加入后缀表达式遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式后缀表达式的计算：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）从左往后扫描下一个元素，直到处理完所有元素若扫描到操作数，则压入栈，并回到步骤1;否则执行步骤3若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤1先出栈的是“右操作数”
前缀表达式 (波兰表达式)
规则：运算符在两个操作数前面例a b+ab c+ab *cd中缀表达式转前缀表达式确定中缀表达式中各个运算符的运算顺序选择下一个运算符，按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数如果还有运算符没被处理，就继续执行步骤2“右优先”原则: 只要右边的运算符能先计算，就优先算右边的;用栈实现前缀表达式的计算从右往左扫描下一个元素，直到处理完所有元素若扫描到操作数则压入栈，并回到步骤1，否则执行步骤3若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤1；先出栈的是“左操作数”
4.中缀表达式的计算(用栈实现)：两个算法的结合： 中缀转后缀 + 后缀表达式的求值
1. 初始化两个栈，操作数栈和运算符栈
2. 若扫描到操作数，压入操作数栈
3. 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈 (期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈项元素并执行相应运算，运算结果再压回操作数栈)
栈在递归中的应用函数调用的特点：最后被调用的函数最先执行结束(LIFO)函数调用时，需要用一个栈存储调用返回地址实参局部变量递归调用时，函数调用栈称为 “递归工作栈”每进入一层递归，就将递归调用所需信息压入栈顶每退出一层递归，就从栈顶弹出相应信息缺点： 太多层递归可能回导致栈溢出数组和特殊矩阵数组的定义
数组是由n(n>=1)个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界
数组的存储结构一维数组各数组元素大小相同，物理上连续存放数组下标：默认从0开始数组元素 a[i] 的存放地址 = $LOC + i * ()$LOC为数组起始地址二维数组行优先/列优先存储优点：实现随机存储M行N列的二维数组 b[M][N] 中，b[i][j]的存储地址：行优先存储: $LOC + (i×N + j) × ()$列优先存储：$LOC + (j×M + i) × ()$普通矩阵的存储：使用二维数组存储
描述矩阵元素时，行、列号通常从1开始
描述数组时，通常下标从 0 开始
特殊矩阵的压缩存储
矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
对称矩阵若n 阶方阵中任意一个元素$a_{i,j}$都有 $a_{i,j}=a_{j,i}$则该矩阵为对称矩阵策略：只存储主对角线+下三角区；按行优先原则将各元素存入一维数组中数组大小：$frac{n(n+1)}{2}$元素下标对应关系：k为$a_{i,j}$在一维数组中的下标
k= left{
begin{array}{l}
frac{i(i-1)}{2}+j-1, quad i ge j quad (下三角区和主对角线元素)
frac{j(j-1)}{2}+i-1, quad iend{array}
right.
三角矩阵以主对角线划分，三角矩阵有上（下）三角两种。上（下）三角矩阵的下（上）三角（不含主对角线）中的元素均为常数。在大多数情况下，三角矩阵常数为零策略：按行优先原则将元素存入一维数组中（同对称矩阵）。并在最后一个位置存储常量元素下标对应关系：k为$a_{i,j}$在一维数组中的下标
k= left{
begin{array}{l}
frac{i(i-1)}{2}+j-1, quad i ge j quad (下三角区和主对角线元素)
frac{n(n+1)}{2}, quad iend{array}
right.
3. 三对角矩阵（带状矩阵）
1. 当$|i-j|>1$时，有$a_{i,j}=0 (1 leq i,j leq n)$
2. 策略：按行优先(或列优先) 原则，只存储带状部分
3. 元素下标对应关系：k为$a_{i,j}$在一维数组中的下标 k=2i+j-3
稀疏矩阵非零元系远远少于矩阵元素的个数策略顺序存储——三元组会失去随机存取的特性十字链表法
———END———
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，永久会员只需109元，全站资源免费下载 点击查看详情
站 长 微 信： nanadh666
