教学专项计划编制问题优秀课程设计优质报告.docx

课程设计(论文)

题 目 名 称 教学计划编制问题
课 程 名 称 数据结构课程设计
学 生 姓 名
学 号
系 、专 业 信息工程系、通信工程类
指 导 教 师

12 月 23 日
摘 要
教学计划是学校确保教学质量和人才培养关键，也是组织教学过程、安排教学过程、安排教学任务、确定教学编制基础依据和课程安排具体形式。是稳定教学秩序、提升教学质量关键确保。从教学计划设计、实施等方面，说明了怎样搞好教学管理，从而为提升教学质量提供确保。伴随教育改革不停深入和社会发展需要，原旧教学计划在定位上方向性偏差，已经不再适应社会需求。所以，应重视教学计划改革和修订工作，以确保教育教学质量，提升教育教学水平。教学计划编制中思绪:一是明确培养目标;二是重视学科设置整体性、统一性和灵活性、全方面性;三是和学分制改革有机结合。
教学计划是高校实施常规教学活动基础管理文档,因为传统手工编制方法存在很多弊端,开发基于Web应用程序形式教学计划编制系统含有很好应用价值。使用C程序设计语言,研究开发教学计划编制系统Web应用系统。
关键词: 教学计划；编制；培养目标；管理

三号黑体，居中，固定值22磅，段前段后1行。
四号黑体，固定值22磅，段前段后0行
目 录
1 问题描述 1
2 需求分析 2
3 概要设计 2
3．1抽象数据类型定义 2
3．2模块划分 2
4 具体设计 3
4．1数据类型定义 4
4．2关键模块算法描述 5
5 测试分析 8
6 课程设计总结 10
6.1问题和处理方法及经验教训、心得体会﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍ 10
6.2 致谢 11
参考文件 11
附录（源程序清单） 12

1 问题描述
大学每个专业全部要制订教学计划。假设任何专业全部有固定学习年限，每年含两学期，每学期时间长度和学分上限值均相等，每个专业开设课程全部是确定，而且课程在开设时间安排必需满足先修关系。每门课程有哪些先修课程是确定，能够有任意多门，也能够没有。每门课恰好占一个学期。试在这么前提下设计一个教学计划编制程序。
[基础要求]
（1）输入参数包含：学期总数，一学期学分上限，每门课课程号(固定占3位字母数字串)、学分和直接先修课课程号。
（2）许可用户指定下列两种编排策略之一：一是使学生在各学期中学习负担尽可能均匀；二是使课程尽可能地集中在前多个学期中。
（3）若依据给定条件问题无解，则汇报合适信息；不然将教学计划输出到用户指定文件中。计划表格格式自行设计。
[测试数据]
学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分次序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系以下：
课程编号
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1，C2
C4
汇编语言
C1
C5
语言设计和分析
C3，C4
C6
计算机原理
C11
C7
编译原理
C5，C3
C8
操作系统
C3，C6
C9
高等数学
无
C10
线性代数
C9
C11
一般物理
C9
C12
数值分析
C9，C10，C1

2 需求分析
大学每个专业全部要编制教学计划。假设任何专业全部有固定学习年限，每年含两学期，每学期时间长度和学分上限全部相等。每个专业开设课程全部是确定，而且课程开设时间安排必需满足先修关系。每个课程先修关系全部是确定，能够有任意多门，也能够没有。每一门课程恰好一个学期。试在这么情况下设置一个教学计划编制程序。
在大学某个专业中选择多个课程作为顶点,经过各门课先修关系来构建个图,该图用邻接表来存放,邻接表头结点存放每门课信息.
本程序目标是为用户编排课程,依据用户输入信息来编排出每学期要学课程.
针对计算机系本科课程，依据课程之间依靠关系（如离散数学应在数据结构之前开设）制订课程安排计划，并满足各学期课程数目大致相同,而且课程在开设时间安排必需满足先修关系。输入参数包含：学期总数，一学期学分上限，每门课课程号(固定占3位字母数字串)、学分和直接先修课课程号。
3 概要设计
3．1抽象数据类型定义
ADT Graph{
数据对象V:V是含有相同特征数据元素集合,称为顶点集.
数据关系R:
R={VR}
VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}
基础操作P:
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);
void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);
}ADT Graph
栈定义:
ADT Stack{
数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}
数据关系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,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．2模块划分
主程序模块

