C++ 程序设计 笔记 * 潘建瑜 2019 年 6 月 9 日 * 本笔记仅供课堂教学使用

Transcription

1 C++ 程序设计 笔记 * 潘建瑜 2019 年 6 月 9 日 * 本笔记仅供课堂教学使用

2 ii 纸上得来终觉浅, 绝知此事要躬行 学而不思则罔, 思而不学则殆 知识, 只有当它靠积极的思考得来, 而不是凭记忆得来的时候, 才是真正的知识

3 目录 第一讲 计算机基础 信息的表示与存储 计算机的数字系统 常见的进制数及它们之间的转换 二进制数的编码表示 算法基本概念 什么是算法 算法的特征与评价 算法的描述方法与基本控制结构 课后阅读 课后练习 第二讲 C++ 编程基础 C++ 语言概述 C++ 源程序结构 C++ 源程序书写规范 书写漂亮的程序 编译器 C++ 基础知识 C++ 字符集, 标识符, 关键字 C++ 数据类型 变量与常量 运算与表达式 C++ 简单输入输出 程序示例 上机练习 第三讲 选择与循环 关系运算与逻辑运算 选择结构 iii

4 iv 目录 IF 语句 SWITCH 结构 循环结构 WHILE 循环 DO WHILE 循环 FOR 循环 循环的非正常终止 程序示例 上机练习 第四讲 函数 函数的声明 定义与调用 函数间的参数传递 函数嵌套与内联函数 数据的作用域 形参带缺省值的函数 函数重载 预编译处理与多文件结构 上机练习 第五讲 数组 一维数组 二维数组 数组作为函数参数 应用实例 : 矩阵乘积的快速算法 普通方法 Strassen 方法 应用实例 : 列主元 Gauss 消去法求解线性方程组 上机练习 第六讲 指针与字符串数组 指针的定义与运算 指针与一维数组 指针与二维数组 指针与引用 指针与函数 持久动态内存分配 字符串 ( 字符数组 ) 上机练习

5 目录 v 第七讲 简单输入输出 C++ 基本输入输出 (I/O) 流 C 语言格式化输出 C 语言文件读写 上机练习 第八讲 排序算法及其 C++ 实现 引言 选择排序 插入排序 希尔排序 冒泡排序 快速排序 上机练习 第九讲 类与对象 I: 面向对象基础 为什么面向对象 类和对象基本操作 构造函数 复制构造函数 匿名对象 类与对象举例 : 游泳池 析构函数 上机练习 第十讲 类与对象 II: 面向对象进阶 类的组合 结构体与联合体 类作用域 静态成员 友元关系 类的 UML 描述 上机练习

6 vi 目录 第十一讲 类与对象 III: 面向对象提高 常对象与常成员 对象数组与对象指针 动态对象 向量类 :vector 字符串类 :string 字符串匹配算法 上机练习 第十二讲 运算符重载与类型转换 为什么要重载运算符 怎么实现运算符重载 运算符重载 : 成员函数方式 运算符重载 : 非成员函数方式 成员函数 or 非成员函数? 运算符 [] 的重载 运算符重载注意事项 自动类型转换 上机练习 第十三讲 继承与派生 继承与派生 派生类的定义 构造函数 派生类成员的标识与访问 派生类的复制构造函数 派生类的析构函数 类型兼容规则 虚父类 上机练习 第十四讲 多态 什么是多态 虚函数 纯虚函数与抽象类 模板 模板函数 模板类 上机练习

7 目录 vii 第十五讲 文件流与输出输入重载 输入输出流 文件流类与文件流对象 文件的打开与关闭 文件读写 : 文本文件与二进制文件 移动或获取文件读写指针 重载 << 和 >> 上机练习 第十六讲 泛化程序设计 STL 标准模板库 容器 迭代 算法 附录 A 一些小知识 160 A.1 PI 的计算 A.2 自动数据类型 auto

8

9 程序示例列表 1.1 二进制转十进制 十进制整数转化为二进制整数 十进制纯小数转化为二进制纯小数 二进制转十六进制 类型转换例 类型转换例 自增自减运算 逗号运算 二进制位运算 sizeof 举例 数学函数举例 操纵符举例 银行贷款问题 显示系统当前的时间 time SWITCH 结构举例 WHILE 循环举例 打印正整数的所有因子 九九乘法表 最大公约数 判断素数 猜生日 计算两个整数的最大值 计算 x k 二进制数转十进制数 用 Taylor 展开计算 sin(x) 的值 回文数 随机数的生成 计时函数 clock 计时函数 time ix

10 x 程序示例列表 4.9 猜数游戏 引用传递 : 交换两个整数的值 递归调用 : 计算阶乘 汉诺塔问题 内联函数 名字空间 形参带缺省值举例 形参带缺省值举例 函数重载 Monte Carlo 方法计算定积分 一维数组举例 Hilbert 矩阵与向量的乘积 交换两个数组 计算矩阵各列的和 ( 函数形式 ) 指针与一维数组 指针与二维数组 函数指针 创建一维动态数组 动态数组 : 前 N 个素数 操纵符示例 : 域宽和填充 操纵符示例 : 小数输出形式和精度 C 语言文件读写 : 文本文件 C 语言文件读写 : 二进制文件 选择排序 插入排序的 MATLAB 实现 希尔排序的 MATLAB 实现 冒泡排序的 MATLAB 实现 快速排序的 MATLAB 实现 时钟的描述 类与对象 : 时钟类 类与对象 : 构造函数 类与对象 : 复制构造函数 类与对象 : 游泳池 类与对象 : 组合类的初始化

11 程序示例列表 xi 10.2 类作用域 : 类的数据成员与成员函数中的局部变量 静态数据成员举例 静态函数成员举例 常对象, 常成员函数, 常数据成员 常引用 向量类 : 创建向量 向量类 : 以其他类的对象为元素 向量类举例 : 找出给定区间内的所有素数 字符串类举例 : 二进制转化为十进制 运算符重载 : 有理数加法运算 运算符重载 : 前置和后置单目运算 运算符重载 : 有理数减法运算, 非成员函数方式 运算符重载 : 前置和后置单目运算, 非成员函数方式 运算符 [] 的重载 自动类型转换 : 基本数据类型 对象 自动类型转换 : 对象 基本数据类型 派生类构造函数举例 ( 一 ) 派生类构造函数举例 ( 二 ) 虚父类举例 多态 : 虚函数举例一 多态 : 虚函数举例二 多态 : 虚函数举例三 多态 : 纯虚函数举例 模板函数举例一 模板函数举例二 模板函数举例三 模板函数举例四 模板类举例一 模板类举例二 文件流 : 文本文件的读写 文件流 : 二进制文件的读写 文件流 : 重载 << 和 >>

12

13 第一讲计算机基础 1.1 信息的表示与存储 计算机的数字系统 计算机内部的信息的分类 : (1) 控制信息 : 包括指令和控制字 ; (2) 数据信息 : 包括数值信息和非数值信息 ; 其中数值信息包括整数 浮点数等 ; 非数值信息包括字符 ( 字符串 ) 和逻辑数据等 信息的存储单位 : (1) 信息存储的基本单位有 : 二进制位 (bit) 和字节 (Byte); (2) 计算机的最小存储单元是字节, 一个字节由 8 个二进制位组成, 即 1B=8b; (3) 其它存储单位有 :KB, MB, GB, TB, PB, EB 等等 ; (4) 一个英文字符占一个字节, 而一个汉字占两个字节. 计算机数字系统 : (1) 计算采用的是二进制数字系统, 基本符号是 0 和 1; (2) 优点 : 易于物理实现 运算简单 可靠性高 通用性强 ; (3) 缺点 : 可读性差 常见的进制数及它们之间的转换 常见进制数 : 二进制, 八进制, 十进制, 十六进制. 二进制转十进制 : 各位数字与它的权相乘, 然后相加. 例 1.1 ( 二进制转十进制 ) (101.11) 2 = = (5.75) 10 八进制和十六进制的整数转化为十进制整数的方法类似. 十进制转二进制 例 1.2 ( 十进制整数转化为二进制整数 ) 除 2 取余, 逆序排列, 即辗转相除法. 1

14 2 第一讲计算机基础 十进制整数转化为八进制或十六进制整数的方法类似. 例 1.3 ( 十进制纯小数转化为二进制纯小数 ) 乘 2 取整, 顺序排列, 与 2 相乘后取整数部分, 即 每次乘以 2 后去掉整数部分, 不断乘下去, 直到小数部分为 0 或达到指定的精度为止, 然后取每 次相乘后的整数部分即可. 绝大部分浮点数是无法用二进制精确表示的, 如 0.1, 0.2, 0.3, 0.4, 0.6, 0.7, 0.8, 0.9. 二进制与八进制, 二进制与十六进制 (1) 每位八进制数对应于一个三位二进制数 ; (2) 每位十六进制数对应于一个四位二进制数 例 1.4 ( 二进制转十六进制 ) = = 1A 二进制数的编码表示 数在计算机内部的存储方式 : 原码 反码 补码. (1) 数的表示 : 符号 + 大小 (2) 符号 : 用 0 表示正, 用 1 表示负, 放在最高位 (3) 大小 : 二进制

15 1.1 信息的表示与存储 3 (4) 优点 : 直观 (5) 缺点 : 零的表示不唯一 ; 四则运算要考虑符号位, 规则复杂 反码 (1) 正数的反码 : 与原码相同 ; (2) 负数的反码 : 符号位不变, 其它位取反 (0 变 1,1 变 0) 反码一般不直接使用, 通常是作为求补码的中间码. 补码 (1) 正数的补码 : 与原码相同 ; (2) 负数的补码 : 反码的最末位加 1 (3) 0 的补码表示唯一, 且可以多表示一个数 ; (4) 对补码再求补即得到原码. 数据在计算机中是以补码的方式存放的. 补码运算规则 (1) 符号位作为数值直接参加运算 ; (2) 减法转化为加法进行运算 ; (3) 运算结果仍为补码. 非数值信息 如果用 8 位字长计算 , 则结果会是什么?

16 4 第一讲计算机基础 (1) 西文字符 : 每个西文字符与其 ASCII 码一一对应 ( 完整的 ASCII 码表见课程主页或教材 ) (2) 中文汉字 : 一个汉字占两个字节, 常见编码有 GB2312, GBK, GB18030, UTF-8 等. 1.2 算法基本概念 什么是算法 一个程序应该包括 : (1) 对数据组织的描述 : 数据的类型和组织形式, 即数据结构 ; (2) 对操作流程的描述 : 即操作步骤, 也就是算法. 算法 : 通俗地说, 算法就是为解决一个问题而采取的方法和具体步骤. (1) 学习程序设计的目的不仅仅是学习一种特定的语言, 而是学习程序设计的一般方法 ; (2) 掌握了算法就是掌握了程序设计的灵魂, 再配合有关的计算机语言, 就能顺利编写出程序, 解决问题 ; (3) 脱离了具体的语言去学习程序设计是困难的 算法的特征与评价 算法的特征 (1) 输入 : 有零个或多个输入量 ; (2) 输出 : 通常有一个或以上输出量 ( 计算结果 ); (3) 明确性 : 算法的描述必须无歧义, 保证算法的正确执行 ; (4) 有限性 : 有限个输入 有限个指令 有限个步骤 有限时间 ; (5) 有效性 : 又称可行性, 能够通过有限次基本运算来实现. 算法性能的评测 (1) 空间复杂度 : 运算量 (2) 时间复杂度 : 存储量 (3) 实现复杂度 : 编程实现与维护 算法的描述方法与基本控制结构 算法的描述方法 : 自然语言, 流程图, 伪代码等. 流程图 : 简洁 直观 准确. 算法的三种基本控制结构 : 顺序结构, 选择结构, 循环结构. (1) 顺序结构是最基本 也是最常用的程序设计结构, 它按照程序语句行的自然顺序, 一条一条地执行程序 ; (2) 选择结构, 又称分支结构或条件结构, 包括简单选择和多分支选择结构, 可根据条件, 判断应该选择哪一条分支来执行 ;

17 1.3 课后阅读 5 (3) 循环结构, 可根据给定的条件, 判断是否需要重复执行某一相同的程序段. 顺序结构选择结构循环结构 三种结构的共同点 :(1) 只有一个入口 ; (2) 只有一个出口 ; (3) 结构内每一部分都有机会被执 行 ; (4) 结构内不存在 死循环. 1.3 课后阅读 IEEE 浮点运算标准, 了解计算机中浮点数是怎样存储和运算的. 1.4 课后练习 练习 1.1 将下列二进制数转化为十进制数 : 101, , 练习 1.2 将下列十进制数转化为二进制数 : 101, , 练习 1.3 ( 思考 ) 如何计算小数的补码.

18 第二讲 C++ 编程基础 C++ 是一门面向对象的编程语言, 现已广泛使用 C++ 语法丰富, 灵活高效, 同时也意味着比较复杂, 不易掌握, 尤其是使用高级特性时, 需要深入了解它的底层 学习编程是一个循序渐进的过程 学习 C++ 语言, 主要是为了掌握 C++ 的基本语法规则, 能够熟练阅读和分析 C++ 程序源代码, 并掌握类与对象的相关知识 同时, 掌握算法设计的基本概念 方法与技巧, 培养面向对象的程序设计能力, 掌握基本的编程和调试技术 另外, 培养编程兴趣, 了解内存 编译和链接相关知识, 弄清编程语言的内在机理 每个初学者都经历过这样的窘境 : 已经学习了语法, 明白了编程语言都有什么, 也按照教程写了不少代码, 但是遇到实际问题就懵了, 没有思路, 不知道从何下手, 也就是只会学不会用 究其原因, 就是实践少, 没有培养起编程思维! 学习知识容易, 运用知识难! 学习 C++, 不仅要理解 C++ 编程的基本概念, 掌握语言的技术细节, 更重要的是培养编程思维! 2.1 C++ 语言概述 C++ 是从 C 语言发展演变而来, 可以看成是 C 的超集 ; 1979/1980 年由 Bjarne Stroustrup 开发创建 ; 1983 年正式取名为 C++,1989 年开始 C++ 的标准化工作 ; 1994 年制定了 ANSI C++ 标准草案 ; 年由 ISO 批准为国际标准, 通称 C++98; 年 8 月发布 C 年 8 月发布 C 年 3 月发布 C ANSI American National Standards Institute 美国国家标准协会 2 ISO International Organization for Standardization 国际标准化组织 6

19 2.1 C++ 语言概述 7 图 2.1. C++ 发展历史与规划, 最新进展见 C++ 源程序结构

20 8 第二讲 C++ 编程基础 C++ 源程序由一个或多个源文件组成 ; 每个源文件可由一个或多个函数组成 ; 一个源程序有且只能有一个 main 函数, 即主函数 ; 程序执行从 main 开始, 在 main 中结束 ; 源程序中可以有预处理命令, 通常应放在源文件或源程序的最前面 ; 一行可以写多个语句, 一个语句也可以分几行书写 C++ 源程序书写规范 每条语句须以分号 ; 结尾, 但预处理命令, 函数头和花括号 } 之后不能加分号 ; 标识符, 关键字之间至少加一个空格表示间隔, 若已有明显的间隔符, 也可不加 ; 区分大小写, 习惯用小写字母 ; 常用锯齿形书写格式 所有标点符号必须在英文状态下输入! 书写漂亮的程序 花括号 { } 要对齐 ; 一行写一个语句, 一个语句写一行 ; 使用 TAB 缩进 ; 有合适的空行 ; 有足够的注释 编译器 编译器就是将 高级语言 翻译为 机器语言 的工具 ; 一个现代编译器的主要工作流程 : 源代码 编译 目标代码 链接 可执行程序 常见的 C++ 编译器 :Visual C++,GNU C++,Intel C++ 等等 常用的 IDE (Integrated Development Environment 集成开发环境 ): (1) Visual Studio :Windows 平台上最流行的商业 C++ 集成开发环境. (2) Dev C++ : 小巧, 免费,Windows 平台上的 gcc, 非常适合学习 C++. (3) Code::Blocks : 开放源码的全功能跨平台集成开发环境, 免费. 2.2 C++ 基础知识 C++ 字符集, 标识符, 关键字 合法的字符集.

21 2.2 C++ 基础知识 9 (1) 字母 : 包括大写和小写, 共 52 个 ; (2) 数字 :0 到 9 共 10 个 ; (3) 空白符 : 空格符 制表符 换行符 ; (4) 标点符号和特殊字符 : + - * / =! # % ^ & ( ) [ ] { } _ ~ < > \ ' " : ;.,? C++ 标识符 : 用来标识变量名 函数名 对象名等的字符序列. (1) 由字母 数字 下划线组成, 第一个字符必须是字母或下划线 ; (2) 区分大小写, 不能用关键字 ; (3) C++ 不限制标识符长度, 实际长度与编译器有关, 一般不要超过 32 个字符 ; (4) 命名原则 : 见名知意, 不宜混淆 C++ 关键字 : 具有特定意义的字符串, 也称为保留字, 包括 : (1) 类型标识符 语句定义符 ( 控制命令 ) 预处理命令等; (2) 全部关键字参见 C++ 分隔符 : 逗号 冒号 分号 空格 ( ) { } C++ 注释 : 有两种注释方式, 分别是 (1) 单行注释 :// (2) 块 ( 多行 ) 注释 :/* */ C++ 数据类型 C++ 的数据类型可分为基本数据类型和派生 ( 扩展 ) 数据类型 基本数据类型 : 整型, 实型, 字符型 (char) 和布尔型 (bool) (1) 整型 :int, short, long, long long, unsigned int, unsigned short, unsigned long, unsigned long long (2) 实型 :float, double, long double

22 10 第二讲 C++ 编程基础 表 2.1. C++ 基本数据类型 数据类型 关键字 所占字节 表示范围 short int 2 / / 整型 long 4 / / unsigned short unsigned int 2 / / unsigned long 4 / / float 4 (6 位有效数字 ) 实型 double 8 (15 位有效数字 ) long double 16 (18 位有效数字 ) 布尔型 bool 1 true, false 字符型 char 1 事实上,C++ 标准没有规定每种数据类型的字节数和表示范围, 只规定大小顺序, 即长度满足下面的关系式 char <= short <= int <= long <= long long 具体长度由处理器和编译器决定 派生 ( 扩展 导出 自定义 ) 数据类型 : 数组, 指针, 枚举, 结构, 类, 等等 数据类型的转换

23 2.2 C++ 基础知识 11 (1) 自动转换 / 隐式转换 : - 相同类型的数据进行运算时, 其结果仍然是同一数据类型, 如 3/2 的结果是 1; - 不同类型的数据进行运算, 需先转换成同一类型 ; - 转换按数据长度增加的方向进行, 以保证精度不降低 ; - 所有的浮点运算都是以双精度进行的 ; - char 型和 short 型参与运算时, 必须先转换成 int 型 ; - 赋值号两边的数据类型不同时, 右边表达式值的类型将转换为左边的类型 ; - 字符变量直接参与算术运算时, 先转化位相应的 ASCII 码, 然后进行运算 char --> short --> int --> unsigned --> long --> unsigned long --> float --> double (2) 强制转换 / 显式转换 类型标识符 ( 表达式 ) // C++ 风格, 将表达式的值转化为指定的数据类型 ( 类型标识符 ) 表达式 // C 语言风格, 作用同上 例 2.1 ( 类型转换 ) 已知有下面的代码 1 int a=2, b=5; 2 double x, y, z; 3 4 x = b/a; // x = y = double(b)/a; // y = z = double(b/a); // z = 2.0 (1) 由于 a 和 b 都是整型, 因此表达式 b/a 的值也是整型, 即 b/a=2. 将其赋值给 double 型 变量 x, 因此 x=2.0. (2) 在计算 double(b)/a 时, 先将 b 的值转化为 double 型 ( 注意, 不是将 b 转化为 double 型, 变量 b 的类型是不会改变的!), 然后与 a 相除. 由于是一个 double 型的数据与一个 int 型的数据进行运算, 所以系统会自动将 int 型的数据转化为 double 型的数据, 然 后再做运算. 所以最后的结果是 2.5. (3) 在计算 double(b/a) 时, 是先计算 b/a, 然后将结果转化为 double 型, 所以最后的结 果是 z=double(2)=2.0 (4) 需要注意的是, 变量 a,b 的类型在整个计算过程中是始终不变的, 即一直是 int 型. 类型转换不会改变变量的数据类型! (5) 类型转换规则 : - 浮点型转整型 : 直接丢掉小数部分 ; - 字符型转整型 : 取字符的 ASCII 码 ; - 整型转字符型 :ASCII 码对应的字符.

24 12 第二讲 C++ 编程基础 例 2.2 已知有下面的代码 1 int i; 2 char a; 3 i=3.6; cout << "i=" << i << endl; 4 i=-3.6; cout << "i=" << i << endl; 5 i='m'; cout << "i=" << i << endl; 6 a=90; cout << "a=" << a << endl; 输出结果为 ( 字符 m 和 Z 的 ASCII 码分别是 109 和 90): 1 i=3 2 i=-3 3 i=109 4 a=z 变量与常量 变量 : 存储数据, 值可以改变 (1) 变量名 : 命名规则与标识符相同 (2) 变量必须先声明, 后使用 ; 先赋值, 后使用 (3) 变量声明 : 数据类型标识符变量名列表 ; - 可以同时声明多个变量, 用逗号隔开 - 变量声明时可以初始化 : 两种方式 ( 赋值运算符和小括号 ), 例如 1 int i, j, k=0; // 同时声明 3 个整型变量, 但只对变量 k 进行初始化 2 double x(3.1415); // 等价于 double x=3.1415; 3 char c; 常量 ( 常数 ): 在程序运行中值不能改变的量 (1) 整型常量 : 整数, 后面加 l 或 L 表示长整型, 后面加 u 或 U 表示无符号整型 ; (2) 实型常量 : 缺省为双精度实数, 后面加 f 或 F 表示单精度, 加 l 或 L 表示 long double (3) 字符型常量 : 用单引号括起来的单个字符和转义字符 ; (4) 字符串常量 : 用双引号括起来的字符序列 ; (5) 布尔常量 :true 和 false 例 : 下面都是常量 1 123, -456, 123L, 456U; 2 1.2, 1.2F, 1.2L, 1.2e8, 1.2e8F, 1.2e-8L 3 'M', 'A', 'T', 'H', '?', '$' 4 "MATH@ECNU" 符号常量 : 用标识符表示常量 (1) 声明方式 :

25 2.2 C++ 基础知识 13 const 数据类型标识符变量名 = 常量值 ; 例 : 声明符号常量 1 const float PI= ; (2) 符号常量在声明时必须初始化 ; (3) 符号常量的值在程序中不能被修改 ( 不能重新赋值 ) typedef: 为一个已有的数据类型另外命名 ( 取别名 ), 可以取一个别名, 也可以取多个别名 typedef 已有类型名新类型名表 ; - 可以同时为一个已有的数据类型取多个别名. 例 : 为一个已有的数据类型另外命名 1 typedef double area, volume; // 为 double 取两个别名 area 和 volume 2 typedef int natural; // 为 int 取别名 natural 3 natural i, j; // 等价于 int i, j; 4 area s; // 等价于 double s; 5 volume v; // 等价于 double v; 枚举 : 定义新的数据类型 enum 枚举类型名 { 变量可取值列表, 即枚举元素 }; (1) 对枚举元素按常量处理, 不能对它们赋值 (2) 枚举元素具有默认值, 依次为 :0, 1, 2,...; (3) 也可以在声明时指定枚举元素的值, 如 : 1 // 枚举类型 2 #include<iostream> 3 4 using namespace std; 源代码 2.1. 枚举示例 5 6 int main() 7 { 8 enum weekday {sun, mon, tue, wed, thu, fri, sat}; // 定义枚举数据类型 weekday 9 weekday today, tomorrow; today = wed; 12 cout << "today=" << today << endl; 13

26 14 第二讲 C++ 编程基础 14 tomorrow = weekday(4); 15 cout << "tomorrow=" << tomorrow << endl; return 0; 18 } (4) 枚举值可以进行关系运算 ; (5) 整数值不能直接赋给枚举变量, 需进行强制类型转换 运算与表达式 运算符 (1) 算术运算符 :+ - * / % ++ ( 自增 ) -- ( 自减 ) (2) 赋值运算符 := += - = *= /= %= &= = ^= >>= <<= (3) 逗号运算符 :, ( 把若干表达式组合成一个表达式 ) (4) 关系运算符 : 用于比较运算,> < == >= <=!= (5) 逻辑运算符 : 用于逻辑运算,&&! (6) 条件运算符 : 是一个三目运算符, 用于条件求值,? : (7) 求字节数运算符 :sizeof ( 计算数据类型所占的字节数 ) (8) 位操作运算符 : 按二进制位进行运算,& ~ ^ ( 异或 ) << ( 左移 ) >> ( 右移 ) (9) 指针运算符 :* ( 取内容 ) & ( 取地址 ) 运算符优先级 : 表 2.2. C++ 运算符优先级 优先级 运算符 描述 结合性 1 :: 作用域解析 从左到右 2 a++ a-- 后缀自增与自减 type() 类型转型 (C++ 风格 ) f() 函数调用 a[] 下标. -> 成员访问 3 ++a --a 前置自增与自减 从右到左 +a -a 一元加与减! ~ 逻辑非和逐位非 (type) 类型转型 (C 语言风格 ) *a 指针运算 &a 指针运算 : 取地址 sizeof 大小 ( 所占字节数 ) co_await await 表达式 (C++20) new new[] 动态内存分配

27 2.2 C++ 基础知识 15 delete delete[] 动态内存分配 4.* ->* 指向成员指针 从左到右 5 a*b a/b a%b 乘法 除法 取余数 6 a+b a-b 加法与减法 7 << >> 逐位左移与右移 8 <=> 三路比较运算符 (C++20) 9 < <= 分别为 < 与 的关系运算符 > >= 分别为 > 与 的关系运算符 10 ==!= 分别为 = 与 的关系运算符 11 a&b 逐位与 12 ^ 逐位异或 ( 排除或 ) 13 逐位或 ( 包含或 ) 14 && 逻辑与 15 逻辑或 16 a?b:c 三元条件运算 从右到左 throw throw 运算符 co_yield yield 表达式 (C++20) = 赋值 += -= 以和及差复合赋值 *= /= %= 以积 商及余数复合赋值 <<= >>= 以逐位左移及右移复合赋值 &= ^= = 以逐位与 异或及或复合赋值 17, 逗号运算 从左到右 C++ 语句 (1) 空语句 ( 只有分号 ) (2) 声明语句 ; (3) 表达式语句 ( 赋值表达式 ); (4) 复合语句 ( 将多个语句用 { } 括起来组成的一个语句 ); (5) 选择语句, 循环语句, 跳转语句 ; (6) 表达式与表达式语句 (1) 表达式 : 由运算符连接常量 变量 函数等所组成的式子 ; (2) 表达式语句 : 表达式后加分号 ; (3) 表达式中的运算符包含赋值运算符 ; 赋值表达式的值是赋值号左边变量的值 ;

