数据结构课程设计报告书--教学计划编制问题

数据结构课程设计报告书教学计划编制问题题目：制定教学计划1.内容摘要摘要：首先利用拓扑排序对课程先后顺序进行分析，邻接表为主要存储结构，栈为主要辅助结构。给出课程的先后关系，即 AOV 网，然后进行拓扑排序，但当有向图中存在环时，无法查找该图的一个拓扑排序。当图中所有定点全部输出，表示对该图排序成功。实现拓扑排序算法时，相应的建立邻接表存储 AOV 网。为了避免重复检测入度为零的顶点，建立一个栈来对入度为零的点进行存放。根据课程先后关系，对各个学期的课程进行拓扑排序，输出。2.索引关键词关键词：邻接表存储，栈的应用，拓扑排序。目 录1.题目要求及设计要求- 12.系统完成功能及功能框图- 243.核心算法及说明- 5214.运行及测试结论- 22235.参考资料- 236.后记- 23- 1 -第一部分：课程设计题目要求1.1 课程设计目的大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。在这样的前提下设计一个教学计划编制程序。1.2 课程设计的实验环境硬件要求能运行 Windows 9.X 操作系统的微机系统。软件： Microsoft Visual C+ 6.0第二部分：设计要求1.输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占 3 位的字母数字串）学分和直接先修课的课程号。2.允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。3.若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。测试数据：学期总数：6学分上限：10该专业共开设 12 门课，课程号从 C1-C12学分顺序为 2，3，4，3，2，3，4，4，7，5，2，3- 2 -第三部分：系统完成功能及功能框图end采用第二种策略：使课程尽可能地集中在前几个学期中根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图 CreateGraph（）：结合先修关系的AOV 网，采用邻接链表存储菜单 OUTPUT()：显示代号所对应课程及课程的先修课程前插法main拓扑排序 TopoSort(G)：将课程排序后并决定出每学期所学课程输出图 G 的信息 Display(G)：将图的顶点和弧边输出- 3 -图 1：某专业的学生必须学习的课程图 2：表示课程之间优先关系的有向图C1，2C4 C5C7C2C3C8C9C12C10C11C6- 4 -图 3：邻接表0 C11 C22 C33 C44 C55 C66 C7 7 C8 8 C99 C1010 C1111 C12 1 5 11 11 1067 6 4 72 11 34 9 - 5 -第四部分：详细设计1程序主要包括五个模块1）、图的邻接表的存储表示，即结构体的定义typedef char VertexTypeMAX_NAME;typedef struct ArcNodeint adjvex; / 该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针ArcNode; / 链表结点typedef struct /链接表VertexType data; /顶点信息int grades; /存储学分信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM; / 头结点typedef structAdjList vertices; /vertices 存储课程名int vexnum, arcnum; / 图的当前顶点数和边数ALGraph;- 6 -2）、利用前插法，建立图的邻接链表printf(“请输入下列课程的先修课程( 无先修课程输入 0 结束后也输入 0)n“);for (k=0;kadjvex = j;p-nextarc = G.verticesi.firstarc; / 插在表头G.verticesi.firstarc = p;scanf(“%s“,va);3）、输出图的顶点和边printf(“%d 个顶点“, G.vexnum);for (i = 0;i %sn“,G.verticesi.data,G.verticesp-adjvex.data);p = p-nextarc;4）、通过栈实现拓扑排序FindInDegr