华东师范大学：《C++ 语言程序设计》课程教学资源（应用阅读）C++ 程序设计简明讲义（共十六讲）

《C++程序设计》简明讲义* 潘建瑜 华东师范大学·数学科学学院 2023年9月 又供课堂数学便 本讲义仅供课堂教学使用 ttps://math.ecnu.edu.cn/~jypar

《C++ 程序设计》简明讲义* 潘建瑜 华东师范大学 • 数学科学学院 2023 年 9 月 *本讲义仅供课堂教学使用 https://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传

目录 第一讲计算机基础 11信息的表示与存储。. 1.1.1计算机的数字系统 1.1.2 常见的数制及它们之间的转换，········ 1.13 一讲制数的绵码表示 3 1.2算法 4 1.2.1什么是算法 4 12.2 算法的特征与评价 4 1.2.3算法的描述方法与基本控制结构 5 5 14果后练习 6 第二讲C+编程基础 7 2.1C++语言概述 7 2.1.1 C+源程序结构 8 2.1.2C++源程序书写规范 8 2.1.3 程序编译 9 2.2C+基础知识. 9 2.2.1 C+字符集，标识符，关键字 9 2.2.2C++数据类型 2.2.3 变量与常量 2.2.4 typedef与枚举 13 2.2.5 2.2.6常用数学函数 16 23C+简单输入输出. 7 2.3.1输入输出语句 24程序示例 伊 第三讲选择与循环 20 3.1 关系运算与逻辑运算 20 3.2选择结构. 21 3.2.1F语句 21

目 录 第一讲 计算机基础 1 1.1 信息的表示与存储 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 计算机的数字系统 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 常见的数制及它们之间的转换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.3 二进制数的编码表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 什么是算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 算法的特征与评价 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 算法的描述方法与基本控制结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 课后阅读 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 课后练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 第二讲 C++ 编程基础 7 2.1 C++ 语言概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 C++ 源程序结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2 C++ 源程序书写规范 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 程序编译 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 C++ 基础知识 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 C++ 字符集, 标识符, 关键字 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 C++ 数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3 变量与常量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.4 typedef 与枚举 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.5 运算与表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.6 常用数学函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 C++ 简单输入输出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.1 输入输出语句 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.2 操纵符 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 程序示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 第三讲 选择与循环 20 3.1 关系运算与逻辑运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 选择结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.1 IF 语句 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 iii 仅供课堂教学使用，请勿外传

.iv. 目录 3.2.2 SWITCH结构 22 3.3循环结构 3.3.1WHLE循环. 3 332 DO WHILE循环 3.3.3FOR循环. 23 33.4 循环的非正常终止 3.4程序示例 25 3.5应用：定积分的数值计算 3.6上机练习.. 第四讲函数 4.1函数的声明、定义与调用 4.2函数间的参数传递 31 43内联函数，.， 3 4.4函数嵌套与递归 32 45数据的作用域 4.6形参带缺省值 35 47函数重 4.8 预编译处理与多文件结构 36 4.9应用：蒙特卡罗算法 4.10上机练习 39 第五讲数组 5.1一维数组 42 5.2 二维数组 43 53数组作为承数参数 5.4字符（字符数组）】 子 5.5上机练习····· 第六讲指针 0 61指针的定义与运算 50 6.2指针与一维数组 52 63指针与二维数组， 53 6.4行指针与二级指针 54 6.4.1行指针 5 6.4.2二级指针 54 6.5指针与引用. 6.6指针与函数 55 67特久动春内军分配 5 68 应用：矩阵乘积的快速算法··· 57 6.9应用：Gauss消去法求解线性方程组 http://math.ecnu.edu.cn/-jypan

· iv · 目 录 3.2.2 SWITCH 结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 循环结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.1 WHILE 循环 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.2 DO WHILE 循环 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.3 FOR 循环 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.4 循环的非正常终止 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 程序示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.5 应用: 定积分的数值计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.6 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 第四讲 函数 28 4.1 函数的声明、定义与调用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2 函数间的参数传递 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 内联函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4 函数嵌套与递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.5 数据的作用域 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.6 形参带缺省值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.7 函数重载 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.8 预编译处理与多文件结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.9 应用: 蒙特卡罗算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.10 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 第五讲 数组 42 5.1 一维数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.2 二维数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.3 数组作为函数参数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.4 字符串（字符数组） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.5 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 第六讲 指针 50 6.1 指针的定义与运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2 指针与一维数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.3 指针与二维数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.4 行指针与二级指针 ∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.4.1 行指针 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.4.2 二级指针 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.5 指针与引用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.6 指针与函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.7 持久动态内存分配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.8 应用: 矩阵乘积的快速算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.9 应用: Gauss 消去法求解线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传

