实验报告七----拓扑排序
一．需求分析
1、采用邻接表法的存储结构来定义有向图
2、实现有向图的创建、遍历
3、实现栈的创建及其基本操作（进栈、退栈、判空）
4、求图中顶点的入度
二．算法设计
本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系
拓扑排序的基本思想是以下两点：
1、在有向图中选一个没有前驱的顶点且输出之。
2、从图中删除该顶点何所有以它为尾的弧。
3、 查邻接表中入度为零的顶点，并进栈。当栈为空时，进行
拓扑排序。
（a）退栈，输出栈顶元素V。
（b）在邻接表中查找Vj的直接后继Vk，将Vk的入度减
一，并令入度减至零的顶点进栈。
4、重复上述两步，直至全部顶点均已输出。如每输出完，则证明有环。
程序基本结构：
设定栈的抽象数据类型定义：
ADT Stack {
数据对象：D={
|
∈CharSet，i=1,2,3,…..,n,n＞=0;}
数据关系：R={＜
，
＞|
，
∈D,i=2,…,n}
存储结构：
(1)表结点
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
(2)链表的存储结构
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VEXTEX_NUM];
(3)图的存储结构
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
(4)栈的存储结构
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
三．程序设计
根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。
1界面设计
1）欢迎界面
2）输入顶点与边的关系，并得到拓扑排序
2主要功能
1）初始化栈
void InitStack(SqStack *S)//初始化栈
{
S-＞base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof (ElemType));
if (!S-＞base) {
printf("memory allocation failed, goodbye");
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;
}
*e = *--S-＞top;
return 0;
}
3）进栈操作
void Push(SqStack *S, ElemType e)//进栈操作
{
if (S-＞top - S-＞base ＞= S-＞stacksize) {
S-＞base = (ElemType *) realloc(S-＞base, (S-＞stacksize + STACKINCREMENT) * sizeof (ElemType));
if (!S-＞base) {
printf("memory allocation failed, goodbye");
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）构建图与欢迎界面
void CreatGraph(ALGraph *G)//构建图
{
int m, n, i;
ArcNode *p;
printf("************************************************\n");
printf(" 欢迎使用拓扑排序\n");
printf(" 制作者：----\n");
printf("************************************************\n");
printf("请输入顶点数和边数:");
scanf("%d%d", &G-＞vexnum, &G-＞arcnum);
for (i = 1; i ＜= G-＞vexnum; i++) {
G-＞vertices[i].data = i;
G-＞vertices[i].firstarc = NULL;
}
for (i = 1; i ＜= G-＞arcnum; i++) //输入存在边的点集合
{
printf("\n请输入存在边的两个顶点的序号:");
scanf("%d%d", &n, &m);
while (n ＜ 0 || n ＞ G-＞vexnum || m ＜ 0 || m ＞ G-＞vexnum) {
printf("输入的顶点序号不正确 请重新输入:");
scanf("%d%d", &n, &m);
}
p = (ArcNode*) malloc(sizeof (ArcNode));
if (p == NULL) {
printf("memory allocation failed,goodbey");
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 ＜= G.vexnum; i++) {
indegree[i] = 0;
}
for (i = 1; i ＜= G.vexnum; i++) {
while (G.vertices[i].firstarc) {
indegree[G.vertices[i].firstarc-＞adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc-＞nextarc;
}
}
}
7）进行拓扑排序
void TopologicalSort(ALGraph G) //进行拓扑排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i ＜= G.vexnum; i++) {
if (!indegree[i])
Push(&S, i);
}
printf("进行拓扑排序输出顺序为:\n"); //输出结果
while (!StackEmpty(&S)) {
Pop(&S, &n);
printf("%4d", G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p-＞nextarc) {
k = p-＞adjvex;
if (!(--indegree[k])) {
Push(&S, k);
}
}
}
printf("\n");
if (count ＜ G.vexnum) {
printf("该有向图有回路");
} else {
printf("排序成功\n");
}
}
3函数调用
四．测试与分析
1、不知道怎么选择储存结构
2、在写代码的过程中，没有弄清使用指针与引用之后，结构体如何使用。当使用指针的时候要使用‘.’，当使用引用或数的时候，要使用‘-＞’。
3、出栈入栈的条件很混乱，不知道该怎么去使用栈。
经验与体会：这个程序，要求我们想的要尽量全面，要将所有情况考虑清楚，不仅有图的知识，还有对栈的灵活应用记。在程序的全面性与健壮性上，我做的还不够好。因为书上有代码，所以不是太难，在栈的那部分比较混乱，又复习了一遍，现在更好的掌握了栈的基本操作几项基本操作，也对拓扑序列有了更清楚的认识。
源程序：
#include＜STDIO.H＞
#include＜STDLIB.H＞
#define MAX_VEXTEX_NUM 20 //最大顶点个数#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define M 20
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode //定义表结点结构
{
int adjvex; //与vi相邻接的顶点编号
struct ArcNode *nextarc; //指向下一条弧(边)的指针
} ArcNode;
typedef struct VNode //定义表头结点结构
{
int data;
ArcNode *firstarc; //指向第一条弧（边）的指针
} VNode, AdjList[MAX_VEXTEX_NUM];
typedef struct //定义邻接表结构
{
AdjList vertices; //表头结点数组
int vexnum, arcnum; //顶点和弧（边）的个数
} ALGraph;
typedef struct //构件栈
{
ElemType *base;
ElemType *top;
int stacksize;
} SqStack;
void InitStack(SqStack *); //函数声明
int Pop(SqStack *, ElemType *);
void Push(SqStack *, ElemType);
int StackEmpty(SqStack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph, int *);
void TopologicalSort(ALGraph);
void InitStack(SqStack *S)//初始化栈
{
S-＞base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof (ElemType));
if (!S-＞base) {
printf("memory allocation failed, goodbye");
exit(1);
}
S-＞top = S-＞base;
S-＞stacksize = STACK_INIT_SIZE;
}
int Pop(SqStack *S, ElemType *e)//出栈操作
{
if (S-＞top == S-＞base) {
return ERROR;
}
*e = *--S-＞top;
return 0;
}
void Push(SqStack *S, ElemType e)//进栈操作
{
if (S-＞top - S-＞base ＞= S-＞stacksize) {
S-＞base = (ElemType *) realloc(S-＞base, (S-＞stacksize + STACKINCREMENT) * sizeof (ElemType));
if (!S-＞base) {
printf("memory allocation failed, goodbye");
exit(1);
}
S-＞top = S-＞base + S-＞stacksize;
S-＞stacksize += STACKINCREMENT;
}
*S-＞top++ = e;
}
int StackEmpty(SqStack *S)//判断栈是否为空
{
if (S-＞top == S-＞base)
return OK;
else
return ERROR;
}
void CreatGraph(ALGraph *G)//构建图
{
int m, n, i;
ArcNode *p;
printf("************************************************\n");
printf(" 欢迎使用拓扑排序\n");
printf(" 制作者：---\n");
printf("************************************************\n");
printf("请输入顶点数和边数:");
scanf("%d%d", &G-＞vexnum, &G-＞arcnum);
for (i = 1; i ＜= G-＞vexnum; i++) {
G-＞vertices[i].data = i;
G-＞vertices[i].firstarc = NULL;
}
for (i = 1; i ＜= G-＞arcnum; i++) //输入存在边的点集合
{
printf("\n请输入存在边的两个顶点的序号:");
scanf("%d%d", &n, &m);
while (n ＜ 0 || n ＞ G-＞vexnum || m ＜ 0 || m ＞ G-＞vexnum) {
printf("输入的顶点序号不正确 请重新输入:");
scanf("%d%d", &n, &m);
}
p = (ArcNode*) malloc(sizeof (ArcNode));
if (p == NULL) {
printf("memory allocation failed,goodbey");
exit(1);
}
p-＞adjvex = m;
p-＞nextarc = G-＞vertices[n].firstarc;
G-＞vertices[n].firstarc = p;
}
}
void FindInDegree(ALGraph G, int indegree[])//找入度为零的节点
{
int i;
for (i = 1; i ＜= G.vexnum; i++) {
indegree[i] = 0;
}
for (i = 1; i ＜= G.vexnum; i++) {
while (G.vertices[i].firstarc) {
indegree[G.vertices[i].firstarc-＞adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc-＞nextarc;
}
}
}
void TopologicalSort(ALGraph G) //进行拓扑排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i ＜= G.vexnum; i++) {
if (!indegree[i])
Push(&S, i);
}
printf("进行拓扑排序输出顺序为:\n"); //输出结果
while (!StackEmpty(&S)) {
Pop(&S, &n);
printf("%4d", G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p-＞nextarc) {
k = p-＞adjvex;
if (!(--indegree[k])) {
Push(&S, k);
}
}
}
printf("\n");
if (count ＜ G.vexnum) {
printf("该有向图有回路");
} else {
printf("排序成功\n");
}
}
int main(void) //主函数
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;
}