计算机工程系《C++程序设计》学习辅导资料之二课程设计指导书

计算机工程系《C++程序设计》学习辅导资料之二

课程设计指导书

于永彦赵建洋

江苏淮阴工学院计算机工程系

二00六年二月二十八日

目录

一、课程设计的目的.................................................1

二、实验环境与教学要求.............................................1

三、实施原则、方案与步骤...........................................1

四、设计课题.......................................................2

（-）幻方.....................................................................2

1.奇数阶幻方的制作........................................................3

2.偶数阶幻方的制作.......................................................4

3.设计要求................................................................8

（二）矩阵操作.................................................................8

1.矩阵翻转................................................................8

2.矩阵卷动................................................................8

3.矩阵旋转................................................................9

4.设计要求...............................................................10

（三）汉诺塔..................................................................11

1.基本涵义...............................................................11

2.常规解法...............................................................11

3.设计要求...............................................................12

（四）八皇后..................................................................13

1.基本涵义...............................................................13

2.设计要求...............................................................13

（五）成绩管理................................................................14

1.设计要求...............................................................14

2.参考代码...............................................................15

（六）H编码..................................................................28

1.二元H码...............................................................28

2.m元H码..............................................................30

（七）数据排序...............................................................32

1.基本概念...............................................................32

2.插入排序...............................................................32

3.交换排序...............................................................34

4.选择排序...............................................................36

5.归并排序...............................................................38

6.设计要求...............................................................39

（八）数据查找...............................................................39

1.基本概念...............................................................39

2.顺序查找...............................................................40

3.二分查找...............................................................41

4.索引查找...............................................................43

5.散列查找...............................................................47

(九)最短路径...............................................................57

1.图概念.................................................................57

2.图的表示方法...........................................................61

3.带权图的最短路径......................................................63

4.设计要求...............................................................66

(十)表达式求值.............................................................67

1.基本概念...............................................................67

2.栈的存储和运算.........................................................67

3.表达式求值.............................................................69

4.设计要求...............................................................73

5.参考代码...............................................................73

五、课程设计报告要求..............................................77

六、成绩评定......................................................78

附录A课程设计报告格式要求........................................79

附录BC/C++常用函数..............................................84

1.数学函数.................................................................84

2.字符串函数...............................................................85

(1)strcpy(chardestination[],constcharsource[]);...............................................................85

(2)stmcpy(chardestination[],constcharsource[],intnumchars);....................................86

(3)strcat(chartarget[],constcharsource[]);........................................................................86

(4)stmcat(chartarget[],constcharsource[],intnumchars);...............................................86

(5)intstrcmp(constcharfirststring[],constcharsecondstring);.........................................87

(6)strlen(constcharstring[]);..............................................................................................87

附录CCString基础.................................................88

1.主要函数的实现...........................................................88

2.常用函数.................................................................89

(1)Delete.................................................................................................................................89

(2)FindOneOf.........................................................................................................................89

(3)Find.....................................................................................................................................89

(4)GetAt..................................................................................................................................89

(5)Insert..................................................................................................................................89

(6)Left......................................................................................................................................89

(7)Right....................................................................................................................................89

(8)MakeLower,MakeUpper.............................................................................................90

(9)MakeReverse......................................................................................................................90

(10)+=.....................................................................................................................................90

(11)str[]...................................................................................................................................90

(12)TrimLeft,TrimRight........................................................................................................90

(13)Remove(TCHARch);...................................................................................................91

3.CString与char□的相互转换................................................91

4.将NULL字节放入CString中..............................................91

5.在非MFC程序中引用CString............................................................................................92

(1)在非dll或lib里使用CString类..........................................92

(2)在dll或lib里使用CString类............................................92

附录D文件操作....................................................94

1.标准流设备...............................................................94

2.文件流...................................................................95

3.使用I/O成员函数.........................................................96

(1)用getline。读取输入行.................................................96

(2)用get()读取一个字符...................................................97

(3)get()输入一系列字符..................................................98

(4)输出一个字符..........................................................99