目录 6.10上机练习 第七讲简单输入输出 60 7.1C+基本输入输出(WO)流 60 61 7.3C语言文件读写 7.3.1 文件的打开和关闭 62 7.3.2 文本文件的读写 7.3.3 二进制文件的读写 63 7.3.4其他文件操作作 6 7.4上机练习 第八讲排序算法及其C+实现 66 8.1引言 66 8.2选择排序 67 8.3插入排序 67 8.4希尔排字 67 8.5冒泡排序 68 8.6快速排序 8.7上机练习 69 第九讲类与对象基础1 71 9.1为什么面向对象 71 9.2类和对象基本操作 72 93构浩函数， 9.4复制构造函数 9.5匿名对象. 9.6类与对象举例：游泳池 78 9.7析构函数····· 9.8 上机练习 79 第十讲类与对象基础Ⅱ 81 10.1类的组合，. 81 10.2结构体与联合体 83 10.3类作用域 10.4静态成员 84 10.5友元关系 10.6类的UML描述 86 10.7上机练习. 第十一讲类与对象基础Ⅲ 11.1常对象与常成员 http://math.ecnu.edu.cn/-jypan

目 录 · v · 6.10 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 第七讲 简单输入输出 60 7.1 C++ 基本输入输出 (I/O) 流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 7.2 C 语言格式化输出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.3 C 语言文件读写 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.3.1 文件的打开和关闭 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.3.2 文本文件的读写 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.3.3 二进制文件的读写 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.3.4 其他文件操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.4 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 第八讲 排序算法及其 C++ 实现 66 8.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 8.2 选择排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.3 插入排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.4 希尔排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.5 冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 8.6 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 8.7 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 第九讲 类与对象基础 I 71 9.1 为什么面向对象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 9.2 类和对象基本操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 9.3 构造函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 9.4 复制构造函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 9.5 匿名对象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 9.6 类与对象举例: 游泳池 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 9.7 析构函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 9.8 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 第十讲 类与对象基础 II 81 10.1 类的组合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 10.2 结构体与联合体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 10.3 类作用域 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 10.4 静态成员 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 10.5 友元关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 10.6 类的 UML 描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 10.7 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 第十一讲 类与对象基础 III 88 11.1 常对象与常成员 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传

i 目录 11.2对象数组与对象指针 89 113动态对象 91 1l.4向量类：vector. 91 1l.5字符串类：string.· 11.5.1字符串匹配算法· 96 11.6上机练习 第十二讲运算符重载与自动类型转换 99 12.1为什么要重载运算符 99 12.2怎么实现运算符重载 100 123运算符重载：成员函数方式」 100 12.4运算符重载：非成员函数方式 101 12.5成员函数or非成员函数g 102 12.6左值与运算符「1的重载 102 12.7自动类型转换 103 12.8上机练习 104 第十三讲继承与派生 105 13.1继承与派生· 105 13.2派生类的定义 105 13.3派生类构造函数 107 134派生类新增成员与父类成员同名问题 108 13.5派生类的复制构造函数 108 13.6派生类的析构函数 108 13.7类型兼容规则 108 13.8虚父类…………… 109 139上机练习。···… 110 第十四讲多态 111 14.1什么是多态 111 14.2虚函数 111 14.3纯虚函数与抽象类 113 14.3.1纯虚函数 113 14.3.2抽象类 113 14.3.3举例 113 14.4模板 113 14.5模板函数 I 14.6模板类 115 14.7上机练习... 116 第十五讲文件流与输出输人重载 117 http://math.ecnu.edu.cn/~-jypan

