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

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

2、恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。1.2需求分析根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题输出每学期的课程。（1）用学分来实现每学期课程数大致相同；（2）根据教学计划中的课程及其关系和学分来定义图的顶点及边的结构体。（3）创建图CreateGraph（）：结合先修关系的AOV网，采用邻接表存储。（4）菜单OUTPUT()：显示代号所对应课程及课程的先修课程。（5）拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程。（6）输出图G的信息Display

3、(G)：将图的顶点和弧边输出。1.3本程序包括2个模块：主程序模块和拓扑排序模块。拓扑排序模块主程序模块2. 本设计所采用的数据结构(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

4、) void puanduan(VertexType str,struct Name name,int n)(7) int InitStack(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

5、() /主函数3. 功能模块详细设计3.1详细设计思想12 main() 1 3 411 2 5 6 7 8 9103.2 核心代码3.21数据类型定义（1）头结点，表结点，邻接表的定义typedef char VertexTypeMAX_NAME; int TotalTerms ;                       /学期总数int MaxScores; 

6、                        /学分上限typedef struct ArcNode       int adjvex;              &#

7、160;         / 该弧所指向的顶点的位置 弧的节点结构       struct ArcNode *nextarc;           /指向下一条弧的指针ArcNode;              

8、60;               / 表结点 typedef struct VNode                              

9、VertexType data;                   /顶点信息       int grades;                    &#

10、160;   /存储学分信息       ArcNode *firstarc;                 /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;       / 头结点 typedef struct ALGraph /邻接表

11、0;      AdjList vertices;                  /vertices 存储课程名       int vexnum, arcnum;            

12、0;   / 图的当前顶点数和弧数ALGraph;邻接表的基本操作：void CreatGraph(ALGraph *);创建邻接表void FindInDegree(ALGraph , int * );求一个结点的入度int TopoSort(ALGraph G,AdjList Temp,struct Name name) /拓扑排序（2）栈的定义：typedef int SElemType;   / 栈类型#define Stack_NUM 20     /存储空间初始分配量#define Stack_More

13、NUM 5   / 存储空间分配增量typedef struct SqStack       SElemType *base;            SElemType *top;              int stacksize;     &#

14、160;  /分配的存储空间SqStack;基本操作：void InitStack (SqStack *S);栈的初始化int StackEmpty(SqStack S);判断栈是否为空void Push(SqStack *S, int );入栈操作int Pop(SqStack *S, int *e);出栈操作3.22系统主要子程序详细设计（1）主函数模块设计void main() ALGraph G; AdjList Temp; struct Name nameN="C1","C2","C3","C4"

15、;,"C5","C6","C7","C8","C9","C10","C11","C12" OUTPUT(); printf("*教学计划编制问题*n" ); printf( "请输入学期总数:"); scanf("%d",&TotalTerms); printf("请输入学期的学分上限:"); scanf("%d",&Ma

16、xScores); CreateGraph(G); Display(G); TopoSort(G,Temp,name); printf("OKn"); scanf("*c");（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); / 初始化

17、栈 for (i = 0;i < G.vexnum;+i) /建零入度顶点栈S if (!indegreei) Push(S, i); / 入度为0者进栈 count = 0; / 对输出顶点计数 while (!StackEmpty(S) Pop(S, i); printf("%s(%d分),",G.verticesi.data,G.verticesi.grades); Tempj+ = G.verticesi; /将当前的拓扑序列保存起来 +count; / 输出i号顶点并计数 for (p =G.verticesi.firstarc; p; p=p->ne

18、xtarc)/ 对i号顶点的每个邻接点的入度减1 k = p->adjvex; if (!(-indegreek) / 若入度减为0,则入栈 Push(S, k); if (count < 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( "n课程编制完成!"); q+; return OK;3.3 程序运行结果（1）主界面设计显示课程代号所对应课程及先修课