数据结构课程设计(教学计划编制问题)报告.doc

《数据结构课程设计(教学计划编制问题)报告.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计(教学计划编制问题)报告.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:张宁学 号：学 院:软件学院专 业:软件工程题 目:教学计划编制问题指导教师何志英2011年12月20日1. 设计任务概述1.1问题描述大学的每个专业都要制定教学计划。针对软件工程本专业制定一个教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。1.2需求分析根据问题描述及要求，可知设计中需要定义先修关

2、系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题输出每学期的课程。（1）用学分来实现每学期课程数大致相同；（2）根据教学计划中的课程及其关系和学分来定义图的顶点及边的结构体。（3）创建图CreateGraph（）：结合先修关系的AOV网，采用邻接表存储。（4）菜单OUTPUT()：显示代号所对应课程及课程的先修课程。（5）拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程。（6）输出图G的信息Display(G)：将图的顶点和弧边输出。1.3本程序包括2个模块：主程序模块和拓扑排序模块。拓扑排序模块主程序模块2. 本设计

3、所采用的数据结构(1)void OUTPUT() /显示代号所对应课程及课程的先修课程(2) int LocateVex(ALGraph G, VertexType u) /查找图中某个顶点位置(3) int CreateGraph(ALGraph G) /采用邻接表存储结构(4) void Display(ALGraph G) /输出图G的信息(5) void FindInDegree(ALGraph G, int indegree) /求顶点的入度(6) void puanduan(VertexType str,struct Name name,int n)(7) int InitStac

4、k(SqStack &S) /栈的初始化(8) int StackEmpty(SqStack S) /判空(9) int Pop(SqStack &S, SElemType &e) /出栈(10) int Push(SqStack &S, SElemType e) /入栈(11) int TopoSort(ALGraph G,AdjList Temp,struct Name name) /拓扑排序(12) void main() /主函数3. 功能模块详细设计3.1详细设计思想12 main() 1 3 411 2 5 6 7 8 9103.2 核心代码3.21数据类型定义（1）头结点，表结点

5、，邻接表的定义typedef char VertexTypeMAX_NAME; int TotalTerms ; /学期总数int MaxScores; /学分上限typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 弧的节点结构 struct ArcNode *nextarc; /指向下一条弧的指针ArcNode; / 表结点typedef struct VNode VertexType data; /顶点信息 int grades; /存储学分信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode, AdjList

6、MAX_VERTEX_NUM; / 头结点typedef struct ALGraph /邻接表 AdjList vertices; /vertices 存储课程名 int vexnum, arcnum; / 图的当前顶点数和弧数ALGraph;邻接表的基本操作：void CreatGraph(ALGraph *);创建邻接表void FindInDegree(ALGraph , int * );求一个结点的入度int TopoSort(ALGraph G,AdjList Temp,struct Name name) /拓扑排序（2）栈的定义：typedef int SElemType; /

7、栈类型#define Stack_NUM 20 /存储空间初始分配量#define Stack_MoreNUM 5 / 存储空间分配增量typedef struct SqStack SElemType *base; SElemType *top; int stacksize; /分配的存储空间SqStack;基本操作：void InitStack (SqStack *S);栈的初始化int StackEmpty(SqStack S);判断栈是否为空void Push(SqStack *S, int );入栈操作int Pop(SqStack *S, int *e);出栈操作3.22系统主要子程

8、序详细设计（1）主函数模块设计void main() ALGraph G; AdjList Temp; struct Name nameN=C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12; OUTPUT(); printf(*教学计划编制问题*n ); printf( 请输入学期总数:); scanf(%d,&TotalTerms); printf(请输入学期的学分上限:); scanf(%d,&MaxScores); CreateGraph(G); Display(G); TopoSort(G,Temp,name); printf(OKn); scanf(*c)

9、;（2）拓扑排序模块设计int TopoSort(ALGraph G,AdjList Temp,struct Name name) int i, k, j = 0, count, indegreeMAX_VERTEX_NUM; SqStack S; ArcNode *p; FindInDegree(G, indegree); / 对各顶点求入度 InitStack(S); / 初始化栈 for (i = 0;i nextarc)/ 对i号顶点的每个邻接点的入度减1 k = p-adjvex; if (!(-indegreek) / 若入度减为0,则入栈 Push(S, k); if (coun

10、t G.vexnum) printf(此有向图有回路无法完成拓扑排序); return ERROR; else printf( 为一个拓扑序列); printf(n); int q=1,Z=0; while (q = TotalTerms) int C = TempZ.grades ; printf(n第%d个学期应学课程:,q); while (C = MaxScores) C = C + TempZ+1.grades; if (Z G.vexnum) puanduan(TempZ.data,name,N); +Z; printf(n); if (q = TotalTerms)printf(

11、 n课程编制完成!); q+; return OK;3.3 程序运行结果（1）主界面设计显示课程代号所对应课程及先修课程。（2）输入1-16的任意数回车（3）按要求输入学期数，学分上限，课程数，课程号和各课程的学分：（4）输入各课程先修课程，回车，运行结果：4. 课程设计心得、存在问题及解决方法经过这次这次课程设计，我学到很多。首先是一个总体思想，先确定总体结构。用邻接表把图存储起来，然后用拓扑排序实现先修关系。其中还用到了栈，进栈是要判断栈是否为满，若满则需要再开辟存储空间，如果开辟失败，存储也就失败了。出栈要判断栈是否空，若空，则出栈失败，且返回错误。一开始程序不能运行，后来才找见错误，原来我错加了“&”符号，可见一点疏忽就会导致整个程序无法运行。以后要更加细心的写程序啦！