· vi · 目 录 11.2 对象数组与对象指针 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 11.3 动态对象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 11.4 向量类: vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 11.5 字符串类: string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 11.5.1 字符串匹配算法 ∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 11.6 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 第十二讲 运算符重载与自动类型转换 99 12.1 为什么要重载运算符 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 12.2 怎么实现运算符重载 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 12.3 运算符重载: 成员函数方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 12.4 运算符重载: 非成员函数方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 12.5 成员函数 or 非成员函数？ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 12.6 左值与运算符 [] 的重载 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 12.7 自动类型转换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 12.8 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 第十三讲 继承与派生 105 13.1 继承与派生 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 13.2 派生类的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 13.3 派生类构造函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 13.4 派生类新增成员与父类成员同名问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 13.5 派生类的复制构造函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 13.6 派生类的析构函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 13.7 类型兼容规则 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 13.8 虚父类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 13.9 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 第十四讲 多态 111 14.1 什么是多态 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 14.2 虚函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 14.3 纯虚函数与抽象类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 14.3.1 纯虚函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 14.3.2 抽象类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 14.3.3 举例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 14.4 模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 14.5 模板函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 14.6 模板类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 14.7 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 第十五讲 文件流与输出输入重载 117 http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传

目录 vii. 15.1输入输出流········· 117 15.2文件流类与文件流对象 117 15.3文件的打开与关闭........ 118 15.4文件读写：文本文件与二进制文件 119 15.5移动或获取文件读写指针 120 15.6重载.·. 444 121 15.7上机练习..... 121 第十六讲标准模板库 123 16.1STL标准模板库 4 123 16.2容器.····· 123 16.3算法····· 44 125 16.4迭代器 ·..126 仅供课堂教学使用 http://math.ecnu.edu.cn/~jypan

目 录 · vii · 15.1 输入输出流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 15.2 文件流类与文件流对象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 15.3 文件的打开与关闭 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 15.4 文件读写: 文本文件与二进制文件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 15.5 移动或获取文件读写指针 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 15.6 重载 > . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 15.7 上机练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 第十六讲 标准模板库 123 16.1 STL 标准模板库 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 16.2 容器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 16.3 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 16.4 迭代器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传

第一讲计算机基础 本讲主要内容： ·数制：二进制、八进制、十进制和十六进制 ·二进制的表示形式：原码，反码，补码 ·算法基本概念 ·什么是算法 ·算法的特征与评价 ,算法的描述方法与基本控制结构 1.1信总的表示与存储 1.1.1计算机的数字系统 (1)计算机内部的信息的分类 ·控制信息：指令集，负责软硬件之间的交互，如：X86,ARM,RISC-VW ·数据信息：包括数值信息和非数值信息：其中数值信息包括整数、浮点数等：非数值信息包括 字符（字符申）和逻辑数据等。 (②)信息的存储单位： ·信息存储的基本单位有：二进制位(bit,简记b)和字节(Bye,简记B): ·计算机的最小存储单元是字节，一个字节由8个二进制位组成，即1B=8b ·其它存储单位有：KB,MB,GB,TB,PB,EB等等： 个英文字符占一个字节，而一个汉字占两个字节 (3)计算机数字系统： ·计算采用的是二进制数字系统基本符号是0和1： ·优点：易于物理实现、运算简单、可靠性高、通用性强； 。缺点：可读性差 11.2常见的数制及它之间的转换 (①)常见数制：二进制、八进制、十进制和十六进制。 (2)二进制转十进制：各位数字与它的权相乘，然后相加。 例1.1（二进制转十进制 (101.11)2=1×22+0×2+1×22+1×2-1+1×2-2=(5.75)10

第一讲 计算机基础 本讲主要内容: • 数制: 二进制、八进制、十进制和十六进制 • 二进制的表示形式: 原码, 反码, 补码 • 算法基本概念 ­ 什么是算法 ­ 算法的特征与评价 ­ 算法的描述方法与基本控制结构 1.1 信息的表示与存储 1.1.1 计算机的数字系统 (1) 计算机内部的信息的分类: • 控制信息: 指令集, 负责软硬件之间的交互, 如: X86, ARM, RISC­V; • 数据信息: 包括数值信息和非数值信息; 其中数值信息包括整数、浮点数等; 非数值信息包括 字符（字符串）和逻辑数据等. (2) 信息的存储单位: • 信息存储的基本单位有: 二进制位（bit, 简记 b）和字节（Byte, 简记 B）; • 计算机的最小存储单元是字节, 一个字节由 8 个二进制位组成, 即 1B=8b; • 其它存储单位有: KB, MB, GB, TB, PB, EB 等等; • 一个英文字符占一个字节, 而一个汉字占两个字节. (3) 计算机数字系统: • 计算采用的是二进制数字系统, 基本符号是 0 和 1; • 优点: 易于物理实现、运算简单、可靠性高、通用性强; • 缺点: 可读性差. 1.1.2 常见的数制及它们之间的转换 (1) 常见数制: 二进制、八进制、十进制和十六进制. (2) 二进制转十进制: 各位数字与它的权相乘, 然后相加. 例 1.1 (二进制转十进制) (101.11)2 = 1 × 2 2 + 0 × 2 1 + 1 × 2 2 + 1 × 2 −1 + 1 × 2 −2 = (5.75)10 1 仅供课堂教学使用，请勿外传

