编程高手修炼捷径(何勤)716.doc

编程高手修炼捷径 何勤 著 前言可以说编程是很难学会的。首先，如果你不喜欢动手编程而只喜欢看编程教科书的话，不管你看了多少书，你都永远不可能学会编程；其次，如果你一直都只热衷于编写难度比较简单的30行以下的小程序，你也永远无法学会编程。我看过的小说至少有好几千本吧，造过的句子也难以计数数。但我决对写不出一篇像样的短篇小说来。然而，又可以说编程是很容易学会的只要你的学习方法正确、并且能够持之以恒。智力正常的人全力以赴的话，从零开始三个月就能编写出小游戏程序来。我所创建的群中已经有不少群友做到了这一点，事实胜于雄辩。只要你仔细通读你手上的这本书，在此基础上，你还要认真做本书中所包含的经过精心挑选的100道编程题。在一边系统学习C语言基本语法的同时目的是掌握常见的语句和程序编写规范；一边阅读消化本书中大量的、难度逐渐递增的、类型丰富的各种类型编程例题目的是积累大量的编程思路和技巧；一边坚持每天做两道本书上的编程题，在编程实践中将语法和算法紧密结合起来，把从书本上所学到的知识真正变为自己脑子里的。使用本书学习过程中，只要你能坚持同时做到以上三点，三个月内你就一定能够成功编写出小游戏程序。要编出一个几百行的能够正常运行的小程序，你必须要有足够强的程序调试能力；通常，还要有一定的用逐步求精伪代码构思设计算法的能力；还要掌握小程序的迭代式开发模式也就是分步骤地实现程序所有功能。从最基本、最简单的功能做起，利用函数将程序模块化。一个人只有能够独立编出几百行的小程序来，才算是真正学会了编程。仅仅能做几个编程的小题目算不上会编程因为你没有通过编程来解决实际问题的基本能力（相当于学写作的人一直只造句子，但从来没写过一段和一篇文章）。会不会编程对于当代的理工农医类大学生是极为重要的。就像是否会射箭对于古代战士那样重要。通过编程充分利用计算机的能力，能够极大提高你做科研或技术开发工作的效率。不会编程的理工农医类大学生，将来毕业后绝对不能去搞科研，不会编程的人去搞科研，科研周期将会很长，科研工作也决对是劳民伤财！一个用计算机做仿真实验不到一年能够轻松解决的问题，不用计算机仿真就要盖实验室，做大量浪费时间和经费的实验。学习本书时要注意模仿本书中的大量例题，掌握用逐步求精伪代码（千万不要使用流程图）来构思设计算法。否则，遇到比较困难的编程问题时，你就会感觉到难以下手。 本书在循环和数组这两章，讲解了大量的例题、收集了大量的编程习题。这是本书的一大特色。原因在于：只有熟练掌握这两章蕴含在例题中的大量编程思路和技巧，才能养成扎实的编程基本功。很多初学者不明白这一点，没有练好这方面的编程基本功，在进一步学习函数、指针、结构、文件和链表等内容和编程时，就会感到困难重重，一筹莫展。本书适合零基础的读者。对于理论基础不感兴趣的初学者，可以直接从本书3.2节开始学习。认真学习本书需要你花费的精力比通常的程序设计教材要多一些。原因是你必须认真阅读消化大量例题的编程思路和技巧；到了后期你还要认真编写一些比较难些的程序。愿不愿意付出这些精力这是你的个人私事，我只付责尽全力把这本书写好。其实学会编程是没有什么捷径的可走的，只是因为初学者可选的路太多了，其中大部分是错误的弯路或死路，因此在过来人的引领下不走弯路或死路就显的特别重要了。持之以恒、不走弯路就是捷径。很多人学习时缺少的就是持之以恒的毅力。缺乏毅力的读者，请结伴学习。朋友之间互相讨论、鼓励和监督比自己一人坚持钻研要容易得多。对本书有什么好的建议或例题，请发邮件给我。我的邮箱地址是2401721440。一旦采纳，将赠亲笔签名书一本。 何勤 关于用逐步求精的伪代码构思设计算法 学会用逐步求精伪代码构思算法是极为重要的。尤其是对于难题，学会用逐步求精伪代码构思算法相当重要为何重要呢？因为人们思考一个复杂问题往往是由粗到细的，逐步求精的伪代码恰好符合了人们的这一思维规律 编写难题不用伪代码构思算法，相当于盖房子事先不进行图纸设计。 构思设计算法，流程图不好用，国外程序设计名著没有使用流程图的。因为流程图难画，难以修改，比伪代码麻烦多了。很多人对于较难编程题感到难以下手、没有思路，关键原因之一就是不会用逐步求精的伪代码去构思、设计算法。 本书中，很多例题用了逐步求精的伪代码来构思、设计算法。伪代码最大的好处体现在逐步求精上。重点是逐步两个字。一级算法对于难题和大题（但不是指软件工程项目那种规模的大问题，而是说大约1000行以下小程序可以解决的问题）来说，是相当重要的。高层次的一级算法用程序语句是无法表示的，程序设计语句缺少伪代码的那种高级抽象层次和概括能力，源程序语句的移植能力也远远低于伪代码。高手与低手的最大区别：高手钻研经典名著，低手随手拿一本书来苦读；高手常用伪代码构思设计算法，低手常用流程图构思设计算法；高手重视编程思想，低手重视考试和证书；高手拥抱代码，低手拥抱语法；高手胆大自信（自信主要来自于正确的学习方法），低手胆小自卑；高手所学所编程序难度逐渐递增，低手所学所编程序难度永远不变；高手仔细阅读分析调试难以懂得的程序，低手看不懂程序立刻求助别人；高手喜爱面向对象编程（容易适应需求变化，容易查找修改错误），低手喜爱结构化编程；高手经常重构优化代码，低手不愿重构优化代码；高手调试程序的方法多，低手调试程序的方法极少（甚至没有）；高手学语法快学算法慢，低手学算法快学语法慢 （高手学习语言的高级语法细节时常常是在实践中，基本语法学的比较快）；如何快速学会编程现在有些群友C语言(或一门其他编程语言)还没学完就想去做小项目，那是不合适的。个人认为学完C语言教科书的同时，至少要编写100题左右由易逐渐到难的各种类型的程序，你才能开始做课程设计类的小项目；至少做了一到两个几百行的小项目，你还要学习算法与数据结构。你才能考虑做更大的项目。但做比较大的项目还有很多事要涉及到：你至少要大体上了解一些做软件工程的知识如果要用到数据库，你还要会进行库结构的设计，还要学会使用SQL语句。SQL语句就是结构化查询语句。结构化查询语句是嵌入在你所使用的主语言源程序中的。你还要考虑你是使用C/S（即客户机/服务器模式）结构还是用B/S结构(即浏览器/服务器模式)，现在採用B/S结构的软件为多 。如果是B/S结构，你还必须学习网页制作，包括动态网页和静态网页。所谓动态网页，就是网页上的数据可以与后台服务器进行双向通信，更新网页或后台服务器（中的数据库）中的一些内容。为此你还必须学习网络编程的相关知识。 如果是做软件工程项目，最好用面向对像的方法去实施：需求分析、编写用例、CRC卡分析类的职责、绘制UML图、考虑对像的持久化、编码、用事先编写测试代码来驱动开发、设计开发中考虑使用一些合适的设计模式、对代码经常进行重构等等。但是，一个人是否能够成为编程人才，我认为最关键的还是头三步要走好：第一步：认真学一本程序设计教科书（最好要含有大量难度循序渐进的例题）并编写大约100个程序（其中最好有三分之一以上是在各类oj上通过）第二步：阅读几个几百行到上千行的程序并编写1到2个几百行的程序（最好编写一、两个图形模式下的游戏程序）第三步：认真学好算法与数据结构，并且做大约100个与之相关的编程题 其中第二步与第三步实施中可以调换次序。但是，千万要注意：学习过程中你所看例题的难度和你所编写程序的难度一定要逐渐递增，类型要丰富。否则你的编程能力基本上不会有太大提高，永远是低水平重复就像永远只造句的人决对难以写出一篇像点样子的（比较长的）文章来。这三步走好了，你不想成为程序员都很困难！因为你已经具备了很高的编程兴趣和强大的自信心（如果你编了一两个小游戏程序的话），这种强烈的兴趣和自信将自动引导你冲破成才道路上的各个其它难关。老老实实多阅读消化经典程序、多编程序，理论与实践并重，持之以恒而不是三天打渔两天晒网，才是正道。仅仅通过看书就想成为编程高手，就像仅仅想看几本小说就能写出好小说那样是不可能的。认真学习经典书籍是很重要的，只是在学习这些书籍时，一定要注意多编写程序。 何勤 第零章 理想厨房的工作原理一种有着神奇的“魔力”和“智能”的人造设备，正在迅速地、彻底地、默默无闻或者令人震惊地改变和丰富我们所生活的大千世界。这个看起来很不起眼的，在少数场合被称为“电脑”的电器设备，是如何具有如此神奇的“魔力”和“智能”的？本章和下一章将带你开始解开这个与我们的生活和工作息息相关的当代社会最大的谜。 01节介绍理想厨房系统，0.2节通过一个炒菜实例，讲解理想厨房各部件是如何密切配合工作的。0.3是一张理想厨房系统与计算机系统的对照表。计算机从发明到现在不过70年左右的时间，然而计算机的发明、改进和普及，把人类带进了智能时代。计算机本身也变得越来越复杂、快速、小巧、种类繁多。但大多数计算机都遵循冯.诺伊曼体系结构，这为我们理解计算机的基本工作原理提供了方便。从某种角度来看，计算机就是一种人造智能生命。想要真正学会编程，通过编写的程序命令计算机工作，就必须懂得计算机的基本工作原理。就像人们要与某种具有智能的其他物种个体进行交流通信，就必须对那个物种的习性有一个基本了解一样。本章和下一章是全书的重要基础。通过这两章，读者可以了解计算机的工作过程。这些知识对学习程序设计非常有帮助。直接学习计算机工作原理是极其枯燥乏味、很困难的，因为有大量的新名词。为此，笔者付出了极大的努力，找到了一种比较好的类比方法理想厨房系统，通过这个例子就可以初步了解计算机的基本工作原理。0.1理想厨房系统：理想厨房系统，是一个通过顺序执行菜谱中的各个加工步骤，把原材料加工成菜肴的系统。它由硬件和软件（菜谱）组成。1) 软件部分：菜谱是理想厨房系统中的一个无重量、无体积、不会损坏、但可以经常更换的极为重要的“软件”部件。菜谱由一个个的加工步骤顺序组成。 每个加工步骤命令理想厨房系统完成一个基本操作（比如炒、蒸、煮、输入一种原材料等）。注意：为了解说简洁起见，在以下叙述中，我们经常把菜谱中的一个“加工步骤”称为一条“指令”。因为一个加工步骤就是一条指导理想厨房如何工作的命令。2) 硬件部分：理想厨房系统，主要由以下四个“硬件”（即实物）部件构成理想厨房、自动冰箱、输入输出设备(即配菜员和传菜生)和三条传送带。 需要注意的是，理想厨房仅仅只是理想厨房系统中的一个重要组成部分。理想厨房系统的构成简图如图0.1所示： 0.1 理想厨房系统运行示意图：0.1 理想厨房系统示意图：自动冰箱：自动冰箱负责临时保存菜谱、原材料和菜肴。它由非常多的（比如几百个）大小一样的格子组成，每个格子都有一个唯一固定编号，这个编号称为地址。地址是从0开始逐一递增的。是不是感到很奇怪：菜谱竟然也要保存在冰箱中？！这样做的道理请看本章后面。每份原材料和菜谱中的每个加工步骤，都占据冰箱中的一个格子。理想厨房：功能：负责根据从冰箱的菜谱中取到的加工步骤，进行炒菜以及进行相关的控制工作。 构成：理想厨房主要由厨房管理员、厨师、炊具和一些碟子组成，参见图0.1。 理想厨房中的各种碟子理想厨房中有一些起着重要作用的碟子：一个PC碟（又称为指令地址存放碟）：此碟中存放一个非负整数值，这个值是一个地址；它指明将要执行的指令位于自动冰箱的哪一格中。一个IR碟（又称为指令存放碟）：用来存放刚刚从冰箱中取过来的一条立即要执行的指令。理想厨房中还有若干个通用碟（图0.1中标有名称R0、R1、R2的碟）：用来临时存放从冰箱中取来的原材料或经过加工了的半成品或成品。这是由于到冰箱格子中存取物品，要比到通用碟慢得多的缘故。 指令执行的全过程理想厨房每次只能按顺序执行菜谱中的一条指令。理想厨房执行指令的流程完全是周期性的，即任意一条指令都是按照“取指令阅读分析指令执行指令”这三个阶段进行的。 厨房管理员首先根据PC碟中的值，通过三条传送带的协调工作（三条传送带如何协调工作的细节，请参见下一节），到自动冰箱的指定格中去取菜谱中的一条指令。取到理想厨房并把它存放到IR碟中之后，PC碟中的值将会加上1这是为取下一条指令预先做好准备。然后，厨房管理员阅读并分析IR碟中刚取到的这一条指令，根据该指令的指示，去做以下六类工作中的一种： 1取物品：通过三套传送带，命令自动冰箱把指定地址格子中的（炒菜加工步骤马上要用到的）原材料（通过材料传送带）传送到理想厨房中来；2加工：命令厨师按照指令的要求，对原材料作一个基本加工操作（做“炒”，“蒸”，“煮”等基本操作步骤中的某一个动作）； 3存物品：通过向三套传送带向自动冰箱发命令，把某个碟子或炊具中的成品（或半成品）送回到冰箱指定的格子中存放； 4在厨房内部进行物品传送：在厨房的各个碟子和炊具之间传送原料或半成品 ；5输入：命令配菜员为某道菜临时配备原材料；（在本章不作讨论）。6输出：命令传菜生将炒好的菜送给顾客；（在本章不作讨论）。 一条指令执行完后，理想厨房立即自动进行下一个完全类似的、新的 “取指令阅读分析指令执行指令”的工作。下面我们通过一个实例来讲述理想厨房系统的工作机制。这是本章的一个重点，因为计算机的工作原理，与之极其相似。0.2理想厨房系统的一个炒菜实例在本节中我们通过炒制一道青菜的例子，来说明理想厨房系统的工作全过程。 首先，把青菜放在冰箱地址为5的格子中，冰箱地址为6号的格子，预留给炒好的菜使用。 菜谱的所有加工步骤（又称为指令）从冰箱地址0号格开始依次按照顺序存放，编写炒青菜的菜谱如下：地址0的格子中： 取地址5（中的物品）到R0碟；地址1的格子中： 将R0（倒入炒锅中）炒好后装到R1碟；地址2的格子中： 存R1碟（中的物品）到地址6中； 可见，此菜谱一共有3个加工步骤。开始时理想厨房系统状态如下图0.3（注意：冰箱格子以及理想厨房碟子中存放的物品都用了斜体字）理想厨房 自动冰箱 碟名 碟中物品 地址 冰箱格子中物品R0R1 厨具R2 厨师PC 0 厨房管理员IR 材料传送带地址传送带0控制传送带 取01234567取地址5到R0碟将R0炒好后装到R1碟；存R1碟到地址6中；青菜图0.3菜谱和原料安放完毕后，启动理想厨房系统，开始自动化的工作。1）厨房管理员根据PC碟子中的数字“0”，知道要到地址为0的格子中取第一条指令（即加工步骤）。于是，厨房管理员向控制传送带上发出一个“取”信号，然后马上将PC碟中的数字“0”复制后放到地址传送带上。这两个信号都会到达冰箱。冰箱收到这两个信号后（知道理想厨房想要得到第0格中的物品，于是自动冰箱）将0号格的内容 “取地址5到R0碟”复制一份，将其放到材料传送带上，送往理想厨房。理想厨房收到后，将这条指令放到IR碟中。然后，厨房管理员将PC碟中的原来值增加1，以便为取下一条指令做好准备。取指令工作完成后，理想厨房系统处于如下图0.4状态： 理想厨房 自动冰箱 碟名 碟中物品 地址 冰箱格子中物品R0R1 炊具R2 厨师PC 1 厨房管理员IR 取地址5到R0碟 材料传送带地址传送带控制传送带01234567取地址5到R0碟将R0炒好后装到R1碟；存R1碟到地址6中；青菜图0.4指令执行阶段：厨房管理员读到指令存放碟（即IR碟）中的加工步骤后，知道要到冰箱地址为5的格子中去取物品，并且要放到R0碟中。因此，管理员向控制传送带上送出一个“取”信号，然后马上将5这个数字放到地址传送带上。 冰箱知道理想厨房要取5格中的物品，于是冰箱将地址为5的格子中的物品“青菜”取出来，放到材料传送带上。 材料传送带上的物品“青菜”，传到理想厨房后，按照指令的要求（通过理想厨房内部的传送带）送到了R0碟中。第一条指令执行完后，理想厨房系统处于如下图0.5所示的状态：理想厨房 自动冰箱 碟名 碟中物品 地址 冰箱格子中物品R0 青菜R1 炊具R2 厨师PC 1 厨房管理员IR 取地址5到R0碟 材料传送带 地址传送带 5控制传送带 取01234567取地址5到R0碟将R0炒好后装到R1碟；存R1碟到地址6中；青菜图0.52）接下来，开始下一条指令的取指令阶段。完全类似于前一条指令，在取指令阶段完成后，理想厨房系统处于如下图0.6状态：理想厨房 自动冰箱 碟名 碟中物品 地址 冰箱格子中物品R0 青菜（原料）R1 炊具R2 厨师PC 2 厨房管理员IR 将R0炒好后装到R1碟； 材料传送带地址传送带 1控制传送带 取01234567取地址5到R0碟将R0炒好后装到R1碟；存R1碟到地址6中；青菜图0.6指令执行阶段：管理员阅读并分析指令存放碟中的指令后，命令厨师将R0碟中的物品倒入锅中炒好后装到R1碟。第二条指令执行完后，理想厨房系统处于如下图0.7状态： 理想厨房 自动冰箱碟名 碟中物品 地址 冰箱格子中物品R0 青菜R1 熟青菜 炊具R2 厨师PC 2 厨房管理员IR 将R0炒好后装到R1碟； 材料传送带地址传送带 控制传送带 01234567取地址5到R0碟将R0炒好后装到R1碟；存R1碟到地址6中；青菜图0.73）同理，在第3条指令的取指令阶段完成后，理想厨房系统处于如下图0.8状态：理想厨房 自动冰箱碟名 碟中物品 地址 冰箱格子中物品R0生青菜R1熟青菜 炊具R2 厨师PC 3 厨房管理员IR 存R1碟到地址6中材料传送带地址传送带 控制传送带01234567取地址5到R0碟将R0炒好后装到R1碟；存R1碟到地址6中；青菜 图0.8指令执行阶段：下面开始执行“存R1碟到地址6中”这条指令。厨房管理员分析指令存放碟中的加工步骤后，知道要将R1碟中的物品，送到冰箱地址为6的格子中去存放。于是，管理员向控制传送带上发一个“存”信号，然后马上将6这个数放到地址传送带上；最后，将R1碟中的物品“熟青菜”放到材料传送带上，送往冰箱。 冰箱收到两个来自理想厨房的信号后，知道理想厨房要存放物品到6格中；于是自动冰箱（的机械手）在材料传送带旁，等待从理想厨房R1碟传来物品“熟青菜”，一旦到达，自动冰箱就将其取下，并将其存放到地址为6的格子中。完成后系统状态如图0.9：理想厨房 自动冰箱碟名 碟中物品 地址 冰箱格子中物品R0 青菜R1熟青菜 炊具R2 厨师PC 3 厨房管理员IR存R1碟到地址6中；材料传送带地址传送带6控制传送带01234567取地址5到R0碟将R0炒好后装到R1碟；存R1碟到地址6中；青菜熟青菜 图0.9 到此为止，炒青菜这道菜终于大功告成。0.3 理想厨房工作的重要特点 现在，我们对刚学到的重点知识，做一个小结：1、顺序性和周期性顺序性：理想厨房每次都只能取得和执行一条指令；一条地址为i中的指令执行完毕后，才能顺序执行地址为i+1中的指令。周期性：厨房管理员的工作完全是周期性的，即他永远在做：（命令各部件）取指令阅读分析指令发出控制命令要求各部件执行指令（简称为 取指译码执行）这一周期性的动作。只要一启动，理想厨房就永远按照这个周期性的动作，一条一条的顺序地取指令并且执行指令，这样不停地、不知疲倦地快速运行着，直到执行了一条“停止运行”指令或发生严重故障时为止。注意：顺序性与周期性是不矛盾的，顺序性指的是所有指令是按照存放在内存中的顺序来执行的，而周期性指的是每条指令的执行都是有类似固定步骤。2、有限和无限有限：厨师会做的各种不同基本加工操作所构成的集合是固定有限的（炒、煎、蒸、煮、烤等几十种），也就是说厨师学不会任何一种新的基本加工操作。厨房管理员能看懂的各种不同种类加工步骤所构成的集合也是固定有限的（从冰箱取物品、存物品到冰箱、厨师的各种不同加工方式、配菜员输入原材料到冰箱或厨房、传菜生输出菜肴给顾客等）。无限：然而，人们可以为理想厨房编写出来的菜谱数量是无限制的。因此，理想厨房可以炒出菜的品种总数也是没有限制的。有限的各种不同基本炒菜操作可以组合成无限多种不同的菜谱。3、智者与白痴理想厨房中的厨师和厨房管理员都是不知疲倦的、机械化的“白痴”，在厨师或厨房管理员的“大脑”中没有任何一道菜的（全部或一部分）加工步骤。加工制作各种菜肴的智慧（即蕴含在加工步骤中的智慧）都是来自于存放在自动冰箱中的菜谱，也就是来自于菜谱的编写者。正是由人们开动脑筋编写出来的可以让理想厨房执行的各种各样的菜谱，才使得原本白痴般的、能力极为有限然而速度却极快的理想厨房系统在炒菜方面显得似乎无所不能！人类的智慧固化在了菜谱中，理想厨房在炒菜时执行了菜谱，因而获得了人类的智能。4、主动与被动：在指令执行的三个阶段中，取指令和分析阅读指令是硬件主动进行的，而在指令的执行阶段，硬件是在软件（即菜谱中的加工步骤）的命令下被动进行的。5、不变与可变： 一个理想厨房系统的硬件组成和结构是不变的，而存放在它的冰箱中的软件（菜谱）却是可以随着客户需要而随时加以改变的； 同一个菜谱（菜谱不变）随着加工处理的原材料的种类的不同（原材料可变），可以得到不同的菜肴（菜肴可变）。比如：情炒青菜的菜谱同样可以用来清炒韭菜，只要把生韭菜放到原来放生青菜的指定格中。一条指令执行的前两个阶段（取指令、阅读分析指令），参与工作的硬件部件是不变的；而在指令的执行阶段，随着指令类型的不同，参与工作的硬件部件是可变的。6、两个中心 厨房管理员是执行指令的控制中心；厨师（加上炊具）是原材料的加工中心。理想厨房系统的工作原理，到此已经全部介绍完毕。在下一章你将看到：理想厨房的工作原理，与计算机的工作原理是极为类似的。因此在本书中，从整体上把握计算机的基本工作原理，就变成为一个比较轻松的名词替换的小游戏。0.4理想厨房系统与计算机系统术语对照表下面给出两个系统之间的术语对照表，见表0.1。表0.1术语对照表理想厨房系统电子数字计算机系统（简称计算机系统） 1.硬件设备自动冰箱（包含很多大小相等的格子）内存(又称为主存，包含很多容量相等的基本存储单元) （冰箱中的）一个格子（内存中的）一个基本存储单元材料传送带数据总线地址传送带地址总线控制信号传送带控制总线理想厨房（包含以下设备）CPU或称为微处理器（包含以下部件)厨师及炊具算术逻辑单元ALU（又称为运算器）厨房管理员控制单元（又称为控制器）通用碟通用寄存器（或数据寄存器）指令地址存放碟PC指令地址寄存器PC（又称为程序计数器）指令存放碟IR指令寄存器IR状态存放碟程序状态字寄存器PSW（又称为标志寄存器）采购员及配菜员输入设备（键盘、鼠标、网卡、U盘等）传菜生输出设备（显示器、打印机、网卡、U盘等）自动仓库外存（硬盘、U盘） 2.软件与硬件之间的接口（编写菜谱或程序的基本要素）冰箱地址（即格子的编号）内存地址（即基本存储单元的编号）厨师可做的各种炒菜基本动作算术逻辑单元可进行的各种基本运算碟子的名称寄存器的编号 理想厨房可以执行的所有不同加工动作该类型计算机的指令集3.软件特殊菜谱(机器语言形式的) 程序加工步骤指令原材料数据 炒好的菜信息（或称为结果）精确的普通菜谱高级语言源程序（又称为源代码） 简要的普通菜谱伪代码4. 系统的使用者编写特殊菜谱者用机器语言编程的程序员 编写精确的普通菜谱者用高级程序设计语言编程的程序员理想厨房系统的大堂经理和顾客计算机的用户以上表中这些与计算机相关的术语，将在1.2节进行讲解。与在理想厨房系统上运行一个菜谱极为类似，在电子计算机上运行一个程序时，上表中列出的计算机的各个部件也会协同工作，完成程序给定的任务（参见1.2节）。学习了理想厨房这个例子，理解计算机原理就变得非常容易了。0.5本章习题1、 在取一条指令到理想厨房的过程中，哪些部件会依次参与工作？哪个部件在此过程中起着核心控制作用？2、 取一份原材料的工作过程与取一条指令的工作过程有什么区别？3、 考虑一下为理想厨房编写的菜谱与给普通人看的菜谱有何不同点？4、 编写一个香菇炒青菜的菜谱。5、 写出三条传送带各自的职责。哪传送带是可以双向传递的？在取指令时，材料传送带是双向的还是单向的？第一章 二进制的数和码捷径有时候是一条弯路。 万事开头难。计算机能够“理解和懂得”的语言是二进制机器语言，计算机能够直接加工处理的，都是二进制的数和码。本章1.1对二进制进行了简介，其中最重要的概念是：字节、二进制的数和码；世界上的各种事物如何通过编码用二进制位串来表示（或近似表示）。1.2对计算机的基本构成成分、机器语言、计算机的基本工作原理进行了简介。 11二进制简介为了从整体上把握计算机的基本工作原理，并为后面的编程学习奠定扎实的基础，读者必须事先对数字信号、二进制及其相关知识有一个比较清晰的、整体的简明了解。以下进行简要介绍。1.1.1 二进制与二进制数的基本概念 十进制数 所对应的二进制数 （所对应的十六进制数）0 0 01 1 12 10 23 11 34 100 45 101 56 110 67 111 78 1000 89 1001 910 1010 A（或a）11 1011 B（或b）12 1100 C（或c）13 1101 D（或d）14 1110 E（或e）15 1111 F（或f）16 10000 10表 1.1 部分十进制数与二进制数（和十六进制数）数值对照表二进制就是只能用数字“0”和“1”来进行计数的数字系统。二进制加法运算的重要规则是： 1+1=10 ，即两个1相加，就产生了向高位的进位即“逢二进一”（做减法时则是“借一当二”），类似于十进制中的“逢十进一”(做减法时则是“借一当十”)。其它二进制加法规则更简单：0+0=0、0+1=1、1+0=1。与十进制数类似，在一个二进制数中，靠左边的数字是高位数，靠右边的数字是低位数，其中最左边的位称为最高位。我们经常用一对圆括号括住一个数值，并在圆括号外的右下角加一个整数下标，用此下标来表示该数值是几进制的（但是对于十进制数一般不用圆括号和下标）。比如：（1011）16是一个十六进制数；而（1011）2是一个二进制数。 1.1.2二进制数的多项式展开表示一个十进制整数，其数值可用以下多项式展开来表示：比如37853785=3103+7102+8101+5100 （1） 我们把（1）式中10的几次方称为权重，权重左边的乘数称为系数。（1）式中共有4个系数，从左到右依次是：“3”、“7”、“8”、“5”，权重依次分别是103、102、101、100。可见，用这种记数法表示数值时，越左边的系数，所对应的权重越大，所以就越重要。权重中的基数（即底）与表示该数的进制是一样大的，在十进制数中都是10。类似的，任意一个二进制整数，其数值也可用多项展开式来表示：比如二进制整数1011（1011）2= 123+022+121 +120 （2） 如果完全用二进制展开表示，则应当是：（1011）2= 11011+01010+1101 +1100 ，系数和权重都用二进制表示，但人们一般仅将系数用二进制表示，其他的仍用十进制。（2）式中系数从左到右依次是：“1”、“0”、“1”、“1”，而权重依次分别是23、22、21、20 （注意：这里的权重是用十进制来表示的。如果权重也用二进制，则应当分别是二进制的1011、1010、101、100）。展开式中系数的最大值一定比进制数小1，比如：在十进制记数系统中，系数的最大值是9，而在在二进制记数系统中，系数的最大值是1。12二进制相关术语简介：位、位串、字节 下面，我们来熟悉一些与书写、存储或传输一串二进制数字有关的术语。1.2.1位（bit）：书写、存储或传输单个二进制数字，我们将其称为“位”（bit）或“比特”。单个“位”中的二进制数字不是0就是1，再没有别的可能数字。任何一个只能处在两种不同稳定状态的电子元件（触发器、电容等）或者某种均匀介质（比如覆盖着磁性颗粒的金属圆盘）表面上的一个小点，都可以用来（间接）表示和存储二进制的一个“位”。如果用电容充满电状态表示二进制数“1”，就可以用电容放完电的状态来表示二进制数“0”。1.2.2位串及其长度：多个二进制数字顺序排列在一起，称之为“位串”（有些教科书称为位模式）。位串中含有的数字总个数称为位串的长度。比如：位串100110的长度是6。处于位串左边的位称为高位，处于位串右边的位是低位。位于位串最左边的位，称为最高位。1.2.3度量位串长度的基本单位字节（Byte）“位”这个二进制最小度量单位太小了，通常用起来很不方便。现代的绝大多数计算机和一些数字处理设备，大多数是以长度为8的位串字节来作为度量（部件或设备的）数据存储容量大小的一种基本单位。 把长度为8的一个位串称作为一个字节，长度为16的一个位串称为2个字节等等。长度为n的位串，一共有n/8个字节。也就是说，一个位串的长度，既可以用位串中的总位数来度量，也可以用位串所具有的字节数来度量。1.2.4二进制数据存储和传输的一些其它常用单位KB、MB和GB 字节（Byte）这个基本单位虽然大小是位（bit）这个最小二进制单位的8倍，但是在很多场合仍然还是显得太小。更大的常用单位有(在以下叙述和各种资料、书籍中，经常用字符B来代表术语字节Byte)：千字节： 1KB = 1024B = 210B 兆字节： 1MB = 1024KB = 210KB = 220B =1048576 B （约为一百零五万字节）吉字节： 1GB = 1024MB = 210MB = 230B =1073742814 B （约十亿七千多万字节）需要引起注意的是：相邻单位之间，都是1024倍的关系,而不是1000倍的关系。1.2.5位串的通常传输方式并行或串行：一个长度为n的位串，既可以用n根并排导线同时进行传输，每根导线传输一个位即并行传输（这种传输方式速度很快，但要用多根导线）；也可以只用一根导线，分为n个相等时间段，一位一位地依次先后进行传输即串行传输（这种传输方式速度较慢，但只要用一根导线）。在导线中如果用直流电的高电平（即有电流通过）来传输1，就可以用低电平（即无电流通过）来传输0。1.4二进制的数和码如果计算机仅仅只能够对一些数值进行运算在计算机刚发明的早期年代，确实就是如此那么它的应用范围就必然很狭窄。然而，现代计算机的应用范围却是极其广泛的，几乎深入到生产生活的方方面面。其根本原因在于：现代计算机不仅能够对“数值”进行运算，还能够对间接表示世界上各种各样事物（或状态）的“码”进行不同的处理。 也就是说，不仅可以直接用一个二进制位串表示一个无符号的整数，通过各种各样的编码规则还可以用二进制位串表示（或近似表示）文字、图像、声音等世界上的几乎各种事物。所以，我们想要真正懂得计算机并且学好编程，就不仅要熟悉二进制的“数”，还必须对一些常见的二进制的“码”有一个比较清晰的整体了解。以下这些内容虽然比较繁琐，然而理解起来却并不困难。十进制的数和码：我们先来看一看十进制数字系统中数与码的区别。如果3785用于表示数，则越高位的数字越重要（因为权重越大，在十进制数3785中，“3”的权重是103，而“5”的权重是100）；而3785用来表示非数值的码，则每一位数字都同样重要。码值仅相差一，所代表的意义就可以有巨大的区别。比如：3785可以代表汉字“大”，而3786可以代表汉字“小”。对数值进行运算是很有必要的，然而对间接表示事物的码进行运算通常都是毫无意义的（除非码被用来间接表示数值）。虽然用十进制3785数字串只能直接表示唯一一个非负整数，这个数的值是三千七百八十五；然而同样一个十进制数字串“3785”，通过某种编码，可以表示的事物种类却是无限制的：既可以表示码为3785的一个汉字，又可以表示任何别的什么一万个（编码从0000到9999）同类型事物中的码值为3785的一个特定事物。与十进制一样，二进制数与二进制码也有完全类似的区别。只不过在二进制中，只能用数字0和1组成的位串，来表达任何大小的数值或者表示具有任何含义的码。一位二进制数和码 如果用单个位来表示整数值，只能直接表示0和1这两个值中的一个。如果用单个“位”来表示码，则能够用来对任何（同属一种类型的）两种不同事物（或状态）制定编码规则。比如:用0表示“假”， 用1表示“真”；用0表示状态“关”，用1表示状态“开”； 用0表示“否”，用1表示“是”等等。存,取、黑,白、读,写、 阴,阳、上,下、好,坏、喜,怒、男,女、大,小等等，都可用1位二进制码来表示。两位二进制数和码如果用长度为2的一个位串来直接表示整数值，则只能够表示00（其值等于0）、01（其值等于1）、10、11这4个二进制非负整数值中的某一个。如果用长度为2的位串来进行编码，由于一共有00、01、10、11这4（即22）个码值可以使用，则能够用来对属于同一类型的4个不同的事物（或状态）制定编码规则。比如：煎、炒、蒸、煮 、加，减，乘，除、A，B，C，D、-2，-1，0，1、宿舍、教学楼、食堂、图书馆、前、后、左、右等等，都可用长度为2的二进制码来间接表示。编码和解码的一个实例 通过制定一个编码规则，比如：可以规定用00表示“D”、01表示“C”、 10表示“B”、 11表示“A” ，这就可以构成一张用4个码来表示4个字符的编码解码表，见表1.2 。用严格的数学术语来讲，所谓制定编码规则，无非是制定了一张两个集合00,01,10,11与 A,B,C,D 之间的所有元素的一对一的映射表而已（两个集合所有元素之间的这种一对一映射表可以有多张）。二进制码字符00 D01 C10 B11 A表1.2 4个字符的一张编码解码表有了这张编码解码表，先通过对字符串“CAB”进行编码，就可以用一些码值构成的二进制位串“011110”，在二进制的数字信号处理设备中间接地存储和传输这个字符串。到达目的地后，接收方也要具有同样的一张“编码解码表”，才能将这种接收到的二进制位串，翻译成它的本来意义。比如将二进制位串011110翻译成字符串“CAB”，这个过程称为解码。 编码 发送 接收 解码 CAB011110 011110CAB 图1.1 字符串的编码、发送、接收、解码全过程长度为n的二进制数和码长度为n的位串，可以表示的最大二进制非负整数1111（一共n个1）究竟是多大呢? 这很简单，将由n个1构成的此二进制数加上1，可得到1000(1的后面一共有n个0)。由这个数的多项式展开可知，它的大小就是2n。因此二进制整数1111（一共n个1）的大小为2n-1。因此，如果用长度为n的位串来直接表示一个非负整数，则可以表示的二进制数值从小到大依次是0、1、10、11、直到111111 (一共n个1，其值等于2n-1) ，一共有2n个数。用长度为n的位串来进行编码，由于一共有2n个码值可以使用，则能够用来对任意的2n个同类事物所构成的集合制定一对一的编码规则。世上的绝大多数事物都可通过编码来间接表示不添加任何别的非数字符号（正负号和小数点），用一个数字固定的位串，只能够直接表示一个非负整数（在计算机科学中，经常把非负整数称为无符号整数），有符号整数和带有小数部分的实数都不能直接用位串来表示。但是，用位串作为码，可以间接表示的事物种类却是无限的。世上一切可数的事物（或状态）都可以用各种码来间接表示。幸运的是，世上大多数人类通常可以感知到的不可数的事物（比如图像、声音、实数等）都可以通过编码来近似表示。无效码（或称为非法码）在可使用的码比（要进行编码的)集合中的元素多的情况下，就会存在一些无效码，这些无效码不代表集合中的任何一个元素。究竟哪些是无效码，是由具体编码规则决定的。比如用长度为3的位串来对某个集合中的所有元素进行编码，可用的码值一共有8（即23）个，集合中如果只有5个元素，那么必然有（8-5=）3个码是无效码。一般情况下，长度为n的位串一共有2n个码，如果用来对m个元素构成的集合进行编码，而且2n大于m,则总共有2n-m个无效码。不定长度编码还有一类码的长度不一样的编码方式，常常用比较短的码表示集合中经常出现的元素；比如哈夫曼编码就是一种不定长度的编码（关于哈夫曼编码请参见其它书籍或资料）。1.6 表示字符的编码1.6.1 ASCII码“目前计算机中用得最广泛的字符集及其编码，是由美国国家标准局(ANSI)制定的ASCII码（American Standard Code for Information Interchange，美国标准信息交换码），它已被国际标准化组织（ISO）定为国际标准，称为ISO 646标准。适用于所有拉丁文字字母，ASCII码有7位码和8位码（即扩展ASCII码）两种形式。 7位ASCII码是用七位二进制数进行编码的，可以表示128个字