拓扑排序模块
4 具体设计
4．1数据类型定义
1．头结点，表结点，邻接表定义
#define MAX_VERTEX_NUM 100 //最大课程总数
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
char name[24]; //课程名
int classid; //课程号
int credit; //课程学分
int indegree; //该结点入度
int state; //该节点状态
ArcNode *firstarc; //指向第一条依附该顶点弧指针
}VNode,AdjList[MAX_VEXTEX_NUM];

typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
邻接表基础操作：
void CreatGraph(ALGraph *);
创建邻接表
void FindInDegree(ALGraph , int * );
求一个结点入度
void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);
拓扑排序来编排课程
void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);
2．栈定义：
#define STACk_INIT_SIZE 100 //存放空间初时分配量
#define STACKINCREMENT 10 //存放空间分配增量
typedef int ElemType;
typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
基础操作：
void InitStack (SqStack *S);
栈初始化
int StackEmpty(SqStack S);
判定栈是否为空
void Push(SqStack *S, int );
入栈操作
int Pop(SqStack *S, int *e);
出栈操作
int Sort(SqStack *S,int *t);
4．2关键模块算法描述
1.LocateVex（）：图邻接表存放基础操作。由初始条件: 图G存在,u和G中顶点有相同特征转而进行判定，若G中存在顶点u,则返回该顶点在图中位置;不然返回-1。

int i

i=0

i<G.vexnum

return i

++i

return -1

图 4.1

2.CreateGraph（）：结构生成图。采取邻接表存放结构,结构没有相关信息图G(用一个函数结构种图)。

int i,j,k;

i=0

i<(*G).vexnum

scanf("%s",(*G).vertices[i].data);

++i

