拓扑排序(算法与数据结构课程设计).docx

拓扑排序一、问题描述在 AOV 网中为了更好地完成工程，必需满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学打算的安排，依据课程之间的依靠关系，制定课程安排打算。依据用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排打算。二、根本要求1、选择适宜的存储构造，建立有向无环图，并输出该图；2、实现拓扑排序算法；3、运用拓扑排序实现对教学打算安排的检验。三、算法思想1、承受邻接表存储构造实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。2、拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出的入度为零的顶点，此操作可利用栈或队列实现。考虑到教学打算安排的实际状况， 一般先学根底课入度为零，再学专业课入度不为零，与队列先进先出的特点相符， 故承受队列实现。3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将全部入度为零的顶点入队列；2) 队列非空时，输出一个顶点，并对输出的顶点数计数；3) 该顶点的全部邻接点入度减一，假设减一后入度为零则入队列；4) 重复 2)、3)，直到队列为空，假设输出的顶点数与图的顶点数相等则该图可拓扑排序， 否则图中有环。4、要对教学打算安排进展检验，因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G)，大体思想为：1) 用户输入待检测的课程序列，将其存入数组；2) 检查课程序列下一个元素是否是图中的顶点课程，是则执行 3)，否则输出“课程 XX 不存在”并跳出；3) 推断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出；4) 该顶点的全部邻接点入度减一；5) 重复 2)、3)、4)直到课程序列中全部元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。wilyes11 收集 博客(与学习无关)： :/blog.sina .cn/u/1810231802四、数据构造1、链式队列的存储类型为： typedef int ElemType; typedef struct 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 name;/顶点信息名称 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；队列非空返回 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 CreateGraph(ALGraph *G) 功能：建立图函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作参数：*G 待操作的图返回值：图建立成功返回 1；图建立失败返回 0 错误推断：包含顶点数、弧数是否正确的推断；包含用户输入的弧的顶点是否存在的推断3) void PrintGraph(ALGraph G) 功能：输出有向图参数：G 待输出的图4) int CreateGraph2(ALGraph *G)功能：建立预置课程图输出函数内预置课程信息，并自动建立有向图 参数：*G 待操作的图返回值：图建立成功返回 1；图建立失败返回 0 错误推断：包含顶点数、弧数是否正确的推断包含弧的顶点是否存在的推断5) void PrintGraph2(ALGraph G) 功能：输出预置课程图参数：G 待输出的图3、拓扑排序及拓扑检测算法1) void TopologicalSort(ALGraph G) 功能：实现拓扑排序参数：G 待进展拓扑排序的图错误推断：包含有向图是否有环的推断2) void TopSortCheck(ALGraph G)功能：运用拓扑排序的思想检测教学打算函数内包含了由用户输入待检测的课程序列的操作参数：G 待操作的图错误推断：包含用户输入的课程是否存在的推断包含不是拓扑序列的缘由该课程有多少个先决课程未学4、主函数void main 功能：主函数利用 while 语句和switch 语句实现菜单化调用函数六、源程序#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=(QueuePtr)malloc(sizeof(QNode); if (!(Q->front) exit(0);Q->front->next=NULL; /* 2.推断空队列 */int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1; elsereturn 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=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 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;/* 5.顶点在头结点数组中的定位 */int LocateVex(ALGraph G,VertexType v)int i; for(i=0;i<G.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).vexnum<0|(*G).arcnum<0|(*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); printf(“n 顶点列表:n 共有%d 个顶点:“,(*G).vexnum);/输出顶点名称for(i=0;i<(*G).vexnum;i+)printf(“%s“,(*G).vexheadi.name); for(i=0;i<(*G).vexnum;i+) /邻接表初始化(*G).vexheadi.firstarc=NULL; (*G).vexheadi.indegree=0;printf(“nn 输入 %d 条边:vi vjn“,(*G).arcnum); /输入有向图的边for(k=0;k<(*G).arcnum;k+)scanf(“%s%s“,v1,v2); /v1 是弧的起点先决条件，v2 是弧的终点i=LocateVex(*G,v1);j=LocateVex(*G,v2); /定位顶点并推断顶点是否存在if(i>=(*G).vexnum)printf(“顶点%s 不存在，有向图建立失败！n“,v1);return 0; if(j>=(*G).vexnum)printf(“顶点%s 不存在，有向图建立失败！n“,v2);return 0; newarc=(ArcNode*)malloc(sizeof(ArcNode); /前插法建顶点链表newarc->vexpos=j;if(*G).vexheadi.firstarc=NULL)newarc->next=NULL; (*G).vexheadi.firstarc=newarc; elsenewarc->next=(*G).vexheadi.firstarc->next; (*G).vexheadi.firstarc->next=newarc; (*G).vexheadj.indegree+; /对应顶点入度计数加 1printf(“n 有向图建立成功！n“); return 1;/* 7.按邻接表方式输出有向图 */ void PrintGraph(ALGraph G)int i;ArcNode *p; printf(“n 输出有向图:n“); for(i=0; i<G.vexnum; i+)printf(“n 顶点:%s“,G.vexheadi.name); printf(“入度:%3dn“,G.vexheadi.indegree); p=G.vexheadi.firstarc;printf(“邻接点:“);while(p!=NULL)printf(“%s“,G.vexheadp->vexpos.name); p=p->next; printf(“n“);/为避开演示时要输入过多数据，以下函数将课程编号、课程间的先后关系通过数组预置/* 8.建立预置课程图邻接表 */int CreateGraph2(ALGraph *G) /成功建立返回 1，不成功则返回 0int i,j,k; VertexType v1,v2;ArcNode *newarc;VertexType SubjectName12=“C1“,“C2“,“C3“,“C4“, /课程名称“C5“,“C6“,“C7“,“C8“,“C9“,“C10“,“C11“,“C12“ ,RelationV116=“C1“,“C1“,“C2“,“C1“, /根底课“C3“,“C4“,“C11“,“C5“,“C3“,“C3“,“C6“,“C9“,“C9“,“C9“,“C10“,“C11“,RelationV216=“C2“,“C3“,“C3“,“C4“, /以上面课程为根底的课“C5“,“C5“,“C6“,“C7“,“C7“,“C8“,“C8“,“C10“,“C11“,“C12“,“C12“,“C12“,;/* 输出本程序使用的课程及先后关系表 */ printf(“n 本程序预置了如下课程及先后关系:n“);printf(“n 课程编号课程名称先决条件nC1程序设计根底无nC2离散数学C1nC3数据构造C1,C2nC4汇编语言C1nC5语言的设计和分析C3,C4nC6计算机原理C11nC7编译原理C5,C3nC8操作系统C3,C6nC9高等数学无nC10线性代数C9nC11一般物理C9nC12数值分析C9,C10,C1n“);system(“PAUSE“); (*G).vexnum=12; (*G).arcnum=16;if(*G).vexnum<0|(*G).arcnum<0|(*G).arcnum>(*G).vexnum*(*G).vexnum-1)printf(“n 课程数或先后关系不正确，有向图建立失败！n“); return 0; /推断课程数和弧数是否正确for(i=0;i<(*G).vexnum;i+)strcpy(*G).vexheadi.name,SubjectNamei); for(i=0;i<(*G).vexnum;i+) /邻接表初始化(*G).vexheadi.firstarc=NULL; (*G).vexheadi.indegree=0; for(k=0;k<(*G).arcnum;k+)strcpy(v1,RelationV1k);strcpy(v2,RelationV2k); i=LocateVex(*G,v1);j=LocateVex(*G,v2); /定位课程并推断课程是否存在if(i>=(*G).vexnum)printf(“课程%s 不存在，有向图建立失败！n“,v1);return 0; if(j>=(*G).vexnum)printf(“课程%s 不存在，有向图建立失败！n“,v2);return 0; newarc=(ArcNode*)malloc(sizeof(ArcNode); /前插法建课程链表newarc->vexpos=j;if(*G).vexheadi.firstarc=NULL)newarc->next=NULL; (*G).vexheadi.firstarc=newarc; elsenewarc->next=(*G).vexheadi.firstarc->next; (*G).vexheadi.firstarc->next=newarc; (*G).vexheadj.indegree+; /对应课程入度计数加 1printf(“n 有向图建立成功！n“); return 1;/* 9.按邻接表方式输出预置课程图 */ void PrintGraph2(ALGraph G)int i;ArcNode *p; printf(“n 输出有向图:n“); for(i=0; i<G.vexnum; i+)printf(“n 课程:%s“,G.vexheadi.name); printf(“入度:%3dn“,G.vexheadi.indegree); p=G.vexheadi.firstarc;printf(“以本课程为根底的课程:“); while(p!=NULL)printf(“%s“,G.vexheadp->vexpos.name); p=p->next;printf(“n“);/*/*以下为拓扑排序算法*/*/* 10.拓扑排序 */void TopologicalSort(ALGraph G)int i,k,count;ElemType e;ArcNode *p; LinkQueue Q; /*定义队列*/ InitQueue(&Q);for(i=0; i<G.vexnum; i+) /零入度课程入队列if(!G.vexheadi.indegree) EnQueue(&Q,i);count=0; /对输出课程计数变量初始化printf(“nnn 以上课程的一个拓扑排序序列为:n“); while(!QueueEmpty(Q)DeQueue(&Q,&e); /先将入度为零的课程输出printf(“%s“,G.vexheade.name); count+; /对输出的顶点计数for(p=G.vexheade.firstarc;p;p=p->next) /遍历当前课程的邻接点k=p->vexpos; /邻接点位置if(!(-G.vexheadk.indegree) /每个邻接点入度减 1 后假设为零则入队列EnQueue(&Q,k);printf(“n“); if(count<G.vexnum)printf(“n 该有向图有回路，无法完成拓扑排序！n“); /*/*以下为拓扑检测算法*/*/* 11.运用拓扑排序的思想检测教学打算 */ void TopSortCheck(ALGraph G)int i,k; ArcNode *p; VertexType v,CheckList12;/待检测序列TopologicalSort(G);printf(“n 输入待检测的课程序列:n“); for(i=0; i<G.vexnum; i+) /输入待检测序列scanf(“%s“,CheckListi); for(i=0; i<G.vexnum; i+) strcpy(v,CheckListi); k=LocateVex(G,v);if(k>=G.vexnum) /推断课程是否存在 printf(“课程%s 不存在！n“,v);return; if(G.vexheadk.indegree!=0) /推断课程入度是否为零 printf(“学习课程%s 时,还有%d 门先决课程未学！n“,v,G.vexheadk.indegree); printf(“本课程序列不是拓扑序列nn“);return; else for(p=G.vexheadLocateVex(G,v).firstarc;p;p=p->next)/遍历此课程邻接点k=p->vexpos; /邻接点位置G.vexheadk.indegree-; /每个邻接点入度减 1printf(“本课程序列符合拓扑序列nn“);/*/*12.主函数*/*/ void mainALGraph G; int menu,menu2; while(1)printf(“n*n“); printf(“*1.建立有向图并输出*n“); printf(“*2.建立有向图并求一个拓扑排序序列*n“); printf(“*3.检测用户输入的课程安排*n“);printf(“*4.清屏*n“);printf(“*5.退出*n“); printf(“*n“); printf(“请输入你的选择:“);scanf(“%d“,&menu); switch(menu)case 1:if(CreateGraph(&G)system(“PAUSE“);PrintGraph(G);/有向图建成则执操作break;case 2:if(CreateGraph(&G) /有向图建成则执操作system(“PAUSE“); PrintGraph(G);system(“PAUSE“); TopologicalSort(G); break; case 3:if(CreateGraph2(&G) /有向图建成则执操作system(“PAUSE“);PrintGraph2(G); system(“PAUSE“); while(1)TopSortCheck(G);printf(“n*n“); printf(“*1.检测其他课程序列*n“);printf(“*2.完成检测*n“); printf(“*n“); printf(“请输入你的选择:“);scanf(“%d“,&menu2); if(menu2!=1) break; break; case 4:system(“CLS“); break;case 5:return;七、测试数据1、对“建立有向图并输出”的测试1) 正确的有向图信息顶点数和弧数:4,3顶点:A B C D边: A B2) 错误的边B CC D顶点数和弧数:4,3 顶点:A B C D边: A BB CC E3) 错误的顶点数或弧数顶点数和弧数:3,72、对“建立有向图并求一个拓扑排序序列”的测试1) 有向图能实现拓扑排序顶点数和弧数:5,5顶点:A B C D E边:A DD CC BE AE C2) 有向图不能实现拓扑排序顶点数和弧数:5,5顶点:A B C D E边:A DD CC BE AB A3、对“检测用户输入的课程安排”的测试1) 课程序列符合拓扑序列课程序列:C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C82) 课程序列中有课程不存在课程序列:C9 C10 C11 C6 C1 C12 C4 C2 C13 C5 C7 C83) 课程序列不是拓扑序列课程序列:C9 C10 C11 C1 C8 C6 C12 C4 C2 C3 C5 C7八、测试状况程序初始执行界面以下测试编号与本文第七节测试数据编号一一对应1、对“建立有向图并输出”的测试1) 正确的有向图信息有向图信息正确的状况下，程序显示“有向图建立成功”，并输出有向图。2) 错误的边本测试中，第三条边(C E)的一个顶点E不是有向图中的顶点，程序能推断本错误并显示相应的提示信息。3) 错误的顶点数或弧数本测试中，顶点数和弧数分别为3,7。假设有向图共有n个顶点，两顶点间最多有2条有向边，则有向图最多有n*(n-1)条边。而3*(3-1)=6<7,故程序提示“顶点数或弧数不正确，有向图建立失败”；程序还能推断负的顶点数和弧数。2、对“建立有向图并求一个拓扑排序序列”的测试1) 有向图能实现拓扑排序有向图能实现拓扑排序的状况下，程序输出其中一个拓扑排序序列。2) 有向图不能实现拓扑排序本测试中，有向图其中四条边(A D)、(D C)、(C B)、(B A)构成环，程序能推断有向图有回路并提示相应信息。3、对“检测用户输入的课程安排”的测试程序首先输出预置的课程信息和据此建立的有向图。1) 课程序列符合拓扑序列在用户输入的课程序列符合拓扑序列的状况下，程序提示“本课程序列符合拓扑序列”， 并显示如图菜单。2) 课程序列中有课程不存在本程序预置了C1-C12共12门课程，假设用户输入的课程序列中有不属于预置课程的课程，程序会提示“课程XX不存在！”，并显示如图菜单。3) 课程序列不是拓扑序列假设用户输入的课程序列不是拓扑序列，程序会输出缘由，即“学习课程XX时，还有X门先决课程未学！” ，并显示如图菜单。九、参考文献1、严蔚敏，数据构造 C 语言版，清华大学出版社。2、谭浩强，C 语言程序设计，清华大学出版社。小结寻常我就比较爱好编程，有时候自己也会设想一些小程序，然后通过自己的努力来实现。因此我把本次课程设计当作了又一次熬炼，拿到题目后，经过与组员的争论便开头了程序的编写。大家都知道，编程是一件很需要急躁的事。由于几乎每一个程序的编写，都需要学习 的学问才能进展，同时程序调试过程很枯燥，有时候一点小错意味着长时间的查错。如语 法错误中，“;”丧失、“”与“”不匹配等问题最难定位到出错语句；规律错误中，作为循环变量的“i”与“j”相互混淆、对未安排空间的节点进展操作等，都会使程序运行出错而难以找到缘由。算法设计、程序调试的过程中，常常遇到看似简洁但又无法解决的问题， 这时候很简洁灰心丧气，此时切不行烦躁，肯定要冷静的思考，认真的分析；而解决问题， 完成程序后，那种兴奋感与成就感也令人兴奋。可以说编写程序既是一件困难的工作，又是 一件开心的事情。我的小组课程设计题目的核心是“拓扑排序”。虽然寻常对拓扑排序有一些了解，上课也学过，但真正应用到程序中，写出算法却一点也不简洁。拓扑排序，首先需要有被排序的 主体，也就是有向图，于是先要实现有向图的建立及相关操作；有向图的建立，该选取怎样的数据构造，是邻接矩阵还是邻接表，本着尽量靠近实际应用的态度，我选择了节约存储空 间的邻接表；拓扑排序要将图中零入度顶点先输出，可利用栈或队列实现，而本程序的一个 应用是实现教学打算的安排，考虑到教学打算安排的实际状况，一般先学各门根底课入度 为零，再学专业课入度不为零，与队列先进先出的特点相符，故承受队列实现。总之， 什么地方该用什么数据构造，该写出怎样的算法，都要经过细心分析和认真考虑。课程设计不是一个人的任务，而是一个小组三个成员共同的任务，不但要能完成程序，而且在完成的过程中也要让团队有效地协作起来。在本次课程设计的过程中，我生疏到以下 几点：第一，要有奉献精神，不要怕自己多做了，不要怕自己担当的任务有多重，而其他成员做的很少。多去做一点不会吃亏，还能学到更多的东西。团队成员之间应团结互助，不计 功过得失；其次，分工上不能马虎，要具体到个人，每个人负责哪局部任务，什么时候完成， 都要有明确的说明，应各尽其能，做到资源优化配置；第三，具体工作时，各成员应频繁沟通，避开各自为政，最终导致函数功能不符要求，参数调用不便利，或是论文作者无从下手； 第四，当工作消灭问题时，各成员应认真商讨，尽快找到问题的症结，决不应推卸责任，更不能相互埋怨。在完成课程设计的过程中，我加深了对程序构造的了解程度，对各种语句理解也更透 彻，学会了敏捷运用。同时体会到了团队合作的乐趣，一向惯于“独立思考”的我们学会了乐观地同团队成员沟通，取长补短，共同进步，只有和同学多沟通多学习才能不断地提高自 身水平。总之，这学期的数据构造课程设计，让我们学到了很多，受益匪浅。