拓扑排序 一 问题描述 本次课程设计题目是：编写函数实现图的拓扑排序 二 概要设计 1. 算法中用到的所有各种数据类型的定义 在该程序中用邻接表作为图的存储结构。首先，定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。 拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。 2.各程序模块之间的层次调用关系 第一部分，void CreatGraph(ALGraph *G)函数构建图，用邻接表存储。这个函数没有调用函数。 第二部分，void TopologicalSort(ALGraph *G)输出拓扑排序函数，这个函数首先调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1];然后设置了一个辅助栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为0 者进栈，while(!StackEmpty(&S))栈不为空时，调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegree[k]--,当输出某一入度为0 的顶点时，便将它从栈中删除。 第三部分，主函数，先后调用void CreatGraph(ALGraph *G)函数构建图、 void TopologicalSort(ALGraph *G)函数输出拓扑排序实现整个程序。 3.设计的主程序流程 开始 调用建图函数 输入顶点数、弧数、顶点值 输入存在弧的两个顶点 建零入度顶点栈 S， 入度为 0 者进栈 !StackEmpty (&S) 判断并输出相应信息 结束 Pop(&S,&n) P=G.v ertices[n].firstarc P!=NULL K=P->adjv es !(--indegree[k]) P=p->nex tarc Pu sh(&S,k); 三 详细设计 1.实现概要设计中定义的所有数据类型 #include #include #include #define MAX_VEXTEX_NUM 20 //*定义点最大的数值为顶30*// #define M 20 #define STACK_INIT_SIZE 100 //*定义点最大的数值为顶30*// #define STACKINCREMENT 10 //*定义栈的增量为10*// #define OK 1 #define ERROR 0 typedef char ElemType; //*定义栈顶元素类型*// typedef struct ArcNode {int adjvex; //该弧所指向的顶点的位置// struct ArcNode *nextarc; //指向下一条弧的指针// }ArcNode; //*表结点*// typedef struct...
