数据结构实验报告十—教学计划编制问题23654.pdf

《数据结构实验报告十—教学计划编制问题23654.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告十—教学计划编制问题23654.pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、问题描述：若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果 A 课程是 B 课程的先修课程，那么 A 到 B 之间有一条有向边从 A指向 B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。基本要求：（1）输入参数：课程总数，每门课的课程号（固定占 3 位的字母数字串）和直接先修课的课程号。（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。一、需求分析：本程序需要基于图的基本操作来实现 二、概要设计：抽象数据类型：为实现上述功能需建立一个结点类，线性表类，图

2、类。算法的基本思想：1、图的构建：建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有 n 个点，则建立 n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。2、Topsort 算法：先计算每个点的入度，保存在数组中。找到第一个入度为 0 的点，将该点所连的各点的入度减一。再在这些点中找入度为 0 的点。如果找到，重复上述操作。如果找不到，则跳出 while 循环，再搜索其他的点，看入度是否为 0。再重复上述操作，如果所有的入度为 0 的点都被寻找

3、到，但个数少于输入顶点的个数，说明该图存在环。程序的流程 程序由三个模块组成：输入模块：读入图的信息（顶点和边，用线性表进行存储）。处理模块：topsort 算法。输出模块：将结果输出。三、详细设计 算法的具体步骤：class Nodeead-node=ch;linei.head-position=i;void pushEdge()ead-node=ch1)pos1=j;ead-node=ch2)pos2=linej.head-position;break;linepos1.insert(pos2,ch2);void topsort()ead;while(p-next!=NULL)dp-nex

4、t-position+;ead-nodenext!=NULL)k=p-next-position;dk-;ead-node=ch;linei.head-position=i;void pushEdge()ead-node=ch1)pos1=j;ead-node=ch2)pos2=linej.head-position;break;linepos1.insert(pos2,ch2);void topsort()ead;while(p-next!=NULL)dp-next-position+;ead-nodenext!=NULL)k=p-next-position;dk-;/当起点被删除，时后面的点的入度-1 if(dk=0)dk=top;top=k;p=p-next;coutendl;if(mnumVertex)/输出点的个数小于输入点的个数，不能完全遍历 cout网络存在回路endl;delete d;int main()int n,m;cout请输入节点的个数和边的个数nm;Graph G(n,m);();();();system(pause);return 0;