1
第三章 栈和队列
3.1 栈栈的定义、栈的存储结构、栈的应用。
队列的定义、队列存储结构、队列的应用。
3.2 队列
栈和队列的逻辑结构和物理结构，以及它们之间的相互关系
定义与之相适应的运算
设计相应的算法
分析算法的效率
2
3.1.1 栈的定义一,栈的概念栈 (stack)是 插入 和 删除 操作限定在 一端 进行的 线性表 。
栈的逻辑表示为,S=(a1,a2,…a n)
栈顶 (top),表中允许进行插入、删除操作的一端。
栈顶的当前位置是动态 (变化的 )的,栈顶的当前位置由一个称为栈顶指针的位置指示器来指示。
栈底 (bottom):表的另一固定端 (非变化的 )
不含元素的栈称为 空栈,
3.1 栈（堆栈）
3
3.1.1 栈的定义一,栈的概念栈的 运算特性 是后进先出 (Last In First Out— LIFO)
或先进后出 (First In Last Out— FILO)
3.1 栈（堆栈）
栈底 (固定端 )
1 2 3 4
栈顶进栈顺序出栈顺序
4
例 3.1 一个栈的输入序列为 abcd,则下列序列中不可能是栈的输出序列的是 ( )
3.1 栈（堆栈）
A,bcda B,dacb C,bcad D,adcb
二,栈的基本运算初始化栈 InitStack(s):构造一个空栈 s。
销毁栈 ClearStack(s):释放栈 s占用的存储空间 。
求栈的长度 StackLength(s):返回栈 s中的元素个数 。
判断栈是否为空 StackEmpty(s):若栈 s为空,则返回真；
否则返回假。
5
进栈 Push(s,e):入栈操作，在栈 s顶部插入元素 e。
出栈 Pop(s,e):出栈函数，若 s不空，则返回栈顶元素并将其值赋给 e，然后删除该栈顶元素；否则返回空元素 NULL。
取栈顶元素 GetTop(s,e):返回当前的栈顶元素,并将其值赋给 e,与 Pop(s,e)函数的差别在不删除栈顶元素。
显示栈中元素 DispStack(s):从栈顶到栈底顺序显示栈中所有元素。
3.1 栈（堆栈）
二,栈的基本运算
6
3.1.2栈的顺序存储结构及其基本运算的实现顺序栈,即栈的顺序存储结构，是利用一组 地址连续 的存储单元（数组）依次存放栈的数据元素。同时附设 指针 top指示栈顶元素在顺序栈中的位置。
3.1 栈（堆栈）
一,顺序栈的存储结构描述
# define MaxSize 50
typedef int(char,…) Elemtype;
typedef struct
{ElemType data[MaxSize];
int top; //栈顶元素位置
} SqStack;
顺序栈的类型定义：
SqStack *s,s1;
如何访问栈顶元素？
7
3.1 栈（堆栈）
s->data[i]表示第 i+1个进栈的元素；
s->data[s->top]表示栈顶元素；
当 s->top=-1表示 空栈 ；
当 s->top=MaxSize-1表示 栈满 ；
顺序栈的特点：
data
top
低地址高地址
0
1
2
n
s
a
b
c
d
栈中元素个数或栈的长度为：
s->top＋ 1。
8
二,顺序栈的基本运算
初始化栈 InitStack(s)
void InitStack(SqStack *&s)
{ //对栈 s进行初始化
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
建立一个新的空栈 s,实际上是将栈顶指针指向 -1即可。
top 栈底-1
0
1
2
…MaxSize-1
顺序栈 s
空栈
3.1 栈（堆栈）
9
二,顺序栈的基本运算
销毁栈 ClearStack(s)
void ClearStack(SqStack *&s)
{
free(s);
}
int StackLength(SqStack *s)
{
return(s->top+1);
}
求栈的长度 StackLength(s)
top
栈底-1
0
1
2
…MaxSize-1
顺序栈 s
3.1 栈（堆栈）
10
二,顺序栈的基本运算
判断栈是否为空 StackEmpty(s)int StackEmpty(SqStack *s)
{
return(s->top==-1);
}
显示栈中元素 DispStack(s)
void DispStack(SqStack *s)
{//从栈顶到栈底顺序显示栈中所有元素。
int i;
for (i=s->top;i>=0;i--)
printf("%c ",s->data[i]);
printf("\n");
}
3.1 栈（堆栈）
11
int Push(SqStack *s,ElemType e)
{
if(s->top==MaxSize-1)
return 0;//栈已满 (即上溢 ),返回 0
s->top++;//栈顶“指针”加 1
s->data[s->top]=e;//将 e值放入栈顶
return 1;
} top
栈底-1
0
1
2
…MaxSize-1
栈 s
26
8
12
3
e=78
s->top++;
s->data[s->top]=e; s->data[++s->top]=e;
3.1 栈（堆栈）
进栈函数 Push(s,e)的实现算法思想：若栈满返回 0；否则将 e入栈，并返回 1
相当于顺序表的 ListInsert(L,n+1,e)
12
int Push(SqStack *s,ElemType e)
{
if(s->top==MaxSize-1)
return 0;//栈已满 (即上溢 ),返回 0
s->data[++s->top]=e;//将 e值进栈
return 1;
}
3.1 栈（堆栈）
进栈函数 Push(s,e)的实现
13
int Pop(SqStack *&s,ElemType &e)
{
if(s->top==-1)
return 0;//栈为空 (下溢 )
e=s->data[s->top];//将栈顶元素赋给 e
s->top--;//修改栈顶指针
return 1;//返回出栈成功标志
}
top
栈底-1
0
1
2
…MaxSize-1
栈 s
26
8
12
3
调用语句,Pop(s,e)e
=
3.1 栈（堆栈）
出栈函数 Pop(s,e)的实现算法思想：若栈空返回 0；否则返回栈顶元素并将其赋给 e，然后返回 1。 相当于顺序表的 ListDelete(L,n,e)
14
int Pop(SqStack *&s,ElemType &e)
{
if(s->top==-1)
return 0;//栈为空中 (下溢 )
e=s->data[s->top--];//出栈并将出栈元素赋给 e
return 1;//返回出栈成功标志
}
3.1 栈（堆栈）
出栈函数 Pop(s,e)的实现
15
[例 3.4]编写一个算法，利用顺序栈判断一个字符串是否为对称串。所谓对称串是指从左向右读和从右向左读的序列相同。
如字串：,bccb”从左向右读为,bccb”,从右向左读为,bccb”，所以该字串是个对称串
3.1 栈（堆栈）
16
int symmetry(ElemType str[])
{
int i;ElemType e; SqStack *st;
InitStack(st);
for(i=0;str[i]!='\0';i++)
Push(st,str[i]);
for(i=0;str[i]!='\0';i++)
{ Pop(st,e);
if(str[i]!=e)
return(0);
}
return(1);
} top -1
0
1
2
…MaxSize-1
栈 st
c
b
1 ‘b’
c
ElemType str[]={'b',‘c',‘c',‘b','\0'};
e=
3.1 栈（堆栈）
17
int main(int argc,char* argv[])
{
ElemType str[]={'b',‘c',‘c',‘b','\0'};
if(symmetry(str))
cout<<"是对称字符串！ "<<endl;
else
cout<<"非对称字符串！ "<<endl;
return 0;
}
主函数调用上述算法
3.1 栈（堆栈）
18
3.1 栈（堆栈）
3.1.3 栈的链式存储结构及其基本运算的实现
Head ‘a’ ∧
‘b’
‘c’
头结点栈顶结点栈底结点链栈示意图若 Head->next=NULL表明栈为空,且只要内存足够,链栈的长度不受限制。
19
3.1 栈（堆栈）
3.1.3 栈的链式存储结构及其基本运算的实现
typedef char ElemType;
typedef struct linknode
{ ElemType data;
struct linknode *next;
}LiStack;
一,链栈的存储结构描述链栈的类型说明如下：
20
3.1 栈（堆栈）
void Push(LiStack *&s,ElemType e)
{/*S是表示一个带头结点的链栈 */
LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e;
p->next=s->next;
s->next=p;
}
s ∧ p ‘a’
调用语句为 Push(s,‘a’)s ‘a’
∧
p ‘b’
‘b’c’
p ‘c’
设进栈函数 Push(s,e)的实现
21
3.1 栈（堆栈）
int Pop(LiStack *&s,ElemType &e)
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
free(p);
return 1;
} s ‘a’
调用语句为 Push(s,e)e
∧
‘b’
p ‘c’
=
出栈函数 Pop(s,e)的实现
22
3.1 栈（堆栈）
例 3.5 一数学表达式存储在一维数组 exp[]中，
编写一个算法判断表达式 exp中的左右括号是否配对。
算法思路：
从左至右扫描表达表 exp,若遇到左括号,将其进栈,继续扫描余下的表达式,若遇到右括号,
将栈顶元素 (即左括号 )出栈,一直到表达式 exp
的所有元素扫描完为止。
若栈为空,说明表达式左右括号配对,函数返回
1，否则，说明左右括号不配对，函数返回 0。
23
3.1 栈（堆栈）
3.1.4 栈的应用举例
1,表达式求值
(1)问题的描述用户输入一个合法的数学表达式,设计一个算法计算用户所输入的表达式的值 。
为简单起见,这里限定用户输入的是一个包含,+”、
,-”,,*”,,/”,正整数和圆括号的合法数学表达式,如,(56-20)/(4+2)
(2)数据组织用户输入的数学表达式用一维数组 exp[]存储；
算法使用顺序栈 op与另一数组 postexp[]处理用户输入的数学表达式 。
24
3.1 栈（堆栈）
(3)设计运算算法
A.与表达式相关的两个概念：
(a)中缀表达式,
运算符位于两个数字 (常称为操作数 )之间的表达式称为中缀表达式 。 通常书写的数学表达式就是中缀表达,如 (56-20)/(4+2) 是个中缀表达式 。
(b)后缀表达式,
运算符位于操作数后的表达式称为后缀表达式 。 如
5620-42+/是个后缀表达式,使用后缀表达式有利于计算机计算表达式的值,因此表达式求值的过程是：
Step1:将通常的算术表达式 (即中缀表达式 )转换为后缀表达式 ;
Step2,对后缀表达式求值 。
25
3.1 栈（堆栈）
Step1:将通常的算术表达式 (即中缀表达式 )转换为后缀表达式 ;
算符优先关系表 a+b*c-d/(e-f+g)
26
3.1 栈（堆栈）
如何由中缀表达式求后缀表达式？
求后缀表达式转换规律：
1,设立 运算符 栈；
2,依次读入表达式中的每个字符，若是 操作数,则直接发送给后缀式； 若是运算符，则和运算符栈 栈顶算符 进行优先级比较：
3,重复 (2),直到表达式读取完毕。
若栈顶算符优先级高，退出栈顶运算符并发给后缀式；
若与栈顶算法相等，则作（）处理。
若栈顶算符优先级低，则将该运算符作 进栈 操作；
Step1:将通常的算术表达式 (即中缀表达式 )转换为后缀表达式 ;
27
3.1 栈（堆栈）
3.1.4 栈的应用举例
while (ch!='\0')
{ 从数组 exp[]取一个字符到变量 ch中 ;
if ch为数字,将后续的所有数字依次存放到数组
postexp中,并以,#”标志数值串结束 ;
if ch为,(”,将此括号进栈到栈 op中 ;
if ch为,)”:将栈 op中,(”以前的运算符 (若有的话 )
依次出栈并存放到数组 postexp中,然后将,(”从 op栈中删除 ;
if ch为,+”或,-”:将栈 op中,(”以前的运算符依次出栈并存放到数组 postexp中,然后将,+”或,-”进栈 ;
if ch为,*” 或,/”:将 op栈中,*” 或,/”运算符依次出栈并存放到数组 postexp中,然后将,*” 或,/”进栈；
}
B 中缀表达转换为后缀表达式的过程 (算法描述 )
28
3.1 栈（堆栈）
字符数组 exp扫描完毕,将 op栈中余下的所有运算符依次出栈并放入数组 postexp中,最后给数组 postexp
加入结束符 ‘\0’,此时 postexp中的内容就是由中缀表达式转换的后缀表达式 。
设有表达式,(56-20)/(4+2),由用户从键盘输入,并存储在字符型数组中,可使用 C\C++语言定义并初始化表达式数组 exp[]:
char exp[]={'(','5','6','-','2','0',')','/','(','4','+','2',')','\0'};
或者,
char exp[]={"(56-20)/(4+2)"};
注,这里重点是学习算法,实际中算术表达由用户从键盘输入,
29
3.1 栈（堆栈）
(
5
6-
2
0
)
/
(
4
+
2
)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
exp
栈底
op栈
top
postexp
\0
(
5
6#
-
2
0#
-
/
(
4#
+
2#
+
/
\0
中缀表达转换为后缀表达式的过程
char exp[]={"(56-20)/(4+2)"};
while (ch!='\0')
{ 从 exp取一个字符到 ch中 ;
if ch为数字,将后续的所有数字依次存放到数组 postexp中,并以,#”
标志数值串结束 ;
if ch为,(”,将此括号进栈到栈 op
中 ;
if ch为,)”:将栈 op中,(”以前的运算符 (若有的话 )依次出栈并存放到数组 postexp中,然后将,(”从 op
栈中删除 ;
if ch为,+”或,-”:将栈 op中,(”
以前的运算符依次出栈并存放到数组 postexp中,然后将,+”或,-”进栈 ;
if ch为,*” 或,/”:将 op栈中,*”
或,/”运算符依次出栈并存放到数组 postexp中,然后将,*” 或,/”进栈；
}
字符数组 exp扫描完毕,
将 op栈中余下的所有运算符依次出栈并放入数组 postexp中,最后数组
postexp中的内容就是由中缀表达式转换的后缀表达式 。
56#20#-4#2#+/
30
3.1 栈（堆栈）
//part 1:建立 op栈与 postexp数组
void trans(char exp[],char postexp[])
{
char ch;
struct
{
char data[MaxSize];
int top;
} op;//定义 op栈
op.top=-1;//设置为空栈
int i=0,j=0;// i为 exp的下标,j为 postexp的下标根据上述原理得到的 trans()算法如下,
31
3.1 栈（堆栈）
while(ch!='\0')//只要不是结束符
{
switch(ch)
{
case '(':
op.top++;op.data[op.top]=ch; //若 ch为‘ (’,将其进栈
ch=exp[j++]; //取下一个字符
break;
case ‘)’:// 若 ch为‘ )’
while(op.data[op.top]!=‘(’) //将‘ (’以前的运算符
postexp[i++]=op.data[op.top--]; //出栈并放入
//postexp中
op.top--;//然后删除 op栈中的‘ (’
ch=exp[j++];//取下一个字符
break;
//part 2:扫描中缀表达式,转换为后缀表达
32
3.1 栈（堆栈）
case '+'://若是 +号
case ‘-’://或是 -号,
while( op.top!=-1&&op.data[op.top]!='(‘ )
postexp[i++]=op.data[op.top--]; //将 ‘(‘前的运算符
//依次出栈 并放 入 postexp中
op.top++;op.data[op.top]=ch;//再将 +或 -号进栈
ch=exp[j++];//扫描下一个字符
break;
//part 2:扫描中缀表达式,转换为后缀表达
33
3.1 栈（堆栈）
case '*'://若是乘号 *或除号 /
case '/':
while(op.data[op.top]=='*'||op.data[op.top]=='/')
{ //只要栈顶是乘号 *或除号 /
postexp[i++]=op.data[op.top];
//出栈，依次将栈顶字符存放到数组 exp中
op.top--;//修改栈顶游标
}
op.top++;op.data[op.top]=*exp;
//再将 ch中的乘号 *或除号 /进栈
exp++; //扫描下一个字符
break;
case ' ',break;//过滤掉表达式中可能存在的空格
//part 2:扫描中缀表达式,转换为后缀表达
34
3.1 栈（堆栈）
default://处理数字字符
while(ch>='0'&&ch<'9')//若是 0-9之间的数字
{
postexp[i++]=ch;//将数字字符放入 postexp中
ch=exp[j++];//扫描下一个字符
}
postexp[i++]='#';//用 #号标识一个数值串的结束
} //switch语句的右括号
} // while(ch!= ‘\0‘)语句的右括号
while(op.top!=-1)//扫描完毕,将栈中余下的运算符
postexp[i++]=op.data[op.top--];//出栈并加入 postexp中
postexp[i]=‘\0’;//最后加 上结束符
}//算法函数的右括号
35
3.1 栈（堆栈）
While(ch!=‘0’)
{ 从数组 postexp中取一个字符到 ch中
ch为,+”:从 st中出栈 2个数值 a和 b,计算 c=a+b;将 c进栈
ch为,-”:从 st中出栈 2个数值 a和 b,计算 c=b-a;将 c进栈
ch为,*”,从 st中出栈 2个数值 a和 b,计算 c=b*a;将 c进栈
ch为,/”:从 st中出栈 2个数值 a和 b,计算 c=b/a;将 c进栈
ch为数字,将连续的数字串转换成数值 d;将 d进栈
}
结束，栈顶数值即为表达式的值对后缀表达式求值的算法描述
36
数组 postexp
5
6#
2
0#
-
4#
2#
+
/
栈底
st栈
top
56
56
20
20 a=20
b=56 d-a=3636
4
4
2
2 a=2
b=4
a+b=6
6 6
36 b/a=66
\0
对后缀表达式求值的过程 While(ch!=‘0’){ 从 postexp中取一个字符到 ch中
ch为,+”:从 st中出栈 2个数值 a和 b,
计算 c=a+b;将 c进栈 ;
ch为,-”:从 st中出栈 2个数值 a和 b,
计算 c=b-a;将 c进栈 ;
ch为,*”,从 st中出栈 2个数值 a和 b,
计算 c=b*a;将 c进栈 ;
ch为,/”:从 st中出栈 2个数值 a和 b,
计算 c=b/a;将 c进栈 ;
ch为数字,将连续的数字串转换成数值 d;将 d进栈 ;
}
结束,栈顶即为表达式的值
37
求后缀表达式值的算法 Part A:定义 st栈及相关变量
float compvalue1(char postexp[])
{
struct
{
float data[MaxSize];
int top;
} st;//定义 st栈
float d,a,b,c;
st.top=-1;//设置为空栈
char ch;
int i=0;//i为后缀表达式 postexp[]数组下标
ch=postexp[i++];//取第一个字符
38
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘+’://ch为‘ +’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=a+b;
st.data[++st.top]=c;//将 c进栈
break;
39
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘-’://ch为‘ -’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=b-a;
st.data[++st.top]=c;//运算结果进栈
break;
40
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘*’://ch为‘ *’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=b*a;
st.data[++st.top]=c;//运算结果进栈
break;
41
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘*’://ch为‘ *’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=b*a;
st.data[++st.top]=c;//运算结果进栈
break;
42
求后缀表达式值的算法 Part B:计算后缀表达式值while(ch!='\0')
{
switch(ch)
{
case ‘/’://ch为‘ /’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
if(a!=0)
{ c=b/a; st.data[++st.top]=c;//运算结果进栈
}
else
{ printf("\n\t 除零错误 !\n");
exit(0); //异常退出
}
break;
43
求后缀表达式值的算法 Part B:计算后缀表达式值default://处理数字
d=0;
while(ch>='0'&&ch<='9')
{ d=10*d+ch-‘0’;//
ch=postexp[i++];
}
st.data[++st.top]=d;//进栈
break;
}
ch=postexp[i++];//取下一个字符
}
return(st.data[st.top]);//用函数名返回表达式值
}
将字符型数字转换为整形数值
44
主函数部分代码
int main(int argc,char* argv[])
{
char exp[]={"(56-20)/(4+2)"},postexp[MaxSize];
cout<<"中缀表达式,"<<exp<<endl;
trans(exp,postexp);
cout<<"后缀表达式,"<<postexp<<endl;
cout<<"表达式的值,"<<compvalue(postexp)<<endl;
return 0;
} 运行结果 中缀表达式,(56-20)/(4+2)
后缀表达式,56#20#-4#2#+/
表达式的值,6
Press any key to continue
45
(1)问题的描述给定一个 M× N的迷宫图,求一条从指定入口到出口的路径,假设迷宫如右图所示。
2.求解迷宫问题
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
入口出口同一方块只能走一次 。
46
int mg[10][10]={
{1,1,1,1,1,1,1,1,1,1},//0
{1,0,0,1,0,0,0,1,0,1},//1
{1,0,0,1,0,0,0,1,0,1},//2
{1,0,0,0,0,1,1,0,0,1},//3
{1,0,1,1,1,0,0,0,0,1},//4
{1,0,0,0,1,0,0,0,0,1},//5
{1,0,1,0,0,0,1,0,0,1},//6
{1,0,1,1,1,0,1,1,0,1},//7
{1,1,0,0,0,0,0,0,0,1},//8
{1,1,1,1,1,1,1,1,1,1}};/*9
0 1 2 3 4 5 6 7 8 9*/
(2) 迷宫数据组织
a.存储迷宫的二维数组 0对应图中白方块,表示通道
1对应图中黑方块,表示墙壁
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
47
(2) 迷宫数据组织
typedef struct
{
int i;//方块的行号
int j;//方块的列号
int di;//相邻方块的方向号
} st[MaxSize];//定义顺序栈
int top=-1;//st的栈顶“指针”
b.算法使用的顺序栈存储结构 i j di
0
1
7
2
3
4
5
6
11
8
9
10
top
顺序栈 st
top++;
st[top].i=1;
st[top].j=2;
st[top].di=3 -1 栈底
1 2 3
方块进栈过程演示,
48
(3) 设计运算算法思路,采用“穷举求解”方法,即从入口开始,先沿某一方向前行试探,若能走通,则继续往前行 ;否则沿原路退回 (称为回溯 ),再换另一方向试探,直至所有的通路都试探完为止。
49
0
1
0 1 2 3 4 5
( i,j )
( i-1,j )
( i,j +1)
( i,j -1)
( i+1,j )
上 (方向 0)
右 (方向 1)
下 (方向 2)
左 ( 方向 3)
a.方块 (i,j)的 4个相邻方块方向编号的规定
2
3
4
5
入口出口
i=
j=
上,方向 0; 右,方向 1;
下,方向 2; 左,方向 3
50
( i,j )
( i-1,j )
( i,j +1)
( i,j -1)
( i+1,j )
上 (方向 0)
右 (方向 1)
下 (方向 2)
左 ( 方向 3)
b.从方块 (i,j)向 4个相邻方块试探的先后次序首先试探方向 0,若走不通试探方向 1,若仍走不通试探方向 2,若还是走不通试探方向 3
51
1,3
2,2 2,3 2,4
3,3
方块 (1,3)是方块 (2,3)在方位 0上的可走相邻方块方块 (2,4)是方块 (2,3)在方位 1上的可走相邻方块方块 (3,3)是方块 (2,3)在方位 2上的不可走相邻方块方块 (2,2)是方块 (2,3)
在方位 3上的不可走相邻方块
c.可走相邻方块与不可走相邻方块的定义方向 0
方向 1
方向 2
方向 3
52
i j di
0
1
0 1 2 3 4 5
2
3
4
5
入口出口
0
top
1
7
2
3
4
5
6
11
8
9
10
1 1 -1
1 2 -1
1 3 -12
2 3 -1
2 4 -1
2
3 3 2
4 3 -1
4 4 -1
到达出口
(1,1) (1,2) k(1,3) (2,3) (3,3) (4,3) (4,4)
用顺序栈 st求解迷宫路径的过程演示
j
i 输出迷宫路径入口方块 (xi=1,yi=1)出口方块 (xe=4,ye=4)
-1
53
用顺序栈 st求解迷宫路径过程 (算法描述 )
入口方块进栈,并设其 di为 -1,为避免重走该方块使 mg(xi,yi)=-1
while(st不为空 )
{ 以栈顶方块 (即 i=st[top].i;j=[st[top].j)为当前方块 ;
if (当前方块是出口方块 (M-2,N-2) )
输出迷宫路径,结束 ;
else
{ 以当前方块为起点,在没有试探过的方位上寻找可走相邻方块 ;
if(在某一方向上找到一个可走相邻方块 (即 mg[i,j]=0的方块 )
{ 用该方向号修改当前栈顶的 di;
将找到的可走相邻方块进栈,并设其 di为 -1;
为避免重走至该方块,设其 mg[i,j]为 -1;
}
else {当前方块无可走相邻方块,将其从栈中删除,并设其为其他路径可走方块 (即 mg[st[top].i][st[top].j]=0); }
}
无可走路径,结束。
54
int mgpath(int xi,int yi,int xe,int ye)
{
int i,j,k,di,find;
top++; //入口方块进栈
st[top].i=xi;st[top].j=yi;
st[top].di=-1;
mg[xi][yi]=-1; //避免重走用顺序栈 st求解迷宫路径算法,
Part A 入口方块进栈
55
while(top>-1)//只要栈不为空
{
i=st[top].i; j=st[top].j; di=st[top].di;//取 栈顶方块为当前方块
if(i==xe && j==ye)//若 当前方块是 出口 方块
{
printf(“迷宫路路径如下,\n” );//输出迷宫路径
for(k=0;k<=top;k++)//从栈底至栈顶
{
printf("\t(%d,%d)",st[k].i,st[k].j);
if((k+1)%5==0) //每行输出 5个方块
printf("\n");
}
printf("\n");
return(1);//结束并返回找到一条迷宫路径标志
}
用顺序栈 st求解迷宫路径算法,
Part B 输出迷宫路径
56
find=0;
while(di<4 && find==0)//在没有试探过的方向寻找可走相邻方块
{
di++;//方向 号增 1
switch(di)//取相应方向上的相邻方块元素的二维坐标
{
case 0:i=st[top].i-1;j=st[top].j;break;
case 1:i=st[top].i;j=st[top].j+1;break;
case 2:i=st[top].i+1;j=st[top].j;break;
case 3:i=st[top].i;j=st[top].j-1;break;
}
if(mg[i][j]==0) find=1;//判断是否是 可走相邻方块
}
用顺序栈 st求解迷宫路径算法,
Part C 在没有试探过的方位上寻找当前方块的下一个可走相邻方块
57
if(find==1)//若 找到 当前方块的下一 个可走 相邻 方块
{
st[top].di=di;//修改栈顶元素的方向号
top++;//下一个可 走 相邻 方块进栈
st[top].i=i;st[top].j=j;st[top].di=-1;
mg[i][j]=-1;//为避免重走该方块,将其置为 -1
}
else//当前方块无可走的相邻 方块
{
mg[st[top].i][st[top].j]=0;//让该方块变为其它路径的可走方块
top--;//将该方从栈中删除
}
}
return(0);//无路可走,返回 0;
}
用顺序栈 st求解迷宫路径算法,Part D
58
#include "stdafx.h"
#include <stdlib.h>
#include <iostream.h>
#define MaxSize 100
struct
{
int i;//迷宫方块行号
int j;//迷宫方块列号
int di;//相邻方块方向号
} st[MaxSize];//定义顺序栈
int top=-1;//初始化为空栈设计求解程序 Part A 定义顺序栈 (全局 )
59
int mg[10][10]={
{1,1,1,1,1,1,1,1,1,1},//0
{1,0,0,1,0,0,0,1,0,1},//1
{1,0,0,1,0,0,0,1,0,1},//2
{1,0,0,0,0,1,1,0,0,1},//3
{1,0,1,1,1,0,0,0,0,1},//4
{1,0,0,0,1,0,0,0,0,1},//5
{1,0,1,0,0,0,1,0,0,1},//6
{1,0,1,1,1,0,1,1,0,1},//7
{1,1,0,0,0,0,0,0,0,1},//8
{1,1,1,1,1,1,1,1,1,1}}; /*9
0 1 2 3 4 5 6 7 8 9*/
设计求解程序 Part B 定义迷宫数组 (全局 )
60
int main(int argc,char* argv[])
{
int xi=1,yi=1,xe=8,ye=8;
if(mgpath(xi,yi,xe,ye)==0)
cout<<"无路可走 "<<endl;
return 0;
}
设计求解程序 建立以下主函数调用上述算法
61
迷宫路径如下,
(1,1) (1,2) (2,2) (3,2) (3,1)
(4,1) (5,1) (5,2) (5,3) (6,3)
(6,4) (6,5) (5,5) (4,5) (4,6)
(4,7) (3,7) (3,8) (4,8) (5,8)
(6,8) (7,8) (8,8)
Press any key to continue
运行结果,
请同学们思考,如何修改本算法,使其能输出迷宫中所有的可行路径?
62
3.2 队列
3.2.1 队列的定义队列 (queue)是限定仅在一端插入，另一端删除的线性表。允许插入的一端叫队尾 (rear),允许删除的一端叫对头 (front).
不含元素的空表称为 空队列队列的运算特性是 先进先出
（ First In First Out— FIFO)
1
2
3
4
front
rear一、定义
63
3.2 队列二、队列的基本运算
InitQueue(&q); //初始化队列：构造一个空队列 q
ClearQueue(&q); //销毁队列：释放队列 q占用的存储空间。
QueueEmpty(q); //判断队列是否空：若队列为空，则返回真；否则返回假。
EnQueue(&q,e); //入队操作：将元素 e入队作为队尾元素。
DeQueue(&q,&e); //出队操作：从队列 q中出队一个元素，并将其赋给 e。
Push(s,e)
Pop(s,e)
64
3.2 队列对队列的操作：
实际模型
1 2
65
3.2 队列
3.2.2 队列的顺序存储结构及其基本运算的实现
1,一般顺序存储结构结构定义：
typedef struct
{ElemType data[MaxSize];
int front,rear;
} SeQueue;
用数组顺序存放存储队列中的所有元素，利用两个整型变量分别存储队首和队尾元素的下标位置，
分别称它们为队首和队尾指针。 并约定,头指针
sq.front总是指向队头元素的前一个位置；尾指针
sq.rear指向队尾元素。
队列变量定义：
SeQueue *q,sq;
66
3.2 队列线性模型
-1 0 1 2 3 4 5 6
a1
enQueue(q,a1)
a2 a3 a4 a5 a6 a7
enQueue(q,a2) enQueue(q,a3)
deQueue(q,a1) enQueue(q,a4) enQueue(q,a5)
deQueue(q,a2) enQueue(q,a6) enQueue(q,a7)
enQueue(&q,a8)
出现“假溢出”，那么该如何解决？
67
3.2 队列
2,循环队列
enQueue(q,a1)
enQueue(q,a2)
enQueue(q,a3)
deQueue(q,a1)
enQueue(q,a4)
enQueue(q,a5)
deQueue(q,a2)
enQueue(q,a6)
enQueue(q,a7)
enQueue(q,a8)
1
2 3
4
5
6
0
a1
a2 a3
a4
a5a6
a7
a8
i=(i+1)%MaxSixe
入队,rear++，再将数据入队出队：先将数据出队,front++
68
3.2 队列
2,循环队列
1
2 3
4
5
6
0
如何判队列是空队列还是满队列呢？
队空条件为,q->rear= =q->front
队满条件为,(q->rear+1)%MaxSize= =q->front
出入队操作指针如何变化？
解决方法,少用一个单元，令 sq.front指向的单元总为空,
69
3.2 队列
3,循环队列的基本运算入队列 enQueue(q,e)
算法思想,在队列不满的条件下,先将 队尾指针 rear
循环增 1,然后将元素添加到该位置 。 对应算法如下,
int enQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+1)%MaxSize==q->front) /*队满 */
return 0;
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return 1;
}
70
3.2 队列循环队列的入队操作
a2入队：
sq.rear=(sq.rear+1)%MaxSize;
1
2 3
4
5
6
0
a1
ai-1 …
a2
ai
Sq.elem[sq.rear]=ai;
ai入队：
1
2 3
4
56
0
a1
a2
sq.rear++;
sq.data[sq.rear]=a2；
if(sq.rear+1>=maxsize)
sq.rear=0;
sq.data[sq.rear]=ai
71
3.2 队列
3,循环队列的基本运算出队列 deQueue(q,e)
算法思想,在队列 q不为空的条件下,将 队首指针 front
循环增 1,并将该位置的元素值赋给 e。对应算法如下,
int deQueue(SqQueue *&q,ElemType &e)
{
if (q->front==q->rear) /*队空 */
return 0;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return 1;
}
72
3.2 队列循环队列的出队操作
a1出队：
1
2 3
4
5
6
0 a
1
…
a2
ai
a1出队：
1
2 3
4
56
0
a1 a2
Sq.front++;
a3
if(sq.front+1>=maxsize)
sq.front=0;
sq.front=(sq.front+1)%maxsize
73
3.2 队列一、链队数据类型定义 (使用两种类型的结点 )
1、链队数据结点类型定义 (用于存储链队数据 )
typedef struct quode
{ ElemType data;//数据结点的数据域
struct quode *next;//数据结点的指针域
} QNode;
2、链队首、尾指针结点 (简称链队结点 )类型定义
typedef struct
{ QNode *front;//队首指针
QNode *rear;//队尾指针
} LiQueue;
front
rear
data next
数据结点链队结点队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。其类型定义如下：
3.2.3 队列的链式存储结构及其基本运算的实现区分指针 q和指针 front/rear
74
3.2 队列二、链队的基本运算算法
void InitQueue(LiQueue *&q)
{ q=(LiQueue *)malloc(sizeof(LiQueue));
q->front=q->rear=NULL;//初始化队列首与尾指针
}
设主函数中调用的语句为：
LiQueue q;
InitQueue(q); q
front
rear
∧
∧
该算法仅生成了一个包含队首指针和队尾指针域均为空的结点,可视为一个空队列。
1、初始化队列 InitQueue(q):构造一个空队列。
75
3.2 队列
4,入队列 enQueue(q,e):创建一个数据结点,若实参传送的队列为空,将队首、队尾指针均指向该数据结点，否则将该数据结点链接到队尾,并将队尾指针指向该结点。
76
3.2 队列4、入队列过程演示
void enQueue(LiQueue *&q,ElemType e)
{ QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=e;
s->next=NULL;
if(q->rear==NULL)//若链队列为空 (无数据结点 )
q->front=q->rear=s;
else
{ q->rear->next=s;//在队尾插入新结点
q->rear=s;//尾指针指向新结点
}
}
q
front
rear
∧
∧
— (1)若实参传送的是一空队列 q
e=‘a’‘
data next
s ‘a’ ∧
入队结束
77
3.2 队列4、入队列过程演示
void enQueue(LiQueue *&q,ElemType e)
{ QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=e;
s->next=NULL;
if(q->rear==NULL)//若链队列为空 (无数据结点 )
q->front=q->rear=s;
else
{ q->rear->next=s;//在队尾插入新结点
q->rear=s;//尾指针指向新结点
}
}
q
front
rear
— (2)若实参传送的是非空队列 q
e=‘b’‘
s‘a’ ∧
入队结束
‘b’ ∧
78
3.2 队列
5、出队列 deQueue(q,e),将队列的第一个数据结点删除
int deQueue(LiQueue *&q,ElemType &e)
{ QNode *t;
if(q->rear==NULL)//队列为空
return 0;
t=q->front;//t指向要删除的第一个数据结点
if(q->front==q->rear)//若队中仅有一个数据结点
q->front=q->rear=NULL;//将首,尾指针设为空
else
q->front=q->front->next;//将原首结点后继
//设为首结点
e=t->data;
free(t);//释放被删除结点的存储空间
return 1;//返回出队成功标志
}
79
3.2 队列
3.2.4 队列的应用举例求解报数问题设有 n个人站成一排，从左向右的编号分别为 1～ n，现在从左往右报数,1,2,1,2…”,
数到 1的人出列，数到 2的人站到队列的最右端。
报数过程反复进行，直到所有的人全部出列为止。求出他们的出列顺序。
1 2 3 4 5 6 7 8
80
3.2 队列编程思想,将 n个人按编号入队，然后反复执行如下操作，直到队列为空。
（ 1）出队一个元素，输出其编号
（ 2）若队列不空，再出队一个元素，并将其重新入队。
81
2.解迷宫问题
(1)问题的描述
(2)数据组织使用一个顺序队列 Qu记录走过的方块,顺序队列的结构如下,
struct
{ int i,j; //方块的位置
int pre; //本路径中上一方块在 Qu中的下标
} Qu[MaxSize];
int front=-1,rear=-1; //队首指针和队尾指针
3.2.4 队列的应用举例
82
顺序队列 Qu的存储结构
#define MaxSize 9
struct
{
int i,j;//方块位置
int pre;//上一方块在队
//列中的一维下标
} Qu[MaxSize];
int front=-1;//队首“指针”
rear=-1;//队尾“指针”
顺序队列 Qu的定义
i j pre
7
5
6
3
4
2
1
0
MaxSize-1
fr
rear++;//入队 1次
Qu[rear].i=1;
Qu[rear].j=1;
Qu[rear].pre=-1;
1 1 -1
Qu[rear].i=1;
Qu[rear].j=2;
Qu[rear].pre=0;
rear++;//入队 1次
1 2 0
front++;//出队 1次执行语句-1
0
1
0 1 2
2
入口 如何在队列 Qu中记录从方块 (1,1)
走到方块 (1,2)的过程呢？
说明,
队列 Qu记录搜索迷宫所走过的方块,所以,出队时并不将出队元素从队中删除 ;
83
迷宫与迷宫数组 mg
int mg[6][6]={
/* 0 1 2 3 4 5 */
/*0*/ {1,1,1,1,1,1},
/*1*/ {1,0,0,0,1,1},
/*2*/ {1,0,1,0,0,1},
/*3*/ {1,0,0,0,1,1},
/*4*/ {1,1,1,0,0,1},
/*5*/ {1,1,1,1,1,1}};
入口方块位置,xi=1,yi=1
出口方块位置,xe=4,ye=4
0
1
0 1 2 3 4 5
2
3
4
5
出口入口
i
j
84
( i-1,j )
( i,j +1)( i,j -1)
( i+1,j )
上 (方向 0)
右 (方向 1)
下 (方向 2)
左 ( 方向 3)
方块 (i,j)的 4个相邻方块方向编号的规定
( i,j )
85
0
1
0 1 2 3 4 5 i j pre
13
17
7
12
5
6
3
4
14
2
1
0
2
3
4
5
出口入口
9
10
16
11
15
8
i j prefr
1 1 -1
0
0
1
2
3
4
5
5
(1,1) (1,2) (1,3) (2,3)
(3,3) (4,3) (4,4)
搜索迷宫路径的过程 队列 Qu的数据变化过程
i
j
1 2
2 1
1 3
3 1
2 3
3 2
2 4
8
9
3 3
4 3
4 4 -1
-1
-1
-1
-
-1
(3)设计运算算法
86
(1,1)
(1,2)
(1,1)
用队列对迷宫路径的搜索方法
(2,1)
(1,3) (3,1)
(2,3) (3,2)
(2,4) (3,3)
(4,3)
(4,4)
×
(1,2) (1,3) (2,3)
(3,3) (4,3) (4,4)
这样的搜索方法称为广度优先搜索方法,所求路径为最短路径。
0
1
0 1 2 3 4 5
2
3
4
5
出口入口
i
走出迷宫的一条路径入口方块出口方块
87
用队列对迷宫路径的搜索方法
//int xi=1,yi=1,xe=8,ye=8;
int mg[10][10]={
{1,1,1,1,1,1,1,1,1,1},//0
{1,0,0,1,1,1,0,0,0,1},//1
{1,0,0,1,1,1,0,1,0,1},//2
{1,0,0,0,0,1,0,1,0,1},//3
{1,0,1,1,0,1,0,1,0,1},//4
{1,0,1,1,0,0,0,1,0,1},//5
{1,0,1,1,1,1,1,0,0,1},//6
{1,0,1,1,1,0,1,1,0,1},//7
{1,0,0,0,0,0,0,0,0,1},//8
{1,1,1,1,1,1,1,1,1,1}};/*9
0 1 2 3 4 5 6 7 8 9*/
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
88
用队列对迷宫路径的搜索方法
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
第 1条路径 (最短 15个方块 )
(1,1) (2,1) (3,1) (4,1) (5,1)
(6,1) (7,1) (8,1) (8,2) (8,3)
(8,4) (8,5) (8,6) (8,7) (8,8)
第 2条路径 (23个方块 )
(1,1) (1,2) (2,2) (3,2) (3,3)
(3,4) (4,4) (5,4) (5,5) (5,6)
(4,6) (3,6) (2,6) (1,6) (1,7)
(1,8) (2,8) (3,8) (4,8) (5,8)
(6,8) (7,8) (8,8)
89
A.用队列求解迷宫路径的算法描述
mgpath(xi,yi,xe,ye)
将入口方块 (xi,yi)入队,并设其 mg[xi,yi]=-1 及域 pre=-1,
出队一次 (即 front++)_;
while(队列不为空且未找到一条走出迷宫的路径 )
{ 以队首方块作为当前方块 ;
if(当前方块是出口方块 )
{ 置找到迷宫路径标志为 1; 输出走出迷宫的路径 ;退出 ;}
else
{ 以当前方块为起点,分别按方向 0至方向 3的顺序搜索当前方块的所有的相邻方块
if(是可走方块 )
{该方块的坐标入队 ;
该方块的起始方块在队列中的下标入队 ;
将该方块对应的迷宫数组元素值置为 -1,以避免重走 ;
}
}
出队一次
}
90
B.输出迷宫路径的算法描述 print(front)
a.给一条迷宫路径的所有方块设置标识符 -1
k=队尾元素的下标 ;
Do
{ j=k;//保存 k值
k=Qu[k].pre;//获取本方块的上一方块在队列中的下标
Qu[j].pre=-1;//设置标识符 -1
} While(k!=0}
b.输出迷宫路径
k=0;
while(k<MaxSize)
{
if(Qu[k].pre==-1)
按每行 5个元素格式输出 Qu[k].i与 Qu[k].j;
k++;
}
91
(4)迷宫路径搜索算法
int mgpath(int xi,int yi,int xe,int ye)
{ int i,j,find=0,di;
rear++; Qu[rear].i=xi;Qu[rear].j=yi; //队首方块入队
Qu[rear].pre=-1; mg[xi][yi]=-1;
while(front<rear && !find)//
{
front++；
i=Qu[front].i; j=Qu[front].j;//以队首方块为当前方块
if((i==xe)&&(j==ye))//若当前方块为出口方块
{ find=1;//找到一条迷宫路径标志
print(front);//调用输出迷宫路径函数
return (1);//找到一条路径时返回 1
}
92
for(di=0;di<=3;di++)
{ switch(di)
{ case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break; }
if(mg[i][j]==0)//找到下一个可走相邻方块
{ rear++;//尾指针前移,准备入队操作
Qu[rear].i=i;Qu[rear].j=j;//可走相邻方块入队
Qu[rear].pre=front;//当前方块的下标入队
mg[i][j]=-1;//避免再重复搜索此方块 }
}
}
return (0);//未找到一条路径时返回 0(课本此处注释错 )
}
93
void print(int front)
{
int k=front,j,ns=0;//k指向队尾
printf("\n");
do //从队尾回推到队首,将路径中的所有方块的 pre置
//为 -1
{
j=k;
k=Qu[k].pre;//保存本方块的上层方块下标
Qu[j].pre=-1;//该方块的 pre域置为 -1
}while(k!=0);//一直遇到队首 (k=0)为止
(5)输出迷宫路径算法
94
printf("用队列求解迷宫的路径如下,\n");
k=0;
while(k<MaxSize)
{
if(Qu[k].pre==-1)//只输出队列中 pre=-1的存储单元
{ ns++;
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(ns%5==0) printf("\n");//按每行 5个元素格式输出
}
k++;
}
printf("\n");
}
95
int main(int argc,char* argv[])
{
int xi=1,yi=1;//入口方块坐标
int xe=8,ye=8;//出口方块坐标
if(mgpath(xi,yi,xe,ye)==0)//调用队列求解迷宫函数
cout<<"迷宫无可走路径 !"<<endl;
return 0;
}
(6)主函数中的相关语句说明,
(1)迷宫数组定义为全局变量 (在主函数之前定义 )
(2)顺序队列 Qu也定义为全局变量 (在主函数之前定义 )
96
本章小结本章基本学习要点如下,
(1)理解栈和队列的特性以及它们与线性表之间的差异,能根据具体情况选用合适的数据结构及物理存储结构 。
线性表、栈、队列的异同点
相同点,逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即操作受限的线性表 (只是对插入、
删除运算加以限制 )。
97
小 结：
线性表、栈、队列的异同点
不同点,
① 运算规则不同,
线性表的插入、删除等基本操作可针对表中的任意位置的数据元素；
而栈是只允许在一端（栈顶）进行插入和删除运算，因而是后进先出表 LIFO；
队列是只允许在队尾进行插入、队头进行删除运算，因而是先进先出表 FIFO。
② 用途不同,线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟,OS作业调度和简化设计等。
98
(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意顺序栈满和栈空的条件 。
(3)重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件 。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题 。
小 结：
99
上机题 3.5使用的迷宫
int mg2[6][6]={
{1,1,1,1,1,1},//0
{1,0,0,0,1,1},//1
{1,0,1,0,0,1},//2
{1,0,0,0,1,1},//3
{1,1,0,0,0,1},//4
{1,1,1,1,1,1}}; //5
/*0 1 2 3 4 5 */
0
1
0 1 2 3 4 5
2
3
4
5
j
i
10
0
第 4条路径的方块数为,7
(1,1) (2,1) (3,1) (3,2) (4,2) (4,3)
(4,4)
0
1
0 1 2 3 4 5
2
3
4
5
j
i
第 1条路径的方块数为,7
(1,1) (1,2) (1,3) (2,3) (3,3)
(4,3) (4,4)
第 2条路径的方块数为,9
(1,1) (1,2) (1,3) (2,3) (3,3)
(3,2) (4,2) (4,3) (4,4)
第 3条路径的方块数为,7
(1,1) (2,1) (3,1) (3,2) (3,3)
(4,3) (4,4)
第三章 栈和队列
3.1 栈栈的定义、栈的存储结构、栈的应用。
队列的定义、队列存储结构、队列的应用。
3.2 队列
栈和队列的逻辑结构和物理结构，以及它们之间的相互关系
定义与之相适应的运算
设计相应的算法
分析算法的效率
2
3.1.1 栈的定义一,栈的概念栈 (stack)是 插入 和 删除 操作限定在 一端 进行的 线性表 。
栈的逻辑表示为,S=(a1,a2,…a n)
栈顶 (top),表中允许进行插入、删除操作的一端。
栈顶的当前位置是动态 (变化的 )的,栈顶的当前位置由一个称为栈顶指针的位置指示器来指示。
栈底 (bottom):表的另一固定端 (非变化的 )
不含元素的栈称为 空栈,
3.1 栈（堆栈）
3
3.1.1 栈的定义一,栈的概念栈的 运算特性 是后进先出 (Last In First Out— LIFO)
或先进后出 (First In Last Out— FILO)
3.1 栈（堆栈）
栈底 (固定端 )
1 2 3 4
栈顶进栈顺序出栈顺序
4
例 3.1 一个栈的输入序列为 abcd,则下列序列中不可能是栈的输出序列的是 ( )
3.1 栈（堆栈）
A,bcda B,dacb C,bcad D,adcb
二,栈的基本运算初始化栈 InitStack(s):构造一个空栈 s。
销毁栈 ClearStack(s):释放栈 s占用的存储空间 。
求栈的长度 StackLength(s):返回栈 s中的元素个数 。
判断栈是否为空 StackEmpty(s):若栈 s为空,则返回真；
否则返回假。
5
进栈 Push(s,e):入栈操作，在栈 s顶部插入元素 e。
出栈 Pop(s,e):出栈函数，若 s不空，则返回栈顶元素并将其值赋给 e，然后删除该栈顶元素；否则返回空元素 NULL。
取栈顶元素 GetTop(s,e):返回当前的栈顶元素,并将其值赋给 e,与 Pop(s,e)函数的差别在不删除栈顶元素。
显示栈中元素 DispStack(s):从栈顶到栈底顺序显示栈中所有元素。
3.1 栈（堆栈）
二,栈的基本运算
6
3.1.2栈的顺序存储结构及其基本运算的实现顺序栈,即栈的顺序存储结构，是利用一组 地址连续 的存储单元（数组）依次存放栈的数据元素。同时附设 指针 top指示栈顶元素在顺序栈中的位置。
3.1 栈（堆栈）
一,顺序栈的存储结构描述
# define MaxSize 50
typedef int(char,…) Elemtype;
typedef struct
{ElemType data[MaxSize];
int top; //栈顶元素位置
} SqStack;
顺序栈的类型定义：
SqStack *s,s1;
如何访问栈顶元素？
7
3.1 栈（堆栈）
s->data[i]表示第 i+1个进栈的元素；
s->data[s->top]表示栈顶元素；
当 s->top=-1表示 空栈 ；
当 s->top=MaxSize-1表示 栈满 ；
顺序栈的特点：
data
top
低地址高地址
0
1
2
n
s
a
b
c
d
栈中元素个数或栈的长度为：
s->top＋ 1。
8
二,顺序栈的基本运算
初始化栈 InitStack(s)
void InitStack(SqStack *&s)
{ //对栈 s进行初始化
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
建立一个新的空栈 s,实际上是将栈顶指针指向 -1即可。
top 栈底-1
0
1
2
…MaxSize-1
顺序栈 s
空栈
3.1 栈（堆栈）
9
二,顺序栈的基本运算
销毁栈 ClearStack(s)
void ClearStack(SqStack *&s)
{
free(s);
}
int StackLength(SqStack *s)
{
return(s->top+1);
}
求栈的长度 StackLength(s)
top
栈底-1
0
1
2
…MaxSize-1
顺序栈 s
3.1 栈（堆栈）
10
二,顺序栈的基本运算
判断栈是否为空 StackEmpty(s)int StackEmpty(SqStack *s)
{
return(s->top==-1);
}
显示栈中元素 DispStack(s)
void DispStack(SqStack *s)
{//从栈顶到栈底顺序显示栈中所有元素。
int i;
for (i=s->top;i>=0;i--)
printf("%c ",s->data[i]);
printf("\n");
}
3.1 栈（堆栈）
11
int Push(SqStack *s,ElemType e)
{
if(s->top==MaxSize-1)
return 0;//栈已满 (即上溢 ),返回 0
s->top++;//栈顶“指针”加 1
s->data[s->top]=e;//将 e值放入栈顶
return 1;
} top
栈底-1
0
1
2
…MaxSize-1
栈 s
26
8
12
3
e=78
s->top++;
s->data[s->top]=e; s->data[++s->top]=e;
3.1 栈（堆栈）
进栈函数 Push(s,e)的实现算法思想：若栈满返回 0；否则将 e入栈，并返回 1
相当于顺序表的 ListInsert(L,n+1,e)
12
int Push(SqStack *s,ElemType e)
{
if(s->top==MaxSize-1)
return 0;//栈已满 (即上溢 ),返回 0
s->data[++s->top]=e;//将 e值进栈
return 1;
}
3.1 栈（堆栈）
进栈函数 Push(s,e)的实现
13
int Pop(SqStack *&s,ElemType &e)
{
if(s->top==-1)
return 0;//栈为空 (下溢 )
e=s->data[s->top];//将栈顶元素赋给 e
s->top--;//修改栈顶指针
return 1;//返回出栈成功标志
}
top
栈底-1
0
1
2
…MaxSize-1
栈 s
26
8
12
3
调用语句,Pop(s,e)e
=
3.1 栈（堆栈）
出栈函数 Pop(s,e)的实现算法思想：若栈空返回 0；否则返回栈顶元素并将其赋给 e，然后返回 1。 相当于顺序表的 ListDelete(L,n,e)
14
int Pop(SqStack *&s,ElemType &e)
{
if(s->top==-1)
return 0;//栈为空中 (下溢 )
e=s->data[s->top--];//出栈并将出栈元素赋给 e
return 1;//返回出栈成功标志
}
3.1 栈（堆栈）
出栈函数 Pop(s,e)的实现
15
[例 3.4]编写一个算法，利用顺序栈判断一个字符串是否为对称串。所谓对称串是指从左向右读和从右向左读的序列相同。
如字串：,bccb”从左向右读为,bccb”,从右向左读为,bccb”，所以该字串是个对称串
3.1 栈（堆栈）
16
int symmetry(ElemType str[])
{
int i;ElemType e; SqStack *st;
InitStack(st);
for(i=0;str[i]!='\0';i++)
Push(st,str[i]);
for(i=0;str[i]!='\0';i++)
{ Pop(st,e);
if(str[i]!=e)
return(0);
}
return(1);
} top -1
0
1
2
…MaxSize-1
栈 st
c
b
1 ‘b’
c
ElemType str[]={'b',‘c',‘c',‘b','\0'};
e=
3.1 栈（堆栈）
17
int main(int argc,char* argv[])
{
ElemType str[]={'b',‘c',‘c',‘b','\0'};
if(symmetry(str))
cout<<"是对称字符串！ "<<endl;
else
cout<<"非对称字符串！ "<<endl;
return 0;
}
主函数调用上述算法
3.1 栈（堆栈）
18
3.1 栈（堆栈）
3.1.3 栈的链式存储结构及其基本运算的实现
Head ‘a’ ∧
‘b’
‘c’
头结点栈顶结点栈底结点链栈示意图若 Head->next=NULL表明栈为空,且只要内存足够,链栈的长度不受限制。
19
3.1 栈（堆栈）
3.1.3 栈的链式存储结构及其基本运算的实现
typedef char ElemType;
typedef struct linknode
{ ElemType data;
struct linknode *next;
}LiStack;
一,链栈的存储结构描述链栈的类型说明如下：
20
3.1 栈（堆栈）
void Push(LiStack *&s,ElemType e)
{/*S是表示一个带头结点的链栈 */
LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e;
p->next=s->next;
s->next=p;
}
s ∧ p ‘a’
调用语句为 Push(s,‘a’)s ‘a’
∧
p ‘b’
‘b’c’
p ‘c’
设进栈函数 Push(s,e)的实现
21
3.1 栈（堆栈）
int Pop(LiStack *&s,ElemType &e)
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
free(p);
return 1;
} s ‘a’
调用语句为 Push(s,e)e
∧
‘b’
p ‘c’
=
出栈函数 Pop(s,e)的实现
22
3.1 栈（堆栈）
例 3.5 一数学表达式存储在一维数组 exp[]中，
编写一个算法判断表达式 exp中的左右括号是否配对。
算法思路：
从左至右扫描表达表 exp,若遇到左括号,将其进栈,继续扫描余下的表达式,若遇到右括号,
将栈顶元素 (即左括号 )出栈,一直到表达式 exp
的所有元素扫描完为止。
若栈为空,说明表达式左右括号配对,函数返回
1，否则，说明左右括号不配对，函数返回 0。
23
3.1 栈（堆栈）
3.1.4 栈的应用举例
1,表达式求值
(1)问题的描述用户输入一个合法的数学表达式,设计一个算法计算用户所输入的表达式的值 。
为简单起见,这里限定用户输入的是一个包含,+”、
,-”,,*”,,/”,正整数和圆括号的合法数学表达式,如,(56-20)/(4+2)
(2)数据组织用户输入的数学表达式用一维数组 exp[]存储；
算法使用顺序栈 op与另一数组 postexp[]处理用户输入的数学表达式 。
24
3.1 栈（堆栈）
(3)设计运算算法
A.与表达式相关的两个概念：
(a)中缀表达式,
运算符位于两个数字 (常称为操作数 )之间的表达式称为中缀表达式 。 通常书写的数学表达式就是中缀表达,如 (56-20)/(4+2) 是个中缀表达式 。
(b)后缀表达式,
运算符位于操作数后的表达式称为后缀表达式 。 如
5620-42+/是个后缀表达式,使用后缀表达式有利于计算机计算表达式的值,因此表达式求值的过程是：
Step1:将通常的算术表达式 (即中缀表达式 )转换为后缀表达式 ;
Step2,对后缀表达式求值 。
25
3.1 栈（堆栈）
Step1:将通常的算术表达式 (即中缀表达式 )转换为后缀表达式 ;
算符优先关系表 a+b*c-d/(e-f+g)
26
3.1 栈（堆栈）
如何由中缀表达式求后缀表达式？
求后缀表达式转换规律：
1,设立 运算符 栈；
2,依次读入表达式中的每个字符，若是 操作数,则直接发送给后缀式； 若是运算符，则和运算符栈 栈顶算符 进行优先级比较：
3,重复 (2),直到表达式读取完毕。
若栈顶算符优先级高，退出栈顶运算符并发给后缀式；
若与栈顶算法相等，则作（）处理。
若栈顶算符优先级低，则将该运算符作 进栈 操作；
Step1:将通常的算术表达式 (即中缀表达式 )转换为后缀表达式 ;
27
3.1 栈（堆栈）
3.1.4 栈的应用举例
while (ch!='\0')
{ 从数组 exp[]取一个字符到变量 ch中 ;
if ch为数字,将后续的所有数字依次存放到数组
postexp中,并以,#”标志数值串结束 ;
if ch为,(”,将此括号进栈到栈 op中 ;
if ch为,)”:将栈 op中,(”以前的运算符 (若有的话 )
依次出栈并存放到数组 postexp中,然后将,(”从 op栈中删除 ;
if ch为,+”或,-”:将栈 op中,(”以前的运算符依次出栈并存放到数组 postexp中,然后将,+”或,-”进栈 ;
if ch为,*” 或,/”:将 op栈中,*” 或,/”运算符依次出栈并存放到数组 postexp中,然后将,*” 或,/”进栈；
}
B 中缀表达转换为后缀表达式的过程 (算法描述 )
28
3.1 栈（堆栈）
字符数组 exp扫描完毕,将 op栈中余下的所有运算符依次出栈并放入数组 postexp中,最后给数组 postexp
加入结束符 ‘\0’,此时 postexp中的内容就是由中缀表达式转换的后缀表达式 。
设有表达式,(56-20)/(4+2),由用户从键盘输入,并存储在字符型数组中,可使用 C\C++语言定义并初始化表达式数组 exp[]:
char exp[]={'(','5','6','-','2','0',')','/','(','4','+','2',')','\0'};
或者,
char exp[]={"(56-20)/(4+2)"};
注,这里重点是学习算法,实际中算术表达由用户从键盘输入,
29
3.1 栈（堆栈）
(
5
6-
2
0
)
/
(
4
+
2
)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
exp
栈底
op栈
top
postexp
\0
(
5
6#
-
2
0#
-
/
(
4#
+
2#
+
/
\0
中缀表达转换为后缀表达式的过程
char exp[]={"(56-20)/(4+2)"};
while (ch!='\0')
{ 从 exp取一个字符到 ch中 ;
if ch为数字,将后续的所有数字依次存放到数组 postexp中,并以,#”
标志数值串结束 ;
if ch为,(”,将此括号进栈到栈 op
中 ;
if ch为,)”:将栈 op中,(”以前的运算符 (若有的话 )依次出栈并存放到数组 postexp中,然后将,(”从 op
栈中删除 ;
if ch为,+”或,-”:将栈 op中,(”
以前的运算符依次出栈并存放到数组 postexp中,然后将,+”或,-”进栈 ;
if ch为,*” 或,/”:将 op栈中,*”
或,/”运算符依次出栈并存放到数组 postexp中,然后将,*” 或,/”进栈；
}
字符数组 exp扫描完毕,
将 op栈中余下的所有运算符依次出栈并放入数组 postexp中,最后数组
postexp中的内容就是由中缀表达式转换的后缀表达式 。
56#20#-4#2#+/
30
3.1 栈（堆栈）
//part 1:建立 op栈与 postexp数组
void trans(char exp[],char postexp[])
{
char ch;
struct
{
char data[MaxSize];
int top;
} op;//定义 op栈
op.top=-1;//设置为空栈
int i=0,j=0;// i为 exp的下标,j为 postexp的下标根据上述原理得到的 trans()算法如下,
31
3.1 栈（堆栈）
while(ch!='\0')//只要不是结束符
{
switch(ch)
{
case '(':
op.top++;op.data[op.top]=ch; //若 ch为‘ (’,将其进栈
ch=exp[j++]; //取下一个字符
break;
case ‘)’:// 若 ch为‘ )’
while(op.data[op.top]!=‘(’) //将‘ (’以前的运算符
postexp[i++]=op.data[op.top--]; //出栈并放入
//postexp中
op.top--;//然后删除 op栈中的‘ (’
ch=exp[j++];//取下一个字符
break;
//part 2:扫描中缀表达式,转换为后缀表达
32
3.1 栈（堆栈）
case '+'://若是 +号
case ‘-’://或是 -号,
while( op.top!=-1&&op.data[op.top]!='(‘ )
postexp[i++]=op.data[op.top--]; //将 ‘(‘前的运算符
//依次出栈 并放 入 postexp中
op.top++;op.data[op.top]=ch;//再将 +或 -号进栈
ch=exp[j++];//扫描下一个字符
break;
//part 2:扫描中缀表达式,转换为后缀表达
33
3.1 栈（堆栈）
case '*'://若是乘号 *或除号 /
case '/':
while(op.data[op.top]=='*'||op.data[op.top]=='/')
{ //只要栈顶是乘号 *或除号 /
postexp[i++]=op.data[op.top];
//出栈，依次将栈顶字符存放到数组 exp中
op.top--;//修改栈顶游标
}
op.top++;op.data[op.top]=*exp;
//再将 ch中的乘号 *或除号 /进栈
exp++; //扫描下一个字符
break;
case ' ',break;//过滤掉表达式中可能存在的空格
//part 2:扫描中缀表达式,转换为后缀表达
34
3.1 栈（堆栈）
default://处理数字字符
while(ch>='0'&&ch<'9')//若是 0-9之间的数字
{
postexp[i++]=ch;//将数字字符放入 postexp中
ch=exp[j++];//扫描下一个字符
}
postexp[i++]='#';//用 #号标识一个数值串的结束
} //switch语句的右括号
} // while(ch!= ‘\0‘)语句的右括号
while(op.top!=-1)//扫描完毕,将栈中余下的运算符
postexp[i++]=op.data[op.top--];//出栈并加入 postexp中
postexp[i]=‘\0’;//最后加 上结束符
}//算法函数的右括号
35
3.1 栈（堆栈）
While(ch!=‘0’)
{ 从数组 postexp中取一个字符到 ch中
ch为,+”:从 st中出栈 2个数值 a和 b,计算 c=a+b;将 c进栈
ch为,-”:从 st中出栈 2个数值 a和 b,计算 c=b-a;将 c进栈
ch为,*”,从 st中出栈 2个数值 a和 b,计算 c=b*a;将 c进栈
ch为,/”:从 st中出栈 2个数值 a和 b,计算 c=b/a;将 c进栈
ch为数字,将连续的数字串转换成数值 d;将 d进栈
}
结束，栈顶数值即为表达式的值对后缀表达式求值的算法描述
36
数组 postexp
5
6#
2
0#
-
4#
2#
+
/
栈底
st栈
top
56
56
20
20 a=20
b=56 d-a=3636
4
4
2
2 a=2
b=4
a+b=6
6 6
36 b/a=66
\0
对后缀表达式求值的过程 While(ch!=‘0’){ 从 postexp中取一个字符到 ch中
ch为,+”:从 st中出栈 2个数值 a和 b,
计算 c=a+b;将 c进栈 ;
ch为,-”:从 st中出栈 2个数值 a和 b,
计算 c=b-a;将 c进栈 ;
ch为,*”,从 st中出栈 2个数值 a和 b,
计算 c=b*a;将 c进栈 ;
ch为,/”:从 st中出栈 2个数值 a和 b,
计算 c=b/a;将 c进栈 ;
ch为数字,将连续的数字串转换成数值 d;将 d进栈 ;
}
结束,栈顶即为表达式的值
37
求后缀表达式值的算法 Part A:定义 st栈及相关变量
float compvalue1(char postexp[])
{
struct
{
float data[MaxSize];
int top;
} st;//定义 st栈
float d,a,b,c;
st.top=-1;//设置为空栈
char ch;
int i=0;//i为后缀表达式 postexp[]数组下标
ch=postexp[i++];//取第一个字符
38
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘+’://ch为‘ +’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=a+b;
st.data[++st.top]=c;//将 c进栈
break;
39
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘-’://ch为‘ -’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=b-a;
st.data[++st.top]=c;//运算结果进栈
break;
40
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘*’://ch为‘ *’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=b*a;
st.data[++st.top]=c;//运算结果进栈
break;
41
求后缀表达式值的算法 Part B:计算后缀表达式值
while(ch!='\0')
{
switch(ch)
{
case ‘*’://ch为‘ *’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
c=b*a;
st.data[++st.top]=c;//运算结果进栈
break;
42
求后缀表达式值的算法 Part B:计算后缀表达式值while(ch!='\0')
{
switch(ch)
{
case ‘/’://ch为‘ /’
a=st.data[st.top--]; //第 1个数值出栈并送 a
b=st.data[st.top--]; //第 2个数值出栈并送 b
if(a!=0)
{ c=b/a; st.data[++st.top]=c;//运算结果进栈
}
else
{ printf("\n\t 除零错误 !\n");
exit(0); //异常退出
}
break;
43
求后缀表达式值的算法 Part B:计算后缀表达式值default://处理数字
d=0;
while(ch>='0'&&ch<='9')
{ d=10*d+ch-‘0’;//
ch=postexp[i++];
}
st.data[++st.top]=d;//进栈
break;
}
ch=postexp[i++];//取下一个字符
}
return(st.data[st.top]);//用函数名返回表达式值
}
将字符型数字转换为整形数值
44
主函数部分代码
int main(int argc,char* argv[])
{
char exp[]={"(56-20)/(4+2)"},postexp[MaxSize];
cout<<"中缀表达式,"<<exp<<endl;
trans(exp,postexp);
cout<<"后缀表达式,"<<postexp<<endl;
cout<<"表达式的值,"<<compvalue(postexp)<<endl;
return 0;
} 运行结果 中缀表达式,(56-20)/(4+2)
后缀表达式,56#20#-4#2#+/
表达式的值,6
Press any key to continue
45
(1)问题的描述给定一个 M× N的迷宫图,求一条从指定入口到出口的路径,假设迷宫如右图所示。
2.求解迷宫问题
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
入口出口同一方块只能走一次 。
46
int mg[10][10]={
{1,1,1,1,1,1,1,1,1,1},//0
{1,0,0,1,0,0,0,1,0,1},//1
{1,0,0,1,0,0,0,1,0,1},//2
{1,0,0,0,0,1,1,0,0,1},//3
{1,0,1,1,1,0,0,0,0,1},//4
{1,0,0,0,1,0,0,0,0,1},//5
{1,0,1,0,0,0,1,0,0,1},//6
{1,0,1,1,1,0,1,1,0,1},//7
{1,1,0,0,0,0,0,0,0,1},//8
{1,1,1,1,1,1,1,1,1,1}};/*9
0 1 2 3 4 5 6 7 8 9*/
(2) 迷宫数据组织
a.存储迷宫的二维数组 0对应图中白方块,表示通道
1对应图中黑方块,表示墙壁
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
47
(2) 迷宫数据组织
typedef struct
{
int i;//方块的行号
int j;//方块的列号
int di;//相邻方块的方向号
} st[MaxSize];//定义顺序栈
int top=-1;//st的栈顶“指针”
b.算法使用的顺序栈存储结构 i j di
0
1
7
2
3
4
5
6
11
8
9
10
top
顺序栈 st
top++;
st[top].i=1;
st[top].j=2;
st[top].di=3 -1 栈底
1 2 3
方块进栈过程演示,
48
(3) 设计运算算法思路,采用“穷举求解”方法,即从入口开始,先沿某一方向前行试探,若能走通,则继续往前行 ;否则沿原路退回 (称为回溯 ),再换另一方向试探,直至所有的通路都试探完为止。
49
0
1
0 1 2 3 4 5
( i,j )
( i-1,j )
( i,j +1)
( i,j -1)
( i+1,j )
上 (方向 0)
右 (方向 1)
下 (方向 2)
左 ( 方向 3)
a.方块 (i,j)的 4个相邻方块方向编号的规定
2
3
4
5
入口出口
i=
j=
上,方向 0; 右,方向 1;
下,方向 2; 左,方向 3
50
( i,j )
( i-1,j )
( i,j +1)
( i,j -1)
( i+1,j )
上 (方向 0)
右 (方向 1)
下 (方向 2)
左 ( 方向 3)
b.从方块 (i,j)向 4个相邻方块试探的先后次序首先试探方向 0,若走不通试探方向 1,若仍走不通试探方向 2,若还是走不通试探方向 3
51
1,3
2,2 2,3 2,4
3,3
方块 (1,3)是方块 (2,3)在方位 0上的可走相邻方块方块 (2,4)是方块 (2,3)在方位 1上的可走相邻方块方块 (3,3)是方块 (2,3)在方位 2上的不可走相邻方块方块 (2,2)是方块 (2,3)
在方位 3上的不可走相邻方块
c.可走相邻方块与不可走相邻方块的定义方向 0
方向 1
方向 2
方向 3
52
i j di
0
1
0 1 2 3 4 5
2
3
4
5
入口出口
0
top
1
7
2
3
4
5
6
11
8
9
10
1 1 -1
1 2 -1
1 3 -12
2 3 -1
2 4 -1
2
3 3 2
4 3 -1
4 4 -1
到达出口
(1,1) (1,2) k(1,3) (2,3) (3,3) (4,3) (4,4)
用顺序栈 st求解迷宫路径的过程演示
j
i 输出迷宫路径入口方块 (xi=1,yi=1)出口方块 (xe=4,ye=4)
-1
53
用顺序栈 st求解迷宫路径过程 (算法描述 )
入口方块进栈,并设其 di为 -1,为避免重走该方块使 mg(xi,yi)=-1
while(st不为空 )
{ 以栈顶方块 (即 i=st[top].i;j=[st[top].j)为当前方块 ;
if (当前方块是出口方块 (M-2,N-2) )
输出迷宫路径,结束 ;
else
{ 以当前方块为起点,在没有试探过的方位上寻找可走相邻方块 ;
if(在某一方向上找到一个可走相邻方块 (即 mg[i,j]=0的方块 )
{ 用该方向号修改当前栈顶的 di;
将找到的可走相邻方块进栈,并设其 di为 -1;
为避免重走至该方块,设其 mg[i,j]为 -1;
}
else {当前方块无可走相邻方块,将其从栈中删除,并设其为其他路径可走方块 (即 mg[st[top].i][st[top].j]=0); }
}
无可走路径,结束。
54
int mgpath(int xi,int yi,int xe,int ye)
{
int i,j,k,di,find;
top++; //入口方块进栈
st[top].i=xi;st[top].j=yi;
st[top].di=-1;
mg[xi][yi]=-1; //避免重走用顺序栈 st求解迷宫路径算法,
Part A 入口方块进栈
55
while(top>-1)//只要栈不为空
{
i=st[top].i; j=st[top].j; di=st[top].di;//取 栈顶方块为当前方块
if(i==xe && j==ye)//若 当前方块是 出口 方块
{
printf(“迷宫路路径如下,\n” );//输出迷宫路径
for(k=0;k<=top;k++)//从栈底至栈顶
{
printf("\t(%d,%d)",st[k].i,st[k].j);
if((k+1)%5==0) //每行输出 5个方块
printf("\n");
}
printf("\n");
return(1);//结束并返回找到一条迷宫路径标志
}
用顺序栈 st求解迷宫路径算法,
Part B 输出迷宫路径
56
find=0;
while(di<4 && find==0)//在没有试探过的方向寻找可走相邻方块
{
di++;//方向 号增 1
switch(di)//取相应方向上的相邻方块元素的二维坐标
{
case 0:i=st[top].i-1;j=st[top].j;break;
case 1:i=st[top].i;j=st[top].j+1;break;
case 2:i=st[top].i+1;j=st[top].j;break;
case 3:i=st[top].i;j=st[top].j-1;break;
}
if(mg[i][j]==0) find=1;//判断是否是 可走相邻方块
}
用顺序栈 st求解迷宫路径算法,
Part C 在没有试探过的方位上寻找当前方块的下一个可走相邻方块
57
if(find==1)//若 找到 当前方块的下一 个可走 相邻 方块
{
st[top].di=di;//修改栈顶元素的方向号
top++;//下一个可 走 相邻 方块进栈
st[top].i=i;st[top].j=j;st[top].di=-1;
mg[i][j]=-1;//为避免重走该方块,将其置为 -1
}
else//当前方块无可走的相邻 方块
{
mg[st[top].i][st[top].j]=0;//让该方块变为其它路径的可走方块
top--;//将该方从栈中删除
}
}
return(0);//无路可走,返回 0;
}
用顺序栈 st求解迷宫路径算法,Part D
58
#include "stdafx.h"
#include <stdlib.h>
#include <iostream.h>
#define MaxSize 100
struct
{
int i;//迷宫方块行号
int j;//迷宫方块列号
int di;//相邻方块方向号
} st[MaxSize];//定义顺序栈
int top=-1;//初始化为空栈设计求解程序 Part A 定义顺序栈 (全局 )
59
int mg[10][10]={
{1,1,1,1,1,1,1,1,1,1},//0
{1,0,0,1,0,0,0,1,0,1},//1
{1,0,0,1,0,0,0,1,0,1},//2
{1,0,0,0,0,1,1,0,0,1},//3
{1,0,1,1,1,0,0,0,0,1},//4
{1,0,0,0,1,0,0,0,0,1},//5
{1,0,1,0,0,0,1,0,0,1},//6
{1,0,1,1,1,0,1,1,0,1},//7
{1,1,0,0,0,0,0,0,0,1},//8
{1,1,1,1,1,1,1,1,1,1}}; /*9
0 1 2 3 4 5 6 7 8 9*/
设计求解程序 Part B 定义迷宫数组 (全局 )
60
int main(int argc,char* argv[])
{
int xi=1,yi=1,xe=8,ye=8;
if(mgpath(xi,yi,xe,ye)==0)
cout<<"无路可走 "<<endl;
return 0;
}
设计求解程序 建立以下主函数调用上述算法
61
迷宫路径如下,
(1,1) (1,2) (2,2) (3,2) (3,1)
(4,1) (5,1) (5,2) (5,3) (6,3)
(6,4) (6,5) (5,5) (4,5) (4,6)
(4,7) (3,7) (3,8) (4,8) (5,8)
(6,8) (7,8) (8,8)
Press any key to continue
运行结果,
请同学们思考,如何修改本算法,使其能输出迷宫中所有的可行路径?
62
3.2 队列
3.2.1 队列的定义队列 (queue)是限定仅在一端插入，另一端删除的线性表。允许插入的一端叫队尾 (rear),允许删除的一端叫对头 (front).
不含元素的空表称为 空队列队列的运算特性是 先进先出
（ First In First Out— FIFO)
1
2
3
4
front
rear一、定义
63
3.2 队列二、队列的基本运算
InitQueue(&q); //初始化队列：构造一个空队列 q
ClearQueue(&q); //销毁队列：释放队列 q占用的存储空间。
QueueEmpty(q); //判断队列是否空：若队列为空，则返回真；否则返回假。
EnQueue(&q,e); //入队操作：将元素 e入队作为队尾元素。
DeQueue(&q,&e); //出队操作：从队列 q中出队一个元素，并将其赋给 e。
Push(s,e)
Pop(s,e)
64
3.2 队列对队列的操作：
实际模型
1 2
65
3.2 队列
3.2.2 队列的顺序存储结构及其基本运算的实现
1,一般顺序存储结构结构定义：
typedef struct
{ElemType data[MaxSize];
int front,rear;
} SeQueue;
用数组顺序存放存储队列中的所有元素，利用两个整型变量分别存储队首和队尾元素的下标位置，
分别称它们为队首和队尾指针。 并约定,头指针
sq.front总是指向队头元素的前一个位置；尾指针
sq.rear指向队尾元素。
队列变量定义：
SeQueue *q,sq;
66
3.2 队列线性模型
-1 0 1 2 3 4 5 6
a1
enQueue(q,a1)
a2 a3 a4 a5 a6 a7
enQueue(q,a2) enQueue(q,a3)
deQueue(q,a1) enQueue(q,a4) enQueue(q,a5)
deQueue(q,a2) enQueue(q,a6) enQueue(q,a7)
enQueue(&q,a8)
出现“假溢出”，那么该如何解决？
67
3.2 队列
2,循环队列
enQueue(q,a1)
enQueue(q,a2)
enQueue(q,a3)
deQueue(q,a1)
enQueue(q,a4)
enQueue(q,a5)
deQueue(q,a2)
enQueue(q,a6)
enQueue(q,a7)
enQueue(q,a8)
1
2 3
4
5
6
0
a1
a2 a3
a4
a5a6
a7
a8
i=(i+1)%MaxSixe
入队,rear++，再将数据入队出队：先将数据出队,front++
68
3.2 队列
2,循环队列
1
2 3
4
5
6
0
如何判队列是空队列还是满队列呢？
队空条件为,q->rear= =q->front
队满条件为,(q->rear+1)%MaxSize= =q->front
出入队操作指针如何变化？
解决方法,少用一个单元，令 sq.front指向的单元总为空,
69
3.2 队列
3,循环队列的基本运算入队列 enQueue(q,e)
算法思想,在队列不满的条件下,先将 队尾指针 rear
循环增 1,然后将元素添加到该位置 。 对应算法如下,
int enQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+1)%MaxSize==q->front) /*队满 */
return 0;
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return 1;
}
70
3.2 队列循环队列的入队操作
a2入队：
sq.rear=(sq.rear+1)%MaxSize;
1
2 3
4
5
6
0
a1
ai-1 …
a2
ai
Sq.elem[sq.rear]=ai;
ai入队：
1
2 3
4
56
0
a1
a2
sq.rear++;
sq.data[sq.rear]=a2；
if(sq.rear+1>=maxsize)
sq.rear=0;
sq.data[sq.rear]=ai
71
3.2 队列
3,循环队列的基本运算出队列 deQueue(q,e)
算法思想,在队列 q不为空的条件下,将 队首指针 front
循环增 1,并将该位置的元素值赋给 e。对应算法如下,
int deQueue(SqQueue *&q,ElemType &e)
{
if (q->front==q->rear) /*队空 */
return 0;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return 1;
}
72
3.2 队列循环队列的出队操作
a1出队：
1
2 3
4
5
6
0 a
1
…
a2
ai
a1出队：
1
2 3
4
56
0
a1 a2
Sq.front++;
a3
if(sq.front+1>=maxsize)
sq.front=0;
sq.front=(sq.front+1)%maxsize
73
3.2 队列一、链队数据类型定义 (使用两种类型的结点 )
1、链队数据结点类型定义 (用于存储链队数据 )
typedef struct quode
{ ElemType data;//数据结点的数据域
struct quode *next;//数据结点的指针域
} QNode;
2、链队首、尾指针结点 (简称链队结点 )类型定义
typedef struct
{ QNode *front;//队首指针
QNode *rear;//队尾指针
} LiQueue;
front
rear
data next
数据结点链队结点队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。其类型定义如下：
3.2.3 队列的链式存储结构及其基本运算的实现区分指针 q和指针 front/rear
74
3.2 队列二、链队的基本运算算法
void InitQueue(LiQueue *&q)
{ q=(LiQueue *)malloc(sizeof(LiQueue));
q->front=q->rear=NULL;//初始化队列首与尾指针
}
设主函数中调用的语句为：
LiQueue q;
InitQueue(q); q
front
rear
∧
∧
该算法仅生成了一个包含队首指针和队尾指针域均为空的结点,可视为一个空队列。
1、初始化队列 InitQueue(q):构造一个空队列。
75
3.2 队列
4,入队列 enQueue(q,e):创建一个数据结点,若实参传送的队列为空,将队首、队尾指针均指向该数据结点，否则将该数据结点链接到队尾,并将队尾指针指向该结点。
76
3.2 队列4、入队列过程演示
void enQueue(LiQueue *&q,ElemType e)
{ QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=e;
s->next=NULL;
if(q->rear==NULL)//若链队列为空 (无数据结点 )
q->front=q->rear=s;
else
{ q->rear->next=s;//在队尾插入新结点
q->rear=s;//尾指针指向新结点
}
}
q
front
rear
∧
∧
— (1)若实参传送的是一空队列 q
e=‘a’‘
data next
s ‘a’ ∧
入队结束
77
3.2 队列4、入队列过程演示
void enQueue(LiQueue *&q,ElemType e)
{ QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=e;
s->next=NULL;
if(q->rear==NULL)//若链队列为空 (无数据结点 )
q->front=q->rear=s;
else
{ q->rear->next=s;//在队尾插入新结点
q->rear=s;//尾指针指向新结点
}
}
q
front
rear
— (2)若实参传送的是非空队列 q
e=‘b’‘
s‘a’ ∧
入队结束
‘b’ ∧
78
3.2 队列
5、出队列 deQueue(q,e),将队列的第一个数据结点删除
int deQueue(LiQueue *&q,ElemType &e)
{ QNode *t;
if(q->rear==NULL)//队列为空
return 0;
t=q->front;//t指向要删除的第一个数据结点
if(q->front==q->rear)//若队中仅有一个数据结点
q->front=q->rear=NULL;//将首,尾指针设为空
else
q->front=q->front->next;//将原首结点后继
//设为首结点
e=t->data;
free(t);//释放被删除结点的存储空间
return 1;//返回出队成功标志
}
79
3.2 队列
3.2.4 队列的应用举例求解报数问题设有 n个人站成一排，从左向右的编号分别为 1～ n，现在从左往右报数,1,2,1,2…”,
数到 1的人出列，数到 2的人站到队列的最右端。
报数过程反复进行，直到所有的人全部出列为止。求出他们的出列顺序。
1 2 3 4 5 6 7 8
80
3.2 队列编程思想,将 n个人按编号入队，然后反复执行如下操作，直到队列为空。
（ 1）出队一个元素，输出其编号
（ 2）若队列不空，再出队一个元素，并将其重新入队。
81
2.解迷宫问题
(1)问题的描述
(2)数据组织使用一个顺序队列 Qu记录走过的方块,顺序队列的结构如下,
struct
{ int i,j; //方块的位置
int pre; //本路径中上一方块在 Qu中的下标
} Qu[MaxSize];
int front=-1,rear=-1; //队首指针和队尾指针
3.2.4 队列的应用举例
82
顺序队列 Qu的存储结构
#define MaxSize 9
struct
{
int i,j;//方块位置
int pre;//上一方块在队
//列中的一维下标
} Qu[MaxSize];
int front=-1;//队首“指针”
rear=-1;//队尾“指针”
顺序队列 Qu的定义
i j pre
7
5
6
3
4
2
1
0
MaxSize-1
fr
rear++;//入队 1次
Qu[rear].i=1;
Qu[rear].j=1;
Qu[rear].pre=-1;
1 1 -1
Qu[rear].i=1;
Qu[rear].j=2;
Qu[rear].pre=0;
rear++;//入队 1次
1 2 0
front++;//出队 1次执行语句-1
0
1
0 1 2
2
入口 如何在队列 Qu中记录从方块 (1,1)
走到方块 (1,2)的过程呢？
说明,
队列 Qu记录搜索迷宫所走过的方块,所以,出队时并不将出队元素从队中删除 ;
83
迷宫与迷宫数组 mg
int mg[6][6]={
/* 0 1 2 3 4 5 */
/*0*/ {1,1,1,1,1,1},
/*1*/ {1,0,0,0,1,1},
/*2*/ {1,0,1,0,0,1},
/*3*/ {1,0,0,0,1,1},
/*4*/ {1,1,1,0,0,1},
/*5*/ {1,1,1,1,1,1}};
入口方块位置,xi=1,yi=1
出口方块位置,xe=4,ye=4
0
1
0 1 2 3 4 5
2
3
4
5
出口入口
i
j
84
( i-1,j )
( i,j +1)( i,j -1)
( i+1,j )
上 (方向 0)
右 (方向 1)
下 (方向 2)
左 ( 方向 3)
方块 (i,j)的 4个相邻方块方向编号的规定
( i,j )
85
0
1
0 1 2 3 4 5 i j pre
13
17
7
12
5
6
3
4
14
2
1
0
2
3
4
5
出口入口
9
10
16
11
15
8
i j prefr
1 1 -1
0
0
1
2
3
4
5
5
(1,1) (1,2) (1,3) (2,3)
(3,3) (4,3) (4,4)
搜索迷宫路径的过程 队列 Qu的数据变化过程
i
j
1 2
2 1
1 3
3 1
2 3
3 2
2 4
8
9
3 3
4 3
4 4 -1
-1
-1
-1
-
-1
(3)设计运算算法
86
(1,1)
(1,2)
(1,1)
用队列对迷宫路径的搜索方法
(2,1)
(1,3) (3,1)
(2,3) (3,2)
(2,4) (3,3)
(4,3)
(4,4)
×
(1,2) (1,3) (2,3)
(3,3) (4,3) (4,4)
这样的搜索方法称为广度优先搜索方法,所求路径为最短路径。
0
1
0 1 2 3 4 5
2
3
4
5
出口入口
i
走出迷宫的一条路径入口方块出口方块
87
用队列对迷宫路径的搜索方法
//int xi=1,yi=1,xe=8,ye=8;
int mg[10][10]={
{1,1,1,1,1,1,1,1,1,1},//0
{1,0,0,1,1,1,0,0,0,1},//1
{1,0,0,1,1,1,0,1,0,1},//2
{1,0,0,0,0,1,0,1,0,1},//3
{1,0,1,1,0,1,0,1,0,1},//4
{1,0,1,1,0,0,0,1,0,1},//5
{1,0,1,1,1,1,1,0,0,1},//6
{1,0,1,1,1,0,1,1,0,1},//7
{1,0,0,0,0,0,0,0,0,1},//8
{1,1,1,1,1,1,1,1,1,1}};/*9
0 1 2 3 4 5 6 7 8 9*/
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
88
用队列对迷宫路径的搜索方法
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9
第 1条路径 (最短 15个方块 )
(1,1) (2,1) (3,1) (4,1) (5,1)
(6,1) (7,1) (8,1) (8,2) (8,3)
(8,4) (8,5) (8,6) (8,7) (8,8)
第 2条路径 (23个方块 )
(1,1) (1,2) (2,2) (3,2) (3,3)
(3,4) (4,4) (5,4) (5,5) (5,6)
(4,6) (3,6) (2,6) (1,6) (1,7)
(1,8) (2,8) (3,8) (4,8) (5,8)
(6,8) (7,8) (8,8)
89
A.用队列求解迷宫路径的算法描述
mgpath(xi,yi,xe,ye)
将入口方块 (xi,yi)入队,并设其 mg[xi,yi]=-1 及域 pre=-1,
出队一次 (即 front++)_;
while(队列不为空且未找到一条走出迷宫的路径 )
{ 以队首方块作为当前方块 ;
if(当前方块是出口方块 )
{ 置找到迷宫路径标志为 1; 输出走出迷宫的路径 ;退出 ;}
else
{ 以当前方块为起点,分别按方向 0至方向 3的顺序搜索当前方块的所有的相邻方块
if(是可走方块 )
{该方块的坐标入队 ;
该方块的起始方块在队列中的下标入队 ;
将该方块对应的迷宫数组元素值置为 -1,以避免重走 ;
}
}
出队一次
}
90
B.输出迷宫路径的算法描述 print(front)
a.给一条迷宫路径的所有方块设置标识符 -1
k=队尾元素的下标 ;
Do
{ j=k;//保存 k值
k=Qu[k].pre;//获取本方块的上一方块在队列中的下标
Qu[j].pre=-1;//设置标识符 -1
} While(k!=0}
b.输出迷宫路径
k=0;
while(k<MaxSize)
{
if(Qu[k].pre==-1)
按每行 5个元素格式输出 Qu[k].i与 Qu[k].j;
k++;
}
91
(4)迷宫路径搜索算法
int mgpath(int xi,int yi,int xe,int ye)
{ int i,j,find=0,di;
rear++; Qu[rear].i=xi;Qu[rear].j=yi; //队首方块入队
Qu[rear].pre=-1; mg[xi][yi]=-1;
while(front<rear && !find)//
{
front++；
i=Qu[front].i; j=Qu[front].j;//以队首方块为当前方块
if((i==xe)&&(j==ye))//若当前方块为出口方块
{ find=1;//找到一条迷宫路径标志
print(front);//调用输出迷宫路径函数
return (1);//找到一条路径时返回 1
}
92
for(di=0;di<=3;di++)
{ switch(di)
{ case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break; }
if(mg[i][j]==0)//找到下一个可走相邻方块
{ rear++;//尾指针前移,准备入队操作
Qu[rear].i=i;Qu[rear].j=j;//可走相邻方块入队
Qu[rear].pre=front;//当前方块的下标入队
mg[i][j]=-1;//避免再重复搜索此方块 }
}
}
return (0);//未找到一条路径时返回 0(课本此处注释错 )
}
93
void print(int front)
{
int k=front,j,ns=0;//k指向队尾
printf("\n");
do //从队尾回推到队首,将路径中的所有方块的 pre置
//为 -1
{
j=k;
k=Qu[k].pre;//保存本方块的上层方块下标
Qu[j].pre=-1;//该方块的 pre域置为 -1
}while(k!=0);//一直遇到队首 (k=0)为止
(5)输出迷宫路径算法
94
printf("用队列求解迷宫的路径如下,\n");
k=0;
while(k<MaxSize)
{
if(Qu[k].pre==-1)//只输出队列中 pre=-1的存储单元
{ ns++;
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(ns%5==0) printf("\n");//按每行 5个元素格式输出
}
k++;
}
printf("\n");
}
95
int main(int argc,char* argv[])
{
int xi=1,yi=1;//入口方块坐标
int xe=8,ye=8;//出口方块坐标
if(mgpath(xi,yi,xe,ye)==0)//调用队列求解迷宫函数
cout<<"迷宫无可走路径 !"<<endl;
return 0;
}
(6)主函数中的相关语句说明,
(1)迷宫数组定义为全局变量 (在主函数之前定义 )
(2)顺序队列 Qu也定义为全局变量 (在主函数之前定义 )
96
本章小结本章基本学习要点如下,
(1)理解栈和队列的特性以及它们与线性表之间的差异,能根据具体情况选用合适的数据结构及物理存储结构 。
线性表、栈、队列的异同点
相同点,逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即操作受限的线性表 (只是对插入、
删除运算加以限制 )。
97
小 结：
线性表、栈、队列的异同点
不同点,
① 运算规则不同,
线性表的插入、删除等基本操作可针对表中的任意位置的数据元素；
而栈是只允许在一端（栈顶）进行插入和删除运算，因而是后进先出表 LIFO；
队列是只允许在队尾进行插入、队头进行删除运算，因而是先进先出表 FIFO。
② 用途不同,线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟,OS作业调度和简化设计等。
98
(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意顺序栈满和栈空的条件 。
(3)重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件 。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题 。
小 结：
99
上机题 3.5使用的迷宫
int mg2[6][6]={
{1,1,1,1,1,1},//0
{1,0,0,0,1,1},//1
{1,0,1,0,0,1},//2
{1,0,0,0,1,1},//3
{1,1,0,0,0,1},//4
{1,1,1,1,1,1}}; //5
/*0 1 2 3 4 5 */
0
1
0 1 2 3 4 5
2
3
4
5
j
i
10
0
第 4条路径的方块数为,7
(1,1) (2,1) (3,1) (3,2) (4,2) (4,3)
(4,4)
0
1
0 1 2 3 4 5
2
3
4
5
j
i
第 1条路径的方块数为,7
(1,1) (1,2) (1,3) (2,3) (3,3)
(4,3) (4,4)
第 2条路径的方块数为,9
(1,1) (1,2) (1,3) (2,3) (3,3)
(3,2) (4,2) (4,3) (4,4)
第 3条路径的方块数为,7
(1,1) (2,1) (3,1) (3,2) (3,3)
(4,3) (4,4)
