数据结构C++课程设计报告教学计划编制问题.docx
- 文档编号:13418480
- 上传时间:2023-06-14
- 格式:DOCX
- 页数:30
- 大小:270.63KB
数据结构C++课程设计报告教学计划编制问题.docx
《数据结构C++课程设计报告教学计划编制问题.docx》由会员分享,可在线阅读,更多相关《数据结构C++课程设计报告教学计划编制问题.docx(30页珍藏版)》请在冰点文库上搜索。
数据结构C++课程设计报告教学计划编制问题
数据结构(C++)课程设计报告--教学计划编制问题
上海电力学院
数据结构(C++)课程设计
题 目:
教学计划编制问题
******
学号:
********
院 系:
计算机科学与技术学院
专业年级:
信息安全2011级
2013年 07月 04日
一、设计题目
大学的每个专业都要编制教学计划。
假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限都相等。
每个专业开设的课程都是确定的,而且课程的开设时间的安排必须满足先修关系。
每个课程的先修关系都是确定的,可以有任意多门,也可以没有。
每一门课程恰好一个学期。
试在这样的情况下设置一个教学计划编制程序。
在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息。
本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程。
二、需求分析
(一)运行环境(软、硬件环境)
设计环境和器材——
硬件:
计算机
软件:
MicrosoftVisulaC++
在本课程设计中,系统开发平台为WindowsXP或Win7,程序运行环境为VisualC++6.0,程序设计语言为C++。
VisualC++一般分为三个版本:
学习版、专业版和企业版,不同版本适合于不同类型的应用开发。
实验中可以使用这三个版本的任意一种,在本课程设计中,以VisualC++6.0为编程环境。
VisualC++以拥有“语法高亮”,IntelliSense(自动编译功能)以及高级除错功能而著称。
比如,它允许用户进行远程调试和单步执行等。
还有允许用户在调试期间重新编译被修改的代码,而不必重新启动正在调试的程序。
其编译及建置系统以预编译头文件、最小重建功能及累加链接著称。
这些特征明显缩短程式编辑、编译及链接的时间花费,在大型软件计划上尤其显著。
VisualC++6.0秉承VisualC++以前版本的优异特性,为用户提供了一套良好的开发环境,主要包括文本编辑器、资源编辑器、工程创建工具和Debugger调试器等等。
用户可以在集成开发环境中创建工程,打开工程,建立、打开和编辑文本,编译、链接、运行和调试应用程序。
(二)输入的形式和输入值的范围
数据输入的方式是键盘输入。
输入的数据多是整型的或是浮点型的,还有一些字符(以中文的形式)。
输入的数值型的数据大都是小于100的数值。
(三)输出的形式描述
输出的是教学编制计划,就是形如:
“第二学期学的课程有:
普通物理线性代数汇编语言”这样的形式。
(四)功能描述
输入参数包括:
学期总数,一学期的学分上限,每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
允许用户指定下列两种编排策略之一:
一是使学生在各学期中的学习负担尽量均匀;二是使课程尽可能地集中在前几个学期中。
若根据给定的条件问题无解,则报告适当的信息;否则将教学计划输出到用户指定的文件中。
计划的表格格式自行设计。
(五)测试数据
学期总数:
6
学分上限:
10
该专业共开设12门课,课程号从01~12,学分顺序为2,3,4,2,2,4,4,4,7,5,2,3。
三、概要设计
(一)抽象数据类型定义描述
(对各类的成员及成员函数进行抽象描述,参见书或ppt及实验)
抽象数据类型:
为实现上述功能需建立一个结点类,线性表类,图类。
ADTGraph{
数据对象V:
V是具有相同特性的数据元素的集合,称为顶点集.
数据关系R:
R={VR}
VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}
基本操作P:
voidcreatpre(AlGraph*CGraph);
voidfindindegree(AlGraph*CGraph,intindegree[]);
voidlayout1(AlGraph*CGraph,queue*q);
voidlayout2(AlGraph*CGraph,queue*q);
}ADTGraph
队列的定义:
ADTList{
数据对象:
D={ai|ai∈ElemSet,i=1,2,…n,n>=0}
数据关系:
R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}
基本操作:
voidqueue_init(queue*q);
voidqueue_in(queue*q,intx);
intqueue_out(queue*q);
intqueue_empty(queue*q);
}ADTStack
(二)功能模块设计
主程序:
voidmain()
{
intchoice;
queueq;
Queue.queue_init(&q);
AlGraphCGraph;
CGraph=Graph.input();
system("cls");
Graph.output(CGraph);
cout< Judgement.judgingcricle(&CGraph,&q); if(! WhetherCricle) { while (1) { cout<<"请选择编排策略: \t"< cout<<"1.使学生在各学期中的学习负担尽量均匀;\t"< cout<<"2.使课程尽可能地集中在前几个学期中。 \t"< cout<<"请选择: "; cin>>choice; system("cls"); if(choice==1) Edit.layout1(&CGraph,&q); else Edit.layout2(&CGraph,&q); cout<<"请选择继续编排策略或退出程序(0退出1继续): \t"< cin>>choice; system("cls"); if(choice==0) break; } } } (三)模块层次调用关系 本程序只有两个模块,调用关系简单 主程序模块→拓扑排序模块 TopSort流程图: 邻接表构造函数ALGraph 邻接表ALGraph的构造函数 四、详细设计 教学计划编制系统主要是处理课程之间的依赖关系。 表列出了若干门计算机系本科课程,其中有些课程不要求先修课程,例如,C1是独立于其他课程的基础课,而有些课程却需要有先修课程,比如,学完程序设计语言C++和离散数学后才能学习数据结构。 课程代号 课程名称 先修课程 C1 高等数学 无 C2 计算机科学导论 无 C3 离散数学 C1 C4 程序设计语言C++ C1、C2 C5 数据结构 C3、C4 C6 计算机原理 C2、C4 C7 数据库原理 C4、C5、C6 先修课程规定了课程之间的依赖关系,这种关系可以用AOV网来表示,其中顶点表示课程,弧表示依赖关系。 程序的主要功能是实现课程的排序,以满足同一学期所修的课程相互之间无依赖关系,并且已修完其所有先修课程。 本程序需要基于图的基本操作来实现 算法的基本思想: 1、图的构建: 建立一个结点类,类的元素有字符型变量用来存储字母,整形变量用来存储位置,该类型的指针,指向下一个元素。 建立一个线性表类,完成线性表的构建。 建立一个图类,完成图的信息的读取,(如有n个点,则建立n个线性表,将每个结点与其指向的结点组成一个线性表,并记录线性表的长度)。 2、Topsort算法: 先计算每个点的入度,保存在数组中。 找到第一个入度为0的点,将该点所连的各点的入度减一。 再在这些点中找入度为0的点。 如果找到,重复上述操作。 如果找不到,则跳出while循环,再搜索其他的点,看入度是否为0。 再重复上述操作,如果所有的入度为0的点都被寻找到,但个数少于输入顶点的个数,说明该图存在环。 3、邻接表类的定义 邻接表是一种顺序存储与链接存储相结合的存储方法。 在邻接表中存在两种结点结构: 顶点表结点和边表结点。 五、调试分析 包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。 (一)实验过程中出现的问题及解决方法 我在实验过程中遇到的最大难题是两个课程排序算法的编写。 刚开始的时候没有任何的思路,网上也只有拓扑排序的算法,对于课程设计要求的排序算法没有任何头绪。 经过请教老师和同学以及翻阅了一些相关书籍,并在网上的搜索有了排序算法的大体思路。 经过三天的修改,终于写出了符合要求的排序算法。 (二)实验体会 上机实践是学生对本门课程所学知识的一种全面、综合的能力训练,是与课堂听讲、自学和练习相辅相成必不可少的一个教学环节,也是对课堂教学效果的一种检验。 通常,实习题中的问题比平时的习题复杂得多,也更接近实际。 实习题注重原理与应用的结合,目的让学生学会如何把书上学到的知识运用于解决实际问题的过程中去,培养从事软件开发设计工作所必需的基本技能。 同时,通过实践能使书上的知识变“活”,起到深化理解和灵活掌握教学内容的作用。 平时的练习较偏重于如何编写功能单一的“小”算法,而实习题是软件设计的综合训练,包括问题分析,总体结构设计,用户界面设计,程序设计基本技能和技巧,可以多人合作,有利于一整套软件工程规范的训练和科学作风的培养。 此外,实践环节中有很重要的一点,就是机器是比任何教师都严格的主考官。 经过此次课程设计,我认识到了理论与实践结合的重要性,仅仅只是从课本上学到算法原理是远远不够的。 在实践中,我们总会出现许多错误。 这就要求我们以一个脚踏实地的态度来处理问题。 我深刻地认识到自己写程序的不足,使我们学到了好多有用的知识,让我们明白了C++语言的语句用法。 六、测试结果 要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分,按照出现的每一步来输入该课程设计所提供的相关数据。 学期总数: 6;学分上限: 10;该专业共开设12门课,课程号从01到12,学分顺序为2,3,4,2,2,4,4,4,7,5,2,3。 然后还要输入课程先修课程总数,可以算出有16种关系,分别输出。 接着程序会根据这些数据,自动生成建立好的邻接表,用户可以根据系统显示的选择编排策略进行选择,有两种编排策略,最后结果体现在实验的正确测试结果里。 输入的内容如下: 课程编号课程名称 学分 先决条件 01 计算机基础 2 无 02 离散数学 3 01 03 数据结构 4 01,02 04 汇编语言 2 01 05 语言的设计和分析2 03,04 06 计算机原理 4 10 07 编译原理 4 05,03 08 操作系统 4 03,06 09 高等数学 7 无 10 普通物理 5 09 11 线性代数 2 09 12 数值分析 3 09,11,01 七、附录: 程序设计源代码 #include #include #include #include usingnamespacestd; #definenull0 #defineMAX_COURSE_NUM100//最大课程个数 typedefstruct { charc[3]; }cid;//课程号 typedefstructCourse { cidid[3]; charname[30]; floatxf; }Course;//课程 typedefstructPreCourse { intadjvex; structPreCourse*nextarc; }PreCourse;//先修的课程节点 typedefstruct { Coursecourse; PreCourse*firstarc; }CourseNode;//课程节点 typedefstruct { CourseNodecourses[MAX_COURSE_NUM];//邻接表 intxqs; intnum; floatxfsx; }AlGraph;//课程图 typedefstruct { intdata[MAX_COURSE_NUM]; intf,r; }queue; intWhetherCricle=0; intjxq; classQueue { public: voidqueue_init(queue*q); voidqueue_in(queue*q,intx); intqueue_out(queue*q); intqueue_empty(queue*q); }Queue; voidQueue: : queue_init(queue*q)//队初始化 { q->f=q->r=0; } voidQueue: : queue_in(queue*q,intx)//入队 { if((q->r+1)%MAX_COURSE_NUM==q->f) { cout<<"队满\t"< exit(0); } q->r=(q->r+1)%MAX_COURSE_NUM; q->data[q->r]=x; } intQueue: : queue_out(queue*q)//出队 { if(q->f==q->r) { cout<<"队空\t"< exit(0); } q->f=(q->f+1)%MAX_COURSE_NUM; returnq->data[q->f]; } intQueue: : queue_empty(queue*q)//队判空1为空 { if(q->f==q->r) return1; elsereturn0; } classGraph { public: AlGraphinput(); voidoutput(AlGraphCGraph); voidcreatpre(AlGraph*CGraph); }Graph; voidGraph: : creatpre(AlGraph*CGraph)//建立先修关系 { system("cls"); intchoice; inti,n; intj; PreCourse*p,*q; cout< \t"< cout< \t"< for(i=0;i { if(i%4==0) cout< cout<<"("< printf("%s\t",CGraph->courses[i].course.id); } cout< cout<<"\n请根据以上的编号,输入每一门课程的先修课程号的编号(输入0表示没有或结束): \t"< for(i=0;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"; else cout<<"输入的先修课程号不在该专业开设的课程序列中"< 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; } AlGraphGraph: : input()//输入并建立课程图 { AlGraphCGraph; intxqzs=0,kczs=0; inti; intchoice; floatxf,xfsx=0; cout<<"教学计划编制\n"< 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位的字母数字串)、课程名、学分——"< for(i=0;i { cout<<"课程号: "; scanf("%s",CGraph.courses[i].course.id); cout<<"课程名: "; scanf("%s",CGraph.courses[i].course.name); cout<<"学分: "; cin>>xf; cout< while(xf>xfsx||xf<=0)//判断输入的学分是否合格 { cout<<"输入的学分有误,请重新输入学分: "; cin>>xf; } CGraph.courses[i].course.xf=xf; CGraph.courses[i].firstarc=null; } cout<<" (1)重新输入\t"<<" (2)确定"< cout<<"请选择: "; cin>>choice; if(choice==1) { system("cls"); input(); } else { creatpre(&CGraph);//建立先修关系 returnCGraph; } } voidGraph: : output(AlGraphCGraph)///输出先修关系 { inti,j,n; PreCourse*p; cout<<"先修关系如下: \n"< cout<<"课程编号\t"<<"课程名称\t"<<"先决条件"< for(i=0;i { printf("%s\t\t%s\t\t",CGraph.courses[i].course.id,CGraph.courses[i].course.name); 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< } } classJudgement { public: voidfindindegree(AlGraph*CGraph,intindegree[]); voidjudgingcricle(AlGraph*CGraph,queue*q2); }Judgement; voidJudgement: : findindegree(AlGraph*CGraph,intindegree[]) { inti; PreCourse*p; for(i=0;i { indegree[i]=0; p=CGraph->courses[i].firstarc; while(p) { indegree[i]++; p=p->nextarc; } } } voidJudgement: : judgingcricle(AlGraph*CGraph,queue*q2)//判断是否有环和课程入队 { intindegree[MAX_COURSE_NUM];//入度 inti,m,j,pd=0; floatxf=0; PreCourse*p; queueq; Queue.queue_init(&q);//队初始化 findindegree(CGraph,indegree);//找入度 for(i=0;i { if(indegree[i]==0&&(xf+CGraph->courses[i].course.xf)<=CGraph->xfsx) { Queue.queue_in(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 C+ 课程设计 报告 教学计划 编制 问题