4.文件操作.................................................................99

(1)文件输出..............................................................99

(2)文件输入..............................................................101

附录E随机函数...................................................103

一、课程设计的目的

《C++程序设计》是计算机科学与技术、通信工程等相关专业的最重要的一门专业基础

课，内容庞大，涉及面广，知识点多，教、学难度都非常大，往往费了大量时间而达不到预

期教学效果。俗语说：学习的最好方法是实践。本课程设计正是基于此，力求为学生提供・•

个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。通过实践，建立系

统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、

吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课

堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体

系。

本书独立于具体的C++语言教科书，重点放在C++语言的基本特征上，结合实际应用，

通过详细的实例，循序渐进地启发学生完成设计。书中给出的课题实例概念清楚，体系完整,

内容丰富，采用循序渐进的方式，提高学生实际动手能力，完成“知识+实践=技能”的整

个学习过程。

二、实验环境与教学要求

要求实验室配备微型电子计算机80台，配置为奔腾PII以上，安装Windows2000以上

操作系统，及VisualC++6.0以上版本的开发环境。

要求教师在正确理解课程教学大纲的基础上,结合课题体系的实际需求及学生的实践能

力、工作条件等外部因素，选择恰当的设计课题，既体现教学目的，乂能反映实际教学情况。

要求保证充足的实践课时，最好配备专职指导教师。

要求同学们：

1.要充分认识课程设计的重要性，认真做好各项准备工作；

2.既要虚心接受老师的指导，又要充分发挥主观能动性，要结合课题，独立思考，努

力钻研，勤于实践，勇于创新：

3.收集资料，自学相关知识，拓宽知识面，根据课题的基本要求，自行完成设计任务。

4.在教师指导下，学习并掌握面向对象的程序设计知识，学习VC++中MFC编程，最

好能应用MFC设计图形界面的成果。

5.要按时、独立完成规定的工作任务，不弄虚作假，不抄袭他人；

6.严格遵守学习和劳动纪律，不无故缺席，不迟到早退，不懈怠，不拖拉，要积极主

动；

7.严格要求自己，树立严肃、严密、严谨的科学态度，按时、按质、按量完成；

8.互帮互助，要树立团队协作精神。

三、实施原则、方案与步骤

制订课程设计实施计划时，要体现以下设计原则：

•以学生为主，要求独立完成设计任务，注重培养学生自学能力、实践能力、文档撰

写能力、主动探索精神。

•教师针对每位学生的知识基础、实践技能等提出具体要求，辅导要有侧重，要因材

施教。对基础差的要勤检查、多指导，对能力强的要适时提高要求，增加选做内容,

积极鼓励，充分发挥其潜力。

•要求学生从点滴开始，踏踏实实按规定去做，培养严谨的科学态度。教育学生遵守

纪律，团结协作，尊重他人。通过设计工作以提高业务能力，增强团队协作精神。

根据C++程序设计的课程特点，本课程设计采取集中与分散相结合的方式，安排在理论

教学完成后进行，具体方案如下：

1.教师下达课程设计任务书

任务书内容包括设计题目、主要技术指标、要求、给定条件及原始数据、所用仪器设备

和参考资料及文献等。教师可以视情况讲授必要的设计思路和设计方法。

2.学生完成预设计

本阶段学生应明确任务，查阅资料及文献，自学新知识、新技术，掌握设计的基本方法,

确定设计方案，进行设计分析，完成预设计。

3.实验阶段

经教师审查通过预设计方案后，即可进入实验室编程调试。实验由学生独立完成，教师

仅作定时指导。

4.设计总结阶段

本阶段学生要认真回顾，总结收获，发现不足，整理技术资料，撰写课程设计报告书，

写出心得体会和改进意见。

具体实施时，要根据具体情况，如课程大纲要求、实验环境、学生专业、层次及软件水

平等，具体安排设计步骤。一般的设计步骤如下：

1.选题与搜集资料：根据分组，选择课题，合理分工，进行需求分析与系统调查，搜

