数据结构(C++)课程设计报告--教学计划编制问题上海电力学院数据结构（C++）课程设计题目: 教学计划编制问题*名：***学号：********院系：计算机科学与技术学院专业年级：信息安全2011级2013年07月04日一、设计题目大学的每个专业都要编制教学计划。

假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。

每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。

每个课程的先修关系都是确定的，可以有任意多门，也可以没有。

每一门课程恰好一个学期。

试在这样的情况下设置一个教学计划编制程序。

在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息。

本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程。

二、需求分析（一）运行环境（软、硬件环境）设计环境和器材——硬件：计算机软件：Microsoft Visula C++在本课程设计中，系统开发平台为Windows XP或Win 7，程序运行环境为Visual C++ 6.0，程序设计语言为C++。

Visual C++一般分为三个版本：学习版、专业版和企业版，不同版本适合于不同类型的应用开发。

实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C++ 6.0为编程环境。

Visual C++以拥有“语法高亮”，IntelliSense（自动编译功能）以及高级除错功能而著称。

比如，它允许用户进行远程调试和单步执行等。

还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。

其编译及建置系统以预编译头文件、最小重建功能及累加链接著称。

这些特征明显缩短程式编辑、编译及链接的时间花费，在大型软件计划上尤其显著。

Visual C++ 6.0秉承Visual C++ 以前版本的优异特性，为用户提供了一套良好的开发环境，主要包括文本编辑器、资源编辑器、工程创建工具和Debugger调试器等等。

用户可以在集成开发环境中创建工程，打开工程，建立、打开和编辑文本，编译、链接、运行和调试应用程序。

（二）输入的形式和输入值的范围数据输入的方式是键盘输入。

输入的数据多是整型的或是浮点型的，还有一些字符（以中文的形式）。

输入的数值型的数据大都是小于100的数值。

（三）输出的形式描述输出的是教学编制计划，就是形如：“第二学期学的课程有:普通物理线性代数汇编语言”这样的形式。

（四）功能描述输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。

计划的表格格式自行设计。

（五）测试数据学期总数：6学分上限：10该专业共开设12门课，课程号从01~12，学分顺序为2，3，4，2，2，4，4，4，7，5，2，3。

三、概要设计（一）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或ppt及实验）抽象数据类型：为实现上述功能需建立一个结点类，线性表类，图类。

