第三章 栈和队列栈和队列是两种特殊的线性表，是 操作受限 的线性表，称限定性 DS
§ 3.1 栈（ stack）
栈的定义和特点
定义：限定仅在 表尾 进行插入或删除操作的线性表，
表尾 — 栈顶,表头 — 栈底,不含元素的空表称空栈
特点：先进后出（ FILO） 或后进先出（ LIFO）
an
a1
a2
……...
栈底栈顶
..,出栈进栈栈 s=(a1,a2,……,an)
栈的存储结构
顺序栈
实现：一维数组 s[M]
top=0
1
2
3
4
5
0
栈空栈顶指针 top,指向实际栈顶后的空位置，初值为 0
top 1
2
3
4
5
0
进栈
A
top
出栈栈满
B
C
D
E
F
设数组维数为 M
top=0,栈空，此时出栈，则 下溢 （ underflow)
top=M,栈满，此时入栈，则 上溢 （ overflow)
top
top
top
top
top
1
2
3
4
5
0A
B
C
D
E
Ftop
top
top
top
top
top
栈空
入栈算法
0 M-1
栈 1底 栈 1顶 栈 2底栈 2顶
出栈算法
在一个程序中同时使用两个栈
链栈栈顶
^…...top data link
栈底
结点定义
入栈算法
出栈算法
typedef struct node
{ int data;
struct node *link;
}JD;
^…...
栈底
toptop
xp
top
^…...
栈底
top
q
栈的应用
过程的嵌套调用
r
主程序
s
rr
r
s
子过程
1 r
s
t
子过程
2 rs
t 子过程
3
例 递归的执行情况分析
递归过程及其实现
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
}
Ch3_10.c
运行结果：
1，
2,2，
3,3,3，
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
(2) 2
(1) 3
输出：
(3) 1
(2) 2
(1) 3
top
(1 ) 3
返回
(3)
(2)
(1) 3
top (4)
结束
Tower of Hanoi问题
问题描述：有 A,B,C三个塔座,A上套有 n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号 1,2,3…… n。 要求将 n个圆盘从 A移到 C,叠放顺序不变，移动过程中遵循下列原则：
每次只能移一个圆盘
圆盘可在三个塔座上任意移动
任何时刻，每个塔座上不能将大盘压到小盘上
解决方法：
n=1时，直接把圆盘从 A移到 C
n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从 A
移到 C,再将 n-1个盘从 B移到 C。 即把求解 n个圆盘的
Hanoi问题转化为求解 n-1个圆盘的 Hanoi问题，依次类推，直至转化成只有一个圆盘的 Hanoi问题
算法：
执行情况：
递归工作栈保存内容：形参 n,x,y,z和返回地址
返回地址用行编号表示 n x y z 返回地址
main()
{ int m;
printf("Input number of disks”);
scanf("%d",&m);
printf(”Steps,%3d disks”,m);
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
12
3
3 A B C 0
3 A B C 0
2 A C B 6
3 A B C 0
2 A C B 6
1 A B C 6
A B C
3 A B C 0
2 A C B 6
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 A C B 6
1 C A B 8
A B C
3 A B C 0
2 A C B 6
3 A B C 0
3 A B C 0
2 A C B 6
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
3 A B C 0
2 B A C 8
1 B C A 6
A B C
3 A B C 0
2 B A C 8
3 A B C 0
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
1 A B C 8
A B C
3 A B C 0
2 B A C 8
3 A B C 0
栈空
3 A B C 0
2 B A C 8
Hanoi.c D:\fengyi\bkc\power\power.c
回文游戏：顺读与逆读字符串一样（不含空格）
d
a
d top 1.读入字符串2.去掉空格（原串）
3.压入栈
4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文
多进制输出：
字符串：,madam im adam”
例 把十进制数 159转换成八进制数
(159)10=(237)8
1598
198
28
0 2 3 7
余 7
余 3
余 2 top
top
7
top
7
3
top
7
3
2
表达式求值中缀表达式 后缀表达式 （ RPN)
a*b+c ab*c+
a+b*c abc*+
a+(b*c+d)/e abc*d+e/+
中缀表达式：操作数栈和运算符栈例 计算 2+4-3*6
操作数 运算符
2
4
+
操作数 运算符
6 -
操作数 运算符
6 -
3
6
*
操作数 运算符
6 -
18
操作数 运算符
12
后缀表达式求值步骤：
1、读入表达式一个字符
2、若是操作数，压入栈，转 4
3、若是运算符，从栈中弹出 2个数，将运算结果再压入栈
4、若表达式输入完毕，栈顶即表达式值；
若表达式未输入完，转 1
top
4
top
4
3
top
7
3
5
top
例 计算 4+3*5 后缀表达式,435*+
top
4
15 top
19
(1)(2)
(4)
(5)
(6)
(7)
(3)
地图四染色问题
R [ 7][ 7 ]
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 0 0 0 0 1 0
0 1 1 1 1 1 0
1 0 1 0 1 1 0
1 0 1 1 0 1 0
1 1 0 1 1 0 0
1 0 0 1 1 0 0
0 0 0 0 0 0 0
1 2 3 4 5 6 7
1 2 2 3 4 14 33 2 3
1# 紫色
2# 黄色
3# 红色
4# 绿色
§ 3.2 队列
队列的定义及特点
定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表
队尾 (rear)—— 允许插入的一端
队头 (front)—— 允许删除的一端
队列特点：先进先出 (FIFO)
a1 a2 a3…………………….an 入队出队
front rear
队列 Q=(a1,a2,……,an)
双端队列
a1 a2 a3…………………….an
端 1 端 2
入队出队入队出队
链队列
结点定义 typedef struct node
{ int data;
struct node *link;
}JD;
头结点
^…...front
队头 队尾
rear
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
入队算法
出队算法
队列的顺序存储结构
实现：用一维数组实现 sq[M]
front=-1
rear=-1
1
2
3
4
5
0
队空
1
2
3
4
5
0
front J1,J1,J3入队
J1
J2
J3rear
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
设两个指针 front,rear,约定：
rear指示队尾元素；
front指示队头元素前一位置初值 front=rear=-1
空队列条件,front==rear
入队列,sq[++rear]=x;
出队列,x=sq[++front];
rear
rear
front
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
front
front
front
存在问题设数组维数为 M,则：
当 front=-1,rear=M-1时，再有元素入队发生溢出 —— 真溢出
当 front?-1,rear=M-1时，再有元素入队发生溢出 —— 假溢出
解决方案
队首固定，每次出队剩余元素向下移动 —— 浪费时间
循环队列
基本思想：把队列 设想成环形,让 sq[0]接在 sq[M-1]之后，
若 rear+1==M,则令 rear=0;
0
M-1
1
front
rear
实现：利用“模”运算
入队,rear=(rear+1)%M; sq[rear]=x;
出队,front=(front+1)%M; x=sq[front];
队满、队空判定条件
0
123
4 5
rear
front
J4
J5
J6
0
123
4 5
rear
front
J9
J8
J7
J4
J5
J6
0
123
4 5
rear
front
初始状态队空,front==rear
队满,front==rear
解决方案：
1.另外 设一个标志 以区别队空、队满
2.少用一个元素空间,
队空,front==rear
队满,(rear+1)%M==front
入队算法：
出队算法：
队列应用举例划分子集问题
问题描述：已知集合 A={a1,a2,……an},及集合上的关系 R={ (ai,aj) | ai,aj?A,i?j},其中 (ai,aj)表示 ai与 aj间存在冲突关系。要求将 A划分成 互不相交 的子集
A1,A2,……Ak,(k?n),使任何子集中的元素均无冲突关系，同时要求 分子集个数尽可能少例 A={1,2,3,4,5,6,7,8,9}
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
算法思想：利用 循环筛选 。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组
所用数据结构
冲突关系矩阵
r[i][j]=1,i,j有冲突
r[i][j]=0,i,j无冲突
循环队列 cq[n]
数组 result[n]存放每个元素分组号
工作数组 newr[n]
工作过程
初始状态,A中元素放于 cq中,result和 newr数组清零，组号
group=1
第一个元素出队，将 r矩阵中第一行,1”拷入 newr中对应位置，这样，凡与第一个元素有冲突的元素在 newr中对应位置处均为,1”,下一个元素出队
若其在 newr中对应位置为,1”，有冲突，重新插入 cq
队尾，参加下一次分组
若其在 newr中对应位置为,0”,无冲突，可划归本组；
再将 r矩阵中该元素对应行中的,1”拷入 newr中
如此反复，直到 9个元素依次出队，由 newr中为,0”的单元对应的元素构成第 1组,将组号 group值,1”写入 result对应单元中
令 group=2,newr清零，对 cq中元素重复上述操作，直到 cq中
front==rear,即队空，运算结束
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
初始
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 1 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 1 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
5 6 7 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
6 7 9 5
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
7 9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
5 6 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
6 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 6
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 6
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 1 0 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
0 1 2 3 4 5 6 7 8
cq
f r
0 1 1 1 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 4
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
Ch3_9.c
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
优先级队列
离散时间模拟
图的广度优先遍历
基数排序
§ 3.1 栈（ stack）
栈的定义和特点
定义：限定仅在 表尾 进行插入或删除操作的线性表，
表尾 — 栈顶,表头 — 栈底,不含元素的空表称空栈
特点：先进后出（ FILO） 或后进先出（ LIFO）
an
a1
a2
……...
栈底栈顶
..,出栈进栈栈 s=(a1,a2,……,an)
栈的存储结构
顺序栈
实现：一维数组 s[M]
top=0
1
2
3
4
5
0
栈空栈顶指针 top,指向实际栈顶后的空位置，初值为 0
top 1
2
3
4
5
0
进栈
A
top
出栈栈满
B
C
D
E
F
设数组维数为 M
top=0,栈空，此时出栈，则 下溢 （ underflow)
top=M,栈满，此时入栈，则 上溢 （ overflow)
top
top
top
top
top
1
2
3
4
5
0A
B
C
D
E
Ftop
top
top
top
top
top
栈空
入栈算法
0 M-1
栈 1底 栈 1顶 栈 2底栈 2顶
出栈算法
在一个程序中同时使用两个栈
链栈栈顶
^…...top data link
栈底
结点定义
入栈算法
出栈算法
typedef struct node
{ int data;
struct node *link;
}JD;
^…...
栈底
toptop
xp
top
^…...
栈底
top
q
栈的应用
过程的嵌套调用
r
主程序
s
rr
r
s
子过程
1 r
s
t
子过程
2 rs
t 子过程
3
例 递归的执行情况分析
递归过程及其实现
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
}
Ch3_10.c
运行结果：
1，
2,2，
3,3,3，
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
(2) 2
(1) 3
输出：
(3) 1
(2) 2
(1) 3
top
(1 ) 3
返回
(3)
(2)
(1) 3
top (4)
结束
Tower of Hanoi问题
问题描述：有 A,B,C三个塔座,A上套有 n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号 1,2,3…… n。 要求将 n个圆盘从 A移到 C,叠放顺序不变，移动过程中遵循下列原则：
每次只能移一个圆盘
圆盘可在三个塔座上任意移动
任何时刻，每个塔座上不能将大盘压到小盘上
解决方法：
n=1时，直接把圆盘从 A移到 C
n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从 A
移到 C,再将 n-1个盘从 B移到 C。 即把求解 n个圆盘的
Hanoi问题转化为求解 n-1个圆盘的 Hanoi问题，依次类推，直至转化成只有一个圆盘的 Hanoi问题
算法：
执行情况：
递归工作栈保存内容：形参 n,x,y,z和返回地址
返回地址用行编号表示 n x y z 返回地址
main()
{ int m;
printf("Input number of disks”);
scanf("%d",&m);
printf(”Steps,%3d disks”,m);
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
12
3
3 A B C 0
3 A B C 0
2 A C B 6
3 A B C 0
2 A C B 6
1 A B C 6
A B C
3 A B C 0
2 A C B 6
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 A C B 6
1 C A B 8
A B C
3 A B C 0
2 A C B 6
3 A B C 0
3 A B C 0
2 A C B 6
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
3 A B C 0
2 B A C 8
1 B C A 6
A B C
3 A B C 0
2 B A C 8
3 A B C 0
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
1 A B C 8
A B C
3 A B C 0
2 B A C 8
3 A B C 0
栈空
3 A B C 0
2 B A C 8
Hanoi.c D:\fengyi\bkc\power\power.c
回文游戏：顺读与逆读字符串一样（不含空格）
d
a
d top 1.读入字符串2.去掉空格（原串）
3.压入栈
4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文
多进制输出：
字符串：,madam im adam”
例 把十进制数 159转换成八进制数
(159)10=(237)8
1598
198
28
0 2 3 7
余 7
余 3
余 2 top
top
7
top
7
3
top
7
3
2
表达式求值中缀表达式 后缀表达式 （ RPN)
a*b+c ab*c+
a+b*c abc*+
a+(b*c+d)/e abc*d+e/+
中缀表达式：操作数栈和运算符栈例 计算 2+4-3*6
操作数 运算符
2
4
+
操作数 运算符
6 -
操作数 运算符
6 -
3
6
*
操作数 运算符
6 -
18
操作数 运算符
12
后缀表达式求值步骤：
1、读入表达式一个字符
2、若是操作数，压入栈，转 4
3、若是运算符，从栈中弹出 2个数，将运算结果再压入栈
4、若表达式输入完毕，栈顶即表达式值；
若表达式未输入完，转 1
top
4
top
4
3
top
7
3
5
top
例 计算 4+3*5 后缀表达式,435*+
top
4
15 top
19
(1)(2)
(4)
(5)
(6)
(7)
(3)
地图四染色问题
R [ 7][ 7 ]
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 0 0 0 0 1 0
0 1 1 1 1 1 0
1 0 1 0 1 1 0
1 0 1 1 0 1 0
1 1 0 1 1 0 0
1 0 0 1 1 0 0
0 0 0 0 0 0 0
1 2 3 4 5 6 7
1 2 2 3 4 14 33 2 3
1# 紫色
2# 黄色
3# 红色
4# 绿色
§ 3.2 队列
队列的定义及特点
定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表
队尾 (rear)—— 允许插入的一端
队头 (front)—— 允许删除的一端
队列特点：先进先出 (FIFO)
a1 a2 a3…………………….an 入队出队
front rear
队列 Q=(a1,a2,……,an)
双端队列
a1 a2 a3…………………….an
端 1 端 2
入队出队入队出队
链队列
结点定义 typedef struct node
{ int data;
struct node *link;
}JD;
头结点
^…...front
队头 队尾
rear
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
入队算法
出队算法
队列的顺序存储结构
实现：用一维数组实现 sq[M]
front=-1
rear=-1
1
2
3
4
5
0
队空
1
2
3
4
5
0
front J1,J1,J3入队
J1
J2
J3rear
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
设两个指针 front,rear,约定：
rear指示队尾元素；
front指示队头元素前一位置初值 front=rear=-1
空队列条件,front==rear
入队列,sq[++rear]=x;
出队列,x=sq[++front];
rear
rear
front
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
front
front
front
存在问题设数组维数为 M,则：
当 front=-1,rear=M-1时，再有元素入队发生溢出 —— 真溢出
当 front?-1,rear=M-1时，再有元素入队发生溢出 —— 假溢出
解决方案
队首固定，每次出队剩余元素向下移动 —— 浪费时间
循环队列
基本思想：把队列 设想成环形,让 sq[0]接在 sq[M-1]之后，
若 rear+1==M,则令 rear=0;
0
M-1
1
front
rear
实现：利用“模”运算
入队,rear=(rear+1)%M; sq[rear]=x;
出队,front=(front+1)%M; x=sq[front];
队满、队空判定条件
0
123
4 5
rear
front
J4
J5
J6
0
123
4 5
rear
front
J9
J8
J7
J4
J5
J6
0
123
4 5
rear
front
初始状态队空,front==rear
队满,front==rear
解决方案：
1.另外 设一个标志 以区别队空、队满
2.少用一个元素空间,
队空,front==rear
队满,(rear+1)%M==front
入队算法：
出队算法：
队列应用举例划分子集问题
问题描述：已知集合 A={a1,a2,……an},及集合上的关系 R={ (ai,aj) | ai,aj?A,i?j},其中 (ai,aj)表示 ai与 aj间存在冲突关系。要求将 A划分成 互不相交 的子集
A1,A2,……Ak,(k?n),使任何子集中的元素均无冲突关系，同时要求 分子集个数尽可能少例 A={1,2,3,4,5,6,7,8,9}
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
算法思想：利用 循环筛选 。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组
所用数据结构
冲突关系矩阵
r[i][j]=1,i,j有冲突
r[i][j]=0,i,j无冲突
循环队列 cq[n]
数组 result[n]存放每个元素分组号
工作数组 newr[n]
工作过程
初始状态,A中元素放于 cq中,result和 newr数组清零，组号
group=1
第一个元素出队，将 r矩阵中第一行,1”拷入 newr中对应位置，这样，凡与第一个元素有冲突的元素在 newr中对应位置处均为,1”,下一个元素出队
若其在 newr中对应位置为,1”，有冲突，重新插入 cq
队尾，参加下一次分组
若其在 newr中对应位置为,0”,无冲突，可划归本组；
再将 r矩阵中该元素对应行中的,1”拷入 newr中
如此反复，直到 9个元素依次出队，由 newr中为,0”的单元对应的元素构成第 1组,将组号 group值,1”写入 result对应单元中
令 group=2,newr清零，对 cq中元素重复上述操作，直到 cq中
front==rear,即队空，运算结束
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
初始
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 1 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 1 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
5 6 7 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
6 7 9 5
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
7 9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
5 6 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
6 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 6
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 6
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 1 0 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 0
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
算法描述
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
0 1 2 3 4 5 6 7 8
cq
f r
0 1 1 1 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 4
0 1 2 3 4 5 6 7 8
result
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),
(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
Ch3_9.c
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
优先级队列
离散时间模拟
图的广度优先遍历
基数排序