…2 第一讲计算机基础 白注记：入进制和十六进制转化为十进制的方法类似 (3)十进制转二进制 例12（十进制整数转化为二进制整数）：“除2取余，逆序排列”，即辗转相除法. 234 余数 低位 7 →3410=1000102 11 0 高位 凸注记：十进制整教转化为八进制或十六进制整数的方法类似， 例1.3（十进制纯小数转化为二进纯小数：“乘2取整，顺序排列”，即每次乘以2后去掉整数部 分，不断乘下去，直到小数部分为0或达到指定的精度为止，然后取每次相乘后的整数部分即可。 0.3125×2=0625 0.625×2=1.25 →0.312510=0.01012 0.25×2=05 0.5×2=0 白注记：需要指出的是，绝大部分浮点数是无法用二进制数来精确表示的，如0.1,0.2,03,0.4 0.6.0.7,0.8.0.9、因此，计算机中存储的浮点数基本上都是近似数 (④二进制与八进制、二进制与十六进制之间的互换 ·每位八进制数对应于一个三位二进制数（见下表左） ·每位十六进制数对应于 一个四位二进制数（见下表右）. 0000 00000 81000 2200 32011 34001 B101 44100 4←→0100 C分1100 5分101 5←→010 D110 例1.4（仁进制啭八进制和十六进锄 11010.12=011010.1002=32.48 11010.12=00011010.10002=1A.816 http://nath.ecnu.edu.cn/-jypan

· 2 · 第一讲 计算机基础 b 注记：八进制和十六进制转化为十进制的方法类似. (3) 十进制转二进制 例 1.2 (十进制整数转化为二进制整数) : “除 2 取余, 逆序排列”, 即辗转相除法. b 注记：十进制整数转化为八进制或十六进制整数的方法类似. 例 1.3 (十进制纯小数转化为二进制纯小数) : “乘 2 取整, 顺序排列”, 即每次乘以 2 后去掉整数部 分, 不断乘下去, 直到小数部分为 0 或达到指定的精度为止, 然后取每次相乘后的整数部分即可. b 注记：需要指出的是, 绝大部分浮点数是无法用二进制数来精确表示的, 如 0.1, 0.2, 0.3, 0.4, 0.6, 0.7, 0.8, 0.9, 因此, 计算机中存储的浮点数基本上都是近似数. (4) 二进制与八进制、二进制与十六进制之间的互换 • 每位八进制数对应于一个三位二进制数（见下表左）; • 每位十六进制数对应于一个四位二进制数（见下表右）. 例 1.4 (二进制转八进制和十六进制) 11010.12 = 011 010.1002 = 32.48 11010.12 = 0001 1010.10002 = 1A.816 http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传

11信息的表示与存储 1.13二进制数的编码表示 (1)数在计算机内部的存储方式：原码、反码、补码 ·数的表示：符号+大小 ·符号：用“0”表示正，用“1”表示负，放在最高位 ·大小：二进制 注：这里假定用一个字节存放数据 34←→00100010 -34←分10100010 符号位 ·优点：直观 ·缺点：零的表示不唯一：四则运算要考虑符号位，规则复杂 (2)反码 。正数的反码：与原码相同 ·负数的反码：符号位不变，其它位取反(0变1,1变0) 原码 反码 34←)00100010)00100010 -34←→10100010分11011101 白注记：反码一般不直接使用，通常是作为求补码的中间码. (3)补码 ·正数的补码：与原码相同 ·负数的补码：反码的最末位加1 原码反码 补码 34←→00100010←→00100010←→00100010 34←→10100010→1101110111011110 ·0的补码表示唯一，因此可以多表示一个数 ·对补码再求补即得到原码。 凸注记：数据在计算机中是以补码的方式存放的】 (④补码运算规则 ·符号位作为数值直接参加运算 ·减法转化为加法进行运算： ·运算结果仍为补码. http://math.ecnu.edu.cn/-jypan

1.1 信息的表示与存储 · 3 · 1.1.3 二进制数的编码表示 (1) 数在计算机内部的存储方式: 原码、反码、补码. • 数的表示: 符号 + 大小 • 符号: 用“0”表示正, 用“1”表示负, 放在最高位 • 大小: 二进制 • 优点: 直观 • 缺点: 零的表示不唯一; 四则运算要考虑符号位, 规则复杂 (2) 反码 • 正数的反码: 与原码相同; • 负数的反码: 符号位不变, 其它位取反（0 变 1, 1 变 0） b 注记：反码一般不直接使用, 通常是作为求补码的中间码. (3) 补码 • 正数的补码: 与原码相同; • 负数的补码: 反码的最末位加 1 • 0 的补码表示唯一, 因此可以多表示一个数; • 对补码再求补即得到原码. b 注记：数据在计算机中是以补码的方式存放的. (4) 补码运算规则 • 符号位作为数值直接参加运算; • 减法转化为加法进行运算; • 运算结果仍为补码. http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传

第一讲计算机基础 例：用8位字长计算67-10 6710=01000011,[原码]←：01000011[补码】 -101。=100010102[原码]→11110101[反码]←11110110[补码] 01000011+11110110=100111001←分00111001 (注意：符号位加入正常运算，超出字长部分自然丢失) 00111001[补码]←00111001，[原码]-57 业思考：如果用8位字长计算85+44，则结果会是什么？ (5)非数值信息 ·西文字符：每个西文字符与其ASC码一一对应（完整的ASC码表见课程主页或教材） ·中文汉字：一个汉字占两个字节，常见编码有GB2312,GBK.GB18030,UTF-8等. 1.2算法 1.2.1什么是算法 程序=算法+数据结构+程序设计方法+语言工具和环境 著名计算机科学家Nikiklaus Wirth,1976 ()一个程序应该包括： ·对数据组织的描述：数据的类型和组织形式，即数据结构； ·对操作流程的描述：即操作步骤，也就是算法. (2)算法：通俗地说，算法就是为解决一个问题而采取的方法和具体步骤. ·学习程序设计的目的不仅仅是学习一种特定的语言，而是学习程序设计的一般方法： ·掌握了算法就是掌握了程序设计的灵魂，再配合有关的计算机语言，就能顺利编写出程序，解 决问题 ·脱离了具体的语言去学习程序设计是困难的 1.2.2算法的特征与评价 (①)算法的特征 ·输入：有零个或多个输入量： ·输出：通常有一个或以上输出量（计算结果） 。明确性：算法的描述必须无歧义，保证算法的正确执行 ·有限性：有限个输入、有限个指令、有限个步骤、有限时间 ·有效性：又称可行性，能够通过有限次基本运算来实现 (2)算法性能的评测 ·空间复杂度：运算量 ·时间复杂度：存储量 ·实现复杂度：编程实现与维护 http://math.ecnu.edu.cn/-jypan

· 4 · 第一讲 计算机基础 K 思考：如果用 8 位字长计算 85 + 44, 则结果会是什么？ (5) 非数值信息 • 西文字符: 每个西文字符与其 ASCII 码一一对应（完整的 ASCII 码表见课程主页或教材） • 中文汉字: 一个汉字占两个字节, 常见编码有 GB2312, GBK, GB18030, UTF­8 等. 1.2 算法 1.2.1 什么是算法 (1) 一个程序应该包括: • 对数据组织的描述: 数据的类型和组织形式, 即数据结构; • 对操作流程的描述: 即操作步骤, 也就是算法. (2) 算法: 通俗地说, 算法就是为解决一个问题而采取的方法和具体步骤. • 学习程序设计的目的不仅仅是学习一种特定的语言, 而是学习程序设计的一般方法; • 掌握了算法就是掌握了程序设计的灵魂, 再配合有关的计算机语言, 就能顺利编写出程序, 解 决问题; • 脱离了具体的语言去学习程序设计是困难的. 1.2.2 算法的特征与评价 (1) 算法的特征 • 输入: 有零个或多个输入量; • 输出: 通常有一个或以上输出量（计算结果）; • 明确性: 算法的描述必须无歧义, 保证算法的正确执行; • 有限性: 有限个输入、有限个指令、有限个步骤、有限时间; • 有效性: 又称可行性, 能够通过有限次基本运算来实现. (2) 算法性能的评测 • 空间复杂度: 运算量 • 时间复杂度: 存储量 • 实现复杂度: 编程实现与维护 http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传