ADT Graph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}基本操作P:void creatpre(AlGraph *CGraph);void findindegree(AlGraph *CGraph,int indegree[]);void layout1(AlGraph *CGraph,queue *q);void layout2(AlGraph *CGraph,queue *q);}ADT Graph队列的定义:ADT List{数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}数据关系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n}基本操作:void queue_init(queue *q);void queue_in(queue *q,int x);int queue_out(queue *q);int queue_empty(queue *q);}ADT Stack（二）功能模块设计主程序：void main(){int choice;queue q;Queue.queue_init(&q);AlGraph CGraph;CGraph=Graph.input();system("cls");Graph.output(CGraph);cout<<endl<<endl;Judgement.judgingcricle(&CGraph,&q);if(!WhetherCricle){while(1){cout<<"请选择编排策略:\t"<<endl;cout<<"1.使学生在各学期中的学习负担尽量均匀;\t"<<endl;cout<<"2.使课程尽可能地集中在前几个学期中。

\t"<<endl;cout<<"请选择:";cin>>choice;system("cls");if(choice==1)yout1(&CGraph,&q);elseyout2(&CGraph,&q);cout<<"请选择继续编排策略或退出程序（0退出1继续）:\t"<<endl;cin>>choice;system("cls");if(choice==0)break;}}}（三）模块层次调用关系本程序只有两个模块,调用关系简单主程序模块→拓扑排序模块TopSort流程图：所有顶点是否处理完？将入度为0的顶点入栈是否用数组OutLes 保存每次入栈的入度将当前结点的后输出课对每个学期的邻接表类成员函数否是否 是运行结束邻接表构造函数ALGraph运行初始化初始化边表，并在相应的结束邻接表ALGraph的构造函数四、详细设计教学计划编制系统主要是处理课程之间的依赖关系。

表列出了若干门计算机系本科课程，其中有些课程不要求先修课程，例如，C1是独立于其他课程的基础课，而有些课程却需要有先修课程，比如，学完程序设计语言C++和离散数课程代号课程名称先修课程C1 高等数学无C2 计算机科学导论无C3 离散数学C1C4 程序设计语言C++ C1、C2C5 数据结构C3、C4C6 计算机原理C2、C4C7 数据库原理C4、C5、C6先修课程规定了课程之间的依赖关系，这种关系可以用AOV网来表示，其中顶点表示课程，弧表示依赖关系。

程序的主要功能是实现课程的排序，以满足同一学期所修的课程相互之间无依赖关系，并且已修完其所有先修课程。

本程序需要基于图的基本操作来实现算法的基本思想：1、图的构建：建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。

建立一个线性表类，完成线性表的构建。

建立一个图类，完成图的信息的读取，（如有n 个点，则建立n 个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。

2、Topsort 算法：先计算每个点的入度，保存在数组中。

找到第一个入度为0的点，将该点所连的各点的入度减一。

再在这些点中找入度为0 的点。

如果找到，重复上述操作。

如果找不到，则跳出while 循环，再搜索其他的点，看入度是否为0。

再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。

3、 邻接表类的定义邻接表是一种顺序存储与链接存储相结合的存储方法。

在邻接表中存在两种结点结构：顶点表结点和边表结点。

五、调试分析包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。

（一）实验过程中出现的问题及解决方法我在实验过程中遇到的最大难题是两个课程排序算法的编写。

刚开始的时CCC CC CC nextadjv first v 表结点 点候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。

经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。

经过三天的修改，终于写出了符合要求的排序算法。

（二）实验体会上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成必不可少的一个教学环节，也是对课堂教学效果的一种检验。

通常，实习题中的问题比平时的习题复杂得多，也更接近实际。

实习题注重原理与应用的结合，目的让学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能。

同时，通过实践能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的作用。

平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，可以多人合作，有利于一整套软件工程规范的训练和科学作风的培养。

此外，实践环节中有很重要的一点，就是机器是比任何教师都严格的主考官。

经过此次课程设计，我认识到了理论与实践结合的重要性，仅仅只是从课本上学到算法原理是远远不够的。

在实践中，我们总会出现许多错误。

这就要求我们以一个脚踏实地的态度来处理问题。

我深刻地认识到自己写程序的不足，使我们学到了好多有用的知识，让我们明白了C++语言的语句用法。

六、测试结果要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分，按照出现的每一步来输入该课程设计所提供的相关数据。

学期总数：6；学分上限：10；该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，2，2，4，4，4，7，5，2，3。

然后还要输入课程先修课程总数，可以算出有16种关系，分别输出。

接着程序会根据这些数据，自动生成建立好的邻接表，用户可以根据系统显示的选择编排策略进行选择，有两种编排策略，最后结果体现在实验的正确测试结果里。

输入的内容如下:课程编号课程名称学分先决条件01 计算机基础 2 无02 离散数学 3 0103 数据结构 4 01，0204 汇编语言 2 0105 语言的设计和分析 2 03，0406 计算机原理 4 1007 编译原理 4 05，0308 操作系统 4 03，0609 高等数学7 无10 普通物理 5 0911 线性代数 2 0912 数值分析 3 09，11，01七、附录：程序设计源代码#include<iostream>#include<string>#include<cstdio>#include<cstdlib>using namespace std;#define null 0#define MAX_COURSE_NUM 100 //最大课程个数typedef struct{char c[3];}cid; //课程号typedef struct Course{cid id[3];char name[30];float xf;}Course; //课程typedef struct PreCourse{int adjvex;struct PreCourse *nextarc;}PreCourse; //先修的课程节点typedef struct{Course course;PreCourse *firstarc;}CourseNode; //课程节点typedef struct{CourseNode courses[MAX_COURSE_NUM]; //邻接表int xqs;int num;float xfsx;}AlGraph; //课程图typedef struct{int data[MAX_COURSE_NUM];int f,r;}queue;int WhetherCricle=0;int jxq;class Queue{public:void queue_init(queue *q);void queue_in(queue *q,int x);int queue_out(queue *q);int queue_empty(queue *q);}Queue;void Queue::queue_init(queue *q) //队初始化{q->f=q->r=0;}void Queue::queue_in(queue *q,int x) //入队{if((q->r+1)%MAX_COURSE_NUM==q->f){cout<<"队满\t"<<endl;exit(0);}q->r=(q->r+1)%MAX_COURSE_NUM;q->data[q->r]=x;}int Queue::queue_out(queue *q) //出队{if(q->f==q->r){cout<<"队空\t"<<endl;exit(0);}q->f=(q->f+1)%MAX_COURSE_NUM;return q->data[q->f];}int Queue::queue_empty(queue *q) //队判空 1为空{if(q->f==q->r)return 1;else return 0;}class Graph{public:AlGraph input();void output(AlGraph CGraph);void creatpre(AlGraph *CGraph);}Graph;void Graph::creatpre(AlGraph *CGraph) //建立先修关系{system("cls");int choice;int i,n;int j;PreCourse *p,*q;cout<<endl<<"建立先修关系:\t"<<endl;cout<<endl<<"输入的每一门课程号的编号：\t"<<endl;for(i=0;i<CGraph->num;i++){if(i%4==0)cout<<endl;cout<<"("<<i+1<<")"; //输入课程的编号printf("%s\t",CGraph->courses[i].course.id);}cout<<endl;cout<<"\n请根据以上的编号，输入每一门课程的先修课程号的编号（输入0 表示没有或结束）：\t"<<endl;for(i=0;i<CGraph->num;i++){printf("%s的先修课程:",CGraph->courses[i].course.id);cin>>j;n=0;while(j) //判断输入的课程编号是否正确{while(j<1||j>CGraph->num||j==i+1){if(j==i+1)cout<<"先修课程号不可能是本课程号\n";elsecout<<"输入的先修课程号不在该专业开设的课程序列中"<<endl;cout<<"请重新输入:";cin>>j;}p=(PreCourse *)malloc(sizeof(PreCourse));p->adjvex=j-1;p->nextarc=null;if(n==0){CGraph->courses[i].firstarc=p;q=CGraph->courses[i].firstarc;n++;}else{q->nextarc=p;q=p;n++;}cin>>j;}}cout<<"(1)重新建立先修关系\t"<<"(2)确定\n";cout<<"请选择:";cin>>choice;if(choice==1)creatpre(CGraph);jxq=0;}AlGraph Graph::input() //输入并建立课程图{AlGraph CGraph;int xqzs=0,kczs=0;int i;int choice;float xf,xfsx=0;cout<<"教学计划编制\n"<<endl;cout<<"输入参数:\n";cout<<"1.学期总数:";cin>>xqzs;CGraph.xqs=xqzs;cout<<"2.专业共开设课程数:";cin>>kczs;CGraph.num=kczs;cout<<"3.学分上限(每个学期的学分上限都一样):";cin>>xfsx;CGraph.xfsx=xfsx;cout<<"4.每门课的课程号(固定占3位的字母数字串)、课程名、学分——"<<endl;for(i=0;i<kczs;i++) //输入课程号，课程名，学分{cout<<"课程号:";scanf("%s",CGraph.courses[i].course.id);cout<<"课程名:";scanf("%s",CGraph.courses[i]);cout<<"学分:";cin>>xf;cout<<endl;while(xf>xfsx||xf<=0) //判断输入的学分是否合格{cout<<"输入的学分有误，请重新输入学分:";cin>>xf;}CGraph.courses[i].course.xf=xf;CGraph.courses[i].firstarc=null;}cout<<"(1)重新输入\t"<<"(2)确定"<<endl;cout<<"请选择:";cin>>choice;if(choice==1){system("cls");input();}else{creatpre(&CGraph); //建立先修关系return CGraph;}}void Graph::output(AlGraph CGraph) ///输出先修关系{int i,j,n;PreCourse *p;cout<<"先修关系如下:\n"<<endl;cout<<"课程编号\t"<<"课程名称\t"<<"先决条件"<<endl;for(i=0;i<CGraph.num;i++){printf("%s\t\t%s\t\t",CGraph.courses[i].course.id,CGraph.courses[ i]);j=0;p=CGraph.courses[i].firstarc;while(p){n=p->adjvex;printf(" %s ",CGraph.courses[n].course.id);p=p->nextarc;j++;}if(j==0)cout<<" 无";cout<<endl;}}class Judgement{public:void findindegree(AlGraph *CGraph,int indegree[]);void judgingcricle(AlGraph *CGraph,queue *q2);}Judgement;void Judgement::findindegree(AlGraph *CGraph,int indegree[]){int i;PreCourse *p;for(i=0;i<CGraph->num;i++){indegree[i]=0;p=CGraph->courses[i].firstarc;while(p){indegree[i]++;p=p->nextarc;}}}void Judgement::judgingcricle(AlGraph *CGraph,queue *q2)//判断是否有环和课程入队{int indegree[MAX_COURSE_NUM]; //入度int i,m,j,pd=0;float xf=0;PreCourse *p;queue q;Queue.queue_init(&q); //队初始化findindegree(CGraph,indegree); //找入度for(i=0;i<CGraph->num;i++){if(indegree[i]==0&&(xf+CGraph->courses[i].course.xf)<=CGraph->xfsx){Queue.queue_in(&q,i);indegree[i]--;xf+=CGraph->courses[i].course.xf;}}m=0;xf=0;Queue.queue_in(&q,-1); //把-1入队用来判断jxq++;while(1){i=Queue.queue_out(&q);Queue.queue_in(q2,i);if(i!=-1){m++;for(j=0;j<CGraph->num;j++)if(j!=i){if(indegree[j]==0&&(xf+CGraph->courses[j].course.xf)<=CGraph->xfsx){Queue.queue_in(&q,j);indegree[j]--;xf+=CGraph->courses[j].course.xf;}else{p=CGraph->courses[j].firstarc;while(p){if(p->adjvex==i){indegree[j]--;if(indegree[j]==0&&(xf+CGraph->courses[j].course.xf)<=CGraph->xfs x){Queue.queue_in(&q,j);indegree[j]--;pd=1;xf+=CGraph->courses[j].course.xf;}}p=p->nextarc;}}}}else{if(pd){pd=0;Queue.queue_in(&q,-1);jxq++;xf=0;}else break;}}if(jxq>CGraph->xqs){cout<<endl<<"错误报告：\n"<<"在"<<CGraph->xqs<<"学期内是无法修完这些课程"<<endl;exit(0);}if(m<CGraph->num){cout<<"\n错误报告："<<endl;cout<<"存在循环，因此课程安排不了"<<endl;WhetherCricle=1;}Queue.queue_in(q2,-1);}class Edit{public:void layout1(AlGraph *CGraph,queue *q);void layout2(AlGraph *CGraph,queue *q);}Edit;void Edit::layout1(AlGraph *CGraph,queue *q){cout<<"\n学生在各学期中的学习负担尽量均匀:\n"<<endl;int i,j,k,xq=1,ck[20];float xf;float m=CGraph->num/CGraph->xqs*1.0f;queue q1=*q;int n;int x;n=0;ck[0]=-1;for(i=0;i<20;i++){j=Queue.queue_out(&q1);ck[i]=j;if(j==-1)i--;if((Queue.queue_empty(&q1)))break;}for(x=0;x<CGraph->xqs;x++){if(ck[0]!=-1){cout<<"\n第"<<xq++<<"学期学：";xf=0;for(i=0;i<m;i++){k=ck[n];printf(" %s ",CGraph->courses[k].course.id);n++;xf+=CGraph->courses[k].course.xf;}cout<<"获得学分是:"<<xf<<endl;}}}void Edit::layout2(AlGraph *CGraph,queue *q){cout<<"\n课程尽可能地集中在前几个学期中:\n"<<endl;int i,j,xq=1;float xf;cout<<"\n第"<<xq<<"学期学：";xq++;xf=0;queue q1=*q;for(i=1;i<=CGraph->num;){j=Queue.queue_out(&q1);if(j!=-1){printf(" %s ",CGraph->courses[j].course.id);i++;xf+=CGraph->courses[j].course.xf;}else{cout<<"获得学分是:"<<xf;cout<<"\n第"<<xq++<<"学期学：";xf=0;}}cout<<"获得学分是:"<<xf<<endl;if(xq<=CGraph->xqs){cout<<"\n第"<<xq++<<"学期学：无\n"<<endl;}}void main(){int choice;queue q;Queue.queue_init(&q);AlGraph CGraph;CGraph=Graph.input();system("cls");Graph.output(CGraph);cout<<endl<<endl;Judgement.judgingcricle(&CGraph,&q);if(!WhetherCricle){while(1){cout<<"请选择编排策略:\t"<<endl;cout<<"1.使学生在各学期中的学习负担尽量均匀;\t"<<endl;cout<<"2.使课程尽可能地集中在前几个学期中。