集相关资料，了解涉及的理论基础知识。

2.系统分析与预设计：根据课题要求及搜集的资料，进行系统功能划分，分析数据流

程，进行模块设计。

3.指导教师检查每位学生的预设计结果，确定是否可以进入下一步。

4.程序设计：预设计通过的学生进入实验室，运用VC++6.0集成环境，编写程序，实

现所设计的模块功能。

5.调试与测试：自主调试程序，或同课题、同组成员交叉测试，并记录测试情况。

6.成果验收：指导教师对每位同学设计的成果进行验收，打成果成果成绩。

7.布置设计成果通过验收的同学撰写课程设计报告。

8.课程设计答辩。

9.结合每位学生的软件成果、工作态度、设计报告等，评定综合成绩。

四、设计课题

下面提供十个设计课题，涉及面有大有小，难度有深有浅，考察的知识点、体现的设计

目的也有所不同。指导教师可根据大纲要求，同学们的学习兴趣、水平高低，指导学生选择

适当的课题。同学们也可自拟设计课题，但必须征得指导老师同意。

(―)幻方

所谓幻方，就是一个n行n列的正方形，共有产个格子，将1、2、3.............「这些数

字放到这些格子里，使其每行的和、每列的利及两条对角线的和都是一个相同的数S,S称

为幻和。当n为奇数时，称为奇数阶幻方，当n为偶数时，称为偶阶幻方。当n可被4整除

时，称方为双偶幻方。当n不可被4整除时，称为单偶幻方。

多少年来，许多数学家都在研究这个古老而有趣的问题，试图找出般的解法，但-•般

都是针对当n是奇数和n是4的倍数的情况。

当n是奇数时的算法：

首先，将1放在第一行中间一个格子里。

其次，依次将后一个数放到前一个数的右上格，如：将2放到1的右上格。将3放到2

的右上格等等。可能出现下面的情况。

①若右上格从上面超出，则将后一数放到与右上格同列的最后•行。

②若右上格从右面超出，则将后一数放到与右上格同行的最后一列。

③若右上格既从右面超出又从上面超出，则将后一数放到前一数的下面。

④若右上格已被数字填充，则将后一数放到前一数的下面

依以上法则，你可以很快的写出奇数阶幻方！当然，这中写法只是其中•个答案，而不

是唯一答案。

1.奇数阶幻方的制作

(1)连续摆数法

例：一个5/5格子，由最上面一行中间一格开始，依次填1,2,3等等。下一个格子填在

左上位置。但是要注意两点：

>出了幻方的范围，右边接到左边，下边接到上边。

>某一格右上已经有了数字，改填在这个格子的下面一格，然后延续前面的方法。

17241815

23571416

46132022

101219213

11182529

也不一定按照斜上方写字，可以走马步，或其他方法。下面用的是马步，得到的是泛对

角幻方。

81711524

11259182

193122110

22620413

51423716

哪些“步子”是可行的，是需要注意的一个问题。

(2)阶梯法

例：以5阶为例。

第一步：画一个9x9的方格。如下斜着填数字。注意中间的5x5格子才是要作的幻方

的位置，已经涂成了黄色。

第二步：黄色范围以外的数字，平移到黄色格子中没有数字的位置。

去掉外围的格子，就得到所要作的幻方。

31692215

20821142

72513119

24125186

114171023

2.偶数阶幻方的制作

偶数阶幻方的制作比较复杂，下面介绍几个方法。

(1)对称法，适用于双偶数阶幻方

例：以8阶幻方为例。

第一步：在左上4x4格子中，取一半的格子，要求每行每列都取到2个。如下图黄色

格子所示。

第二步：按照左右对称、上下对称、中心对称的方法把这8个格子扩充为32个格子。

第三步：从左上角开始，从左到右从上到下，从1开始填数。不过只填没有选中的格子

(即没有涂黄色的格子)

2-157

9111416

17192224

26282931

34363739

41434648

49515456

58606163

第四步：从右下角开始从右到左从下到上在选中的格子里填进刚才没有填的数字。