28 16 第二讲 C++ 编程基础 (4) 表达式可以包含在其它表达式中, 但语句不行! 赋值语句 (1) 标准赋值语句 变量 = 表达式 ; 例 : 赋值运算 1 x=3; 2 x=y=3; // 等价于 y=3; x=y; 这种赋值方式不能用于初始化 (2) 自增自减 :++, -- - 前置 : 先自增或自减, 然后参与表达式运算 ; - 后置 : 先参与表达式运算, 然后自增或自减 ; - 不要在同一语句中包含一个变量的多个 ++ 或 --, 因为它们的解释在 C/C++ 标准中没有 规定, 完全取决于编译器的个人行为 例 2.3 自增自减运算 1 x++; // 等价于 x=x+1; 2 ++x; // 等价于 x=x+1; 3 y=x++*x; // 等价于 y=x*x; x=x+1; 4 y=++x*x; // 等价于 x=x+1; y=x*x; (3) 复合赋值运算符 :+= -= *= /= %= 例 : 复合赋值运算 1 int x 2 x+=3; // 等价于 x=x+3; 3 x/=3; // 等价于 x=x/3; 4 5 int a, b, c, d, e, f; 6 a = 5; 7 b = a + 3; // b=8 8 a = a + (c=6); // c=6; a=11; 9 d = e = f = a; // f=11, e=11, d=11 10 e *= d; // e= f /= c - 2; // f=? (1 or 2) 逗号运算符 : 表达式 1, 表达式 2 (1) 先计算表达式 1, 再计算表达式 2, 并将表达式 2 的值作为整个表达式的结果

29 2.2 C++ 基础知识 17 例 2.4 逗号运算 ( 注意运算的优先级!) 1 int a=2, b; 2 a = 3*5, a+10; // a=12 or 15? 3 b = (3*5, a+10); // b=? 为了避免由运算优先级所导致的低级错误, 建议多使用小括号 位运算符 : 按二进制位进行运算 & ^ ( 异或 ) ~ ( 取反 ) << ( 左移 ) >> ( 右移 ) 例 2.5 二进制位运算 1 short a=5; // a : short b=14; // b : short c1,c2,c3,c4,c5,c6; 5 c1 = a & b; // : c2 = a b; // : C3 = ~ a; // : C4 = a ^ b; // : C5 = a << 3; // : C6 = a >> 2; // : 求字节数运算符 : sizeof( 数据类型 ) // 返回指定数据类型所占的字节数 sizeof( 表达式 ) // 返回表达式结果所对应的数据类型所占的字节数 例 2.6 sizeof 举例 1 int a, b, c; 2 a = sizeof(int); 3 b = sizeof(3 + 5); 4 c = sizeof(3.0l + 5); 常用数学函数 ( 需加入 cmath 头文件 :#include <cmath> ) 绝对值平方根指数函数 x y 对数函数取整函数三角函数 abs(x) sqrt(x) exp(x) power(x,y) log(x), ln(x) ceil(x), floor(x), round(x), trunk(x) sin, cos, tan, asin, acos, atan

30 18 第二讲 C++ 编程基础 双曲三角函数 sinh, cosh, tanh, asinh, acosh, atanh 例 2.7 数学函数举例 1 #include <iostream> 2 #include <cmath> // 数学函数 3 using namespace std; 4 int main() 5 { 6 double x, y; 7 8 cout << "max(1.2,3.1)=" << max(1.2,3.1) << endl; 9 cout << "min(1.2,3.1)=" << min(1.2,3.1) << endl << endl; 10 cout << "ceil(3.5)=" << ceil(3.5) << endl; 11 cout << "floor(3.5)=" << floor(3.5) << endl; 12 cout << "round(3.5)=" << round(3.5) << endl; 13 cout << "trunc(3.5)=" << trunc(3.5) << endl; return 0; 16 } 2.3 C++ 简单输入输出 C++ 输入 / 输出 : cin >> 变量名或字符串 ;`cout << 变量名或字符串 ; 输入运算符与输出运算符 :>> << 字符串中可以包含转义字符, 常见的转义字符有 \a 响铃 \r 回车 \\ 反斜杠 \b 退后一格 \t 水平制表符 \' 单引号 \n 换行 \v 垂直制表符 \" 双引号 例 : cout 举例 1 x = ; 2 y = ; 3 cout << "x=" << x << "\t y=" << y << "\n"; 4 5 cout << "The double quotation mark is \" \n"; 例 : cin 举例 1 cout << "Please input x: "; // 输入语句前通常需要输出一些提示信息 2 cin >> x;

