面向对象程序设计C++课程设计指导书文档格式.docx
《面向对象程序设计C++课程设计指导书文档格式.docx》由会员分享，可在线阅读，更多相关《面向对象程序设计C++课程设计指导书文档格式.docx（23页珍藏版）》请在冰点文库上搜索。
C++是一种混合性语言，它既具有独特的面向对象的特征，又保留传统的高效结构化程序设计语言C的主要特征。
因此，可以说C++是包含支持面向对象程序设计和C语言的一个超集，C++全面支持数据抽象、数据封装、继承性和多态性。
无论是使用面向对象程序设计语言，还是结构化程序设计语言，最重要的一个方面就是“算法”，可以说：
算法是一个程序的灵魂。
一个好的算法是可以使用任何语言实现的，即“编程语言的无关性”。
本书就是从算法出发，重点介绍了几个常用的数值计算算法和非数值计算算法的基本思想和分析过程，并配以相应的设计练习题目来完成对本算法的应用。
对于一种算法，可以有许多种变换形式，本文中只是做一简单介绍，希望学生在今后的学习中多注重算法的学习和把握。
鉴于时间仓促和编者水平有限，对于本书中存在的错误和不足，敬请各位同学和教师批评指正。
第一章概述
1．1课程设计目的
C++语言是世界上最流行和实用的一种计算机高级程序设计语言，它具有丰富的数据类型和各种运算功能，带有庞大的函数库和类库，既支持面向过程的程序设计，又支持面向对象的程序设计，因此是目前进行计算机软件开发的重要工具之一。
它作为一门专业基础课程，贯穿于数据结构、操作系统、数据库、软件工程等所有后续课程始终，因此，学生更好的掌握C++语言的程序设计技能可以为将来的各门课程学习打下坚实的基础。
面向对象程序设计语言C++语言是从早期的C语言逐渐发展演变而来，它对C语言不是简单的扩充。
C++语言保留了C语言的灵活性，并且具有强有力处理软硬件接口和低层系统程序设计的能力；
C++语言保留了C语言的紧凑性和强有力的表达式功能；
更重要的是C++语言提供了支持面向对象程序设计和高层问题抽象的平台。
在面向对象程序设计方法中，属性和方法是类设计的重要方面，而方法中又遵循了过程化程序设计思路，因此，这两种程序设计方法是互相联系，互为应用的。
C++语言课程设计，主要训练学生的独立思考能力和动手能力；
培养学生在过程化程序设计方法和面向对象程序设计方法的应用和结合；
培养学生对计算机算法的理解和应用。
学生通过算法分析和设计，最后使用C++语言编译环境运行该算法程序，加深对计算机算法的理解和应用。
同时，掌握一种问题的分析和解决方法。
在课程设计过程中，学生重点掌握过程化程序设计方法的设计过程，并加深对面向对象的程序设计方法的理解和应用，提高C++语言程序设计的综合能力。
1．2基本要求
为了更好的完成本次课程设计的目的，为了使学生真正领悟过程化程序设计方法和面向对象程序设计方法，学生必须严格按照要求完成设计题目。
具体要求如下：
1、学生需要至少完成九道设计题目中的6道设计题目的算法分析和设计，应用程序流程图（或N_S流程图）表示分析和设计结果；
2、学生必须完成对至少20个设计联系题目的编程测试任务。
3、如果学生在课程设计时间内完成了要求的设计题目，可以同教师联系，教师可以另外补充设计题目。
4、学生必须完成全部面向对象设计题目的调试、运行任务，并基本理解程序设计思想和编程方法。
5、课程设计结束后，学生需要参加答辩或最后的实际上机编程考核。
同时，学生需要提交设计报告一份，报告中包括全部的算法分析和设计流程图，并打印程序清单。
6、教师每天必须检查学生的设计情况，并认真登记，作为最后的考评依据。
1．3考核方法和成绩评定
1.3.1考核方法
在设计考核中主要采用如下三个方面：
a.算法分析、设计和实际操作技能课程设计过程中，教师检查学生的算法分析和设计流程图，并在计算机上检查学生调试和运行程序的情况，为每个学生进行评分。
b.答辩或应试操作能力在课程设计结束后，学生就课程设计的设计思想和面向对象理论进行答辩，或参加最后一次的上机实际操作编程考试。
教师根据情况为学生进行评分。
c.课程设计报告在课程设计结束后，学生提交应用程序文档，应用程序清单和课程设计报告，教师根据文档资料的书写和学生对理论和设计内容的理解，为每个学生进行评分。
1.3.2成绩评定
根据课程设计考核办法，各方面成绩占总成绩的比例为：
a.算法分析、设计和实际操作技能占总成绩的比例为：
60%
b.答辩或应试操作能力占总成绩的比例为：
20%
c.课程设计报告占总成绩的比例为：
第二章程序设计方法与常用算法
2．1程序设计与算法
2.1.1算法
算法是解决问题方法的精确描述，但是并不是所有问题都有算法，有些问题经研究可行，则相应有算法；
而有些问题不能说明可行，则表示没有相应算法，但这并不是说问题没有结果。
例如：
猜想问题，有结果，然而目前还没有算法。
1、算法的性质
（1）解题算法是一有穷动作序列。
（2）动作序列仅有一个初始动作。
（3）序列中每个动作的后继动作是确定的。
（4）序列的终止表示问题得到解答或问题没有解答。
2、待解问题的表述
待解问题的表述应精确、简练、清楚，使用形式化模型刻划问题是最恰当的。
使用数学模型刻划问题是最简明、严格的，一旦问题形式化了，就可依据相应严格的模型对问题求解。
3、算法分类
根据待解问题刻划的形式模型和求解要求，算法可以分成两大类：
数值的和非数值的。
数值的算法是以数学方式表示的问题求数值解的方法。
代数方程计算、矩阵计算、线性方程组求解、函数方程求解、数值积分、微分方程求解等；
非数值的算法通常为求非数值解的方法，例如：
排序查找、模式匹配、排列模拟、表格处理、文字处理等。
4、算法设计
算法设计的任务是对各类具体问题设计良好的算法及研究设计算法的规律和方法。
常用的算法设计方法有：
数值算法（如：
迭代法、递归法、插值法等）；
非数值算法（如：
分治法、贪婪法、回溯法等）。
5、算法分析
算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于那类问题，或某类问题宜采用那种算法。
算法的复杂度分时间复杂度和空间复杂度。
设问题规模以某种单位由1增至n，研究解决问题的具体算法。
在运行算法时所耗费的时间为f（n）（即n的函数），实现算法所站用的空间为g（n）（也为n的函数），则称O（f（n））和O（g（n））为该算法的复杂度。
2.1.2结构程序设计
1、程序
程序是对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人称：
数据结构+算法=程序。
2、程序设计
程序设计实际就是设计、编制和调试程序的过程。
3、结构化程序设计
结构化程序设计就是利用逐步精化的方法，按照一套程式化的设计准则进行程序的设计。
由这种方法产生的程序是结构良好的，所谓“结构良好”是指：
（1）易于保证和验证其正确性
（2）易于阅读、易于理解和易于维护。
按照这种方法或准则设计出的程序称为结构化的程序。
“逐步精化”是对一个复杂问题，不是一步编成一个可以执行的程序，而是分布进行。
第一步编出的程序抽象级最高；
第二步编出的程序抽象级比第一步低；
依次类推，第i步编出的程序抽象级比第i–1步低；
直到最后，第n步编出的程序即为可以执行的程序。
所谓“抽象程序”是指程序所描述的解决问题的处理规则，是由那些“做什么”操作组成，而不涉及操作“怎样做”以及解决问题的对象具有什么结构，不涉及几构造的每个局部细节。
采用“逐步精化”方法的优点是：
（1）便于构造程序。
由这种方法产生的程序，其结构清晰、易读、易写、易理解、易调试、易维护；
（2）适用于大任务、多人员设计，也便于软件管理
4、采用的设计方法
在结构化程序设计中主要采用自然语言抽象算法结构；
采用程序流程图、N_S流程图或其他流程图描述算法的执行过程。
2.1.3面向对象开发方法
面向对象开发方法是以对象为中心的开发方法，是从客观世界中抽象出来的软件开发的新的思维方法。
面向对象开发方法可以促进软件工作者在应用领域中最大限度的发挥他的才能和思维能力。
面向对象方法有如下的基本特征：
（1）对象是数据和有关操作的封装体，突破了传统的将数据与操作分离的模式，较好地实现了数据的抽象；
（2）面向对象方法的继承性体现了概念分离抽象。
在对象继承结构上，下层对象继承上层对象的特征（属性和操作），因而面向对象方法便于软件的演化和增量式扩充；
（3）现象对象方法用消息将对象动态链接在一起。
与传统的模块调用不同，现象对象方法采用了灵活的消息传递方式，从而便于在概念上提乡并行和分布式结构；
（4）面向对象方法具有信息隐藏性。
对象将其实现细节隐藏在它的内部，因此无论是对象功能的完善扩充，还是对象实现的修改，其影响仅限于该对象内部，而不会对外界产生影响。
这保证了面向对象软件的可构造性和易维护性。
面向对象开发是不依赖于程序设计语言的概念化开发过程，面向对象开发本质是一种新的符合人的思维的方式，而不是程序设计技术；
最大好处是帮助研究和开发人员清楚的表达用户所需的抽象概念，并能够将用户与研究、开发人员之间的信息相互表达、沟通。
在面向对象开发中，主要包括以下几个阶段：
（1）分析阶段（Analysis）
（2）系统设计（Systemdesign）
（3）对象设计（Objectdesign）
（4）实现阶段（Implementation）
2.1.4设计练习题目
【题目1】
按照如下要求打印九九乘法口诀表。
具体格式如下：
1*1=1
2*1=22*2=4
3*1=33*2=63*3=9
……（按以上格式进行打印）
【题目2】
已知杨辉三角形的具体形式如下，请编写程序完成10行数据的按照规则生成的数据。
具体的数据格式如下：
1
11
121
1331
14641
15101051
……
【题目3】
有17个人围成一圈（编号为：
0~16），从第0号的人开始从1开始报数，凡报到3的倍数的人离开圈子，然后再数下去。
直到最后只剩下一个人为止。
问此人原来的位置是什么号码。
2．2常用数值计算算法
在数值计算算法中主要包括：
迭代法、递推法、递归法、插值法、差分法等算法，这里只对前三种算法的基本思路进行描述，并给出相应的实验题目。
2.2.1迭代法
迭代法适用于方程（或方程组）求解，是使用间界方法求方程近似根的一种常用算法。
设方程f（x）=0，该方法将方程表示为等价形式：
x=g（x），或一般地将f（x）拆成两个函数f1和f2，即：
f（x）=f1（x）–f2（x）=0，因而有f1（x）=f2（x）。
其中f1（x）是这样一个函数，对于任意数c，容易求出f1（x）=c的精确度很高的是根。
迭代法求解算法如下：
（1）首先选一个x的近似值x0，从x0出发，代入右面函数，并解方程f1（x）=f2（x0）得到下一个近似值x1；
（2）将上次近似根x1代入右面函数，并解方程f1（x）=f2（x1），得到又一个近似根x2；
（3）重复
（2）的计算，得到一系列近似根x0,x1,x2,……,xn……
若方程有根，这数列收敛于方程的根。
若满足|xn–xn-1|<
ε，则认为xn是方程的近似根。
使用迭代法应注意：
（1）如果方程无解，数列必然不收敛，因而迭代的重复为“死循环”，所以使用迭代算法前应考虑方程是否有解。
另外，应对重复次数给予一定控制，以防止死循环。
（2）当方程有解时，若迭代公式选择不当，或初始化近似根选择不当，也会导致迭代失败，例如：
迭代公式中出现除数为0、ln0等。
（3）有时为了算法的效率，在一定精确度的条件下，利用误差理论，预先确定迭代重复次数，而不采用|xn–xn-1|<
ε的方法。
通常采用混合算法，例如计算x的平方根，先利用契比雪夫多项式（二次的）计算x的初始根，在用迭代公式yi+1=（yi+x/yi）/2迭代两次，便可以达到10-12的精确度。
2.2.2递推法
递推法实际上是需要抽象为一种递推关系，然后按照递推关系求解。
递推法通常表现为两种方式：
一是从简单推到一般；
二是将一个复杂问题逐步推到一个已知解的简单为体。
这两种方式反映了两种不同的递推方向，前者往往用于计算级数，后者与“回归”配合成为一种特殊的算法——递归法。
由简单推到一般的方法，例如：
为得到某项（组）数值，依据前面各项（组）的值推出。
通常用于计算级数的第n项的值。
2.2.3递归法
递归算法包括“递推”和“回归”两个部分。
递推就是为得到问题的解，将它推到比原问题见大的问题的求解。
n!
=f（n），为计算f（n），将它推到f（n–1），即f（n）=n*f（n–1）,这就是说，为计算f（n），将问题推到计算f（n–1），而计算f（n–1）比计算f（n）简单，因为f（n–1）比f（n）更接近已知解0!
=1或1!
=1。
使用递推应注意：
（1）递推应有终止条件，就是在此条件下问题的解是明确的，缺少终止条件便回使算法失败。
（2）“简单问题”表示离递推终止条件更为接近的问题。
简单问题与原问题其解的算法是一致的，其差别主要反映在参数上。
回归指当“简单问题”得到解后，回归到原问题的解上来。
使用回归应注意：
（1）回归到原问题的解时，算法中涉及的处理对象应是关于当前问题的，即递归算法所涉及的参数与局部处理对象是有层次的。
（2）有时回归到原问题已得到问题的解，回归并不引起其它动作。
2.2.4设计练习题目
【题目4】
用迭代法求正整数a的平方根。
（求平方根的迭代公式为：
xn+1=（xn+a/xn）/2）
【题目5】
用二分法求方程在（-10,10）之间的根。
2x3–4x2+3x–6=0
【题目6】
编写程序，求出在1到x的y次幂之间的全部素数。
要求：
1、应用递归方式编写f1函数求任意的x的y次幂；
2、编写函数f2判断任意数是否为素数；
在main（）函数中输入x和y的值，并按要求求出全部素数，并按每行5个输出求出的全部素数；
【题目7】
请应用递归方法和非递归方法实现求任意整数的n的阶乘。
2．3非数值计算算法
在非数值计算算法中主要包括：
穷举搜索法、递归法、回溯法、贪婪法、分治法等算法，这里只对前三种算法的基本思路进行描述，并给出相应的实验题目。
2.3.1穷举搜索法
穷举搜索法是穷举所有可能情形，并从中找出符合要求的解。
穷举所有可能情形，最直观的是联系循环的算法。
【题目8】
找出n个自然数（1，2，3，……，n）中r个数的组合。
n=5，r=3，所有组合为：
543
542
541
532
531
521
432
431
421
321
2.3.2递归法
递归法也是非数值计算中常用的方法。
对于【题目8】中所提示的10组数。
首先固定第一位数（如5），其后是在另4个数中再“组合”2个数。
这就将“5个数中3个数的组合”推到了“4个数中2个数的组合”上去了。
第一位数可以是n→r（如5→3），n个数中r个数组合递推为n–1个数中r–1个数的组合，这是一个典型的递归算法。
【题目9】
求1!
+2!
+3!
+....+10!
的值
2.3.3回溯法
回溯法是一种选优搜索法，按照选优条件向前搜索，以达到目标。
但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
将自然数排列在数组A中：
A[1]A[2]A[3]
543
542
321
排数时从A[1]→A[2]→A[3]，后一个至少比前一个数小1，并且应该满足ri+A[ri]>
r这个关系。
若ri+A[ri]≤r就要回溯，该关系就是回溯条件。
为直观起见，当输出一组组合数后，若最后一位为1，也应该作一次回溯（若不回溯，便由上诉回溯条件处理）。
【题目10】
对于【题目8】中要求的题目，应用回溯算法实现。
2.3.4设计练习题目
【题目11】
请用递归方法判断一行文字是否是回文。
所谓回文数是指这样的数据，它的各个位数码是左右对称的，例如：
121，676，94249等。
（提示：
设一行字符为M–W，对于M分解成由ch1表记的一个字符与一自串m；
对w分解成一字符串w和由ch2表记的一个字符，因此M–W为“回文”取决于：
（1）m–w是回文；
（2）ch1=ch2。
即将原问题递推到m–w的解。
递归终止条件是M与W（或m或w）长度为0。
“回归”时，若m–w是回文且ch1=ch2，则M–W是回文；
否则M–W就不是回文。
）
【题目12】
寻找6个成等差级数且小于160的素数。
设级数为：
n,n–d,n–2d,n–3d,n–4d,n–5d。
若这6个数全为素数，则为要求的解。
这里d,n是要寻找的，可以用穷尽法，d最大可以为31。
【题目13】
求具有下列两个性质的最小的自然数n。
（1）n的个位数是6
（2）若将n的个位数字移到其余各位数字之前，所得的新数是n的4倍。
【题目14】
有一个三位数，其尾数不大于2，将尾数移到首位后，新的三位数是原三位数的两倍多，试求这个三位数。
【题目15】
从键盘输入n个数值范围在1~99之间的数，分别统计出个位数为1，2，3，4，5的数各有多少个
第三章排序与查找
3．1排序
对由n个记录组成的表（或文件）（R1，R2，……Rn），依据记录中某个数据乡的数值重新进行排列的过程称为排序，该数据项称为排序码。
一般情况下，总是选择记录的关键码作为排序码。
如果待排序的表中有多个排序码值相等的记录，用某中方法排序后，这些记录的相对次序不变，则称这种排序方法是“稳定的”，否则是“不稳定的”。
排序算法比较多，排序一般分成两大类：
1．内排序：
待排序的记录比较少，真个排序过程都可以在内存进行。
2．外排序：
待排序的记录足够多，以至于一定要借助外存才能完成排序工作。
本章仅讨论几个内排序的方法。
3.1.1直接插入排序
对于排序数据（R1，R2，……Rn），若数据（R1，R2，……Ri-1）已经按照关键码有序，即对应的关键码有K1，K2，……Ki–1，将Ki与Ki–1，….，K1依次比较，一旦Ki大于或等于某个Kj（1≤j≤i–1）时，把Rj+1，Rj+2，……Ri–1后移一个位置，并将Ki插入第j+1个位置上。
【题目16】
请编写一个函数，实现应用直接插入排序的方法对任意N个数据进行排序。
并编写主函数实现对本函数的调用，并输出排序前后的结果。
3.1.2选择排序
选择排序是在待排序的n个记录中先选出关键码最大的记录，将它送到第n个位置上，然后再从其余n–1个记录中选出关键码最大的记录送到第n–1个位置上，……，直到选择了n–1个记录。
这种方法又称为直接选择排序。
【题目17】
请编写一个函数，实现应用选择排序的方法对任意N个数据进行排序。
3.1.3冒泡排序
这种排序方法从表的一端开始，依次比较相邻两个记录的关键码R[i]和R[i+1]，若R[i]>
R[i+1]，则交换R[i]和R[i+1]。
假设从表的左端开始，当i从0到n–2对表扫描一趟后，具有最大关键码的记录将被移到最右边的位置上。
重复以上操作对所有数据进行扫描，最后完成数据排序处理。
【题目18】
请编写一个函数，实现应用冒泡排序的方法对任意N个数据进行排序。
【题目19】
编写一个程序，输入3个学生的英语成绩和计算机成绩，并按总分从高到低排序。
要求设计一个学生类Student。
3．2查找
查找又称为检索，是计算机最重要的应用之一。
查找就是在某种数据结构中找出满足给定条件的结点。
查找的结果有两种可能：
在结构中找到满足条件的结点，查找成功；
找不到满足条件的结点，查找失败。
查找往往是程序中最耗费时间的操作，使用何种存储结构和查找算法对程序的性能有本质的差别，因此，在讨论各种查找算法时都应指明所用的存储结构。
查找一个结点所作的平均比较次数被称为平均查找长度，它是衡量一个查找算法的主要标准，是结点个数n的函数。
本节主要主要讨论几个简单的查找算法。
3.2.1顺序查找
顺序查找又称为线性查找，对给顶的关键码值K，从表的一端开始，依次检查表中每个记录的关键码值，直至找到所需要的记录或到达表的另一端。
【题目20】
请编写一个函数，实现应用顺序查找的方法对任意N个数据查找一个指定的数据X，如果查找成功则返回1，否则返回0。
并编写主函数实现对本函数的调用，在主函数中输出查找的具体结果。
3.2.2二分法查找
如果一个表的各个元素已经按照关键码值有序，对其中某个元素的查找，可以提高顺序查找的速度。
因为在扫描表的过程中，一旦遇到一个关键码值比K大的元素时便可以结束查找，而不必遍历整个表。
对有序表的查找，可以随机地取表中的一个元素Ri，比较K与Ri的关键码，若K小于Ri的关键码，则要查找的元素只可能在（R1，R2，……Ri-1）中；
否则，只可能在（Ri+1，Ri+2，……Rn）中。
如果取i=n/2，即用表的中间位置上的元素与K比较，若相等，则查找成功；
若不相等，根据比较的结果确定下一步是在（R1，R2，……Ri-1）还是在（Ri+1，Ri+2，……Rn）中继续查找，因此本方法也叫折半查找。
【题目21】
请编写一个函数，实现应用二分法查找的方法对任意N个数据查找一个指定的数据X，如果查找成功则返回1，否则返回0。
并编写主函数实现对本函数的调用，在主
升级会员 