642624559757

955115352145016

1747194544224224

4026382829353133

3234303637273925

4123432120461848

4915511312541056

858660613631

制作成功。

这个方法可以产生不同的双偶数阶幻方。

思考：能否算出这个方法可以产生多少个8阶幻方？

(2)斯特雷奇法，适用于单偶数幻方

例：设阶数n=2(2m+1)=6,m=1。

第一步：把方阵分为4个小方阵，位置依次为A左上，B右下，C右上，D左下。

用连续摆数法，把l-aA2放在A中成第一个幻方；把92+1〜2az'2放在B中成第二

个幻方。把2aA2+1〜3a人2放在C中成第三个幻方。把3aA2+1〜4aA2放在D中成第四个幻

方。

816261924

357212325

492222720

352833171015

303234121416

313629131822

换。

3516261924

3327212325

3192222720

82833171015

30534121416

43629131822

（3）LUX方法这是剑桥大学康韦教授发明的方法

例：设阶数n=2（2m+l尸10,m=2。

第一步：任取一个2m+l阶幻方，例如5阶幻方。如下。

12316421

151471811

24171392

20819126

53102225

第二步：在上面的m+1行（此处为3行）的每个格子里填入一个字母L；接下去一行填

字母U,余下m-l行填字母X。最后把中间的一个L与它下面的一个U交换一下。

1L23L16L4L21L

15L14L7L18L11L

24L17L13U9L2L

20U8U19L12U6U

5X3X10X22X25X

第三步：作一个10x1。方格，设想为每2x2为一个单位，每个单位相应于上面一个格子。

对应于5阶幻方中数字1的单位填1,2,3,4o对应于5阶幻方中数字2的填5,6,7,8。

等等。但是标有字母L的按照“右上一左下一右下一左上“次序；标有字母U的按照“左上

一左下一右下一右上“次序；标有字母X的按照“左上一右下一左下一右上“次序。

419289646116138481

239091626314158283

60575653282572694441

58595455262770714243

969368654952363385

949566675051343567

77802932767345482124

78793031747546472223

17209123740858897100

19181110393887869998

当然，这个方法也产生很多幻方，并不唯一。

3.设计要求

编写代码，实现奇、偶数幻方的制作。运行程序后，出现下面的参考界面:

幻方制作

1.奇数阶幻方

2.偶数阶幻方

请选择（1或2,0：退出）:

选择一个菜单后，要求输入幻方的阶数n。n的取值范围为3〜10。输入n后，首先判断

是否存在对应阶的幻方，如果存在，则显示幻方制作效果。

（-）矩阵操作

1.矩阵翻转

沿某中心轴翻转，或垂直，或水平翻转。翻转的实质是，矩阵的每行（或每列）元素进

行倒序排放。

01230123

12；4121241,21

65：923239;56

38:734341；83

4556：67787867!5645

2.矩阵卷动

可以左右、上下卷动。如下图:

01230123

1241224121

6592359236

3873487343

4556677856677845

——A-----------/

矩阵卷动涉及二个问题：

(1)卷动方向，或左右卷动，或上下卷动。

(2)卷动幅度T,如上下卷动行数，左右卷动列数。

卷动的实质是将某行或某列元素循环移位。上卜一卷动时，是将每列元素循环移位，左右

卷动时是将每行元素循环移位，卷动方向决定是左移还是右移。

一维数组的循环移位问题：

如，已知inttemp[10],将其循环右移一位。

显然，移位后，

temp[8]~temp[O]

依次存入

temp[9]~temp[l]

而原来的temp[9]则返回数组起始部位，存入temp[O]«

那么，循环右移W位呢？循环左移W位呢？

了解了一维数组循环移位问题后，显然，矩阵卷动无非是多个一维数组循环移位，只要

在外层加个大循环就解决了。

3.矩阵旋转

矩阵旋转(绕中心点)涉及二个方面：

(1)旋转方向，顺时针还是逆时针。

