何勤：《C语言程序设计问题以及求解方法》.pdf

C语言程序设计问题与求解方法编程高手修炼捷径何 勤 著代序目前，人们要真正学会编程，大多都要花费五年以上的时间，悬梁刺股、卧薪尝胆。真正原因何在？其实只需到真正会编程的人身上，就能找到根本原因。经过认真仔细分析，我发现根本原因在于：每个真正会编程者，都必须具备计算机科学的大局观。也就是说，每个真正会编程者都必须懂得和掌握：1、c 语言的基本语法（主要是各种命令型语言的公共部分，其他语言目前还无法取代）2、大量阅读和调试经典的、基本的、由易到难的各种类型的C 语言程序（至少100题以上）。消化和积累各种基本问题的编程思路，并能用逐步求精的伪代码构造常见问题的算法；3、学习算法和数据结构的基本知识。4、整体上把握计算机到底是如何工作的；5、整体上把握操作系统是如何在硬件的密切配合下通过查找各种表格，管理调度计算机的所有软硬件资源为多道应用程序运行（和计算机用户）提供服务的。6、编译程序大体上是如何对源程序进行编译工作的。以上六项是必须具备的。此外，如果想成为程序员，还应当学习和掌握：汇编语言程序设计、数据库原理及数据库编程、计算机网络及网络编程、面向对象程序设计等课程知识、计算机原理和操作系统更深入的知识。由此可见，这条成才之路确实非常漫长和艰苦！尤其是第4 到第6 项知识的掌握，更是一个极为痛苦的心路历程上的万里长征！因为读者不仅要认真学习这些知识，而且还要做大量的提炼精华、融会贯通的艰巨功课。这是由于各门课程之间的内容衔接这项无比艰巨的工作，通常必须由学生亲自去完成，目前没有任何一本书在这方面做得比较好。为了大大减轻这个成才过程中的痛苦，明显缩短读者真正学会编程的周期。笔者花费了十余年时间广泛收集、筛选素材，并且进行了长时间地、艰苦地探索。终于很幸运地找到了一个绝好的比喻理想厨房系统，恰好可以把以上几个方面的知识在一个比较初级的层次上，比较完美地串联起来。构成一幅计算机科学中（与真正学会编程有关的）最重要的、最精华的基本知识的“联络图”。为初学者在短时间内把握计算机科学的大局观并学会编程，开辟了一条相对比较轻松的捷径。而且，这也为后续更高级编程技术课的学习奠定了扎实的知识基础。本书虽然比较系统地讲解了 C 语言语法，但是，读者别指望从这本书中找到很多高深语法细节问题的详细讲解。因为笔者认为：过早学习太多高深语法知识，是很多读者学不会编程的罪魁祸首！这将导致很多读者觉得程序设计课相当枯燥乏味。浪费了读者本可以用来学习生动有趣的编程思路和技巧的、有限和宝贵的精力。大脑里留存下了一大堆未经消化的细节语法规则，反而束缚了最需灵活自由的编程思路的展开和翱翔。编程语言的高级语法知识的学习和掌握，比大量编程思路的领会、消化和积累要容易得多！读者在学习编程过程中最需要得到的是编程思路上的引导和启发。读者应当在真正学会编程后再决定是否要比较全面深入自学哪一种程序设计语言的语法细节知识。本书中的大多数例题值得你认真钻研，因为其中蕴含了大量比较经典的基本编程思想和编程技巧。本书不可能系统讲解各种编程思路（这是算法、数据结构这两门课程的任务），然而，本书却教给了读者很多有效的举一反三的编程方法，这种方法强调从特殊到一般，来探索问题的编程思路和编程技巧。在循环和数组这两章中的很多例题中，展现了如何利用这种方法来做各类编程题。本书也很重视培养读者用逐步求精的伪代码来构思算法的能力。读者要注意，学习钻研本书，一定要配套做100200道各种类型的由易到难的编程题。这个亲自动手编写和调试程序的实践性修炼环节，是任何编程书籍和老师都无法替代的。这是学会编程决不能省略的最重要环节。再困难也要坚持，挺过开始的困难阶段，变成一种习惯后，你就能够逐渐享受到编程带来的极大乐趣。读者还要特别注意：千万不要被某些教科书误导，从而陷入钻研一门高级语言语法细节知识的痴迷和狂热之中，误以为学好一门语言的高深语法，就可以轻松步入编程高手的行列。这就象一位想学会写作文的学生，只热衷于冷僻汉字和高深语法，而置更为重要的通过认真学习消化课文来积累写作思路和技巧（包括大量造句和写作文）于不顾那么可笑！必须将编程思路的学习领会和积累，放在编程学习中的首要位置。以理想厨房为 纲，以程序如何运行、如何构思、如何编写为“目,把计算机科学中为了真正学会编程必须掌握的、几乎所有的、基础的、精华的知识有机的串联起来。在本书中仅仅做了这样一件事。一书在手，“软（指软件）硬（指硬件）兼施、内（指编程思想）外（指语言语法）兼修”，让读者可以真正全方位学习编程，并且真正学会编程，这是本书的写作目标。所以，本书中的知识讲解比较密集、浓缩，尤其是第一章和第二章。读者要作好心理上的准备，你是否愿意付出艰苦努力，去认真学习本书，出版社和作者是否值得信任。读者不要以为真正学会编程只是计算机专业学生的事。任何一位当代社会的理工类大学生，都必须具备一定的编程能力，能够在未来的科技工作中把计算机做为自己的得力助手和亲密伙伴，否则你就不是当代社会的合格科技人材。当代科技工作者不会编程，就象古代战士不会射箭一样。何勤初学者阅读本书，建议从第4 1页开始第一部分：计算机原理（初）第。章“理想厨房”的工作原理0.1理想厨房系统0.2理想厨房系统的一个炒菜实例0.3 理想厨房”工作的重要特点0.4理想厨房系统与计算机系统术语对照表第1章计算机的基本工作原理1.1 二进制简介1.1.1 二进制与二进制数的基本概念1.1.2 与二进制相关的术语：位、位串、字节1.1.3 数和码的含义与区别1.2 计算机系统1.2.1 计算机系统中的硬件1.2.2 计算机系统中的软件1.2.3 计算机指令能做的工作1.3 提高部分1.3.1 程 序（指令序列）在硬件上的运行过程1.3.2 结构化、规范化的机器语言程序1.3.3 各种数制之间的转换第二部分（C语言基础）第2章C语言程序结构和基本语法要素第3章顺序结构程序设计3.1 语句执行的顺序性3.2 用计算机求解问题的步骤3.3 逐步求精的伪代码3.4 验证算法的方法3.5 赋值表达式和多重赋值3.6 变量类型的进一步讨论3.7 各种类型的常量3.8 不同类型数据之间的类型转换3.9 常见编程错误3.1 0 提高部分3.1 0.1 机内形式的整数3.1 0.2 二进制浮点数在计算机中的表示方法第4章选择结构程序设计4.1 两种基本的i f语句4.2 布尔表达式之一：关系表达式4.3 空语句4.4 复合语句4.5 if语句的嵌套及其用法4.6 布尔表达式之二：逻辑表达式4.7 一种特殊的多重嵌套if语句多分支选择结构语句4.8 switch 语句4.9 选择结构常见错误4.1 0 提高部分4.10.1 其他表达式作为布尔表达式使用4.10.2 条件运算符4.10.3逻辑表达式的短路运算第5章循环结构程序设计5.1 while 语句5.2 自增、自减运算符和表达式的副作用5.3 do-while循环语句5.4 f o r语句5.5 复合赋值运算符和逗号表达式5.6 break 语句和 continue 语句5.7 循环语句的嵌套5.8常见错误5.9提高部分第6章数组6.1 引言6.2 一维数组6.2.1 一维数组的定义6.2.2 下标变量（数组元素）6.2.3 下标和下标表达式6.2.4 动态下标变量6.2.5 下标和下标表达式的允许取值范围6.2.6 数组元素在内存中的相对位置6.2.7 数组元素的初始化6.2.8 下标变量的存取6.3 一维字符数组和字符串6.3.1 一维字符数组的定义6.3.2 单个字符的输入输出库函数6.4 二维数组6.5 编程综合练习第7章函数7.1 引言7.2 函数的概念7.3 函数编写的一些重要原则7.4 使用数组（或数组元素）作为函数参数7.5 函数的嵌套与递归7.6 有关函数定义、返回、声明、调用的进一步说明7.6.1 函数定义7.6.2 return语句与函数类型7.6.3 函数声明与函数原型7.6.4 函数调用7.6.5 函数的形式参数与实际参数7.7 提高部分第8章指针8.1 引言8.2 指针变量的定义、初始化和应用8.2.1 指针变量的定义8.2.2 指针变量的初始化8.2.3 指针赋值8 2 4间接寻址运算符8.2.5 指针变量作为函数的形式参数和实际参数8.2.6 指针作为函数调用的返回值8.3 指向数组的指针以及相关的运算8.3.1 指针变量指向数组元素8.3.2 数组名用作指针（常量）8.4 提高部分第9章C语言进阶9.1 结构9.1.1 结构类型的定义9.1.2 定义结构变量9.1.3 结构变量的初始化和访问（输入/输出和存取）9.1.4 结构数组和结构指针的定义、初始化以及访问方式9.1.5 用typedef定义类型的别名9.2 编译预处理9.2.1#includc 命令9.2.2#def ine 命令9.2.3 条件编译指令9.3 文件、流和输入/输出9.3.1 概述9.3.2 文件和流的概念9.3.3 文件的两种形式9.3.4 文件的输入和输出9.4 提高部分9.4.1 链 表（单链表）9.4.2 位运算9.4.3 枚举类型9.4.4 文件流的本质第三部分算法与数据结构简介第四部分利用ege图形库函数的游戏编程案例第五部分计算机原理和操作系统简介第11章编程原理进阶1 1.1 引言11.2 输入/输出设备和输入/输出接口电路11.3 内存与外存1 1.4 中断和操作系统11.4.1 操作系统工作的机制11.4.2 操作系统的特点11.5 提高部分11.5.1计算机为何使用二进制数字信号？11.5.2 模拟图像和声音的数字化编码过程附录A ege图形库函数使用说明和库函数列表附录B常用字符与ASCII码对照表附录B常用C语言库函数附录C运算符的优先级和结合性附录D格式化输入输出库函数的用法小结参考文献第零章理想厨房的工作原理一种有着神奇的“魔 力 和“智能”的人造设备，正在迅速地、彻底地、默默无闻或者令人震惊地改变和丰富我们所生活的大千世界。这个看起来很不起眼的，在少数场合被称为“电脑”的电器设备，是如何具有如此神奇的“魔力”和“智能”的？本章和下一章将带你开始解开这个与我们的生活和工作息息相关的当代社会最大的谜。0.1 节介绍理想厨房系统，0.2 节通过一个炒菜实例，讲解理想厨房各部件是如何密切配合工作的。0.3是一张理想厨房系统与计算机系统的对照表。计算机从发明到现在不过70年左右的时间，然而计算机的发明、改进和普及，把人类带进了智能时代。计算机本身也变得越来越复杂、快速、小巧、种类繁多。但大多数计算机都遵循冯.诺伊曼体系结构，这为我们理解计算机的基本工作原理提供了方便。从某种角度来看，计算机就是一种人造智能生命。想要真正学会编程，通过编写的程序命令计算机工作，就必须懂得计算机的基本工作原理。就像人们要与某种具有智能的其他物种个体进行交流通信，就必须对那个物种的习性有一个基本了解一样。本章和下一章是全书的重要基础。通过这两章，读者可以了解计算机的工作过程。这些知识对学习程序设计非常有帮助。直接学习计算机工作原理是极其枯燥乏味、很困难的，因为有大量的新名词。为此，笔者付出了极大的努力，找到了一种比较好的类比方法理想厨房系统，通过这个例子就可以初步了解计算机的基本工作原理。0.1理想厨房系统：理想厨房系统，是一个通过顺序执行菜谱中的各个加工步骤，把原材料加工成菜肴的系统。它由硬件和软件（菜谱）组成。1）软件部分：菜谱是理想厨房系统中的一个无重量、无体积、不会损坏、但可以经常更换的极为重要的“软件”部件。菜谱由一个个的加工步骤顺序组成。每个加工步骤命令理想厨房系统完成一个基本操作（比如炒、蒸、煮、输入一种原材料等）。注意：为了解说简洁起见，在以下叙述中，我们经常把菜谱中的一个“加工步骤”称为一条“揖令:。因为一个加工步骤就是一条指导理想厨房如何工作的命令。2）硬件部分：理想厨房系统，主要由以下四个“硬 件 （即实物）部件构成理想厨房、自动冰箱、输入输出设备（即配菜员和传菜生）和三条传送带。需要注意的是，理想厨房仅仅只是理想厨房系统中的一个重要组成部分。理想厨房系统的构成简图如图0所示：理想厨房自动冰箱0.1理想厨房系统运行示意图：0.1理想厨房系统示意图：自动冰箱：自动冰箱负责临时保存菜谱、原材料和菜肴。它由非常多的（比如几百个）大小一样的格子组成，每个格子都有一个唯一固定编号，这个编号称为地址。地址是从0开始逐一递增的。是不是感到很奇怪：菜谱也要保存在冰箱中，这样做的道理请看本章后面。每份原材料和菜谱中的每个加工步骤，都占据冰箱中的一个格子。理想厨房：功能：负责根据从冰箱的菜谱中取到的加工步骤，进行炒菜以及进行相关的控制工作。构成：理想厨房主要由厨房管理员、厨师、炊具和一些碟子组成，参见图0.1。理想厨房中的各种碟子理想厨房中有一些起着重要作用的碟子：一 个P C碟（又称为指令地址存放碟）：此碟中存放一个非负整数值，这个值是一个地址；它指明将要执行的指令位于自动冰箱的哪一格中。一个IR碟（又称为指令存放碟）：用来存放刚刚从冰箱中取过来的一条立即要执行的指令。理想厨房中还有若干个通用碟（图0.1中标有名称RO、RI、R 2的碟）：用来临时存放从冰箱中取来的原材料或经过加工了的半成品或成品。这是由于到冰箱格子中存取物品，要比到通用碟慢得多的缘故。指令执行的全过程理想厨房每次只能按顺序执行菜谱中的一条指令。理想厨房执行指令的流程完全是周期性的，即任意一条指令都是按照“取指令阅读分析指令执行指令”这三个阶段进行的。厨房管理员首先根据PC碟中的值，通过三条传送带的协调工作（三条传送带如何协调工作的细节，请参见下一节），到自动冰箱的指定格中去取菜谱中的一条指令。取到理想厨房并把它存放到IR 碟中之后，PC碟中的值将会加上1这是为取下一条指令预先做好准备。然后，厨房管理员阅读并分析IR 碟中刚取到的这一条指令，根据该指令的指示，去做以下六类工作中的一种：1.取物品：通过三套传送带，命令自动冰箱把指定地址格子中的（炒菜加工步骤马上要用到的）原 材 料（通过材料传送带）传送到理想厨房中来；2.加 工：章令厨师按照指令的要求，对原材料作一个基本加工操作（做 炒 ，蒸二“煮”等基本操作步骤中的某一个动作）；3.存物品：通过向三套传送带向自动冰箱发号令，把某个碟子或炊具中的成品（或半成品）送回到冰箱指定的格子中存放；4.在厨房内部进行物品传送：在厨房的各个碟子和炊具之间传送原料或半成品；5.输入：命令配菜员为某道菜临时配备原材料；（在本章不作讨论）。6.输出：命令传菜生将炒好的菜送给顾客；（在本章不作讨论）。一条指令执行完后，理想厨房立即自动进行下一个完全类似的、新 的“取指令阅读分析指令执行指令”的工作。下面我们通过一个实例来讲述理想厨房系统的工作机制。这是本章的一个重点，因为计算机的工作原理，与之极其相似。0.2理想厨房系统的一个炒菜实例在本节中我们通过炒制一道青菜的例子，来说明理想厨房系统的工作全过程。首先，把青菜放在冰箱地址为5 的格子中，冰箱地址为6 号的格子，预留给炒好的菜使用。菜谱的所有加工步骤（又称为指令）从冰箱地址0 号格开始依次按照顺序存放，编写炒青菜的菜谱如下：地 址0的格子中地 址1的格子中地址2的格子中取地址5（中的物品）到RO碟;将R0（倒入炒锅中）炒好后装到R1碟;存R1碟（中的物品）到地址6中;可见，此菜谱一共有3 个加工步骤。开始时理想厨房系统状态如下图0.3（注意：冰箱格子以及理想厨房碟子中存放的物品都用了斜体字）理想厨房 自动冰箱碟名碟中物品地址 冰箱格子中物品图0.3R0材料传送带0取她址5到RO碟R1 厨具1将R。炒好后装到R1碟;R2 厨师2存R 1碟到地址6中;地址传送带304PC 0 厨房管理员5青菜IR控制传送带6取7菜谱和原料安放完毕后，启动理想厨房系统，开始自动化的工作。1）厨房管理员根据PC碟子中的数字“炉，知道要到地址为。的格子中取第一条指令（即加工步躲）。于是，厨房管理员向控制传送带上发出一个“取”信号，然后马上将PC碟中的数字 V 复制后放到地址传送带上。这两个信号都会到达冰箱。冰箱收到这两个信号后（知道理想厨房想要得到第0 格中的物品，于是自动冰箱）将。号格的 内 容“取地址5到破 复 制 一 份，将其放到材料传送带上，送往理想厨房。理想厨房收到后，将这条指令放到IR碟中。然后，厨房管理员将PC碟中的原来值增加1,以便为取下一条指令做好准备。取指令工作完成后，理想厨房系统处于如下图。.4 状态:碟名碟中物品理想厨房R0R1炊具R2厨师PC1厨房管理员IR取地址5到RO碟材料传送带地址传送带控制传送带图0.4地址 冰箱格子中物品自动冰箱01234567取地址5至1!R 0碟将RO炒好后装到R 1碟;存R 1碟到地址6中;青菜指令执行阶段：厨房管理员读到指令存放碟（即 IR 碟）子中去取物品，并且要放到R0碟中。因此,然后马上将5 这个数字放到地址传送带上。中的加工步骤后，知道要到冰箱地址为5 的格管理员向控制传送带上送出一个“取”信号，冰箱知道理想厨房要取5 格中的物品，于是冰箱将地址为5 的格子中的物品 喜菜 取出来，放到材料传送带上。材料传送带上的物品“青果”，传到理想厨房后，按照指令的要求（通过理想厨房内部的传送带）送到了 R。碟中。第一条指令执行完后，理想厨房系统处于如下图0.5所示的状态:理想厨房碟名碟中物品自动冰箱地址 冰箱格子中物品2）接下来，开始下一条指令的取指令阶段。完全类似于前一条指令，在取指令阶段完成后,理想厨房系统处于如下图0.6 状态：R 0青菜R1 炊具R2 厨师PC 7 厨房管理员IR取地址5 到 R O 碟材料传送带地址传送带5控制传送带取01234567取她址5 到 R O 碟将 R。炒好后装到R 1 碟;存 R 1 碟到地址6中;青菜图0.5指令执行阶段：管理员阅读并分析指令存放碟中的指令后，命令厨师将R 0 碟中的物品倒入锅中炒好后装到 R 1 碟。第二条指令执行完后，理想厨房系统处于如下图0.7 状态：理想厨房 自动冰箱理想厨房自动冰箱碟名 碟中物品地址冰箱格子中物品R0青 菜（原料）材料传送带0取地址5至！1 R 0 碟R1炊具1将 R O 炒好后装到R 1 碟;R2厨师2存 R 1 碟到地址6中;地址传送带314PC2 厨房管理员5青菜IR将 R0炒好后装到R 1 碟;控制传送带6取7图0.6图0.7碟名 碟中物品地址冰箱格子中物品R0青菜材料传送带0取地址5 至 R 0 碟R1熟青菜 炊具1将 R O 炒好后装到R 1 碟;R2厨师地址传送带2345存R 1 碟到地址6中;PC2 厨房管理员青菜IR将 R O 炒好后装到R 1 碟;控制传送带673）同理，在第3 条指令的取指令阶段完成后，理想厨房系统处于如下图0.8 状态:理想厨房 自动冰箱指令执行阶段：下面开始执行“存R1碟到地址6中”达条墙令。厨房管理员分析指令存放碟中的加工步骤后，知道要将R1碟中的物品，送到冰箱地址为6的格子中去存放。于是，管理员向控制传送带上发一个“存”信号，然后马上将6这个数放到地址传送带上；最后，将R 1碟中的 物 品“熟青菜”放到材料传送带上，送往冰箱。碟名碟中物品地址冰箱格子中物品生青菜材料传送带0取地址5到RO碟R 1熟青菜炊具1将RO炒好后装到R 1碟;R2厨师2存R I碟到地址6中;地址传送带345青菜PC 3 厨房管理员控制传送带6I R存R 1碟到地址6中7图0.8冰箱收到两个来自理想厨房的信号后，知道理想厨房要存放物品到6格中；于是自动冰箱（的机械手）在材料传送带旁，等待从理想厨房R 1碟传来物品“熟青菜”、一旦到达，自动冰箱就将其取下，并将其存放到地址为6的格子中。完成后系统状态如图0.9:理想厨房自动冰箱碟名碟中物品R O青菜R 1黑香点 炊具R2 厨师PC 3 厨房管理员班 存R7碟到地址6中;材料传送带地址传送带6控制传送带地址 冰箱格子中物品01取地址5到RO碟将RO炒好后装到R1碟;2存R 1碟到地址6中;345青菜6熟青菜7图0.9到此为止，炒青菜这道菜终于大功告成。0.3理想厨房工作的重要特点现在，我们对刚学到的重点知识，做一个小结：1、顺序性和周期性顺序性：理想厨房每次都只能取得和执行一条指令；一条地址为i中的指令执行完毕后，才能顺序执行地址为i+1中的指令。周期性：厨房管理员的工作完全是周期性的，即他永远在做：（命令各部件）取指令一阅读分析指令f发出控制命令要求各部件执行指令（简称为取指T 译码一执行）这一周期性的动作。只要一启动，理想厨房就永远按照这个周期性的动作，一条一条的顺序地取指令并且执行指令，这样不停地、不知疲倦地快速运行着，直到执行了一条 停止运行 指令或发生严重故障时为止。2、有限和无限有限：厨师会做的各种不同基本加工操作所构成的集合是固定有限的（炒、煎、蒸、煮、烤等几十种），也就是说厨师学不会任何一种新的基本加工操作。厨房管理员能看懂的各种不同种类加工步骤所构成的集合也是固定有限的（从冰箱取物品、存物品到冰箱、厨师的各种不同加工方式、配菜员输入原材料到冰箱或厨房、传菜生输出菜肴给顾客等）。无限：然而，人们可以为理想厨房编写出来的菜谱数量是无限制的。因此，理想厨房可以炒出菜的品种总数也是没有限制的。3、智者与白痴理想厨房中的厨师和厨房管理员都是不知疲倦的、机械化的“白痴”，在厨师或厨房管理 员 的“大脑”中没有任何一道菜的（全部或一部分）加工步骤。加工制作各种菜肴的智慧（即蕴含在加工步骤中的智慧）都是来自于存放在自动冰箱中的菜谱，也就是来自于菜谱的编写者。正是由人们编写出来的可以让理想厨房执行的各种各样的菜谱，才使得原本白痴般的、能力极为有限然而速度却极快的理想厨房系统在炒菜方面显得似乎无所不能！4、主动与被动：在指令执行的三个阶段中，取指令和分析阅读指令是硬件主功进行的，而在指令的执行阶段，硬件是在软件（即菜谱中的加工步骤）的命令下被动进行的。5、不变与可变：一个理想厨房系统的硬件组成和结构是不变的，而存放在它的冰箱中的软件（菜谱）却是可以随着客户需要而随时加以改变的；同一个菜谱（菜谱不变）随着加工处理的原材料的种类的不同（原材料可变），可以得到不同的菜肴（菜肴可变）。比如：情炒青菜的菜谱同样可以用来清炒韭菜，只要把生韭菜放到原来放生青菜的指定格中。一条指令执行的前两个阶段（取指令、阅读分析指令），参与工作的硬件部件是不变的；而在指令的执行阶段，随着指令类型的不同参与工作的硬件部件是可变的。6、两个中心厨房管理员是执行指令的控制中心；厨 师（加上炊具）是原材料的加工中心。理想厨房系统的工作原理，到此已经全部介绍完毕。在下一章你将看到：理想厨房的工作原理，与计算机的工作原理是极为类似的。因此在本书中，从整体上把握计算机的基本工作原理，就变成为一个比较轻松的名词替换的小游戏。0.4理想厨房系统与计算机系统术语对照表下面给出两个系统之间的术语对照表，见表0.1。表0.1术语对照表理想厨房系统电子数字计算机系统（简称计算机系统）1.硬件设备2.软件与硬件之间的接口（编写菜谱或程序的基本要素）自动冰箱（包含很多大小相等的格子）（冰箱中的）一个格子内存（又称为主存，包含很多容量相等的基本存储单元）（内存中的）一个基本存储单元材料传送带数据总线地址传送带地址总线控制信号传送带控制总线理想厨房（包含以下设备）CPU或称为微处理器（包含以下部件）厨师及炊具算术逻辑单元ALU（又称为运算器）厨房管理员控制单元（又称为控制器）通用碟通用寄存器（或数据寄存器）指令地址存放碟PC指令地址寄存器PC（又称为程序计数器）指令存放碟IR指令寄存器限状态存放碟程序状态字寄存器PSW（又称为标志寄存器）采购员及配菜员输入设备（键盘、鼠标、网卡、U盘等）传菜生输出设备（显示器、打印机、网卡、u盘等）自动仓库外 存（硬盘、U盘）冰箱地址（即格子的编号）内存地址（即基本存储单元的编号）厨师可做的各种炒菜基本动作算术逻辑单元可进行的各种基本运算碟子的名称寄存器的编号理想厨房可以执行的所有不同加工动作该类型计算机的指令集3.软件特殊菜谱（机器语言形式的）程序加工步骤指令原材料数据炒好的菜信 息（或称为结果）精确的普通菜谱高级语言源程序（又称为源代码）简要的普通菜谱伪代码4.系统的使用者编写特殊菜谱者用机器语言编程的程序员编写精确的普通菜谱者用高级程序设计语言编程的程序员理想厨房系统的大堂经理和顾客计算机的用户以上表中这些与计算机相关的术语，将在1.2节进行讲解。与在理想厨房系统上运行一个菜谱极为类似，在电子计算机上运行一个程序时，上表中列出的计算机的各个部件也会协同工作，完成程序给定的任务（参 见1.2节）。学习了理想厨房这个例子，理解计算机原理就变得非常容易了。0.5本章习题1、在取一条指令到理想厨房的过程中，哪些部件会依次参与工作？哪个部件在此过程中起着核心控制作用？2、取一份原材料的工作过程与取一条指令的工作过程有什么区别？3、考虑一下为理想厨房编写的菜谱与给普通人看的菜谱有何不同点？4、编写一个香菇炒青菜的菜谱。5、写出三条传送带各自的职责。哪传送带是可以双向传递的？在取指令时，材料传送带是双向的还是单向的？第一章二进制的数和码捷径有时候是一条弯路。万事开头难。计算机能够 理解和懂得”的语言是二进制机器语言，计算机能够直接加工处理的，都是二进制的数和码。本章1.1对二进制进行了简介，其中最重要的概念是：字节、二进制的数和码；世界上的各种事物如何通过编码用二进制位串来表示（或近似表示）。1.2对计算机的基本构成成分、机器语言、计算机的基本工作原理进行了简介。1.1 二进制简介为了从整体上把握计算机的基本工作原理，并为后面的编程学习奠定扎实的基础，读者必须事先对数字信号、二进制及其相关知识有一个比较清晰的、整体的简明了解。以下进行简要介绍。1.1.1二进制与二进制数的基本概念表1,1部分十进制数与二进制数（和十六进制数）数值对照表十进制数所对应的二进制数（所对应的十六进制数）0001112102311341004510156110671117810008910019101010A（或 a）111011B（或 b）121100C（或 c）131101D（或 d）141110E（或 c）151111F（或 f）161000010二进制就是只能用数字 0 和“1”来进行计数的数字系统。二进制加法运算的重要规则是：1+1=1 0 ,即两个1相加，就产生了向高位的进位即“逢二进一”（做减法时则是“借一当二”），类似于十进制中的“逢十进一”（做减法时则是“借一当十”）o其它二进制加法规则更简单：0+0=0、0+1 =1、1+0=1 o与十进制数类似，在一个二进制数中，靠左边的数字是高位数，靠右边的数字是低位数，其中最左边的位称为最高位。我们经常用一对圆括号括住一个数值，并在圆括号外的右下角加一个整数下标，用此下标来表示该数值是几进制的（但是对于十进制数一般不用圆括号和下标）。比如：（1 0 1 1）1 6是一个十六进制数；而（1 0 1 1）2是一个二进制数。1.1.2二进制数的多项式展开表示一个十进制整数，其数值可用以下多项式展开来表示：比如3 7 8 53 7 8 5=3 X 1 03+7 X 1 02+8 X1 0 +5 X1 0 （1）我 们 把（1）式 中10的几次方称为权重，权重左边的乘数称为系数。（1）式中共有4个系数,从左到右依次是：3、“7”、8、5，权重依次分别是KA i o2,1 0 1 0%可见，用这种记数法表示数值时，越左边的系数，所对应的权重越大，所以就越重要。权重中的基数（即底）与表示该数的进制是一样大的，在十进制数中都是1 0。类似的，任意一个二进制整数，其数值也可用多项展开式来表示：比如二进制整数1 0 1 1（1 0 1 1）2=1 X 23+0 X 22+1 X 21+1 X 2 （2）1（2）式中系数从左到右依次是：1、0、“1”、“1”，而权重依次分别是2 3、2 2、2 2。（注意：这里的权重是用十进制来表示的。如果权重也用二进制，则应当分别是二进制的1 0、1 0 1 1 0 1 0 0）。展开式中系数的最大值一定比进制数小1,比如：在十进制记数系统中，系数的最大值是9,而在在二进制记数系统中，系数的最大值是1。1.2二进制相关术语简介：位、位串、字节下面，我们来熟悉一些与书写、存储或传输一串二进制数字有关的术语。1 2 1位（bi t）:书写、存储或传输单个二进制数字,我们将其称为位（bi t）或“比特”。单 个“位”中的二进制数字不是0就是1,再没有别的可能数字。任何一个只能处在两种不同稳定状态的电子元件（触发器、电容等）或者某种均匀介质（比如覆盖着磁性颗粒的金属圆盘）表面上的一个小点，都可以用来（间接）表示和存储二进制的一个“位，如果用电容充满电状态表示二进制数1，就可以用电容放完电的状态来表示二进制数“0”。1 2 2位串及其长度：多个二进制数字顺序排列在一起，称 之 为“位串”（有些教科书称为位模式）。位串中含有的数字总个数称为位串的长度。比如：位 串1 0 0 1 1 0的长度是6。处于位串左边的位称为高位，处于位串右边的位是低位。位于位串最左边的位，称为最高位。1 2 3度量位串长度的基本单位字 节（B yt e）“位”这个二进制最小度量单位太小了，通常用起来很不方便。现代的绝大多数计算机和一些数字处理设备，大多数是以长度为8的位串字节来作为度量（部件或设备的）数据存储容量大小的一种基本单位。如果完全用二进制展开表示，则应当是：（1 0 1 1）2=1 X1 0 1 1+0 X1（）1 0+1 X1（）1+1 X1 0。,系数和权重都用二进制表示，但人们一般仅将系数用二进制表示。把长度为8 的一个位串称作为一个字节，长度为16的一个位串称为2 个字节等等。长度为n 的位串，一共有n/8 个字节。也就是说，一个位串的长度，既可以用位串中的总位数来度量，也可以用位串所具有的字节数来度量。1.2.4二进制数据存储和传输的一些其它常用单位KB、MB和 GB字 节（Byte）这个基本单位虽然大小是位（bit）这个最小二进制单位的8 倍，但是在很多场合仍然还是显得太小。更大的常用单位有（在以下叙述和各种资料、书籍中，经常用字符 B 来代表术语字节Byte）：千字节：1KB=1024B=2B兆字节：1MB=1024KB=2KB=2B=1048576 B（约为一百零五万字节）吉字节：1GB=1024MB=2iMB=23B=1073742814 B（约十亿七千多万字节）需要引起注意的是：相邻单位之间，都是1024倍的关系,而不是1000倍的关系。1 2 5 位串的通常传输方式并行或串行：一个长度为n 的位串，既可以用n 根并排导线同时进行传输，每根导线传输一个位即并行传输（这种传输方式速度很快，但要用多根导线）；也可以只用一根导线，分为n 个相等时间段，一位一位地依次先后进行传输即串行传输（这种传输方式速度较慢，但只要用一根导线）。在导线中如果用直流电的高电平（即有电流通过）来传输1,就可以用低电平（即无电流通过）来传输0。在计算机内部全部使用二进制的数或码，但由于二进制通常太长不好书写，人们在编程和将数据输入计算机时，还是喜欢用十进制（或者十六进制和八进制）。因此，我们必须对用各种进制表示的数如何转化成别的进制数有一个基本了解。L3各种进制数之间的转换1.3.1 二进制整数转化成十进制整数任意一个二进制整数，其数值可用以下展开式来表示：比如二进制数整1011（1011）2=1 X23+0X22+1 X21+1X20（2）此二进制数的值，等于十进制的1X8+0X4+1X2+1X1=8+2+1=11（3）由此可以得到二进制整数转化成十进制整数的一般方法：只要将一个二进制整数（比如1011）展开后的（2）式中的每一位的系数值（采用十进制乘法规则）乘以这一位转化成十进制数后的权重（即 2 的几次方），然后再将乘积项的数值（采用十进制加法规则）逐个相加起来即可。1.3.2 任意R 进制实数（或整数）的表示法一般情况下，任何一个R 进制去数，都可以紧凑地表示为：（+Vn.f-ro,rir.2.r.m）R（1.3）（在计算科学中，R 通常是2,8,10,16中的某一个正整数）其中的任何一个（系数）i，都是位于0 到 R-1之间的一个正整数，r。是个位数，r 是小数点后的第一位数，%是最高位数。丁是小数点后的最低位数。如果小数点后的所有（系数）口、Q、丁 等都为0,则（1.3）表示一个整数。将任意一个R 进制数扩大R 倍（即乘以R）,只需将小数点右移一位即可；类似地，将任意一个R 进制数缩小R 倍（即除以R）,只需将小数点左移一位即可。其中R 等于10是人们最为熟悉的十进制数，这 种（可以带小数点的）十进制数的简洁紧凑表示方法，是由古代印度人发明的（来源于人有十个手指）。任何一个R进制实数，也都可以用多项式展开表示为：（rnX Rn+rn.lXR-,+-+rlX Rl+r0XR +口X曰+QX/+小X Rm）（ij称为系数，史称为权重）在R进制数值的多项式展开表示法中，不使用小数点。人们最为熟悉的仍然是R等于10时的多项式展开式。1.3.3 将十进制整数转化成二进制数把一个十进制转整数（比如89）换成二进制，只需要用新的基数2（采用十进制除法规则）除以这个十进制数（89）,余 数（1）是结果左边的下一位数字，商（44）是新的被除数，然后重复这个过程，直到商为0时终止。短除法就是按照这个转换原理，把要转换的十进制整数不断的除以2,然后取余数，商作为新的被除数，直到商为0的时候结束。然后把余数倒着写出来。例如：把89转换成二进制数2|89 1 八21 44021 2202|11121 5121 202110即：89=02延伸与拓展：转换规则的技术内幕要想明白这种转换规则的道理，请考虑十进制整数与它等值的二进制整数的方程式：8 9=（r0 X Z+n X 乎+X 2 +r0 X Z）2其中的二进制系数3。等等应该如何求得？可将该方程式的左边的十进制整数整除2,得到商44和余数1；与此同时将方程式的右边的二进制整数的小数点左移一位（等价于整除2）。这样方程式右边将得到rn X 2n-4+0X 2+f!X 2+r0 X 2T;显然，商44应当与二进制整数%X2n+2X2r】X2。相等；而89整除2所得到的余数1（除以2的余数不是0就是1）就等于方程右边的系数力 （系数%不是0就是1）。同理，从方程式4 4=rnX2 ,我们可以用完全相同的方式得到系数口的值，转换工作直到方程左边的商为0时结束。注意：短除法也完全适用于将一个十进制整数转换为一个任意R（R2）进制的整数，只需将除数由2替换为R即可。1.3.4 将十进制小数转化成二进制小数10进制小数转换为2进制小数的转换过程，与整数的进制转换过程有些类似而计算方法又恰恰相反：不是用新的基数2除这个数，而是用新基数2去乘它。乘法的进位（进到个位的数字）将成为答案右边的下一位数字，乘法结果中的小数部分将成为新的被乘数，整个过程直到乘法结果中的小数部分为0时终止。例如：把十进制小数0.375转换成二进制小数：0.375X2二 0.7500/进位0,小数点后的第一位0.75X2=1.501进位1,小数点后的第二位0.5 X2=1.01进位1,小数点后的第三位所以，（0.375）1 产（0.011）2延伸与拓展：转换规则的技术内幕要想明白这种转换规则的道理，请考虑十进制小数与它等值二进制小数的方程式：0.735=（0.其中的二进制系数。、心等等应该如何求得。可将该方程式的左边乘以十进制的2,与此同时将方程式的右边的小数点右移一位。这样方程式左边将得到一个整数值1,这个整数值1与二进制小数最左边的系数均相等。去掉整数部分后，方程式两边剩下的小数部分的数值仍然是相等的，即0.47=0.。注意：这个规则也完全适用于将一个十进制小数转换为一个任意R（R2）进制的小数，只需将乘数由2替换为R即可。1.3.5 将十进制实数转化成二进制实数一个十进制实数，只要将它的整数部分和小数部分分别转化成二进制数，然后将其合起来即可。1.3.6 二进制整数