,数据结构,
第三章（下）
数据结构
tjm
3.3 栈与递归的实现
A ( ) {
…
A( ) ;
…
}
B( ) { C( ) {
… …
C( ); B( );
… …
} }
A 直接调用自己 B间接调用自己
概念：一个直接调用自己或通过一系列调用语句
间接地调用自己的函数称为递归函数。
数据结构
tjm
以下三种情况常常用到递归方法,
定义是递归的
数据结构是递归的
问题的解法是递归的
递归算法的编写：
1） 将问题用递归的方式描述 。
2） 根据问题的递归描述编写递归算法 。
递归描述包括两项：
基本项 （ 终止项 ）,描述递归终止时问题的求解 。
递归项：将问题分解为与原问题性质相同但规模较
小的问题 。
数据结构
tjm
定义是递归的
求解阶乘函数的递归算法：
long Factorial ( long n )
{
if ( n == 0 ) return 1;
else return n*Factorial (n-1);
}
【 例 1】 阶乘函数
?
?
?
???
?
?
时当
时当
1,)!1(
0,1
!
n
n
nn
n
数据结构
tjm
求解 n! 的过程
数据结构
tjm
【 例 2】 计算斐波那契数列的函数 Fib(n)
?
?
?
????
?
?
1),2()1(
0,1,
)(
nnF i bnF i b
nn
nF i b
long Fib ( long n )
{
if ( n <= 1 )
return n;
else
return Fib (n-1) + Fib (n-2);
}
数据结构
tjm
【 例 3】 求数组 A 中 n 个整数的和
int sum ( int n )
{
if ( n == 1 )
result = A[0];
else
result = A[n-1] + sum(n-1);
return result;
}
数据结构是递归的
数据结构
tjm
搜索链表最后一个结点并打印其数值
void Find ( LNode *f )
{
if ( f → next == NULL )
printf(,%d \n”,f → data );
else Find ( f → next);
}
【 例 4】 单链表结构
数据结构
tjm
问题的解法是递归的
【 例 5】 汉诺塔问题
问题描述：有 A,B,C三个塔座,A上套有 n个直径
不同的圆盘，按直径从小到大叠放，形如宝塔,编
号 1,2,3……n。 要求将 n个圆盘从 A移到 C,叠
放顺序不变，移动过程中遵循下列原则：
每次只能移一个圆盘
圆盘可在三个塔座上任意移动
任何时刻，每个塔座上不能将大盘压到小盘上
数据结构
tjm
解决方法：
n=1时，直接把圆盘从 A移到 C。
n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从 A
移到 C,再将 n-1个盘从 B移到 C。 即把求解 n个圆盘的
Hanoi问题转化为求解 n-1个圆盘的 Hanoi问题，依 此 类
推，直至转化成只有一个圆盘的 Hanoi问题。
数据结构
tjm
递归工作栈保存内容：
返回地址 n x y z
返回地址用行编号表示
参见 P55算法
执行情况：
每层递归调用需分配的空间形成递归工作记录，
按后进先出的 栈 组织 。 递归工作栈保存内容：
数据结构
tjm
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
0 1
数据结构
tjm
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b)
2
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
0 1
数据结构
tjm
3
move(a,1,c)
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b)
0 1 2
move(c,1,b)
数据结构
tjm
30 1 2
move(a,1,c)
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b) move(c,1,b)
Hanoi(1,b,c,a)
move(b,2,c)
Hanoi(1,a,b,c)
数据结构
tjm
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b)
Hanoi(1,b,c,a)
move(b,2,c)
Hanoi(1,a,b,c)
0 1 2 3
move(a,1,c)
move(c,1,b)
move(b,1,a)
move(a,1,c)
数据结构
tjm
move(a,2,b)
Hanoi(1,c,a,b)
Hanoi(3,a,b,c)
3
2
1
a b c
Hanoi(2,a,c,b)
3
a b c
2
1
Hanoi(1,a,b,c)
3
a b c
1
2
23 1
a b c
3
a b c
2
1
数据结构
tjm
32
1
a b c
3
2
1
a b c
move (a,3,c)
Hanoi(2,b,a,c)
321
a b c
Hanoi(1,b,c,a)
3
2
1
a b c
move(b,2,c)
3
2
1
a b c
Hanoi(1,a,b,c)
数据结构
tjm
3.4 队列
3.4.1 抽象数据类型队列的定义
队列 (Queue)也是 一种运算受限的线性表 。它只
允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为 队头 (front),允许插入的一
端称为 队尾 (rear)。
例如,排队购物、操作系统中的作业排队。先进入
队列的成员总是先离开队列。因此队列亦称作 先进
先出 (First In First Out)的线性表, 简称 FIFO
表。
数据结构
tjm
q.front q.rear
x入 队 ^x
q.front q.rear
y入 队 x ^y
q.front q.rear
x出 队 x ^y
q.front q.rear
空队 ^
q.frontq.rear
y出 队 ^ 在链队列上实现的基本运算：1、入队列 (P62)
2、出队列 (P62)
数据结构
tjm
3.4.3 循环队列－队列的顺序表示和实现
队列的顺序存储结构称为顺序队列。
在非空队列里，头指针始终指向队头元素，而尾指
针始终指向队尾元素的下一位置。由此可见，当头
尾指针相等时队列为空。
０ １ ２ ３ 0 1 2 3
q.front
q.rear
a b c
q.front q.rear
(a)队列初始为空 （ b） A,B,C入队
数据结构
tjm
０ １ ２ ３ ０ １ ２ ３
b c
q.front q,rear q.front
q.rear
（ c) a出队 (d) b,c出队，队为空
入队时 将新元素插入尾指针所指的位置，然后将 尾
指针加１。出队时,删去头指针所指的元素，然后
将 头指针加１ 并返回被删元素。
队列中也有 上溢和下溢现象 。此外，顺序队列中还
存在,假上溢” 现象。
数据结构
tjm
克服假上溢现象的方法：
将一维数组空间想象为一个 首尾相接的圆环,存储
在其中的队列称为 循环队列 。在循环队列中进行出
队、入队操作时，头尾指针仍要加 1。只不过当头
尾指针指向数组上界（ MAXQSIZE-1）时，其加
1操作的结果是指向数组的下界 0。
循环队列的类型定义：
#define MAXQSIZE 100
typedef struct{
QElemType *base;
int front;
int rear;
}SqQueue;
数据结构
tjm
[0]
[2]
[M-1] [0]
[1]
[2]
[M-1]
初始状态
q.front=q.rear=0
A
B
C
D
入队列：
q.base[q.rear]=e
q.rear=q.rear+1
front front rear
rear
[1]
数据结构
tjm
[0]
[1]
[2]
[M-1]
A
B
[0]
[1]
[2]
[M-1]
A
B
C
D
出队列：
e=q.base[q.front]
q.front=q.front+1
c
front
front
rear
rear
D
数据结构
tjm
[0]
[1]
[2]
[M-1]
B
BB
B
B
B
rear
front
q.rear==MAXQSIZE-1时,再添加元素,则
q.rear+1 > 数组的最大下标,这种循环意义下
的加 1操作可以描述为：
if(q.rear+1==MAXQSIZE) q.rear=0;
else q.rear++;
利用模运算可简化为：
q.rear=(q.rear+1)% MAXQSIZE
数据结构
tjm
故，入队列为：
q.base[q.rear]=e；
q.rear=(q.rear+1)% MAXQSIZE；
出队列为：
e=q.base[q.front]；
q.front=(q.front+1)% MAXQSIZE ；
数据结构
tjm
[0]
[1]
[2]
[M-1]
B
[0]
[1]
[2]
[M-1]
B
B
BB
B
BB
B
B
队列满 队列空
rear
front
rear
front
如图所示,队空和队满时头尾指针均相等 。无法通
过 q.front==q.rear来判断队列“空”还是
“满”。
数据结构
tjm
解决此问题的方法如：
1、另设一个布尔变量以匹别队列的空和满；
2、使用一个计数器记录队列中元素的总数（实际
上是队列长度） 。
3、少用一个元素的空间，约定入队前，测试尾指
针在循环意义下加 1后是否等于头指针，若相等
则认为队满，即
(q.rear+1)%MAXQSIZE==q.front
（注意,rear所指的单元始终为空）；（见书
P64-65算法）
第三章（下）
数据结构
tjm
3.3 栈与递归的实现
A ( ) {
…
A( ) ;
…
}
B( ) { C( ) {
… …
C( ); B( );
… …
} }
A 直接调用自己 B间接调用自己
概念：一个直接调用自己或通过一系列调用语句
间接地调用自己的函数称为递归函数。
数据结构
tjm
以下三种情况常常用到递归方法,
定义是递归的
数据结构是递归的
问题的解法是递归的
递归算法的编写：
1） 将问题用递归的方式描述 。
2） 根据问题的递归描述编写递归算法 。
递归描述包括两项：
基本项 （ 终止项 ）,描述递归终止时问题的求解 。
递归项：将问题分解为与原问题性质相同但规模较
小的问题 。
数据结构
tjm
定义是递归的
求解阶乘函数的递归算法：
long Factorial ( long n )
{
if ( n == 0 ) return 1;
else return n*Factorial (n-1);
}
【 例 1】 阶乘函数
?
?
?
???
?
?
时当
时当
1,)!1(
0,1
!
n
n
nn
n
数据结构
tjm
求解 n! 的过程
数据结构
tjm
【 例 2】 计算斐波那契数列的函数 Fib(n)
?
?
?
????
?
?
1),2()1(
0,1,
)(
nnF i bnF i b
nn
nF i b
long Fib ( long n )
{
if ( n <= 1 )
return n;
else
return Fib (n-1) + Fib (n-2);
}
数据结构
tjm
【 例 3】 求数组 A 中 n 个整数的和
int sum ( int n )
{
if ( n == 1 )
result = A[0];
else
result = A[n-1] + sum(n-1);
return result;
}
数据结构是递归的
数据结构
tjm
搜索链表最后一个结点并打印其数值
void Find ( LNode *f )
{
if ( f → next == NULL )
printf(,%d \n”,f → data );
else Find ( f → next);
}
【 例 4】 单链表结构
数据结构
tjm
问题的解法是递归的
【 例 5】 汉诺塔问题
问题描述：有 A,B,C三个塔座,A上套有 n个直径
不同的圆盘，按直径从小到大叠放，形如宝塔,编
号 1,2,3……n。 要求将 n个圆盘从 A移到 C,叠
放顺序不变，移动过程中遵循下列原则：
每次只能移一个圆盘
圆盘可在三个塔座上任意移动
任何时刻，每个塔座上不能将大盘压到小盘上
数据结构
tjm
解决方法：
n=1时，直接把圆盘从 A移到 C。
n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从 A
移到 C,再将 n-1个盘从 B移到 C。 即把求解 n个圆盘的
Hanoi问题转化为求解 n-1个圆盘的 Hanoi问题，依 此 类
推，直至转化成只有一个圆盘的 Hanoi问题。
数据结构
tjm
递归工作栈保存内容：
返回地址 n x y z
返回地址用行编号表示
参见 P55算法
执行情况：
每层递归调用需分配的空间形成递归工作记录，
按后进先出的 栈 组织 。 递归工作栈保存内容：
数据结构
tjm
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
0 1
数据结构
tjm
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b)
2
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
0 1
数据结构
tjm
3
move(a,1,c)
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b)
0 1 2
move(c,1,b)
数据结构
tjm
30 1 2
move(a,1,c)
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b) move(c,1,b)
Hanoi(1,b,c,a)
move(b,2,c)
Hanoi(1,a,b,c)
数据结构
tjm
Hanoi(3,a,b,c)
Hanoi(2,a,c,b)
move (a,3,c)
Hanoi(2,b,a,c)
Hanoi(1,a,b,c)
move(a,2,b)
Hanoi(1,c,a,b)
Hanoi(1,b,c,a)
move(b,2,c)
Hanoi(1,a,b,c)
0 1 2 3
move(a,1,c)
move(c,1,b)
move(b,1,a)
move(a,1,c)
数据结构
tjm
move(a,2,b)
Hanoi(1,c,a,b)
Hanoi(3,a,b,c)
3
2
1
a b c
Hanoi(2,a,c,b)
3
a b c
2
1
Hanoi(1,a,b,c)
3
a b c
1
2
23 1
a b c
3
a b c
2
1
数据结构
tjm
32
1
a b c
3
2
1
a b c
move (a,3,c)
Hanoi(2,b,a,c)
321
a b c
Hanoi(1,b,c,a)
3
2
1
a b c
move(b,2,c)
3
2
1
a b c
Hanoi(1,a,b,c)
数据结构
tjm
3.4 队列
3.4.1 抽象数据类型队列的定义
队列 (Queue)也是 一种运算受限的线性表 。它只
允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为 队头 (front),允许插入的一
端称为 队尾 (rear)。
例如,排队购物、操作系统中的作业排队。先进入
队列的成员总是先离开队列。因此队列亦称作 先进
先出 (First In First Out)的线性表, 简称 FIFO
表。
数据结构
tjm
q.front q.rear
x入 队 ^x
q.front q.rear
y入 队 x ^y
q.front q.rear
x出 队 x ^y
q.front q.rear
空队 ^
q.frontq.rear
y出 队 ^ 在链队列上实现的基本运算：1、入队列 (P62)
2、出队列 (P62)
数据结构
tjm
3.4.3 循环队列－队列的顺序表示和实现
队列的顺序存储结构称为顺序队列。
在非空队列里，头指针始终指向队头元素，而尾指
针始终指向队尾元素的下一位置。由此可见，当头
尾指针相等时队列为空。
０ １ ２ ３ 0 1 2 3
q.front
q.rear
a b c
q.front q.rear
(a)队列初始为空 （ b） A,B,C入队
数据结构
tjm
０ １ ２ ３ ０ １ ２ ３
b c
q.front q,rear q.front
q.rear
（ c) a出队 (d) b,c出队，队为空
入队时 将新元素插入尾指针所指的位置，然后将 尾
指针加１。出队时,删去头指针所指的元素，然后
将 头指针加１ 并返回被删元素。
队列中也有 上溢和下溢现象 。此外，顺序队列中还
存在,假上溢” 现象。
数据结构
tjm
克服假上溢现象的方法：
将一维数组空间想象为一个 首尾相接的圆环,存储
在其中的队列称为 循环队列 。在循环队列中进行出
队、入队操作时，头尾指针仍要加 1。只不过当头
尾指针指向数组上界（ MAXQSIZE-1）时，其加
1操作的结果是指向数组的下界 0。
循环队列的类型定义：
#define MAXQSIZE 100
typedef struct{
QElemType *base;
int front;
int rear;
}SqQueue;
数据结构
tjm
[0]
[2]
[M-1] [0]
[1]
[2]
[M-1]
初始状态
q.front=q.rear=0
A
B
C
D
入队列：
q.base[q.rear]=e
q.rear=q.rear+1
front front rear
rear
[1]
数据结构
tjm
[0]
[1]
[2]
[M-1]
A
B
[0]
[1]
[2]
[M-1]
A
B
C
D
出队列：
e=q.base[q.front]
q.front=q.front+1
c
front
front
rear
rear
D
数据结构
tjm
[0]
[1]
[2]
[M-1]
B
BB
B
B
B
rear
front
q.rear==MAXQSIZE-1时,再添加元素,则
q.rear+1 > 数组的最大下标,这种循环意义下
的加 1操作可以描述为：
if(q.rear+1==MAXQSIZE) q.rear=0;
else q.rear++;
利用模运算可简化为：
q.rear=(q.rear+1)% MAXQSIZE
数据结构
tjm
故，入队列为：
q.base[q.rear]=e；
q.rear=(q.rear+1)% MAXQSIZE；
出队列为：
e=q.base[q.front]；
q.front=(q.front+1)% MAXQSIZE ；
数据结构
tjm
[0]
[1]
[2]
[M-1]
B
[0]
[1]
[2]
[M-1]
B
B
BB
B
BB
B
B
队列满 队列空
rear
front
rear
front
如图所示,队空和队满时头尾指针均相等 。无法通
过 q.front==q.rear来判断队列“空”还是
“满”。
数据结构
tjm
解决此问题的方法如：
1、另设一个布尔变量以匹别队列的空和满；
2、使用一个计数器记录队列中元素的总数（实际
上是队列长度） 。
3、少用一个元素的空间，约定入队前，测试尾指
针在循环意义下加 1后是否等于头指针，若相等
则认为队满，即
(q.rear+1)%MAXQSIZE==q.front
（注意,rear所指的单元始终为空）；（见书
P64-65算法）