31 2.3 C++ 简单输入输出 19 操纵符 : 控制输出格式 常用的操纵符有 ( 需加入头文件 #include <iomanip>)

32 20 第二讲 C++ 编程基础 操作符 含义 endl 插入换行符, 并刷新流 ( 将缓冲区中的内容刷入输出设备 ) setw(n) 设置域宽 cout.width(n) fixed 使用定点方式输出 scientific 使用指数形式输出 setfill(c) 设置填充,c 可以是任意字符, 缺省为空格, cout.fill(c) 如 setfill('*'), setfill('0') setprecision(n) 设置输出的有效数字个数, 若在 fixed 或 scientific 后使用, 则设置小数位数 left 左对齐 right 右对齐 ( 缺省方式 ) showpoint 显示小数点和尾随零 ( 即使没有小数部分 ) 操纵符的作用范围 : - setw 仅对紧随其后的输出起作用 ; - 其它操纵符 : 至下一个同类型命令为止. 例 2.8 操纵符举例 1 double x= , y= ; 2 cout << setprecision(5); 3 cout << "x=" << x << endl; 4 cout << "y=" << y << endl; 5 6 cout << fixed; cout << setprecision(5); 7 cout << "x=" << x << endl; 8 cout << "y=" << y << endl; 9 10 cout <<left; 11 cout << "x=" << setw(20) << x << "MATH" <<endl; 12 cout << setw(20) << "x=" << x << "MATH" <<endl; 2.4 程序示例 例 2.9 ( 银行贷款问题 ) 已知贷款总额为 L 万元, 贷款年利率为 r, 贷款年限为 y 年, 计算每月需偿还的金额和偿还总额 假 设采用等额本息方式, 则每月的还款额为 ( 万元 ) Lr m (1 + r m ) 12y (1 + r m ) 12y 1, 其中 r m 表示月利率, 即 r m = r/12 ( 思考 : 每月还款额公式是怎么推导出来的?)

33 2.4 程序示例 21 1 // 等额本息 2 3 #include <iostream> 4 #include <cmath> // 数学函数 5 6 using namespace std; 7 8 int main() 9 { 10 double Loan, rate_year, rate_month, year; 11 double payment_month, payment_total; cout << "input loan amount: "; 14 cin >> Loan; 15 cout << "input yearly interest rate: "; 16 cin >> rate_year; 17 rate_month = rate_year/1200; 18 cout << "input number of years: "; 19 cin >> year; // 计算每月需还款金额 22 double vtmp = pow(1+rate_month,12*year); 23 payment_month=loan*rate_month*vtmp/(vtmp-1); 24 payment_total=payment_month*year*12; cout << "Monthly payment: " << payment_month << ", "; 27 cout << "Total payment: " << payment_total; return 0; 30 } 例 2.10 ( 显示系统当前的时间 ) 头文件 ctime 中函数 time(0) 或 time(null) 返回当前时间与 1970 年 1 月 1 日零时的时间差 ( 格 林威治时间, 以秒为单位 ), 北京时间 : 格林威治时间 + 8 小时 1 // 显示当前时间 ( 时 : 分 : 秒 ) 2 #include <iostream> 3 #include <ctime> 4 5 using namespace std; 6 7 int main() 8 { 9 long Second, Minute, Hour; Second = time(null); 12 Minute = Second / 60; 13 Hour = Minute / 60; 14 cout << " 当前北京时间是 "; 15 cout << (Hour+8) % 24 << ":" << Minute % << ":" << Second % 60 << endl ; return 0; 19 }

34 22 第二讲 C++ 编程基础 2.5 上机练习练习 2.1 编写程序, 从键盘读入圆柱体的半径和高度, 计算其表面积和体积, 并将结果在屏幕上输出, π 取值 练习 2.2 银行提供两种 5 年定期存款方式 :(1) 一年期方式 : 年利率 10%, 每年到期后, 自动将本年度的利息加入本金中 ; (2) 五年期方式 : 年利率 11%, 五年后本金和利息一起归还储户 编写程序, 分别以两种方式存入 100 万元, 输出五年后各得多少? 练习 2.3 修改程序 ex02_showtime.cpp, 使得输出的时 分 秒都占两个位置, 如 :14 点 25 分 10 秒显示为 14:25:10,9 点 8 分 5 秒显示为 09:08:05

35 第三讲选择与循环 3.1 关系运算与逻辑运算 关系运算, 即比较大小 :> < == >= <=!= (1) 结论是真则返回 true, 否则返回 false (2) C++ 中用 1 表示 true,0 表示 false (3) bool 型变量的值为 0 时表示 false, 其他它值都表示 true (4) 注意 == 与 = 的区别 (5) 对浮点数进行比较运算时尽量不要使用 == 逻辑运算 :&&( 逻辑与 ) ( 逻辑或 )!( 逻辑非 ) (1) 表达式 1 && 表达式 2 - 先计算表达式 1 的值, 若是 true, 再计算表达式 2 的值 ; - 若表达式 1 的值是 false, 则不再计算表达式 2 (2) 表达式 1 表达式 2 - 先计算表达式 1 的值, 若是 false, 再计算表达式 2 的值 ; - 若表达式 1 的值是 true, 则不再计算表达式 2 (3) 优先级 :! 优于 && 优于 条件运算符 :? : 条件表达式? 表达式 1 : 表达式 2 (1) C++ 中唯一的三目运算符 ; (2) 条件表达式为真时返回表达式 1 的值, 否则返回表达式 2 的值 ; (3) 表达式 1 和表达式 2 的类型要一致 例 3.1 关系运算举例 1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int x1=1, x2=2, x3=3; 8 bool b1, b2, b3; 9 10 b1 = (x1 < x2) && (x2 < x3); // 正确写法 11 cout << "b1=" << b1 << "\n"; 12 b2 = x1 < x2 < x3; // 有没有问题? 13 cout << "b2=" << b2 << "\n"; 23

36 24 第三讲选择与循环 14 b3 = x3 > x2 > x1; // 有没有问题? 15 cout << "b3=" << b3 << "\n"; return 0; 18 } 3.2 选择结构 选择结构的两种实现方式 :if 和 switch IF 语句 (1) 单分支 : if ( 条件表达式 ) 语句 这里的语句可以是复合语句 ( 别遗漏大括号!) (2) 双分支 : if ( 条件表达式 ) else (3) 多分支 : 语句 语句 if ( 条件表达式 ) 语句 else if ( 条件表达式 ) 语句 else if ( 条件表达式 ) 语句..`else 语句 (4) 条件表达式两边的小括号不能省略! (5) if 语句可以嵌套 ; (6) 嵌套时每一层 if 都要和 else 配套, 若没有 else, 则需将该层 if 语句用 { } 括起来 SWITCH 结构 switch( 表达式 ) // 该表达式可以是整型 字符型 枚举型 { case 常量表达式 1:

37 3.2 选择结构 25 语句 case 常量表达式 2: 语句.`case 常量表达式 n: 语句 default: 语句 (1) 以 case 中的常量表达式值为入口标号, 由此开始顺序执行 ; (2) 每个 case 分支最后一般需要加 break 语句 ; (3) 每个 case 后面的常量表达式的值不能相同 ; (4) 每个 case 后面可以有多个语句 ( 复合语句 ), 但可以不用 { } 例 3.2 SWITCH 结构举例 1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int day; 8 9 cout << "Please input a day: "; 10 cin >> day; switch (day) 13 { 14 case 0: 15 cout << "Sunday" << endl; 16 break; 17 case 1: 18 cout << "Monday" << endl; 19 break; 20 case 2: 21 cout << "Tuesday" << endl; 22 break; 23 case 3: 24 cout << "Wednesday" << endl; 25 break; 26 case 4: 27 cout << "Thursday" << endl; 28 break; 29 case 5: 30 cout << "Friday" << endl; 31 break; 32 case 6: 33 cout << "Saturday" << endl; 34 break; 35 default: 36 cout << "Day out of range [Sunday,..., Saturday]" << endl; 37 break; 38 } return 0;

38 26 第三讲选择与循环 41 } 3.3 循环结构 循环结构的三种实现方式 :while 循环,do while 循环和 for 循环. 循环可以嵌套 WHILE 循环 DO WHILE 循环 FOR 循环 WHILE 循环 while( 条件表达式 ) { } 循环体语句 执行过程 (1) 计算条件表达式的值 ; (2) 如果是 真, 则执行循环体语句 ; 否则退出循环 ; (3) 返回第 (1) 步 如果循环体语句是复合语句, 别忘了大括号! 例 3.3 WHILE 循环举例 1 #include <iostream> 2

39 3.3 循环结构 27 3 using namespace std; 4 5 int main() 6 { 7 int i=1, n, s=0; 8 9 cout << "Please input n: " ; 10 cin >> n; while ( i <= n ) 13 { 14 s += i; 15 i++; 16 } 17 cout << "1+...+" << n << "=" << s << endl; return 0; 20 } DO WHILE 循环 do { 循环体语句 } while( 条件表达式 ); 执行过程 (1) 执行循环体语句 ; (2) 判断条件表达式的值, 如果是 真, 返回第 (1) 步 ; 否则退出循环 与 while 循环的区别 : 无论条件是否成立, 循环体语句至少执行一次 FOR 循环 for( 初始化语句 ; 表达式 1; 表达式 2) { } 循环体语句 执行过程 (1) 执行初始化语句 ; (2) 计算表达式 1 的值, 如果是 真, 则执行循环体语句, 否则退出循环 ; (3) 执行表达式 2, 返回第二步 初始化语句, 表达式 1, 表达式 2 均可省略, 但分号不能省 ; 表达式 1 是循环控制语句, 如果省略的话就构成死循环 ; 循环体可以是单个语句, 也可以是复合语句 ( 大括号!);

40 28 第三讲选择与循环 初始化语句与表达式 2 可以是逗号语句 ; 若省略初始化语句和表达式 2, 只有表达式 1, 则等同于 while 循环 for 循环有时也可以描述为 for( 循环变量赋初值 ; 循环条件 ; 循环变量增量 ) { 循环体语句 } 循环变量可以在初始化语句中声明, 这样, 循环变量只在该循环内有效, 循环结束后, 循环变量 即被释放 1 s=0; 2 for (int i=1; i<=10; i++) 3 s=s+i; 循环的非正常终止 break // 跳出循环体, 但只能跳出一层循环, 一般用在循环语句和 switch 语句中 continue // 结束本轮循环, 执行下一轮循环, 一般用在循环语句中 goto // 跳转语句, 建议尽量不使用

41 3.4 程序示例 29 图 3.1. break 和 continue 图示 ( 以 for 循环为例 ) break 和 continue 通常要与 if 语句配合使用 3.4 程序示例 例 3.4 给定一个正整数, 在屏幕上打印其所有因子 1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int n, k; 8 9 cout << "Please input a positive integer: "; 10 cin >> n; 11 cout << "n=" << n << endl; 12 cout << "Its factors: "; 13

42 30 第三讲选择与循环 14 for (k=1; k <= n; k++) 15 if (n % k == 0) 16 cout << k << " "; 17 cout << endl; return 0; 20 } 例 3.5 在屏幕上打印九九乘法表 1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int i, j; 8 9 for (i = 1; i <= 9; i++) 10 { 11 for (j = 1; j <= i; j++) 12 cout << i << "*" << j << "=" << i*j << " "; 13 cout << endl; 14 } return 0; 17 } 例 3.6 找出 100 到 200 之间所有不能被 3 整除, 但能被 7 整除的数 1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int k; 8 9 cout << "100 到 200 之间所有不能被 3 整除, 但能被 7 整除的数有 :" << endl; 10 for (k = 100; k <= 200; k++) 11 if ( k % 3!= 0 && k % 7 == 0 ) cout << k << " "; 12 cout << endl; return 0; 15 } 例 3.7 计算两个正整数的最大公约数, 穷举法 1 #include <iostream> 2 3 using namespace std; 4

43 3.4 程序示例 31 5 int main() 6 { 7 int m, n, gcd; 8 9 cout << "Input m: "; cin >> m; 10 cout << "Input n: "; cin >> n; for (int k=1; k<=m && k<=n; k++) 13 { 14 if (m%k==0 && n%k==0) 15 gcd = k; 16 } 17 cout << " 最大公约数是 : " << gcd << endl; return 0; 20 } 若考虑执行效率的话, 可以将其中的循环加以改进, 以减少循环次数 1 // 改进后的程序 2 #include <iostream> 3 4 using namespace std; 5 6 int main() 7 { 8 int m, n, gcd; 9 10 cout << "Input m: "; cin >> m; 11 cout << "Input n: "; cin >> n; int k = (m<n? m : n); 14 for ( ; k>0; k--) 15 { 16 if (m%k==0 && n%k==0) 17 { 18 gcd = k; break; 19 } 20 } 21 cout << " 最大公约数是 : " << gcd << endl; return 0; 24 } 例 3.8 判断一个给定的正整数是否为素数 1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int n, k; 8 9 cout << " 请输入一个正整数 : ";

44 32 第三讲选择与循环 10 cin >> n; if (n == 1) 13 cout << "n=" << n << " 不是素数." << endl; 14 else 15 for (k = 2; k < n; k++) 16 if ( n % k == 0 ) break; if (k < n) 19 cout << "n=" << n << " 不是素数." << endl; 20 else 21 cout << "n=" << n << " 是素数." << endl; return 0; 24 } 例 3.9 猜生日 : 请回答你的生日出现在下面五组数的哪几组中? 这几组数的第一个数字之和就是你 的生日 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int birthday=0; 8 char answer; 9 10 cout << " 你的生日在下面的数组中吗? " << endl; 11 cout << " \n " << endl; 12 cout << " 请输入 Y 或 N: " ; 13 cin >> answer; 14 if (answer=='y' answer=='y') 15 birthday = birthday + 16; cout << "\n 你的生日在下面的数组中吗? " << endl; 18 cout << " \n " << endl; 19 cout << " 请输入 Y 或 N: " ; 20 cin >> answer; 21 if (answer=='y' answer=='y') 22 birthday = birthday + 8; cout << "\n 你的生日在下面的数组中吗? " << endl; 25 cout << " \n " << endl; 26 cout << " 请输入 Y 或 N: " ; 27 cin >> answer;

45 3.5 上机练习 if (answer=='y' answer=='y') 29 birthday = birthday + 4; cout << "\n 你的生日在下面的数组中吗? " << endl; 32 cout << " \n " << endl; 33 cout << " 请输入 Y 或 N: " ; 34 cin >> answer; 35 if (answer=='y' answer=='y') 36 birthday = birthday + 2; cout << "\n 你的生日在下面的数组中吗? " << endl; 39 cout << " \n " << endl; 40 cout << " 请输入 Y 或 N: " ; 41 cin >> answer; 42 if (answer=='y' answer=='y') 43 birthday = birthday + 1; cout << "\n 你的生日是 : " << birthday << endl; return 0; 48 } 3.5 上机练习练习 3.1 成绩转换练习 3.2 如何跳出多重循环练习 3.3 最大素数练习 3.4 大数吃小数练习 3.5 计算常数 e 练习 3.6 闰年 : 输出 21 世纪 (2001 至 2100 年 ) 中所有的闰年 闰年的判定标准 :(1) 能被 4 整除且不能被 100 整除 ; 或者 (2) 能被 400 整除 要求 : 每行输出 6 个, 闰年之间用两个空格隔开

46 第四讲函数 4.1 函数的声明 定义与调用 函数是程序设计中, 对功能的抽象, 是 C++ 的基本模块 ; C++ 程序是由函数构成的 ( 一个或多个函数 ); C++ 程序必须有且只能有一个 main 函数 ; 函数的定义 类型标识符函数名 ( 形式参数列表 ) // 函数头 { } 函数体 (1) 类型标识符 指明了本函数的类型, 即函数返回值的类型 ; (2) 若没有返回值, 则使用 void 形式参数列表 类型标识符变量, 类型标识符变量, (1) 形式参数表 ( 简称形参 ) 要指定数据类型 (2) 有多个形参时, 用逗号隔开, 每个形参需单独指定数据类型 (3) 如果函数不带参数, 则形参可以省略, 但括号不能省 (4) 形参只在函数内部有效 / 可见, 即是局部变量 1 int my_max(int x, int y) // OK 2 int my_max(int x, y) // ERROR 函数的返回值 (1) 函数返回值通过 return 语句给出 ; (2) 若没有返回值, 可以不写 return, 也可以写不带表达式的 return 函数的调用 (1) 函数调用前须先声明 : 可以在主调函数中, 或程序文件中所有函数之外声明 (2) 函数的调用方式 : 函数名 ( 实参数表 ) (3) 被调函数可以出现在表达式中, 此时必须要有返回值 (4) 主调函数与被调函数 : 被调函数在主调函数前定义, 则可直接调用, 否则必须先声明 34

47 4.1 函数的声明 定义与调用 35 例 4.1 计算两个整数的最大值 1 #include <iostream> 2 3 using namespace std; 4 5 int my_max(int x, int y) 6 { 7 if (x > y) return x; 8 else return y; 9 } int main() 12 { 13 int m, n; cout << "please input m and n: " ; 16 cin >> m >> n; cout << "max(" << m <<"," << n <<")=" << my_max(m,n) << endl; return 0; 21 } 例 4.2 计算 x k 1 #include <iostream> 2 3 using namespace std; 4 5 double my_power(double x, int k); // 函数声明 6 7 int main() 8 { 9 double x; x = my_power(3,3) + my_power(4,4); 12 cout << "3^3 + 4^4 = " << x << endl; return 0; 15 } double my_power(double x, int k) 18 { 19 double y = 1.0; for (int i=1; i<=k; i++) 22 y = y * x; return y; 25 }

48 36 第四讲函数 例 4.3 输入一个二进制数, 输出相应的十进制数 1 #include <iostream> 2 3 using namespace std; 4 5 int my_power2(int k); // compute 2^k, 函数声明 6 7 int main() 8 { 9 long x, x0; 10 int y = 0, k = 0, t; cout << " 请输入一个二进制数 :"; 13 cin >> x; x0 = x; 16 while (x!= 0) 17 { 18 t = x % 10; 19 if (t==1) y = y + my_power2(k); 20 x = x / 10; 21 k = k + 1; 22 } cout << " 二进制数 " << x0 << " 对应的十进制数为 " << y << endl; return 0; 27 } int my_power2(int k) // compute 2^k 30 { 31 int y = 1; for (int i=1; i<=k; i++) 34 y = y * 2; return y; 37 } 思考 : 如何计算 对应的十进制数? 例 4.4 利用 sin 函数的 Taylor 展开计算 sin(π/2) 的值. ( 直到级数某项的绝对值小于 为止 ) 1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 sin(x) = x 1! x3 3! + x5 5! x7 7! + = ( 1) k 1 x 2k 1 (2k 1)! 6 double mysin(double x) // compute sin(x) k=1

49 4.1 函数的声明 定义与调用 37 7 { 8 double y, ak; 9 int k; y = 0.0; 12 k = 1; 13 ak = x; 14 while ( fabs(ak) >= 1e-15) // fabs --> absolute value 15 { 16 y = y + ak; 17 ak = -ak*x*x/(2*k*(2*k+1)); 18 k = k + 1; 19 } return y; 22 } int main() 25 { 26 double x, y; cout << " 请输入 x:"; 29 cin >> x; y = mysin(x); cout << "mysin(" << x << ")=" << y << endl; 34 cout << " 自带函数 :" << sin(x) << endl; return 0; 37 } 思考 : 利用上面的公式计算 sin(41π/2), 结果如何? 例 4.5 找出 之间的数 m, 满足 m m 2 和 m 3 均为回文数. ( 回文数 : 各位数字左右对称的 整数, 如 11,121,1331) 分析 : 利用除以 10 取余的方法, 从最低位开始, 依次取出该数的各位数字 按反序重新构成新的数, 比较与原数是否相等, 若相等, 则原数为回文数 1 #include <iostream> 2 3 using namespace std; 4 5 bool issymm(long n) // 判别回文数 6 { 7 long i, m; 8 9 i = n; 10 m = 0; while(i) 13 { 14 m = m*10 + i%10;

50 38 第四讲函数 15 i = i/10; 16 } 17 return ( m==n ); 18 } int main() 21 { 22 long m; for(m=11; m<1000; m++) 25 if (issymm(m) && issymm(m*m) && issymm(m*m*m)) 26 cout << "m=" << m << ", m*m=" << m*m 27 <<", m*m*m=" << m*m*m << endl; return 0; 30 } 例 4.6 随机数的生成. ( 需包含头文件 cstdlib) rand(): 返回一个 0 RAND_MAX 之间的伪随机整数 srand(seed): 设置种子 如不设定, 默认种子为 1 相同的种子对应相同的伪随机整数 每次执行 rand() 后, 种子会自动改变, 但变化规律是固定的 1 #include <iostream> 2 #include <cstdlib> 3 4 using namespace std; 5 6 int main() 7 { 8 int seed, x; 9 10 cout << "Enter seed: "; 11 cin >> seed; srand(seed); 14 x = rand(); 15 cout << "x=" << x << endl; cout << "seed=" << seed << ", RAND_MAX=" << RAND_MAX << endl; // 每次执行 rand 函数后, 种子会自动改变, 但变化规律是固定的 20 for(int i=0;i<10;i++) 21 { 22 x = rand(); 23 cout << "i=" << i << ", x=" << x << endl; 24 } return 0; 27 }

51 4.1 函数的声明 定义与调用 39 思考 : 如何生成 [a, b] 之间的随机整数?( 其中 a, b 为正整数 ) 思考 : 如何生成 [0, 1] 之间的随机小数? 如何生成 [a, b] 之间的随机小数?( 其中 a, b 为任意浮点 数 ) 例 4.7 计时函数 clock ( 需包含头文件 ctime) clock() : 返回进程启动后所使用的 cpu 总毫秒数. 1 #include <iostream> 2 #include <ctime> 3 4 using namespace std; 5 6 const int n=20000; 7 8 int main() 9 { 10 clock_t t0, t1; 11 double totaltime; 12 int i, j, a; t0 = clock(); // 程序开始 17 for(i=0; i<n; i++) 18 for(j=0; j<n; j++) 19 a = (i+1)*(j+1); 20 // 程序结束 t1 = clock(); totaltime = (double)(t1-t0)/clocks_per_sec; 25 cout << " 运行时间为 :" << totaltime << " 秒!" << endl; return 0; 28 } CLOCKS_PER_SEC: 每秒的滴答数, 通常为 例 4.8 计时函数 time ( 需包含头文件 ctime) time(null) 或 time(0) : 返回从 1970 年 1 月 1 日 0 时至当前时刻的总秒数. 1 #include <iostream> 2 #include <ctime> 3 4 using namespace std; 5 6 const int n=20000; 7 8 int main() 9 {

52 40 第四讲函数 10 time_t t0, t1; 11 int i, j, a; t0 = time(null); // 程序开始 16 for(i=0; i<n; i++) 17 for(j=0; j<n; j++) 18 a = (i+1)*(j+1); 19 // 程序结束 t1 = time(null); 22 cout << " 运行时间 :" << t1-t0 << " 秒!" << endl; 23 return 0; 24 } 例 4.9 ( 猜数游戏 ) 由计算机随机产生 [1, 100] 之间的一个整数, 然后由用户猜测这个数 要求根据用 户的猜测情况给出不同的提示 : 如果猜测的数大于产生的数, 则显示 Larger; 小于则显示 Smaller; 等于则显示 You won! 同时退出游戏 用户最多有 7 次机会 1 #include <iostream> 2 #include <ctime> 3 #include <cstdlib> 4 5 using namespace std; 6 7 int main() 8 { 9 int x, guess, flag = 1; 10 int N = 7; srand(time(null)); 13 x = rand()% ; cout << " 欢迎参加猜数游戏! 你共有 " << N << " 次机会 " << endl; 16 cout << " 请猜测一个 1 到 100 之间的一个整数 \n" << endl; 17 for (int k=1; k<=n; k++) 18 { 19 cout << "Input your guess: "; 20 cin >> guess ; 21 if (guess < x) cout << "Smaller\n"; 22 else if (guess > x) cout << "Larger\n"; 23 else 24 { 25 cout << "Congratulation, you won!\n" << endl; 26 flag = 0; 27 break; 28 } 29 if (k==n) break; 30 cout << " 你还有 " << N-k << " 次机会!\n" << endl ; 31 } if (flag == 1) cout << "\nsorry, you lost!\n" << endl; 34

53 4.2 函数间的参数传递 return 0; 36 } Tips: 如何生成每次都不同的随机整数? 1 srand(time(null)); // srand(time(0)) 2 x = rand(); 4.2 函数间的参数传递 传递方式一 : 值传递 (1) 传递时是将实参的值传递给对应的形参, 即单向传递 ; (2) 形参只在函数被调用时才分配存储单元, 调用结束即被释放 ; (3) 实参可以是常量 变量 表达式 函数 ( 名 ) 等, 但它们必须要有确定的值 ; (4) 实参和形参在数量 类型 顺序上应严格一致 ; (5) 形参获得实参传递过来的值后, 便与实参脱离关系 传递方式二 : 引用传递 (1) 引用的声明与使用 :& (2) 引用是一种特殊类型的变量, 可看作是变量的别名 ; (3) 声明一个引用时必须初始化, 指向一个存在的对象 ; (4) 引用一旦初始化就不能改变, 即不能再作为其它对象的引用 ( 别名 ); (5) 若引用作为形参, 则调用函数时才会被初始化, 此时形参是实参的一个别名, 对形参的任何 操作也会直接作用于实参 例 4.10 引用作为形参, 交换两个整数的值 1 #include <iostream> 2 3 using namespace std; 4 5 void swap_old(int a, int b) // 值传递 6 { 7 int t = a; 8 a = b; b = t; 9 } void swap_new(int & a, int & b) // 引用传递 12 { 13 int t = a; 14 a = b; b = t; 15 } int main() 18 { 19 int x = 5, y = 8; 20

54 42 第四讲函数 21 cout << "Before swap: x=" << x << ", y=" << y << endl; swap_old(x, y); 24 cout << "After swap_old: x=" << x << ", y=" << y << endl; swap_new(x, y); 27 cout << "After swap_new: x=" << x << ", y=" << y << endl; return 0; 30 } 4.3 函数嵌套与内联函数 函数的嵌套调用 (1) 函数可以嵌套调用, 但不能嵌套定义 (2) 函数也可以递归调用 ( 函数可以直接或间接调用自己 ) 例 4.11 利用下边的公式计算阶乘 : 1, n = 0, n! = n (n 1)!, n > 0. 1 #include <iostream> 2 3 using namespace std; 4 5 int factorial_loop(int n); // 普通方式 ( 循环 ) 6 int factorial_recursion(int n); // 递归方式 7 8 int main() 9 { 10 int n, y; 11 cout << " 请输入 n:"; 12 cin >> n; y = factorial_loop(n); cout << " 普通方式 :" << n << "!=" << y << endl; y = factorial_recursion(n); 19 cout << " 递归方式 :" << n << "!=" << y << endl; return 0; 22 } int factorial_loop(int n) // 普通方式 25 { 26 int y = 1; for (int i=1; i<=n; i++) 29 y = y * i; 30

55 4.3 函数嵌套与内联函数 return y; 32 } int factorial_recursion(int n) // 递归方式 35 { 36 if (n==0) return 1; 37 else return n*factorial_recursion(n-1); 38 } 对同一个函数的多次不同调用中, 编译器会给函数的形参和局部变量分配不同的存储空间, 它们互不影响 例 4.12 汉诺塔问题 : 有三根针 A B C,A 针上有 n 个大小不同的盘子, 大的在下, 小的在上, 把这 n 个盘子从 A 针移到 C 针, 在移动过程中可以借助 B 针 要求 :(1) 每次只允许移动一个 盘,(2) 在移动过程中在三根针上的盘子都要保持大盘在下, 小盘在上 分析 : 该问题可分解为下面三个步骤 : (1) 将 A 上 n 1 个盘子移到 B 针上 ( 借助 C 针 ); (2) 把 A 针上剩下的一个盘子移到 C 针上 ; (3) 将 n 1 个盘子从 B 针移到 C 针上 ( 借助 A 针 ) 上面三个步骤包含两种操作 : (1) 将多个盘子从一个针移到另一个针上, 这是一个递归的过程, 我们用 hanoi 函数实现 ; (2) 将 1 个盘子从一个针上移到另一针上, 该过程用 move 函数实现 1 #include <iostream> 2 3 using namespace std; 4 5 void move(char src, char dest) // 移动一个盘子 : 从 src 到 dest 6 { 7 cout << src << "-->" << dest << endl; 8 } 9 10 void hanoi(int n, char src, char medium, char dest) // 移动多个盘子 11 { 12 if (n==1) 13 move(src, dest); 14 else 15 { 16 hanoi(n-1, src, dest, medium); // 将上面 n-1 个盘子移到中间柱子上 17 move(src, dest); // 将最下面的一个盘子移到目标柱子上 18 hanoi(n-1, medium, src, dest); // 将中间柱子上的盘子移到目标柱子上

56 44 第四讲函数 19 } 20 } int main() 23 { 24 int m; cout << "Enter the number of diskes:" ; 27 cin >> m; 28 cout << "the steps to moving " << m << " diskes:" << endl; 29 hanoi(m,'a','b','c'); return 0; 32 } 内联函数 (1) 关键字 inline (2) 编译时在调用处用函数体进行替换 ; (3) 使用内联函数能节省参数传递 控制转移等开销, 提高代码的执行效率 ; (4) 内联函数通过应该功能简单 规模小 使用频繁 ; (5) 内联函数体内不建议使用循环语句和 switch 语句 ; (6) 有些函数无法定义成内联函数, 如递归调用函数等 例 4.13 内联函数举例 1 #include <iostream> 2 #include<ctime> 3 4 using namespace std; 5 6 inline double f(double x) // 内联函数 7 { 8 return 2*x*x - 1; // f(x) = 2x^2-1 9 } int main() 12 { cout << "f(3)=" << f(3.0) << endl; return 0; 17 } 4.4 数据的作用域每个变量都有作用域, 即在程序中哪些地方可以引用该变量 数据的作用域 : 数据在程序中有效的区域 C++ 的作用域 : (1) 函数原型作用域 : 函数原型声明时形参的作用范围, 仅限形参列表的左右括号之间 ; (2) 局部作用域 ( 函数, 语句块等 );

57 4.4 数据的作用域 45 (3) 类作用域 在函数声明时, 形参的变量名可省略, 但类型不能省, 比如下面两条语句是等价的 : 1 int my_max(int x, int y); 2 int my_max(int x, int y); 局部变量与全局变量 (1) 每个变量都有作用域, 即在程序中哪些地方可以使用该变量 ; (2) 函数定义时的形参, 或函数中定义的变量均为局部变量, 只在该函数内有效 ; (3) 语句块中定义的变量是局部变量, 只在该语句块中有效 ; (4) for 循环的初始语句中定义的变量也是局部变量, 只在 for 循环中有效 ; (5) 在所有函数外定义的变量为全局变量, 在它后面定义的函数中均可以使用 ; 若要在它前面定 义的函数中使用该全局变量, 则需声明其为外部变量 extern 类型名变量名 ; 若局部变量与全局变量同名, 则优先使用局部变量! 作用域解析运算符 :: 若存在同名的局部变量和全局变量, 则缺省引用局部变量, 此时若需引用全局变量, 需在变量名 前加作用域解析运算符 名字空间 namespace 大型程序通常由不同模块组成, 不同模块中的类和函数可能存在重名 为解决这个问题,C++ 引 入命名空间概念 namespace 名字空间名 { } 名字空间内的各种声明, 包括函数声明, 类声明等 (1) 名字空间内的元素, 可以是类 函数 变量等, 均称为名字 ; (2) 名字空间的使用 :using (3) 可以将名字空间中的所有名称都导入到当前作用域中, 也可以只导入指定的某个名称 ; (4) 标准库的所有函数 类 对象等, 都在 std 名字空间中 例 4.14 名字空间举例 1 #include <iostream> 2 3 using namespace std; 4 5 namespace mynames 6 { 7 int k = 3;

58 46 第四讲函数 8 double pi = 3.14; 9 int my_max(int x, int y); 10 double my_power(double x, int k); 11 } int main() 14 { 15 using mynames::my_power; 16 using mynames::k; double x = 3.0, y; // cout << "pi=" << pi << "\n" << endl; // error y = my_power(x, k); // 23 cout << "y=" << y << "\n" << endl; return 0; 26 } int mynames::my_max(int x, int y) 29 { 30 if ( x > y ) return x; 31 else return y; 32 } double mynames::my_power(double x, int k) 35 { 36 if (k==1) return x; 37 else 38 { 39 double y = 1.0; for (int i=1; i<=k; i++) 42 y = y * x; return y; 45 } 46 } 可见性 (1) 可见性是指对标识符 ( 变量, 函数等 ) 是否可以访问 ; (2) 如果标识符在某处可见, 则就可以在该处引用此标识符 ; (3) 对于两个嵌套的作用域, 若内层作用域内定义了与外层作用域中同名的标识符, 则外层作用域的标识符在内层不可见 生存期 (1) 静态生存期 : 生存期与程序的运行期相同, 即一直有效 ; (2) 动态生存期 : 当对象所在的程序块执行完后即消失 ; (3) 静态变量和全局变量 : 静态生存期 ; (4) 动态变量 : 动态生存期 ; (5) 局部变量缺省为动态变量 静态变量

59 4.5 形参带缺省值的函数 47 (1) 静态变量的声明 : static 类型名变量名 ; (2) 静态局部变量不会随函数的调用结束而消失, 下次调用该函数时, 该变量会保持上次调用后 的值 ; (3) 没有初始化的静态变量会自动初始化为 0; (4) 静态变量只能初始化一次 4.5 形参带缺省值的函数 形参缺省值 (1) 函数在定义时可以预先给形参设定一个值 ( 即缺省值 ), 函数被调用时, 如果给定实参, 则采 用实参的值, 否则采用预先设定的缺省值 (2) 好处 : 调用时可以不提供或只提供部分实参 形参可以全部带缺省值, 也可以部分带缺省值, 如果部分带缺省值, 则规定如下 : (1) 形参缺省值必须从右向左顺序声明 ; (2) 带缺省值的形参, 其右面不能有不带缺省值的形参 ( 在函数调用时, 实参与形参的配对是按 从左向右的顺序进行的 ); 1 int add(int x, int y=5, int z=6); // 正确 2 int add(int x=1, int y=5, int z); // 错误 3 int add(int x=1, int y, int z=6); // 错误 缺省值是在函数声明时设定, 还是在函数定义时设定? (1) 同一作用域中, 哪个在前就由哪个设定, 后面的不能再设定 ( 如果先声明, 后定义, 则声明 时设定, 定义时就不能再设定, 反之亦然 ); (2) 在不同作用域内, 允许设置不同的缺省值 例 4.15 给形参设置缺省值 : 先声明后定义 1 #include <iostream> 2 3 using namespace std; 4 5 int add(int x=1, int y=2); // 声明时设定缺省值 6 7 int main() 8 { 9 int add(int x=3, int y=4); // 不同作用域的声明可设定不同的缺省值 10 cout << "In main: add()=" << add() << endl; void fun(); 13 fun(); return 0; 16 } 17

60 48 第四讲函数 18 void fun() 19 { 20 cout << "In fun: add()=" << add() << endl; 21 } int add(int x, int y) // 这里不能再出现默认形参 24 { 25 return x+y; 26 } 例 4.16 给形参设置缺省值 : 先定义后声明 1 #include <iostream> 2 3 using namespace std; 4 5 int add(int x=1, int y=2) // 定义时设定缺省值 6 { 7 return x+y; 8 } 9 10 int main() 11 { 12 int add(int x=3, int y=4); // 不同作用域的声明可设定不同的缺省值 13 cout << "In main: add()=" << add() << endl; 14 cout << "In main: add(11)=" << add(11) << endl; 15 cout << "In main: add(11,12)=" << add(11,12) << endl; 16 cout << endl; void fun(); 19 fun(); return 0; 22 } void fun() 25 { 26 int add(int x=5, int y=6); // 不同作用域的声明可设定不同的缺省值 27 cout << "In fun: add()=" << add() << endl; 28 cout << "In fun: add(11)=" << add(11) << endl; 29 cout << "In main: add(11,12)=" << add(11,12) << endl; 30 } 4.6 函数重载 C++ 允许功能相近的函数在相同的作用域内使用相同函数名, 从而形成重载, 方便使用, 便于记忆 函数重载 : 两个以上的函数, 具有相同的函数名, 但形参的个数或类型不同, 调用时, 编译器会根据实参和形参的最佳匹配, 自动确定调用哪一个函数 (1) 功能相近的函数在相同的作用域内以相同函数名存在 ; (2) 重载函数特点 : 函数名必须相同, 形参必须不同 ( 个数不同或类型不同 );

61 4.7 预编译处理与多文件结构 49 (3) 函数名相同, 形参个数与类型相同, 函数返回值类型不同, 不形成重载, 是语法错误! (4) 在使用带有默认形参的重载函数时, 要注意防止二义性! 不建议将功能不同的函数定义为重载函数 例 4.17 函数重载举例 1 #include <iostream> 2 3 using namespace std; 4 5 int add(int x, int y) 6 { return x + y; } 7 8 double add(double x, double y) // 函数名与上面相同, 但形参不同 9 { return x + y; } int main() 12 { 13 int a=1, b=2; 14 double x=1.1, y=2.2; cout << "a+b=" << add(a,b) << "\n" << endl; cout << "x+y=" << add(x,y) << "\n" << endl; return 0; 21 } 4.7 预编译处理与多文件结构 头文件 #include < 文件名 > // 按标准方式导入头文件, 即在系统目录中寻找指定的文件 #include " 文件名 " // 先在当前目录中寻找, 然后再按标准方式搜索 表 4.1. 常用头文件 iostream iomanip cmath 基本输入输出 操纵符 数学函数 ctime 计时函数,clock, time, clock_t, time_t, CLOCKS_PER_SEC,... cstdlib abs, rand, srand, system,... cstring cctype C 语言字符串操作 C 语言字符操作 cstdio C 语言文件操作 : fopen, fclose, fread, fwrite, printf, scanf,...

62 50 第四讲函数 string vector fstream 字符串类 向量类 文件流 定义符号常量 1 #define PI // 定义符号常量 2 #undef PI // 删除由 #define 定义的符号常量 在很多情况下可以由 const 实现该功能 此外,#define 还可以用来定义带参数的宏, 但 也可以用内联函数取代 条件编译 #if 常量表达式 #endif 程序正文 #if 常量表达式 #else #endif 程序正文 程序正文 #if 常量表达式 1 程序正文 #elif 常量表达式 2 // 当 常量表达式 非零时编译 // 当 常量表达式 非零时编译 // 否则编译这段程序 // 当 常量表达式 1 非零时编译 程序正文 // 否则, 当 常量表达式 2 非零时编译 #elif 常量表达式 3 程序正文 // 否则, 当 常量表达式 3 非零时编译 #else #endif 程序正文 #ifdef 标识符 #else #endif 程序正文 程序正文 // 否则编译这段程序 // 当 标识符 已由 #define 定义时编译 // 否则编译这段程序

63 4.7 预编译处理与多文件结构 51 #ifndef 标识符程序正文 // 当 标识符 没有定义时编译 #else 程序正文 // 否则编译这段程序 #endif 多文件结构 一个程序可以由多个文件组成, 编译时可以使用工程 / 项目来组合 若使用命令行编译, 则需要同 时编译 外部变量 : 如果需要用到其它文件中定义的变量, 则需要用 extern 声明其为外部变量 extern 类型名变量名 ; 外部函数 : 如果需要用到其它文件中定义的函数, 则需要用 extern 声明其为外部函数 extern 函数声明 / 函数原型 ; 系统函数 (1) 标准 C++ 函数 ( 库函数 ): 参见 (2) C++ 的系统库中提供了几百个函数可供程序员直接使用, 使用库函数时要包含相应的头文件 ; (3) 非标准 C++ 函数 : 操作系统或编译环境提高的系统函数 充分使用库函数不仅可以大大减少编程工作量, 还可以提高代码可靠性和执行效率 π 2 例 4.18 用蒙特卡洛 (Monte Carlo) 方法计算定积分 sin(x)dx 的近似值 0 分析 : 定积分计算 b 1 #include <iostream> 2 #include <cstdlib> 3 #include <ctime> 4 #include <cmath> 5 6 using namespace std; 7 a f(x)dx = lim xi f(ξ i ) ( x i = x i x i 1, ξ i [x i 1, x i ]) x i 0 n = lim hf(x i ) ( 取 x i = h b a n n, ξ i = x i ) i=1 = lim h n f(x i ). n i=1 8 const int n = ; // 随机点的个数 9 const double a = 0.0; 10 const double b = atan(1)*2; // b = pi/2

64 52 第四讲函数 11 const double length = b - a; // 区间长度 int main() 14 { 15 long double S = 0.0; 16 double x; srand(time(0)); 19 for(int i=1; i<=n; i++) 20 { 21 x = a + length*double(rand())/rand_max; 22 S = S + sin(x); 23 } 24 cout << "S=" << length/n*s << endl; return 0; 27 } 4.8 上机练习练习 4.1 编写函数, 判断一个整数是否为素数, 并在主函数中找出三位数中所有的素数, 在屏幕上输出时每行输出 8 个 练习 4.2 编写函数, 判断给定的年份是否为闰年, 并在主函数中输出 21 世纪 (2001 至 2100 年 ) 中所有的闰年, 每行输出 6 个 ( 闰年 : 能被 400 整除 ; 或者能被 4 整除但不能被 100 整除 ) 练习 4.3 编写程序, 用 while 实现猜数游戏练习 4.4 Emirp 数 : 如果一个素数反转后仍然是素数, 则称这个素数为 emirp 数 如 13 是素数, 反转后 31 也是素数, 故 13 和 31 都是 emirp 数 编写程序, 输出前 100 个 emirp 数, 每行输出 5 个 要求 : 先编写两个函数 :isprime 和 reverse, 分别用于判断素数和计算反序数 练习 4.5 梅森素数 : 如果一个素数可以写成 2p-1 的形式, 则称该素数为梅森素数 编写程序, 找出所有 p<32 的梅森 (Mersenne) 素数, 并以指定形式输出 ( 注意优化循环次数 ) 练习 4.6 3n + 1 问题 : 给定一个正整数 n, 不断按照下面的规律进行运算 : 如果当前数是偶数, 则下一个数为当前数除以 2, 如果当前数为奇数, 则下一个数为当前数乘 3 加 1 整个过程直到当前数是 1 为止 这样形成的数列的长度称为数 n 的链数 如 : 从 3 开始, 得到的数列为 :3, 10, 5, 16, 8, 4, 2, 1, 所以整数 3 的链数为 8 (a) 编写一个函数 ( 函数名 num_chain ), 计算给定的正整数的链数 ;(b) 找出 [90, 100] 中, 链数最大的那个数 练习 4.7 使用递归实现上面问题中的函数 num_chain 练习 4.8 编写函数, 用递归方法计算 Fibonacci 数, 并在主函数中输出第 40 个 Fibonacci 数 练习 4.9 给定一个正整数, 使用递归方法找出其所有的素数因子 ( 提示 : 先找出最小的素数因子, 然后除以这个数, 得到商, 再找商的最小素数因子, 以此类推, 构成递归 注意递归的出口 只要在屏幕上输出这些素数因子, 不用保存 ) 练习 4.10 编写两个函数, 分别计算两个正整数的最大公约数与最小公倍数, 要求用递归方法计算最大公约数, 最小公倍数则可以通过调用最大公约数实现, 并在主函数中计算 2012 与 1509 的最大

65 4.8 上机练习 53 公约数与最小公倍数 在例 3.7 中, 我们用穷举法来计算两个非负整数的最大公约数, 效率不高 早在公元前 300 年, 欧几里得就提出了一种效率较高的计算方法, 其核心思想是基于下面的结论 : gcd(a, b) = gcd(b, a mod b) ( 这里假定 a > b). 由此, 可以通过递归方法 ( 辗转求余法, 类似于辗转相除法 ) 设计求解最大公约数的高效 算法 π 2 练习 4.11 用蒙特卡洛 (Monte Carlo) 投点法计算定积分 sin(x)dx 的近似值的近似值 0

66 第五讲数组 数组 : 具有一定顺序关系的若干相同类型变量的集合体 5.1 一维数组 一维数组的声明 : 类型标识符数组名 [n] // 声明一个长度为 n 的一维数组 ( 向量 ) (1) 数组名存放的是数组在内存中的首地址 ; (2) 类型标识符 : 数组元素的数据类型 ; (3) n 为数组的长度, 即元素的个数, 可以是一个表达式, 但值必须是一个确定的正整数 一维数组的引用 : 数组名 [k] // 注 : 下标 k 的取值为 0 到 n-1 (1) 只能逐个引用数组元素, 而不能一次引用整个数组 ; (2) 数组元素在内存中顺序存放, 它们的地址是连续的 ; (3) 数组名代表数组存放在内存中的首地址 注意 : 数组的下标不能越界, 否则可能会引起严重的后果! 例 5.1 一维数组举例 1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 int main() 7 { 8 int i, x[5]; 9 10 for (i=0; i<5; i++) 11 x[i] = 2*i; for (i=0; i<5; i++) 14 cout << "x[" << i << "]=" << x[i] << endl; return 0; 17 } 一维数组的初始化 : 在声明时可以同时赋初值 54

67 5.2 二维数组 55 1 int x[5]={0,2,4,6,8}; (1) 全部元素都初始化时可以不指定数组长度, 如 int x[]={0,2,4,6,8}; (2) 可以部分初始化, 即只给部分元素赋初值, 如 int x[5]={0,2,4}; (3) 若数组声明时进行了部分初始化, 则没有初始化的元素自动赋值为 0; (4) 声明数组时, 若长度为一个表达式, 且含有变量, 则不能初始化! 只能对数组元素赋值, 不能对数组名赋值! 若数组元素没有赋值, 则其值是不确定的 ( 静态数据类型除外 ); 注意数组声明与数组引用的区别 ; 注意数组初始化与数组赋值的区别 5.2 二维数组 二维数组的声明 类型标识符变量名 [m][n] // 声明一个 m x n 的二维数组 ( 矩阵 ) 二维数组的引用 变量名 [i][j] // 注意下标不要越界! 二维数组的存储 : 按行存储 在 C++ 中, 二维数组可以看作是由一维数组组成的数组 二维数组的初始化 (1) 全部初始化, 此时可以省略第一维的大小 ( 但不能省略其他维数 ); 1 int x[2][3]={1,3,5,2,6,10}; 2 int x[][3]={1,3,5,2,6,10}; // 省略第一维的大小 (2) 可以分组初始化, 也可以部分初始化 1 int x[2][3]={{1,3,5}, {2,6,10}}; 2 int x[2][3]={{1}, {2,6}}; // 部分初始化 多维数组 : 多维数组的赋值 引用 初始化与二维数组类似

68 56 第五讲数组 类型标识符变量名 [n1][n2][n3]... 例 5.2 计算 n 阶 Hilbert 矩阵与全是 1 的向量的乘积, 其中 1 #include <iostream> 2 #include <cmath> 3 #include <ctime> 4 5 using namespace std; 6 7 const int n = 1000; // 矩阵维数 8 9 int main() 10 { 11 clock_t t0, t1; 12 int i, j; 13 double H[n][n], x[n], y[n]; t0 = clock(); 16 for (i=0; i<n; i++) 17 { 18 x[i] = 1.0; // 给 x 赋值 19 y[i] = 0.0; // 给 y 赋初值 20 } 21 H = [h ij ] n i,j=1, h ij = 22 for (i=0; i<n; i++) 23 for(j=0; j<n; j++) 24 H[i][j] = 1.0 / (i+j+1); // Hilbert 矩阵 for(i=0; i<n; i++) 27 for(j=0; j<n; j++) 28 y[i] = y[i]+h[i][j]*x[j]; t1 = clock(); 31 1 i + j cout << "y[0]=" << y[0] << ", y[n-1]=" << y[n-1] << endl; 33 cout << "Time: " << double(t1-t0)/clocks_per_sec << endl; 34 cout << endl; cout << "x[0]=" << x[0] << ", x[n-1]=" << x[n-1] << endl; 37 cout << "H[0]=" << H[0][0] << ", H[n-1]=" << H[0][n-1] << endl; return 0; 40 } 5.3 数组作为函数参数 数组中的单个元素作实参 : 与单个变量一样, 采用值传递 ; 数组名作为参数 : 地址传递, 即传递的是数组的首地址

69 5.3 数组作为函数参数 57 (1) 形参后面要加中括号, 可以不指定第一维的大小 ; (2) 形参和实参都应该是数组名, 类型要一致 ; (3) 实参与形参代表的是同一个数组, 在函数中对形参的任何改动都会影响到实参 ; (4) 数组作为形参时一般不指定大小, 此时需要加一个参数, 用来传递实参数组的大小 ; (5) 若形参数组的大小中含有变量, 则必须是常量 函数调用时, 只需给出数组名即可 例 5.3 交换两个数组 1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 void my_swap(int a[], int b[], int n) 7 { 8 int t, i; 9 10 for (i=0; i<n; i++) 11 { 12 t = a[i]; a[i] = b[i]; b[i] = t; 13 } 14 } int main() 17 { 18 const int n=3; int i; 21 int x[n]={1,2,3}, y[n]={2,4,6}; for(i=0; i<n; i++) 24 cout << "x[" << i << "]=" << x[i] << "\t" 25 << "y[" << i << "]=" << y[i] << "\n"; my_swap(x,y,n); for(i=0; i<n; i++) 30 cout << "x[" << i << "]=" << x[i] << "\t" 31 << "y[" << i << "]=" << y[i] << "\n"; cout << endl; return 0; 36 } 例 5.4 计算矩阵各列的和 ( 函数形式 ) 1 #include <iostream> 2 #include <cmath> 3 #include <ctime> 4

70 58 第五讲数组 5 using namespace std; 6 7 const int m = 3, n = 4; // 矩阵维数 8 9 void sum_col(double A[][n], double s[]) // 计算矩阵列和, 只能省略第一维的大小 10 { 11 int i, j; 12 for(j=0; j<n; j++) 13 s[j]=0.0; for(j=0; j<n; j++) 16 for(i=0; i<m; i++) 17 s[j] = s[j] + A[i][j]; 18 } int main() 21 { 22 int i, j; 23 double H[m][n], s[n]; for(i=0; i<m; i++) 26 for(j=0; j<n; j++) 27 H[i][j] = 1.0 / (i+j+1); // Hilbert 矩阵 sum_col(h, s); cout << "H[0][0]=" << H[0][0] << ", H[0][n-1]=" << H[0][n-1] << endl; 32 cout << "s[0]=" << s[0] << ", s[n-1]=" << s[n-1] << endl; return 0; 35 } 5.4 应用实例 : 矩阵乘积的快速算法 普通方法 To be continued Strassen 方法 Strassen [1] 在 1969 年提出了计算矩阵乘积的快速算法, 将运算量降为 O(n 2.81 ) 先以二阶矩阵为例, 设 [ ] [ ] a11 a 12 b11 b 12 A =, B =. a 21 a 22 b 21 b 22 则 C = AB 的每个分量为 c 11 = a 11 b 11 + a 12 b 21, c 12 = a 11 b 12 + a 12 b 22, c 21 = a 21 b 11 + a 22 b 21, c 22 = a 21 b 12 + a 22 b 22. 在 Strassen 算法中, 我们并不直接通过上面的公式来计算 C, 而是先计算下面 7 个量 : x 1 = (a 11 + a 22 )(b 11 + b 22 ), x 2 = (a 21 + a 22 )b 11,

71 5.5 应用实例 : 列主元 Gauss 消去法求解线性方程组 59 x 3 = a 11 (b 12 b 22 ), x 4 = a 22 (b 21 b 11 ), x 5 = (a 11 + a 12 )b 22, x 6 = (a 21 a 11 )(b 11 + b 12 ), x 7 = (a 12 a 22 )(b 21 + b 22 ). 于是,C 的各元素可以表示为 : c 11 = x 1 + x 4 x 5 + x 7, c 12 = x 3 + x 5, c 21 = x 2 + x 4, c 22 = x 1 + x 3 x 2 + x 6. 易知, 需要做 7 次乘法, To be continued 应用实例 : 列主元 Gauss 消去法求解线性方程组 To be continued 上机练习 练习 5.1 均值与标准差练习 5.2 统计数字出现次数练习 5.3 反转数组练习 5.4 矩阵乘积练习 5.5 找最小值及其位置练习 5.6 有序数组中插入新元素练习 5.7 储物柜问题练习 5.8 硬币的状态矩阵 :9 枚硬币, 放入 3 3 的矩阵中,0 表示正面朝上,1 表示反面朝上 这 枚硬币的状态可用一个长度为 9 的二进制数表示, 比如 中的状态对应的二进制数为 总共可能有 512 种状态, 因此可由数字 0, 1, 2,..., 511 来表示所有状态 编写程序, 提示用户输入一个 0 至 511 之间的数字, 然后在屏幕上输出相应的状态矩阵 ( 即 3 3 的矩阵 ) void dec2binmatrix(int n, int A[M][M]) 练习 5.9 八皇后问题 : 将八个代表皇后的棋子放入 8 8 的棋盘中, 使得任何一个皇后都不会攻击到别的皇后, 即没有两个皇后在同一行 同一列和同一条对角线上 编写程序, 显示所有可能的

72 60 第五讲数组 解 用 1 表示皇后,0 表示空位, 比如下面就是一个解 : 练习 5.10 全排列问题 : 编写函数, 输出 1, 2,..., n 的全排列 (n 9), 并在主函数中以 n = 4 为例, 输出所有排列以及排列个数 void myperms(int a[], int m, int k) 参数 m, k 表示对数组第 m 至第 k 个位置上的元素进行全排列, 用递归实现 提示 : 依次将每个元素放到队列最前面, 然后对剩余元素进行全排列, 形成递归, 直到剩余元 素只有一个时为止, 此时就得到一个排列, 输出即可 以 n=3 为例 : (1) 将 1 放到最前面, 然后排列 2 3, 得到排列 :1 2 3;1 3 2 排完后再将 1 放回原来位置 ( 第 一步的描述是为了跟后面的描述保持一致性 ) (2) 将 2 放到最前面 ( 跟第一个元素交换 ), 然后排列 1 2, 得到排列 :2 1 3;2 3 1 然后将 2 放回原来位置 ( 即与刚才的交换再做一次 ) (3) 将 3 放到最前面 ( 跟第一个元素交换 ), 然后排列 2 1, 得到排列 :3 2 1;3 1 2 然后将 3 放回原来位置 ( 即与刚才的交换再做一次 )

73 第六讲指针与字符串数组 指针变量, 简称指针, 用来存放其它变量的内存地址 通过指针, 可以直接访问系统内存, 从而 提高程序执行效率 6.1 指针的定义与运算 指针的定义 类型标识符 * 指针变量名 (1) 类型标识符表示该指针可指向的对象的数据类型, 即该指针所代表的内存单元所存放的数据 的类型 指针的两个基本运算 (1) 提取变量的内存地址 :& 变量名 (2) 引用指针所指向的变量 :* 指针 1 int x; 2 int * px; // 声明指针 px 3 px = &x; // 将 x 的地址赋给指针 px 4 *px = 3; // 等价于 x = 3, 注意星号与 px 之间不能有空格! 此时, 我们通常称 px 是指向 x 的指针 Tips: 内存空间的访问方式 :1) 变量名 ; 2) 内存地址, 即指针 指针的初始化 : 声明指针变量时, 可以赋初值 1 int x; 2 int * px = &x; // 初始化 在使用指针时, 我们通常关心的是指针指向的元素! 指针赋值 (1) 指针的类型必须与其指向的对象的类型一致 (2) 给指针赋值时, 只能使用以下的值 - 空指针 :0,NULL 或值为 0/NULL 的常量 ; - 类型匹配的某个对象的地址 ; - 同类型的另一个有效指针 ; - 类型匹配的对象的下一个地址 ( 相对位置 ) 61

74 62 第六讲指针与字符串数组 没有初始化或赋值的指针是无效的指针, 引用无效指针会带来难以预料的后果 void 类型的指针 void * 指针名 (1) void 类型的指针可以存储任何类型的对象的地址 ; (2) 不允许直接使用 void 指针操纵它所指向的对象 ; (3) 必须通过显式类型转换, 才可以访问 void 类型指针所指向的对象 1 int x; 2 int * px; 3 void * pv; 4 pv = &x; // OK, void 型指针指向整型变量 5 px = (int *)pv; // OK, 使用 void 型指针时需要强制类型转换 指向常量的指针 const 类型标识符 * 指针名 (1) 指向常量的指针必须用 const 声明 ; (2) 这里的 const 限定了指针所指对象的属性, 不是指针本身的属性 ; (3) 允许把非 const 对象的地址赋给指向常量的指针, 即指向常量的指针也可以指向普通变量 ; (4) 但不允许使用指向常量的指针来修改它所指向的对象的值, 即使它所指向的对象不是常量 1 const int a = 3; 2 int b = 5; 3 const int * cpa = &a; // OK 4 *cpa = 5; // ERROR 5 cpa = &b; // OK 6 *cpa = 9; // ERROR 7 b = 9; // OK 常量指针, 简称常指针 : 指针本身的值不能修改 类型标识符 * const 指针名 1 int a = 3, b = 5; 2 int * const pa = &a; // OK 3 pa = &b; // ERROR 指向常量的常指针 const 类型标识符 * const 指针名 (1) 指针本身的值不能修改, 也不能通过它修改其指向的对象的值

75 6.2 指针与一维数组 63 指针算术运算 (1) 指针可以和整数或整型变量进行加减运算, 运算规则与指针的类型有关 ; (2) 在指针上加上或减去一个整型数值 k, 等效于获得一个新指针, 该新指针指向原来的元素之 后或之前的第 k 个元素 ; (3) 一个指针可以加上或减去 0, 其值不变 ; 指针数组 : 由指针变量组成的数组 (1) 指针数组的声明 : 类型标识符 * 指针数组名 [n] 6.2 指针与一维数组 在 C++ 中, 指针与数组密切相关 : 由于数组元素在内存中是连续存放的, 因此使用指针可以非常 方便地处理数组元素 引用数组元素的四种方式 (1) 数组名与下标 ; (2) 数组名与指针运算 ; (3) 指针与指针运算 ; (4) 指针与数组运算 例 6.1 指针与一维数组 : 引用数组元素的四种方式 1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 int main() 7 { 8 const int n = 5; 9 int a[n] = {0,2,4,6,8}; // 第一种方式 : 数组名与下标 12 cout << " 第一种方式 : 数组名与下标 :\n" ; 13 for (int i=0; i<n; i++) 14 cout << a[i] << ","; 15 cout << "\n\n" ; // 第二种方式 : 数组名与指针运算 18 cout << " 第二种方式 : 数组名与指针运算 :\n" ; 19 for (int i=0; i<n; i++) 20 cout << *(a+i) << ","; 21 cout << "\n\n" ; // 第三种方式 : 指针与指针运算 24 cout << " 第三种方式 : 指针 :\n" ; 25 for (int *pa=a; pa<a+n; pa++) 26 cout << *pa << ",";

76 64 第六讲指针与字符串数组 27 cout << "\n\n" ; // 第三种方式 : 指针与数组运算 30 cout << " 第三种方式 : 指针 ( 二 ):\n" ; 31 for (int *pa=a, i=0; i<n; i++) 32 cout << pa[i] << "," ; 33 cout << "\n\n" ; return 0; 36 } 数组名存放的是数组的首地址, 因此当数组名出现在表达式中时, 等效于一个常量指针 1 int a[]={0,2,4,8}; 2 int * pa = a; 3 *pa = 1; // 等价于 a[0]=1 4 *(pa+2) = 5; // 等价于 a[2]=5 5 *(a+2) = 5; // OK, 等价于 a[2]=5 6 *(pa++) = 3; // OK, 等价于 a[0]=3; pa = pa+1; 7 *(a++) = 3; // ERROR! a 代表数组首地址, 是常量指针! 8 *(pa+1) = 10; // 思考 : 修改了哪个元素的值? 小结 (1) 一维数组名 a 是地址常量, 数组名 a 与 &a[0] 等价 ; (2) a+i 是 a[i] 的地址,a[i] 与 *(a+i) 等价 ; (3) 若指针 pa 存储的是数组 a 的首地址, 则 *(pa+i) 与 pa[i] 等价 ; (4) 数组元素的下标访问方式也是按地址进行的 ; (5) 指针的值可以随时改变, 即可以指向不同的元素, 通过指针访问数组的元素更加灵活 ; (6) 数组名等效于常量指针, 值不能改变 ; (7) pa++ 或 ++pa 合法, 但 a++ 不合法 ; a[i] <=> pa[i] <=> *(pa+i) <=> *(a+i) 6.3 指针与二维数组 在 C++ 中, 二维数组是按行存储的, 可以理解为由一维数组组成的数组

77 6.3 指针与二维数组 65 引用二维数组的元素可以通过数组名和指针运算进行 ; 对于二维数组 A, 虽然 A A[0] 都是数组首地址, 但二者指向的对象不同 : (1) A[0] 是一维数组名, 它指向的是行数组 A[0] 的首元素, 即 *A[0] 与 A[0][0] 等价 ; (2) A 是二维数组名, 它指向的是它的首元素, 而它的元素都是一维数组 ( 即行数组 ), 因此 *A 与 A[0] 等价 另外, 它的指针移动单位是 行, 所以 A+i 对应的是第 i 个行数组, 即 A[i] 1 int A[2][3]={{1,2,3},{7,8,9}}; 2 int * p = A[0]; // OK, p 指向 A[0][0] 3 int * p = A; // ERROR!p 只能指向一个具体的整型变量, 不能是向量 指针与二维数组 : 设指针 pa=&a[0][0], 则 A[i][j] <=> *(pa+n*i+j) // 这里假定 A 的列数为 n 例 6.2 指针与二维数组举例 1 #include <iostream> 2 #include <iomanip> 3 4 using namespace std; 5 6 const int n = 5; 7 8 int main() 9 { 10 int A[n][n]; 11 int i, j; for(i=0; i<n; i++) 14 for(j=0; j<n; j++) 15 A[i][j] = i+j; cout << " 使用数组名 :\n"; 18 for(i=0; i<n; i++)

78 66 第六讲指针与字符串数组 19 { 20 for(j=0; j<n; j++) 21 cout << setw(3) << A[i][j]; 22 cout << endl; 23 } cout << " 使用指针 :\n" ; 26 int *pa = &A[0][0]; 27 for(i=0; i<n; i++) 28 { 29 for(j=0; j<n; j++) 30 cout << setw(3) << *(pa+n*i+j); 31 cout << endl; 32 } cout << endl; return 0; 37 } 6.4 指针与引用 指针与引用的区别 : (1) 引用是变量的别名, 必须初始化, 且不能修改 ; (2) 引用只针对变量, 函数没有引用 ; (3) 引用能实现的功能, 用指针都能实现 ; (4) 传递大量数据时, 建议使用指针 1 int a = 3; 2 int * pa = &a; // 指针 3 int & ra = a; // 引用 引用作为函数参数的优点 : (1) 传递方式与指针类似, 但可读性强 ; (2) 函数调用简单 安全 6.5 指针与函数 指针作为函数参数 : (1) 指针作为函数参数时, 以地址方式传递数据 ; (2) 形参是指针时, 实参可以是同类型指针或地址 ; (3) 可以传递函数代码的首地址 ( 函数指针 ) 当函数间需要传递大量数据时, 开销会很大 此时, 如果数据是连续存放的, 则可以只传递数据的首地址, 这样就可以减小开销, 提高执行效率!

79 6.5 指针与函数 67 Tips: 如果在被调函数中不需要改变指针所指向的对象的值, 则可以将形参中的指针声明为 指向常量的指针 指针型函数 : 函数的返回值是地址或指针, 一般形式如下 : 数据类型 * 函数名 ( 形参列表 ) { } 函数体 指向函数的指针, 即函数指针 (1) 在程序运行过程中, 不仅数据要占用内存空间, 函数也要在内存中占用一定的空间 ; (2) 函数名就代表函数在内存空间中的首地址 ; (3) 用来存放这个地址的指针就是指向该函数的指针 ; (4) 函数指针的定义 : 数据类型 (* 函数指针名 )( 形参列表 ) (5) 这里的数据类型和形参列表应与其指向的函数相同 ; (6) 函数名除了表示函数的首地址外, 还包括函数的形参, 返回值类型等信息 ; (7) 可以象使用函数名一样使用函数指针 例 6.3 函数指针举例 1 #include <iostream> 2 #include <cmath> 3 #include <iomanip> 4 5 using namespace std; 6 7 int Gcd(int x, int y) // 最大公约数 8 { 9 int z = x; 10 if (x > y) z = y; // 取 x 和 y 中的最小值 11 for (int i=z; i>=1; i--) 12 if (x%i==0 && y%i==0) return i; 13 } int Lcm(int x, int y) // 最小公倍数 16 { 17 for (int i=1; i<=x; i++) 18 if ( i*y % x == 0) return i*y; 19 } int main() 22 { 23 int a, b; int (* pf)(int, int); // 声明函数指针 26

80 68 第六讲指针与字符串数组 27 cout << "Input a and b: "; 28 cin >> a >> b; pf = Gcd; // pf 指向函数 Gcd 31 cout << " 最大公约数 :" << pf(a,b) << endl; pf = Lcm; // pf 指向函数 Lcm 34 cout << " 最小公倍数 :" << pf(a,b) << endl; return 0; 37 } 6.6 持久动态内存分配 若在程序运行之前, 不能够确切知道数组中元素的个数, 如果声明为很大的数组, 则可能造成浪 费, 如果声明为小数组, 则可能不够用 此时需要动态分配空间, 做到按需分配 每个程序在执行时都会占用一块可用的内存, 用于存放动态分配的对象, 此内存空间称为自由存 储区 (free store) 或堆 (heap). 申请单个存储单元 px = new 数据类型 ; px = new 数据类型 ( 初始值 ); (1) 申请用于存放指定数据类型数据的内存空间 ; (2) 若申请成功, 则返回该内存空间的首地址, 并赋给指针 px; (3) 若申请不成功, 则返回 0 或 NULL 释放由 new 申请的存储单元 delete px; (1) px 必须是由 new 操作的返回值 创建一维动态数组 px = new 数据类型 [ 数组长度 ]; px = new 数据类型 [ 数组长度 ](); // 全部赋初值 0 px = new 数据类型 [ 数组长度 ]{...}; // 初值非零,C++11 新标准 (1) 上面最后一行用初始化列表赋初值是 C++11 标准加入的新功能, 之前的标准不支持 动态数组的释放 delete[] px; 例 6.4 创建一维动态数组 1 #include <iostream> 2 #include <cmath> 3

81 6.6 持久动态内存分配 69 4 using namespace std; 5 6 int main() 7 { 8 int N=5; 9 10 int* pa = new int[n](); 11 int* pb = new int[n]{1,2,3,4,5}; // 初始化列表, C++11 新标准 for(int i=0; i<n; i++) 14 cout << *(pa+i) << " "; 15 cout << endl << endl; for(int i=0; i<n; i++) 18 cout << *(pb+i) << " "; 19 cout << endl; delete[] pa; 22 delete[] pb; return 0; 25 } 创建和释放多维动态数组 px = new 数据类型数据类型 [n1][n2]...[nm]; delete[] px; 例 6.5 动态数组 : 给定一个正整数 N, 寻找前 N 个素数, 并在屏幕上输出 1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 void findnprime(int *p, int N) // 寻找前 N 个素数 7 { 8 int n=2, k=0, flag, i; 9 while (k<n) 10 { 11 flag=0; 12 for(i=0; i<k && p[i]<=sqrt(n); i++) // 只需验证是否存在素数因子 13 if (n % p[i] == 0) {flag = 1; break;} if (flag==0) { p[k]=n; k++; } 16 n = n + 1; 17 } 18 } int main() 21 { 22 int N; 23 cout << "Input N: "; 24 cin >> N;

82 70 第六讲指针与字符串数组 int * pa = new int[n]; findnprime(pa, N); cout << " 最小的 " << N << " 个素数为 :\n"; 31 for(int i=0; i<n; i++) 32 cout << *(pa+i) << " "; cout << endl << endl; 35 delete[] pa; return 0; 38 } 6.7 字符串 ( 字符数组 ) 本节主要介绍 C 语言中字符串的实现与运用, 在 C++ 中同样适用 字符串 : 在 C 语言中, 字符串是通过字符数组来实现的 (1) 字符串以 \0 为结束标志 ( 称为字符串结束标志符 ); (2) 使用双引号表示的字符串常量进行初始化时, 会自动添加结束标志符 1 char str[5]={'m','a','t','h','\0'}; // OK, 只能用于初始化 2 char str[5]="math"; // OK, 只能用于初始化 3 char str[]="math"; // OK, 只能用于初始化 字符串的输出, 有两种方式 : (1) 利用循环逐个输出 ; (2) 利用字符串的特殊性, 整体输出 1 char str[20]="c++ and Matlab"; 2 for(int i=0; i<20; i++) // 逐个输出 3 if (str[i]!='\0') 4 cout << str[i]; 5 else 6 break; 1 char str[20]="c++ and Matlab"; 2 cout << str << endl; // 整体输出 输出字符串中不含字符串结束标志符 \0 字符串的输入 cin >> str; // 输入单个字符串, 中间不能有空格 cin.getline(str,n, 结束符 ); // 整行输入

83 6.7 字符串 ( 字符数组 ) 71 (1) cin.getline 连续输入多个字符 ( 可以有空格 ) 直到读入 N-1 个字符为止, 或遇到指定 的结束符 (2) 不存储结束符, 结束符可以省略, 缺省为 '\n' ( 换行符 ) 单个字符的输入 ch=getchar(); // ch 为字符变量 字符串相关函数 ( 头文件 cstring 和 cstdlib) 函数 strlen(str) strcat(dest,src) strcpy(dest,src) strcmp(str1,str2) atoi(str) atol(str) atof(str) itoa(int,str,raidx) 含义求字符串长度字符串连接字符串复制字符串比较将字符串转换为整数将字符串转换为 long 将字符串转换为 double 将整数转换为字符串 这些函数只能作用在字符串上, 不能作用在字符上 C++ 字符检测函数 ( 头文件 cctype) 函数 含义 示例 isdigit 是否为数字 isdigit('3') isalpha 是否为字母 isalpha('a') isalnum 是否为字母或数字 isalnum('c') islower 是否为小写 islower('b') isupper 是否为大写 isupper('b') isspace 是否为空格 isspace(' ') isprint 是否为可打印字符, 包含空格 isprint('a') isgraph 是否为可打印字符, 不含空格 isgraph('a') ispunct 除字母数字空格外的可打印字符 ispunct('*') iscntrl 是否为控制符 iscntrl('\n') tolower 将大写转换为小写 tolower('a') toupper 将小写转换为大写 toupper('a') 以上检测和转换函数只针对单个字符, 而不是字符串 字符与整数的运算

84 72 第六讲指针与字符串数组 (1) 字符参加算术运算时, 自动转换为整数 ( 按 ASCII 码转换 ) 6.8 上机练习练习 6.1 引用与指针作为函数参数练习 6.2 前 100 个素数, 用三种方式在屏幕上输出练习 6.3 矩阵乘积, 用指针实现练习 6.4 统计满足要求的数字个数练习 6.5 二进制转十进制, 用字符串实现练习 6.6 字符易位破译练习 6.7 围圈报数

85 第七讲简单输入输出 本讲主要内容 : C++ 基本输入输出操作 C 语言格式化输出 C 语言文件读写 7.1 C++ 基本输入输出 (I/O) 流 C++ 本身没有输入输出语句, 其输入输出是通过相应的 I/O 流类库实现的 数据流 : 将数据从一个对象到另一个对象的流动抽象为 流 (1) 提取 ( 读 ): 从流对象中获取数据, 运算符为» ; (2) 插入 ( 写 ): 向流对象中添加数据, 运算符为 «; (3) 提取和插入运算符是所有标准 C++ 数据类型预先设计的 ; (4) 插入运算符与操纵符一起使用, 可以控制输出格式 头文件 iostream 中预定义的四个输入输出对象 cin 标准输入 ( 键盘等 ) cout 标准输出 ( 屏幕 打印机等 ) cerr clog 标准错误输出, 没有缓冲, 立即被输出 与 cerr 类似, 但有缓冲, 缓冲区满时被输出 常用操纵符 ( 头文件 iomanip) 操作符 含义 endl 插入换行符, 并刷新流 ( 将缓冲区中的内容刷入输出设备 ) setw(n) 设置域宽, 若数据超过设置的宽度, 则显示全部值 cout.width(n) fixed 使用定点方式输出 scientific 使用指数形式输出 setfill(c) 设置填充,c 可以是任意字符, 缺省为空格, cout.fill(c) 如 setfill('*'), setfill('0') setprecision(n) 设置输出的有效数字个数, 若在 fixed 或 scientific 后使用, 则设置小数位数 left 左对齐 right 右对齐 ( 缺省方式 ) 73

86 74 第七讲简单输入输出 showpoint 显示小数点和尾随零 ( 即使没有小数部分 ) 除 setw 和 cout.width 外, 其它操纵符一直有效, 直到遇到相同类型的操纵符为止. 例 7.1 操纵符的使用 : 域宽和填充 1 #include <iostream> 2 #include <cstdlib> 3 #include <iomanip> 4 5 using namespace std; 6 7 int main() 8 { 9 int A[3][3]={{11,12,13},{21,22,23},{31,32,33}}; cout << " 使用 setw \n"; 12 for (int i=0; i<3; i++) 13 { 14 for (int j=0; j<3; j++) 15 cout << setw(4) << A[i][j]; // 设置输出域宽 16 cout << "\n"; 17 } 18 cout << endl; cout << " 使用 cout.width \n"; 21 cout << setfill('*'); // 设置填充符, 也可以用 cout.fill('*') for (int i=0; i<3; i++) 24 { 25 for (int j=0; j<3; j++) 26 { 27 cout.width(4); 28 cout << A[i][j]; // 设置输出域宽 29 } 30 cout << "\n"; 31 } 32 cout << endl; return 0; 35 } 例 7.2 操纵符的使用 : 小数输出形式和精度设置 1 #include <iostream> 2 #include <cstdlib> 3 #include <iomanip> 4 5 using namespace std; 6 7 int main() 8 {

87 7.2 C 语言格式化输出 double a[3]={ , , }; 11 cout << " 以定点格式输出 \n"; 12 cout << fixed; // 以定点格式输出, 缺省小数点后保留 6 位 13 for (int i=0; i<3; i++) 14 cout << a[i] << ", "; cout << endl << endl; 17 cout << " 以指数形式输出 \n"; 18 cout << scientific; // 以指数形式输出 19 cout << setprecision(4); // 小数点后保留 4 位 20 for (int i=0; i<3; i++) 21 cout << a[i] << ", "; cout << "\n" << endl; return 0; 26 } 7.2 C 语言格式化输出 printf(" 格式控制字符串 ", 输出变量列表 ); // 需加头文件 cstdio (1) 格式控制字符串 : 包括 普通字符串 格式字符串 转义字符 (2) 格式字符串 : 以 % 开头, 后面跟格式说明符和其它选项 %[flag][ 输出最小宽度 ][. 精度 ] 格式说明符 1 int k=5; 2 double a=3.14; 3 printf("k=%d, a=%f\n",k, a); // 普通字符串按原样输出 ; 一个格式字符串对应一个变量 常见的格式说明符 c 字符型 g 浮点数 ( 系统自动选择输出格式 ) d 十进制整数 o 八进制 e 浮点数 ( 科学计数法 ) s 字符串 f 浮点数 ( 小数形式 ) x/x 十六进制

88 76 第七讲简单输入输出 常见的转义字符 ( 输出特殊符号 ) \b 退后一格 \t 水平制表符 \f 换页 \\ 反斜杠 \n 换行 \" 双引号 \r 回车 %% 百分号 7.3 C 语言文件读写 文件读写基本步骤 : 打开文件 读取或写入 关闭文件 文件指针 :FILE *pf; 文件类型 - 按数据的组织形式划分 : 文件文件和二进制文件 文件打开 pf=fopen( 文件名, 打开方式 ); (1) 文件名 : 普通字符串 (2) 打开方式 : 指定读写方式和文件类型, 取值有 rt wt at rb wb ab rt+ wt+ at+ rb+ wb+ ab+ r 为读,w 为写,+ 为读写,t 为文本,b 为二进制 (3) 若文件打开成功, 返回指向文件的指针 ; 若打开失败, 则返回一个空指针 (NULL) 文件关闭 :fclose(pf); (1) 正常关闭返回值为 0; 出错时, 返回值为非 0 写文本文件 fprintf(pf, " 格式控制字符串 ", 输出变量列表 ); (1) fprintf 的用法与 printf 类似 例 7.3 C 语言文件读写 : 文本文件 1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <iomanip> 5 6 using namespace std; 7 8 int main() 9 { 10 FILE * pf; pf = fopen("out1.txt","wt");

89 7.3 C 语言文件读写 double pi= ; 15 fprintf("pi=%-12.6f\n", pi); // 在屏幕上输出 16 fprintf(pf,"pi=%-12.6f\n", pi); // 写入到文件中 fclose(pf); return 0; 21 } 读文本文件 fscanf(pf, " 格式控制字符串 ", 地址列表 ); 写二进制文件 fwrite(buffer, size,count,pf); 将 count 个长度为 size 的连续数据写入到 pf 指向的文件中,buffer 是这些数据的首地址 ( 可 以是指针或数组名 ) 读二进制文件 fread(buffer, size,count,pf); 从 pf 指向的文件中读取 count 个长度为 size 的连续数据,buffer 是存放这些数据的首地址 ( 可以是指针或数组名 ) 例 7.4 C 语言文件读写 : 二进制文件 1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <iomanip> 5 6 using namespace std; 7 8 int main() 9 { 10 int A[3][3]={{11,12,13},{21,22,23},{31,32,33}}; FILE * pf; pf = fopen("data1.dat","wb"); // 写文件 15 fwrite(a,sizeof(int),9, pf); // 也可以写为 fwrite(a,sizeof(a),1, pf); 16 fclose(pf); pf = fopen("data1.dat","rb"); // 读文件 19 int B[3][3]; 20 fread(b,sizeof(int),9, pf); 21 fclose(pf); cout << "A=\n"; 24 for (int i=0; i<3; i++) 25 {

90 78 第七讲简单输入输出 26 for (int j=0; j<3; j++) 27 cout << setw(4) << A[i][j]; 28 cout << "\n"; 29 } cout << "B=\n"; 32 for (int i=0; i<3; i++) 33 { 34 for (int j=0; j<3; j++) 35 cout << setw(4) << B[i][j]; 36 cout << "\n"; 37 } return 0; 40 } 7.4 上机练习练习 7.1 文本文件读写练习 7.2 二进制文件读写练习 7.3 计算一个正整数的所有数字之和 ( 循环和递归 ) 练习 7.4 多项式乘积运算练习 7.5 ( 可选题 ) Gauss 消去法解方程

91 第八讲排序算法及其 C++ 实现 排序是计算机内经常进行的一种操作, 其目的是将一组 无序 的数据排列成为 有序 的序列 排序算法就是如何实现排序的方法, 是计算机科学中非常重要的算法之一, 一个优秀的算法可以节省 大量的资源 8.1 引言 算法评价的重要指标 (1) 时间复杂度 ( 运算量 操作次数 ): 设有 n 个数据, 一般来说, 好的排序算法性能是 O(n log n), 差的性能是 O(n 2 ), 而理想的性能是 O(n) (2) 空间复杂度 : 算法在运行过程中临时占用存储空间的大小 稳定排序算法 : 相等的数据维持原有相对次序 表 8.1. 常见排序算法的复杂度 算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 选择排序 O(n 2 ) O(n 2 ) O(n 2 ) O(1) 不稳定 插入排序 O(n 2 ) O(n 2 ) O(n) O(1) 稳定 希尔排序 O(n log 2 n) O(n 2 ) O(n log n) O(1) 不稳定 冒泡排序 O(n 2 ) O(n 2 ) O(n) O(1) 稳定 快速排序 O(n log n) O(n 2 ) O(n log n) O(n log n) 不稳定 堆排序 O(n log n) O(n log n) O(n log n) O(1) 不稳定 归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定 图书馆排序 O(n log n) O(n 2 ) O(n log n) O(n) 稳定 基数排序 O(n k) O(n k) O(n k) O(n + k) 稳定 桶排序 O(n + k) O(n 2 ) O(n) O(n + k) 稳定 计数排序 O(n + k) O(n + k) O(n + k) O(n + k) 稳定 本讲主要介绍以下几类排序算法 : 选择排序, 插入排序, 希尔排序, 冒泡排序, 快速排序 79

92 80 第八讲排序算法及其 C++ 实现 本讲中假定是对数据进行从小到大排序 8.2 选择排序 选择排序也称最小排序, 基本思想是 : 找出最小值, 将其与第一个位置的元素进行交换, 然后对 剩余的序列重复以上过程, 直至排序结束 例 8.1 选择排序 1 #include <iostream> 2 #include <cstdlib> 3 #include <iomanip> 4 #include <cstdio> 5 6 using namespace std; 7 8 int findmin(int * px, int n) // 找出最小值所在的位置 9 { 10 int idx=0, xmin=*px; 11 for (int i=1; i<n; i++) 12 if (*(px+i)<xmin) 13 { xmin = *(px+i); idx=i; } 14 return idx; 15 } void sort_min(int * px, int n) // 选择排序 18 { 19 int idx, t; 20 for(int k=0; k<n-1; k++) 21 { 22 idx = findmin(px+k,n-k); // 找出待排序部分的最小值及其所在位置 23 if (idx!=0) 24 { t=px[k]; px[k]=px[k+idx]; px[k+idx]=t; } // 交换 25 } 26 } int main() 29 { 30 int x[]={2, 8, 3, 12, 5, 20, 7, 14, 5, 16}; 31 int n, i; n = sizeof(x)/sizeof(x[0]); // 获取数据个数 cout << "x=\n"; // 输出原始数据 36 for(i=0;i<n;i++) cout << setw(3) << x[i]; 37 cout << endl << endl; sort_min(x, n); // 排序 cout << " 排序后 :\n"; // 输出排序后结果 42 for(i=0;i<n;i++) cout << setw(3) << x[i]; 43 cout << endl << endl; 44

93 8.3 插入排序 return 0; 46 } 8.3 插入排序 插入排序的基本思想 (1) 假设前面 k 个元素已经按顺序排好了, 在排第 k + 1 个元素时, 将其插入到前面已排好的 k 个元素中, 使得插入后得到的 k + 1 个元素组成的序列仍按值有序 ; (2) 然后采用同样的方法排第 k + 2 个元素 ; (3) 以此类推, 直到排完序列的所有元素为止 关键点 (1) 如何将第 k + 1 个元素插入到前面的有序序列中? (2) 策略 : 依次与其左边的元素进行比较, 直至遇见第一个不大于它的元素为止 优化 : 可以将比较与移位同时进行 例 8.2 插入排序的 MATLAB 实现 1 function x = Sort_Insert(x,n) 2 for k = 1 : n-1 3 key = x(k+1); % 需要插入的元素 4 i = k; 5 while (i > 0 && x(i) > key) 6 x(i+1) = x(i); % 将前面 k 个元素中大于 x(k+1) 的数据向后移动 7 i = i - 1; 8 end 9 x(i+1) = key; % 将当前元素插入合适的位置 10 end 8.4 希尔排序希尔排序又称为 缩小增量排序 (Diminishing Increment Sort), 由 D. Shell 于 1959 年提出, 是对插入排序的改进 基本过程 (1) 把序列按照某个增量 (gap) 分成几个子序列, 对这几个子序列进行插入排序 ; (2) 不断缩小增量, 扩大每个子序列的元素数量, 并对每个子序列进行插入排序 ; (3) 当增量为 1 时, 子序列就是整个序列, 而此时序列已经基本有序了, 因此只需做少量的比较和移动就可以完成对整个序列的排序 出发点 : 插入排序在元素基本有序的情况下, 效率很高 增量 (gap) 的选取 : 初始值可设为 n/2, 然后不断减半 例 8.3 希尔排序的 MATLAB 实现 1 function x = Sort_Shell(x,n) 2 gap = floor(n/2); % 增量从数组长度的一半开始, 每次减小一倍

94 82 第八讲排序算法及其 C++ 实现 3 while gap > 0 4 for k = gap + 1 : n 5 key = x(k); % 需要插入的元素 6 i = k-gap; % 对一组增量为 step 的元素进行插入排序 7 while ( i > 0 && x(i) > key) 8 x(i+gap) = x(i); 9 i = i - gap; 10 end 11 x(i+gap) = key; % 将当前元素插入合适的位置 12 end 13 gap = floor(gap/2); 14 end 8.5 冒泡排序 基本过程描述如下 : (1) 走访需要排序的序列, 比较相邻的两个元素, 如果他们的顺序错误就把他们交换过来 (2) 不断重复上述过程, 直到没有元素需要交换, 排序结束 (3) 这个算法的名字由来是因为越大的元素会经由交换慢慢 浮 到数列的顶端 具体过程 (1) 将第 1 个和第 2 个元素进行比较, 如果前者大于后者, 则交换两者的位置, 否则位置不变 ; (2) 然后将第 2 个元素与第 3 个元素进行比较, 如果前者大于后者, 则交换两者的位置, 否则位 置不变 ; (3) 依此类推, 直到最后两个元素比较完毕为止 这就是第一轮冒泡过程, 这个过程结束后, 最 大的元素就 浮 到了最后一个位置上 (4) 对前面 n 1 个元素进行第二轮冒泡排序, 结束后, 这 n 1 个元素中的最大值就被安放在了 第 n-1 个位置上 (5) 对前面的 n 2 个元素进行第三轮冒泡排序 (6) 以此类推, 当执行完第 n 1 轮冒泡过程后, 排序结束 冒泡排序的优化 如果在某轮冒泡过程中没有发生元素交换, 这说明整个序列已经排好序了, 这时就不用再进行后 面的冒泡过程, 可以直接结束程序 冒泡排序的进一步优化 假设有 100 个数的数组, 仅前面 10 个无序, 后面 90 个都已排好序且都大于前面 10 个数字, 那 么在第一轮冒泡过程后, 最后发生交换的位置必定小于 10, 且这个位置之后的数据必定已经有序 了, 记录下这位置, 第二次只要从数组头部遍历到这个位置就可以了 例 8.4 冒泡排序的 MATLAB 实现 1 function x = Sort_Bubble(x,n) 2 for k = 1 : n 3 flag = 0; % 用于记录是否有需要交换的元素 4 for i = 1 : n-k 5 if x(i) > x(i+1) 6 flag = 1;

95 8.6 快速排序 83 7 t = x(i); x(i) = x(i+1); x(i+1) = t; 8 end 9 end 10 if flag==0 % 如果这次遍历没有元素需要交换, 那么排序结束 11 break; 12 end 13 end 8.6 快速排序 快速排序是目前最常用的排序算法之一, 它采用的是分而治之思想 : 将原问题分解为若干个规模更小但结构与原问题相似的子问题, 然后递归求解这些子问题, 最后将这些子问题的解组合为原问题的解 具体实现过程 : (1) 随机选定其中一个元素作为基准数 (pivot)( 通常可采用第一个元素 ), 然后通过循环和比较运算, 将原序列分割成两部分, 使得新序列中在该基准数前面的元素都小于等于这个元素, 而其后面的元素都大于等于这个元素 ( 这时基准数已经归位 ) (2) 依此类推, 再对这两个分割好的子序列进行上述过程, 直到排序结束 ( 递归思想, 分而治之 ) 第一步的具体实现 :( 假定基准数的值为 a, 原始位置是 i 1 = 1) (1) 先从原序列的最右边开始, 往左找出第一个小于 a 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 2 ; (2) 从 i 1 右边的位置开始, 往右找出第一个大于 a 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 3 ; (3) 从 i 2 左边的位置开始, 往左找出第一个小于 a 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 4 ; (4) 从 i 3 右边的位置开始, 往右找出第一个大于 a 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 5 ; (5) 不断重复以上过程, 遍历整个序列 事实上, 可以不用交换, 而是先把基准数保留, 然后直接覆盖即可 后面步骤 : (1) 对基准数所在位置前面的子序列和后面的子序列, 分别重复第一步的过程 (2) 不断重复以上过程, 通过递归实现排序 快速排序还有很多改进版本, 如随机选择基准数, 区间内数据较少时直接用其它的方法排序以减小递归深度等等 有兴趣的同学可以深入研究 例 8.5 快速排序的 MATLAB 实现 1 function sort_quick(left,right) 2 global x

96 84 第八讲排序算法及其 C++ 实现 3 4 if left < right 5 mid = partition(left, right); 6 sort_quick(left, mid-1); 7 sort_quick(mid+1, right); 8 end 9 10 function left = partition(left, right) 11 global x pivot = x(left); % 采用子序列的第一个元素为中间元素 14 while (left < right) 15 % 从后往前, 在后半部分中寻找第一个小于中间元素的元素 16 while left<right && x(right) >= pivot 17 right = right - 1; 18 end 19 % 将这个比中间元素小的元素移到前半部分 20 if (left < right) 21 x(left) = x(right); left = left + 1; 22 end % 从前往后在前半部分中寻找第一个大于中间元素的元素 25 while left<right && x(left) < pivot 26 left = left + 1; 27 end 28 % 将这个比中间元素大的元素移到后半部分 29 if (left < right) 30 x(right) = x(left); right = right - 1; 31 end 32 end 33 x(left) = pivot; 8.7 上机练习练习 8.1 插入排序练习 8.2 希尔排序练习 8.3 冒泡排序练习 8.4 快速排序

97 第九讲类与对象 I: 面向对象基础 9.1 为什么面向对象 出发点 : 更直观地描述客观世界中存在的事物 ( 对象 ) 以及它们之间的关系 目的 : 提高代码的可重用性, 降低软件的开发成本和维护成本, 从而大大提高程序员的生产力 面向对象基本特点 : (1) 将客观事物看作具有属性 ( 数据 ) 和行为 ( 函数 ) 的对象 ; (2) 通过抽象找出同一类对象的共同属性和行为, 形成类 ; (3) 通过类的继承与多态实现代码重用 面向对象的几个主要特征 : 抽象 封装 继承和多态 - 抽象 : 对具体问题 / 事物 ( 对象 ) 进行概括, 抽出这一类对象的公共性质并加以描述的过程 (1) 首先关注的是问题的本质及描述, 其次是实现过程或细节 ; (2) 抽象包括 : 数据抽象和行为抽象 : 数据抽象 : 描述某类对象的属性或状态 ( 对象相互区别的物理量 ); 行为抽象 ( 功能抽象 ): 描述某类对象的共同行为或功能特征 (3) 抽象的实现 : 类 (class) - 封装 : 将抽象得到的数据和行为 ( 或功能 ) 相结合, 形成一个有机的整体, 即将数据与操作数据的函数进行有机结合, 形成 类, 其中数据和函数都是类的成员 封装可以增强数据的安全性, 并简化编程 用户不必了解具体的实现细节, 而只需要通过外部接口, 依据给定的访问权限, 来访问类的成员 例 9.1 时钟的描述 数据抽象 :hour, minute, second 行为抽象 :ShowTime(), SetTime() 实现方法 : 时钟类 1 // 时钟类 2 class Clock 3 { 4 public: // 指定成员的访问权限 5 void SetTime(int h, int m, int s); 6 void ShowTime(); 7 8 private: // 指定成员的访问权限 9 int hour, minute, second; 10 }; // 此处的分号不能省略! - 继承 :C++ 提供了继承机制, 允许程序员在保持原有类的特性的基础上, 进行更具体 更详 85

98 86 第九讲类与对象 I: 面向对象基础 细的说明 - 多态 : 同一段程序作用在不同类型的对象上, 的能力 在 C++ 中, 多态性是通过强制多态 ( 如 类型转换 ) 重载多态 ( 如函数重载 运算符重载 ) 类型参数化和虚函数 模板等 9.2 类和对象基本操作 类是 C++ 面向对象程序设计的核心! 类与函数的区别 : (1) 函数是结构化 ( 过程式 ) 程序设计的基本模块, 用于完成特定的功能 (2) 类是面向对象程序设计的基本模块, 类将逻辑上相关的数据与函数封装, 是对问题的抽象描述 类的集成程度更高, 更适合大型复杂程序的开发 类的声明 : 类必须先声明后使用 class 类名 { }; public: // 公有 公有成员 ( 外部接口 ) private: // 私有 私有成员 protected: // 保护 保护型成员 类的成员 : (1) 数据成员 : 描述事物的属性 (2) 函数成员 : 描述事物的行为 / 功能 / 操作 成员的访问属性 ( 访问权限控制 ) (1) public( 公有 外部接口 ): 任何外部函数都可以访问公有类型的数据和函数 (2) private( 私有 ): 只能被本类中的函数成员访问, 任何来自外部的访问都非法 (3) protected( 保护 ): 与私有类似, 区别在于继承过程中的影响不同, 将在后面章节中详细解释 如果没有指定访问属性, 则缺省是 private 一般情况下, 建议将数据成员声明为私有或保护 一个类如果没有任何外部接口, 则无法使用 在定义类时, 不同访问属性的成员可以按任意顺序出现, 修饰访问权限的关键字也可以多次出现, 但一个成员只能有一种访问属性 1 // 不同访问属性的成员可以按任意顺序出现

99 9.2 类和对象基本操作 87 2 class Clock 3 { 4 public: 5 void SetTime(int h, int m, int s); 6 private: 7 int hour, minute, second; 8 public: 9 void ShowTime(); 10 }; 一般将公有类型的成员放在最前面, 便于阅读 ; 在类中可以只声明函数原型, 函数的具体实现可以在类外部定义 ; 声明一个类时, 并没有为这个类分配内存, 而只是告诉编译器这个类是什么, 即包含哪些数据, 有什么功能 对象的创建 : 声明一个类后, 便可将其作为新的数据类型来创建变量, 即对象 类名对象名 1 Clock x; // 声明对象 2 Clock y, z; (1) 类与对象的关系类似于基本数据类型与普通变量之间的关系 (2) 对象是类的实例, 即具有该类型的变量, 因此声明对象的过程也称为类的实例化 (3) 对象所占的内存空间只用于存放数据成员 (4) 函数成员在内存中只占一份空间, 不会在每个对象中存储副本 (5) 同一个类的不同对象之间的主要区别 : 名称与数据 对象成员的访问 :. 操作符 对象名. 数据成员名 对象名. 函数成员名 ( 参数列表 ) 1 Clock myclock; // 声明对象 myclock 2 3 myclock.showtime(); // 显示时间 4 myclock.settime(16,10,28); // 设置时间 (1) 类的成员函数可以访问所有数据成员 ; (2) 外部函数只能访问公有成员 成员函数的定义 (1) 可以在类内部声明的时候直接定义 ( 一般适合简短函数 ), 如 : 1 class Clock // 时钟类的声明 2 {

100 88 第九讲类与对象 I: 面向对象基础 3 public: // 外部接口, 公有成员函数 4 void SetTime(int h, int m, int s) 5 { hour = h; minute = m; second = s; } 6 void ShowTime() 7 { cout << hour << ":" << minute << ":" << second << endl; } 8 9 private: // 私有数据成员 10 int hour, minute, second; 11 }; (2) 也可以在类内部声明, 然后在类外部定义 ( 适用复杂函数 ), 如 : 1 class Clock // 时钟类的声明 2 { 3 public: // 外部接口, 公有成员函数 4 void settime(int h, int m, int s); 5 void ShowTime(); 6 7 private: // 私有数据成员 8 int hour, minute, second; 9 }; // 在类外部定义成员函数 12 void Clock::setTime(int h, int m, int s) 13 { 14 hour = h; minute = m; second = s; 15 } // 在类外部定义成员函数 18 void Clock::ShowTime() 19 { 20 cout << hour << ":" << minute << ":" << second << endl; 21 } 在类外部定义成员函数时的一般形式是 : 数据类型类名 :: 函数名 ( 形参列表 ) { } 函数体 ; - 与普通函数的区别 : 前面要加上类的名称和两个连续冒号 ( 作用域分辨符 ) 简单成员函数建议直接在类内部定义, 此时函数名前面不需要加类名 ::, 而复杂函数 建议在类内部声明, 然后在类外部定义

101 9.2 类和对象基本操作 89 目的对象 / 目标对象 (1) 调用成员函数时, 需用. 操作符指定本次调用所针对的对象 ; (2) 该对象就是本次调用的 目的对象 ; (3) 在成员函数中, 可以直接引用目的对象的所有数据成员, 而无需使用. 操作符 ; (4) 在成员函数中, 引用其它对象的数据成员和函数成员时, 必须使用. 操作符 ; (5) 在类的成员函数中, 可以直接访问当前类的所有对象的私有成员 形参可以带缺省值 (1) 与普通函数一样, 成员函数的形参也可以带缺省值 ; (2) 成员函数的形参缺省值只能在类中声明或定义时设置, 不能在类外部定义函数时设置 1 // 举例 : 形参可以带缺省值 2 class Clock 3 { 4 public: 5 void SetTime(int h=0, int m=0, int s=0); }; 内联成员函数 (1) 成员函数可以是内联函数, 声明内联成员函数有两种方式 : 隐式方式和显式方式 - 隐式方式 : 在类中直接定义的成员函数是内联成员函数 ; - 显式方式 : 在类外部定义成员函数时, 使用关键字 inline (2) 使用内联函数可以减少调用开销, 提高效率, 但只适合简单的函数 ( 短函数 ) 1 class Clock 2 { 3 public: 4 void ShowTime(); }; 7 8 inline void Clock::ShowTime() // 内联函数 9 { cout << hour << : << minute << : << second << endl; } 例 9.2 类与对象 : 时钟类 1 // 时钟类 2 #include <iostream> 3 #include <cstdlib> 4 5 using namespace std; 6 7 class Clock // 时钟类的声明 8 { 9 public: // 外部接口, 公有成员函数

102 90 第九讲类与对象 I: 面向对象基础 10 void SetTime(int h=0, int m=0, int s=0); 11 void ShowTime(); private: // 私有数据成员 14 int hour, minute, second; 15 }; void Clock::SetTime(int h, int m, int s) 18 { hour = h; minute = m; second = s; } void Clock::ShowTime() 21 { 22 cout << hour << ":" << minute << ":" << second << endl; 23 } int main() // 主函数 26 { 27 Clock myclock; // 定义对象 myclock cout << "First time: " << endl; 30 myclock.settime(); // 用形参缺省值设置时间 31 myclock.showtime(); // 显示时间 cout << "Second time: " << endl; 34 myclock.settime(16,10,28); // 设置时间为 16:10:28 35 myclock.showtime(); // 显示时间 return 0; 38 } 9.3 构造函数 对象的初始化 : 创建对象时, 设置数据成员的值 构造函数 : 负责对象的初始化, 即创建对象时, 对其数据成员进行初始化 对象创建的过程 : (1) 申请内存空间 ( 用于存放数据成员 ); (2) 初始化 : 自动调用构造函数初始化数据成员 构造函数几点说明 : (1) 构造函数的函数名与类的名称相同 ; (2) 构造函数没有返回值, 前面也不需要带任何返回数据类型 ; (3) 构造函数在对象创建时会被系统自动调用 ; (4) 缺省构造函数 : 若用户没有定义构造函数, 则系统会自动生成构造函数, 形参和函数体都为空 ( 如 Clock() { }), 但如果用户自己定义了构造函数, 则系统不再提供缺省构造函数 ; (5) 构造函数可以是内联函数, 形参可以带缺省值 ; (6) 使用不带参数的构造函数初始化对象时不需要加小括号 构造函数可以重载, 即可定义多个构造函数

103 9.3 构造函数 91 例 9.3 类与对象 : 构造函数 1 // 构造函数 2 #include <iostream> 3 #include <cstdlib> 4 5 using namespace std; 6 7 class Clock 8 { 9 public: 10 Clock(); // 不带形参的构造函数 11 Clock(int x, int y, int z); // 带三个形参的构造函数 12 void ShowTime(); private: 15 int hour, minute, second; 16 }; // 不带形参的构造函数 19 Clock::Clock() 20 { hour=0; minute=0; second=0; } // 带三个形参的构造函数 23 Clock::Clock(int x, int y, int z) 24 { hour=x; minute=y; second=z; } inline void Clock::ShowTime() 28 { cout << hour << ":" << minute << ":" << second << endl; } int main() // 主函数 32 { 33 Clock c1; // 调用不带形参的构造函数初始化 c1 34 Clock c2(16,12, 25); // 调用带形参的构造函数初始化 c cout << "c1: "; c1.showtime(); 37 cout << "c2: "; c2.showtime(); 38 cout << endl; return 0; 41 } 调用不带形参的构造函数初始化对象时, 不要加小括号 ; 如果构造函数的形参都带有缺省值, 且在初始化对象时都采用缺省值, 则此时也不要加小 括号, 如 : 1 class Clock 2 { 3 public: 4 Clock(int x=10, int y=10, int z=10); // 形参带缺省值 };

104 92 第九讲类与对象 I: 面向对象基础 int main() 11 { 12 Clock c1; // OK 13 Clock c2(); // ERROR, 全部使用缺省值时不要加小括号! } 9.4 复制构造函数 复制构造函数 : 是一类特殊的构造函数, 其作用是将已有对象的值复制给其它对象 复制构造函数的一般形式 : class 类名 { }; public: 类名 ( 类名 & 对象名 ); // 复制构造函数, 形参必须是对象的引用! 类名 :: 类名 ( 类名 & 对象名 ) // 复制构造函数的定义 { 函数体 ; } (1) 复制构造函数的形参必须是对象的引用, 因此不能被重载 ; (2) 复制构造函数也可以在类内部声明时直接定义 缺省复制构造函数 : 系统自动生成, 将已有对象的数据全部简单复制给指定对象, 即浅拷贝 (1) 不管是否存在用户自定义的复制构造函数, 缺省复制构造函数总是存在的, 这与构造函数不同 ; (2) 若不存在自定义复制构造函数, 则在所有用对象赋值的地方都调用缺省赋值构造函数 ; (3) 若存在用户自己定义的复制构造函数, 则在以下几种情况下会调用自定义复制构造函数 : - 用一个对象去初始化另一个同类的对象时 ( 注意是初始化, 不是赋值 ) - 若函数的形参是对象, 调用函数时形参与实参的结合 ( 值传递 ) (4) 自定义复制构造函数不影响赋值号 ( 初始化除外 ) 的行为, 即将一个对象赋给另一个对象时, 调用的是缺省复制构造函数 缺省复制构造函数只能实现浅拷贝, 即将已有对象的数据成员的值简单复制给另外一个对象的数据成员, 有时这种复制满足不了实际需求 比如对象 A 中有两个数据成员 x 和 px, 其中 px 是指向 x 的指针, 则将 A 复制给另外一个对象 B 时,B 中的指针 px 所得到的值也是 A 中 x 的地址, 这显然不是我们想要的结果 ( 事实上, 我们希望 B 中的 px 应该指向 B 中 x, 而不是 A 中 x) 对象作为函数参数

105 9.4 复制构造函数 93 (1) 对象可以作为成员函数和非成员函数的参数 ; (2) 与普通变量一样, 对象实参与形参的传递方式有三种 : 值传递, 引用传递, 地址传递 ; (3) 为了提高程序执行效率, 一般情况下, 对象作为函数参数时, 很少使用值传递 例 9.4 类与对象 : 复制构造函数 1 // 复制构造函数 2 #include <iostream> 3 #include <cstdlib> 4 5 using namespace std; 6 7 class Point // Point 类的声明 8 { 9 public: // 外部接口 10 Point(int a=0, int b=0) // 构造函数 11 { x=a; y=b; } 12 Point(const Point &); // 复制构造函数, 常引用 ( 对象的常引用将在后面介绍 ) 13 int Getx() {return x;} private: // 私有数据 16 int x, y; 17 }; // 复制构造函数 20 Point::Point(const Point & p) 21 { 22 x=p.x; y=p.y; 23 cout << " 自定义复制构造函数被调用!" << endl; 24 } // 形参为 Point 类对象的函数 27 void f(point p) 28 { 29 cout << "x=" << p.getx() << endl; 30 } // 返回值为 Point 类对象的函数 33 Point g() 34 { 35 Point A(1,2); 36 return A; 37 } int main() // 主函数 40 { 41 Point A(4,5); // 第一个对象 A // 情况一 : 用 A 初始化 B, 调用自定义复制构造函数 44 cout << "Point B(A): "; 45 Point B(A); // 或 Point B=A; 46 cout << "x=" << B.Getx() << endl << endl; // 情况二 : 对象 B 作为函数的实参, 调用自定义复制构造函数 49 cout << "f(b): ";

106 94 第九讲类与对象 I: 面向对象基础 50 f(b); 51 cout << endl; // 自定义的复制构造函数不改变赋值号的行为 54 cout << "C=A: "; 55 Point C; 56 C = A; // 赋值 : 调用缺省的复制构造函数 57 cout << "x=" << C.Getx() << endl << endl; cout << "C=g(): "; 60 C = g(); // 赋值 : 调用缺省的复制构造函数 61 cout << "x=" << C.Getx() << endl << endl; return 0; 64 } 函数调用时, 只有在进行值传递时, 复制构造函数才会被调用 若形参是引用或指针, 则 不会调用复制构造函数 9.5 匿名对象 在大多数情况下, 创建对象时都需要指定一个对象名, 但在有些情况下, 可能需要创建一个临时 对象, 只使用一次, 这时可以使用匿名对象 匿名对象的声明 : 类名 (); // 调用不带形参的构造函数 ( 或形参都带缺省值 ) 类名 ( 参数列表 ); // 调用带形参的构造函数 1 // 匿名对象举例 2 class Clock 3 { 4 public: 5 Clock(); // 构造函数 6 Clock(int x, int y, int z); // 构造函数重载 }; int main() 13 { 14 Clock c1, c2; 15 c1 = Clock(); // 使用不带参数的构造函数 16 c2 = Clock(16,16,16); // 使用带参数的构造函数 }

107 9.6 类与对象举例 : 游泳池 95 创建匿名对象时, 使用不带参数的构造函数或形参都使用缺省值时, 一定要带小括号! 9.6 类与对象举例 : 游泳池 例 9.5 一圆形游泳池如图所示, 现在需在其周围建一圆形过道, 并在其四周围上栅栏 栅栏造价为 35 元 / 米, 过道造价为 20 元 / 平方米, 过道宽度 3 米, 游泳池半径由键盘输入 编程计算并输出过道 和栅栏的造价 1 // 分析 : 可以定义一个名为 圆 的类 2 // 数据成员 : 半径 ; 函数成员 : 计算周长与面积 3 4 #include <iostream> 5 #include <cstdlib> 6 7 using namespace std; 8 9 const float pi= ; // 给出 pi 的值 10 const float price1=35.0; // 栅栏的单价 11 const float price2=20.0; // 过道造价 class Circle // 声明类 Circle 14 { 15 public: // 外部接口 16 Circle(float x) { r=x; } // 构造函数 17 float Circum(); // 计算圆周长 18 float Area(); // 计算圆面积 private: // 私有数据成员 21 float r; 22 }; // 成员函数 25 float Circle::Circum() // 计算圆的周长 26 { 27 return 2*pi*r; 28 } float Circle::Area() // 计算圆的面积 31 { 32 return pi*r*r; 33 } int main () // 主函数 37 { 38 float x, y, z; cout << " 输入游泳池半径 :"; // 提示用户输入半径 41 cin >> x; Circle Pool(x); // 小圆 : 游泳池 44 Circle PoolRim(x+3); // 大圆 : 游泳池加过道 // 计算栅栏造价并输出

108 96 第九讲类与对象 I: 面向对象基础 47 y = PoolRim.Circum()*price1; 48 cout << " 栅栏造价为 :" << y << endl; // 计算过道造价并输出 51 z = (PoolRim.Area()-Pool.Area())*price2; 52 cout << " 过道的造价为 :" << z << endl; return 0; 55 } pt pt 9.7 析构函数 析构函数 : 负责对象被释放时的一些清理工作 析构函数的一般形式 : ~ 类名 () { 函数体 } (1) 析构函数的函数名由类名前加 ~ 组成 (2) 析构函数没有返回值, 也不需要加返回值数据类型 (3) 析构函数在对象生存期即将结束时被自动调用 (4) 析构函数不接收任何参数 (5) 若没有析构函数, 系统会自动生成一个析构函数 ( 函数体为空 ) 9.8 上机练习练习 9.1 设计 Rectangle 类练习 9.2 设计 Complex 类练习 9.3 设计 Integer 类

109 第十讲类与对象 II: 面向对象进阶 10.1 类的组合 类的组合 : 将已有的类的对象作为新的类的数据成员, 如 : 1 class Point // 声明 Point 类 2 { }; 5 6 class Line // 声明 Line 类 7 { 8 public: private: 11 Point p1, p2; // 内嵌对象成员 12 float S; // 普通数据成员 13 }; (1) 在创建类的对象时, 如果这个类的数据成员中包含其它类的对象 ( 称为内嵌对象成员 ), 则各 个内嵌对象将首先被自动创建 (2) 组合类初始化包括内嵌对象成员的初始化和普通数据成员初始化 组合类构造函数的一般形式 : 类名 :: 类名 ( 总参数列表 ) : 内嵌对象 1( 参数 ), 内嵌对象 2( 参数 ),... { } 函数体 ( 类的数据成员的初始化 ) (1) : 内嵌对象 1( 参数 ), 内嵌对象 2( 参数 ),... 称为 初始化列表, 作用是对内嵌对象进行初始化, 这里的参数前面不用加数据类型 ( 是实参 ); (2) 除了自身的构造函数外, 内嵌对象的构造函数也被调用 ; (3) 构造函数调用顺序 : - 按内嵌对象在组合类的声明中出现的顺序依次调用内嵌对象的构造函数 ; - 最后调用本类的构造函数 (4) 总参数列表中的参数需要带数据类型 ( 形参 ), 初始化列表则不需要 ; (5) 析构函数的调用顺序与构造函数相反 97

110 98 第十讲类与对象 II: 面向对象进阶 例 10.1 类与对象 : 组合类的初始化 1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 class Point // 声明类 Point 7 { 8 public: // 外部接口 9 Point(double newx=0, double newy=0) // 构造函数 10 { x = newx; y = newy; } 11 double getx() {return x;} // 获取横坐标 12 double gety() {return y;} // 获取纵坐标 private: // 私有数据成员 15 double x, y; 16 }; class Line // 声明类 Line 19 { 20 public: // 外部接口 21 Line(double xa, double ya, double xb, double yb) : A(xA, ya) // 构造函数 22 { B = Point(xB,yB); } 23 double getlength(); // 计算线段的长度 private: // 私有数据成员 26 Point A, B; 27 int x, y; 28 }; double Line::getlength() // 计算线段的长度 31 { 32 double xx, yy; 33 xx = B.getx() - A.getx(); 34 yy = B.gety() - A.gety(); 35 return sqrt(xx*xx+yy*yy); 36 } int main () // 主函数 39 { 40 Line AB(1,2,4,6); cout << " 线段长度 : " << AB.getlength() << endl; return 0; 45 } 数据成员中常量和引用的初始化 : (1) 常量和引用的特殊性 : 不能赋值, 只能初始化 ( 因此必须初始化, 否则无意义 ); (2) 在初始化列表中进行初始化, 如 : 1 class Myclass 2 { 3 public:

111 10.2 结构体与联合体 99 4 Myclass(int x, int y, int z); 5 void display(); 6 7 private: 8 const int a; // a 是常量 9 int & b; // b 是引用 10 int c; // c 是普通变量 11 }; Myclass::Myclass(int x, int y, int z) : a(x),b(y) // 常量和引用的初始化 14 { 15 c = z; 16 } 不能在类的声明中初始化任何数据成员! 前向引用声明 : 如果在声明类 A 时需要用到类 B 的对象, 根据类必须先声明后使用的原则, 应该 先声明类 B, 但是若声明 B 时也需要用到 A 的对象, 这种情况如何处理? (1) 若两个类之间需要互相引用对方的对象, 则需要使用前向引用声明, 如 : 1 class B; // 前向引用声明 2 class A // 声明类 A 3 { 4 public: 5 void f(b b); // 声明类 A 时需要用到类 B 的对象 6 }; 7 8 class B // 声明类 B 9 { 10 public: 11 void g(a a); // 声明 B 时也需要用到 A 的对象 12 }; 使用前向引用声明时, 只能使用被声明的符号, 而不能涉及类的任何细节 10.2 结构体与联合体 容性 结构体与联合体是两种特殊形态的类, 他们是从 C 语言继承而来, 也是为了保持与 C 语言的兼 结构体 : struct 结构体名称 {

112 100 第十讲类与对象 II: 面向对象进阶 }; public: 公有成员 private: 私有成员 protected: 保护成员 (1) 结构体与类的唯一区别 : 在类中, 对于未指定访问控制属性的成员, 默认为私有成员 ; 而在 结构体中, 未指定访问控制属性的成员, 默认为公有成员 (2) C++ 中的结构体可以包含数据成员和函数成员, 而 C 语言中的结构体只能包含数据成员 联合体 : 一种特殊的数据结构, 可以包含多个成员, 但却共用一个存储单元, 如 : union Mark { }; char grade; // 等级制 bool pass; // 是否通过 int score; // 百分制 (1) 联合体的所有成员, 在同一时间至多一个有意义 ; (2) 联合体中成员的默认访问属性是公有类型 ; (3) 联合体一般只存放数据, 不包含函数成员 10.3 类作用域 类的数据成员与成员函数中的局部变量 : (1) 数据成员可以被类中的所有函数成员访问 ( 类似全局变量 ); (2) 成员函数中声明的变量是局部变量, 只在该函数中有效 ; (3) 如果成员函数中声明了与数据成员同名的变量, 则在该函数中数据成员被屏蔽 ( 类似于同名 的局部变量和全局变量 ) 例 10.2 类作用域 : 类的数据成员与成员函数中的局部变量 1 #include <iostream> 2 #include <cstdlib> 3 4 using namespace std; 5 6 class Point // Point 类的声明 7 { 8 public: // 外部接口 9 Point(double a, double b) // 构造函数 10 { x=a; y=b; } 11 void mycout()

113 10.4 静态成员 { 13 cout << " 数据成员 :x=" << x << endl; int x = 10; // 局部变量, 与数据成员同名 16 cout << " 局部变量 :x=" << x << endl; 17 } private: // 私有数据 20 int x, y; 21 }; int main() // 主函数 25 { 26 Point A(4,5); cout << "Point A: \n"; 29 A.mycout(); return 0; 32 } 10.4 静态成员 生存期 : 与普通变量一样, 对象也有动态生存期和静态生存期 (1) 动态生存期 : 对象所在的程序块执行完后, 对象就立即被释放 ; (2) 静态生存期 : 生存期与程序的运行期相同, 即在整个程序执行期间一直有效 静态数据成员 : (1) 一般情况下, 同一个类的不同对象都有自己的数据成员, 名字一样, 但各有各的值, 互不相 干 但有时希望某些数据成员为所有对象所共有, 这样可以实现数据共享 (2) 全局变量可以达到共享数据的目的, 但其安全性得不到保证 : 任何函数都可以自由修改全局 变量的值, 很有可能偶然失误, 全局变量的值被错误修改, 导致程序的失败 因此在编程中 要慎用全局变量 (3) 如果需要在同一个类的多个对象之间实现数据共享, 可以使用静态数据成员 静态数据成员的声明 : 与普通变量一样, 声明时在前面加上关键字 static (1) 静态数据成员在内存中只占一份空间, 为整个类所共有, 不属于任何特定对象 ; (2) 该类的所有对象共同使用和维护静态数据成员 ; (3) 静态数据成员可以初始化, 但必须在类的外部初始化, 如 : 1 class Point 2 { private: 5 static int count; // 静态变量 6 }; 7 8 int Point::count=1; // 静态数据成员的定义和初始化

114 102 第十讲类与对象 II: 面向对象进阶 (4) 如果静态数据成员没有初始化, 则系统会自动赋予初值 0; (5) 定义了静态数据成员, 即使不创建对象, 系统也会为静态数据成员分配空间, 并可以被引用 ; (6) 静态数据成员既可以通过对象名引用, 也可以通过类名来引用, 即 : 对象名. 静态成员名或类名 :: 静态成员名 例 10.3 静态数据成员举例 1 #include <iostream> 2 3 using namespace std; 4 5 class Box 6 { 7 public: 8 Box(int, int); 9 int volume(); static int height; // 把 height 定义为公有的静态数据成员 12 int width; 13 int length; 14 }; int Box::height=10; // 对静态数据成员 height 初始化 Box::Box(int wid, int len) // 通过构造函数对 width 和 length 赋初值 19 { 20 width=wid; length=len; 21 } int Box::volume() // 计算体积 24 { 25 return(height*width*length); // 直接使用静态数据成员 height 26 } int main() 29 { 30 Box a(15,20), b(20,30); cout<<a.height<<endl; // 通过对象 a 引用静态数据成员 33 cout<<b.height<<endl; // 通过对象 b 引用静态数据成员 34 cout<<box::height<<endl; // 通过类名引用静态数据成员 35 cout<<a.volume()<<endl; // 计算体积 return 0; 38 } 静态函数成员 (1) 用关键字 static 修饰, 为整个类所共有, 调用方式 : 类名 :: 静态函数成员名 (2) 静态成员函数没有目的对象, 所以不能对非静态数据成员进行缺省访问, 如 :

115 10.4 静态成员 // 假定静态成员函数中有以下语句 : 2 cout << height; // 若 height 是 static, 则合法 3 cout << width; // 若 width 是非静态数据成员, 则不合法 (3) 静态成员函数一般用于访问静态数据成员, 维护对象之间共享的数据 (4) 如果静态成员函数访问非静态数据成员时, 需指明对象, 如 : 1 cout << p.width; // 访问对象 p 的非静态数据成员 width (5) 静态成员函数声明时需加 static, 但定义时不需加 static 1 // 静态函数成员 2 class A 3 { public: static void fun(a a); }; 实际上也允许通过对象名调用静态成员函数, 但此时使用的是类的性质, 而不是对象 本身 编程好习惯 : 只用静态成员函数引用静态数据成员, 而不引用非静态数据成员, 这样 思路清晰, 逻辑清楚, 不易出错 例 10.4 静态函数成员举例 1 #include <iostream> 2 3 using namespace std; 4 5 class Student 6 { 7 public: 8 Student(int num=0, float s=0) 9 { id=num; score=s; } 10 void total(); // 普通成员函数 11 static float average(); // 静态成员函数 private: 14 int id; 15 float score; 16 static float sum; // 静态数据成员 17 static int count; // 静态数据成员 18 }; float Student::sum=0; // 对静态数据成员初始化 21 int Student::count=0; // 对静态数据成员初始化

116 104 第十讲类与对象 II: 面向对象进阶 void Student::total() // 普通成员函数 24 { 25 sum+=score; // 计算总分, 访问普通数据成员 26 count++; // 已统计的人数, 访问静态数据成员 27 } float Student::average() // 静态函数 30 { 31 return(sum/count); 32 } int main() 35 { 36 Student stu[4]={student(1001,70), 37 Student(1002,78), 38 Student(1005,98), 39 Student()}; 40 int n; 41 cout << " 输入需要统计的人数 : "; 42 cin >> n; // 统计前 n 名学生的平均成绩 for(int i=0;i<n;i++) 45 stu[i].total(); cout << " 前 "<< n <<" 个学生的平均成绩是 :" 48 << Student::average() << endl; // 调用静态成员函数 return 0; 51 } 10.5 友元关系 友元关系 : 提供一种类与外部函数之间进行数据共享的机制 通俗说法 : 一个类主动声明哪些类或外部函数是它的朋友, 从而给它们提供对本类成员的访问特 许, 即可以访问私有成员和保护成员 (1) 好处 : 友元提供了一种数据共享的方式, 提高了程序效率和可读性 (2) 坏处 : 友元在一定程度上破坏了数据封装和数据隐藏机制 友元包括 : 友元函数与友元类 友元类的所有函数成员都是友元函数 友元函数 (1) 用关键字 friend 修饰 (2) 友元函数是非成员函数 ( 可以是普通函数或其它类的成员函数 ) (3) 友元函数可以通过对象名直接访问私有成员和保护成员 1 class Point 2 { 3 public: friend float dist(point &, Point &); // 将外部函数 dist 声明为友元函数

117 10.6 类的 UML 描述 private: 7 int x, y; 8 }; 9 float dist(point & p1, Point & p2) 10 { 11 double x=p1.x-p2.x, y=p1.y-p2.y; // 友元函数可以直接访问私有成员 12 return sqrt(x*x+y*y); 13 } 友元类 (1) 用关键字 friend 修饰 (2) 友元类的所有成员函数都是友元函数 1 class A 2 { 3 public: friend class B; // 将 B 声明为友元类 }; 除非确有必要, 一般不建议把整个类声明为友元类, 而只将确实有需要的成员函数声明为友元函数, 这样更安全 关于友元关系的几点说明 (1) 友元关系不能传递 (2) 友元关系是单向的 (3) 友元关系不能被继承 ( 关于类的继承将在后面介绍 ) 面向对象程序设计的一个基本原则是封装性和信息隐蔽, 而友元是对封装原则的一个小的破坏 但是它能有助于数据共享, 提高程序的效率 在使用友元时, 要注意它的副作用, 不要过多地使用友元, 只有在使用它能使程序精炼, 并能大大提高执行效率时才用, 否则可能会得不偿失 10.6 类的 UML 描述 UML:Unified Modeling Language (1) 面向对象建模语言, 通过图形的方式描述面向对象程序设计 (2) 在 UML 类图中, 类一般由三部分组成 : 类名, 数据成员, 函数成员

118 106 第十讲类与对象 II: 面向对象进阶 数据成员表示方法 : 访问属性名称 : 类型 [ = 缺省值 ] 访问属性 :+ 表示 public,- 表示 private,# 表示 protected 函数成员表示方法 : 访问属性名称 ( 参数列表 ) [: 返回类型 ] 10.7 上机练习 练习 10.1 设计一个名为 Score 的类, 设计一个名为 Student 的类 练习 10.2 设计一个名为 MyDate 的类

119 第十一讲类与对象 III: 面向对象提高 11.1 常对象与常成员 将对象声明成常对象, 可以有效地保护数据 常对象的声明 : const 类名对象名 ; // const 可以放在 类名 前面 类名 const 对象名 ; // 也可以放在后面 (1) 常对象必须进行初始化 ( 初始化列表, 不能赋值 ) (2) 常对象主要是针对数据成员, 及常对象的所有数据成员均为常量, 不能被修改 不能通过常对象调用普通成员函数, 即常对象不能作为普通成员函数的目的对象 ( 这 里的普通成员函数是相对于后面介绍的常成员函数而言, 即常对象只能作为常成员函 数的目的对象 ) 常数据成员 (1) 可以将部分数据成员声明为常量 (2) 常数据成员必须初始化 ( 采用初始化列表方式, 不能在构造函数的函数体内赋值 ), 如 : 1 // 假定数据成员 x 是常量,y 是普通变量 2 Point::Point(int a, int b): x(a) { y=b; } 常函数成员 类型标识符函数名 ( 形参 ) const; (1) 若一个对象是常对象, 则通过该对象只能调用常成员函数 ; (2) 普通对象也可以调用常成员函数 ; (3) 无论对象是否为常对象, 在常成员函数被调用期间, 目的对象都将被视为常对象 如果某个成员函数不修改对象的数据, 则可将其声明为常函数 例 11.1 常对象, 常成员函数, 常数据成员 1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 class Myclass 7 { 107

120 108 第十一讲类与对象 III: 面向对象提高 8 public: 9 Myclass(int x, int y); 10 void display() const; // 常函数成员 11 void show(); private: 14 const int a; // 常数据成员 15 int b; 16 }; Myclass::Myclass(int x, int y): a(x) // 常数据成员的初始化 19 { 20 b = y; 21 } 22 // 也可以写为 : Myclass::Myclass(int x, int y): a(x), b(y) { } 23 // 但不能是 : Myclass::Myclass(int x, int y) { a = x; b = y; } void Myclass::display() const 26 { 27 cout << "a=" << a << ", b=" << b << endl; 28 } void Myclass::show() 31 { 32 cout << "a=" << a << ", b=" << b << endl; 33 } int main () // 主函数 36 { 37 Myclass obj1(2,3); // 普通对象 38 const Myclass obj2(4,5); // 常对象 39 Myclass const obj3(6,7) ; // 常对象 // 常成员函数 42 cout << "obj1:"; obj1.display(); 43 cout << "obj2:"; obj2.display(); 44 cout << "obj3:"; obj3.display(); // 普通成员函数 47 cout << "obj1:"; obj1.show(); 48 // cout << "obj2:"; obj2.show(); // ERROR, 常对象不能作为普通成员函数的目的对象 49 // cout << "obj3:"; obj3.show(); // ERROR, 常对象不能作为普通成员函数的目的对象 return 0; 52 } 常引用 const 类型标识符 & 引用名 ; (1) 常引用可以绑定到常对象, 普通引用不能绑定到常对象 ; (2) 常引用也可以绑定到普通对象, 但无论常引用所绑定的是常对象还是普通对象, 都不能通过 常引用来修改其所绑定的对象的数据

121 11.1 常对象与常成员 109 例 11.2 常引用 1 #include <iostream> 2 #include <cstdlib> 3 #include <cmath> 4 5 using namespace std; 6 7 class Complex 8 { 9 public: 10 Complex(double a, double b) { x=a; y=b; } 11 double mydist(const Complex &); // 形参是常引用 12 double mydistnew(complex &); // 形参是普通引用 private: 15 double x, y; 16 }; double Complex::mydist(const Complex & z) 19 { 20 double xx = x - z.x; 21 double yy = y - z.y; return sqrt(pow(xx,2)+pow(yy,2)); 24 } double Complex::mydistnew(Complex & z) 27 { 28 double xx = x - z.x; 29 double yy = y - z.y; return sqrt(pow(xx,2)+pow(yy,2)); 32 } int main() 35 { 36 Complex a(2.5,3.8), b(-4.2,5.6); // 普通对象 37 const Complex c(9.4,10.2); // 常对象 // 常引用 40 cout << " a-c =" << a.mydist(c) << endl; // 常引用可以绑定到常对象 41 cout << " a-b =" << a.mydist(b) << endl; // 常引用也可以绑定到普通对象 // 普通引用 44 cout << " a-b =" << a.mydistnew(b) << endl; 45 // cout << " a-c =" << a.mydistnew(c) << endl; // ERROR, 普通引用不能绑定到常对象 return 0; 48 } 用常引用和常指针作函数参数, 不仅可以节省开销, 还可以保证数据的安全

122 110 第十一讲类与对象 III: 面向对象提高 11.2 对象数组与对象指针 对象数组 : 与普通数组类似, 只是数组元素是对象 一维对象数组的声明 : 类名数组名 [n] 一维对象数组的引用 : 数组名 [k]. 成员名 类似地, 可以声明高维对象数组 一维对象数组的初始化 : 对每个分量都调用构造函数 Point() { x=0; y=0} // 构造函数 3 Point(int a, int b) { x=a; y=b; } // 构造函数 int main() 7 { 8 Point A[2]={Point(), Point(2,3); // 一维对象数组的初始化 } 对象指针 : 指向对象的指针, 即存放对象的地址 (1) 对象指针的声明 : 类名 * 对象指针名 (2) 使用对象指针访问对象成员 ( 两种方式 ): 对象指针名 -> 成员名 (* 对象指针名 ). 成员名 - 其中前面一种方式是对象指针所特有的使用方式, 推荐使用 (3) 指向常对象的指针 :const 类名 * 对象指针名 this 指针 : 隐含在非静态成员函数中的特殊指针, 永远指向目的对象 (1) this 指针是常指针 ; (2) 当局部作用域中声明了与类成员同名的标识符 ( 如变量名 ) 时, 可以通过 this 指针来访问目的对象的成员 ; (3) 当通过一个对象来调用成员函数 ( 非静态成员函数 ) 时, 系统会把该对象的起始地址赋给 this 指针

123 11.3 动态对象 111 非静态成员函数有 this 指针, 而静态成员函数没有 this 指针 ( 静态成员函数没有目 的对象!) 指向非静态成员的指针 : 直接指向类的成员 ( 数据成员或函数成员 ) 类型标识符类名 ::* 指针名 类型标识符 ( 类名 ::* 指针名 )( 参数 ) // 指向函数成员 (1) 指向数据成员的指针的赋值 : 指针名 =& 类名 :: 数据成员名 (2) 指向数据成员指针的引用 : 对象名.* 指针名 对象指针名 ->* 指针名 (3) 指向函数成员指针的赋值 : 指针名 =& 类名 :: 函数成员名 (4) 指向函数成员指针的引用 : ( 对象名.* 指针名 )( 参数 ) ( 对象指针名 ->* 指针名 )( 参数 ) // 指向数据成员, 与普通指针的区别 : 加类名 指向静态成员的指针 : 由于对静态成员的访问不依赖于对象, 因此可以通过普通的指针来访问静态成员, 即声明时不用 加类名 11.3 动态对象 动态对象的创建 :new 类名 * 指针名 =new 类名 () // 调用不带参数的构造函数进行初始化 类名 * 指针名 =new 类名 ( 参数列表 ) // 调用带参数的构造函数进行初始化 动态对象的释放 :delete delete 指针名 动态对象使用结束后一定要用 delete 手工释放, 否则可能会造成内存泄漏 11.4 向量类 :vector C++ 提供了向量类, 用于创建向量 向量是对象, 其使用与一维数组类似, 但向量的长度可以根 据需要自动增减, 而且提供了更加丰富的成员函数, 比普通数组更加灵活和方便

124 112 第十一讲类与对象 III: 面向对象提高 包含向量类的头文件 :#include <vector> 向量的声明 : vector< 数据类型标识符 > 向量名 ; 1 // 创建向量对象 2 #include <vector> vector<int> x(10); // 创建一个长度为 10 的整型向量, 注意这里是 ( ), 不是 [ ] 5 vector<double> y(3); // 创建一个长度为 3 的双精度型向量 (1) 可创建不同数据类型的向量, 需要指出的是, 这里 x 是对象, 不是数组名 ; (2) 由于向量是对象, 所以创建时会直接初始化 ( 调用相应的构造函数 ); (3) 向量的元素也可以是某个类的对象 例 11.3 向量类 : 创建向量 1 #include <iostream> 2 #include <vector> 3 4 using namespace std; 5 6 int main() 7 { 8 vector <int> x; 9 vector <int> y(10,1); // 长度为 10, 所有元素都是 cout << "size of x: " << x.size() << endl; 12 cout << "size of y: " << y.size() << endl; 13 cout << "first member of y: " << y[0] << endl; 14 cout << "last member of y: " << y.back() << endl; cout << "\n=== add a member from the back ===\n"; 17 y.push_back(5); 18 cout << "size of y: " << y.size() << endl; 19 cout << "last member of y: " << y.back() << endl; return 0; 22 } 例 11.4 向量类 : 以其他类的对象为元素 1 #include <iostream> 2 #include <vector> 3 4 using namespace std; 5 6 class Point 7 { 8 public: 9 point() { x=0; y=0; }

125 11.4 向量类 :vector Point(int a, int b) { x=a; y=b; } 11 void Display() 12 { cout << "(" << x << "," << y << ")"; } private: 15 int x, y; 16 }; int main() 19 { 20 vector<point> x; // 长度为 cout << "size of x:" << x.size() << endl; x.push_back(point(1,2)); // 在末尾插入一个 Point 对象, push_back() 的用法介绍见后面 25 cout << "\nafter push_back \nsize of x:" << x.size() << endl; 26 cout << "x[0]="; x[0].display(); cout << endl; return 0; 29 } 向量类构造函数 ( 部分 ) vector<type>(); // 缺省构造函数, 创建一个空向量, 即长度为 0 的向量 vector<type>(int n); // 创建长度为 n 的向量 vector<type>(int n, const Type & a); // 创建长度为 n 的向量, 并用 a 初始化所 有分量 vector<type>(const vector<type> & x); // 复制构造函数, 用向量 x 初始化新向量 这里的 Type 可以是基本数据类型, 如 int,float,double 等, 也可以是类名, 如 Point 1 vector<int> x(100); // 创建长度为 100 的整型向量, 值全部为 0 2 vector<float> y(10, 2.1); // 创建长度为 10 的单精度型向量, 初值都是 vector<double> z; // 创建一个双精度型的向量, 长度为 0 创建向量时, 如果是基本数据类型, 且只指定长度, 如上面代码的第一行, 则所有分量都 会被初始化为 0. 如果分量是都是某个类的对象, 则创建向量时可以不指定长度 ( 即长度为 0), 然后通过成员函数 push_back() 逐步添加元素 向量的基本操作 :

126 114 第十一讲类与对象 III: 面向对象提高 v[k] 下标运算, 返回第 k 个分量的值 ( 下标从 0 开始 ) v1 = v2 赋值运算 ( 复制 ) v1 == v2 v1!= v2 比较运算, 个数和值都相等时返回真, 否则为假 比较运算, 不相等时返回真, 否则为假 <, <=, >, >= 比较运算, 按字典顺序进行比较 常用成员函数 : at(int k) size() clear() 返回下标为 k 的分量 返回向量的长度 清空向量中的数据, 只清空数据, 不改变向量长度 empty() 判断向量是否为空 ( 长度为 0) front() back() push_back( 数据 ) pop_back() swap(vector<type> &) 返回第一个分量的值返回最后一个分量的值在向量末尾插入一个数据删除最后一个分量交换目的向量与指定向量 ( 形参 ) 的值 一定要铭记 : 向量名不是地址! 向量是对象 1 // 误区 : 下标只能用于获取已存在的元素, 所以下面的用法是不对的 2 vector<int> x; 3 for(int k=0; k<10; k++) 4 x[i] = i; 5 6 // 正确用法是 7 vector<int> x; 8 for(int k=0; k<10; k++) 9 x.push_back(i); // 或者 12 vector<int> x(10); 13 for(int k=0; k<10; k++) 14 x[i] = i; 例 11.5 找出给定区间内的所有素数, 存储到一个向量中 1 #include <iostream> 2 #include <cmath>

127 11.5 字符串类 :string #include <vector> 4 5 using namespace std; 6 7 bool is_prime(int n) 8 { 9 if (n<2) return false; 10 for (int k=2; k<=sqrt(n); k++) 11 if (n%k==0) return false; return true; 14 } void find_prime(int a, int b, vector<int> & x) 17 { 18 for (int k=a; k<=b; k++) 19 { 20 if (is_prime(k)) 21 x.push_back(k); 22 } 23 } int main() 26 { 27 int a, b; 28 vector<int> x; cout << "Input a and b: "; 31 cin >> a >> b; find_prime(a,b,x); cout << "[" << a << "," << b << "] 中的素数有 :" << endl; 36 for (int i=0; i<x.size(); i++) 37 { 38 cout << x[i] << " "; 39 if (i%10==9) cout << endl; 40 } 41 cout << endl; return 0; 44 } 11.5 字符串类 :string 在 C++ 中, 字符串可以通过字符数组来实现, 也可以通过 string 类实现 在实际使用中,string 类 更灵活方便 为了以示区别, 我们将由字符数组定义的字符串称为数组字符串 使用 string 类必须包含 string 头文件 :#include <string> 1 #include <string> // 注意不是 cstring

128 116 第十一讲类与对象 III: 面向对象提高 3 string str; // 创建一个空字符串对象 4 string str1="math.", str2("ecnu"); // 创建字符串对象并初始化 5 string str3=str1+str2; // str3="math.ecnu" 6 string str4(5,'c'); // 创建长度为 5 的字符串, 分量都是字符 'c' string 类构造函数 ( 部分 ): string(); // 缺省构造函数 string(const string &); // 复制构造函数 string(const char * s); // 用字符串常量进行初始化 string(const string & s, unsigned int p, unsigned int n); // 从位置 p 开始, 取 n 个字符, 即 s[p],.., s[p+n-1] string(const char * s, unsigned int n); // 使用 s 的前 n 个字符进行初始化 string(unsigned int n, char c); // 给定的字符重复 n 次 字符串的输入输出 : cin >> str; cout << str; 输入也可以用 getline getline(cin,str) // 以换行符作为输入结束符 getline(cin,str,'c') // 将字符 'c' 作为输入结束符 字符串的基本操作 str[k] 下标运算, 返回第 k 个分量 + 连接两个字符串 = 赋值运算 ( 复制 ) += 连接赋值 ==,!=, <, <=, >, >= 比较运算 比较大小按字典顺序, 从前往后逐个进行比较 1 string str1 = "Hello"; 2 string str2(3,'a'); 3 string str3 = str1 + str2; 两个 string 对象可以相加,string 对象和数组字符串也可以相加, 但两个数组字符串不能直接相加 1 string str4 = str1 + " Math"; // OK 2 string str4 = "Hello" + " Math"; // ERROR 3 string str4 = "Hello" + str1 + " Math"; // OK

129 11.5 字符串类 :string 117 string 对象可以直接赋值, 但数组字符串不能! 1 string str1; 2 char str2[10]; 3 4 str1="hello"; // OK 5 str2="hello"; // ERROR 常用成员函数 str.at(k) 返回第 k 个字符 ( 会自动检测是否越界 ) str.length() 字符串对象的长度 ( 字符个数 ) str.size() str.capacity() 同上 返回为当前字符串分配的存储空间 str.clear() str.erase(k,n) str.~string() str.empty() 清除字符串中所有内容从下标 k 开始, 连续清除 n 个字符释放 string 对象判断 string 对象是否为空 str.assign(str1) str.assign(cstr) 用字符串对象赋值 用数组字符串赋值 str.assign(str1,k,n) str.assign(str1,n) str.assign(n,c) 用 str 从下标 k 开始的连续 n 个字符赋值 用 str 前 n 个字符赋值 用 n 个字符 c 赋值 str.append(str1) str.append(str1,k,n) str.append(cstr,n) str.append(n,c) 将字符串 str1 追加到当前字符串后面追加 str1 从下标 k 开始的连续 n 个字符追加数组字符串 cstr 的前 n 个字符追加 n 个字符 c str.substr(k,n) str.substr(k) 返回当前字符串从下标 k 开始的连续 n 个字符 返回当前字符串从下标 k 开始的子串 str.compare(str1) 与 str 比较 ( 大于为正, 等于为 0, 小于为负 ) str.compare(k,n,str1) 与 str 的字串 ( 从下标 k 开始的连续 n 个字符 ) 进行比较

130 118 第十一讲类与对象 III: 面向对象提高 str.insert(k,str1) str.insert(k,n,c) str.replace(k,n,str1) 在下标 k 位置插入字符串 str 在下标 k 位置连续插入 n 个字符 c 用 str 的内容替换从下标 k 开始的 n 个字符 str.find(str1) str.find(str1,k) str.find(c) str.find(c,k) 返回 str 在当前字符串中首次出现的位置同上, 从下标 k 位置开始查找返回字符 c 在当前字符串中首次出现的位置同上, 从下标 k 位置开始查找 str.c_str() str.data() 将当前字符串转化为数组字符串 同上 更多成员函数参见 C++ Reference 例 11.6 二进制转化为十进制, 用 string 类实现 1 #include <iostream> 2 #include <iomanip> 3 #include <string> 4 5 using namespace std; 6 7 long bin2dec(const string & str); 8 9 int main() 10 { 11 string str; cout << " 请输入二进制数 :"; 14 getline(cin,str); cout << " 对应的十进制数为 :" << bin2dec(str) << endl; return 0; 19 } long bin2dec(const string & str) 22 { 23 long num=0; for (int i=0; i<str.length(); i++) 26 num = num*2 + str[i]-'0'; return num; 29 } 字符串匹配算法

131 11.6 上机练习 119 字符串匹配的形式定义 : 文本 (Text) 是一个长度为 n 的数组 T [n]; 模式 (Pattern) 是一个长度为 m (m n) 的数组 P [m]; T 和 P 中的元素都属于某个有限的字符表, 如字母, 字母加数字, 等等 如果存在正整数 s (s n m), 使得 P [i] = T [s + i], i = 0, 1,..., m 1, 则称模式 P 在文本 T 中出现, 称 s 是一个有效位移 (Valid Shift) 字符串匹配的算法包括 : 朴素算法,Rabin-Karp 算法,Knuth-Morris-Pratt (KMP) 算法,Boyer-Moore 算法等, 其中朴素算法简单易懂, 但效率较低, 而 KMP 算法是目前常用的高效字符串匹配算法 首先介绍朴素算法 (Naive string matching), 基本思想就是逐个搜索匹配, 代码如下 : 1 for (i=0, flag=0; T[i]!='\0'; i++) 2 { 3 for (j=0; T[i+j]!='\0' && P[j]!='\0' && T[i+j]==P[j]; j++); 4 5 if (P[j]=='\0') 6 { 7 flag = 1; // found a match 8 break; 9 } 10 } 11 if (flag) 12 cout << "Found a match" << endl; 13 else 14 cout << "No match found" << endl; 朴素算法通过两重循环来实现, 所以在最坏情况下的时间复杂度为 O(mn) 1977 年,Donald Knuth 和 Vaughan Pratt 提出了改进的匹配方法, 同一时间,James H. Morris 也独立提出了相同的改进方法, 因此该方法被命名为 KMP 算法 To be continued 上机练习练习 11.1 设计 Rectangle2D 类练习 11.2 字符异位破译, 用字符串类实现练习 11.3 设计 Employee 类

132 第十二讲运算符重载与类型转换 12.1 为什么要重载运算符 预定义的运算符 ( 如 + - * / > < == << >> 等 ) 只针对基本数据类型, 若要使得对象 也能进行类似的运算, 则需要通过运算符重载来实现 运算符重载 : 本质上就是函数重载, 即对已有的运算符添加多重含义, 使得同一个运算符可以作用于不同类型 的数据, 特别是类的对象 比如声明了 Complex 类后, 怎样实现 Complex 对象的加法? 1 int x1=1, x2=2, x3; 2 x3 = x1 + x2; // 普通数据类型的加法 3 4 Complex z1(1.2,3.4), z2(5.6,7.8), z3; 5 z3 = z1 + z2; // Complex 类对象的加法, 如何实现? --> 运算符重载 运算符重载基本规则 : (1) 只能重载已有的运算符 ; (2) 重载不改变运算符的优先级和结合率 ; (3) 运算符重载不改变运算符的操作数的个数 ; (4) 重载的运算符的功能应该与已有的功能类似 ; (5) 运算符重载是为了满足新数据类型 ( 类与对象 ) 的需要, 因此要求至少有一个操作数是新类型的数据 ( 这里可以理解为自定义类的对象 ) 四个不能被重载的运算符 :..* ::?: 12.2 怎么实现运算符重载 运算符重载的一般形式 :( 以成员函数方式为例 ) (1) 声明 : 类型标识符 operator 运算符 ( 形参列表 ); (2) 定义 : 可以在声明时直接定义, 也可以在类内部只声明, 然后在类外部定义, 此时需加上类 名, 即 类型标识符类名 ::operator 运算符 ( 形参列表 ) { 函数体 ; } 120

133 12.3 运算符重载 : 成员函数方式 1 // 重载加法运算, 使得 Complex 类对象也能相加 2 Complex Complex::operator+(Complex & c2) 3 { 4 return Complex(real+c2.real, imag+c2.imag); } 这里的类型标识符可以是类名或基本数据类型 运算符重载的两种实现方式 : 成员函数和非成员函数 ( 即外部函数 ) 12.3 运算符重载 : 成员函数方式 特点 : (1) 可以自由访问本类对象的 ( 私有 ) 数据成员 ; (2) 运算符重载为成员函数时, 形参个数可以少一个 ; (3) 若是双目运算, 则左操作数就是目的对象本身, 可使用 this 指针来调用 ; (4) 若是单目运算, 则目的对象就是操作数, 不需要其它形参 ( 注 : 后置 ++ 和后置 -- 除外 ) 例 12.1 运算符重载 : 有理数加法运算 1 #include <iostream> 2 3 using namespace std; 4 5 class Rational 6 { 7 public: 8 Rational() { x=0; y=1; } 9 Rational(int x, int y) { this->x=x; this->y=y; } 10 Rational operator+(const Rational & p); 11 void Display() { cout << x << "/" << y << endl; } private: 14 int x, y; 15 }; Rational Rational::operator+(const Rational & p) // 重载加法运算 18 { 19 int newx = x*p.y + y*p.x; 20 int newy = y*p.y; 21 return Rational(newx, newy); 22 } int main() 25 { 26 Rational a(4,5), b(7,3), c; cout << "a="; a.display(); 29 cout << "b="; b.display(); c = a + b; // 使用重载运算符完成有理数加法

134 122 第十二讲运算符重载与类型转换 32 cout << "a+b="; c.display(); return 0; 35 } 双目运算符的重载 ( 成员函数方式 ): 类型标识符 operator (const 类名 & ); 形参建议用 常引用, 既可以实现与变量的运算, 也可以实现与常量的运算 这里 表示可以重载的双目运算 注意 : 只有一个形参 前置单目运算符的重载 ( 成员函数方式 ): 类型标识符 operator (); 常见的前置单目运算符有 :! 注意 : 没有形参 后置单目运算符 (++ --) 的重载 ( 成员函数方式 ): 类型标识符 operator (int); 带一个整型形参, 但该参数在运算中不起任何作用, 只用于区分前置和后置, 因此也称为伪参 数 例 12.2 运算符重载 : 前置和后置单目运算 1 #include <iostream> 2 #include <iomanip> 3 4 using namespace std; 5 6 class Clock // 时钟类 7 { 8 public: 9 Clock(int H=0, int M=0, int S=0); 10 void ShowTime() const; 11 Clock operator++(); // 前置单目运算符重载 12 Clock operator++(int); // 后置单目运算符重载 private: 15 int hour, minute, second; 16 }; Clock::Clock(int H, int M, int S) // 构造函数 19 { 20 if(0<=h && H<24 && 0<=M && M<60 && 0<=S && S<60) 21 { hour = H; minute = M; second = S; } 22 else 23 { cout<<"time error!"<<endl; } 24 }

135 12.4 运算符重载 : 非成员函数方式 void Clock::ShowTime() const // 显示时间 27 { 28 cout.fill('0'); 29 cout << setw(2) << hour << ":" 30 << setw(2) << minute << ":" 31 << setw(2) << second << endl; 32 } Clock Clock::operator++() // 前置单目运算符重载 35 { 36 second++; 37 if(second >= 60) 38 { 39 second -= 60; 40 minute++; 41 if(minute >= 60) 42 { 43 minute -= 60; 44 hour = (++hour) % 24; 45 } 46 } 47 return *this; 48 } Clock Clock::operator++(int) // 后置单目运算符重载 51 { // 注意形参表中的整型参数 52 Clock old = *this; 53 ++(*this); // 调用前置 return old; 55 } int main() 58 { 59 Clock myclock(23,59,59); cout<<"first time output:"; 62 myclock.showtime(); cout<<"show myclock++ : "; // 后置 ++, 先参与运算, 然后自身加 1 65 (myclock++).showtime(); cout<<"show ++myclock : "; 68 (++myclock).showtime(); // 前置 ++, 先自身加 1, 然后参与运算 return 0; 71 } 12.4 运算符重载 : 非成员函数方式 非成员函数 ( 外部函数方式 ): (1) 形参个数与操作数相同 ; (2) 所有操作数都通过参数传递 ; (3) 一般需在相关类中将其声明为友元函数, 以便可以直接访问 ( 私有 ) 数据成员

136 124 第十二讲运算符重载与类型转换 1 class Complex 2 { public: 4 friend Complex operator+(const Complex &, const Complex &); } 7 8 Complex operator+(const Complex & c1, const Complex & c2) 9 { 10 return complex(c1.real+c2.real, c1.imag+c2.imag); 11 } 双目运算符的重载 ( 非成员函数方式 ): (1) 在类内部声明为友函数 : friend 类型标识符 operator (const 类名 &, const 类名 &); (2) 定义 ( 必须在类外部定义 ): 类型标识符 operator (const 类名 & p1, const 类名 & p2) { 函数体 ; } 注意 : 不是成员函数, 所以定义时不要加类名 例 12.3 运算符重载 : 有理数减法运算, 非成员函数方式 1 #include <iostream> 2 #include <cstdlib> 3 4 using namespace std; 5 6 class Rational 7 { 8 public: 9 Rational() { x=0; y=1; } 10 Rational(int x, int y) { this->x=x; this->y=y; } 11 void Display() { cout << x << "/" << y << endl; } 12 friend Rational operator-(const Rational &, const Rational &); private: 15 int x, y; 16 }; Rational operator-(const Rational &p1, const Rational &p2) // 外部函数 ( 非成员函数 ) 19 { 20 int newx = p1.x*p2.y - p1.y*p2.x; 21 int newy = p1.y*p2.y; 22 return Rational(newx, newy); 23 } int main() 26 { 27 Rational a(4,5), b(7,3), c;

137 12.4 运算符重载 : 非成员函数方式 cout << "a="; a.display(); 30 cout << "b="; b.display(); c = a - b; // 使用重载运算符完成有理数的减法 33 cout << "a-b="; c.display(); return 0; 36 } 前置单目运算符的重载 ( 非成员函数方式 ): friend 类型标识符 operator ( 类名 &); 后置单目运算符 ( 如 :++ --) 的重载 ( 非成员函数方式 ): friend 类型标识符 operator ( 类名 &, int); 第二个形参是伪参数, 只用于区分前置和后置 例 12.4 运算符重载 : 前置和后置单目运算, 非成员函数方式 1 #include <iostream> 2 #include <iomanip> 3 4 using namespace std; 5 6 class Clock 7 { 8 public: 9 Clock(int H=0, int M=0, int S=0); 10 void ShowTime() const; 11 friend Clock operator++(clock &); // 前置单目运算符重载 12 friend Clock operator++(clock &, int); // 后置单目运算符重载 private: 15 int hour, minute, second; 16 }; Clock::Clock(int H, int M, int S) // 构造函数 19 { 20 if(0<=h && H<24 && 0<=M && M<60 && 0<=S && S<60) 21 { hour = H; minute = M; second = S; } 22 else 23 { cout<<"time error!"<<endl; } 24 } void Clock::ShowTime() const // 显示时间 27 { 28 cout.fill('0'); 29 cout << setw(2) << hour << ":" 30 << setw(2) << minute << ":" 31 << setw(2) << second << endl; 32 } 33

138 126 第十二讲运算符重载与类型转换 34 Clock operator++(clock & c1) // 前置单目运算符重载函数 35 { 36 c1.second = c1.second + 1; 37 if(c1.second >= 60) 38 { 39 c1.second = c1.second - 60; 40 c1.minute = c1.minute + 1; 41 if(c1.minute >= 60) 42 { 43 c1.minute = c1.minute - 60; 44 c1.hour = (c1.hour+1) % 24; 45 } 46 } 47 return c1; 48 } Clock operator++(clock & c1, int) // 后置单目运算符重载 51 { 52 Clock old=c1; 53 ++(c1); // 调用前置 return old; 55 } int main() 58 { 59 Clock myclock(23,59,59); cout<<"first time output:"; 62 myclock.showtime(); cout<<"show myclock++ : "; 65 (myclock++).showtime(); cout<<"show ++myclock : "; 68 (++myclock).showtime(); cout << endl; return 0; 73 } 12.5 成员函数 or 非成员函数? 有些运算符只能以成员函数方式重载, 如 = [] -> (), 有些只能以非成员函数方式重载, 如 << >>, 其他运算符则既可以用成员函数方式重载, 也可以用非成员函数重载 采用何种方式, 建议如下 : 单目运算符, 建议用成员函数方式重载 ; 双目运算符, 如果两个操作数的地位是平等的, 且不改变操作数的值, 则建议用非成员函数方式 ; 双目运算符, 如果两个操作数的地位不平等, 则建议用成员函数方式, 如 += 等

139 12.6 运算符 [] 的重载 运算符 [] 的重载 为什么要重载 [] 在数组运算中, 可以通过 [] 来引用指定位置的元素 现在对于 Rational 类, 我们希望用 r[0] 表示分子,r[1] 表示分母, 怎么实现? 我们可以这么做 : 1 // 成员函数方式重载 2 int Rational::operator[](int idx) 3 { 4 if (idx == 0) 5 return x; 6 else 7 return y; 8 } 这样, 我们就可以用 r[0] 代表分子,r[1] 代表分母了, 如 : 1 Rational a(4,5); 2 cout << a[0] << "/" << a[1] << endl; 但是, 如果我们还希望用 r[0] 和 r[1] 对分子和分母赋值呢? 比如 r[0]=3, 上面的实现方式显 然是不行的 这个问题涉及到左值 左值 : 能出现在赋值号左边的量称为左值 比如普通变量是左值, 常量不是左值 怎样才能使得 r[0] 能出现在赋值号左边? 返回 r[0] 的引用 1 int & Rational::operator[](int idx) // 函数返回的是一个引用 2 { 3 if (idx == 0) 4 return x; 5 else 6 return y; 7 } 例 12.5 运算符 [] 的重载 1 #include <iostream> 2 3 using namespace std; 4 5 class Rational 6 { 7 public: 8 Rational() { x=0; y=1; } 9 Rational(int x, int y) { this->x=x; this->y=y; } 10 void display() { cout << x << "/" << y << endl; } 11 int & operator[](int idx); private:

140 128 第十二讲运算符重载与类型转换 14 int x, y; 15 }; int & Rational::operator[](int idx) // 重载 [], 返回的是引用 18 { 19 if (idx == 0) 20 return x; 21 else 22 return y; 23 } int main() 26 { 27 Rational a(4,5); cout << "a="; a.display(); 30 cout << endl; a[0]=3; a[1]=2; // 可以用 [] 进行赋值运算 33 cout << "a="; a.display(); return 0; 36 } 12.7 运算符重载注意事项 运算符 [] = -> () 必须以成员函数方式重载 运算符 () 通常表示强制类型转换, 如 double(x) 运算符 << >> 必须以非成员函数重载 ( 这两个运算符的重载涉及到输入输出流, 将在文件流中介绍 ) 算术运算符和关系运算符建议以非成员函数方式重载, 以便实现一些简单的自动类型转换 12.8 自动类型转换 为什么要自动类型转换? 实现对象与基本数据类型变量之间的运算 怎么实现? 将对象自动转换为基本数据类型, 或者将基本数据类型自动转换为对象 基本数据类型 对象 1 Rational a(1,2), b; 2 int c=3; 3 b = a + c; // 怎么实现?--> 将整数转换为有理数, 然后参与运算 (1) 实现方法 : 构造函数, 例如有理数与整数的加法运算

141 12.8 自动类型转换 129 例 12.6 自动类型转换 : 基本数据类型 对象 1 #include <iostream> 2 #include <cstdlib> 3 4 using namespace std; 5 6 class Rational 7 { 8 public: 9 Rational() { x=0; y=1; } 10 Rational(int x, int y) { this->x=x; this->y=y; } 11 Rational(int x) {this->x=x; y=1; }; // 构造函数, 整数转有理数 12 Rational operator+(const Rational &); // 一定要加 const! 13 void display() { cout << x << "/" << y << endl; } private: 16 int x, y; 17 }; Rational Rational::operator+(const Rational & p) 20 { 21 int newx = x*p.y + y*p.x; 22 int newy = y*p.y; 23 return Rational(newx, newy); 24 } int main() 27 { 28 Rational a(1,2), b; 29 int c=3; b = a + c; // 将 c 转换为有理数对象, 然后参与运算, 注意 :c 只能出现在加号右边! cout << "b="; b.display(); return 0; 36 } 上例中要把 c 放在加号的右边, 怎么实现它也能出现在左边, 即 b=c+a? 对象 基本数据类型 1 Rational a(1,2); 2 double b=0.8, c; 3 c = a + b; // 怎么实现?--> 将有理数转换为双精度数, 然后参与运算 (1) 实现方法 : 重载类型转换函数 ( 必须以成员函数方式 ) (2) 声明 : operator 转换函数名 (); (3) 定义 ( 假定在类外部定义 ):

142 130 第十二讲运算符重载与类型转换 类名 ::operator 转换函数名 () { 函数体 }; 注意 : 没有返回数据类型, 因为转换函数名就指定了返回数据类型 例 12.7 自动类型转换 : 对象 基本数据类型 1 #include <iostream> 2 #include <cstdlib> 3 4 using namespace std; 5 6 class Rational 7 { 8 public: 9 Rational() { x=0; y=1; } 10 Rational(int x, int y) { this->x=x; this->y=y; } 11 void display() { cout << x << "/" << y << endl; } 12 operator double(); // 重载转换函数 double() private: 15 int x, y; 16 }; Rational::operator double() // 重载转换函数 double() 19 { 20 return double(x)/y; 21 } int main() 24 { 25 Rational a(1,2); 26 double b=0.8, c; c = a + b; // 将 a 转换为双精度数, 然后参与运算 29 cout << "c=" << c << endl; return 0; 32 } 自动类型转换的注意点 : (1) 一个类可以重载类型转换函数, 实现对象到基本数据类型的转换, 也可以重载构造函数, 实 现基本数据类型到对象的转化, 但两者不能并存! (2) 若重载了类型转换函数, 则建议用非成员函数方式实现运算符重载, 并且形参使用 常引用 如 : 1 Rational operator+(const Rational & r1, const Rational & r2) 12.9 上机练习 练习 12.1 使用成员函数方式重载复数类的加法和减法

143 12.9 上机练习 131 练习 12.2 使用非成员函数方式重载复数的加法和减法运算 练习 12.3 使用成员函数方式重载有理数的比较运算

144 第十三讲继承与派生 继承是面向对象技术的一个重要概念 如果一个类 B 继承自另一个类 A, 就把这个 B 称为 A 的派生类, 而把 A 称为 B 的父类 继承可以使得派生类具有父类的各种属性和功能, 而不需要再次编写相同的代码 派生类在继承父类的同时, 还可以通过重新定义某些属性或改写某些方法, 来更新父类的原有属性和功能, 或增加新的属性和功能 13.1 继承与派生 类的派生 : 在已有类的基础上产生新类的过程 ; 类的继承 : 派生类继承了父类的特性, 包括数据成员和函数成员 ; 原有类称为基类或父类, 新类则称为派生类或子类 ; 派生类可以改造父类的特性, 也可以加入新的特性 ; 派生类也可以作为父类, 派生出新的子类 ; 继承和派生提高了代码的可重用性, 有利于软件开发 13.2 派生类的定义 class 派生类名 : 继承方式父类名 1, 继承方式父类名 2,... { }; 派生类成员声明 ; 关于派生的几点说明 : (1) 一个派生类可以有多个父类, 此时称为多重继承 (2) 一个派生类只有一个父类, 则称为单继承 (3) 一个父类可以派生出多个子类, 从而形成类族 继承方式 : (1) 继承方式 : 决定从父类继承的成员的访问控制 (2) 继承方式有三种 :public protected private, 缺省为 private (3) 派生类成员 : 从父类继承的成员 + 新增加的成员 (4) 继承是可传递的 : 从父类继承的特性可以传递给新派生的子类 类的派生过程 : (1) 吸收父类成员 : 派生类包含父类中除构造函数和析构函数外的所有非静态成员 (2) 改造父类成员 : 132

145 13.3 构造函数 通过继承方式改变父类成员的访问控制 - 对父类成员的屏蔽 ( 如果新成员与父类成员同名, 则缺省只能访问新成员 ) (1) 添加新成员 : 根据实际需要, 添加新的数据成员或函数成员 构造函数, 析构函数和静态成员不能被继承 派生类成员的访问控制 : 能否访问和怎样访问从父类继承得来的成员 (1) 这里主要强调派生类中新增成员和外部函数能否访问派生类中从父类继承的成员 (2) 继承方式不同, 访问控制不同 : 公有继承 (public) - 父类的公有和保护成员的访问属性保持不变 - 父类的私有成员不可直接访问私有继承 (private) - 父类的公有和保护成员都成为派生类的私有成员 - 父类的私有成员不可直接访问保护继承 (protected) - 父类的公有和保护成员都成为派生类的保护成员 - 父类的私有成员不可直接访问 几点注记 : (1) 从父类继承的成员函数对父类成员的访问不受影响 (2) 无论以何种方式继承, 父类的私有成员都不可直接访问 (3) 私有继承后, 父类成员 ( 特别是公有函数 ) 无法在以后的派生类中直接发挥作用, 相当于终止了父类功能的继续派生 因此, 私有继承较少使用 (4) 保护继承与私有继承的区别 : 父类成员 ( 特别是公有函数 ) 可以在以后的派生中作为保护成员继承下去 访问控制小结 : (1) 父类成员函数访问父类成员 : 正常访问 (2) 派生类成员函数访问派生类新增成员 : 正常访问 (3) 父类成员函数访问派生类新增成员 : 不能访问 (4) 派生类成员函数访问父类成员 : 取决于继承方式和父类成员本身访问属性 (5) 派生类外部函数 ( 非成员函数 ) 访问派生类所有成员 : 只能访问公有成员 (6) 派生类成员按访问属性可划分为下面四类 : - 不可访问成员 : 父类的私有成员 - 私有成员 : 父类继承的部分成员 + 新增的私有成员 - 保护成员 : 父类继承的部分成员 + 新增的保护成员 - 公有成员 : 父类继承的部分成员 + 新增的公有成员 13.3 构造函数 派生类不能继承父类的构造和析构函数, 必须自己定义 派生类对象的初始化 :

146 134 第十三讲继承与派生 - 派生类的构造函数只负责新增数据成员的初始化 - 从父类继承的成员需通过调用父类的构造函数进行初始化 派生类的构造函数只负责新增成员的初始化 从父类继承的成员需通过调用父类的构造函数进行初始化 派生类构造函数 ( 初始化参数列表 ) 派生类名 ( 总参数列表 ) : 父类 1( 参数 ),..., 父类 n( 参数 ), { }; 成员对象 1( 参数 ),..., 成员对象 m( 参数 ) 新增数据成员的初始化 ( 不包括继承的父类成员和其他类的对象 ); (1) 总参数列表中的参数需要带数据类型 ( 形参 ), 其他不需要 (2) 需要初始化的数据成员 : 父类成员 + 新增成员, 基本数据类型变量 + 类的对象 (3) 父类数据成员的初始化 : 调用父类构造函数 (4) 对象成员的初始化 : 调用对象所在类的构造函数 几点注记 (1) 在派生类构造函数的总参数列表中, 有一些参数是传递给父类的构造函数的 (2) 若父类使用不带形参的构造函数, 则可以省略 (3) 若成员对象使用不带形参的构造函数来初始化, 也可以省略 (4) 派生类构造函数执行的一般次序 - 调用父类的构造函数, 按被继承时声明的顺序执行 - 对派生类新增对象成员初始化, 按它们在类中声明的顺序执行 - 执行派生类的构造函数体的内容 例 13.1 派生类构造函数举例 ( 一 ) 1 #include <iostream> 2 #include <cstdlib> 3 4 using namespace std; 5 6 class B1 // 类 B1, 构造函数有参数 7 { 8 public: 9 B1(int i) { cout << "constructing B1 " << i << endl; } 10 }; class B2 // 类 B2, 构造函数有参数 13 { 14 public: 15 B2(int j) { cout << "constructing B2 " << j << endl; } 16 }; class B3 // 类 B3, 构造函数无参数 19 { 20 public:

147 13.3 构造函数 B3() { cout << "constructing B3 *" << endl; } 22 }; class C: public B2, public B1, public B3 // 派生类 C, 注意父类的顺序 25 { 26 public: 27 C(int a, int b, int c, int d) : B1(a), memberb2(d), memberb1(c), B2(b) 28 { x = a; } 29 void Showx() {cout << "x=" << x << endl; } private: 32 B1 memberb1; 33 B2 memberb2; 34 B3 memberb3; 35 int x; 36 }; int main() 39 { 40 C obj(1,2,3,4); obj.showx(); return 0; 45 } 程序运行结果为 1 constructing B2 2 2 constructing B1 1 3 constructing B3 * 4 constructing B1 3 5 constructing B2 4 6 constructing B3 * 7 x=1 例 13.2 派生类构造函数举例 ( 二 ) 1 #include <iostream> 2 #include <string> 3 4 using namespace std; 5 6 class Person // 父类 7 { 8 public: 9 Person(string & str, int age ) 10 { name=str; this->age = age; } 11 void show() 12 { cout << "Name: " << name << endl; 13 cout << "Age: " << age << endl; 14 }

148 136 第十三讲继承与派生 15 private: 16 string name; // 姓名 17 int age; // 年龄 18 }; class Student : public Person // 派生类 21 { 22 public: 23 Student(string & str, int age, int stuid) : Person(str, age) 24 { this->stuid = stuid; } 25 void showstu() 26 { this->show(); // 不能直接访问 name 和 age 27 cout << "Stuid: " << stuid << endl; 28 } 29 private: 30 int stuid; // 学号 31 }; int main() 34 { 35 string str="xi Jiajia"; 36 Student stu1(str, 18, ); stu1.showstu(); return 0; 41 } 如果 Student 中的成员函数 showstu 也取名为 show, 则该如何处理? 13.4 派生类成员的标识与访问 如果派生类中出现与父类同名的成员, 该如何处理? 屏蔽规则 (1) 如果存在两个或多个具有包含关系的作用域, 外层作用域声明的标识符在内层作用域可见, 但如果在内层作用域声明了同名标识符, 则外层标识符在内层不可见 (2) 父类是外层, 派生类是内层 (3) 若在派生类中新定义了与父类同名的成员, 则缺省使用新定义的成员 (4) 若在派生类中声明了与父类同名的新函数, 即使函数参数表不同, 从父类继承的同名函数的 所有重载形式都会被屏蔽 (5) 如何访问被屏蔽的成员 : 类名 + 作用域分辨符 :: 类名 :: 成员名 // 数据成员 类名 :: 成员名 ( 参数 ) // 函数成员 (6) 若派生类有多个父类, 且这些父类中有同名标识符, 则必须使用作用域分辨符来指定使用哪 个父类的标识符!

149 13.5 派生类的复制构造函数 137 (7) 通过作用域分辨符就明确地唯一标识了派生类中从父类继承的成员, 从而解决了成员同名问 题 13.5 派生类的复制构造函数 派生类复制构造函数的作用 : 调用父类的复制构造函数完成父类数据成员的复制, 然后再执行派生类数据成员的复制 在定义派生类的复制构造函数时, 需要为父类相应的复制构造函数传递参数 13.6 派生类的析构函数 派生类的析构函数只负责新增数据成员 ( 非对象成员 ) 的清理工作 派生类析构函数的定义与普通析构函数一样 父类成员和新增对象成员的清理工作由父类和对象成员所属类的析构函数负责 析构函数的执行顺序与构造函数相反 : - 执行派生类析构函数体 - 执行派生类对象成员的析构函数 - 执行父类的析构函数 13.7 类型兼容规则 基本规则 (1) 在需要父类对象出现的地方, 可以使用派生类 ( 以公有方式继承 ) 的对象来替代 (2) 通俗解释 : 公有派生类实际具备了父类的所有功能, 凡是父类能解决的问题, 公有派生类都可以解决 (3) 替代后, 只能使用从父类继承的成员, 即派生类只能发挥父类的作用 类型兼容规则中的替代包括以下情况 : (1) 派生类的对象可以隐式转化为父类对象 (2) 派生类的对象可以初始化父类的引用 (3) 派生类的指针可以隐式转化为父类的指针 13.8 虚父类在多重继承时, 如果派生类的部分或全部父类是从另一个共同父类派生而来, 则在最终的派生类中会保留该间接共同父类数据成员的多份同名成员 这时不仅会存在标识符同名问题, 还会占用额外的存储空间, 同时也增加了访问这些成员时的困难, 且容易出错 事实上, 在很多情况下, 我们只需要一个这样的成员副本 ( 特别是函数成员 ) 虚父类 : 当某个类的部分或全部父类是从另一个共同父类派生而来时, 可以将这个共同父类设置成虚父类, 这时从不同路径继承来的同名数据成员在内存中只存放一个副本, 同一个函数名也只有一个映射

150 138 第十三讲继承与派生 派生时将父类声明为虚父类 class 派生类名 : virtual 继承方式父类名 { }; 虚父类并不是在声明父类时声明的, 而是在声明派生类时, 指定继承方式时声明的 一个类可以在生成某个派生类时作为虚父类, 而在生成另一个派生类时不作为虚父类 为了保证虚父类成员在派生类中只继承一次, 应当在该父类的所有直接派生类中声明其为虚父类, 否则仍然可能会出现对该父类的多次继承 具有虚父类的派生类的构造函数 : - 如果虚父类的构造函数带有参数, 则在所有直接或间接继承虚父类的派生类中, 都必须在构造函 数的初始化列表中包含虚父类构造函数的直接调用 ; - 如果虚父类的构造函数不带参数, 则可以省略 例 13.3 虚父类举例 1 #include <iostream> 2 #include <string> 3 4 using namespace std; 5 6 class Person // 公共父类 Person 7 { 8 public: 9 Person(const string & str, int a) // 构造函数 10 { name=str; age=a; } 11 protected: // 保护成员 12 string name; 13 int age; 14 }; class Teacher : virtual public Person // 声明 Person 为公用继承的虚父类 17 { 18 public: 19 Teacher(const string & str, int a, const string & tit):person(str,a) 20 { title=tit; } // 虚父类的构造函数带有参数, 因此必须包含虚父类构造函数的直接调用 21 protected: 22 string title; // 职称 23 }; class Student : virtual public Person // 声明 Person 为公用继承的虚父类 26 { 27 public: 28 Student(const string & str, int a, float sco) // 构造函数 29 : Person(str,a), score(sco){ } // 必须包含虚父类构造函数的直接调用 30 protected: 31 float score; // 成绩

151 13.9 上机练习 }; class Graduate : public Teacher, public Student // 多重继承 35 { 36 public: 37 Graduate(const string & str, int a, const string & tit, float sco, float w) 38 : Person(str,a), Teacher(str,a,tit), Student(str,a,sco), wage(w){ } 39 // 必须包含虚父类构造函数的直接调用 40 void show() 41 { 42 cout << "name:" << name << endl; 43 cout << "age:" << age << endl; 44 cout << "score:" << score << endl; 45 cout << "title:" << title << endl; 46 cout << "wage:" << wage << endl; 47 } 48 private: 49 float wage; // 工资 50 }; int main() 53 { 54 Graduate grad("xi Jiajia", 24, "assistant", 89.5, ); 55 grad.show(); 56 return 0; 57 } 在初始化 Graduate 类的对象时, 只会通过 Graduate 的构造函数中的 Person(str,a) 来初 始化从 Person 类继承的数据成员,Teacher(str,a,tit) 和 Student(str,a,sco) 中对 Person 构造函数的直接调用会被忽略 1 // 如果将 Graduate 的构造函数改为下面的语句, 程序运行结果不变 2 Graduate(const string & str, int a, const string & tit, float sco, float w) 3 : Person(str,a), Teacher("Tea",2,tit), Student("Stu",3,sco), wage(w){ } 13.9 上机练习练习 13.1 设计一个名为 Point 的类练习 13.2 在 Point 类的基础上定义派生类 Point3D 练习 13.3 设计 Clock 类,Weekday 类,Mytime 类

152 第十四讲多态 14.1 什么是多态 多态是指同样的消息被不同类型的对象接收时会导致不同的行为, 即接口的多种不同实现方式 一个典型例子就是函数重载 多态是面向对象程序设计的关键技术之一, 若程序设计语言不支持多态, 不能称为面向对象的语言 多态 封装和继承是面向对象程序设计的三大特征 常见的多态实现方式 : (1) 函数重载, 运算符重载 (2) 虚函数 (3) 模板 14.2 虚函数 为什么虚函数 : 我们知道, 用派生类对象替代父类的对象后, 只能发挥父类的功能 比如父类中定义了成员函数 show, 派生类中也有成员函数 show, 则用派生类对象替代父类对象后, 只能发挥父类的 show 功 能 但能否仍然发挥派生类的 show 功能呢?C++ 中的虚函数就是用来解决这个问题 虚函数的声明 : 只需要在函数声明前面增加 virtual 关键字 virtual 数据类型名函数名 ( 形参列表 ) 例 14.1 虚函数举例一 1 #include <iostream> 2 #include <string> 3 4 using namespace std; 5 6 class Person // 父类 7 { 8 public: 9 Person(const string & name, int age ) 10 { 11 this->name = name; this->age = age; 12 } 13 virtual void show() // 关键字 virtual, 即声明为虚函数 14 { 15 cout << "Name: " << name << endl; 16 cout << "Age: " << age << endl; 140

153 14.2 虚函数 } 18 private: 19 string name; // 姓名 20 int age; // 年龄 21 }; class Student : public Person // 派生类 24 { 25 public: 26 Student(const string & name, int age, int stuid) : Person(name, age) 27 { 28 this->stuid = stuid; 29 } 30 virtual void show() // 派生类中可以不带 virtual 31 { 32 Person::show(); 33 cout << "Stuid: " << stuid << endl; 34 } 35 private: 36 int stuid; // 学号 37 }; int main() 40 { 41 Person p1("gao Dai", 20); 42 Student stu1("xi Jiajia", 18, ); 43 Person * p; p = &p1; 46 p->show(); // 父类指针 p 指向父类对象, 因此调用的是父类的 show() p = &stu1; 49 pstu->show(); // 父类指针 p 指向派生类对象, 此时调用的是派生类的 show() return 0; 52 } 在这个例子里,p 是父类指针, 当它指向的对象是父类的对象时, 则实现的时父类的功能, 而当它 指向派生类的对象时, 则能实现派生类的功能 这表明, 父类指针可以按照父类的方式来做事, 也可以按照派生类的方式来做事, 它有多种形态, 或者说有多种表现方式, 这种现象就是多态 (Polymorphism) 派生类中声明虚函数时, 关键字 virtual 可以省略, 这意味着, 只要在父类中声明的虚函 数, 则所有派生类中的同名函数 ( 形参也相同 ) 都是虚函数 虚函数提供了一种通过基类访问派生类 ( 包括直接派生和间接派生 ) 的功能的机制 ; 虚函数只能借助于指针或引用才能达到多态的效果, 否则无法实现多态, 比如下面的例子就无法 实现多态 例 14.2 虚函数举例二 1 // 2 // 前面部分的程序同上例

154 142 第十四讲多态 3 // 4 int main() 5 { 6 Student stu1("xi Jiajia", 18, ); 7 Person p1 = stu1; p1.show(); // 不能实现多态, 调用的仍然是 Person::show() 11 return 0; 12 } 引用一旦依附到某个对象上后就不能修改, 不如指针灵活, 因此在多态方面缺乏表现力, 所 以实现多态时一般是用指针 关于虚函数的几点说明 只需在声明处加关键字 virtual, 函数定义 ( 在外部定义 ) 时不能加 ; 如果派生类中没有对虚函数的具体定义, 则仍使用父类的虚函数 ; 构造函数不能是虚函数, 但析构函数可以 ; 对于具有复杂继承关系的大中型程序, 多态可以增加其灵活性, 让代码更具有表现力 构成多态的条件 : (1) 必须存在继承关系 ; (2) 继承关系中必须有虚函数, 并且它们形成屏蔽关系, 即父类与派生类中存在具有相同函数原 型的虚函数 ; (3) 只能通过父类的指针或引用来调用虚函数 例 14.3 虚函数举例三 1 #include <iostream> 2 3 using namespace std; 4 5 class Point // 父类 6 { 7 public: 8 Point() { x = 0; } 9 virtual void Setpoint() { x = -1; } 10 virtual void Setpoint(float a) { x = a; } 11 virtual void Display() 12 { 13 cout << "x=" << x << endl; 14 } 15 protected: 16 float x; 17 }; class Point2D : public Point // 派生类 20 { 21 public: 22 Point2D() { x = 0; y = 0; }

155 14.3 纯虚函数与抽象类 virtual void Setpoint() { x = 1; y = 1;} 24 virtual void Setpoint(float a, float b) { x = a; y = b; } 25 virtual void Display() 26 { 27 cout << "(x,y)=(" << x << "," << y << ")" << endl; 28 } 29 private: 30 int y; 31 }; int main() 34 { 35 Point * p = new Point2D(); p->setpoint(); // OK, 调用派生类的虚函数 38 p->display(); p->setpoint(2); // OK, 调用父类的函数 41 p->display(); // p->setpoint(3,4); // ERROR 44 // p->display(); return 0; 47 } 在上例中, 如果 Point2D 中没有把 void Setpoint(float a, float b) 声明为虚函数, 则程序能否正常运行? 有了虚函数, 就可能出现这种情况 : 一个函数的调用并不是在编译时刻被确定的, 而是在程序运 行时才被确定 比如下面的例子, 只有当程序运行时, 根据指针 p 指向的是父类对象还是派生 类对象, 才能决定调用的是父类的成员函数还是派生类的成员函数 这种现象就称为推迟联编 或动态联编 1 void fun(person * p) 2 { 3 p->show(); // Person:show() or Student:show()? 程序运行是才能确定 4 } // 同一段代码, 可以产生不同效果 多态 由于编写代码的时候并不能确定被调用的是父类的成员函数还是派生类的成员函数, 所以 称为 虚 函数 14.3 纯虚函数与抽象类 纯虚函数的声明 : virtual 类型标识符函数名 ( 形参列表 )=0; // "=0" 表示一个虚函数为纯虚函数 在声明虚函数时, 末尾 =0, 表明此函数为纯虚函数

156 144 第十四讲多态 纯虚函数没有函数体 纯虚函数用来规范派生类的行为, 实际上就是所谓的 接口, 它在父类中只声明不定义 它的作用仅仅是告诉使用者, 我的派生类都会有这个函数 如果类中有纯虚函数, 则表示 : 我是一个抽象类, 不能实例化, 即不能创建对象 抽象类 : 含有纯虚函数的类称为抽象类 - 抽象类是一种特殊的类, 它通常是为了派生而建立的, 一般处于继承层次结构的较上层 ; - 抽象类不能用来声明对象 ( 即不能实例化 ), 只能用来派生, 所以是 抽象 的 ; - 如果纯虚函数在派生类中也没有具体定义, 则这个派生类还是个抽象类 ; - 抽象类的主要作用是将有关的功能作为接口组织在一个继承层次结构中, 由它为派生类提供一个公共的根, 具体实现由派生类完成 定义纯虚函数的一个目的就是让父类不可实例化 事实上, 有些父类只是用来派生, 如动物, 用它来声明对象没有任何实际意义 例 14.4 纯虚函数举例 1 #include <iostream> 2 #include <string> 3 4 using namespace std; 5 6 class Person // 父类 7 { 8 public: 9 Person(const string & name, int age ) 10 { 11 this->name = name; this->age = age; 12 } 13 virtual void show()=0; // 纯虚函数 14 protected: 15 string name; // 姓名 16 int age; // 年龄 17 }; class Teacher: public Person // 派生类 20 { 21 public: 22 Teacher(const string & name, int age, const string & title): Person(name, age) 23 { 24 this->title = title; 25 } 26 void show() // 纯虚函数在派生类中要有定义, 即实例化 27 { 28 cout << "Name: " << name << endl; 29 cout << "Age: " << age << endl; 30 cout << "title: " << title << endl; 31 } 32 private: 33 string title; // 职称 34 };

157 14.4 模板 class Student : public Person // 派生类 37 { 38 public: 39 Student(const string & name, int age, int stuid) : Person(name, age) 40 { 41 this->stuid = stuid; 42 } 43 void show() // 每个派生类中都要实例化, 否则该派生类仍然是抽象类 44 { 45 cout << "Name: " << name << endl; 46 cout << "Age: " << age << endl; 47 cout << "Stuid: " << stuid << endl; 48 } 49 private: 50 int stuid; // 学号 51 }; int main() 54 { 55 Teacher teacher("shu Fen", 38, "Professor"); 56 Student stu("xi Jiajia", 20, ); 57 Person * p; p = &teacher; 60 p->show(); // Teacher::show() 61 cout << endl; p = &stu; 64 p->show(); // Student::show() 65 cout << endl; return 0; 68 } 14.4 模板 在 C++ 中, 数据类型也可以通过参数来传递 : 在函数定义时可以不指明具体的数据类型, 当发生 函数调用时, 编译器可以根据实参确定数据类型 这就是数据类型的参数化 为什么模板 : 设计更具通用性的函数和类, 使得它们可以作用于不同类型的数据, 使得程序更加简洁和高效 模板是 C++ 中最强大的特性之一 模板提供了在函数中将类型作为参数的功能 C++ 中的模板有模板函数和模板类 值和类型是一个数据的两个基本特征, 它们在 C++ 中都可以被参数化

158 146 第十四讲多态 14.5 模板函数 所谓模板函数, 就是一个通用函数, 它涉及的数据 ( 包括返回值 形参 局部变量 ) 的类型可以 不具体指定, 而是用一个虚拟的类型来代替 ( 实际上是用一个标识符来占位 ), 等发生函数调用时再根 据传入的实参来确定真正的类型 模板函数的声明和定义 : template <typename T> // 模板头,typename 是关键字,T 是形参, 称为类型参数 T fun(t x, T y) {... } template <typename T1, typename T2, typename T3> // 也可以有多个类型参数 T3 fun(t1 x, T2 y) {... } (1) 模板头和函数名是一个整体, 为了使得代码更加清晰, 模板头通常独占一行 ; (2) 一但定义了模板函数, 就可以用类型参数来声明和定义函数了, 也就是说, 原来使用 int, float, double 等数据类型标识符的地方, 都可以用类型参数来代替 ; (3) 调用模板函数时, 用于传递给类型参数的实参可以是基本数据类型, 也可以是用户自己定义 的类 类型参数原则上可以任意合法的标识符, 如 typename mytype, 但使用 T, T1, T2,... 已经形成了一种惯例 关键字 typename 也可以用 class 替代, 它们没有任何区别 C++ 早期对模板的支持并不严谨, 没有引入新的关键字, 而是用 class 来指明类型参数, 但是 class 已经用在类的定义中了, 这样做显得不太友好, 所以后来引入一个新的关键字 typename, 专门用来定义类型参数 不过至今仍然有很多代码在使用 class, 包括 C++ 标准库 一些开源程序等 例 14.5 模板函数举例一 1 #include <iostream> 2 3 using namespace std; 4 5 template <typename T> 6 T Max(T x, T y) 7 { 8 if (x >= y) 9 return x; 10 else 11 return y; 12 } int main() 15 {

159 14.5 模板函数 int a=2, b=3; 17 double e=2.2, f=3.3; cout << "max(a,b)=" << Max<int>(a,b) << endl; // 将实参 int 传给形参 T 20 cout << "max(e,f)=" << Max<double>(e,f) << endl; // 将实参 double 传给形参 T return 0; 23 } 例 14.6 模板函数举例二 1 #include <iostream> 2 3 using namespace std; 4 5 template <typename T1, typename T2, typename T3> 6 T3 Max(T1 & x, T2 & y) 7 { 8 if (x >= y) 9 return x; 10 else 11 return y; 12 } int main() 15 { 16 int a=2, b=3; 17 double e=2.2, f=2.3; cout << "max(a,e)=" << Max<int,double,float>(a,e) << endl; 20 // 分别将 int, double, float 传给 T1, T2 和 T return 0; 23 } 例 14.7 模板函数举例三 1 #include <iostream> 2 3 using namespace std; 4 5 class Rational 6 { 7 public: 8 Rational() { x=0; y=1; } 9 Rational(int x, int y) { this->x=x; this->y=y; } 10 Rational operator+(const Rational & p); 11 void Display() { cout << x << "/" << y << endl; } 12 private: 13 int x, y; 14 }; Rational Rational::operator+(const Rational & p)

160 148 第十四讲多态 17 { 18 int newx = x*p.y + y*p.x; 19 int newy = y*p.y; 20 return Rational(newx, newy); 21 } template <typename T> // 模板函数 24 T Add(T & x, T & y) 25 { 26 return x+y; 27 } int main() 30 { 31 Rational a(4,5), b(7,3), c; c = Add<Rational>(a,b); // 用类名 Rational 作为类型实参 34 cout<<"a+b="; 35 c.display(); return 0; 38 } 在调用模板函数时, 类型实参可以省略, 编译器会根据传入的数据自动推断其数据类型 ( 包括基 本数据类型和用户自定义的类 ) 例 14.8 模板函数举例四 1 #include <iostream> 2 3 using namespace std; 4 5 template <typename T> 6 T Div(T x, T y) 7 { 8 return x/y; 9 } int main() 12 { 13 int a=3, b=2; 14 double e=3.0, f=2.0; cout << " 自动判断数据类型 :a/b=" << Div(a,b) << endl; // 省略类型实参 int 17 cout << " 自动判断数据类型 :e/f=" << Div(e,f) << endl; // 省略类型实参 double 18 cout << " 明确指定数据类型 :a/b=" << Div<double>(a,b) << endl; // 明确指定类型实参 return 0; 21 } 14.6 模板类 C++ 除了支持模板函数, 还支持模板类 模板函数的类型参数可用于声明和定义函数, 而模板类 的类型参数则可以用在类的声明和实现中 模板类的目的同样是将数据类型参数化

161 14.6 模板类 149 前面介绍的向量类 vector 和字符串类 string 都是模板类 模板类的声明 : template <typename 类型参数 1, typename 类型参数 2,...> class 类名 { }; // 可以直接使用类型参数 在类外部定义成员函数时, 仍然需要带上模板头 : template <typename 类型参数 1, typename 类型参数 2,...> 类型标识符类名 < 类型参数 1, 类型参数 2,...>:: 函数名 ( 形参列表 ) { }; // 函数体中可以直接使用类型参数 - 需要注意, 除模板头以外, 类名后面也要带上类型参数, 但不用加 typename 例 14.9 模板类举例一 1 #include <iostream> 2 3 using namespace std; 4 5 template <typename T> 6 class Point 7 { 8 public: 9 Point(T a, T b); 10 T Getx(); 11 T Gety(); private: 14 T x, y; 15 }; template <typename T> 18 Point<T>::Point(T a, T b) 19 { x=a; y=b; } template <typename T> 22 T Point<T>::Getx() 23 { return x; } template <typename T> 26 T Point<T>::Gety() 27 { return y; } int main()

162 150 第十四讲多态 30 { 31 Point<int> A(4,5); 32 cout << "A.x=" << A.Getx() << endl; Point<float> B(4.2,5.3); 35 cout << "B.x=" << B.Getx() << endl; return 0; 38 } 与模板函数不同的是, 用模板类创建对象时, 必须明确指明数据类型, 编译器不能根据给 定的数据判断其数据类型 模板类的类型参数可以带缺省值 例 模板类举例二 1 #include <iostream> 2 3 using namespace std; 4 5 template <typename T=int> // 类型参数带缺省值 6 class Point 7 { 8 public: 9 Point(T a, T b); 10 T Getx(); 11 T Gety(); private: 14 T x, y; 15 }; template <typename T> 18 Point<T>::Point(T a, T b) 19 { x=a; y=b; } template <typename T> 22 T Point<T>::Getx() 23 { return x; } template <typename T> 26 T Point<T>::Gety() 27 { return y; } int main() 30 { 31 Point<> A(4.2,5.3); // 使用缺省值 32 cout << "A.x=" << A.Getx() << endl; Point<float> B(4.2,5.3); 35 cout << "B.x=" << B.Getx() << endl; return 0;

163 14.7 上机练习 } 几点注记 : - 模板增强了 C++ 语言的灵活性, 虽然不是 C++ 的首创, 但是却在 C++ 中大放异彩 ; - C++ 模板有着复杂的语法, 我们这里只是做了简单介绍 ; - C++ 模板非常重要, 整个标准库几乎都是使用模板来开发的,STL(Standard Template Library, 标准模板库 ) 更是经典之作 14.7 上机练习 练习 14.1 设计 Real 类,Rational 类,Complex 类 练习 14.2 设计 Point2D 类,Point3D 类, 定义模板函数

164 第十五讲文件流与输出输入重载 15.1 输入输出流 (1) 在 C++ 中, 所有的输入输出都通过 流 来描述的 (2) 输入流 : 数据流向程序, 即 input (3) 输出流 : 数据从程序中流出, 即 output (4) 具体实现方法 : 流类和流对象 15.2 文件流类与文件流对象 C++ I/O 库中定义的流类类名 作用 头文件 ios 抽象父类 iostream istream 通用输入流和其他输入流的父类 iostream ostream 通用输出流和其他输出流的父类 iostream 通用输入输出流和其他输入输出流的父类 ifstream 输入文件流类 fstream ofstream 输出文件流类 fstream 输入输出文件流类 istrstream 输入字符串流类 strstream ostrstream 输出字符串流类 strstream 输入输出字符串流类 各流类继承关系 文件流类 ( 需加头文件 :#include <fstream>) ofstream ifstream 向文件写入数据 从文件读取数据 152