内容发布更新时间 : 2024/12/23 13:38:34星期一 下面是文章的全部内容请认真阅读。

计算机科学与技术学院实验课程

实验报告

实验课名称：数据结构与程序设计实验 实验名称：教学计划编制问题 班级： 学号： 实验类型：设计性实验 姓名： 时间： 一、问题描述 教学计划编制的主要任务是根据需要完成的课程的先修关系、每学期开设的课程总数及总的学习时间，制定出教学计划。需事先的基本功能如下。 ? 课程进修目录的读入。 ? 课程进修目录的编辑，如课程增加、删除、信息修改等。 ? 满足一定条件的教学计划的输出。 ②设计要求 ? 设学期总数不超过8，课程总数不超过5，设计一份课程进修单，包括：学期总数、一学期的学分上限、每门课的课程编号、学分和直接先修课程的课程号。 ? 实现上述基本功能。 ? 按各学期中的学习负担尽量均匀地制定教学计划。 ? 按尽可能短的时间完成学习，制定教学计划。 ? 如果无解，报告适当信息。 测试样例的关系图如下图所示： C4C5C13C1C2C3C7C14C12C8C10C6C9 C11 二、数据结构设计 程序中建立的抽象数据类型有以下几种： 1.由测试样例的关系图可以看出课程之间的关系是非线性且有序的，可以用有向图来描述。在对图中所存储的课程进行排序时，使用拓扑排序可以得到所需顺序，而拓扑排序可以用顶点入度为0的方法实现，所以为实现拓扑排序的顶点的存放，创建一个线性表来存放。 2.有向图的每个结点都代表一门课程，需要描述的属性有课程名，课程编号和对应的学分，程序中用结构体描述。 typedef struct { AdjList vertices,vertices2,vertices3; //分别存课程号，课程名和 学分； int vexnum,arcnum; int kind; } ALGraph; 3.结点之间的弧也用结构体描述，数据成员包括弧指向的顶点位置，指向下一条弧的指针和权值指针。 typedef struct ArcNode //弧结构； { int adjvex; //该弧所指向的顶点的位置; struct ArcNode * nextarc; //指向下一条弧的指针; InfoType * info; //网的权值指针; } ArcNode; 4.在课程安排时需要让所有课程按一定顺序入栈再出栈，用到了栈结构。 typedef struct SqStack { SElemType *base; SElemType *top; int stacksize; } SqStack; 三、算法设计 程序的算法分为以下几个部分： 1.输入部分：输入教学计划编制所需的参数，包括学期总数、一学期的学分上限、每门课的课程编号、学分和直接先修课程的课程号。学期总数和学分上限存储在两个int值中，课程的相关信息存储在结构体中。部分代码如下： printf(\请输入学期总数:\ scanf(\ printf(\请输入每学期的学分上限:\ scanf(\CreateGraph(f); 其中CreateGraph函数是输入课程信息的函数，实现了输入并将其存储在结构体的功能。 2.建立有向图，将输入的课程信息存储在有向图中。 void Display(ALGraph G) { int i; ArcNode * p; switch(G.kind) { case DG: printf(\有向图\\n\ } printf(\个顶点：\\n\ for(i=0; iadjvex].data); p=p->nextarc; } printf(\ } } 3.完成图的构建之后，使用拓扑排序得到有序课程表。每当节点入度为0，输出该节点存储的课程信息，并删除该节点，同时与该节点相连的各个顶点的入度均减1。重复以上操作直到图为空。排序成功，输出排序后的顶点序列；否则，若入度为0的节点数小于节点总数，则不存在满足条件的课程表，输出提示信息，结束程序。部分代码如下： for(i=0; inextarc) { k=p->adjvex; if(!(--indegree[k])) Push(&S,k); } } if(count