-
实验报告七
----
拓扑排序
一
．
需
求
< br>分
析
2
、实现有向图的创建、遍历
1
、采用邻接表法的存储结构来定义
有向图
3
、实现栈的创建及其基本操
作（进栈、退栈、判空）
4
、求图中顶点的入度
二
．
算
法
设
计
本
程
序
中
采
用
的
< br>数
据
模
型
，
用
到
的
抽
象
数
据
类
型
的
定
义
，
程
序
的
主
要
算
法
< br>流
程
及
各
模
块
之
间
的
层
次
调
用
关
系
拓
扑
排
序
的
基
本
思
想
< br>是
以
下
两
点
：
1
、
在
有
向
图
中
选
一
个
没
有
前
驱
的
顶
点
且
< br>输
出
之
。
2
、
从
图
中
删
除
该
顶
点
何
所
有
以
它
为
尾
的
弧
。
< br>
3
、
查
邻
接
表
中
入
度
为
零
的
顶
点
，并
进
栈
。当
栈
为
空
时
，进
行
拓
扑
排
序
。
（
a
）
退
栈
，
输
出
栈
顶
元
素
V
。
< br>（
b
）
在
邻
接
表
中
查
找
Vj
的
直<
/p>
接
后
继
Vk
，
将
Vk
的
入
度
减
4
、
重
复
上
述
两
步
，直
至
全
部
顶
点
均
已
输
出
。如
< br>每
输
出
完
，则
证
明
有
环
。
程
序<
/p>
基
本
结
构
：
一
，
并
令
入
度
减
至
零
的
顶
点
进
< br>栈
。
信息工程学院
1
设定栈的抽象数据类型定义：
ADT
Stack {
数据对象：
D={
a
i
|
a
i
∈
CharSet
，i=1,2,3,….
.,n,n>=0;}
数据关系：
R
={<
a
i
?
1
，
a
i
>
|
a
i
?
1<
/p>
，
a
i
∈D,i
=2,…,n}
存储结构：
(1)
表结点
typedef struct ArcNode
{
i
nt adjvex;
s
truct ArcNode
*nextarc;
}ArcNode;
(2)
链表的存储结构
typedef struct VNode
{
i
nt data;
A
rcNode
*firstarc;
}VNode,AdjList[MAX_VEXTEX_NUM];
(3)
图的存储结构
信息工程学院
2
typedef struct
{
A
djList vertices;
i
nt vexnum,
arcnum;
}ALGraph;
(4)
栈的存储结构
typedef struct
{
E
lemType *base;
E
lemType *top;
i
nt stacksize;
}SqStack;
三
．
程
序
设
计
根
据
算
法
设
计
中
给
出
的<
/p>
有
关
数
据
和
算
法
，
选
定
物
理
结
构
，
详
细
设
计
需
求
分
析
中
所<
/p>
要
求
的
程
序
。包
括
：人
机
界
面
设
计
、主
要
功
能
的
函
数
< br>设
计
、
函
数
之
间
调
用
关
系
描
述
等
。
1
界
面
设
计
1
）
欢
< br>迎
界
面
2
）输入顶点与边的关系，并得到拓扑排序
信息工程学院
3
2
主
要
功
能
1
）
初
始
化
栈
void InitStack(SqStack *S)//
初
始
化
栈
{
S->base = (ElemType *)
malloc(STACK_INIT_SIZE * sizeof
(ElemType));
if (!S->base) {
printf(
exit(1);
}
S->top = S->base;
S->stacksize =
STACK_INIT_SIZE;
}
2
）
出
栈
操
作
int Pop(SqStack *S,
ElemType *e)//
出
栈
操
作
{
if
(S->top == S->base) {
return ERROR;
}
信息工程学院
4
*e = *--S->top;
return 0;
}
3
）
进
栈
操
作
void Push(SqStack *S,
ElemType e)//
进
栈
操<
/p>
作
{
if
(S->top - S->base >= S->stacksize) {
S->base = (ElemType *)
realloc(S
->base, (S->stacksize +
STACKINCREMENT) * sizeof
(ElemType));
if (!S->base) {
printf(
exit(1);
}
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e;
}
4
）
判
断
栈
是
否
为
空
int
StackEmpty(SqStack *S)//
判
断
栈
是
否
为
空
{
if
(S->top == S->base)
return OK;
else
return ERROR;
}
5
）
构<
/p>
建
图
与
欢
迎
界
面
void CreatGraph(ALGraph *G)//
构
建
图
{
int m, n, i;
ArcNode *p;
printf(
******n
printf(
欢
迎
使
用
拓
扑
排
序
n
printf(
制
作
者
：
----n
p
rintf(
n
printf(
请
输
入
顶
点
数
和
边
数
:
scanf(
for (i =
1; i <= G
->vexnum; i++) {
信息工程学院
5
G->vertices[i].data =
i;
G->vertices[i].firstarc =
NULL;
}
for (i =
1; i <= G
->arcnum; i++) //
输<
/p>
入
存
在
边
的
点
集
合
{
printf(
< br>请
输
入
存
在
边
的
两
个
顶
点
的
序
号
:
scanf(
while (n < 0 || n >
G
->vexnum || m < 0 || m >
G
->vexnum) {
printf(
< br>输
入
的
顶
点
序
号
不
正
确
请
重
新
输
入
:
scanf(
}
p = (ArcNode*) malloc(sizeof
(ArcNode));
if (p == NULL)
{
printf(
exit(1);
}
p->adjvex = m;
p->nextarc =
G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
}
6
）
找
入
度
为
零
的
结
点
void
FindInDegree(ALGraph G, int indegree[])//
找
入
度
为
零
的
节
点
{
int i;
for
(i = 1; i <= i++) {
indegree[i] = 0;
}
for (i = 1; i <= i++) {
while (es[i].firstarc) {
indegree[es[i].firstarc
->adjve
x]++;
es[i].firstarc =
es[i].firstarc
->nextarc;
}
}
}
7
）
进
行
拓
扑
排
序
void
TopologicalSort(ALGraph G) //
进
行
拓
扑
排
序
{
信息工程学院
6