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

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

1、8A Uni-20-20 学年第一学期工作计划 9864 b0 中北大学 数据结构与算法课程设计 说 明 书 学 院、系：软件学院 专 业：软件工程 学 生 姓 名：学 号：设 计 题 目：教学计划编制问题 起 迄 日 期:2013 年 12 月 9 日-2013年 12 月 20日 指 导 教 师:2013 年 12 月 20 日 1 需求分析 1.在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接8A Uni-20-20 学年第一学期工作计划 9864 b1 表的头结点存储每门课的信息.2.本程序的目的是为用户编排课程,根据用户输入的信息来编排

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=VR VR=(v,w)|v,wV,(v,w)表示 v 和 w 之间存在直接先修关系 基本操作 P:void CreatGraph(ALGraph*);void FindInDegree(ALGraph,int*);int TopologicalOrder(ALGraph G,A

3、djList R,struct Name name)int LocateVex(ALGraph G,VertexType u)/*查找图中某个顶点位置*/ADT Graph 2.栈的定义如下：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 Stack 3.本程序有两个模块，调用关

4、系简单：主程序模块 拓扑排序模块 8A Uni-20-20 学年第一学期工作计划 9864 b2 3 系统完成功能及功能框图 图 3.1 系统功能框图 end 采用第二种策略：使课程尽可能地集中在前几个学期中 根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体 创建图 CreateGraph（）：结合先修关系的 AOV 网，采用邻接链表存储 菜单 OUTPUT()：显示代号所对应课程及课程的先修课程 前插法 main 拓扑排序 TopoSort(G)：将课程排序后并决定出每学期所学课程 输出图 G 的信息 Display(G)：将图的顶点和弧边输出 8A Uni-20-20 学年第一学

5、期工作计划 9864 b3 图 3.2 邻接表 0 C1 1 C2 2 C3 3 C4 4 C5 5 C6 6 C7 7 C8 8 C9 9 C10 10 C11 11 C12 1 5 11 11 10 6 7 6 4 7 2 11 3 4 9 8A Uni-20-20 学年第一学期工作计划 9864 b4 Y Y N Y N Y 图 3.3 拓扑排序流程图 对每个顶点求入度，并存入数组 InDegreei中（i=0n）初始化栈 Stack,Counter=0 Return OK Return ERROR 依次将入度为 0 的顶点存入栈中 对以 i 号顶点为尾弧的每个邻接点的入度减 1，并将入

6、度减 1 后为零的顶点号压入栈中，输出 i，计数器加 1(Counter+)推出栈顶的一个元素（入度为零的顶点号）至 i，输出 i，计数器加 1（Counter+）堆栈是否为空？n 个顶点全输出 8A Uni-20-20 学年第一学期工作计划 9864 b5 图 3.4 课程先修关系图 4 详细设计 1.图的邻接表的存储表示，即结构体的定义：typedef struct ArcNode int AdjOfV;/该弧所指向的顶点的位置 struct ArcNode*next;/指向下一条弧的指针 ArcNode;typedef char VertexTypeMAXOfNAME;typedef s

7、truct /链接表 VertexType data;/顶点信息 int grades;/存储学分信息 ArcNode*first;/指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VER;/头结点 typedef struct AdjList ver;/vertices 存储课程名 C1 C4 C5 C7 C2 C3 C8 C9 C12 C10 C11 C6 8A Uni-20-20 学年第一学期工作计划 9864 b6 int vexnum,arcnum;/图的当前顶点数和弧数 ALGraph;2.建立图的邻接链表：printf(请输入下列课程的先修课程(无先修课程输入

8、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.通过栈实现拓扑排序：8A Uni-20-20 学年第一学期工作计划 9864 b

9、7 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(此有向图有回路无法完成拓扑排序);retur

10、n 0;else printf(为一个拓扑序列);printf(n);8A Uni-20-20 学年第一学期工作计划 9864 b8 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

11、.top+=x;8A Uni-20-20 学年第一学期工作计划 9864 b10 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;Vertex

12、Type 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)8A Uni-20-20 学年第一学期工作计划 9864 b11 scanf(%s,&G.veri.data);getchar();G.veri.first=NULL;pr

13、intf(请输入%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 的信息*/8A Uni-20-20 学年第一学期工作计划 9864 b12 int i;ArcNo

14、de*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;str

15、uct Name 8A Uni-20-20 学年第一学期工作计划 9864 b13 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(strcm

16、p(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(

17、电工技术);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 SqStack 8A Uni-20-20 学年第一学期工作计划 9864 b14 int *a;int *top;int size;/分

18、配的存储空间 SqStack;typedef struct ArcNode int AdjOfV;/该弧所指向的顶点的位置 struct ArcNode*next;/指向下一条弧的指针 ArcNode;typedef char VertexTypeMAXOfNAME;typedef struct /链接表 VertexType data;/顶点信息 int grades;/存储学分信息 ArcNode*first;/指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VER;/头结点 typedef struct AdjList ver;/vertices 存储课程名 int v

19、exnum,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)/*判断栈是否为空*/8A Uni-20-20 学年第一学期工作计划 9864 b15 if(S.top=S.a)return 1;else return 0;int Push(SqStack S,int x)/*入

20、栈*/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;

21、+i)if(strcmp(u,G.veri.data)=0)return i;return-1;int CreateGraph(ALGraph G)/*采用邻接表存储结构*/int i,j,h;8A Uni-20-20 学年第一学期工作计划 9864 b16 VertexType va;ArcNode*p;printf(请输入教学计划的课程数:);scanf(%d,&G.vexnum);getchar();printf(请输入各个课程的先修课程的总和(弧总数):);scanf(%d,&G.arcnum);getchar();printf(请输入%d 个课程的课程号(最多%d 个字符,字母+数字

22、如 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;8A Uni-20-20 学年第一学期工作计划 9864 b17 p-next=G.veri.fir

23、st;/插在表头 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,

24、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,na

25、me2.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(s

26、trcmp(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;char q=1,Z=0;8A Uni-20-20 学年第一学期工作计划 9864 b19 SqStack S;ArcNode*p;FindInDegree(G,indegree);/对各顶点求入度 InitStack(S);/初始化栈 for(i=0;i nex

27、t)/对 i 号顶点的每个邻接点的入度减 1 k=p-AdjOfV;if(!(-indegreek)/若入度减为 0,则入栈 Push(S,k);if(count G.vexnum)printf(此有向图有回路无法完成拓扑排序);return 0;else printf(为一个拓扑序列);printf(n);while(q=TotalOfTerms)int C=RZ.grades;printf(n 第%d 个学期应学课程:,q);8A Uni-20-20 学年第一学期工作计划 9864 b20 while(C=MaxScores)C=C+RZ+1.grades;if(Z G.vexnum)Cm

28、pOfStr(RZ.data,name,N);/*让 C1C12 分别与 12 门课程对应起来*/+Z;printf(n);if(q=TotalOfTerms)printf(nOK Over!);q+;return 1;/*/int main()ALGraph G;AdjList R;struct Name nameN=C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12;printf(*教学计划编制问题*n);printf（*製作人 张启尧 董茁华 *n）;printf(请输入学期总数:);scanf(%d,&TotalOfTerms);getchar();printf(请输入学期的学分上限:);scanf(%d,&MaxScores);getchar();CreateGraph(G);8A Uni-20-20 学年第一学期工作计划 9864 b21 Display(G);TopologicalOrder(G,R,name);return 0;8 心得体会 青山埋白骨，绿水吊忠魂。