教学计划安排检验程序(拓扑排序)报告书.doc
设计题目：示例数据：输入：学期数：5，课程数：12，课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11 v6输出：第1学期应学的课程：v1 v9第2学期应学的课程：v2 v4 v10 v11第3学期应学的课程：v3 v6 v12第4学期应学的课程：v5 v8第5学期应学的课程：v7一 需求分析1.1 引言通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。一般应用：拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。1.2 拓扑排序的了解.问题的描述在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划. 拓扑排序进行教学计划安排检验理论基础为实现对无权值有向图进行拓扑排序，输出拓扑序列，先考虑如何存储这个有向图。拓扑排序的过程中要求找到入度为0的顶点，所以要采用邻接表来存储有向图，而要得到邻接表，则先要定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。 在具体实现拓扑排序的函数中，根据规则，当某个顶点的入度为0（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为0的顶点，设立一个栈St，以存放入度为0的顶点。.拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入队列； 2)队列非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入队列； 4)重复2)、3)，直到队列为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。1.3 查阅相关资料，完成程序的实现二 总体设计拓扑排序：开始输入学期数，课程数，课程代表值，课程相互关系数，课程两两先后关系学期数<=8,课程数<=20拓扑排序输出相应课程结束否是开始输入入度，定点数，已输出顶点数已输出定点数<顶点数>入度=0顶点入栈栈非空输出顶点顶点数减1顶点入度减1累加已输出顶点数结束是否否是是三 详细设计3.1 算法设计分析拓扑排序时有向图的一种重要运算。在课表排序中，每门课都有多种关系：、（一）先后关系，即必须在一门课学完后，才能开始学习另一门课；（二）在一类课之间没有次序要求，即两门课可以同时学习，互不影响。将AOV网络中的各个顶点排列成一个线性有序序列，使得所有的要求的前趋、后趋关系都能得到满足。在AOV网络进行拓扑排序的方法：（一） 从中选择一个没有前趋的顶点，并把它输出；（二） 从网络中删去该顶点和从该顶点出发的所有有向边；重复执行上述两步，直到网中所有的顶点都被输出3.2 源代码#include <malloc.h>#include <stdio.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define STACKINCREMENT 10 #define MAX_VERTEX_NUM 20#define STACK_INIT_SIZE 100 typedef int Status;typedef int SElemType;int indegree20=0;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data10;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;ALGraph;Status InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e) if(S.top-S.base>=S.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; Status Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;else return FALSE;Status CreateDG(ALGraph &G) int i,l,v,w,vex; printf("t请输入学期数目（小于等于8）：t"); scanf("%d",&l); if(l>8) printf("tWarning!nt学期数目必须小于等于8 ! 请重新输入："); scanf("%d",&l); printf("t请输入课程数目（小于20）：");scanf("%d",&vex);if(vex>=20)printf("tWarning! nt课程数目必须小于20 ! 请重新输入：");scanf("%d",&vex); G.vexnum=vex; printf("t请输入课程间的先后关系数：");scanf("%d",&G.arcnum);printf("请输入课程的代表值（课程名的长度小于等于10个字符）:");for(i=0;i<G.vexnum;i+) scanf("%s",&G.verticesi.data);G.verticesi.firstarc = NULL;printf("请注意 v1=1,v2=2,v3=3,v4=4,c5=5,v6=6,v7=7,v8=8,v9=9,v10=10,v11=11,v12=12n");printf("请输入课程间两两间的先后关系：");for(i=0;i<G.arcnum;i+)scanf("%d %d,",&v, &w);ArcNode *p= new ArcNode;if(!p) return ERROR;p->adjvex=w-1;p->nextarc=G.verticesv-1.firstarc;G.verticesv-1.firstarc=p;return OK; void FindInDegree(ALGraph G)ArcNode* p;for(int i=0;i<G.vexnum;i+)p=G.verticesi.firstarc;while(p) for(int j=0;j<G.vexnum;j+)if(p->adjvex=j)indegreej+;p=p->nextarc;Status TopologicalSort(ALGraph G) SqStack S1,S2;ArcNode* p;int i,count,k;FindInDegree(G);InitStack(S1);InitStack(S2);for(i=0;i<G.vexnum;+i)if(!indegreei) Push(S1,i); count=0; while(!StackEmpty(S1)printf("第%d学期应学的课程:",count+1);while(!StackEmpty(S1)Pop(S1,i);printf("%s ",G.verticesi.data); Push(S2,i); printf("n"); count+; while(!StackEmpty(S2)Pop(S2,i);for(p=G.verticesi.firstarc;p;p=p->nextarc) k=p->adjvex; if(!(-indegreek) Push(S1,k);if(count<G.vexnum) return ERROR;else return OK;int main() printf("*n");printf(" 教学计划检验程序（拓扑排序） nn"); printf(" v1 程序设计基础 v2 离散数学 v3 数据结构n");printf(" v4 汇编语言 v5 语言设计与分析 v6 计算机原理n");printf(" v7 编译原理 v8 操作系统 v9 高等数学n");printf(" v10 线性代数 v11 普通物理 v12 数值分析nn"); printf("*n"); ALGraph T;CreateDG (T);TopologicalSort(T);return 0;3.3 调试与分析1. 运行程序打开界面如下图，并根据提示，输入学期数目：2.输入出错时显示如下：3输入正确则继续,根据界面提示输入课程的代表值：4.根据界面提示输入课程间两两间的先后关系：5 输入课程间两两间的先后关系后，则输出每学期应学的课程：6 完美运行结果：四 总结经过近三个星期的不断的学习与努力，有收获，有挫折，终于完成了教学计划安排检验程序（拓扑排序）的数据结构课程设计。从最开始确定程序设计题目到算法基本完成，从运行程序中逐步完善再到设计报告说明书的结束，每一步都是一种新的挑战，也是进步的重要历程。这次课程设计的完成，我意识到自己掌握的知识还是远远不够的，在接下来的学习期间，我会尽最大的可能去拓宽自己在计算机编程方面知识，并在不断地实践中运用自己的理论，使得理论与实践结合，提高自己的技术与能力。通过去图书馆查看相关的资料和书籍以及在网上与他人探讨，通过自己独立的思考，使程序设计一步步完善起来。我也切实认识到做程序设计必然会遇到许许多多不曾遇到过的难题，比如此次程序设计中，要查阅相关资料，明白拓扑排序的定义以及实现拓扑排序的代码，认真细致的分析题目，根据题目得到拓扑排序的排列序列，在多种思路中寻找到时间复杂度最小的方法，实现程序的最优化通过这次课程设计我受益匪浅，从中明白了一个道理：计算机程序设计只要认认真真的用心去做，其中遇到任何的问题都可以一一解决。在这次课程设计中，收获的不仅仅是技术，本次程序设计使我不仅深化理解了教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，并且在总体分析、总体结构设计、算法设计、课程设计、上机操作及程序调试等基本技能方面受到了综合训练，使我在今后的编程读写中更加的得心应手。在今后的不断学习中，不断锤炼自己的技能，使得自己更加适应现在这个信息化高速发展的时代，在未来的舞台更好的展现自己。 总的来说，在程序设计过程中，每一次的小成功都会有一份喜悦，程序的完成都是自己努力的结晶。最后，感谢指导老师不厌其烦的教导，学哥学姐的建议，网上热心人得帮助。 参考文献1严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2013.2谭浩强编著.C程序设计（第二版）.北京：清华大学出版社,1999.3 温秀梅，丁学钧编著.Visual C+面向对象程序设计教程与实验（第二版）.北京：清华大学出版社，20134机械工业出版社.拓扑学M.