(2)旋转角度,如90°、180°、270°,360°等。

分析：

(1)考虑旋转方向、角度

(2)此处仅考虑方阵情况，即矩阵行、列数相同。

(3)考虑是奇次方阵还是偶次方阵。

(4)旋转时，实质是数组元素的重新组合，对应交换元素值。

(5)设方阵有K圈，每圈操作过程相似。

因此，问题的关键是某圈元素的旋转、交换。

如下图。

考虑几种特殊情况，如90°,180°,270°,360°等。

（1）其它角度都是90°的整数倍.因此，设计时仅需要考虑90°情况，其它情况只需

重复操作若干次即可。以顺时针旋转为例，如需旋转180°,只需将旋转90°操作连续

执行两次即能实现。

（2）逆时针旋转可以看作为“过度”旋转，如逆时针旋转90°,可认为是顺时针旋转270

当然，也可设计新的交换规则。

4.设计要求

编写代码，实现矩阵的翻转、卷动和旋转。运行程序后，随机生成一个元素为三位正整

数的5X5矩阵，并显现下面的参考界面：

矩阵操作

1.矩阵翻转

2.矩阵卷动

3.矩阵旋转

请选择（1、2或3,0：退出）:

选择•个菜单后，要求输入操作的方向、行数或列数或角度，输入后，显示操作结果。

（三）汉诺塔

1.基本涵义

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块

黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上

地穿好了由大到小的64片金片，这就是所谓的汉诺塔（如下图）。不论白天黑夜，总有一

个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必在大片

匕面。当所有的金片都从梵天穿好的那根针上移到另外•概针上时，世界就将在一声霹雳中

消灭，梵塔、庙宇和众生都将同归于尽。故汉诺塔问题又被称为“世界末日问题。”

漫舟塔周篇的初始模型

611II__________

ABC

这是一个典型问题。由于问题中给出的圆盘移动条件是：一次仅能移动一个盘，且不允

许大盘放在小盘的上面，这样64个盘子的移动次数为：

18,446,744,073,709,511,615（次）

这是个天文数字，若每一微秒可以计算（并不输出）•次移动，那麽也需要几乎一百万

年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但目前计算机的速度还不能

解决64曾的汉诺塔。

2.常规解法

按照上面的方法分析问题，找到移动圆盘的的递归算法：

设要解决的的汉诺塔共有N个圆盘，对A杆上的全部N个圆盘从小到大顺序编号，最小

的圆盘为1号，次之为2号，依次类推，则最下面的圆盘的编号为N。

第一步：先将问题简化。假设A杆上只有一个圆盘，即汉诺塔只有一层N1,则只要

将1号盘从A杆上移到B杆上即可。

第二步：对於一个有N（N>1）个圆盘的汉诺塔，将N个圆盘分成两部分：上面的N

-1个圆盘和最下面的N号圆盘。

第三步：将“上面的N—1个圆盘”看成一个整体，为了解决N个圆盘的汉诺塔，可以

按下面图示的方式迳行操作：

（1）将A杆上面的N—1个盘子，借助B杆，移到C杆上；

（2）将A杆上剩余的N号盘子移到B杆上;

1

2

L…

\N-1

BC

（3）将C杆上的N―1个盘子，借助A杆，移到B杆上。

I2

II…

,r--------h,N-I

_________NII___________

ABC

整理上述结果，把第一步中化简问题的条件作为递归结束条件，将第三步分析得到的算

法作为递归算法，可以写出如下完整得递归算法描述。

3.设计要求

编写代码，用两种方法解决盘子的移动。运行程序后，显现下面的参考界面:

汉诺塔

1.递归解法

2.非递归解法

请选择（1或2,0：退出）:

选择•个菜单后，要求输入盘片数目，输入后，显示移动过程及结果。

(四)八皇后

1.基本涵义

八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提

出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处

于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,

后来有人用图论的方法解出92种结果。

显然问题的键在于如何判定某个皇后所在的行、歹U、斜线上是否有别的皇后；可以从矩

阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同

