? 栈 ( Stack )
? 队列 ( Queue )
? 递归的概念
? 递归与递归工作栈
? 递归与回溯
? 只允许在一端插入和删除的线性表
? 允许插入和删除
的一端称为 栈顶
(top)，另一端称
为 栈底 (bottom)
? 特点
后进先出 (LIFO)
栈 ( Stack )
退栈 进栈
a0
an-1
an-2
?
top
bottom
ADT Stack {
//对象,由数据类型为 StackData的元素构成
int Push (stack *S,StackData x); //进栈
int Pop (stack *S,StackData &x); //出栈
int GetTop (stack *S,StackData &x); //取栈顶
void InitStack (stack *S); //置空栈
int StackEmpty (stack *S); //判栈空否
int StackFull (stack *S); //判栈满否
}
栈的主要操作
#define StackSize 100
typedef char StackData;
typedef struct { //顺序栈定义
StackData data[StackSize]; //栈数组
int top; //栈顶指针
} SeqStack;
栈的数组表示 — 顺序栈
0 1 2 3 4 5 6 7 8 9 StackSize-1
top (栈空 )
data
int StackEmpty (SeqStack *S) {
//判断栈是否空？空则返回 1，否则返回 0
return S->top == -1;
}
int StackFull (SeqStack *S) {
//判断栈是否满？满则返回 1，否则返回 0
return S->top == StackSize-1;
}
void InitStack ( SeqStack *S) { //置空栈
S->top = -1;
}
top 空栈
top top
toptop
top
a 进栈 b 进栈
a ab
ab
c
d
e
e 进栈
ab
c
d
e
f 进栈溢出
ab
d
e
e 退栈
c
top
c 退栈 b 退栈
ab
a
a 退栈 空 栈
top
ab
d
d 退栈
c
top
ab
c
top
top
int Push (SeqStack *S,StackData x) {
//若栈满返回 0,否则 新元素 x 进栈并返回 1
if ( StackFull (S) ) return 0;
S->data[++S->top] = x; //加入新元素
return 1;
}
int Gettop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素读到 x并返回 1
if ( StackEmpty(S) ) return 0;
x = S->data[S->top];
return 1;
}
b[0] t[0] t[1] b[1]
0 maxSize-1
data
int pop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素退出到 x并返回 1
if ( StackEmpty(S) ) return 0;
x = S->data[S->top--];
return 1;
}
双栈共享一个栈空间
双栈处理
? 两个栈共享一个数组空间 V[maxSize]
? 设立栈顶指针数组 t[2] 和栈底指针数组 b[2]
t[i]和 b[i]分别指示 第 i 个栈 的栈顶与栈底
? 初始 t[0] = b[0] = -1
t[1] = b[1] = maxSize
? 栈满条件,t[0]+1 == t[1]
//栈顶指针相遇
? 栈空条件,t[0] = b[0]或 t[1] = b[1]
//栈顶指针退到栈底
int push ( DualStack *DS,StackData x,int i ) {
if ( DS->t[0]+1 == DS->t[1] ) return 0;
if ( i == 0 ) t[0]++; else t[1]--;
DS->data[DS->t[i]] = x; return 1;
}
int Pop (DualStack *DS,StackData &x,int i ) {
if ( DS->t[i] == DS->b[i] ) return 0;
x = DS->data[DS->t[i]];
if ( i == 0 ) t[0]--; else t[1]++;
return 1;
}
栈的链接表示 — 链式栈
? 链式栈无栈满问题，空间可扩充
? 插入与删除仅在栈顶处执行
? 链式栈的栈顶在链头
? 适合于多栈操作
top
typedef int StackData;
typedef struct node {
StackData data; //结点数据
struct node *link; //结点链指针
} StackNode;
typedef struct {
StackNode *top; //栈顶指针
} LinkStack;
链式栈 (LinkStack)的定义
链式栈操作的实现
void InitStack ( LinkStack *S ) {
S->top = NULL;
}
int Push ( LinkStack *S,StackData x ) {
StackNode *p = ( StackNode * ) malloc
( sizeof ( StackNode ) );
p->data = x; p->link = S->top;
S->top = p; return 1;
}
int StackEmpty (LinkStack *S) {
return S->top == NULL;
}
int Pop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
StackNode * p = S->top;
S->top = p->link;
x = p->data;
free (p);
return 1;
}
int GetTop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
x = S->top->data;
return 1;
}
? 定义
? 队列是只允许在一端删除，在另一端插
入的线性表
? 允许删除的一端叫做队头 (front)，允许
插入的一端叫做队尾 (rear)。
? 特性
? 先进先出 (FIFO,First In First Out)
a0 a1 a2 an-1
front rear
??
队列 ( Queue )
ADT Queue {
//对象,由数据类型为 QueueData的元素构成
int EnQueue (Queue *Q,QueueData x); //进队
int DeQueue (Queue *Q,QueueData &x);//出队
int GetFront (Queue *Q,QueueData &x);//取队头
void InitQueue (Queue *Q); //置空队
int QueueEmpty (Queue *Q); //判队空否
int QueueFull (Queue *Q); //判队满否
}
队列的主要操作
#define QueueSize 50;
typedef int QueueData;
typedef struct {
QueueData data[QueueSize];
int rear,front;
} SeqQueue;
void InitQueue ( SeqQueue *Q ) {
Q->front = Q->rear = -1;
}
队列的顺序存储表示 — 顺序队列
队列的进队和出队
front rear 空队列 front rear A进队
A
front rear B进队
A B
front rear C,D进队
A B C D
front rear A退队
B C D
front rear B退队
C D
front rear E,F,G进 队
C D E F G C D E F G
front rear H进 队,溢出
队列的进队和出队原则
? 进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位置加入。
? 出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
? 队满时再进队将 溢出出错 ；
? 队空时再出队将 队空处理 。
? 解决办法之一：将队列元素存放数组首尾
相接，形成 循环 (环形 )队列 。
? 队列存放数组被当作首尾相接的表处理。
? 队头、队尾指针 加 1时从 QueueSize -1直接进
到 0，可用语言的取模 (余数 )运算实现。
?队头指针进 1,front = (front+1) % QueueSize;
?队尾指针进 1,rear = (rear+1) % QueueSize;
?队列初始化,front = rear = 0;
?队空条件,front == rear;
?队满条件,(rear+1) % QueueSize == front
循环队列 (Circular Queue)
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 frontrear
A A
BCrear
rear空队列 A进 队 B,C进 队
0
1
23
4
5
6 7
0
1
23
4
5
6 7
A退 队 B退 队
0
1
23
4
5
6 7
D,E,F,G,H,I进 队
frontBCrear
A
front
BC
rear front
C
rearDE
F G
H
I
void InitQueue ( SeqQueue *Q ) {
Q->rear = Q->front = 0;
}
int QueueEmpty ( SeqQueue *Q ) {
return Q->rear == Q->front;
}
int QueueFull ( SeqQueue *Q ) {
return (Q->rear+1) % QueueSize == Q->front;
}
循环队列操作的实现
int EnQueue ( SeqQueue *Q,QueueData x ) {
if ( QueueFull (Q) ) return 0;
Q->rear = ( Q->rear+1) % QueueSize;
Q->data[Q->rear] = x;
return 1;
}
int DeQueue ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
Q->front = ( Q->front+1) % QueueSize;
x = Q->data[Q->front]; return 1;
}
int GetFront ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[(Q->front+1) % QueueSize];
return 1;
}
队列的链接表示 — 链式队列
? 队头在链头，队尾在链尾。
? 链式队列在进队时无队满问题，但
有队空问题。
? 队空条件为 front == NULL
front
rear
链式队列的定义
typedef int QueueData;
typedef struct node {
QueueData data; //队列结点数据
struct node *link; //结点链指针
} QueueNode;
typedef struct {
QueueNode *rear,*front;
} LinkQueue;
void InitQueue ( LinkQueue *Q ) {
Q->rear = Q->front = NULL;
}
int QueueEmpty ( LinkQueue *Q ) {
return Q->front == NULL;
}
int GetFront ( LinkQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->front->data; return 1;
}
链式队列主要操作的实现
int EnQueue ( LinkQueue *Q,QueueData x ) {
QueueNode *p = ( QueueNode * ) malloc
( sizeof ( QueueNode ) );
p->data = x; p->link = NULL;
if ( Q->front == NULL )
//空,创建第一个结点
Q->front = Q->rear = p;
else Q->rear = Q->rear->link = p;
return 1;
}
int DeQueue ( LinkQueue *Q,QueueData &x) {
//删去队头结点，并返回队头元素的值
if ( QueueEmpty (Q) ) return 0; //判队空
QueueNode *p = Q->front;
x = p->data; //保存队头的值
Q->front = Q->front->link; //新队头
if (Q->front == NULL) Q->rear = NULL;
free (p);
return 1;
}
1 1 i = 1
1 2 1 2
1 3 3 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
队列的应用举例
— 逐行打印二项展开式 (a + b)i 的系数
杨辉三角形 (Pascal’s triangle)
分析第 i 行元素与第 i+1行元素的关系
从前一行的数据可以计算下一行的数据
0 1 1 0 t
s+t
i = 3 0 1 3 3 1 0
s
i = 4 1 4 6 4 1
i = 2 0 1 2 1 0
从第 i 行数据计算并存放第 i+1 行数据
1 2 1 0 1 3 3 1 0 1 4 6
s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1
s+t s=t s=t s=t s=t s=t s=t s=t s=t
s+t s+t s+t s+t s+t s+t s+t s+t
利用队列打印二项展开式系数的程序
#include "queue.h"
void YANGVI ( int n ) {
Queue q; //队列初始化
InitQueue(q);
EnQueue (q,1); EnQueue (q,1);
int s = 0,t;
for ( int i = 1; i <= n; i++ ) { //逐行计算
printf (“\n”);
EnQueue (q,0);
for ( int j = 1; j <= i+2; j++ ) { //下一行
DeQueue (q,&t);
EnQueue (q,s+t);
s = t;
if ( j != i+2 ) printf (“%d”,s);
}
}
}
递归的概念
? 递归的定义 若一个对象部分地包含它
自己,或用它自己给自己定义,则称这
个对象是递归的；若一个过程 直接地或
间接地调用自己,则称这个过程是递归
的过程。
? 以下三种情况常常用到递归方法。
? 定义是递归的
? 数据结构是递归的
? 问题的解法是递归的
定义是递归的
求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
例如，阶乘函数
?
?
?
???
?
?
时当
时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 n! 的过程
主程序 main, fact(4)
参数 4 计算 4*fact(3) 返回 24
参数 3 计算 3*fact(2) 返回 6
参数 2 计算 2*fact(1) 返回 2
参数 1 计算 1*fact(0) 返回 1
参数 0 直接定值 = 1 返回 1
参
数
传
递
结
果
返
回
递
归
调
用
回
归
求
值
数据结构是递归的
? 一个结点，它的指针域为 NULL，是
一个单链表 ;
? 一个结点，它的指针域指向单链表，
仍是一个单链表。
例如，单链表结构
f ?
f ?
搜索链表最后一个结点并打印其数值
void Print ( ListNode *f ) {
if ( f ->link == NULL )
printf (“%d\n”,f ->data );
else Print ( f ->link );
}
f
f f f f
?a0 a1 a2 a3 a4
递归找链尾
在链表中寻找等于给定值的结点并打印
其数值
void Print ( ListNode *f,ListData& x ) {
if ( f != NULL )
if ( f -> data == x )
printf (“%d\n”,f ->data );
else Print ( f -> link,x );
}
f
f f f
?
递归找含 x值的结点
x
问题的解法是递归的
例如，汉诺塔 (Tower of Hanoi)问题的解法：
如果 n = 1,则将这一个盘子直接从 A 柱
移到 C 柱上 。 否则, 执行以下三步：
① 用 C 柱做过渡, 将 A 柱上的 (n-1) 个
盘子移到 B 柱上：
② 将 A 柱上最后一个盘子直接移到 C 柱
上；
③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个
盘子移到 C 柱上。
#include <iostream.h>
#include"strclass.h”
void Hanoi (int n,String A,String B,String C) {
//解决汉诺塔问题的算法
if ( n == 1 ) printf (" move %s",A," to %s,C);
else { Hanoi ( n-1,A,C,B );
printf (" move %s",A," to %s,C);
Hanoi ( n-1,B,A,C );
}
}
自顶向下、逐步分解的策略
? 子问题应与原问题做同样的事情，且更
为简单；
? 解决递归问题的策略是把一个规模比较
大的问题分解为一个或若干规模比较小
的问题，分别对这些比较小的问题求解，
再综合它们的结果，从而得到原问题的
解。 — 分而治之策略（分治法）
? 这些比较小的问题的求解方法与原来问
题的求解方法一样。
构成递归的条件
? 不能无限制地调用本身，必须有一个出口，
化简为非递归状况直接处理。
Procedure <name> ( <parameter list> ) {
if ( < initial condition> )
return ( initial value );
else
return (<name> ( parameter exchange ));
}
递归过程与递归工作栈
? 递归过程在实现时，需要自己调用自己。
? 层层向下递归，退出时的次序正好相反：
递归调用
n! (n-1)! (n-2)! 1! 0!=1
返回次序
? 主程序第一次调用递归过程为 外部调用 ；
? 递归过程每次递归调用自己为 内部调用 。
? 它们 返回 调用它的过程的 地址 不同。
递归工作栈
? 每一次递归调用时，需要为过程中使用
的参数、局部变量等另外分配存储空间。
? 每层递归调用需分配的空间形成递归工
作记录，按后进先出的栈组织。
局部变量
返回地址
参 数
活动
记录
框架
递归
工作记录
函数递归时的活动记录
……………….
<下一条指令 >
Function(<参数表 >)
……………….
<return>
调用块
函数块
返回地址 (下一条指令 ) 局部变量 参数
long Factorial ( long n ) {
int temp;
if ( n == 0 ) return 1;
else temp = n * Factorial (n-1);
RetLoc2
return temp;
}
void main ( ) {
int n;
n = Factorial (4);
RetLoc1
}
计算 Fact时活动记录的内容
递
归
调
用
序
列
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
参数 返回地址 返回时的指令
RetLoc1 return 4*6 //返回 24
RetLoc2 return 3*2 //返回 6
RetLoc2 return 1 //返回 1
RetLoc2 return 1*1 //返回 1
RetLoc2 return 2*1 //返回 2
递归过程改为非递归过程
? 递归过程简洁、易编、易懂
? 递归过程 效率低,重复计算多
? 改为非递归过程的目的是 提高效率
? 单向递归 和 尾递归 可直接用 迭代 实
现其非递归过程
? 其他情形必须借助 栈 实现非递归过
程
计算斐波那契数列的函数 Fib(n)的定义
求解斐波那契数列的递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
?
?
?
????
?
?
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
调用次数 NumCall(k) = 2*Fib(k+1) - 1。
斐波那契数列的递归调用树
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(4)
Fib(1) Fib(0)
Fib(2)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(5)
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
栈结点 n tag
tag = 1,向左递归； tag = 2,向右递归
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2? ? ? ?
4 1
n=1
sum=1+1
4 2
? n=4-2??
?
?
?
?
?
?
?
?
?
? ?
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
2 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
?
? ? ?
?
?
? ?
long Fibnacci ( long n ) {
Stack<Node> S; Node *w; long sum = 0;
//反复执行直到所有终端结点数据累加完
do {
while ( n > 1 ) {
w->n = n; w->tag = 1; S.push ( w );
n--;
}
//向左递归到底,边走边进栈
sum = sum + n; //执行求和
while ( !S.IsEmpty( ) ) {
w = S.getTop( ); S.Pop( );
if ( w->tag == 1 ) { //改为向右递归
w->tag = 2; S.push ( w );
n = w->n – 2; //F(n)右侧为 F(n-2)
break;
}
}
} while ( !S.IsEmpty( ) );
return sum;
}
单向递归用迭代法实现
long FibIter ( long n ) {
if ( n <= 1 ) return n;
long twoback = 0,oneback = 1,Current;
for ( int i = 2; i <= n; i++ ) {
Current = twoback + oneback;
twoback = oneback; oneback = Current;
}
return Current;
}
void recfunc ( int A[ ],int n ) {
if ( n >= 0 ) {
printf (“%d”,A[n] );
n--;
recfunc ( A,n );
}
}
25 36 72 18 99 49 54 63
尾递归用迭代法实现
void sterfunc ( int A[ ],int n ) {
//消除了尾递归的非递归函数
while ( n >= 0 ) {
printf ( "value %s,,A[n] );
n--;
}
}
递归与回溯 常用于搜索过程
n皇后问题
在 n 行 n 列的 国际象棋棋盘上，
若 两个皇后 位于 同一行, 同一列,
同一对角线 上，则称为它们为 互相
攻击 。 n皇后问题是指 找到这 n 个
皇后的互不攻击的布局 。
1#主对角线
3#主对角线
5#主对角线
?
?
?
0#次对角线
2#次对角线
4#次对角线
6#次对角线
1#次对角线
3#次对角线
5#次对角线
0#主对角线
2#主对角线
4#主对角线
6#主对角线
?
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
解题思路
? 安放 第 i 行 皇后时，需要在列的方向从 0
到 n-1 试探 ( j = 0,…,n -1 )
? 在 第 j 列 安放一个皇后：
? 如果在 列, 主对角线, 次对角线 方向
有其它皇后，则出现攻击，撤消在 第 j
列 安放的皇后。
? 如果没有出现攻击，在 第 j 列 安放的
皇后不动，递归安放第 i+1行皇后。
? 设置 4 个数组
? col [n], col[i] 标识第 i 列是否安放
了皇后
? md[2n-1], md[k] 标识第 k 条主对
角线是否安放了皇后
? sd[2n-1], sd[k] 标识第 k 条次对角
线是否安放了皇后
? q[n], q[i] 记录第 i 行皇后在第几列
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( 第 i 行第 j 列没有攻击 ) {
在 第 i 行第 j 列安放皇后 ；
if ( i == n-1 ) 输出一个布局 ；
else Queen ( i+1 );
撤消 第 i 行第 j 列的皇后 ；
}
}
}
算法求精
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( !col[j] && !md[n+i-j-1] && !sd[i+j] )
{
/*第 i 行第 j 列没有攻击 */
col[j] = md[n+i-j-1] = sd[i+j] = 1;
q[i] = j;
/*在 第 i 行第 j 列安放皇后 */
if ( i == n-1 ) { /*输出一个布局 */
for ( int k = 0; k < n; k++ )
cout << q[k] << ‘,’;
cout << endl;
}
else Queen ( i+1 );
col[j] = md[n+i-j-1] = sd[i+j] = 0;
q[i] = 0; /*撤消 第 i 行第 j 列的皇后 */
}
}
}
? 队列 ( Queue )
? 递归的概念
? 递归与递归工作栈
? 递归与回溯
? 只允许在一端插入和删除的线性表
? 允许插入和删除
的一端称为 栈顶
(top)，另一端称
为 栈底 (bottom)
? 特点
后进先出 (LIFO)
栈 ( Stack )
退栈 进栈
a0
an-1
an-2
?
top
bottom
ADT Stack {
//对象,由数据类型为 StackData的元素构成
int Push (stack *S,StackData x); //进栈
int Pop (stack *S,StackData &x); //出栈
int GetTop (stack *S,StackData &x); //取栈顶
void InitStack (stack *S); //置空栈
int StackEmpty (stack *S); //判栈空否
int StackFull (stack *S); //判栈满否
}
栈的主要操作
#define StackSize 100
typedef char StackData;
typedef struct { //顺序栈定义
StackData data[StackSize]; //栈数组
int top; //栈顶指针
} SeqStack;
栈的数组表示 — 顺序栈
0 1 2 3 4 5 6 7 8 9 StackSize-1
top (栈空 )
data
int StackEmpty (SeqStack *S) {
//判断栈是否空？空则返回 1，否则返回 0
return S->top == -1;
}
int StackFull (SeqStack *S) {
//判断栈是否满？满则返回 1，否则返回 0
return S->top == StackSize-1;
}
void InitStack ( SeqStack *S) { //置空栈
S->top = -1;
}
top 空栈
top top
toptop
top
a 进栈 b 进栈
a ab
ab
c
d
e
e 进栈
ab
c
d
e
f 进栈溢出
ab
d
e
e 退栈
c
top
c 退栈 b 退栈
ab
a
a 退栈 空 栈
top
ab
d
d 退栈
c
top
ab
c
top
top
int Push (SeqStack *S,StackData x) {
//若栈满返回 0,否则 新元素 x 进栈并返回 1
if ( StackFull (S) ) return 0;
S->data[++S->top] = x; //加入新元素
return 1;
}
int Gettop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素读到 x并返回 1
if ( StackEmpty(S) ) return 0;
x = S->data[S->top];
return 1;
}
b[0] t[0] t[1] b[1]
0 maxSize-1
data
int pop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素退出到 x并返回 1
if ( StackEmpty(S) ) return 0;
x = S->data[S->top--];
return 1;
}
双栈共享一个栈空间
双栈处理
? 两个栈共享一个数组空间 V[maxSize]
? 设立栈顶指针数组 t[2] 和栈底指针数组 b[2]
t[i]和 b[i]分别指示 第 i 个栈 的栈顶与栈底
? 初始 t[0] = b[0] = -1
t[1] = b[1] = maxSize
? 栈满条件,t[0]+1 == t[1]
//栈顶指针相遇
? 栈空条件,t[0] = b[0]或 t[1] = b[1]
//栈顶指针退到栈底
int push ( DualStack *DS,StackData x,int i ) {
if ( DS->t[0]+1 == DS->t[1] ) return 0;
if ( i == 0 ) t[0]++; else t[1]--;
DS->data[DS->t[i]] = x; return 1;
}
int Pop (DualStack *DS,StackData &x,int i ) {
if ( DS->t[i] == DS->b[i] ) return 0;
x = DS->data[DS->t[i]];
if ( i == 0 ) t[0]--; else t[1]++;
return 1;
}
栈的链接表示 — 链式栈
? 链式栈无栈满问题，空间可扩充
? 插入与删除仅在栈顶处执行
? 链式栈的栈顶在链头
? 适合于多栈操作
top
typedef int StackData;
typedef struct node {
StackData data; //结点数据
struct node *link; //结点链指针
} StackNode;
typedef struct {
StackNode *top; //栈顶指针
} LinkStack;
链式栈 (LinkStack)的定义
链式栈操作的实现
void InitStack ( LinkStack *S ) {
S->top = NULL;
}
int Push ( LinkStack *S,StackData x ) {
StackNode *p = ( StackNode * ) malloc
( sizeof ( StackNode ) );
p->data = x; p->link = S->top;
S->top = p; return 1;
}
int StackEmpty (LinkStack *S) {
return S->top == NULL;
}
int Pop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
StackNode * p = S->top;
S->top = p->link;
x = p->data;
free (p);
return 1;
}
int GetTop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
x = S->top->data;
return 1;
}
? 定义
? 队列是只允许在一端删除，在另一端插
入的线性表
? 允许删除的一端叫做队头 (front)，允许
插入的一端叫做队尾 (rear)。
? 特性
? 先进先出 (FIFO,First In First Out)
a0 a1 a2 an-1
front rear
??
队列 ( Queue )
ADT Queue {
//对象,由数据类型为 QueueData的元素构成
int EnQueue (Queue *Q,QueueData x); //进队
int DeQueue (Queue *Q,QueueData &x);//出队
int GetFront (Queue *Q,QueueData &x);//取队头
void InitQueue (Queue *Q); //置空队
int QueueEmpty (Queue *Q); //判队空否
int QueueFull (Queue *Q); //判队满否
}
队列的主要操作
#define QueueSize 50;
typedef int QueueData;
typedef struct {
QueueData data[QueueSize];
int rear,front;
} SeqQueue;
void InitQueue ( SeqQueue *Q ) {
Q->front = Q->rear = -1;
}
队列的顺序存储表示 — 顺序队列
队列的进队和出队
front rear 空队列 front rear A进队
A
front rear B进队
A B
front rear C,D进队
A B C D
front rear A退队
B C D
front rear B退队
C D
front rear E,F,G进 队
C D E F G C D E F G
front rear H进 队,溢出
队列的进队和出队原则
? 进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位置加入。
? 出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
? 队满时再进队将 溢出出错 ；
? 队空时再出队将 队空处理 。
? 解决办法之一：将队列元素存放数组首尾
相接，形成 循环 (环形 )队列 。
? 队列存放数组被当作首尾相接的表处理。
? 队头、队尾指针 加 1时从 QueueSize -1直接进
到 0，可用语言的取模 (余数 )运算实现。
?队头指针进 1,front = (front+1) % QueueSize;
?队尾指针进 1,rear = (rear+1) % QueueSize;
?队列初始化,front = rear = 0;
?队空条件,front == rear;
?队满条件,(rear+1) % QueueSize == front
循环队列 (Circular Queue)
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 frontrear
A A
BCrear
rear空队列 A进 队 B,C进 队
0
1
23
4
5
6 7
0
1
23
4
5
6 7
A退 队 B退 队
0
1
23
4
5
6 7
D,E,F,G,H,I进 队
frontBCrear
A
front
BC
rear front
C
rearDE
F G
H
I
void InitQueue ( SeqQueue *Q ) {
Q->rear = Q->front = 0;
}
int QueueEmpty ( SeqQueue *Q ) {
return Q->rear == Q->front;
}
int QueueFull ( SeqQueue *Q ) {
return (Q->rear+1) % QueueSize == Q->front;
}
循环队列操作的实现
int EnQueue ( SeqQueue *Q,QueueData x ) {
if ( QueueFull (Q) ) return 0;
Q->rear = ( Q->rear+1) % QueueSize;
Q->data[Q->rear] = x;
return 1;
}
int DeQueue ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
Q->front = ( Q->front+1) % QueueSize;
x = Q->data[Q->front]; return 1;
}
int GetFront ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[(Q->front+1) % QueueSize];
return 1;
}
队列的链接表示 — 链式队列
? 队头在链头，队尾在链尾。
? 链式队列在进队时无队满问题，但
有队空问题。
? 队空条件为 front == NULL
front
rear
链式队列的定义
typedef int QueueData;
typedef struct node {
QueueData data; //队列结点数据
struct node *link; //结点链指针
} QueueNode;
typedef struct {
QueueNode *rear,*front;
} LinkQueue;
void InitQueue ( LinkQueue *Q ) {
Q->rear = Q->front = NULL;
}
int QueueEmpty ( LinkQueue *Q ) {
return Q->front == NULL;
}
int GetFront ( LinkQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->front->data; return 1;
}
链式队列主要操作的实现
int EnQueue ( LinkQueue *Q,QueueData x ) {
QueueNode *p = ( QueueNode * ) malloc
( sizeof ( QueueNode ) );
p->data = x; p->link = NULL;
if ( Q->front == NULL )
//空,创建第一个结点
Q->front = Q->rear = p;
else Q->rear = Q->rear->link = p;
return 1;
}
int DeQueue ( LinkQueue *Q,QueueData &x) {
//删去队头结点，并返回队头元素的值
if ( QueueEmpty (Q) ) return 0; //判队空
QueueNode *p = Q->front;
x = p->data; //保存队头的值
Q->front = Q->front->link; //新队头
if (Q->front == NULL) Q->rear = NULL;
free (p);
return 1;
}
1 1 i = 1
1 2 1 2
1 3 3 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
队列的应用举例
— 逐行打印二项展开式 (a + b)i 的系数
杨辉三角形 (Pascal’s triangle)
分析第 i 行元素与第 i+1行元素的关系
从前一行的数据可以计算下一行的数据
0 1 1 0 t
s+t
i = 3 0 1 3 3 1 0
s
i = 4 1 4 6 4 1
i = 2 0 1 2 1 0
从第 i 行数据计算并存放第 i+1 行数据
1 2 1 0 1 3 3 1 0 1 4 6
s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1
s+t s=t s=t s=t s=t s=t s=t s=t s=t
s+t s+t s+t s+t s+t s+t s+t s+t
利用队列打印二项展开式系数的程序
#include "queue.h"
void YANGVI ( int n ) {
Queue q; //队列初始化
InitQueue(q);
EnQueue (q,1); EnQueue (q,1);
int s = 0,t;
for ( int i = 1; i <= n; i++ ) { //逐行计算
printf (“\n”);
EnQueue (q,0);
for ( int j = 1; j <= i+2; j++ ) { //下一行
DeQueue (q,&t);
EnQueue (q,s+t);
s = t;
if ( j != i+2 ) printf (“%d”,s);
}
}
}
递归的概念
? 递归的定义 若一个对象部分地包含它
自己,或用它自己给自己定义,则称这
个对象是递归的；若一个过程 直接地或
间接地调用自己,则称这个过程是递归
的过程。
? 以下三种情况常常用到递归方法。
? 定义是递归的
? 数据结构是递归的
? 问题的解法是递归的
定义是递归的
求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
例如，阶乘函数
?
?
?
???
?
?
时当
时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 n! 的过程
主程序 main, fact(4)
参数 4 计算 4*fact(3) 返回 24
参数 3 计算 3*fact(2) 返回 6
参数 2 计算 2*fact(1) 返回 2
参数 1 计算 1*fact(0) 返回 1
参数 0 直接定值 = 1 返回 1
参
数
传
递
结
果
返
回
递
归
调
用
回
归
求
值
数据结构是递归的
? 一个结点，它的指针域为 NULL，是
一个单链表 ;
? 一个结点，它的指针域指向单链表，
仍是一个单链表。
例如，单链表结构
f ?
f ?
搜索链表最后一个结点并打印其数值
void Print ( ListNode *f ) {
if ( f ->link == NULL )
printf (“%d\n”,f ->data );
else Print ( f ->link );
}
f
f f f f
?a0 a1 a2 a3 a4
递归找链尾
在链表中寻找等于给定值的结点并打印
其数值
void Print ( ListNode *f,ListData& x ) {
if ( f != NULL )
if ( f -> data == x )
printf (“%d\n”,f ->data );
else Print ( f -> link,x );
}
f
f f f
?
递归找含 x值的结点
x
问题的解法是递归的
例如，汉诺塔 (Tower of Hanoi)问题的解法：
如果 n = 1,则将这一个盘子直接从 A 柱
移到 C 柱上 。 否则, 执行以下三步：
① 用 C 柱做过渡, 将 A 柱上的 (n-1) 个
盘子移到 B 柱上：
② 将 A 柱上最后一个盘子直接移到 C 柱
上；
③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个
盘子移到 C 柱上。
#include <iostream.h>
#include"strclass.h”
void Hanoi (int n,String A,String B,String C) {
//解决汉诺塔问题的算法
if ( n == 1 ) printf (" move %s",A," to %s,C);
else { Hanoi ( n-1,A,C,B );
printf (" move %s",A," to %s,C);
Hanoi ( n-1,B,A,C );
}
}
自顶向下、逐步分解的策略
? 子问题应与原问题做同样的事情，且更
为简单；
? 解决递归问题的策略是把一个规模比较
大的问题分解为一个或若干规模比较小
的问题，分别对这些比较小的问题求解，
再综合它们的结果，从而得到原问题的
解。 — 分而治之策略（分治法）
? 这些比较小的问题的求解方法与原来问
题的求解方法一样。
构成递归的条件
? 不能无限制地调用本身，必须有一个出口，
化简为非递归状况直接处理。
Procedure <name> ( <parameter list> ) {
if ( < initial condition> )
return ( initial value );
else
return (<name> ( parameter exchange ));
}
递归过程与递归工作栈
? 递归过程在实现时，需要自己调用自己。
? 层层向下递归，退出时的次序正好相反：
递归调用
n! (n-1)! (n-2)! 1! 0!=1
返回次序
? 主程序第一次调用递归过程为 外部调用 ；
? 递归过程每次递归调用自己为 内部调用 。
? 它们 返回 调用它的过程的 地址 不同。
递归工作栈
? 每一次递归调用时，需要为过程中使用
的参数、局部变量等另外分配存储空间。
? 每层递归调用需分配的空间形成递归工
作记录，按后进先出的栈组织。
局部变量
返回地址
参 数
活动
记录
框架
递归
工作记录
函数递归时的活动记录
……………….
<下一条指令 >
Function(<参数表 >)
……………….
<return>
调用块
函数块
返回地址 (下一条指令 ) 局部变量 参数
long Factorial ( long n ) {
int temp;
if ( n == 0 ) return 1;
else temp = n * Factorial (n-1);
RetLoc2
return temp;
}
void main ( ) {
int n;
n = Factorial (4);
RetLoc1
}
计算 Fact时活动记录的内容
递
归
调
用
序
列
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
参数 返回地址 返回时的指令
RetLoc1 return 4*6 //返回 24
RetLoc2 return 3*2 //返回 6
RetLoc2 return 1 //返回 1
RetLoc2 return 1*1 //返回 1
RetLoc2 return 2*1 //返回 2
递归过程改为非递归过程
? 递归过程简洁、易编、易懂
? 递归过程 效率低,重复计算多
? 改为非递归过程的目的是 提高效率
? 单向递归 和 尾递归 可直接用 迭代 实
现其非递归过程
? 其他情形必须借助 栈 实现非递归过
程
计算斐波那契数列的函数 Fib(n)的定义
求解斐波那契数列的递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
?
?
?
????
?
?
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
调用次数 NumCall(k) = 2*Fib(k+1) - 1。
斐波那契数列的递归调用树
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(4)
Fib(1) Fib(0)
Fib(2)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(5)
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
栈结点 n tag
tag = 1,向左递归； tag = 2,向右递归
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2? ? ? ?
4 1
n=1
sum=1+1
4 2
? n=4-2??
?
?
?
?
?
?
?
?
?
? ?
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
2 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
?
? ? ?
?
?
? ?
long Fibnacci ( long n ) {
Stack<Node> S; Node *w; long sum = 0;
//反复执行直到所有终端结点数据累加完
do {
while ( n > 1 ) {
w->n = n; w->tag = 1; S.push ( w );
n--;
}
//向左递归到底,边走边进栈
sum = sum + n; //执行求和
while ( !S.IsEmpty( ) ) {
w = S.getTop( ); S.Pop( );
if ( w->tag == 1 ) { //改为向右递归
w->tag = 2; S.push ( w );
n = w->n – 2; //F(n)右侧为 F(n-2)
break;
}
}
} while ( !S.IsEmpty( ) );
return sum;
}
单向递归用迭代法实现
long FibIter ( long n ) {
if ( n <= 1 ) return n;
long twoback = 0,oneback = 1,Current;
for ( int i = 2; i <= n; i++ ) {
Current = twoback + oneback;
twoback = oneback; oneback = Current;
}
return Current;
}
void recfunc ( int A[ ],int n ) {
if ( n >= 0 ) {
printf (“%d”,A[n] );
n--;
recfunc ( A,n );
}
}
25 36 72 18 99 49 54 63
尾递归用迭代法实现
void sterfunc ( int A[ ],int n ) {
//消除了尾递归的非递归函数
while ( n >= 0 ) {
printf ( "value %s,,A[n] );
n--;
}
}
递归与回溯 常用于搜索过程
n皇后问题
在 n 行 n 列的 国际象棋棋盘上，
若 两个皇后 位于 同一行, 同一列,
同一对角线 上，则称为它们为 互相
攻击 。 n皇后问题是指 找到这 n 个
皇后的互不攻击的布局 。
1#主对角线
3#主对角线
5#主对角线
?
?
?
0#次对角线
2#次对角线
4#次对角线
6#次对角线
1#次对角线
3#次对角线
5#次对角线
0#主对角线
2#主对角线
4#主对角线
6#主对角线
?
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
解题思路
? 安放 第 i 行 皇后时，需要在列的方向从 0
到 n-1 试探 ( j = 0,…,n -1 )
? 在 第 j 列 安放一个皇后：
? 如果在 列, 主对角线, 次对角线 方向
有其它皇后，则出现攻击，撤消在 第 j
列 安放的皇后。
? 如果没有出现攻击，在 第 j 列 安放的
皇后不动，递归安放第 i+1行皇后。
? 设置 4 个数组
? col [n], col[i] 标识第 i 列是否安放
了皇后
? md[2n-1], md[k] 标识第 k 条主对
角线是否安放了皇后
? sd[2n-1], sd[k] 标识第 k 条次对角
线是否安放了皇后
? q[n], q[i] 记录第 i 行皇后在第几列
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( 第 i 行第 j 列没有攻击 ) {
在 第 i 行第 j 列安放皇后 ；
if ( i == n-1 ) 输出一个布局 ；
else Queen ( i+1 );
撤消 第 i 行第 j 列的皇后 ；
}
}
}
算法求精
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( !col[j] && !md[n+i-j-1] && !sd[i+j] )
{
/*第 i 行第 j 列没有攻击 */
col[j] = md[n+i-j-1] = sd[i+j] = 1;
q[i] = j;
/*在 第 i 行第 j 列安放皇后 */
if ( i == n-1 ) { /*输出一个布局 */
for ( int k = 0; k < n; k++ )
cout << q[k] << ‘,’;
cout << endl;
}
else Queen ( i+1 );
col[j] = md[n+i-j-1] = sd[i+j] = 0;
q[i] = 0; /*撤消 第 i 行第 j 列的皇后 */
}
}
}
