C++程序设计指导书.doc

淮阴工学院
C++程序设计指导书
张亚红于长辉殷路于永涛许超俊
淮阴工学院·计算机与软件工程学院
二O一六年五月
前言
“C++程序设计”是计算机类专业的一门专业核心基础课程,涉及知识点多,教、学难度非常大,往往费了大量时间而达不到预期效果。俗语说:学习的最好方法是实践。
本课程设计正是基于此目的,力求为学生提供一个理论联系实际的机会,通过布置一定难度的课题,要求学生独立完成。通过实践,建立课程设计的整体思想,锻炼编写程序、调试程序的能力,学习文档编写规范,培养独立学习、吸取他人经验、探索前沿知识的习惯,树立团队协作精神。
指导书中的综合选题可以分成几个小项目供学生分工合作,其中给出的代码已经有意识地予以变化或删减,在一些关键之处有意设置了一点错误,直接复制一般难以调试通过,或难以达到预期的目的。同学们应该加以分析,补充完整,并尽可能地增加功能。同学们应注意小组成员之间共同研究技术难题,培养团队协作精神。
书中给出的实例概念清楚,体系完整,内容丰富,采用循序渐进的方式,提高学生实际动手能力,完成“知识+实践=技能”的整个学习过程。
在设计时,同学们可以采用结构化程序设计方法、面向对象程序设计方法同时使用。
目 录
前言 I
选题1 Huffman编码 1
一、二元Huffman码 1
二、m元Huffman码 2
选题2 幻方 5
一、奇数阶幻方的制作 5
二、偶数阶幻方的制作 7
三、设计要求 10
选题3 矩阵操作(动态数组) 11
一、矩阵翻转 11
二、矩阵卷动 11
三、矩阵旋转 12
四、设计要求 13
选题4 汉诺塔问题 14
一、基本涵义 14
二、常规解法 14
三、设计要求 15
选题5 八皇后问题 16
一、基本涵义 16
二、设计要求 16
选题6 学生成绩管理 18
一、设计要求 18
选题7 数据排序 19
一、基本概念 19
二、插入排序 19
三、交换排序 21
四、选择排序 23
五、归并排序 25
六、设计要求 26
选题8 数据查找 28
一、基本概念 28
二、顺序查找 28
三、二分查找 30
四、索引查找 32
五、散列查找 35
选题9 学生运动会成绩管理 46
一、问题描述 46
二、设计要求 46
选题10 算术表达式求值 47
一、基本概念 47
二、栈的存储、运算及STL 47
三、表达式求值 50
四、设计要求 53
选题11 图书管理 54
一、设计要求 54
选题12 集合的运算 55
一、问题描述 55
二、设计要求 55
三、设计要点 55
选题13 单位人事档案管理 55
一、设计要求 55
附录A C++程序设计课程设计操作规程 57
一、课程设计的目的 57
二、实践环境与教学要求 57
三、实施原则、方案与步骤 57
四、课程设计报告要求 58
五、成绩评定规则 59
六、说明 59
Huffman编码
一、二元Huffman码
在通信领域,信息编码是一种最基本的理论基础与技术手段,可以针对文字、声音、图像、视频、模型等,分为信源编码、信道编码。编码的方法有很多。1952年,一位外国人提出了一种逐个符号的编码方法,姑且称为H编码方法。其基本思想如下:
设有n个信号u1,u2,…,un,其概率分布依次为p(u1),p(u2),…,p(un),称为信号值,且满足下式:
p(u1)+p(u2)+…+p(un)=1
简记为:
H码的编码步骤可以简述为:
首先将n个信号按值的大小排列。
将最小的两个信号合并成一个新的信号,新信号的值为该两信号值的和,从而将原n个信号缩减为n-1个信号。
把缩减后的信号仍按值递减排列,然后再将其中最小的两个信号合并成一个新信号,这样又缩减为n-2个信号。
依此类推,直至只剩下1个信号为止。
将每次合并的两个信号分别用“0”和“1”两个符号表示。
从最后一级开始,向前返回,就得出各信号所对应的符号序列,即为各信号对应的码字。
例如:已知
其对应的H码如图所示:
再如:对
有两种编码过程:
方法(a)的具体原则是,把合并后的信号总是放在其他相同值的信号之上(或之左),方法(b)则是把合并后的信号值放在其他相同值的信号之下(或之右)。通过分析,方法(a)优于方法(b),方法(a)的方差比方法(b)的方差要小许多。
二、m元Huffman码
上面讨论的编码方法可称为二元编码,其思想可推广到m元编码。不同的只是每次把值最小的m个信号合并成一个新的信号,并分别用0,1,…,m-1等m个符号来表示。
对于m元编码,信号个数n必须满足下式:
n=(m-1)Q+m
式