1、. . . . .数据结构课程设计教学计划编制问题班级学号2143201学生姓名周子健提交日期2016年1月19日成 绩 计算机与通信工程学院. 专业.专注 .设计要求：针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。1.1 课程设计目的本课程设计主要是针对计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数目大致相同。教学计划编制系统是基于C+的软件系统，通过建立AOV网，按学期对课程序号、课程代号、课程名称以及课程学分进行相应输出，并且保证用户实现自由选择专业选修课功能。1.2 课程设计
2、内容教学计划编制系统主要是处理课程之间的依赖关系。表1.1列出了若干门计算机系本科课程，其中有些课程不要求先修课程，例如，C1是独立于其他课程的基础课，而有些课程却需要有先修课程，比如，学完程序设计语言C+和离散数学后才能学习数据结构。具体情况如表1.1所示。表1.1 课程以及课程之间的依赖关系课程代号课程名称先修课程C1高等数学无C2计算机科学导论无C3离散数学C1C4程序设计语言C+C1、C2C5数据结构C3、C4C6计算机原理C2、C4C7数据库原理C4、C5、C6先修课程规定了课程之间的依赖关系，这种关系可以用AOV网来表示，其中顶点表示课程，弧表示依赖关系，如图1.1所示。C1C7C
3、6C4C5C3C2图1.1 表1.1对应的AOV网程序的主要功能是实现课程的排序，以满足同一学期所修的课程相互之间无依赖关系，并且已修完其所有先修课程。另外，设置学分变量，控制每个学期的课程量基本均匀。2 概要设计2.1 数据表示教学计划编制问题中，操作对象是课程。课程之间的依赖关系用AOV网表示， AOV网的构造采用邻接表实现。因此，本程序设计定义了两个类：课程类和邻接表类。课程类（Lesson）添加了5个私有成员变量用来定义课程的5个属性：课程代号、课程名称、课程序号、课程学分以及是否被选择过的课程标记。同时还定义了8个成员函数，已实现相关的操作功能。邻接表类（ALGraph）定义了2个整
4、型成员变量和1个结构体数组来存放顶点数、边数和顶点表。同时还定义了4个成员函数实现用来实现AOV网的构造、删除、排序以及相关输出功能。2.2 数据处理数据处理必须借助函数来实现。本程序设计通过调用类的各种成员函数实现各种需要操作。课程类（Lesson）的成员函数如表2.1所示。表2.1 Lesson类的成员函数函数名称功能声明void SetLes()对课程各种属性进行赋值string GetNum()获得课程代号string GetName()获得课程名称float GetLesScore()获得课程学分int GetLesNo()获得课程序号bool GetSelect()获得是否选择过的
5、标志变量void SetSelect()设置选择控制标志变量，以避免重复选课void SetName()单独定义设置课程名称的函数，以方便一些操作邻接表类（ALGraph）的成员函数如表2.2所示。表2.2 ALGraph类的成员函数函数名称功能声明ALGraph()构造函数ALGraph()析构函数void TopSort()实现AOV网中顶点的排序并进行相应的输出void BalanScore()平衡每次输出的顶点的数目3 详细设计3.1 课程类的定义课程类（Lesson）添加了5个私有成员变量：LesNum（课程代号）、LesName（课程名称）、LesScore（课程学分）、LesNo
6、（课程序号）以及Select（是否被选择过的课程标记），分别用来定义课程的5个属性；同时还定义了8个成员函数：SetLes（对课程各种属性进行赋值）、GetNum（获得课程代号）、GetName（获得课程名称）、GetLesScore（获得课程学分）、GetLesNo（获得课程序号）、GetSelect（获得是否选择过的标志变量）、SetSelect（设置选择控制标志变量）和SetName（单独定义设置课程名称），用来实现相关的操作功能。计算机系一共有65门课程，其中相互之间存在依赖关系的课程有56门，另外9门为独立课程，不存在依赖关系。Lesson B65定义课程类的对象数组，可以通过调用课
7、程类的各种成员函数对65门课程的课程序号、课程代号、课程名称以及课程学分等等进行操作。3.2 邻接表类的定义邻接表是一种顺序存储与链接存储相结合的存储方法。在邻接表中存在两种结点结构：顶点表结点和边表结点，如图3.1所示。adjlist next Indegree vertex firstedge 顶点表结点 边表结点图3.1邻接表表示的结点结构采用C+中的结构类型描述上述结点，用 C+中的类实现基于邻接表存储结构下图的各种数据类型和操作功能。由于采用了C+的模板机制，邻接表中的数据元素可以是任意的。在本次课程设计中，邻接表中的数据元素初始化为课程类对象。3.3 重要函数的实现（1）邻接表构造
8、函数ALGraph邻接表构造函数ALGraph(T a,int n,int e,int edge73) ，初始化一个有n个顶点、e条边和73个依赖关系的AOV网。当定义一个邻接表类的对象时，调用该构造函数，通过实参与形参相结合，实现课程信息的存储，建立AOV网，实现课程及课程之间的关系。流程图如图3.2所示。初始化顶点表初始化边表，并在相应的边表中插入结点结束运行图3.2 邻接表ALGraph的构造函数（2）邻接表成员函数TopSort邻接表成员函数TopSort(T OutLes10100,T B65)按批次扫描AOV网，每次扫描后都将得到的入度为0的顶点依次存入数组的每行，同时对存入顶点的
9、后继顶点进行入度减1操作。不同批次扫描得到的顶点存在数组的不同列。在此函数中通过用户的输入，还实现了专业课选择操作，并且实现了相关的输出功能。邻接表成员函数TopSort流程图如图3.3所示。所有顶点是否处理完？将入度为0的顶点入栈是否为空？用数组OutLes保存每次入栈的入度为0的顶点；并进行相应的调整。将当前结点的后继结点减1输出课程名称对每个学期的课程量进行控制图3.3邻接表类成员函数TopSort否是否是运行结束（3）邻接表类成员函数BalanScore邻接表类成员函数BalanScore(T OutLes10100,int count,int s,float score,T B65)
10、主要通过设置学分变量对每个学期的课程量进行控制，以实现不同学期的课程数目大致相等。对于某个学期课程学分未达到最少修读学分的问题，主要通过插入独立课程补足学分解决，同时在插入的同时设置学分上限，以免超过学分修读范围。最后将课程信息按不同学期依次进行输出。邻接表类成员函数BalanScore流程图如图3.4所示。运行学分是否21？显示可以进行选择的课程信息进行选择学分是否在2129总学分29本次选择无效，重新选择输出课程信息结束否是否是是否图3.4邻接表类成员函数BalanScore4 运行环境与测试结果4.1 运行环境在本课程设计中，系统开发平台为Windows XP,程序运行环境为Visual
11、 C+ 6.0，程序设计语言为C+。Visual C+一般分为三个版本：学习版、专业版和企业版，不同版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。Visual C+以拥有“语法高亮”，IntelliSense（自动编译功能）以及高级除错功能而著称。比如，它允许用户进行远程调试和单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及建置系统以预编译头文件、最小重建功能及累加链接著称。这些特征明显缩短程式编辑、编译及链接的时间花费，在大型软件计划上尤其显著。Visual C+ 6.0
12、秉承Visual C+ 以前版本的优异特性，为用户提供了一套良好的开发环境，主要包括文本编辑器、资源编辑器、工程创建工具和Debugger调试器等等。用户可以在集成开发环境中创建工程，打开工程，建立、打开和编辑文本，编译、链接、运行和调试应用程序。4.2 测试结果（1）对所有课程输出情况的测试在主函数运行初，先利用课程类定义了对象数组，通过对象数组调用了各种成员函数，实现对计算机系本科课程信息的总体输出。同时，使用制表符和设置宽度函数，调整输出结果，使查看更清楚。计算机系本科课程信息部分输出如图4.1所示。图4.1部分本科课程输出（2)对利用学分均匀每学期课程量的测试输出数组OutLes101
13、00第一行元素保存的课程名称，即第一学期课程名称，独立课程暂时不计入内。如图4.2所示。图4.2排序输出及已选学分学分未达到修读要求，根据提示选择可选的独立课程补足学分。具体情况如图4.2、4.3和4.4所示。图4.3提示输入选择课程的序号图4.4提示与选择当所选课程的学分已大于学分修读下限时，此时停止选择，输出第1个学期的课程信息。第1个学期的课程信息输出情况如图4.4所示。图4.4第1个学期课程信息（3）对选择专业选修课的测试当排序输出过程中遇到专业选修课时，可以通过根据提示输入所选课来进行选择，如图4.5所示。图4.5选择专业选修课（4）对计算机系本科课程安排计划的输出测试通过对课程排序
14、、保存、判断、选择和插入等一系列操作，最终解决计算机系本科课程的编制的问题，并输出结果。前3个学期的课程安排计划输出如图4.6、4.7和4.8所示。图4.6第1个学期的课程安排计划图4.7第2个学期的课程安排计划图4.8第3个学期的课程安排计划5 课程设计心得体会；在这次课程设计中我又进一步地了解了数据结构中算法的核心思想的重要性，懂得了一个程序地好坏关键在于算法是否优秀，一个好的优秀的算法可以使我们的程序更加完善，安全性更高以及有更高的效率。这次设计中我发现了自己的许多不足，如对指针的机制掌握的还不是很透彻，有的时候会出现指针指向错误以及空指针的错误,还有不能很好地分析自己算法地复杂度以及不
15、能很好地使用控制机制使自己的程序流畅地运行。#ifndef GRAPH_H /定义头文件#define GRAPH_H #include using namespace std;/定义边表结点struct ArcNode int adjvex; /邻接点域ArcNode *next;/定义顶点表结点templatestruct VertexNode T vertex; /数据域int indegree; /入度ArcNode *firstedge;const int MaxSize=56; /图的最大顶点数templateclass ALGraphpublic:ALGraph(T a,int
16、n,int e,int edge73); /构造函数，初始化一个有n个顶点e条边73个依赖关系的图ALGraph(); /析构函数，释放邻接表中各边表结点的存储空间void TopSort(T OutLes10100,T B64) ;/排序并进行相应的输出,按批次保存顶点，并且每次保存的顶点入度都为0void BalanScore(T OutLes10100,int count,int s,float score,T B64);/平衡每次输出的顶点的量private:VertexNode adjlistMaxSize; /存放顶点表的数组int vertexNum,arcNum; /图的顶点数
17、和边数;#endif/定义邻接表的cpp文件#include#include graph.h/引入头文件/邻接表构造函数ALGraphtemplateALGraph:ALGraph(T a,int n,int e,int edge73) int i1,j1; /边所依附的两个顶点的序号 int lat=-1;vertexNum=n;arcNum=e; /输入顶点信息，初始化顶点表for(int i=0;ivertexNum;i+) adjlisti.vertex=ai; /ai为输入的课程信息，通过实参与形参结合实现课程信息存储adjlisti.firstedge=NULL;adjlisti.
18、indegree=0; /根据数组中调出的每一条边的信息，初始化边表，并在相应的边表中插入结点for(int k=0;karcNum;k+) i1=edge0+lat;j1=edge1lat; couti1j1 adjvex=j1; /生成一个边表结点ss-next=adjlisti1.firstedge; /将结点s插入到结点i的边表的表头adjlisti1.firstedge=s; /最后生成i-jadjlistj1.indegree=adjlistj1.indegree+1; /入度加1/邻接表的析构函数ALGraphtemplateALGraph:ALGraph()for(int i=
19、0;inext;delete p;p=adjlisti.firstedge; /排序并进行相应的输出,按批次保存顶点入二维数组OutLes，并且每次保存的顶点入度都为0templatevoid ALGraph:TopSort(T OutLes10100,T B65) /采用顺序栈并初始化，累加器初始化int count=-1;int top=-1; int s;int S100;int b=0;int m; /按批次将入度为0的顶点入栈for(int i=0;ivertexNum; i=i+m ) count+;for(int k=0;kadjvex;adjlistk.indegree-; /
20、将入度减1p=p-next;/对每个顶点的相关信息进行输出，暂时不计独立的顶点/在本程序中顶点的类型其实就是课程类/所以下面的循环就是对课程的课程名称进行输出，暂时不计独立的科目for( ;bcount+1;b+) coutendl;cout第b+1个学期课程的课程名称如下：endl;cout说明：独立的课程暂时不计入内endl;coutendl;float score=0;for(int a=0;as;a+) /对专业选修课进行选择if(OutLesba.GetName()=JAVA程序设计（C#程序设计）)cout请从JAVA程序设计和C#程序设计中任选一门您的专业选修课endl;stri
21、ng p2=JAVA程序设计,C#程序设计;int q;cout选择JAVA程序设计，则请输入0；否则输入1q;while(!(q=0|q=1);coutpqendl;OutLesba.SetName(pq);elsecoutOutLesba.GetName()endl;/提示用户所选的课程名称score=score+OutLesba.GetLesScore();/对学分进行统计 BalanScore(OutLes, count, s,score, B);/平衡每次输出的顶点的量/在本例中其实就是利用学分变量对每个学期的课程量进行控制templatevoid ALGraph:BalanScor
22、e(T OutLes10100,int count,int s,float score,T B65)/学分的控制范围为21score29if(!(21score)float Allscore=163;/总学分数为163float Avescore=Allscore/7;/每个学期平均学分数coutn每个学期平均学分数为：Avescoren您每个学期所选的课程学分应大于Avescore-2且小于Avescore+6endl;/输出每个学期的平均学分数以及学分修读范围要求 /对课程量不够的学期，增加一定量的课程，直到达到学分修读要求为止coutn本学期课程量不够，请从以下课程中选择一定量的课程，以
23、满足学分修读要求nendl;for(int i=56;i65;i+)/对已选的课程进行排除，避免重复选择if(!Bi.GetSelect()cout序号:Bi.GetLesNo() 课程代号: Bi.GetNum()t课程名称: setw(32)Bi.GetName()t课程学分: Bi.GetLesScore()tendl;/用学分对每个学期的课程量进行控制while(!(Avescore-2)score&score(Avescore+6)coutn您现在已选学分为：scoreendl;/提示用户已选学分数cout请您输入所选课程的序号Number; /用户输入所选课程序号if(score+
24、BNumber.GetLesScore()29)cout您所选的课程为：BNumber.GetName()endl;/提示用户所选的课程名称OutLescounts+=BNumber;score+=BNumber.GetLesScore();/学分累加BNumber.SetSelect(true);/对已选课程进行标记/对学分超过的情况进行重新选课else cout您所选课程的学分超过了学分修读范围，请重新选课endl;/对每个学期的课程进行输出，完成教学计划的编制coutn第count+1个学期的课程如下：nendl;for( int h=0;hs;h+)/使用制表符和设置宽度函数对输出信息
25、进行美化，方便用户查看 cout序号:OutLescounth.GetLesNo() 课程代号: OutLescounth.GetNum()t课程名称: setw(22)OutLescounth.GetName()t课程学分: OutLescounth.GetLesScore()tendl;/计算机系本科课程信息/定义头文件#ifndef INFORMATION_H #define INFORMATION_H #include using namespace std;/参与依赖关系的课程的代号string newLesNum56=C1,C2,C3,C4,C5,C6,C7, C8,C9,C10,
26、C11,C12,C13,C14,C15,C16,C17,C18,C19,C20,C21,C22,C23,C24,C25,C26,C27,C28,C29,C30,C31,C32,C33,C34,C35,C36,C37,C38,C39,C40,C41,C42,C43,C44,C45,C46,C47,C48,C49,C50,C51,C52,C53,C54,C55,C56;/独立的课程的代号string depLesNum9=L1,L2,L3,L4,L5,L6,L7,L8,L9;/参与依赖关系的课程的名称string newLesName56= C+程序设计基础,高等数学A（一）,计算机科学导论,大学
27、英语（一）,C+课程设计,大学物理（上）,高等数学A（二）,线性代数,体育（一）,大学英语（二）,体育（二）,VC+课程设计,大学物理(下),大学物理实验,汇编语言A,计算机电路,离散数学,体育（三）,大学英语（三）,数据结构A,数据库基本原理与技术,大学英语（四）,体育（四）,概率论与数理统计B,数字逻辑与数字系统,数据库系统应用课程设计,编译原理与技术A,操作系统B,计算机网络原理与技术B,计算机组成原理,数据结构课程设计,专业英语,计算机组成原理课程设计, C+程序设计,XML与Web应用技术,高级操作系统分析,接口技术,嵌入式系统B,软件工程A,网络系统课程设计,电子商务软件及其开发技
28、术,多媒体技术,算法分析与设计,计算机体系结构,方向课程综合课程设计,软件工程课程设计,微机生产实习,图形图象处理技术,计算机网络工程设计,大型数据库设计,分布式数据库管理,嵌入式操作系统,嵌入式系统设计,网络管理及安全,中间件技术,人工智能导论;/独立的课程的名称string depLesName9= 大学生学习方法指导,军事理论,军训,大学生心理健康,思想道德修养及法律基础,中国现代史纲要,人文类选修课,马克思主义基本原理,毛泽东思想、邓小平理论和“三个代表”重要思想概论;/参与依赖关系的课程的学分float newLesScore56= 3,5,2,4,3,2.5,5,2,1.5,4,1
29、.5,2,3.5,2,3,5,2.5,1.5,4,3,3,4,1.5,2.5,3.5,2,3,2,3,3,2,2,2,3,3,2,3,2,3,2,2,2,2.5,2,2,2,2,2.5,3,2,2,2,2,3,2,2; /独立的课程的学分 float depLesScore9=0.5,1,3,1,2,2,8,3,3;/为所有课程编的序号，以方便对课程进行各种操作int newLesNo65;/课程之间的依赖关系int fomer=2;int later=73;int edge273=0,1,1,1,3,8,0,4,5,5,0,2,4,5,1,6,7,10,9,0,2,16,0,16,18,17
30、,0,6,16,15,20,19,19,19,24,19,21,24,19,29,27,29,29,27,19,33,28,19,20,33,19,20,33,19,33,27,37,38,43,41,28,39,38,38,35,37,37,28,39,20,38,29,43, 4,5,6,7,9,10,11,11,12,13,14,14,14,15,16,16,16,17,18,19,19,19,20,20,21,22,23,23,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,37,38,38,39,40,40,40,41,41,41,42,42
31、,43,44,45,46,47,48,48,49,50,51,51,52,53,53,54,54,55,55;#endif;/引入头文件#include#include#include#includegraph.cpp#includeinformation.husing namespace std;/使用命名空间/课程类的定义class Lessonpublic:/对课程的各种属性进行赋值 void SetLes(string inLesNum,string inLesName,float inLesScore,int inLesNo,bool inSelect=false);string G
32、etNum()return LesNum; /获得课程代号string GetName()return LesName; /获得课程名称float GetLesScore()return LesScore; /获得课程学分int GetLesNo()return LesNo;/获得课程序号bool GetSelect()return Select;/获得是否选择过的标志变量void SetSelect(bool Select)this-Select=Select;/设置选择控制标志变量，以避免重复选课void SetName(string newname)LesName=newname;/单独
33、定义设置课程名称的函数，以方便一些操作private:string LesNum;/课程代号string LesName;/课程名称float LesScore;/课程学分int LesNo;/课程序号bool Select;/是否选择过的标志;/成员函数的实现void Lesson:SetLes(string inLesNum,string inLesName,float inLesScore,int inLesNo,bool inSelect)LesNum=inLesNum;LesName=inLesName;LesScore=inLesScore;LesNo=inLesNo;Select
34、=inSelect;/主函数int main()/给对每门课程编个序号for(int k=0;k65;k+)newLesNok=k;int n=65; /65门课程int e=73; /所有课程中一共有73个依赖关系Lesson B65;/输出存在依赖关系的课程信息int x,y,z,u,v,w,j;x=y=z=u=v=w=j=0;cout参与依赖关系的课程如下：endl; coutendl;for(int i=0;i56;i+)/利用数组对课程类对象成员进行赋值Bi.SetLes(newLesNumx+,newLesNamey+,newLesScorez+,newLesNoj+);/使用制表符和设置宽度函数对输出信息进行美化，方便用户查看cout序号:Bi.GetLesNo() 课程代号: Bi.GetNum()t课程名称: setw(22)Bi.GetName()t课程学分: Bi.GetLesScore()tendl;coutendl;/输出不存在依赖关系的课程信息cout不参与依赖关系的课程即独立课程如下：endl;coutendl;for(;i65;i+)Bi.SetLes(depLesNumu+,depLesNamev+,depLesScorew+,newLesNoj+);cout序号:Bi.GetLesNo()t
