《数据结构课程设计报告书--教学计划编制问题》由会员分享，可在线阅读，更多相关《数据结构课程设计报告书--教学计划编制问题（26页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告书数据结构课程设计报告书教学计划编制问题题目：制定教学计划1.1.内容摘要内容摘要摘要摘要：首先利用拓扑排序对课程先后顺序进行分析，邻接表为主要存储结构，栈为主要辅助结构。给出课程的先后关系，即 AOV 网，然后进行拓扑排 序，但当有向图中存在环时，无法查找该图的一个拓扑排序。当图中所有定 点全部输出，表示对该图排序成功。实现拓扑排序算法时，相应的建立邻接 表存储 AOV 网。为了避免重复检测入度为零的顶点，建立一个栈来对入度为 零的点进行存放。根据课程先后关系，对各个学期的课程进行拓扑排序，输 出。2.2.索引关键词索引关键词关键词：邻接表存储，栈的应用，拓扑排序。目 录
2、1.题目要求及设计要求- 12.系统完成功能及功能框图- 243.核心算法及说明- 5214.运行及测试结论- 22235.参考资料- 236.后记- 23- 1 -第一部分：课程设计题目要求1.1 课程设计目的大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。在这样的前提下设计一个教学计划编制程序。1.2 课程设计的实验环境硬件要求能运行 Windows 9.X 操作系统的微
3、机系统。软件： 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 -第三部分：系统完成功能及功
4、能框图end采用第二种策略：使课程尽可能地集中在前几个学期中根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图 CreateGraph（）：结合先修关系的AOV 网，采用邻接链表存储菜单 OUTPUT()：显示代号所对应课程及课程的先修课程前插法main拓扑排序 TopoSort(G)：将课程排序后并决定出每学期所学课程输出图 G 的信息 Display(G)：将图的顶点和弧边输出- 3 -图 1：某专业的学生必须学习的课程图 2：表示课程之间优先关系的有向图C1，2C4C5C7C2C3C8C9C12C10C11C6- 4 -图 3：邻接表0C11C22C33C44C55C66C
5、77C88C99C1010C1111C121 5 11 111067 6 4 72 1134 9 - 5 -第四部分：详细设计详细设计1程序主要包括五个模块1）、图的邻接表的存储表示，即结构体的定义）、图的邻接表的存储表示，即结构体的定义typedef char VertexTypeMAX_NAME;typedef struct ArcNodeint adjvex; / 该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针ArcNode; / 链表结点typedef struct /链接表VertexType data; /顶点信息int grades;
6、 /存储学分信息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
7、; / 插在表头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）、通过栈实现拓扑排序）、通过栈实现拓扑排序FindInDegree(G, indegree); / 对各顶点求入度InitStack(S); / 初始化栈for (i = 0;i nextarc)/ 对 i 号顶点的每个邻接点的入度减 1k = p-adj
8、vex;- 8 -if (!(-indegreek) / 若入度减为 0,则入栈Push(S, k);if (count #include#include- 11 -#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define MAX_NAME 3#define MAXCLASS 100 /顶点字符串的最大长度#define MAX_VERTEX_NUM 100 /最大顶点数#define N 12typedef char VertexTypeMAX_NAME;int TotalTerms ; /学期总数int
9、MaxScores; /学分上限/* -图的邻接表存储表示- */typedef struct ArcNodeint adjvex; / 该弧所指向的顶点的位置 弧的节点结构struct ArcNode *nextarc; /指向下一条弧的指针ArcNode; / 链表结点typedef struct /链接表VertexType data; /顶点信息int grades; /存储学分信息- 12 -ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM; / 头结点typedef structAdjList verti
10、ces; /vertices 存储课程名int vexnum, arcnum; / 图的当前顶点数和弧数ALGraph;void OUTPUT()int s;printf(“tt 教学计划编制菜单 n“);printf(“tt 课程代码 | 课程名称 |优先课程 n“);printf(“ttC1 |程序设计基础 | 无 n“);printf(“ttC2 |离散数学 | C1 n“);printf(“ttC3 |数据结构 | C1，C2 n“);printf(“ttC4 |汇编语言 | C1 n“);printf(“ttC5 |语言的设计和分析 | C3，C4 n“);printf(“ttC6
11、|计算机原理 | C11 n“);printf(“ttC7 |编译原理 | C5，C3 n“);printf(“ttC8 |操作系统 | C3，C6 n“);printf(“ttC9 |高等数学 | 无 n“);printf(“ttC10 |线性代数 | C9 n“);printf(“ttC11 |普通物理 | C9 n“);- 13 -printf(“ttC12 |数值分析 | C9,C10,C1 n“);printf(“press any numkey to continue:“);scanf(“%d“,/* 查找图中某个顶点位置 */int LocateVex(ALGraph G, Ve
12、rtexType u)int i;for (i = 0;i adjvex = j;p-nextarc = G.verticesi.firstarc; / 插在表头G.verticesi.firstarc = p;scanf(“%s“,va);- 14 -return OK;/* 输出图 G 的信息*/void Display(ALGraph G)int i;ArcNode *p;printf(“有向图n“);printf(“%d 个顶点“, G.vexnum);for (i = 0;i %sn“,G.verticesi.data,G.verticesp-adjvex.data);p = p-nextarc;/*求顶点的入度*/- 15 -void FindInDegree(ALGraph G, int indegree)int i;ArcNode *p;for (i = 0;i adjvex+;p = p-nextarc;struct Namechar c20;name;/*栈定义*/typedef int SElemType; / 栈类型#define Stack
