目录 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, RISCV; • 数据信息: 包括数值信息和非数值信息; 其中数值信息包括整数、浮点数等; 非数值信息包括 字符（字符串）和逻辑数据等. (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, UTF8 等. 1.2 算法 1.2.1 什么是算法 (1) 一个程序应该包括: • 对数据组织的描述: 数据的类型和组织形式, 即数据结构; • 对操作流程的描述: 即操作步骤, 也就是算法. (2) 算法: 通俗地说, 算法就是为解决一个问题而采取的方法和具体步骤. • 学习程序设计的目的不仅仅是学习一种特定的语言, 而是学习程序设计的一般方法; • 掌握了算法就是掌握了程序设计的灵魂, 再配合有关的计算机语言, 就能顺利编写出程序, 解 决问题; • 脱离了具体的语言去学习程序设计是困难的. 1.2.2 算法的特征与评价 (1) 算法的特征 • 输入: 有零个或多个输入量; • 输出: 通常有一个或以上输出量（计算结果）; • 明确性: 算法的描述必须无歧义, 保证算法的正确执行; • 有限性: 有限个输入、有限个指令、有限个步骤、有限时间; • 有效性: 又称可行性, 能够通过有限次基本运算来实现. (2) 算法性能的评测 • 空间复杂度: 运算量 • 时间复杂度: 存储量 • 实现复杂度: 编程实现与维护 http://math.ecnu.edu.cn/~jypan 仅供课堂教学使用，请勿外传