目 录
摘 要 ...................................................................................................................... 1 前 言 ...................................................................................................................... 2 正 文 ...................................................................................................................... 3 1. 2. 3. 4. 5. 6.
问题描述 ...................................................................................................... 3 逻辑设计 ...................................................................................................... 3 详细设计 ...................................................................................................... 6 称序编码 ..................................................................................................... 11 程序调试与测试 ........................................................................................ 14 软件安装和使用说明书 ............................................................................ 15
设 计 总 结 .................................................................................................... 16 参考文献 ................................................................................................................ 17 致 谢 .................................................................................................................... 18
摘 要
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
关键词：数据、结构、教学、计划
1
前 言
随着科学技术和市场经济的迅速发展,技术和产品的生命周期日益缩短,市
场需求日益多样化和个性化,社会对人才的需求也越来越呈现多样化、专业化和个性化[1-2]。高等学校学历教育的主要任务是传授专业基础知识、培养可持续发展的综合素质。学生毕业后,面对瞬变的人才市场,常感到无所适从,而企业方面又常感到合适的人才难求。顺应社会的需求,针对具体行业需求的定制式教学悄然兴起。 近年来,伴随着经济发展轨道的变化,广东省的一些企业向高校提出了定制式教学培训的要求。例如某摩托车生产企业为了开拓海外市场,要对原产品进行改造,要求开设机械设计理论课程,主要目的是提高技术队伍人员的动力学分析与综合水平。
定制式教学需求属于同一工程领域,教学目标呈现多样化特征,所需基础涉及若干门课程,但不是这些课程的简单组合,亦无法照搬学校现成的教学计划。为了迅速响应社会需求,需要研究面向定制式教学的多样化教学计划设计方法。
2
正 文
1. 问题描述
根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。采用第二种策略：使课程尽可能地集中在前几个学期中；根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图GrateGraph（）：结合先修关系的AOV网，显示代号所对应课程及课程的先修课程拓扑排序TopologicalOrder (G)：将课程排序后并决定出每学期所学课程，输出图G的信息Display(G)：将图的顶点和弧边输出 。
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计
2. 逻辑设计
CreatGraph(ALGraph *G)//构件图（如下右图）
void FindInDegree(ALGraph G, int indegree[])//求图中各节点的入度（如下左图）
3
void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) //有向图G采用邻接表存储结构(如下左图)
void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) //有向图G采用邻接表存储结构（如下右图）
4
主函数：void main()
5
3. 详细设计
1 、图的邻接表的存储表示，即结构体的定义 typedef struct ArcNode { int AdjOfV; // 该弧所指向的顶点的位置
struct ArcNode *next; //指向下一条弧的指针
}ArcNode;
typedef char VertexType[MAXOfNAME];
typedef struct //链接表 {
6
VertexType data; //顶点信息 int grades; //存储学分信息
ArcNode *first; //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VER]; // 头结点
typedef struct {
AdjList ver; //vertices 存储课程名 int vexnum, arcnum; // 图的当前顶点数和弧数
}ALGraph;
2 、利用前插法，建立图的邻接链表
printf(\"请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\\n\");
for (h=0;h printf(\"%s的先修课程:\ scanf(\"%s\ while (va[0]!='0') { i = LocateVex(G, va); //弧头 j = h; //弧尾 7 p = (ArcNode*)malloc(sizeof(ArcNode)); p->AdjOfV = j; p->next = G.ver[i].first; // 插在表头 G.ver[i].first = p; scanf(\"%s\ getchar(); } } 3 、输出图的顶点和边 printf(\"%d个顶点\ for (i = 0;i < G.vexnum;++i)printf(\"%4s\ printf(\" \\n%d条弧边:\\n\ for (i = 0;i < G.vexnum;i++) { p = G.ver[i].first; while (p) { printf(\"%s---->%s\\n\ p = p->next; } } 4 、通过栈实现拓扑排序 int TopologicalOrder(ALGraph G,AdjList R,struct Name name[]) { 8 int i, k, j = 0, count, indegree[MAX_VER]; SqStack S; ArcNode *p; FindInDegree(G, indegree); // 对各顶点求入度 InitStack(S); // 初始化栈 for (i = 0;i < G.vexnum;++i) //建零入度顶点栈S if (!indegree[i]) Push(S, i); // 入度为0者进栈 count = 0; // 对输出顶点计数 while (!StackEmpty(S)) { Pop(S, i); printf(\"%s(%d学分),\R[j++] = G.ver[i]; //将当前的拓扑序列保存起来 ++count; // 输出i号顶点并计数 for (p =G.ver[i].first; p; p=p->next)// 对i号顶点的每个 邻接点的入度减1 } 9 { } k = p->AdjOfV; if (!(--indegree[k])) // 若入度减为0,则入栈 Push(S, k); 来*/ ++Z; } 10 if (count < G.vexnum) { } else printf( \" 为一个拓扑序列\"); printf(\"\\n\"); int q=1,Z=0; while (q <= TotalOfTerms) { int C = R[Z].grades ; printf(\"\\n第%d个学期应学课程:\while (C <= MaxScores) { C = C + R[Z+1].grades; printf(\"此有向图有回路无法完成拓扑排序\"); return 0; if (Z < G.vexnum) { CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起 } printf(\"\\n\"); if (q == TotalOfTerms)printf( \"\\nOK Over!\"); q++; } return 1;/**/ } 4. 称序编码 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); 11 }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 2. 主程序 int main() //主函数 { int numterm; //学期总数 int uplcredit; //一个学期的学分上限 int selectway; ALGraph G; 12 printf(\"请输入学期总数:\\n\"); scanf(\"%d\ printf(\"请输入一个学期的学分上限:\\n\"); scanf(\"%d\ CreatGraph(&G); printf(\"请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布\\n\"); scanf(\"%d\ if(selectway==1) TopologicalSort_1(G,numterm,uplcredit); if(selectway==2) TopologicalSort_2(G,numterm,uplcredit); system(\"pause\"); return 0; } 3. 本程序只有两个模块,调用关系简单. 主程序模块 ↓ 13 拓扑排序模块 。 5. 程序调试与测试 14 6. 软件安装和使用说明书 使用VC++，打开教学计划编制问题.cpp文件，接着编译，无错误，然后重建也没有错误，最后执行该文件。显示如下图：要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分，按照出现的每一步来输入该课程设计所提供的相关数据。然后还要输入课程先修课程总数，依据教科书图7．26，可以算出有16种关系，分别输出如下图所示。接着程序会根据这些数据，自动生成建立好的邻接表，用户可以根据系统显示的选择编排策略进行选择，有两种编排策略，最后结果体现在实验的正确测试结果里（如上图）。 15 设 计 总 结 经过此次课程设计，我深刻地认识到自己写程序的不足，认识到了仅仅只是从课本上学到算法原理是远远不够的，理论与实践结合才是最重要的。实验中，我总是不经意间出现各种错误，这就要求今后的我要以脚踏实地的态度来思考处理问题。总之本次课程设计，让我进一步熟悉了C语言的语句用法，学到了很多有用的知识。经过此次课程设计，我们认识到了理论与实践结合的重要性，仅仅只是从课本上学到算法原理是远远不够的。在实践中，我们总会出现许多错误。这就要求我们以一个脚踏实地的态度来处理问题。我们深刻地认识到自己写程序的不足，使我们学到了好多有用的知识，让我们明白了C语言的语句用法。 16 参考文献 1 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社. 2 严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社. 3 《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.《c语言程序设计》. 清华大学出版社. 5．数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译 电子工业出版社 2001 年1月 17 致 谢 本课题在选题及进行过程中得到张其文老师的悉心指导。论文行文过程中， 张老师多次帮助我分析思路，开拓视角，在我遇到困难想放弃的时候给予我最大的支持和鼓励。张老师严谨求实的治学态度，踏实坚韧的工作精神，将使我终生受益。再多华丽的言语也显苍白。在此，谨向张老师致以诚挚的谢意和崇高的敬意 18 因篇幅问题不能全部显示，请点此查看更多更全内容