Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 1页第 4章 栈和队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 2页
4.1 栈
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 3页
4.1.1 栈的结构特点和操作
栈 (Stack)是限制在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶 (Top)，另一端为 栈底 (Bottom)。当表中没有元素时称为 空栈 。
假设栈 S=(a1,a2,a3,… an)，则 a1称为栈底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,… an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的 。因此,栈称为后进先出表
（ LIFO） 。
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 4页由栈的定义可以发现,栈有如下特点：
1,进,出都在同一端进行；
2,先进去的后出来 。
a1
a2
an-1
an
……
栈顶栈底
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 5页
4.1.2 栈的表示和操作的实现
顺序栈（参见程序 Stack.cpp)
链栈
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 6页
4.2 栈的应用举例
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 7页例 4.1 数制转换
十进制数 N和其他 d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
N = (N div d)× d + N mod d
(其中,div 为整除运算,mod 为求余运算）
例如：（ 1348)10 = (2504)8,其运算过程如下：
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 8页算法 4.1 数制转换问题
void conversion () {
// 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数
InitStack(S); // 构造空栈
cin>>N;
while (N) {
Push(S,N % 8); //,余数,入栈
N = N/8; //,商,继续运算
}//while
while (!StackEmpty) { // 和,求余,所得相逆的顺序输出八进制的各位数
Pop(S,e);
cout< <e；
}//while
} // conversion
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 9页例 4.2 括号匹配的检验
假设表达式中允许包含两种括号：圆括号和方括号，
其嵌套的顺序随意，即 ([ ］ ( ))或［ (［ ］［ ］ )］
等为正确的格式，［ ( ］ )或 (［ ( ) )或 (( )])均为不正确的格式。 检验括号是否匹配的方法可用 "期待的急迫程度 "这个概念来描述。 例如考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的不匹配的情况,
1,到来的右括弧 非是所,期待,的 ;
2,到来的是,不速之客,;
3,直到结束，也 没有到来所,期待,的。
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 10页栈和递归函数的关系
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
例 递归的执行情况分析
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
}
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 11页递归调用执行情况如下：
主程序
(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)
结束运行结果：
1，
2,2，
3,3,3，
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 12页
4.3 队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 13页
4.3.1 队列的结构特点和操作
队列 (queue)是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。
容许插入的一端称做 队尾（ rear）
容许删除的一端称为 队头（ front）
队列的特点：
先进先出（ Fisrt In First Out) FIFO
a1 a2 a3 ……… an
出队列 入队列队头 队尾
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 14页队列的抽象数据类型
ADT Queue {
数据对象,D={ai|ai∈ ElemSet，
i=1,2,……,n,n≥0}
数据关系,R1={< ai-1,ai >| ai-1,ai ∈ D,
i=1,2,……,n}
约定 a1为队头,an为队尾
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 15页基本操作：
InitQueue(&Q)
DestroyQueue(&Q)
ClearQueue(&Q)
QueueEmpty(Q)
GetHead(Q,&e)
EnQueue(&Q,e) //进队列
DeQueue(&Q,&e)} //出队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 16页
4.3.2 队列的表示和操作的实现
1、链队列
typedef struct QNode {
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 17页
a1
a2
an ^
Q.front
Q.rear
…...
队头队尾链队列示意图
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 18页
3.4.3 循环队列 -队列的顺序表示
J1
J2
J3 J3
J4
J55
4
3
2
1
0 Q.front
Q.rear
Q.rear
Q.front
Q.front
Q.rear
Q.rear
Q.front
普通队列的浪费了存储空间浪费的空间
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 19页循环队列示意图
….
….
0
1
maxsize-1
Q.rear
Q.front
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 20页
J5
J6
J7
J8
J9
J10
J4
J5
J7
J8
J9
J4
J55
4
3
2
1
0
Q.front
Q.rear
Q.rear
Q.front
Q.front
Q.rear
Q.rear
Q.front
循环队列
“满队列”空队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 21页循环队列中元素个数：
(Q.rear-Q.front+MAXSIZE)%MAXSIZE
循环队列是否满：
(Q.rear+1)%MAXSIZE==Q.front
循环队列是否空：
Q.rear==Q.front
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 22页队列应用举例（划分子集问题）
问题描述：
已知集合 A={a1,a2,……an},及集合上的关系
R={ (ai,aj) | ai,aj?A,i?j}，
其中 (ai,aj)表示 ai与 aj间存在冲突关系。
要求将 A划分成 互不相交 的子集 A1,A2,……Ak,(k?n)，
使任何子集中的元素均无冲突关系，同时要求 划 分子集个数尽可能少
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 23页例：
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 }
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 24页
算法思想：
利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组
所用数据结构
冲突关系矩阵
r[i][j]=1,i,j有冲突
r[i][j]=0,i,j无冲突
循环队列 cq[n]
数组 result[n]存放每个元素分组号
工作数组 clash[n]
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 25页
工作过程
初始状态,A中元素放于 cq中,result和 clash数组清零，组号
group=1
第一个元素出队，将 r矩阵中第一行,1”拷入 clash中对应位置，这样，凡与第一个元素有冲突的元素在 clash中对应位置处均为,1”,下一个元素出队
若其在 clash中对应位置为,1”，有冲突，重新插入 cq队尾，参加下一次分组
若其在 clash中对应位置为,0”,无冲突，可划归本组；再将 r矩阵中该元素对应行中的,1”拷入 clash中
如此反复，直到 9个元素依次出队，由 clash中为,0”的单元对应的元素构成第 1组,将组号 group值,1”写入 result对应单元中
令 group=2,clash清零，对 cq中元素重复上述操作，直到 cq中
front==rear,即队空，运算结束
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 26页
算法描述
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
初始
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 27页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 28页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 29页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 30页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 31页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 32页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 33页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 34页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 35页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 36页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 37页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 38页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 39页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 40页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 41页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 42页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 43页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 44页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 45页
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可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 46页算法 4.8
void division ( int R[ ][ ],int n,int result [ ] ) {
// 已知 R[n][n] 是编号为 0 至 n-1 的 n 个元素的关系矩阵，子集划分的
//结果记入 result 数组,result[k] 的值是编号为 k 的元素所属组号
pre = n; group = 0;
InitQueue_Sq ( Q,n ); // 设置最大容量为 n 的空队列
for ( e = 0; e < n; e++ ) EnQueue_Sq ( Q,e,0 );
while ( !QueueEmpty ( Q ) ) {
DeQueue_Sq ( Q,i );
if ( i < pre ) {
group ++; // 增加一个新的组
for ( j = 0; j < n; j ++ ) clash[j] = 0;
}
if ( clash[i] == 0 ) {
result[i] = group; // 编号为 i 的元素入 group 组
for ( j = 0; j < n; j ++ ) clash[j] += R[i][j]; // 添加和 i冲突的信息 }
else EnQueue ( Q,i,0 ); // 编号为 i 的元素不能入当前组
pre = i;
} // while
}// division
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 47页循环队列的应用 （作业）
在实验中不断检测数据，为了减少仪器误差，对数据进行适当处理：根据连续五个实验数据的平均值为一个新测试数据，也就是不断去掉处于第一位置的老数据，再加入一个新测试数据为一组数据，计算其平均值，为一个测试数据，试写一个算法实现。
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 1页第 4章 栈和队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 2页
4.1 栈
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 3页
4.1.1 栈的结构特点和操作
栈 (Stack)是限制在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶 (Top)，另一端为 栈底 (Bottom)。当表中没有元素时称为 空栈 。
假设栈 S=(a1,a2,a3,… an)，则 a1称为栈底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,… an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的 。因此,栈称为后进先出表
（ LIFO） 。
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 4页由栈的定义可以发现,栈有如下特点：
1,进,出都在同一端进行；
2,先进去的后出来 。
a1
a2
an-1
an
……
栈顶栈底
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 5页
4.1.2 栈的表示和操作的实现
顺序栈（参见程序 Stack.cpp)
链栈
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 6页
4.2 栈的应用举例
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 7页例 4.1 数制转换
十进制数 N和其他 d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
N = (N div d)× d + N mod d
(其中,div 为整除运算,mod 为求余运算）
例如：（ 1348)10 = (2504)8,其运算过程如下：
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 8页算法 4.1 数制转换问题
void conversion () {
// 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数
InitStack(S); // 构造空栈
cin>>N;
while (N) {
Push(S,N % 8); //,余数,入栈
N = N/8; //,商,继续运算
}//while
while (!StackEmpty) { // 和,求余,所得相逆的顺序输出八进制的各位数
Pop(S,e);
cout< <e；
}//while
} // conversion
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 9页例 4.2 括号匹配的检验
假设表达式中允许包含两种括号：圆括号和方括号，
其嵌套的顺序随意，即 ([ ］ ( ))或［ (［ ］［ ］ )］
等为正确的格式，［ ( ］ )或 (［ ( ) )或 (( )])均为不正确的格式。 检验括号是否匹配的方法可用 "期待的急迫程度 "这个概念来描述。 例如考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的不匹配的情况,
1,到来的右括弧 非是所,期待,的 ;
2,到来的是,不速之客,;
3,直到结束，也 没有到来所,期待,的。
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 10页栈和递归函数的关系
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
例 递归的执行情况分析
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
}
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 11页递归调用执行情况如下：
主程序
(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)
结束运行结果：
1，
2,2，
3,3,3，
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 12页
4.3 队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 13页
4.3.1 队列的结构特点和操作
队列 (queue)是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。
容许插入的一端称做 队尾（ rear）
容许删除的一端称为 队头（ front）
队列的特点：
先进先出（ Fisrt In First Out) FIFO
a1 a2 a3 ……… an
出队列 入队列队头 队尾
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 14页队列的抽象数据类型
ADT Queue {
数据对象,D={ai|ai∈ ElemSet，
i=1,2,……,n,n≥0}
数据关系,R1={< ai-1,ai >| ai-1,ai ∈ D,
i=1,2,……,n}
约定 a1为队头,an为队尾
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 15页基本操作：
InitQueue(&Q)
DestroyQueue(&Q)
ClearQueue(&Q)
QueueEmpty(Q)
GetHead(Q,&e)
EnQueue(&Q,e) //进队列
DeQueue(&Q,&e)} //出队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 16页
4.3.2 队列的表示和操作的实现
1、链队列
typedef struct QNode {
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 17页
a1
a2
an ^
Q.front
Q.rear
…...
队头队尾链队列示意图
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 18页
3.4.3 循环队列 -队列的顺序表示
J1
J2
J3 J3
J4
J55
4
3
2
1
0 Q.front
Q.rear
Q.rear
Q.front
Q.front
Q.rear
Q.rear
Q.front
普通队列的浪费了存储空间浪费的空间
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 19页循环队列示意图
….
….
0
1
maxsize-1
Q.rear
Q.front
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 20页
J5
J6
J7
J8
J9
J10
J4
J5
J7
J8
J9
J4
J55
4
3
2
1
0
Q.front
Q.rear
Q.rear
Q.front
Q.front
Q.rear
Q.rear
Q.front
循环队列
“满队列”空队列
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 21页循环队列中元素个数：
(Q.rear-Q.front+MAXSIZE)%MAXSIZE
循环队列是否满：
(Q.rear+1)%MAXSIZE==Q.front
循环队列是否空：
Q.rear==Q.front
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 22页队列应用举例（划分子集问题）
问题描述：
已知集合 A={a1,a2,……an},及集合上的关系
R={ (ai,aj) | ai,aj?A,i?j}，
其中 (ai,aj)表示 ai与 aj间存在冲突关系。
要求将 A划分成 互不相交 的子集 A1,A2,……Ak,(k?n)，
使任何子集中的元素均无冲突关系，同时要求 划 分子集个数尽可能少
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 23页例：
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 }
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 24页
算法思想：
利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组
所用数据结构
冲突关系矩阵
r[i][j]=1,i,j有冲突
r[i][j]=0,i,j无冲突
循环队列 cq[n]
数组 result[n]存放每个元素分组号
工作数组 clash[n]
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 25页
工作过程
初始状态,A中元素放于 cq中,result和 clash数组清零，组号
group=1
第一个元素出队，将 r矩阵中第一行,1”拷入 clash中对应位置，这样，凡与第一个元素有冲突的元素在 clash中对应位置处均为,1”,下一个元素出队
若其在 clash中对应位置为,1”，有冲突，重新插入 cq队尾，参加下一次分组
若其在 clash中对应位置为,0”,无冲突，可划归本组；再将 r矩阵中该元素对应行中的,1”拷入 clash中
如此反复，直到 9个元素依次出队，由 clash中为,0”的单元对应的元素构成第 1组,将组号 group值,1”写入 result对应单元中
令 group=2,clash清零，对 cq中元素重复上述操作，直到 cq中
front==rear,即队空，运算结束
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 26页
算法描述
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
初始
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 27页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 28页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 29页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 30页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 31页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 32页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 33页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 34页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 35页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 36页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 37页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 38页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 39页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 40页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 41页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 42页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 43页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 44页
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
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 45页
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可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
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=
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) }
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 46页算法 4.8
void division ( int R[ ][ ],int n,int result [ ] ) {
// 已知 R[n][n] 是编号为 0 至 n-1 的 n 个元素的关系矩阵，子集划分的
//结果记入 result 数组,result[k] 的值是编号为 k 的元素所属组号
pre = n; group = 0;
InitQueue_Sq ( Q,n ); // 设置最大容量为 n 的空队列
for ( e = 0; e < n; e++ ) EnQueue_Sq ( Q,e,0 );
while ( !QueueEmpty ( Q ) ) {
DeQueue_Sq ( Q,i );
if ( i < pre ) {
group ++; // 增加一个新的组
for ( j = 0; j < n; j ++ ) clash[j] = 0;
}
if ( clash[i] == 0 ) {
result[i] = group; // 编号为 i 的元素入 group 组
for ( j = 0; j < n; j ++ ) clash[j] += R[i][j]; // 添加和 i冲突的信息 }
else EnQueue ( Q,i,0 ); // 编号为 i 的元素不能入当前组
pre = i;
} // while
}// division
Da
ta
Str
uc
tur
e
数据结构——
第
4
章栈和队列胡建华 2009-7-24计算机教研室第 47页循环队列的应用 （作业）
在实验中不断检测数据，为了减少仪器误差，对数据进行适当处理：根据连续五个实验数据的平均值为一个新测试数据，也就是不断去掉处于第一位置的老数据，再加入一个新测试数据为一组数据，计算其平均值，为一个测试数据，试写一个算法实现。
