内容提要
? 4.1 栈
? 顺序栈
? 链式栈
? 栈的应用
? 4.2 栈和递归的实现
? 基本概念
? 基本问题
? 4.3 队列
? 顺序队列
? 链式队列
? 队列的应用
? 4.4 栈和队列的应用范例
4.1 栈
1、定义
栈 (Stack)：一种后进先出 (LIFO)的线性表。
栈顶 (top)：允许插入和删除的一端
栈底 (bottom)：不允许插入和删除的一端
栈的主要操作,
建立空栈 进栈
出栈 判断栈是否空
判断栈是否满 获取栈顶元素值
向栈中插入和删 除元素，必须在栈的一
端进行。因此，栈是操作受限的！
栈 (cont’d)
a1
a2
…
an
进栈出栈
栈顶
栈的示意图
栈的修改是按 后进先出
(Last In First Out，简称
LIFO)的原则进行的。
栈 之 顺序栈
2、顺序栈, 用顺序表实现的栈
(1) 顺序栈的数据类型定义,
#define MAXSIZE 50
typedef struct
{
elemtype elem[MAXSIZE];
int top; /*栈顶 */
}SQSTACK;
栈 之 顺序栈 (cont’d)
(2) 顺序栈的基本操作 (建栈 )：
void initstack(SQSTACK *s)
{
s?top= -1; /*-1表示空栈 */
}
? 建立空栈
栈 之 顺序栈 (cont’d)
(3) 顺序栈的基本操作 (判断 )：
int stackempty(SQSTACK s)
{
return s.top == -1;
}
? 判断栈是否空
栈 之 顺序栈 (cont’d)
(4) 顺序栈的基本操作 (入栈 )：
int push(SQSTACK *s,
elemtype e)
{
if(s?top==MAXSIZE-1)
return 0; /*栈满,入栈失败 */
s?top++;
s?elem[s?top]=e;
return 1;
}
? 入栈
栈 之 顺序栈 (cont’d)
(5) 顺序栈的基本操作 (出栈 )：
int pop(SQSTACK *s,elemtype
*e)
{
if(s?top==-1)
return 0; /*栈空,出栈失败 */
*e=s?elem[s?top];
s?top--;
return 1;
}
? 出栈
栈 之 顺序栈 (cont’d)
(6) 顺序栈的基本操作 (获取 )：
int gettop(SQSTACK
s,elemtype *e)
{
if(s?top==-1)return 0;
*e=s?elem[s?top];
}
? 获取栈顶值
栈 之 链式栈
3、链式栈, 用链表实现的栈
(1) 链式栈的数据类型定义（与链表相同）,
typedef struct node
{
elemtype data;
struct node *next;
}NODE,*NODEPTR,*LKSTACK;
#define LEN sizeof(NODE)
栈 之 链式栈 (cont’d)
3、链式栈, 用链表实现的栈
(2) 链式栈的基本操作 (建栈 )：
LKSTACK top;
top=NULL;
? 建立空栈
栈 之 链式栈 (cont’d)
3、链式栈, 用链表实现的栈
(3) 链式栈的基本操作 (入栈 )：
int push(LKSTACK *top,
elemtype e)
{ NODEPTR p;
p=(NODEPTR)malloc(LEN);
if(p==NULL) return 0;
p?data=e;
p?next=*top;
*top=p;
}
? 入栈
栈 之 链式栈 (cont’d)
3、链式栈, 用链表实现的栈
(4) 链式栈的基本操作 (出栈 )：
int pop(LKSTACK *top,
elemtype *e)
{ NODEPTR p;
if(*top==NULL) return 0;
*e=(*top)?data;
p=*top;
*top=(*top)?next;
free(p);
}
? 出栈
栈 之 栈的应用
4、栈的应用范例 (函数调用 )
(1) 函数的调用和返回
系统调用函数时，为了能
够正确返回，必须将返回地
址先入栈，此外，非静态的
局部变量也占用栈的空间，
当函数返回时，这些数据将
出栈。这也就是局部变量生
存期短的原因。
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (表达式 )
(2) 算术表达式求值 (算符优先法 )
基本知识：
?表达式由运算符、操作数和界限符构成，它们
被称为“单词”
?操作数可以是常量或者变量
?运算符区分左右结合性，同优先级运算符连用
时的优先顺序受结合性约束
?界限符包括圆括号和算式结束符
运算符栈 操作数栈
【 例 】 计算,2＋ 3*2^2^2*5-2;
2(
+ 3
* 2
^ 2
^ 2
2^2=4
4
2^4=16
16
3*16=48
48
5
48*5=240240
240＋ 2＝ 242242
－ 2
242－ 2＝ 240
240
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (表达式 )
(2) 算术表达式求值 (算符优先法 )
表达式求值操作规则, 从左向右扫描表达式串，每次去一个单
词，
?如果单词是操作数，一律入操作数栈
?如果单词是运算符 (称为外运算符 )，则比较该外运算符与运
算符栈栈顶运算符的优先级。
? 如果外运算符优先级高或相同，则将该运算符入栈；
?否则将栈顶运算符出栈并出栈操作数计算结果入操作数栈。
注意：运算符栈一开始有个运算符 (，它的优先级最低。
?表达式终结符－－分号的优先级最低，比栈内任何实际运算
符都低。
?当栈顶运算符与外运算符是不同运算符时，按照预先定义的
优先级处理，如果是相同的运算符，右结合性的运算符，外运
算符优先级高。
?为了能对圆括号作统一处理，特别规定左括号在栈内优先级
最低，在栈外优先级最高。
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (表达式 )
(2) 算术表达式求值 (算符优先法 )
为了方便栈内外运算符优先级比较，可以事先规
定运算符的栈内外的优先级数。可以根据下面的表格，
编写函数获取运算符的优先级数：
优先级函数
运算符 x 栈内
isp( x)
栈外
ielp( x)
^ 单目运算符 3 4
* / 2 2
+ - 1 1
( 0 4
float evaluate(char exp[])
{ /*实现开辟操作数栈 s1和运算符栈 s2，并将 (入到 s2
中； exp是输入表达式串 */
while(1)
{从 exp中取出一个单词 x
switch(x)
{ case x是操作数,push(&s1,x);break;
case x是 ')':
反复出栈处理,直到遇到 (为止,break;
case x是 ';':反复出栈处理，直到栈只剩下 (为止；
return操作数栈顶值 ;
case x是其它运算符,
while(ielp(x)<=isp(s2.elem[s2.top--])){出栈处理 }
push(&s2,x);break; }//switch
}//while
}
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (算符 )
(3) 算符优先法求值算法
将程序补充
完整！
练习：
1、设有一个栈,元素进栈的次序,A,B,C,D,E。
试问能否得到出栈序列：
（ 1） C,E,A,B,D；（ 2） C,B,A,D,E；
（ 3） D,C,A,B,E；（ 4） A,C,B,E,D；
（ 5） A,B,C,D,E；（ 6） E,A,B,C,D。
2、按照运算符优先数法，画出对下列算术表达式求值
时运算符栈和操作数栈的变化过程：
A + B^C*E – D/F*G;
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (算符 )
(3) 算符优先法求值算法
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (非递归算法 )
(4) 实现递归问题的非递归算法
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
??
??
?
0,0)),1,,(,1(
0,42
0,31
0,20
0,1
01
),,(
ynxyxnAnA
yn
yn
yn
ynx
nx
yxnA
递归算法：
int Ackerman(int n,int x,int y)
{ if(n==0) return x+1;
else if(y==0)
{if(n==1) return x;
else if(n==2) return 0;
else if(n==3) return 1;
else return 2; }
else
return Ackerman(n-1,Ackerman(n,x,y-1),x);
}
基本思想：
1)如果 (n,x,y)是递归终点,则直接返回具体值 ;
2)如果 (n,x,y)不是递归终点,那么形成新的参
数 (n-1,A(n,x,y-1),x)。但必须先求 A(n,x,y-1),
的值，因此需要将 [n,x]入栈。这个过程称为
一次递归。
3)整个算法就是无限循环，反复执行递归和
返回操作，直到栈空时，结束算法。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
??
??
?
0,0)),1,,(,1(
0,42
0,31
0,20
0,1
01
),,(
ynxyxnAnA
yn
yn
yn
ynx
nx
yxnA
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (非递归算法 )
Ackerman非递归算法
栈 之 栈的应用 (cont’d)
4,栈的应用范例 (递归算法 )
Ackerman非递归算法
A(3,1,2)的计算实例,
当前计算
A(3,1,2)= A(2,A(3,1,1),1)
A(3,1,2)
2 1
3,1,1
2,A 2,A(3,1,0),1),1)
A(3,1,0)=1
2 1
2,1,1)
(2,1,1)
1,2,1,
1
A(2,1,0)=0
1,0,1)
1,0,1)
0,1,0,,0)
0 0
1,0,0)=0
0,0,0)
0,0,0)
2,1,1)
2,1,1)
1,2,1,0)
1
2,1,0)
1,0,1)
1,0,1
0,1,0,0),0)
0 0
1,0,0)
0,0,0)
=1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
??
??
?
0,0)),1,,(,1(
0,42
0,31
0,20
0,1
01
),,(
ynxyxnAnA
yn
yn
yn
ynx
nx
yxnA
? 递归函数：一个直接调用自己或通过一系列
的调用语句间接地调用自己的函数。
? 递归是程序设计中一个强有力的工具。
? 特征：
? 有很多数学函数是递归定义的；
? 有的数据结构本身固有的递归特征，因
此它的操作可递归地描述；
?还有一类问题，虽则问题本身没有明显的
递归结构，但用递归求解比迭代求解更简
单。
4.2 栈和递归实现
1、基本概念和特征
算法思想：
1)递归,只要 n!=0&&y!=0,则反复执行：
y--;准备计算下一个 A(n,x,y)
将返回信息 (n-1,x)入栈
2)返回：如果 (n,x,y)是递归终点，得到一个终
点值 v。如果栈空，算法结束。否则弹出栈顶，
构成新的参数 (n-1,v,x)再次进入递归。
栈和递归实现 (cont’d)
2、应用范例 —— 数学函数递归
? Ackerman非递归算法
int Akmval(int n,int x,int y)
{ /*递归出口的求值函数 */
if(n==0) return x+1;
else switch(n)
{ case 1,return x;
case 2,return 0;
case 3,return 1;
default,return 2;
} //switch
}
/*下面定义入栈的返回信息的数据类型 */
typedef struct
{
int n; int x;
}elemtype;
栈和递归实现 (cont’d)
2、栈应用范例 —— 数学函数递归
ckerman(int n,int x,int y)
SQSTACK s; elemtype e,int v;
initstack(&s);
while(1)
{while(n!=0&&y!=0) /*进入递归 */
{e.n=n-1;e.x=x;push(&s,e); /*返回信息入栈 */
y--; /*准备计算 A(n,x,y-1)*/
}
v=Akmval(n,x,y); /*遇到递归终点 */
if(stackempty(s))return v;
else {pop(&s,&e);
n=e.n;y=e.x;x=v; /*形成新的参数 (n-1,v,x)*/
}
}//while
}
?Ackerman非递归算法
typedef struct { int n,x,y; }elemtype;
int Ackerman(int n,int x,int y)
{SQSTACK s; elemtype e; int v;
initstack(&s);
e.n=n; e.x=x; e.y=y;push(&s,e); /*初始参数入栈 */
while(!stackempty(s))
{gettop(s,&e);n=e.n;x=e.x;y=e.y; /*获取栈顶参数 */
while(n!=0&&y!=0) /*一直递归到终点 */
{y--;e.n=n;e.x=x;e.y=y;
push(&s,e); /*继续入栈下一组参数 */ }
v=Akmvalue(n,x,y);pop(&s,&e); /*终点参数出栈 */
if(stackempty(s)) return v;
else {pop(&s,&e);e.n--;e.y=e.x;e.x=v;
push(&s,e); /*替换成新的栈顶参数 */ }
}//while
}
栈和递归实现 (cont’d)
2、栈的应用范例 —— 数学函数递归
?Ackerman非递归算法 (另 )
入栈信息不同，
算法也会炯异
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
? 实现递归问题的非递归算法
递归问题之二
走迷宫：迷宫有一个入
口和一个出口，从入口到
出口可能有多条通路，但
每次只能走一步，可以有 8
个方向可以走。
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
? 走迷宫的非递归算法
O
O
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9人口
出口
求迷宫中从人口到出口的所有
路径是一个经典的程序设计问
题。由于解迷宫时，通常用的
是“穷举求解”的方法，即从
人口出发，顺着某一方向向前
探索，若能走通，则继续往前
走；否则沿原路退回，换一个
方向再继续探索，直至所有可
能的通路都探索到为止。
算法思想：
1)用二维数组 maze表示迷宫，数组单元是 0表
示可走，是 1表示不通。
2)将方向按顺时针编成号,1－ 8,1表示正北
3)利用两个一维数组表示位置的变化量：
int movex[]={0,-1,-1,0,1,1,1,0,-1};//行变化
int movey[]={0,0,1,1,1,0,-1,-1,-1}; //列变化
注意,movex[0],movey[0]为无效方向
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
4)从入口开始，向 8个方向探索可以走的下一
个位置，如果有可走的位置，则将当前位置
及其探索的方向入栈，下一个可走的位置作
为当前位置。如果 8个方向都不可走，弹出栈
顶位置信息，作为当前位置，继续探索。如
果下一个可走的位置是出口，则输出栈中的
信息，即是一条通路。
5)当前位置退回到栈顶位置时，原当前位置
应该清 0，这样才能保证探索出多条通路。
? 走迷宫的非递归算法
typedef struct {int x,y,v;}elemtype;
void go(int maze[N][M],int x,int y,int xx,int yy)
{ /*(x,y)是入口,(xx,yy)是出口,N,M是迷宫的行列数 */
int k,x1,y1,x2,y2,v,count=0;SQSTACK s;elemtype e;
initstack(&s);
ex.x=x;e.y=y;e.v=0;
push(&s,e);maze[x][y]=2; //入口入栈,作已走标记 2
while(!stackempty(s))
{ pop(&s,&e);
x1=e.x;y1=e.y; //弹出栈顶位置,作为当前位置
v=e.v+1; //开始下一个方向探索
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
while(v<=8) //开始沿着 8个方向继续探索
{x2=x1+ ovex[v];y2=y1+movey[v]; //计算新位置
if(x2==xx&&y2==yy) //找到出口，输出一条通路
{printf("path %d:",++count);
for(k=0;k<=s.top;k++)
printf("(%d,%d)?",s.elem[k].x,s.elem[k].y);
printf("(%d,%d)?",x1,y1);
printf("(%d,%d)\n",xx,yy);
//如果只需要一条通路，就在这里 return
}//if
if(e.v>0) //如果前面曾探索过通路,将探索过的位置清 0
maze[x1+movex[e.v]][y1+movey[e.v]]=0;
else if(!maze[x2][y ]) //新位置可走
{e.x=x1;e.y=y1;e.v=v;push(&s,e); //当前位置入栈
x1=x2;y1 y2;v=0; //新位置作为当前位置
}//else if
v++; //开始探索下一个有效方向
}//while (v<=8)
}//while
if(count==0) printf("no path\n");
}
? 走迷宫的非递归算法
栈和递归实现 (cont’d)
4、应用范例 —— 汉诺塔
? 实现递归问题的非递归算法
递归问题之三
汉诺塔, 存在 x,y,z三个柱子，
x的上面套有盘子，大盘子在下
面，小盘子在上面，先要求将
这些盘子从 x搬到 z上，这个过程
中，一次只能搬动一个盘子，
并且任何时候都必须保证大盘
子在下面小盘子在上面，可以
利用第三个柱子暂时放置盘子 。
X Y Z
图 3阶 Hanoi塔问题的初始状态
void hanoi(int n,char x,char y,char z)
{SQSTACK s;elemtype e;char t;
initstack(&s);
e.n=n;e.x=x;e.y=y;e.z=z;
push(&s,&e); //初始参数入栈
while(1)
{gettop(s,&e);
while(e.n>1)
{e.n--;t=e.y;e.y=e.z;e.z=t;
push(&s,e); //新参数入栈 }
pop(&s,&e); //栈顶状态可以直接搬动
move(e.x,1,e.z); //递归终点
if(satckempty(s))return; //栈空,算法终止
pop(&s,&e); //取出栈顶参数，这个栈顶
将被替换
move(e.x,e.n,e.z);
e.n--;t=e.x;e.x=e.y;e.y=t;
push(&s,&e); //新的参数入栈
}//while(1)
}
汉诺塔的非递归算法
void hanoi(int n,char x,char y char z)
{if (n==1) move(x,1,z);
else
{hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z); }
}
汉诺塔的递归算法
(1)、确定入栈的返回信息，这些返回信息在出栈
时可以帮助计算函数值或者新的返回信息
(2)、确定入栈的条件，即非递归终点的条件
(3)、确定出栈时对栈顶的操作，是替换成新的返
回信息还是直接出栈
(4)、确定算法终止的条件
5、递归问题的非递归算法编写技巧
栈和递归实现 (cont’d)
初始化栈,确保栈顶参数就
是当前待解决的问题
将栈顶问题分解成规模
更小的问题,新的参数入栈,
直到遇到递归终点
栈顶是递归终点,出栈后,
栈顶的参数不是递归终点,
利用栈顶参数生成新的问题
或者不断出栈
栈空,退出
栈和递归实现 (cont’d)
5、递归问题的非递归算法编写技巧
4.3 队列
1、定义
队列, 是一种先进先出 (FIFO)的线性表。
队尾,允许插入的一端
队首,允许删除的一端
队列的主要操作,
建立空队 进队 (入队 )
出队 判断队列是否满
判断队列是否空 获取队首元素的值
向队列中插入元素只允许在一端进行，
删除元素只允许在另一端进行
队列 (cont’d)
a1 a2 a3 … an
图 1 队列示意图
队
尾
队
头
出队列 入队列
(front) (rear)
队列 (cont’d)
2、顺序存储的队列：循环队列
(1) 循环队列的数据类型定义：
#define MAXSIZE 50
typedef struct
{
elemtype elem[MAXSIZE];
int front,rear;
int len;
}SQQUEUE;
队列 (cont’d)
(d)
5
4
3
2
1
0
(a)
Q.rear
Q.front
(b)
Q.rear
Q.front
(c)
Q.rear
Q.front
Q.rear
Q.front
J1
J2
J3 J3
J5
J6
图 2 头、尾指针和队列中元素之间的关系
(a)空队列； (b)J1,J2和 J3相继入队； (c)J1和 J2相继被删除；
(d)J4,J5和 J6相继插入队列后 J4被删除。
队列 (cont’d)
0
1
maxsize ?1
Q.front
Q.rear
...
...
队列
图 3 循环队列示意图
此时 Q.front = Q.rear无法判
别队列空间是“空”还是“
满”。
两种方法处理：
?另设一个标志位以区别队
列是“空”还是“满”；
?少用一个元素空间，约定
以“队列头指针在队尾指针
的下一位置上”作为队列呈
“满”状态的标志。
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (空队 )：
void initqueue(SQQUEUE *q)
{
q?front=q?rear=0;
q?len=0;
}
? 建立空队
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (队空 )：
int queueempty(SQQUEUE q)
{
return q.len==0;
}
? 判断队是否空
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (入队 )：
int inqueue(SQQUEUE *q,elemtype e)
{ if(q?len==MAXSIZE) return 0;
if(q?len==0)
{ q?front=q?rear=0;
q?elem[q?rear]=e; }
else
{q?rear=(q?rear+1)%MAXSIZE;
q?elem[q?rear]=e; }
q?len++;
return 1;
}
? 元素入队
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (出队 )：
int dequeue(SQQUEUE *q,elemtype *e)
{ if(q?len==0)return 0;
*e=q?elem[q?front];
q?front=(q?front+1)%MAXSIZE;
q?len=0;
return 1;
}
? 元素出队
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (队首 )：
int getfront(SQQUEUE q,elemtype *e)
{
if(q.len==0)return 0;
*e=q.elem[q.front];
return 1;
}
? 获取队首的值
队列 (cont’d)
3、链式存储的队列
(1) 链式队列的数据类型定义：
typedef struct node
{elemtype data;
struct node *next;
}NODE,*NODEPTR;
#define LEN sizeof(NODE)
typedef struct
{
NODEPTR front,rear;
}LINKQUEUE;
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (空队 )：
void initqueue(LINKQUEUE *q)
{
q?front=q?rear=NULL;
}
? 建立空队
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (队空 )：
int queueempty(LINKQUEUE q)
{
return q.front==NULL
}
? 判断队是否空
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (入队 )：
int inqueue(LINKQUEUE *q,
elemtype e)
{NODEPTR p;
p=(NODEPTR)malloc(LEN);
if(p==NULL)return 0;
p?data=e;p ? next=NULL;
if(q?front==NULL)
{q?front=q?rear=p;}
else {q?rear?next=p;
q?rear=p;}
return 1; }
? 元素入队
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (出队 )：
int dequeue(LINKQUEUE *q,
elemtype *e)
{NODEPTR p;
if(q?front==NULL) return 0;
*e=q?front?data;
p=q?front;q?front=p?next;free(p);
if(q?front==NULL) q?rear=NULL;
return 1;
}
? 元素出队
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (队首 )：
int getfront(LINKQUEUE q,elemtype
*e)
{
if(q.front==NULL) return 0;
*e=q.front?data;
return 1;
}
? 获取队首值
队列 (cont’d)
4、队列的应用范例
void part(LINKLIST L1,LINKLIST
*L2)
{ /*L1,L2不带头结点，将 L1中的偶数结点反向链入
L2中 */
NODEPTR p,q;
p=L1;*L2=NULL;
while(p!=NULL&&p?next!=NULL)
{ q=p?next;
p?next=q?next;p=p?next;
q?next=*L2;*L2=q;
}
}
链的拆分
算法思想：
?为了求最短路径，不能象前面算法一样进
行深度优先探索，而应该进行广度优先探索。
?首先将入口位置入队，并将入口设置为已
走。
?进行下面的循环操作：
出队一个位置，从这个位置向 8个反向探
索，只要下一个位置可以走，则入队。入
队时要记录前驱位置。如果下一个位置是
出口，则终止算法。
4.4 栈和队列的应用
1、应用范例
(1) 迷宫的最短路径
栈和队列的应用 (cont’d)
1、应用范例
(1) 迷宫的最短路径
int go3(int maze[N][M],int x,int y,int xx,int
yy)
{int x1,y1,x2,y2,v,front,rear,p;
struct {int x,y,pre;}s[N*M];
/*循环队列,pre是 s的下标,用来记录前驱位置 */
front=rear=1;
s[rear].x=x;s[rear].y=y;
s[rear].pre=0; /*入口入队，前驱为 0，即没有
前驱 */
maze[x][y]=2; //标记为已走
while(front<=rear) // 队不空
{ x1=s[front].x;y1=s[front].y; // 获取队首位置
for(v=1;v<=8;v++) //向 8个方向探索
{ x2=x1+movex[v]; y2=y1+movey[v];
if(!maze[x2][y2]) //如果可走，则入队
{rear++; s[rear].x=x2; s[rear].y=y2;
s[rear].pre=front; maze[x2][y2]=2;
if(x2==xx&&y2==yy) //找到啦！
{p=rear;
while(p>=1)
{maze[s[p].x][s[p].y]=3;//将最短路径标上 3
p=s[p].pre; //沿着 pre寻找前驱位置 }//while
return 1; } //if(x2==xx
}//if(!maze[][]
}//for
front++; //出队
}//while
return 0; //没找到,(
}
背包问题,假设有个能装入总重量为 s的背包，
有 n个重量为 W1,W2,…,Wn 的物品，能否从 n件
物品中选出若干件使其总重量为 s，恰好将背
包装满。
栈和队列的应用 (cont’d)
【 背包问题 】 设有一个背包可以放入的物品的
重量为 s，现有 n件物品，重量分别为 w[1],
w[2],…,w[n] 。问能否从这 n件物品中选择若干
件放入此背包中，使得放入的重量之和正好为
s。如果存在一种符合上述要求的选择，则称
此背包问题有解 (或称其解为真 )；否则称此背
包问题无解 (或称其解为假 )。试用递归方法设
计求解背包问题的算法。
1、应用范例
(2)背包问题
背包问题,假设有个能装入总重量为 s的背包，
有 n个重量为 W1,W2,…,Wn 的物品，能否从 n件
物品中选出若干件使其总重量为 s，恰好将背
包装满。
栈和队列的应用 (cont’d)
算法思想,
?递归算法，即选取 Wn后，问题转化为选取
总重量是 s-Wn的背包问题或者不选择 Wn，问
题转化为在 n-1件物品中，选取总重量是 s的背
包问题。出口有两种情况，一是 s＝ 0(有解 )，
二是 s>0&&n<=0(无解 )。
?非递归算法，返回信息是 (s,n),如果栈顶的
(s,n)不是递归终点，即 s>0&&n>0，即将 (s-
Wn,n-1)入栈。如果 s是 0，栈中 n序列就是解。
如果 (s>0&&n<=0)||s<0，则无解。
1、应用范例
(2)背包问题的全解
栈和队列的应用 (cont’d)
#define N 20
int W[N],count=0;
int biaoji[N]={0};
void knap(int s,int n,int biaoji[])
{/*数组 biaoji标志着物品的选择状态 */
int k；
if(s==0) //开始输出解决方案
{printf("solution %dth is:",++count);
for(k=0;k<N;k++)
if(biaoji[k]==1)printf("%3d ",W[k]);
printf("\n");
} //if
else if(s>0&&n>0)
{biaoji[n-1]=1; //选择 Wn
knap(s-W[n-1],n-1,biaoji); //转化为 s-Wn的背包问题
biaoji[n-1]=0; //不选择 Wn
kanp(s,n-1,biaoji); //转化为总重量为 s的背包问题
}//else
}
递归算法
(2)背包问题的全解
如何只求
得一个解
就退出？
栈和队列的应用 (cont’d)
typedef struct node
{int s,n;
}NODE;
NODE a[N],x;
int top,k,count=0;
void kanp1(int s,int n)
{/*用栈保存选择的物品，由栈顶参数决定继续递归还是输出
得到的解还是推栈 (选错 )修改栈顶值继续再递归 */
top=1;
a[top].s=s;a[top].n=n;
while(top) //top是 0，表示栈空
{while(a[top].s>0&&a[top].n>=1) /继续递归入栈
{top++;a[top].s=a[top-1].s-W[n-1];
a[top].n=n=a[top-1].n-1;
} //while
if(a[top].s<0||(a[top].s>0&&a[top].n==0)) //错误的选择,退栈
{top--;a[top].n=n=a[top].n-1; }
else if(a[top].s==0) //输出一组解
{printf("solution %dth is",++count);
for(k=top-1;k>=1;k--)
printf("%3d ",W[a[k].n-1]);
printf("\n");
//弹出栈顶，修改参数，开始另一种选择
top--;a[top].n= a[top].n-1;
} //else if
} //while(top
}
(2)背包问题的全解 非递归算法
,数据结构,
第三章 栈和队列
? 4.1 栈
? 顺序栈
? 链式栈
? 栈的应用
? 4.2 栈和递归的实现
? 基本概念
? 基本问题
? 4.3 队列
? 顺序队列
? 链式队列
? 队列的应用
? 4.4 栈和队列的应用范例
4.1 栈
1、定义
栈 (Stack)：一种后进先出 (LIFO)的线性表。
栈顶 (top)：允许插入和删除的一端
栈底 (bottom)：不允许插入和删除的一端
栈的主要操作,
建立空栈 进栈
出栈 判断栈是否空
判断栈是否满 获取栈顶元素值
向栈中插入和删 除元素，必须在栈的一
端进行。因此，栈是操作受限的！
栈 (cont’d)
a1
a2
…
an
进栈出栈
栈顶
栈的示意图
栈的修改是按 后进先出
(Last In First Out，简称
LIFO)的原则进行的。
栈 之 顺序栈
2、顺序栈, 用顺序表实现的栈
(1) 顺序栈的数据类型定义,
#define MAXSIZE 50
typedef struct
{
elemtype elem[MAXSIZE];
int top; /*栈顶 */
}SQSTACK;
栈 之 顺序栈 (cont’d)
(2) 顺序栈的基本操作 (建栈 )：
void initstack(SQSTACK *s)
{
s?top= -1; /*-1表示空栈 */
}
? 建立空栈
栈 之 顺序栈 (cont’d)
(3) 顺序栈的基本操作 (判断 )：
int stackempty(SQSTACK s)
{
return s.top == -1;
}
? 判断栈是否空
栈 之 顺序栈 (cont’d)
(4) 顺序栈的基本操作 (入栈 )：
int push(SQSTACK *s,
elemtype e)
{
if(s?top==MAXSIZE-1)
return 0; /*栈满,入栈失败 */
s?top++;
s?elem[s?top]=e;
return 1;
}
? 入栈
栈 之 顺序栈 (cont’d)
(5) 顺序栈的基本操作 (出栈 )：
int pop(SQSTACK *s,elemtype
*e)
{
if(s?top==-1)
return 0; /*栈空,出栈失败 */
*e=s?elem[s?top];
s?top--;
return 1;
}
? 出栈
栈 之 顺序栈 (cont’d)
(6) 顺序栈的基本操作 (获取 )：
int gettop(SQSTACK
s,elemtype *e)
{
if(s?top==-1)return 0;
*e=s?elem[s?top];
}
? 获取栈顶值
栈 之 链式栈
3、链式栈, 用链表实现的栈
(1) 链式栈的数据类型定义（与链表相同）,
typedef struct node
{
elemtype data;
struct node *next;
}NODE,*NODEPTR,*LKSTACK;
#define LEN sizeof(NODE)
栈 之 链式栈 (cont’d)
3、链式栈, 用链表实现的栈
(2) 链式栈的基本操作 (建栈 )：
LKSTACK top;
top=NULL;
? 建立空栈
栈 之 链式栈 (cont’d)
3、链式栈, 用链表实现的栈
(3) 链式栈的基本操作 (入栈 )：
int push(LKSTACK *top,
elemtype e)
{ NODEPTR p;
p=(NODEPTR)malloc(LEN);
if(p==NULL) return 0;
p?data=e;
p?next=*top;
*top=p;
}
? 入栈
栈 之 链式栈 (cont’d)
3、链式栈, 用链表实现的栈
(4) 链式栈的基本操作 (出栈 )：
int pop(LKSTACK *top,
elemtype *e)
{ NODEPTR p;
if(*top==NULL) return 0;
*e=(*top)?data;
p=*top;
*top=(*top)?next;
free(p);
}
? 出栈
栈 之 栈的应用
4、栈的应用范例 (函数调用 )
(1) 函数的调用和返回
系统调用函数时，为了能
够正确返回，必须将返回地
址先入栈，此外，非静态的
局部变量也占用栈的空间，
当函数返回时，这些数据将
出栈。这也就是局部变量生
存期短的原因。
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (表达式 )
(2) 算术表达式求值 (算符优先法 )
基本知识：
?表达式由运算符、操作数和界限符构成，它们
被称为“单词”
?操作数可以是常量或者变量
?运算符区分左右结合性，同优先级运算符连用
时的优先顺序受结合性约束
?界限符包括圆括号和算式结束符
运算符栈 操作数栈
【 例 】 计算,2＋ 3*2^2^2*5-2;
2(
+ 3
* 2
^ 2
^ 2
2^2=4
4
2^4=16
16
3*16=48
48
5
48*5=240240
240＋ 2＝ 242242
－ 2
242－ 2＝ 240
240
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (表达式 )
(2) 算术表达式求值 (算符优先法 )
表达式求值操作规则, 从左向右扫描表达式串，每次去一个单
词，
?如果单词是操作数，一律入操作数栈
?如果单词是运算符 (称为外运算符 )，则比较该外运算符与运
算符栈栈顶运算符的优先级。
? 如果外运算符优先级高或相同，则将该运算符入栈；
?否则将栈顶运算符出栈并出栈操作数计算结果入操作数栈。
注意：运算符栈一开始有个运算符 (，它的优先级最低。
?表达式终结符－－分号的优先级最低，比栈内任何实际运算
符都低。
?当栈顶运算符与外运算符是不同运算符时，按照预先定义的
优先级处理，如果是相同的运算符，右结合性的运算符，外运
算符优先级高。
?为了能对圆括号作统一处理，特别规定左括号在栈内优先级
最低，在栈外优先级最高。
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (表达式 )
(2) 算术表达式求值 (算符优先法 )
为了方便栈内外运算符优先级比较，可以事先规
定运算符的栈内外的优先级数。可以根据下面的表格，
编写函数获取运算符的优先级数：
优先级函数
运算符 x 栈内
isp( x)
栈外
ielp( x)
^ 单目运算符 3 4
* / 2 2
+ - 1 1
( 0 4
float evaluate(char exp[])
{ /*实现开辟操作数栈 s1和运算符栈 s2，并将 (入到 s2
中； exp是输入表达式串 */
while(1)
{从 exp中取出一个单词 x
switch(x)
{ case x是操作数,push(&s1,x);break;
case x是 ')':
反复出栈处理,直到遇到 (为止,break;
case x是 ';':反复出栈处理，直到栈只剩下 (为止；
return操作数栈顶值 ;
case x是其它运算符,
while(ielp(x)<=isp(s2.elem[s2.top--])){出栈处理 }
push(&s2,x);break; }//switch
}//while
}
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (算符 )
(3) 算符优先法求值算法
将程序补充
完整！
练习：
1、设有一个栈,元素进栈的次序,A,B,C,D,E。
试问能否得到出栈序列：
（ 1） C,E,A,B,D；（ 2） C,B,A,D,E；
（ 3） D,C,A,B,E；（ 4） A,C,B,E,D；
（ 5） A,B,C,D,E；（ 6） E,A,B,C,D。
2、按照运算符优先数法，画出对下列算术表达式求值
时运算符栈和操作数栈的变化过程：
A + B^C*E – D/F*G;
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (算符 )
(3) 算符优先法求值算法
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (非递归算法 )
(4) 实现递归问题的非递归算法
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
??
??
?
0,0)),1,,(,1(
0,42
0,31
0,20
0,1
01
),,(
ynxyxnAnA
yn
yn
yn
ynx
nx
yxnA
递归算法：
int Ackerman(int n,int x,int y)
{ if(n==0) return x+1;
else if(y==0)
{if(n==1) return x;
else if(n==2) return 0;
else if(n==3) return 1;
else return 2; }
else
return Ackerman(n-1,Ackerman(n,x,y-1),x);
}
基本思想：
1)如果 (n,x,y)是递归终点,则直接返回具体值 ;
2)如果 (n,x,y)不是递归终点,那么形成新的参
数 (n-1,A(n,x,y-1),x)。但必须先求 A(n,x,y-1),
的值，因此需要将 [n,x]入栈。这个过程称为
一次递归。
3)整个算法就是无限循环，反复执行递归和
返回操作，直到栈空时，结束算法。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
??
??
?
0,0)),1,,(,1(
0,42
0,31
0,20
0,1
01
),,(
ynxyxnAnA
yn
yn
yn
ynx
nx
yxnA
栈 之 栈的应用 (cont’d)
4、栈的应用范例 (非递归算法 )
Ackerman非递归算法
栈 之 栈的应用 (cont’d)
4,栈的应用范例 (递归算法 )
Ackerman非递归算法
A(3,1,2)的计算实例,
当前计算
A(3,1,2)= A(2,A(3,1,1),1)
A(3,1,2)
2 1
3,1,1
2,A 2,A(3,1,0),1),1)
A(3,1,0)=1
2 1
2,1,1)
(2,1,1)
1,2,1,
1
A(2,1,0)=0
1,0,1)
1,0,1)
0,1,0,,0)
0 0
1,0,0)=0
0,0,0)
0,0,0)
2,1,1)
2,1,1)
1,2,1,0)
1
2,1,0)
1,0,1)
1,0,1
0,1,0,0),0)
0 0
1,0,0)
0,0,0)
=1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
??
??
?
0,0)),1,,(,1(
0,42
0,31
0,20
0,1
01
),,(
ynxyxnAnA
yn
yn
yn
ynx
nx
yxnA
? 递归函数：一个直接调用自己或通过一系列
的调用语句间接地调用自己的函数。
? 递归是程序设计中一个强有力的工具。
? 特征：
? 有很多数学函数是递归定义的；
? 有的数据结构本身固有的递归特征，因
此它的操作可递归地描述；
?还有一类问题，虽则问题本身没有明显的
递归结构，但用递归求解比迭代求解更简
单。
4.2 栈和递归实现
1、基本概念和特征
算法思想：
1)递归,只要 n!=0&&y!=0,则反复执行：
y--;准备计算下一个 A(n,x,y)
将返回信息 (n-1,x)入栈
2)返回：如果 (n,x,y)是递归终点，得到一个终
点值 v。如果栈空，算法结束。否则弹出栈顶，
构成新的参数 (n-1,v,x)再次进入递归。
栈和递归实现 (cont’d)
2、应用范例 —— 数学函数递归
? Ackerman非递归算法
int Akmval(int n,int x,int y)
{ /*递归出口的求值函数 */
if(n==0) return x+1;
else switch(n)
{ case 1,return x;
case 2,return 0;
case 3,return 1;
default,return 2;
} //switch
}
/*下面定义入栈的返回信息的数据类型 */
typedef struct
{
int n; int x;
}elemtype;
栈和递归实现 (cont’d)
2、栈应用范例 —— 数学函数递归
ckerman(int n,int x,int y)
SQSTACK s; elemtype e,int v;
initstack(&s);
while(1)
{while(n!=0&&y!=0) /*进入递归 */
{e.n=n-1;e.x=x;push(&s,e); /*返回信息入栈 */
y--; /*准备计算 A(n,x,y-1)*/
}
v=Akmval(n,x,y); /*遇到递归终点 */
if(stackempty(s))return v;
else {pop(&s,&e);
n=e.n;y=e.x;x=v; /*形成新的参数 (n-1,v,x)*/
}
}//while
}
?Ackerman非递归算法
typedef struct { int n,x,y; }elemtype;
int Ackerman(int n,int x,int y)
{SQSTACK s; elemtype e; int v;
initstack(&s);
e.n=n; e.x=x; e.y=y;push(&s,e); /*初始参数入栈 */
while(!stackempty(s))
{gettop(s,&e);n=e.n;x=e.x;y=e.y; /*获取栈顶参数 */
while(n!=0&&y!=0) /*一直递归到终点 */
{y--;e.n=n;e.x=x;e.y=y;
push(&s,e); /*继续入栈下一组参数 */ }
v=Akmvalue(n,x,y);pop(&s,&e); /*终点参数出栈 */
if(stackempty(s)) return v;
else {pop(&s,&e);e.n--;e.y=e.x;e.x=v;
push(&s,e); /*替换成新的栈顶参数 */ }
}//while
}
栈和递归实现 (cont’d)
2、栈的应用范例 —— 数学函数递归
?Ackerman非递归算法 (另 )
入栈信息不同，
算法也会炯异
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
? 实现递归问题的非递归算法
递归问题之二
走迷宫：迷宫有一个入
口和一个出口，从入口到
出口可能有多条通路，但
每次只能走一步，可以有 8
个方向可以走。
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
? 走迷宫的非递归算法
O
O
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7 8 9人口
出口
求迷宫中从人口到出口的所有
路径是一个经典的程序设计问
题。由于解迷宫时，通常用的
是“穷举求解”的方法，即从
人口出发，顺着某一方向向前
探索，若能走通，则继续往前
走；否则沿原路退回，换一个
方向再继续探索，直至所有可
能的通路都探索到为止。
算法思想：
1)用二维数组 maze表示迷宫，数组单元是 0表
示可走，是 1表示不通。
2)将方向按顺时针编成号,1－ 8,1表示正北
3)利用两个一维数组表示位置的变化量：
int movex[]={0,-1,-1,0,1,1,1,0,-1};//行变化
int movey[]={0,0,1,1,1,0,-1,-1,-1}; //列变化
注意,movex[0],movey[0]为无效方向
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
4)从入口开始，向 8个方向探索可以走的下一
个位置，如果有可走的位置，则将当前位置
及其探索的方向入栈，下一个可走的位置作
为当前位置。如果 8个方向都不可走，弹出栈
顶位置信息，作为当前位置，继续探索。如
果下一个可走的位置是出口，则输出栈中的
信息，即是一条通路。
5)当前位置退回到栈顶位置时，原当前位置
应该清 0，这样才能保证探索出多条通路。
? 走迷宫的非递归算法
typedef struct {int x,y,v;}elemtype;
void go(int maze[N][M],int x,int y,int xx,int yy)
{ /*(x,y)是入口,(xx,yy)是出口,N,M是迷宫的行列数 */
int k,x1,y1,x2,y2,v,count=0;SQSTACK s;elemtype e;
initstack(&s);
ex.x=x;e.y=y;e.v=0;
push(&s,e);maze[x][y]=2; //入口入栈,作已走标记 2
while(!stackempty(s))
{ pop(&s,&e);
x1=e.x;y1=e.y; //弹出栈顶位置,作为当前位置
v=e.v+1; //开始下一个方向探索
栈和递归实现 (cont’d)
3、应用范例 —— 迷宫求解
while(v<=8) //开始沿着 8个方向继续探索
{x2=x1+ ovex[v];y2=y1+movey[v]; //计算新位置
if(x2==xx&&y2==yy) //找到出口，输出一条通路
{printf("path %d:",++count);
for(k=0;k<=s.top;k++)
printf("(%d,%d)?",s.elem[k].x,s.elem[k].y);
printf("(%d,%d)?",x1,y1);
printf("(%d,%d)\n",xx,yy);
//如果只需要一条通路，就在这里 return
}//if
if(e.v>0) //如果前面曾探索过通路,将探索过的位置清 0
maze[x1+movex[e.v]][y1+movey[e.v]]=0;
else if(!maze[x2][y ]) //新位置可走
{e.x=x1;e.y=y1;e.v=v;push(&s,e); //当前位置入栈
x1=x2;y1 y2;v=0; //新位置作为当前位置
}//else if
v++; //开始探索下一个有效方向
}//while (v<=8)
}//while
if(count==0) printf("no path\n");
}
? 走迷宫的非递归算法
栈和递归实现 (cont’d)
4、应用范例 —— 汉诺塔
? 实现递归问题的非递归算法
递归问题之三
汉诺塔, 存在 x,y,z三个柱子，
x的上面套有盘子，大盘子在下
面，小盘子在上面，先要求将
这些盘子从 x搬到 z上，这个过程
中，一次只能搬动一个盘子，
并且任何时候都必须保证大盘
子在下面小盘子在上面，可以
利用第三个柱子暂时放置盘子 。
X Y Z
图 3阶 Hanoi塔问题的初始状态
void hanoi(int n,char x,char y,char z)
{SQSTACK s;elemtype e;char t;
initstack(&s);
e.n=n;e.x=x;e.y=y;e.z=z;
push(&s,&e); //初始参数入栈
while(1)
{gettop(s,&e);
while(e.n>1)
{e.n--;t=e.y;e.y=e.z;e.z=t;
push(&s,e); //新参数入栈 }
pop(&s,&e); //栈顶状态可以直接搬动
move(e.x,1,e.z); //递归终点
if(satckempty(s))return; //栈空,算法终止
pop(&s,&e); //取出栈顶参数，这个栈顶
将被替换
move(e.x,e.n,e.z);
e.n--;t=e.x;e.x=e.y;e.y=t;
push(&s,&e); //新的参数入栈
}//while(1)
}
汉诺塔的非递归算法
void hanoi(int n,char x,char y char z)
{if (n==1) move(x,1,z);
else
{hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z); }
}
汉诺塔的递归算法
(1)、确定入栈的返回信息，这些返回信息在出栈
时可以帮助计算函数值或者新的返回信息
(2)、确定入栈的条件，即非递归终点的条件
(3)、确定出栈时对栈顶的操作，是替换成新的返
回信息还是直接出栈
(4)、确定算法终止的条件
5、递归问题的非递归算法编写技巧
栈和递归实现 (cont’d)
初始化栈,确保栈顶参数就
是当前待解决的问题
将栈顶问题分解成规模
更小的问题,新的参数入栈,
直到遇到递归终点
栈顶是递归终点,出栈后,
栈顶的参数不是递归终点,
利用栈顶参数生成新的问题
或者不断出栈
栈空,退出
栈和递归实现 (cont’d)
5、递归问题的非递归算法编写技巧
4.3 队列
1、定义
队列, 是一种先进先出 (FIFO)的线性表。
队尾,允许插入的一端
队首,允许删除的一端
队列的主要操作,
建立空队 进队 (入队 )
出队 判断队列是否满
判断队列是否空 获取队首元素的值
向队列中插入元素只允许在一端进行，
删除元素只允许在另一端进行
队列 (cont’d)
a1 a2 a3 … an
图 1 队列示意图
队
尾
队
头
出队列 入队列
(front) (rear)
队列 (cont’d)
2、顺序存储的队列：循环队列
(1) 循环队列的数据类型定义：
#define MAXSIZE 50
typedef struct
{
elemtype elem[MAXSIZE];
int front,rear;
int len;
}SQQUEUE;
队列 (cont’d)
(d)
5
4
3
2
1
0
(a)
Q.rear
Q.front
(b)
Q.rear
Q.front
(c)
Q.rear
Q.front
Q.rear
Q.front
J1
J2
J3 J3
J5
J6
图 2 头、尾指针和队列中元素之间的关系
(a)空队列； (b)J1,J2和 J3相继入队； (c)J1和 J2相继被删除；
(d)J4,J5和 J6相继插入队列后 J4被删除。
队列 (cont’d)
0
1
maxsize ?1
Q.front
Q.rear
...
...
队列
图 3 循环队列示意图
此时 Q.front = Q.rear无法判
别队列空间是“空”还是“
满”。
两种方法处理：
?另设一个标志位以区别队
列是“空”还是“满”；
?少用一个元素空间，约定
以“队列头指针在队尾指针
的下一位置上”作为队列呈
“满”状态的标志。
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (空队 )：
void initqueue(SQQUEUE *q)
{
q?front=q?rear=0;
q?len=0;
}
? 建立空队
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (队空 )：
int queueempty(SQQUEUE q)
{
return q.len==0;
}
? 判断队是否空
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (入队 )：
int inqueue(SQQUEUE *q,elemtype e)
{ if(q?len==MAXSIZE) return 0;
if(q?len==0)
{ q?front=q?rear=0;
q?elem[q?rear]=e; }
else
{q?rear=(q?rear+1)%MAXSIZE;
q?elem[q?rear]=e; }
q?len++;
return 1;
}
? 元素入队
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (出队 )：
int dequeue(SQQUEUE *q,elemtype *e)
{ if(q?len==0)return 0;
*e=q?elem[q?front];
q?front=(q?front+1)%MAXSIZE;
q?len=0;
return 1;
}
? 元素出队
队列 (cont’d)
2、顺序存储的队列：循环队列
(2) 循环队列的基本操作 (队首 )：
int getfront(SQQUEUE q,elemtype *e)
{
if(q.len==0)return 0;
*e=q.elem[q.front];
return 1;
}
? 获取队首的值
队列 (cont’d)
3、链式存储的队列
(1) 链式队列的数据类型定义：
typedef struct node
{elemtype data;
struct node *next;
}NODE,*NODEPTR;
#define LEN sizeof(NODE)
typedef struct
{
NODEPTR front,rear;
}LINKQUEUE;
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (空队 )：
void initqueue(LINKQUEUE *q)
{
q?front=q?rear=NULL;
}
? 建立空队
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (队空 )：
int queueempty(LINKQUEUE q)
{
return q.front==NULL
}
? 判断队是否空
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (入队 )：
int inqueue(LINKQUEUE *q,
elemtype e)
{NODEPTR p;
p=(NODEPTR)malloc(LEN);
if(p==NULL)return 0;
p?data=e;p ? next=NULL;
if(q?front==NULL)
{q?front=q?rear=p;}
else {q?rear?next=p;
q?rear=p;}
return 1; }
? 元素入队
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (出队 )：
int dequeue(LINKQUEUE *q,
elemtype *e)
{NODEPTR p;
if(q?front==NULL) return 0;
*e=q?front?data;
p=q?front;q?front=p?next;free(p);
if(q?front==NULL) q?rear=NULL;
return 1;
}
? 元素出队
队列 (cont’d)
3、链式存储的队列
(2) 链式队列的基本操作 (队首 )：
int getfront(LINKQUEUE q,elemtype
*e)
{
if(q.front==NULL) return 0;
*e=q.front?data;
return 1;
}
? 获取队首值
队列 (cont’d)
4、队列的应用范例
void part(LINKLIST L1,LINKLIST
*L2)
{ /*L1,L2不带头结点，将 L1中的偶数结点反向链入
L2中 */
NODEPTR p,q;
p=L1;*L2=NULL;
while(p!=NULL&&p?next!=NULL)
{ q=p?next;
p?next=q?next;p=p?next;
q?next=*L2;*L2=q;
}
}
链的拆分
算法思想：
?为了求最短路径，不能象前面算法一样进
行深度优先探索，而应该进行广度优先探索。
?首先将入口位置入队，并将入口设置为已
走。
?进行下面的循环操作：
出队一个位置，从这个位置向 8个反向探
索，只要下一个位置可以走，则入队。入
队时要记录前驱位置。如果下一个位置是
出口，则终止算法。
4.4 栈和队列的应用
1、应用范例
(1) 迷宫的最短路径
栈和队列的应用 (cont’d)
1、应用范例
(1) 迷宫的最短路径
int go3(int maze[N][M],int x,int y,int xx,int
yy)
{int x1,y1,x2,y2,v,front,rear,p;
struct {int x,y,pre;}s[N*M];
/*循环队列,pre是 s的下标,用来记录前驱位置 */
front=rear=1;
s[rear].x=x;s[rear].y=y;
s[rear].pre=0; /*入口入队，前驱为 0，即没有
前驱 */
maze[x][y]=2; //标记为已走
while(front<=rear) // 队不空
{ x1=s[front].x;y1=s[front].y; // 获取队首位置
for(v=1;v<=8;v++) //向 8个方向探索
{ x2=x1+movex[v]; y2=y1+movey[v];
if(!maze[x2][y2]) //如果可走，则入队
{rear++; s[rear].x=x2; s[rear].y=y2;
s[rear].pre=front; maze[x2][y2]=2;
if(x2==xx&&y2==yy) //找到啦！
{p=rear;
while(p>=1)
{maze[s[p].x][s[p].y]=3;//将最短路径标上 3
p=s[p].pre; //沿着 pre寻找前驱位置 }//while
return 1; } //if(x2==xx
}//if(!maze[][]
}//for
front++; //出队
}//while
return 0; //没找到,(
}
背包问题,假设有个能装入总重量为 s的背包，
有 n个重量为 W1,W2,…,Wn 的物品，能否从 n件
物品中选出若干件使其总重量为 s，恰好将背
包装满。
栈和队列的应用 (cont’d)
【 背包问题 】 设有一个背包可以放入的物品的
重量为 s，现有 n件物品，重量分别为 w[1],
w[2],…,w[n] 。问能否从这 n件物品中选择若干
件放入此背包中，使得放入的重量之和正好为
s。如果存在一种符合上述要求的选择，则称
此背包问题有解 (或称其解为真 )；否则称此背
包问题无解 (或称其解为假 )。试用递归方法设
计求解背包问题的算法。
1、应用范例
(2)背包问题
背包问题,假设有个能装入总重量为 s的背包，
有 n个重量为 W1,W2,…,Wn 的物品，能否从 n件
物品中选出若干件使其总重量为 s，恰好将背
包装满。
栈和队列的应用 (cont’d)
算法思想,
?递归算法，即选取 Wn后，问题转化为选取
总重量是 s-Wn的背包问题或者不选择 Wn，问
题转化为在 n-1件物品中，选取总重量是 s的背
包问题。出口有两种情况，一是 s＝ 0(有解 )，
二是 s>0&&n<=0(无解 )。
?非递归算法，返回信息是 (s,n),如果栈顶的
(s,n)不是递归终点，即 s>0&&n>0，即将 (s-
Wn,n-1)入栈。如果 s是 0，栈中 n序列就是解。
如果 (s>0&&n<=0)||s<0，则无解。
1、应用范例
(2)背包问题的全解
栈和队列的应用 (cont’d)
#define N 20
int W[N],count=0;
int biaoji[N]={0};
void knap(int s,int n,int biaoji[])
{/*数组 biaoji标志着物品的选择状态 */
int k；
if(s==0) //开始输出解决方案
{printf("solution %dth is:",++count);
for(k=0;k<N;k++)
if(biaoji[k]==1)printf("%3d ",W[k]);
printf("\n");
} //if
else if(s>0&&n>0)
{biaoji[n-1]=1; //选择 Wn
knap(s-W[n-1],n-1,biaoji); //转化为 s-Wn的背包问题
biaoji[n-1]=0; //不选择 Wn
kanp(s,n-1,biaoji); //转化为总重量为 s的背包问题
}//else
}
递归算法
(2)背包问题的全解
如何只求
得一个解
就退出？
栈和队列的应用 (cont’d)
typedef struct node
{int s,n;
}NODE;
NODE a[N],x;
int top,k,count=0;
void kanp1(int s,int n)
{/*用栈保存选择的物品，由栈顶参数决定继续递归还是输出
得到的解还是推栈 (选错 )修改栈顶值继续再递归 */
top=1;
a[top].s=s;a[top].n=n;
while(top) //top是 0，表示栈空
{while(a[top].s>0&&a[top].n>=1) /继续递归入栈
{top++;a[top].s=a[top-1].s-W[n-1];
a[top].n=n=a[top-1].n-1;
} //while
if(a[top].s<0||(a[top].s>0&&a[top].n==0)) //错误的选择,退栈
{top--;a[top].n=n=a[top].n-1; }
else if(a[top].s==0) //输出一组解
{printf("solution %dth is",++count);
for(k=top-1;k>=1;k--)
printf("%3d ",W[a[k].n-1]);
printf("\n");
//弹出栈顶，修改参数，开始另一种选择
top--;a[top].n= a[top].n-1;
} //else if
} //while(top
}
(2)背包问题的全解 非递归算法
,数据结构,
第三章 栈和队列
