《拓扑排序(算法与数据结构课程设计)》由会员分享，可在线阅读，更多相关《拓扑排序(算法与数据结构课程设计)（16页珍藏版）》请在金锄头文库上搜索。
1、拓扑排序一、问题描述 在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。二、基本要求 1、选择合适的存储结构，建立有向无环图，并输出该图； 2、实现拓扑排序算法； 3、运用拓扑排序实现对教学计划安排的检验。三、算法思想 1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。 2、拓扑排序算法void TopologicalSort(
2、ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现。考虑到教学计划安排的实际情况，一般先学基础课（入度为零），再学专业课（入度不为零），与队列先进先出的特点相符，故采用队列实现。 3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入队列； 2)队列非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入队列； 4)重复2)、3)，直到队列为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。 4、要
3、对教学计划安排进行检验，因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G)，大体思想为： 1)用户输入待检测的课程序列，将其存入数组； 2)检查课程序列下一个元素是否是图中的顶点（课程），是则执行3)，否则输出“课程XX不存在”并跳出； 3)判断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出； 4)该顶点的所有邻接点入度减一；5)重复2)、3)、4)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。四、数据结构 1、链式队列的存储类型为：typedef int ElemType;typedef st
4、ruct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue; 2、图的类型（邻接表存储结构）为：typedef char VertexType20;/顶点信息（名称）typedef struct ArcNode/链表结点int vexpos;/该弧所指向的顶点在数组中的位置struct ArcNode *next;/指向当前起点的下一条弧的指针ArcNode;typedef struct VNode/头结点VertexType na
5、me;/顶点信息（名称）int indegree;/顶点入度ArcNode *firstarc;/指向当前顶点的第一条弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vexhead;/邻接表头结点数组int vexnum,arcnum;/图的顶点数和弧数ALGraph;五、模块划分1、链式队列操作1) void InitQueue(LinkQueue *Q)功能：初始化链式队列参数：*Q 待初始化的队列2) int QueueEmpty(LinkQueue Q)功能：判断空队列参数：Q 待判断的队列返回值：队列为空返回 1；队列非空返
6、回 03) void EnQueue(LinkQueue *Q, ElemType e)功能：元素入队列参数：*Q 待操作的队列；e 要入队列的元素4) void DeQueue(LinkQueue *Q, ElemType *e)功能：元素出队列参数：*Q 待操作的队列；*e 记录出队列元素的变量2、有向图(DAG)邻接表存储结构(ALG)的操作1) int LocateVex(ALGraph G,VertexType v)功能：顶点在头结点数组中的定位参数：G 待操作的图；v 要在图中定位的顶点返回值：顶点存在则返回在头结点数组中的下标；否则返回图的顶点数2) int CreateGrap
7、h(ALGraph *G)功能：建立图函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作参数：*G 待操作的图返回值：图建立成功返回1；图建立失败返回0错误判断：包含顶点数、弧数是否正确的判断；包含用户输入的弧的顶点是否存在的判断3) void PrintGraph(ALGraph G)功能：输出有向图参数：G 待输出的图4) int CreateGraph2(ALGraph *G)功能：建立预置课程图（输出函数内预置课程信息，并自动建立有向图）参数：*G 待操作的图返回值：图建立成功返回1；图建立失败返回0错误判断：包含顶点数、弧数是否正确的判断包含弧的顶点是否存在的判断5) void P
8、rintGraph2(ALGraph G)功能：输出预置课程图参数：G 待输出的图3、拓扑排序及拓扑检测算法1) void TopologicalSort(ALGraph G)功能：实现拓扑排序参数：G 待进行拓扑排序的图错误判断：包含有向图是否有环的判断2) void TopSortCheck(ALGraph G)功能：运用拓扑排序的思想检测教学计划函数内包含了由用户输入待检测的课程序列的操作参数：G 待操作的图错误判断：包含用户输入的课程是否存在的判断包含不是拓扑序列的原因（该课程有多少个先决课程未学）4、主函数void main()功能：主函数利用while语句和switch语句实现菜单
9、化调用函数六、源程序#include stdlib.h#include stdio.h#include string.h/*/* 以下为链式队列操作 */*/* 定义链式队列类型 */typedef int ElemType;typedef struct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;/* 1.初始化链式队列 */void InitQueue(LinkQueue *Q)Q-front=Q-rear=(QueueP
10、tr)malloc(sizeof(QNode);if (!(Q-front) exit(0);Q-front-next=NULL; /* 2.判断空队列 */int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;else return 0; /* 3.入队列 */void EnQueue(LinkQueue *Q, ElemType e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if (!p) exit(0);p-data=e; p-next=NULL;Q-rear-next=p;Q-rear=
11、p; /* 4.出队列 */void DeQueue(LinkQueue *Q, ElemType *e)QueuePtr p;if(Q-front!=Q-rear)p=Q-front-next;*e=p-data;Q-front-next=p-next;if (Q-rear=p) Q-rear=Q-front;free(p); /*/* 以下为有向图(DAG)邻接表存储结构(ALG)的操作 */*/#define MAX_VERTEX_NUM 20 /最大顶点个数typedef char VertexType20; /顶点信息（名称）/* 图的类型定义（邻接表存储结构） */typedef
12、struct ArcNode /链表结点int vexpos; /该弧所指向的顶点在数组中的位置struct ArcNode *next; /指向当前起点的下一条弧的指针ArcNode;typedef struct VNode /头结点VertexType name; /顶点信息（名称）int indegree; /顶点入度ArcNode *firstarc; /指向当前顶点的第一条弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vexhead; /邻接表头结点数组int vexnum,arcnum; /图的顶点数和弧数ALGraph
13、;/* 5.顶点在头结点数组中的定位 */int LocateVex(ALGraph G,VertexType v)int i;for(i=0;iG.vexnum;i+)if(strcmp(v,G.vexheadi.name)=0) break;return i; /* 6.建立图（邻接表） */int CreateGraph(ALGraph *G) /成功建立返回1，不成功则返回0int i,j,k; VertexType v1,v2;ArcNode *newarc;printf(n输入有向图顶点数和弧数vexnum,arcnum:); /输入顶点数和弧数scanf(%d,%d,&(*G).vexnum,&(*G).arcnum); /输入并判断顶点数和弧数是否正确if(*G).vexnum0|(*G).arcnum(*G).vexnum*(*G).vexnum-1)printf(n顶点数或弧数不正确，有向图建立失败！n);return 0; printf(n输入 %d 个顶点:,(*G).vexnum); /输入顶点名称for(i=0;i(*G).vexnum;i+)scanf(%s,(*G).vexheadi.name);