printf("请输入%d个课程学分值”)

i=0

i<(*G).vexnum

scanf("%s",(*G).verticestwo[i].data);

++i

multi

图 4.2
3.Display（）：输出图邻接矩阵。采取循环设置输出图邻接矩阵。

int i;

G.kind=DG

printf("%d个顶点：\n",G.vexnum);

i=0

i<G vexnum

++i

multi

图 4.3
4.FindInDegree（）：求顶点入度。

int i

i=0

i<G.vexnum

i++

i=0

i<G.vexnum

p=G.vertices[i].firstarc;

p

indegree[p->adjvex]++;

i++;

maxcredit

图 4.4

5.TopologicalSort（）：输出G顶点拓扑排序结果。有向图G采取邻接表存放结构。若G无回路,则输出G顶点一个拓扑序列并返回OK, 不然返ERROR。

inti,k,j=0,count,indegree[MAX_VERTEX_NUM];

i=0

i<G.vexnum

Push(&S,i);

++i

count=0

!StackEmpty(S)

multi

multi

图 4.5
5 测试分析
使用VC++，打开教学计划编制问题.cpp文件，接着编译，无错误，然后重建也没有错误，最终实施该文件。
要求输入学期总数、一个学期学分上限、需要编排课程总数、课程名、课程号、该课程学分，根据出现每一步来输入该课程设计所提供相关数据。然后还要输入课程先修课程总数，能够算出有16种关系，分别输出。接着程序会依据这些数据，自动生成建立好邻接表，用户能够依据系统显示选择编排策略进行选择，有两种编排策略，最终结果表现在试验正确测试结果里。显示以下图：

6 课程设计总结
6.1 问题和处理方法及经验教训、心得体会
即使在大一我们已经学习了C语言，不过，直到本期我们才开设了数据结构这一门课程。这门课程让我从C语言那基础再深入了解了软件开发复杂性。对以往模糊经验，起了总结提升作用。在学习了这门课程后，我们进行了2个星期课程设计，来实践我们所学这门课内容。
这次试验，我进行了大量资料查阅，包含向老师请求帮助解释题目要求，对所学知识进行复习。经过这些努力，我对数据结构这门课程有了新认识，对编程步骤，有了具体体会。经过和同学广泛交流，我体会到了合作必需性及合作优势。更关键是，这个课题完全脱离于只限于书本上问题，多用在实际生活当中，让我对计算机行业，充满了信心和自豪。以往我们学计算机知识通常停留在理论上，这让我们不太了解计算机应用和前景，而较少重视我们对算法实践锻炼。而这一次实习既需要我们去联络理论，又需要我们去实践方法，很多东西看上去全部学过，不过和实际联络才知道变通艰苦。书上得来并不是一切，大多还是需要在其它方面去吸收，这是我这次实习最大收获。这次试验让我们知道该怎样跨过实际和理论之间鸿沟。
因为程序十分复杂，碰到了很多常见语法错误，及逻辑错误。这需要我们不
参考献中内容为五号宋体。
断调试分析。符号格式之类，指针使用方法，判定输入输出条件全部是十分轻易犯错地方。在逐条排除，向同学老师请教后，程序最终得以完成。这让我明白了，处理问题，要细心认真，集思广益，这么才能把问题处理。
6.2 致谢
此次课程设计，并不是我自己一个人设计出来。
首先，我要感谢我数据结构老师——黄老师，此次课程设计黄老师帮助了我们不少，所以在这里我致以最真挚谢意，老师，谢谢您！另外，我还要感谢在我这次课程设计中帮助过我同学，谢谢你们一直以来对我帮助，没有你们也没有我此次结果，谢谢。
参考文件
[1] 黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，
[2] 董建寅，黄俊民，黄同成．数据结构试验指导和题解[M]．北京：中国电力出版社，
[3] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，
[4] 刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，
附录（源程序清单）
#include<string.h>
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<process.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
#define MAX_NAME 10
#define MAXCLASS 100
int Z=0;
int X=0;
int xqzs,q=1,xfsx;
typedef int InfoType;
typedef char VertexType[MAX_NAME];
#define MAX_VERTEX_NUM 100
typedef enum{DG}GraphKind;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices,verticestwo;
int vexnum,arcnum;
int kind;
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph *G)
{
int i,j,k;
VertexType va,vb;
ArcNode *p;
printf("请输入教学计划课程数: ");
scanf("%d",&(*G).vexnum);
printf("请输入拓扑排序所形成课程先修关系边数: ");
scanf("%d",&(*G).arcnum);
printf("输入%d个课程代表值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)
{ scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
printf("输入%d个课程学分值(<%d个符):\n", (*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)
{
scanf("%s",(*G).verticestwo[i].data);
}
printf("请次序输入每条弧(边)弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s",va,vb);
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info=NULL;
p->nextarc=(*G).vertices[i].firstarc;
(*G).vertices[i].firstarc=p;
}
return OK;
}
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向图\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
p=p->nextarc;
}
printf("\n");
}
}
void FindInDegree(ALGraph G,int indegree[])
{
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0;
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType;
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
typedef struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S)
{
(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status Pop(SqStack *S,SElemType *e)
{
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
Status Push(SqStack *S,SElemType e)
{
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof (SElemType));
if(!(*S).base)
exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
typedef int pathone[MAXCLASS];
typedef int pathtwo[MAXCLASS];
Status TopologicalSort(ALGraph G)
{
int i,k,q=1,j=0,count,indegree[MAX_VERTEX_NUM];
SqStack S;
pathone a;
pathtwo b;
ArcNode *p;
FindInDegree(G,indegree);
InitStack(&S);
for(i=0;i<G.vexnum;++i)
if(!indegree[i])
Push(&S,i);
count=0;
while(!StackEmpty(S))
{
Pop(&S,&i);
a[i]=*G.vertices[i].data;
b[i]=*G.verticestwo[i].data;
if(q<=6)
{
printf("第%d个学期应学课程：课程%s→学分%s\n",q,G.vertices[i].data,G.verticestwo[i].data);
q++;
}
else
{
printf("***课程%s→学分%s\n",G.vertices[i].data,G.verticestwo[i].data);
}
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!(--indegree[k]))
Push(&S,k);
}
}
if(count<G.vexnum)
{printf("此有向图有回路\n");
return ERROR;
}
else
{
printf("为一个拓扑序列。\n");
printf("教学编制计划已完成。\n");
}
return 0;
}
void main()
{ ALGraph f;
printf("教学计划编制问题数据模型为拓扑排序AOV-网结构。\n");
printf("以下为教学计划编制问题求解过程:\n");
printf("请输入学期总数:");
scanf("%d",&xqzs);
printf("请输入学期学分上限:");
scanf("%d",&xfsx);
CreateGraph(&f);
Display(f);
TopologicalSort(f);
}