教学计划编制问题课程设计报告.doc

中北大学数据结构与算法课程设计说 明 书学 院、系：软件学院专 业：软件工程学 生 姓 名：学 号：设 计 题 目：教学计划编制问题起 迄 日 期:2013年12月9日-2013年12月20日指 导 教 师:2013 年12月 20 日1需求分析1. 在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.2. 本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程. 3.测试数据：学期总数：6；学分上限：9；本专业共开设12门课，课程号从C00到C11，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。2概要设计1.抽象数据类型图的定义如下：ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作P:void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int * );int TopologicalOrder(ALGraph G,AdjList R,struct Name name)int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ ADT Graph2.栈的定义如下：ADT Stack数据对象:D=ai|aiElemSet,i=1,2,n,n=0 数据关系:R1=ai-1 ai|ai-1,aiD,i=2,n基本操作：void InitStack (SqStack *S);int StackEmpty(SqStack S);void Push(SqStack *S, int );int Pop(SqStack *S, int *e);ADT Stack3.本程序有两个模块，调用关系简单：主程序模块 拓扑排序模块3系统完成功能及功能框图end采用第二种策略：使课程尽可能地集中在前几个学期中根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图CreateGraph（）：结合先修关系的AOV网，采用邻接链表存储菜单OUTPUT()：显示代号所对应课程及课程的先修课程前插法main拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程输出图G的信息Display(G)：将图的顶点和弧边输出 图3.1系统功能框图0C11 5 11 111067 6 4 72 1134 9 1C22C33C44C55C66C77C88C99C1010C1111C12 图3.2 邻接表对每个顶点求入度，并存入数组InDegreei中（i=0n）初始化栈Stack,Counter=0Return OKReturn ERROR依次将入度为0的顶点存入栈中对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter+)推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter+）堆栈是否为空？n个顶点全输出 Y Y N Y N Y 图3.3 拓扑排序流程图C1C4C5C7C2C3C8C9C12C10C11C6 图3.4 课程先修关系图4 详细设计1. 图的邻接表的存储表示，即结构体的定义：typedef struct ArcNodeint AdjOfV; / 该弧所指向的顶点的位置struct ArcNode *next; /指向下一条弧的指针ArcNode;typedef char VertexTypeMAXOfNAME; typedef struct /链接表VertexType data; /顶点信息int grades; /存储学分信息ArcNode *first; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VER; / 头结点typedef structAdjList ver; /vertices 存储课程名int vexnum, arcnum; / 图的当前顶点数和弧数ALGraph;2. 建立图的邻接链表：printf(请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n); for (h=0;hAdjOfV = j; p-next = G.veri.first; / 插在表头 G.veri.first = p; scanf(%s,va); getchar(); 3. 输出图的顶点和边：printf(%d个顶点, G.vexnum); for (i = 0;i G.vexnum;+i)printf(%4s, G.veri.data); printf( n%d条弧边:n,G.arcnum); for (i = 0;i %sn,G.veri.data,G.verp-AdjOfV.data); p = p-next; 4. 通过栈实现拓扑排序：int TopologicalOrder(ALGraph G,AdjList R,struct Name name) int i, k, j = 0, count, indegreeMAX_VER; SqStack S;ArcNode *p;FindInDegree(G, indegree); / 对各顶点求入度InitStack(S); / 初始化栈for (i = 0;i next)/ 对i号顶点的每个邻接点的入度减1 k = p-AdjOfV;if (!(-indegreek) / 若入度减为0,则入栈Push(S, k);if (count G.vexnum)printf(此有向图有回路无法完成拓扑排序);return 0;else printf( 为一个拓扑序列);printf(n);int q=1,Z=0;while (q = TotalOfTerms)int C = RZ.grades ;printf(n第%d个学期应学课程:,q);while (C = MaxScores)C = C + RZ+1.grades;if (Z = S.size)S.a = (int *) realloc ( S.a, (S.size + StackforMore) * sizeof(int);if ( !S.a ) exit(-1);S.top =S.a +S.size;S.size +=StackforMore;*S.top+ = x;return 1;int Pop(SqStack &S, int &x) /*出栈*/ if (S.top = S.a)return 0;x = *-S.top; return 1;int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ int i; for (i = 0;i G.vexnum;+i) if (strcmp(u,G.veri.data)=0)return i; return -1;int CreateGraph(ALGraph &G) /*采用邻接表存储结构*/ int i, j, h; VertexType va; ArcNode *p; printf(请输入教学计划的课程数: ); scanf(%d,&G.vexnum); getchar(); printf( 请输入各个课程的先修课程的总和(弧总数): ); scanf(%d,&G.arcnum); getchar(); printf( 请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):, G.vexnum,MAXOfNAME); for (i = 0;i G.vexnum;+i) scanf(%s,&G.veri.data); getchar(); G.veri.first = NULL; printf(请输入%d个课程的学分值:,G.vexnum); for (i = 0;i G.vexnum;+i) scanf(%d,&G.veri.grades);getchar(); printf(请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n); for (h=0;hAdjOfV = j; p-next = G.veri.first; / 插在表头 G.veri.first = p; scanf(%s,va); getchar(); return 1;void Display(ALGraph G) /* 输出图G的信息*/ int i; ArcNode *p; printf(有向图n); printf(%d个顶点, G.vexnum); for (i = 0;i G.vexnum;+i)printf(%4s, G.veri.data); printf( n%d条弧边:n,G.arcnum); for (i = 0;i %sn,G.veri.data,G.verp-AdjOfV.data); p = p-next; void FindInDegree(ALGraph G, int indegree) /*求顶点的入度*/ int i; ArcNode *p; for (i = 0;i G.vexnum;i+) indegreei = 0; for (i = 0;i AdjOfV+; p = p-next; struct Name char c20;name;void CmpOfStr(VertexType str,struct Name name,int n) /*让C1C12分别与12门课程对应起来*/ if(strcmp(str,name0.c)=0)printf( C程序设计); if(strcmp(str,name1.c)=0)printf( 模拟数字电路); if(strcmp(str,name2.c)=0)printf( 数据结构); if(strcmp(str,name3.c)=0)printf( C+面向对象 ); if(strcmp(str,name4.c)=0)printf( 大学英语 ); if(strcmp(str,name5.c)=0)printf( 计算机组成原理); if(strcmp(str,name6.c)=0)printf( 传感器原理); if(strcmp(str,name7.c)=0)printf( 软件工程导论); if(strcmp(str,name8.c)=0)printf( 高等数学); if(strcmp(str,name9.c)=0)printf( 线性代数); if(strcmp(str,name10.c)=0)printf( 大学物理基础); if(strcmp(str,name11.c)=0)printf( 电工技术); 4 界面设计5 源代码#include#include#include#include#define N 12#define MAXOfNAME 3 /最多字符个数#define MAX_VER 100 /最大顶点数#define StackofNUM 20 /存储空间初始分配量#define StackforMore 5 / 存储空间分配增量int TotalOfTerms ; /学期总数int MaxScores;typedef struct SqStackint *a;int *top;int size; /分配的存储空间SqStack;typedef struct ArcNodeint AdjOfV; / 该弧所指向的顶点的位置struct ArcNode *next; /指向下一条弧的指针ArcNode;typedef char VertexTypeMAXOfNAME;typedef struct /链接表VertexType data; /顶点信息int grades; /存储学分信息ArcNode *first; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VER; / 头结点typedef structAdjList ver; /vertices 存储课程名int vexnum, arcnum; / 图的当前顶点数和弧数ALGraph; /学分上限int InitStack(SqStack S) /*栈的初始化*/S.a= (int *)malloc(StackofNUM * sizeof(int);if (!S.a)exit(-1);S.top =S.a;S.size =StackofNUM;return 1;int StackEmpty(SqStack S) /*判断栈是否为空*/if (S.top = S.a)return 1;else return 0;int Push(SqStack S, int x)/*入栈*/if (S.top - S.a = S.size)S.a = (int *) realloc ( S.a, (S.size + StackforMore) * sizeof(int);if ( !S.a ) exit(-1);S.top =S.a +S.size;S.size +=StackforMore;*S.top+ = x;return 1;int Pop(SqStack S, int x) /*出栈*/if (S.top = S.a)return 0;x = *-S.top; return 1;int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ int i; for (i = 0;i G.vexnum;+i) if (strcmp(u,G.veri.data)=0)return i; return -1;int CreateGraph(ALGraph G) /*采用邻接表存储结构*/ int i, j, h; VertexType va; ArcNode *p; printf(请输入教学计划的课程数: ); scanf(%d,&G.vexnum); getchar(); printf( 请输入各个课程的先修课程的总和(弧总数): ); scanf(%d,&G.arcnum); getchar(); printf( 请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):, G.vexnum,MAXOfNAME); for (i = 0;i G.vexnum;+i) scanf(%s,&G.veri.data); getchar(); G.veri.first = NULL; printf(请输入%d个课程的学分值:,G.vexnum); for (i = 0;i G.vexnum;+i) scanf(%d,&G.veri.grades);getchar(); printf(请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n); for (h=0;hAdjOfV = j; p-next = G.veri.first; / 插在表头 G.veri.first = p; scanf(%s,va); getchar(); return 1;void Display(ALGraph G) /* 输出图G的信息*/ int i; ArcNode *p; printf(有向图n); printf(%d个顶点, G.vexnum); for (i = 0;i G.vexnum;+i)printf(%4s, G.veri.data); printf( n%d条弧边:n,G.arcnum); for (i = 0;i %sn,G.veri.data,G.verp-AdjOfV.data); p = p-next; void FindInDegree(ALGraph G, int indegree) /*求顶点的入度*/ int i; ArcNode *p; for (i = 0;i G.vexnum;i+) indegreei = 0; for (i = 0;i AdjOfV+; p = p-next; struct Name char c20;name;void CmpOfStr(VertexType str,struct Name name,int n) /*让C1C12分别与12门课程对应起来*/ if(strcmp(str,name0.c)=0)printf( c程序设计); if(strcmp(str,name1.c)=0)printf( 模拟数字电路); if(strcmp(str,name2.c)=0)printf( 数据结构); if(strcmp(str,name3.c)=0)printf( C+面向对象 ); if(strcmp(str,name4.c)=0)printf( 大学英语 ); if(strcmp(str,name5.c)=0)printf( 计算机组成原理); if(strcmp(str,name6.c)=0)printf( 传感器原理); if(strcmp(str,name7.c)=0)printf( 软件工程导论 ); if(strcmp(str,name8.c)=0)printf( 高等数学); if(strcmp(str,name9.c)=0)printf( 线性代数); if(strcmp(str,name10.c)=0)printf( 大学物理基础); if(strcmp(str,name11.c)=0)printf( 电工技术);int TopologicalOrder(ALGraph G,AdjList R,struct Name name)int i, k, j = 0, count, indegreeMAX_VER;ch