数据结构课程设计：有向图拓扑排序算法的实现

创

建

邻

接

表

栈

< br>的

初

始

化

拓

扑

排

序

图

3.1

程 序模块功能图

3.2

抽象数据类型

ADT ALGraph

｛

数据对象：

D={V|V

是具有相同特性的数据元素的集合，即顶点集

}

数据关系：

R={|v,w

∈

V

,

表示顶点

v

到顶点

w

< br>的弧

}

基本操作

P:

CreatGraphlist(ALGraph *G)

初 始条件：成对输入顶点集

V

中的点。

操作结果：构造图

G

的邻接表。

FindInDegree(ALGraph G, intindegree[])

初始条件：图

G

的邻接表中存在结点

V

。

操作结果：找到图中入度为

0

结点。< /p>

Initgraph()

操作结果：完成图形初始化。

TopologicalSort(ALGraph G)

初 始条件：构造的有向图

G

已初始化。

操作结果：对于有向图

G

根据邻接存储 表进行拓扑排序。

}

第

3

页共

18

页

4

详细设计

4.1 C

语言定义的相关数据类型

#define max_vextex_num 20

/*

宏定义最大顶点个数

*/

#define stack_init_size 100

/*

宏定义栈的存储空间大小

*/

typedefintElemType;

typedefstructVNode /*

邻接表头结点的类型

*/

{

int data; /*

顶点信息

,

数据域

*/

}VNode, AdjList[MAX_VEXTEX_NUM];

/*AdjList

是邻接表类型

*/

typedefstruct

{

AdjList vertices;

/*

邻接表

*/

intvexnum, arcnum; /*

图中顶点数

vexn

和边数

arcn*/

}ALGraph;

/*

图的类型

*/

typedefstruct //

构建栈

{

ElemType *base;

/*

数据域

*/

ElemType *top;

/*

栈指针域

*/

intstacksize;

}SqStack;

4.2

主要模块的伪码算法

4.2.1

主函数伪码算法：

开始

{

创建及输出邻接表

CreatGraphlist(&G);

输出排序后的输出序列

TopologicalSort(G) ;

}

结束

4.2.2

邻接表伪码算法：

#define MAX_VEXTEX_NUM 20

typedefstructVNode /*

邻接表头结点的类型

*/

{

int data; /*

顶点信息

,

数据域

*/

第

4

页共

18

页

ArcNode *firstarc; /*

指向第一条弧

*/

}VNode, AdjList[MAX_VEXTEX_NUM];

/*AdjList

是邻接表类型

*/

typedefstruct

{

AdjList vertices;

/*

邻接表

*/

intvexnum, arcnum; /*

图中顶点数

vexn

和边数

arcn*/

}ALGraph;

/*

图的类型

*/

开始

{

定义一个指针

P

置

< br>i

的初值为

1

邻接表中所有头结点指针置初值

当< /p>

i<=G-vexnum

时自加，执行下面操作：

输出数据域里的顶点信息

使指针

p

指向顶点

i

< br>第一条弧的头结点

输出访问顶点

使指针

p

指向顶点

i

的下一条弧的头 结点

类此循环到输出最后一个顶点

}

结束

4.2.3

拓扑排序的伪码算法

开始

{

引入栈操作函数和入度操作函数

访问邻接存储表中的顶点

n

If

该顶点入度为

0

顶点进栈

循环操作到所有顶点入栈

当栈不为空

顶点出栈

}

结束

第

5

页共

18

页

4.3

主函数流程图

主函数流程图如图

4.3

所示

开始

输入顶点数

和弧数

输入

判断是否满足条件

Y

根据输入信息建立邻接表

建栈

N

在邻接表中寻找入度为零的顶点，使其入栈

N

输出栈顶元素，

打印，

顶点的入度减

1

判断是否空栈

Y

结束

图

4.3

主函数程序流程图

第

6

页共

18

页

5

程序编码

#include

#include

#define true 1

#define false 0

#define MAX_VEXTEX_NUM 20

#define M 20

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

/*------- ----------------

图的邻接表存储结构

--- ---------------------*/

typedefstructArcNode

/*

弧结点结构类型

*/

{

intadjvex;

/*

该弧指向的顶点的位置

*/

structArcNode *nextarc;

/*

指向下一条弧的指针

*/

}ArcNode;

typedefstructVNode

/*

邻接表头结点类型

*/

{

int data;

/*

顶点信息

*/

ArcNode *firstarc;

/*

指向第一条依附于该点的弧的指针

*/

}VNode,AdjList[MAX_VEXTEX_NUM];

/*AdjList

为邻接表类型

*/

typedefstruct

{

AdjList vertices;

intvexnum, arcnum;

}ALGraph;

/*-------- -------------------------------------------------- ------*/

void CreatGraph(ALGraph *G)

/*

通过用户交互产生一个图的邻接表

*/

{

int m, n, i;

ArcNode *p;

pri ntf(

printf(

输入顶点数

:

scanf(

printf(

输入边数

:

scanf(

printf(

for (i=1; i<=G->vexnum;i++)

/*

初始化各顶点

*/

{

G->vertices[i].data=i;

/*

编写顶点的位置序号

*/

G->vertices[i].firstarc=NULL;

第

7

页共

18

页