《教学计划编制数据结构课程设计报告》由会员分享，可在线阅读，更多相关《教学计划编制数据结构课程设计报告（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计教学计划编制问题（图的应用）班级学号21333班2133326学生姓名孙丽提交日期2015年7月23日成 绩 计算机与通信工程学院目 录一 需求分析11.设计任务12.功能模块图13.流程图24.目标测试2二 详细设计41.运行环境42.开发工具43.涉及知识点44.数据结构定义及基本操作45.函数调用关系图56.伪码流程6三 调试分析91.调试过程中遇到的问题与解决方法92算法的时空分析93.改进思想94.经验体会9四 用户手册9五 测试结果111.输入112.输出14六 附录16七 参考文献23一、需求分析1、设计任务教学计划编制问题（图的应用）问题描述大学的每个专业都要制
2、定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。实现提示输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。应允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户
3、指定的文件中。计划的表格格式可以自己设计。可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。2、功能模块图主程序模块栈的定义及操作拓扑排序模块图的定义及操作1、栈的顺序存储表示2、构造空栈3、判断栈是否为空4、入栈 5、出栈1、图的邻接表存储表示2、构造图3、求图中各节点的入度1、在有向图中选个没有前驱顶点且输出。2、从图中删除该顶点和所有以它为尾的弧。CreateGraph（）：构造图 InitStack（）：构造一个空栈 StackEmpty（）：判断是否为空栈 Push（）：入栈Pop（）：出栈 FindInDegree（）：求
4、顶点的入度TopologicalSort（）：输出G顶点的拓扑排序结果3、流程图（具体流程图见详细设计伪码流程）主程序构造图GreateGraph ( )拓扑排序TopologicalSort开始结束4、目标测试正确测试：错误测试：二、详细设计1、运行环境：（1）WINDOWS 7系统（2）C-Free 5.02、开发工具： C语言3、涉及知识点：(1) 栈。用到有关栈的操作有初始化栈、判断栈是否为空、入栈和出栈。其中栈主要用来存放入度为零的顶点，即当前无先修关系可以编排的课程。(2) 图。用到有关图的操作有创建图、统计图中各顶点的入度。利用邻接表作为有向图的存储结构，且在头结点中增加一个存放
5、顶点入度的数组（indegree）。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点入度减一来实现。(3) 拓扑排序。 （a）在有向图中选一个没有前驱的顶点且输出之。 （b）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止，后一种情况则说明有向图中存在环。4、数据结构定义及基本操作A.所用存储结构及宏定义：#define MAX_VERTEX_NUM 100 /最大课程总数#define STACK_INIT_SIZE 100 /存储空间的初始分配量#define STACKINCREMENT 10 /存
6、储空间的分配增量/图的邻接表存储表示typedef struct ArcNode int adjvex;/该弧所指向顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针ArcNode;typedef struct VNodechar name24;/课程名int classid; /课程号int credit;/课程的学分 int indegree;/该结点的入度 int state;/该节点的状态，1代表已学，0代表未学 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef st
7、ructAdjList vertices;/顶点向量int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;typedef int ElemType;/栈的顺序存储表示typedef struct /栈ElemType *base;ElemType *top;int stacksize;SqStack;B.程序中各函数的简要说明：（1） void CreatGraph(ALGraph &G)构建图。先输入各顶点（课程）的信息，包括课程名、课程号、课程学分。再输入弧信息（先修关系），将弧中顶点赋为弧尾，相应入度加1.最后输出构建好的邻接表。（2） void InitStack(
8、SqStack &S)构造空栈int StackEmpty(SqStack &S)判断是否为空栈void Push(SqStack &S,int e)入栈 int Pop(SqStack &S, int *e)出栈（3） void FindInDegree(ALGraph G, int indegree)求图中各节点的入度。从每个节点的第一条依附于该节点的弧出发，将该节点对应的入度加1，接着指向下一条弧执行同样的操作，直至指针为空。（3）void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)按课程尽可能集中到前几个学期进行编排。当
9、每个学期的学分总数不超过学分上限时，在有向图中选一个没有前驱的顶点（课程）且输出之。从图中删除该顶点（课程）和所有以它为尾的弧。当某学期的学分已满时，进入下一学期的编排。重复上述几步，直至全部顶点（课程）均已输出，或者当前图中不存在无前驱的顶点（课程）为止，后一种情况则说明有向图中存在环。（4）void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)按课程尽量均匀分布编排。当每个学期的学分总数不超过学分上限且课程数不超过课程数上限时，在有向图中选一个没有前驱的顶点（课程）且输出之。从图中删除该顶点（课程）和所有以它为尾的弧。当某学期
10、的学分已满或课程数已满时，进入下一学期的编排。重复上述几步，直至全部顶点（课程）均已输出，或者当前图中不存在无前驱的顶点（课程）为止，后一种情况则说明有向图中存在环。（5）int main()主函数。在主函数中输出交互界面，要求用户输入各项信息。调用CreateGraph函数创建图，之后根据用户选择调用TopologicalSort_1或者TopologicalSort_2函数进行拓扑排序并输出编排结果，写入文件中。5、函数调用关系图Main函数GreateGraph ( )TopologicalSort_1或TopologicalSort _2FILE *fpFindInDegree ( )InitStack ( )Push ( )Pop ( )StackEmpty ( )6、伪码流程（1）void CreatG
