数据结构与程序设计专题实验报告 1 实验报告 一、实验任务 实验题目：图的基本操作及教学计划的编制 二、实验内容 实验四：图的基本操作及教学计划编制问题 （一）实验目的：掌握图的基本操作 （二）基本要求：实现必要的图的基本操作，编写教学计划编制程序，输出正确结果。 （三）内容提要： 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 （ 1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3 位的字母数字串）、学分和直接先修课的课程号。 （ 2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。 （ 3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 （ 4）测试数据：学期总数6；学分上限10；共开设12 门课，课程号从C1-C12,学分顺序为 2,3,4,3,2,3,4,4,7,5,2,3。 先修关系见教材（严蔚敏-数据结构-C 语言版）图 7.26.但程序不能仅局限于该测试数据。 三、要点分析 题目中涉及的主要知识点有： (1)栈。用到有关栈的操作有初始化栈、判断栈是否为空、入栈和出栈。其中栈主要用来存放入度为零的顶点，即当前无先修关系可以编排的课程。 (2)图。用到有关图的操作有创建图、统计图中各顶点的入度。利用邻接表作为有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree）。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点入度减一来实现。 (3)拓扑排序。 （ a）在有向图中选一个没有前驱的顶点且输出之。 （ b）从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止，后一种情况则说明有向图中存在环。 2 四、程序的算法描述 1、所用存储结构及宏定义： #define MAX_VERTEX_NUM 100 //最大课程总数 #define STACK_INIT_SIZE 100 //存储空间的初始分配量 #define STACKINCREMENT 10 //存储空间的分配增量 typedef struct ArcNod...