在“/”斜线上的行列值之和相同；如果同在“\”斜线上的行列值之差相同；如果斜线不

分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。从下图可以验

证上面的说法：

对于一组布局我们可以用•个一维数组来表示：X:ARRAY[1..8]OFINTEGER;X[I]的下

标I表示第I个皇后在棋盘的第I行，X[I]的内容表示在第I行的第X[I]列，例如：X[3]=5

就表示第3个皇后在第3行的第5歹h在这种方式下，要表示两个皇后A和B不在同一列

或斜线上的条件可以描述为：

X[A]oX[B]ANDABS(A-B)oABS(X[A]-X[B]){A和B分别表示两个皇后的行号}。

2.设计要求

编写代码，用至少三种方法解决八皇后问题。运行程序后，显现下面的参考界面：

八皇后问题I

1.方法一

2.方法二

3.方法三

请选择（1、2或3,0：退出）:

选择一个菜单后，要求输入棋盘的阶层，即N。输入后，显示共有多少种布局方案，并

显示每一种方案的具体情况，如下图：

77:(0,2)(1,0)(2,6)(3,4)(4,7)(5,1)(6,3)(7,5)

78:(0,7)(1,1)(2,4)(3,2)(4,0)(5,6)(6,3)(7,5)

第77种状态为:第78种状态为:

******@*****@***

Q********@******

（五）成绩管理

1.设计要求

由于同学们已经学习了指针、链表、文件读写等基本知识，为了与后续课程，如数据结

构、数据库系统等有一个知识体系上的衔接，特设置一个信息管理类的课题《成绩管理系统》,

其它诸如人事管理、学籍管理、图书管理、通讯录管理等，结构类似，仅管理对象有所不同。

管理内容包括：

学号、姓名、班级、五门课成绩。

主要功能有：

添加、修改、删除、读出、写入、查找、排序、计算总分、平均分、分类汇总等。

编写代码，运行程序后，显现下面的参考界面：

成绩管理

输入学生成绩

修改学生成绩

删除学生成绩

计算每位学生的总分

计算每位学生的平均分

按学号或姓名查询学生成绩

按班级查询学生成绩

8.成绩排序

9.按班级统计学科总分、平均分等

请选择（1~9,0：退出）：

选择一个菜单后，显示结果。

2.参考代码

#include"stdio.h”/*1/0函数*/

#include“stdlib.h”/*其它说明*/

//includenstring.h"/*字符串函数*/

#include"conio.h"/*屏幕操作函数*/

#include"mem.hH/*内存操作函数*/

#include"ctype.h"/*字符操作函数*/

#include"alloc.h"/*动态地址分配函数*/

#defineN3/*定义常数*/

typedefstructzl/*定义数据结构*/

charno[l1];

charname[15];

intscore[N];

floatsum;

floataverage;

intorder;

structzl*next;

}STUDENT;

/*以下是函数原型*/

STUDENT*init();/*初始化函数*/

STUDENT*create();/*创建链表*/

STUDENT*delete(STUDENT*h);/*删除记录*/

voidprint(STUDENT*h);/*显示所有记录*/

voidsearch(STUDENT*h);/*查找*/

voidsave(STUDENT*h);/*保存*/

STUDENT*load();/*读入记录*/

voidcomputer(STUDENT*h);/*计算总分和均分*/

STUDENT*insert(STUDENT*h);/*插入记录*/

voidappend();/*追加记录*/

voidcopy();/*复制文件*/

STUDENT*sort(STUDENT*h);/*排序*/

STUDENT*index(STUDENT*h);/*索弓I*/

voidtotal(STUDENT*h);/*分类合计*/

intmenu_select();/*菜单函数*/

/******主函数开始*******/

main()

inti;

STUDENT*head;/*链表定义头指针*/

head=init();/*初始化链表*/

clrscr();/*清屏*/

for(;;)/*无限循环*/

(

switch(menu_select())/*调用主菜单函数，返回值整数作开关语句的条件*/

{/*值不同，执行的函数不同，b