自1995年首次发布以来，Java编程语言作为一种教学语言变得日益重要，现在已经成为初级计算自1995年首次发布以来，Java编程语言作为一种教学语言变得日益重要，现在已经成为初级计算课程斯 坦 福 大 学的标准语言。Java语言可以让学生编写高度交互式程序，这充分激发了他们的学习兴趣。但Java语言很复杂，老师和学生们在理解Java语言的结构时，复杂性成为了最大的障碍。

　　在本书中，斯坦福大学教授、著名的计算机科学教育领导者Eric S.Roberts着重强调了更适合于初学者的友好讲解方式，使用ACM Java库简化编程。本书简练清晰地介绍了传统CS1课程的内容，同时也包含了最近的Computing Curriculum 2001报告计算机科学卷中指定为CS101O或CS111O课程的全部主题。

Augusta Ada Byron, Lady Lovelace(1815—1852)

　　Augusta Ada Byron是英国著名诗人拜伦(Lord Byron)的女儿。当年有人鼓励她从事自己感兴趣的科学和数学专业，尽管那个时候几乎不允许妇女学习这些科目。17岁时，Ada遇到了Charles Babbage。Charles Babbage是一位杰出的英国科学家，他一生致力于设计实现数学计算功能的机器—— 尽管他未能完成这种机器的结构。但Ada坚信Babbage分析机的潜力，她记录了大量有关其设计的笔记，并编写了一些复杂的数学程序。这些程序使许多人把她当作第一位编程人员。为了纪念她，1980年美国国防部将该编程语言命名为Ada。

　　想想我们在21世纪初具有的优势，很难相信1940年竟然还没有计算机。而今天它们到处都是，用流行语来说(至少标题作者这么说)：我们生活在计算机时代。

1.1  计算简史

　　从某种意义上说，计算从古代就有了。许多早期数学都是为了解决现实中重要的计算问题，如监控牧群数量，计算小块土地面积，以及记录商业交易等。这些活动要求人们开发新的计算技术，有些情况下，还需要发明机器帮助计算，如算盘。算盘是一种简单的计算设备，由能够在杆上滑动的珠子组成，已经在亚洲使用了几千年，很可能在公元前2000年就有了。

　　纵观其整个历史，计算的发展相对缓慢。1623年，德国科学家Wilhelm Schickard发明了第一台为人所知的机械计算机，它能够自动执行简单的算术计算。虽然Schickard的机器在“三十年战争(1618－1648)”的破坏中消失于历史，但法国哲学家Blaise Pascal在17世纪40年代使用相同的技术构造了一台机械加法器，其仿制品现在陈列于法国巴黎国立工艺学院(Conservatoire des Arts et Métiers)。1673年，德国数学家Gottfried Leibniz开发了一种相当精密的设备，它能够进行加减乘除运算。所有这些设备都完全是机械的，没有引擎，也没有其他能量来源。操作员通过将金属轮设置到特殊位置来输入数字，运行过程中，转动这些轮子，可以设置机器的其他部分，改变输出显示。

　　工业革命时期，技术的快速发展使开发新的机械计算方法成为可能。蒸汽机已经提供了工厂和铁路所需的能量。是否有人能够用蒸汽机来驱动更加精密的计算机器(这些机器能够利用自身动力实现重要计算)呢？在那种情况下，问这种问题合情合理。然而，在取得进展之前，人们不得不提出这一问题，并开始寻找答案。必然的思想火花来自于英国数学家Charles Babbage。在计算历史中，他是最值得关注的人之一。

　　Babbage一生设计了两台不同的计算机器，分别命名为差分机和分析机，每台机器都对当时的计算机器进行了极大改进。他一生的遗憾是这两个项目都未能完成。他设计用来产生数学函数表的差分机，最终由瑞典发明家在1854年—— 提出最初设计30年后制造成功。 分析机是Babbage一生的梦想，直到1871年他去世时仍未完成。即便如此，其设计仍然包含了现代计算机中的许多重要特征。更重要的是，Babbage将分析机构想为一种多用途机器，依靠编程能够执行许多不同功能。在Babbage的设计中，分析机的运行由一段小孔控制，这些小孔被打在一张机器能够阅读的卡片上。改变小孔的样式，就可以改变机器的行为，执行不同类型的计算。

　　Augusta Ada Byron是诗人拜伦(Lord Byron)与妻子Annabella的女儿。我们知道，Babbage的许多工作都来源于她的著作。和大多数同时代的人一样，Ada意识到了分析机的潜力，并成为了它的拥护者。她为该机器设计了一些复杂程序，也因此成为了第一位编程人员。20世纪70年代，美国国防部为了纪念她在这方面做出的贡献，将自己的编程语言命名为Ada。

　　Babbage设计的有些方面确实影响了后来的计算历史，例如使用打孔卡来控制进程。法国发明家Joseph Marie Jacquard首先将这种思想作为织布机设备(后来被称为Jacquard织布机)的一部分，使织布过程自动化。1890年，Herman Hollerith使用打孔卡片使美国人口普查数据表格统计实现了自动化。为了让这种技术市场化，Hollerith建立了一个公司，这就是后来的IBM(国际商用机器)公司，它在20世纪大部分时间占据着计算机产业的主导地位。

　　Babbage版的可编程计算机直到20世纪40年代才变为现实，电子学的出现使超越机械设备成为可能，之前都是机械设备在计算领域占主导地位。1939年末，爱荷华州州立学院的John Atanasoff和他的学生Clifford Barry组装了第一台电子计算机原型。1942年5月，他们完成了包含300个电子管的具有全面执行能力的机器。这台计算机能够解决线性方程这类小的系统问题。Atanasoff-Barry计算机在设计方面做了一些调整，它可以执行更复杂的计算，但是这一项目的工作被第二次世界大战中断了。

　　第一台大规模电子计算机是电子数字积分计算机(Electronic Numerical Integrator and Computer，简称ENIAC)。1946年，在宾夕法尼亚大学摩尔学校J.Presper Eckert和John Mauchly指导下完成的ENIAC，包含了18 000多个电子管，占满了一个30ft长、50ft宽的房间。 ENIAC通过将电线插入被称为配线架(patch pannel)的小钉板状设备里进行编程。通过将配线架上不同的插孔与电线连接起来，操作员可以控制ENIAC的行为。这种类型的编程需要具备机器内部运行的基本知识。事实证明，这种编程方法比ENIAC发明者想象的要困难得多。

　　也许现代计算技术最重大的突破发生于1946年。这一年，普林斯顿高级研究中心的John von Neumann(冯?诺伊曼)提出可以用相同的方法表示程序和数据，并且这些程序和数据可以存储在相同的内存里。这一概念极大地简化了编程过程，几乎是所有现代计算机的基础。由于这方面的设计，据说现代计算机采用的都是冯?诺伊曼体系结构。

　　随着ENIAC的完成和冯?诺伊曼体系存储编程概念的发展，计算技术也快速发展起来。新系统、新概念被引入如此快速发展的系列产品中，将它们全部罗列出来毫无意义。根据基本技术，大多数历史学家将现代计算机的发展阶段分为如下4代：

● 第一代  第一代电子计算机使用电子管作为其内部电路的基础。这一计算时期从1939年Atanasoff-Barry原型开始。

● 第二代  1947年晶体管的发明将计算机带入了新的一代。晶体管是半导体设备，它的功能与电子管一样，但它比电子管小，需要少量电子能量。第一台使用晶体管的计算机是1958年推出的IBM 7090。

● 第三代  虽然晶体管比电子管小，但是包含100 000或1 000 000个单个晶体管的计算机仍需要占用很大的空间。第三代计算机随着1959年集成电路(芯片)的发展而出现。集成电路(芯片)是一块小的硅晶片，它通过图像压印，包含了许多连接在一起的晶体管。第一台在结构上使用集成电路的计算机是1964年出现的IBM 360。

● 第四代  第四代计算开始于1975年，将计算机的整个处理单元集成到单个硅芯片上。那一年，构建集成电路的技术使这一想法成为可能。该制作技术被称为大规模集成。由单个芯片组成的计算机处理器称为微处理器，今天大多数计算机都在使用这种处理器。

　　从历史的观点上说，第一代和第二代的早期计算机与现代计算机的前身同样重要，只是现在没有使用它们而已。它们是计算机科学中的恐龙：巨大、笨拙、智能低下，很快就灭绝。集成电路的发明者之一、Intel公司的创始人Robert Noyce评论说，与ENIAC相比，典型的现代计算机“速度快20倍，内存大，可靠性强上千倍，消耗的能量相当于一个电灯泡，而不是一辆机车，体积是它的1/30 000，成本是它的1/10 000。”当然，计算机还有未来时代。

1.2  计算机科学的含义

　　成长于现代世界，这可能会让你明白计算机的含义。然而，本文更多关注的是计算机科学，而不是作为物理设备的计算机。

　　乍一看，计算机和科学好像是不可调和的一对词语。按其典型用法，科学是指对自然现象的研究；当人们说到生物科学或物理学时，我们可以理解，并觉得这种用法很恰当。计算机科学好像和这不一样。计算机是人造物品，这一点让我们勉强将计算机研究归类为科学。毕竟，现代技术也可以生产汽车，但我们没有讨论“汽车科学”。相反，我们说“汽车工程”或“汽车技术”。计算机为什么就不同呢？

　　要回答这个问题，关键是认识到计算机本身只是原因的一部分。今天可以在本地计算机商店购买到的物理机器只是计算机硬件的一个示例。它是有形的。您可以拿起它，把它带回家，放在桌子上。如果需要，可以把它作为制门器使用，尽管有点贵。但是，如果除了硬件之处什么也没有，如果您拿到的机器和它下线时完全一样，那么作为制门器可能是它能做的几件事之一。现代计算机是多用途机器，具有执行广泛任务的潜力。然而，要实现其潜力，必须对计算机进行编程。编程计算机的行为就是给它提供一组指令(程序)，这些指令指定解决问题必需的所有步骤。这些程序通常称为软件，只有软件和硬件相结合才可能进行计算。

　　相对于硬件而言，软件是抽象的、无形的实体。它是一系列简单的步骤和操作，表述为一种硬件可以解释的明确语言。讨论计算机科学时，主要关注计算机软件领域，更重要的是，关注更加抽象的问题解决域。问题解决是具有高度挑战性的活动，它需要创造性、技能和训练。在很大程度上，计算机科学被认为是解决问题的科学，其解决方案恰好与计算机有关。

　　这不是说计算机本身不重要。没有计算机时，人们只能解决相对简单的计算问题。最近50多年以来，计算机的存在使人们以一种及时高效的方式，解决日益困难和复杂的问题变成了可能。而且，随着基础技术的提高，解决更复杂的问题也是可能的。然而，由于要解决的问题越来越复杂，寻找有效解决方案策略的任务也越来越复杂。这样就要求解决问题的科学要随着计算技术的发展而发展。

1.3  计算机硬件简介

　　计算机由软件控制，也可以为每个单独的应用程序重新设计软件，计算机解决复杂问题的灵活性即来源于这一实际。考虑到软件体现了问题解决策略—— 这些策略是计算机科学的本质，因此本书专门讨论了计算软件方面的问题。虽然如此，本章花些时间简要讨论一下计算机硬件结构也很有必要。理由很简单：编程是一门在实践中学习的学科。只阅读本书，即使解决了纸上的所有练习，也不会成为编程人员。编程是一个需要动手的工作，这项工作需要与计算机配合。

　　要使用计算机，就要了解其硬件。要知道如何开机，如何使用键盘输入程序，如何执行已经写好的程序。很遗憾，各计算机系统执行这些操作所必须遵循的步骤差别很大。作为编写普通教科书的人，我无法给出特定系统的工作原理，相反，必须着重讨论通用规则，这些规则在用户可能使用的任何一台计算机上都是通用的。阅读这一部分的时候，用户应该看着自己的计算机，看看一般性讨论如何应用于自己的计算机。

　　今天使用的大多数计算机都由如图1-1所示的组件组成。被称为总线的通信信道将图中每个组件连接起来，它允许数据在各独立的单元间流动。单个组件在下面几节介绍。

图1-1  典型的计算机组件

1.3.1  CPU

　　CPU(中央处理器)是计算机的“大脑”。它执行实际计算，协调整个计算机的活动。程序决定CPU的行为，这些程序由存储在内存系统里的一系列编码指令组成。例如，一条指令可能命令计算机相加两个数字。另一条指令可能让一个字符出现在计算机屏幕上。通过执行适当序列的简单指令，CPU可以执行复杂任务。

　　现代计算机中，CPU由集成电路—— 一个微型硅芯片组成，该芯片压印集成了数百万个连接形成大型电路的晶体管，这些电路可以实现简单的算术运算和逻辑运算。

1.3.2  内存

　　计算机执行程序时，必须能够存储程序本身和计算所涉及到的数据。总的来说，任何能够存储和恢复信息的计算机硬件都是存储设备。程序主动运行时使用的存储设备构成其主存储器，通常称为内存。自从1946年冯?诺伊曼首次提出这一思想以来，计算机就使用同样的内存来存储组成程序的单个指令和计算中所使用的数据。

　　内存系统设计得非常有效，因此它们可以让CPU非常迅速地访问其内容。今天的计算机中，内存通常被扩建为一个特殊的集成电路芯片，该芯片称为随机存取存储器，简称RAM。 随机存取存储器允许程序在任何时候使用任何存储单元的内容。

1.3.3  辅助存储器

　　程序运行时，计算机通常将活动数据保存在内存里，但是大多数主存设备存在不足，它们只是在计算机开机时才发挥作用。关闭计算机后，所有存储在主存里的信息都会丢失。要存储永久数据，需要使用一种存储设备，这种设备不需要电源就可以保存信息。这种设备就是辅助存储器。

　　今天的计算机使用了多种辅助存储设备。几乎每台买到的计算机都有硬盘，即使关闭计算机，硬盘也可以存储大量已有信息。创作或编辑程序通常在硬盘上进行。如果要将程序转移到另一台计算机上或为了保存而进行备份，可以将程序复制到可移动媒介—— 软盘、可写CD或内存条。

1.3.4  输入/输出(I/O)设备

　　对于有用的计算机而言，它必须有某种方式可以与外界用户进行交流。计算机输入通常由键盘上输入的字符组成，计算机输出通常显示在计算机显示屏上或打印机上。总的来说，执行输入和输出操作的硬件设备称为I/O设备。

　　不同计算机的I/O设备差异很大。除了标准的按字母顺序排列的键之外，计算机键盘的排列也各不相同，甚至是一些重要的键也使用不同的名称。例如，用于表示一行结束的键，有的键盘标记的是Return，有的则是Enter。有的计算机系统中，使用键盘上方或旁边的特殊功能键(它们提供简单编辑操作)就可以改变程序。而有些系统中，使用被称为鼠标来选择要改变的程序文本，也可以完成相同的任务。无论哪种情况，计算机都清楚当前输入位置，通常在屏幕上用闪烁的线或矩形(指针)来指示。

1.3.5  网络

　　图1-1中最后的组件是标记为网络的星形符号，表示到其他计算机群的连接，那些计算机连接在一起作为Internet的一部分。Internet是全球计算机的大集合，里面的计算机通过允许它们共享数据和程序的通信线路连接在一起。很多情况下，网络只是I/O结构的一部分。现代计算机的输入输出操作不仅仅局限于本地机器，而是扩展到了由Internet连接起来的广阔世界，记住这一点很有帮助。学习Java时，网络特别重要。因为Java作为一种编程语言，其成功之处就是紧随网络的发展，这一点将在本章稍后讨论。

1.4  算法

　　前面已经介绍了计算机系统的结构，下面继续讨论计算机科学。因为计算机科学是利用计算机解决问题的学科，所以要理解一个概念，它是计算机科学和问题解决抽象学科的基础，这个概念就是算法。“算法”一词来自于19世纪波斯数学家Abu Ja'far Mohammed ibn M?s? al-Khow?rizm?的名字，他在一本名为《Kitab al jabr w’al-muqabala》的杂志上发表了一篇数学论文，其标题产生了英语单词“algebra”(代数学)。广义上说，可以将算法理解为解决问题的策略。然而，要理解计算机科学家如何使用这个术语，需要规范其直观理解，严格其定义。

　　要成为算法，解决方案方法必须符合3条基本要求。第一，算法必须以明确形式表示，这种形式可以让读者确切明白包含了哪些步骤。第二，算法内的步骤必须有效，即这些步骤有可能在实践中实现。例如，包含操作“用r乘以it的准确值”的方法就无效，因为不可能计算出it的准确值。第三，算法不能永远运行，必须在有限时间内显示答案。总之，算法必须：

● 有明确无误的定义。

● 有效，即其步骤必须可执行。

● 有限，即经过有限步运行之后可以终止。

　　稍后开始使用复杂算法时，这些属性就显得特别重要。这里，只要认为算法是抽象解决方案策略即可—— 这些策略最终会成为您所编写程序的核心。

　　很快您就会发现，算法—— 就像要解决的问题一样—— 变化非常复杂。有些问题很简单，大脑中马上就会闪现合适的算法，于是可以编写程序解决这样的问题，不会有太多麻烦。然而，随着问题变得越来越复杂，想出能合适地解决这些问题的算法就需要更多的思考。大多数情况下，几种不同的算法可以用来解决特殊问题。写出最终程序之前，需要考虑多种潜在解决方案。

1.5  编程过程的几个阶段

　　用计算机解决问题从概念上可以分为明显的两个步骤第一，需要开发一种解决问题的算法，或选择一种已有的算法。这一部分过程称为算法设计。第二步就是用编程语言将这种算法表述为计算机程序。这一过程称为编码。

　　随着编程的开始，编码过程—— 将算法转换为功能程序—— 似乎是该过程中更难的阶段。作为刚刚入门的编程人员，可以从具有简单解决方案的简单问题入手，算法设计阶段似乎不特别具有挑战性。然而，因为不熟悉语言及其规则，所以有时编码好像很难、很随意。我希望可以安心地说，学习更多编程过程之后，编码很快就会变得很容易。同时，随着请求解决的问题的复杂性不断增加，算法设计也会变得更难。

　　本书中介绍的新算法，最初通常用英语表示。虽然英语常常不够准确，但只要是在两个完全讲英语的人之间交流，它也是一种表达解决方案策略的合理语言。很明显，如果要给只会讲俄语的人表述自己的算法，英语就不是一个合适的选择。同样，要给计算机表达算法，英语也不是合适的选择。虽然计算机科学家研究这一问题已几十年，但让计算机理解英语、俄语或其他人类语言仍然超出了当前技术范围。要让计算机能够解释算法，需要将算法转换为编程语言。有许多编程语言，如Fortran、BASIC、Pascal、Lisp、C和C++等。本书将学习如何使用编程语言Java，它由Sun Microsystems于1995年开发，并已成为工业和计算机科学课程的标准。

1.5.1  创建和编辑程序

　　在大多数计算机系统上运行程序之前，需要输入程序文本并将它存放在文件里。文件是一个总名称，它集合了所有存储在计算机辅助存储器里的信息。每个文件必须有一个名称。名称通常分为两个部分，中间用句点隔开，如MyProgram.java。创建文件时，需要决定根名称(名称里句号之前的部分)来说明文件所包含的内容。文件名中句点之后的部分表示文件的种类，称为扩展名。有些扩展名有预定的含义，例如，扩展名为.java表示用Java语言所写的程序文件。包含程序文本的文件称为源文件。

　　通常，输入或改变文件内容的过程称为编辑文件。因为不同的计算机系统编辑过程大不相同，因此不可能用一种适用于所有硬件类型的方法描述该过程。在特定计算机系统上工作，需要学习创建新文件和编辑已有文件的方法。可以在与所使用的编程环境有关的手册或在线文档上找到这些信息。

1.5.2  编译过程

　　创建源文件以后，下一步就是将程序转换为计算机可以理解的形式。Java、C和C++都是计算机科学家所说的高级语言。设计这些语言是为了让编程人员更方便地表达算法，而不需要他们深入理解基本软件究竟如何执行这些算法。一般来说，高级语言具有独立的区分单个计算机结构的特定特性。然而，每个计算机系统内部只能理解专用于那一类硬件的低级语言，这种语言称为机器语言。例如，Apple Macintosh和Windows计算机使用不同的内部机器语言，即使它们都能执行用高级语言编写的程序。

　　要让用高级语言编写的程序可以在不同的计算机系统上运行，有两种基本策略。典型方法是使用被称为编译器的程序，将所写的程序转换为适合计算机运行的低级机器语言。使用这种方法，具有不同硬件结构的计算机就需要不同的转换器。例如，如果为Macintosh编写了C语言程序，就需要一个编译器将C语言程序转换为Macintosh的机器语言程序。如果要在Window计算机上运行相同的程序，就需要一个不同的编译器，因为基本硬件使用的是不同的机器语言。

　　第二种方法是将程序转换为独立于基本结构的中间语言。对于所有特定的机器结构，这些中间语言程序的运行都由解释程序执行，由解释程序在计算机上执行中间语言。例如，如果中间语言程序包含将两个数字相加的指令，解释程序通过执行在基本硬件上执行加法所必需的所有指令来完成这项任务。然而，相对于编译器而言，解释程序实际没有产生机器语言指令来执行原始程序指定的特定加法运算。相反，解释程序通过执行有相同效果的指令模仿了加法运算。

　　现代Java系统使用混合策略，结合了编译器和解释程序的功能。在最初编译阶段，Java将程序翻译为普通的独立于基本硬件的中间语言。然后，一种称为Java虚拟机(简称JVM)的程序会解释中间语言，并执行机器的中间语言。运行Java虚拟机的程序通常将中间代码块编译为内部机器语言。因此，Java通常可以达到传统解释程序不能达到的效果。

　　在典型的编译器系统中，编译器将您所写的源文件翻译到包含该计算机系统相关指令的第二个文件(称为目标文件)中。然后，该目标文件与其他目标文件相结合，通常包括被称为库的预定义目标文件，该目标文件包含用于不同普通操作的机器语言指令。这些组合文件共同生成一个可以在系统上运行的可执行文件。将所有单个目标文件组合为一个可执行文件的过程称为链接。图1-2显示的是整个编译过程。

图1-2  典型编译过程的几个阶段

　　在Java中，过程稍微详细一些。如前所述，Java产生中间代码，这些代码存储在被称为类文件的文件里。这些类文件与其他类文件和库结合，生成中间程序的完整版本。该程序版本的常见格式是单独文件经过压缩的集合，称为JAR存档文件。然后通过Java虚拟机来解释，并在计算机上显示输出，过程如图1-3所示。

图1-3  运行Java程序的阶段

1.5.3  编程错误与调试

　　除了翻译功能之外，编译器还可以执行另一项重要功能。和人类语言一样，编程语言有它自己的词汇和语法。语法是一套规则，它决定不同语言部分如何结合在一起。这些语法规则可以判定哪些语句结构比较好，哪些不好。例如，英语中说“we goes”就不对，因为主语和动词之间数的形式不一致。每种编程语言都有自己的语法，它决定该语言中程序的各个元素如何组织在一起。

　　编译程序时，编译器首先会检查程序的语法是否正确。如果违反了语法规则，编译器会显示一条错误信息。由于违反这些语法规则而产生的错误称为语法错误。只要收到编译器指示语法错误的信息，都必须重新编辑程序来更正错误。

　　虽然语法错误令人沮丧，尤其是对新的编程人员而言，但它们不是沮丧的最大来源。通常，如果编写的程序不能正确运行，往往不是语法问题，而是逻辑问题。许多情况下，完美的逻辑程序不知何故就会出现不正确的答案或根本就不能产生答案。检查程序，发现在逻辑方面出现了错误—— 编程人员将这种类型的错误称为故障(bug)。查找和改正这种错误的过程称为调试，它是编程的重要组成部分。

　　故障具有很强的隐蔽性，这很容易让人灰心。您绝对相信算法是正确的，但会后来发现它不能执行一些前面忽略的案例。或者，您知道程序的某个部分需要进一步修改，只是后来忘了。或者，您可能犯了一个似乎很愚蠢的错误，以至于您不相信有人会犯下如此严重的错误。

　　不要紧张。您在一个优秀的公司之中，甚至最优秀的编程人员也有此经历。实际上，所有编程人员都犯过逻辑错误，您也一样。算法需要技巧，通常您会发现并没有好好使用它。

　　从某种程度上说，发现自己易错的缺点是每一个编程人员必经的重要过程。20世纪60年代，计算机科学家前辈Maurice Wilkes描述其经历时写道：

　　不知何故，在摩尔学校及毕业之后，有人总认为编程过程中没有特别的困难。我总记得那个时刻，它让我渐渐明白，我未来生活中很大一部分时间都要花在查找自己程序里的错误上。

　　优秀编程人员与普通编程人员之间的区别不是他们可以完全避免故障，而是他们努力将已完成代码里的故障数量减少到最小。设计好一个算法并将它转换为语法正确的程序后，工作并没有完成，明白这一点至关重要。基本上，程序里总会有个别故障。编程人员的任务就是找出故障并修复它。完成一个之后，应该继续找出下一个故障并修复它。要对自己的程序总是有所怀疑，要尽可能彻底地测试它们。

1.5.4  软件维护

　　软件开发最令人惊讶的问题之一是程序需要维护。实际上，软件开发研究显示，对于大多数程序而言，软件发行之后，因为维护软件而给编程人员支付的费用占总成本的80%~90%。然而，在软件方面，要准确理解维护是什么意思有点困难。乍一听，这个概念有点古怪。如果用在小轿车或大桥上，什么东西坏掉了就需要维护——金属锈蚀、某块机械连接因过度使用而报废，或者什么东西因事故而被打碎等。这些情况都不适用于软件。代码本身不会锈蚀。一遍又一遍地重复使用相同的程序丝毫不会降低其功能。偶然误用的确会产生不良后果，但不会损害程序本身；即使损害了程序本身，它也可以从备份副本中恢复。在那种环境中，维护是什么意思呢？

　　

　　两个主要原因使软件需要维护。第一，即使经过大量测试，有时甚至实际使用多年，原始代码中也仍然存在故障。因此，当出现始料未及的情况时，以前隐匿的故障就会导致程序失效。所以，调试是程序维护的重要部分。但它不是最重要的部分。更重要的部分，特别是按照它在程序维护总成本贡献方面的大小来说，是功能强化。编写程序就是为了使用；它们通常比其他方法更快、成本更低地执行客户需要完成的任务。同时，程序很可能不会执行客户的任何要求。程序使用一段时间之后，客户会想，如果程序能够做其他事，或者以不同的方式做，或者以一种更有用的方式显示数据，或者运行得更快一点，或者能扩展容量，或者有一些更简单但更吸引人的功能(贸易中通常称为额外特征)，那就太好了。由于软件具有极大的灵活性，因此供应者有办法解决这些问题。无论哪种情况—— 修复故障或添加功能—— 必须有人参与进来，查看程序，弄明白发生了什么，做一些必需的修改，检验这些修改是否可行，然后发行新版本。这个过程很艰难，很消耗时间，代价很高，也会出错。

　　程序维护十分困难，一部分原因是许多编程人员编写程序时没有长远打算。对他们而言，程序能够运行似乎就足够了，然后他们就转而做其他的事情。编写程序以便其他人可以理解、维护这些程序的学科称为软件工程。我们鼓励编写表现良好工程风格的程序。

　　编写程序时，想象一下，两年之后其他人再看到它们时会有何感想。您的程序还有意义吗？ 程序会告诉新读者您要做什么吗？改变它容易吗？它看起来是不是晦涩难懂？如果设身处地为未来维护人员(许多公司新的编程人员，您很可能就是那个角色)想一下，这会让你明白为什么好的风格至关重要。

　　许多编程新手很迷惑，因为没有一套准确规则可以遵循，从而确保好的编程风格。好的软件工程不是过程食谱。相反，它是一门技术，还带有一点艺术性质。实践最重要。一个人要想写出好的程序，就要动手写，并且要阅读其他人的程序，就像一个人要成为一个小说家一样。好的编程需要有针对未来维护人员的训练—— 这些训练不能抄近道或被遗忘，不能匆忙完成。好的编程风格需要开发一种审美感—— 意思就是程序应该可读，表示正确。

1.6  Java和面向对象范例

　　正如本章前面所述，本文使用Java编程语言来阐明编程和计算机科学的一般概念。为什么要用Java呢？主要原因是Java鼓励编程人员思考编程过程。

　　过去十多年，计算机科学和编程都经历了某种革命。和大多数革命一样—— 要么是政治剧变要么是概念重构，正如1962年Thomas Kuhn在他的书The Structure of Scientific Revolutions里所描写的那样—— 一种思想的出现推动了这种改变，这种思想对现有的理论构架(或范例)提出了挑战。起初，两种观点互不相让。曾经有段时间，旧秩序占据着主导地位。但是随着时间的推移，新思想的力量和声望不断增长，直至取代了旧秩序，Kuhn称之为范例转换。今天的编程世界中，旧秩序以过程范例为代表，在过程范例中，程序由在数据上运行的过程和功能的集合组成。挑战者是面向对象范例。在面向对象范例中，程序被视为“对象”的集合，数据和相关操作被封装在综合单元里。许多传统语言，包括Fortran、Pascal和C，体现的都是过程范例。面向对象范例最著名的代表是Smalltalk、C++和Java。

　　虽然面向对象语言以牺牲过程语言为代价得到了普及，但是认为面向对象和过程范例互相排斥则是错误的。不同编程范例之间与其说是互相竞争的，不如说是互补的。面向对象的范例和过程范例及其他重要范例，例如嵌入LISP和Scheme中的功能性编程风格，实际中都有很多重要的应用程序。即使在单个应用程序的情况下，也很可能发现使用了多个方法。作为编程人员，必须掌握许多不同的范例，以便使用最适合于当前任务的概念模型。在本书中，可以在面向对象的范例方面打下坚实的基础，同时也会学到过程范例的一些知识。

1.6.1  面向对象编程的历史

　　面向对象编程的思想并不是很新奇。第一种面向对象的语言是SIMULA，它是一种编码模拟语言，由斯堪的纳维亚(北欧一地区)计算机科学家Ole-Johan Dahl、Bj?rn、Myhrhaug和Kristen Nygaard于20世纪60年代设计。由于其远远领先于时代的设计，SIMULA率先提出了许多概念，这些概念后来成为编程中的通用概念，包括抽象数据的概念和许多现代面向对象范例。实际上，用来描述面向对象系统的大多数术语都来源于SIMULA最初版及后续版 SIMULA 67的原始报告。

　　然而，许多年来，SIMULA大部分时间都被束之高阁。很少有人注意到它，也许能听到它的唯一地方就是在编程语言设计课上。计算界公认的第一种面向对象语言是Smalltalk，由Xerox帕洛阿尔托研究中心(通常称为Xerox PARC)于20世纪70年代后期开发。Smalltalk的目的，Adele Goldberg和David Robson所著的Smalltalk-80：The Language and Its Implementation一书中说，就是让广大读者可以理解编程。因此，Smalltalk是Xerox PARC成果的一部分，这些成果催生了许多现代用户界面技术的开发，这些技术现在是个人计算机的标准。

　　尽管Smalltalk有许多吸引人的特征和简化编程过程的高度交互式用户环境，但它从未取得广泛的商业成就。业界总体上对面向对象编程感兴趣，在其中心思想与编程语言C的变量合并之后，C语言已经成为了行业标准。尽管在设计基于C语言的面向对象语言方面有一些类似努力，但最成功的是C++，它是20世纪80年代初由Bjarne Stroustrup在AT&T贝尔实验室设计的。通过让面向对象技术与现有的C代码结合，C++让许多编程人员能够以一种渐进的、革命性的方式采用面向对象的范例。

1.6.2  Java编程语言

　　面向对象编程历史中的最近一项是Sun微系统公司James Gosling领导的编程人员团队对Java的开发。1991年，Sun公司开始这个项目(它最终创造了Java)时，其目标是设计一种能够适用于编写嵌入客户电子设备微处理器的语言。如果项目专注于这个目标，Java就不可能发展到现在这个程度。计算案例通常这样，为了适应不断变化的产业环境，Java项目的方向也在其开发阶段改变了。导致改变的主要原因是20世纪90年代早期出现的Internet的显著增长，特别是World Wide Web(简称WWW)的出现。WWW是全球计算机用户提供的互连资源的空前集合。1993年，当人们对Web的兴趣空前高涨时，Sun公司将Java重新设计为一个可以编写高度交互式、基于Web应用程序的工具。这个决定被证明正合时宜。自从1995年5月发布Java以来，它在理论计算领域和商业计算领域都产生了强烈影响。在此过程中，面向对象编程已经被牢牢确立为计算产业的中心范例。

　　要感受Java的力量，看一看图1-4就会有所了解，图1-4是一篇关于原始Java设计的优秀论文的摘要，这篇论文是James Gosling和Henry McGilton在1996年写的。论文中，作者用一长串形容词来描述Java：简单的、面向对象的、熟悉的、充满活力的、安全的、结构中立的、可移植的、高性能的、解释的、线程的和动态的。图1-4的讨论会让您明白这些专门用语的意思。随着对Java和计算机科学的不断学习，就更能理解这些特征的重要性。

　　

　　JAVA?编程语言的设计目标

　　计算环境(必须部署软件)的本质推动着Java?编程语言的设计需求。

　　Internet和WWW的飞速增长让我们以全新的方式看待软件开发和发布。要在一个电子商务和分布式的世界里生存，Java技术就必须在异构、分布式网络中的多平台上确保开发出安全、高性能和颇具活力的应用程序。

　　在异构网络里多平台上的操作，使二进制分布、发行、升级、补丁等传统配置失效。要在这种复杂的环境中生存下来，Java编程语言必须是结构中性的、可移植的和动态适应的。

　　满足这些需要的系统很简单，因此许多开发人员可以很容易地对它进行编程；熟悉的，以致现在的开发人员很容易就能学会Java编程语言；面向对象的，要利用现代软件开发方法论，适应分布式客户端－服务器端应用程序；多线程的，为了应用程序的高性能，这些应用程序需要执行多个并发活动，如多媒体；解释的，为了最大方便和动态性能。

　　上面的要求是一些专门用语的集合，因此在继续讨论之前，我们研究其中一些术语及各自的优点。

　　简单的、面向对象的和熟悉的

　　Java编程语言的基本特征之一就是简单，编程人员不需要大量的训练就可以进行编程，并与目前软件实践相协调。很快就可以掌握Java技术的基本概念；编程人员从一开始就会高产。

　　Java编程语言完全是面向对象的。对象技术在经过30年的酝酿之后最终找到了通向编程主流的途径。分布式、基于系统的客户端－服务器端需求符合基于对象软件的封装、消息传递范例。要在日益复杂的、基于网络的环境里发挥作用，编程系统必须采用面向对象的概念。Java技术提供了一个整洁有效的面向对象的开发平台。

　　使用Java编程语言的编程人员可以访问经过测试的对象的现有库，这些库可以提供多种功能性，范围可以从通过I/O和网络界面获得的基本数据类型一直到图形用户界面工具箱。可以扩展这些库来提供新的行为。

　　即使C++作为一种执行语言被拒绝，让Java编程语言尽可能看起来和C++一样，也会使它成为一种熟悉的语言，同时删除了C++不必要的复杂性。让Java编程语言保留面向对象的许多特征，“形式和感觉”都像C++，这样编程人员就可以很方便地转移到Java平台，很快就会变得多产。 

　　健壮的和安全的

　　设计Java编程语言就是为了创建高度可靠的软件。它提供广泛的编译时检查，然后是二级运行时检查。语言特征指导编程人员养成可靠的编程习惯。

　　内存管理模型也非常简单：用新的运算符创建对象。没有明显的编程人员定义的指针数据类型，没有指针算法和自动无用单元收集。这种简单的内存管理模型减少了困扰C和C++编程人员的编程错误的整个类。可以开发Java代码，在产品代码装运之前，相信系统很快就会发现许多错误，相信主要问题不是隐匿的。  图1-4  Java开发人员在语言设计上的洞察力

　　Java技术在分布式环境中运行，这意味着安全性极为重要。Java技术的安全特征被设计到语言和运行系统之中，它让您可以构造从外部无法入侵的应用程序。网络环境中，用Java编程语言写的应用程序是安全的，可以防止入侵，这些入侵来自未授权代码企图到达幕后创建病毒或入侵文件系统。

　　体系结构中立的和可移植的

　　Java技术支持应用程序，这些应用程序会被部署到异构网络环境。在那种环境中，应用程序必须能够在不同硬件结构上执行。在这些硬件平台上，应用程序必须在多种操作系统上执行，并能够与多编程语言界面互操作。为了适应操作系统的多样性，Java Compiler? 产品生成了字节码—— 一种结构中立的中间格式，可以将代码有效传递到多种硬件和软件平台。Java技术解释的特征解决了二进制分布问题和版本问题；相同的Java编程语言位元码可以在任何平台上运行。

　　结构中立性只是真正便携式系统的一部分。Java技术通过严格基本的语言定义，让便携性又进了一步。Java技术奠定了基础，指定了其基本数据类型的大小，以及算子的行为。 程序在每个平台上都是相同的—在所有硬件和软件结构中所有数据类型都兼容。

　　Java技术的结构中立性和便携式语言平台被称为Java虚拟机。它是抽象机器的规范，Java编程语言编译器可以为它生成代码。Java虚拟机为专用硬件和软件平台的特殊执行提供了虚拟机的具体实现。Java虚拟机主要基于POSIX界面规范—— 便携式系统界面的行业标准定义。在新结构上执行Java虚拟机是一项相对简单的任务，只要目标平台满足基本要求就行，如支持多线程。

　　高性能的

　　性能总是一个需要考虑的因素。Java平台通过采用一种配置取得了较高性能，通过这种配置，解释程序可以全速运行，而不需要检查运行时的环境。自动无用单元收集器作为一种低优先权的后台线程运行，确保内存在需要时可用的可能性提高，这样会产生更好的性能。可以设计需要大量运算能力的应用程序，这样可以按要求用本地机器代码编写计算密集的部分，并通过界面与Java平台连接。通常，用户认为交互式应用程序反应迅速，即使它们需要进行解释。

　　解释的、线程的和动态的

　　Java解释程序可以直接在任何计算机上执行Java字节码，这些计算机通过端口连接解释程序和运行时系统。在解释平台(如Java技术系统)中，程序的链接阶段是简单的、递增的和轻量级的。受益于更加快速的开发周期—— 原型、实验，相对于传统重型编译、链接和测试周期而言，快速开发是正常情况。

　　现代基于网络的应用程序，如适用于WWW的HotJava? Browser，通常需要同时做几件事。使用HotJava Browser的用户可以同时运行几部动画片，同时可以下载图像、滚动页面。Java技术的多线程功能提供创建包含活动的多个同时线程应用程序的方法。多线程为终端用户提供了高度的交互性。

　　Java平台支持语言级的多线程和精确的同步原语：语言库提供线程类，运行时系统提供监控器和条件锁定原语。而且，在库级别，Java技术的高级系统库线程是安全的，库提供的功能是可用的，不会与执行的多个并发线程相冲突。   图1-4  (续)

　　Java编译程序在其编译时的静态检查是严格的，在链接阶段，语言和运行时系统是动态的。只有需要时才会链接类。按照不同资源甚至是网络资源的要求，可以将新代码模块链接进来。在HotJava浏览器和类似应用程序中，可以从任何地方加载交互式可执行代码，这样就可以进行应用程序的透明更新。结果促进了在线服务的持续发展；它们可以保持创新和新鲜，吸引更多客户；刺激Internet上电子商务的增长。

　　　　　—— 摘自James Gosling，Henry McGilton. 

      　　White Paper：The Java Language Environment 图1-4  (续)

1.7  Java和WWW

　　从某种程序上说，Java作为语言的最初成功与20世纪90年代初计算机网络的刺激密不可分。从1969年ARPANET(当今Internet的前身)最初的4个节点连成一线起，计算机网络到那时已经存在了20年。整个20世纪90年代，推动Internet技术空前繁荣的，与其说是网络本身，还不如说是WWW的发明，通过点击交互式链接，它允许用户从一个文档移动到另一个文档。

　　包含交互式链接的文档称为超文本—— 这一术语是1965年由Ted Nelson创造的，他计划创建一个综合的文档集合，这个集合与今天的WWW十分类似。然而，基本概念还要早些，第一位总统科学顾问(Presidential Science Advisor)Vannevar Bush在1945年提出了相同的思想。然而，这种分布式超文本系统的思想直到1989年才成功实行。当时位于日内瓦的欧洲粒子物理研究所(CERN)的Tim Berners-Lee提出创建一个他称为WWW的资料档案库。1991年，CERN的执行者完成了第一个浏览器，它是用来显示Web文档的程序，通过这种方式，用户可以很容易跟踪内部链接访问Web的其他部分。

　　CERN取得成果的新闻传播到物理领域其他研究人员耳中之后，更多团队便开始研究浏览器。这些产品中，最成功的是Mosaic浏览器，它是位于美国伊利诺斯州Champaign的国家超级电脑应用中心(NCSA)开发的。1993年，Mosaic浏览器出现后，对Web的兴趣也爆发了。 执行WWW资料档案库的计算机系统的数量从1993年的约500个猛增到2003年的35 000 000多个。对Internet上Web的热情也激发了大量的商业兴趣，催生了一些新公司，发布了一些商业Web浏览器，如Apple公司的Safari、Netscape公司的Navigator及Microsoft公司的Internet Explorer。

　　WWW上可用文档的数量飞速增长，因为Internet用户可以方便地创建新的文档并把它们添加到Web。如果要将新文档添加到Web，要做的就是在装有称为Web服务器程序的系统上创建文件，Web服务器允许外部用户访问系统上的文件。服务器输出的单个文件称为Web页面。Web页面通常是用一种称为HTML的语言写的，HTML是超文本链接标识语言的简称。HTML文档由文本、格式化信息和到Web上其他页面的链接组成。每个页面都由统一资源定位符(简称URL)标识，它让Web 浏览器可以在现有页面的海洋中找到页面。WWW的URL以前缀“http://”开始，紧接着描述的是Internet路径，通过该路径可以到达想访问的页面。

　　Java特别有趣的一点是，虚拟机并不总是运行于存储程序的同一台计算机上。 Java设计目标之一是让语言在网络上能够运行良好。这种设计目标特别有趣的结果是，Java支持创建applet(一种Java小程序)，它是一种运行于网络浏览器上下文中的程序。 运行applet的过程如图1-5所示。

1.8  小结

　　本章的目的是为学习计算机科学和编程(该过程将从第2章正式开始)打好基础。本章着重介绍了编程过程主要包含的内容，以及它如何延伸到计算机科学更大的范围。

　　本章介绍的重点包括以下内容。

● 计算机系统的物理组件—— 看得见、摸得着的部分—— 硬件。然而，计算机硬件要发挥作用，必须事先指定一系列指令(程序)告诉硬件要做什么。这些程序称为软件。

● 计算机科学与其说是计算机的科学，还不如说是使用计算机解决问题的科学。

● 使用计算机解决问题的策略称为算法。要成为算法，策略必须有明确无误的定义，必须有效、有限。

● 程序一般使用高级语言编写，人类读者可以理解所设计的这种高级语言。

● 执行用高级语言写的程序有两种基本策略：编译和解释。编译器将程序转换为特殊计算机系统的机器语言，因此，允许程序直接在该计算机的硬件上运行。解释程序通过读取程序结构，执行必需的操作来模拟该过程。

● Java在程序执行方面使用混合策略。Java编译器将程序转换为中间语言，然后解释该中间语言。中间语言像机器语言一样在假想计算机(称为Java 虚拟机)上执行。

● 编程语言有一套语法规则，它决定程序结构是否正确。编译器使用这些语法规则来检查程序，当违反规则时，它就会报告语法错误。

● 编程错误最严重的类型是，语法正确，但是程序产生了不正确的结果或者根本没有结果。这种类型的错误是一种逻辑错误，它阻止程序正确解决问题，称为故障。发现和修复故障的过程称为调试。

● 大多数程序必须定期更新，以便更正故障或适应应用程序要求的变化。这个过程称为软件维护。设计程序以方便维护是软件工程的重要部分。

● 本文使用Java编程语言来阐明编程过程。区别Java和其前身语言的基本特征就是，Java是一种面向对象语言，它可以将数据和所有相关操作封装到概念上统一的实体(对象)里。Java在20世纪90年代“Internet爆发”的时期开始设计，目的就是在网络环境中能运行良好。特别是，Java可以在web浏览器的上下文中运行程序。以这种方式运行的程序称为applet。

1.9  复习题

　　1. 即使Babbage的两台机器都没有完成，但是分析机的设计引入了一种新思想，这种思想成为了现代计算的中心。区分分析机和早期差分机的重要特征是什么？

　　2. 通常谁被认为是第一位编程人员？

　　3. 冯?诺伊曼结构的核心概念是什么？

　　4. 硬件和软件之间有何不同？

　　5. 传统科学关注抽象理论还是宇宙本质—— 不是人造物品。构成计算机科学核心的抽象概念是什么？

　　6. 算法必须满足的3个标准是什么？

　　7. 算法设计和编码之间有何差别？哪种活动通常更难一些？

　　8. 术语“高级语言”是什么意思？作为本文基础使用的高级语言是什么？

　　9. 解释程序和编译器有何不同？

　　10. 源文件和目标文件之间的关系如何？作为编程人员，哪些文件可以直接使用？

　　11. 语法错误和故障之间有何不同？

　　12. 判断题：优秀的编程人员从来不会在其程序中引入故障。

　　13. 判断题：编写程序的主要成本是程序的开发；一旦程序投入使用，编程成本就可忽略不计。

　　14. 术语“软件维护”是什么意思？

　　15. 编写程序时，遵循好的软件工程规则为什么很重要？

　　16. 面向对象和过程范例有什么主要不同点？

　　17. 在Web浏览器的控制下运行applet有哪些步骤？运行Java applet与运行Java应用程序的方式有何不同？

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

目   录

第1章  前言 1

1.1  计算简史 1

1.2  计算机科学的含义 3

1.3  计算机硬件简介 4

     1.3.1  CPU 5

     1.3.2  内存 5

     1.3.3  辅助存储器 5

     1.3.4   输入/输出(I/O)设备 5

     1.3.5  网络 5

1.4  算法 6

1.5  编程过程的几个阶段 6

     1.5.1  创建和编辑程序 7

     1.5.2  编译过程 7

     1.5.3  编程错误与调试 9

     1.5.4  软件维护 9

1.6  Java和面向对象范例 10

     1.6.1  面向对象编程的历史 11

     1.6.2  Java编程语言 11

1.7  Java和WWW 14

1.8  小结 15

1.9  复习题 16

第2章  编程示例 17

2.1  “Hello world”程序 18

     2.1.1  注释 19

     2.1.2  输入 19

     2.1.3  主类 19

2.2  编程过程的观点 21

2.3  两数相加的程序 22

2.4  编程习语和模式 25

2.5  类和对象 26

     2.5.1  类的层次结构 27

     2.5.2  Program类的层次结构 28

2.6  图形程序 29

     2.6.1  HelloProgram示例回顾 29

     2.6.2  向GObjects发送消息 30

     2.6.3  GObject类的层次结构 32

     2.6.4  GRect类 33

     2.6.5  GOval类 36

     2.6.6  GLine类 37

2.7 小结 38

2.8  复习题 39

2.9  编程练习 40

第3章  表达式 43

3.1  原始数据类型 44

3.2  常量与变量 45

     3.2 1  常量 45

     3.2 2  变量 46

     3.2 3  声明 47

     3.2 4  命名常量 48

3.3  运算符和操作数 48

     3.3.1  合并整数和浮点数 49

     3.3 2  整数除法和余数运算符 50

     3.3 3  优先级 50

     3.3 4  应用优先级规则 52

     3.3 5  类型转换 53

3.4  赋值语句 55

     3.4.1  简写赋值运算符 57

     3.4.2  递增运算符和递减运算符 58

3.5  布尔表达式 58

     3.5 1  关系运算符 58

     3.5 2  逻辑运算符 59

     3.5 3  短路赋值 61

     3.5 4  标记 62

     3.5.5  Boolean计算示例 62

3.6  设计改变 63

     3.6 1  可读性的重要性 63

     3.6 2  使用命名常量支持程序维护 64

     3.6 3  使用命名常量支持程序开发 64

3.7  小结 66

3.8  复习题 68

3.9  编程练习 69

第4章  语句形式 73

4.1  Java的语句类型 74

     4.1.1  简单语句 74

     4.1.2  复合语句 75

     4.1.3  控制语句 76

4.2  控制语句和问题解决 76

     4.2.1  一般化Add2Integers程序 77

     4.2.2  重复N次模式 78

     4.2.3  “读取到指定条件为止”模式 79

4.3  if 语句 80

     4.3.1  单行if语句 82

     4.3.2  多行if语句 82

     4.3.3  if-else语句 83

     4.3.4  级联if语句 83

     4.3.5  ?:运算符 84

4.4  switch语句 85

4.5  while语句 88

     4.5.1  使用while循环 88

     4.5.2  无限循环 90

     4.5.3  解决“循环到中途”问题 90

4.6  for语句 92

     4.6.1  for和while之间的关系 94

     4.6.2  在浮点数据中使用for语句 95

     4.6.3  嵌套for语句 96

     4.6.4  简单的图形动画 97

4.7  小结 99

4.8  复习题 100

4.9  编程练习 100

第5章  方法 105

5.1  方法概述 105

     5.1.1  作为降低复杂性机制的方法 106

     5.1.2  作为编程人员工具而不是

           用户工具的方法 106

     5.1.3  作为表达式的方法调用 107

     5.1.4  作为消息的方法调用 108

5.2  编写自己的方法 109

     5.2.1  方法定义的格式 109

     5.2.2  return语句 110

     5.2.3  包含内部控制结构的方法 111

     5.2.4  返回非数字值的方法 112

     5.2.5  断言方法 115

5.3  方法调用过程的技巧 116

     5.3.1  参数传递 117

     5.3.2  从其他方法内调用方法 120

5.4  分解 126

     5.4.1  逐步细化 126

     5.4.2  指定参数 128

     5.4.3  自顶向下设计 129

     5.4.4  寻找共同特征 130

     5.4.5  完成分解 131

5.5  算法方法 132

     5.5.1  “强力”方法 132

     5.5.2  欧几里得算法 133

     5.5.3  讨论欧几里得算法的正确性 133

     5.5.4  两种算法的效率比较 134

5.6  小结 135

5.7  复习题 135

5.8  编程练习 136

第6章  对象和类 141

6.1  使用RandomGenerator类 142

     6.1.1  伪随机数 142

     6.1.2  使用RandomGenerator类 143

     6.1.3  随机数种子的作用 145

6.2  javadoc文档系统 146

6.3  定义自己的类 149

     6.3.1  类定义的结构 149

     6.3.2  控制条目的可见性 150

     6.3.3  封装 150

6.4  表示学生信息 150

     6.4.1  声明实例变量 151

     6.4.2  完成类定义 151

     6.4.3  编写javadoc注释 154

     6.4.4  写构造函数 154

     6.4.5  getters and setters 155

     6.4.6  toString方法 155

     6.4.7  定义类中的命名常量 156

     6.4.8  使用Student类 156

6.5  有理数 157

6.6  扩展现有类 161

     6.6.1  创建类表示实心三角形 161

     6.6.2  继承构造函数的规则 165

     6.6.3  继承方法的规则 165

6.7  小结 167

6.8  复习题 168

6.9  编程练习 169

第7章  对象和内存 175

7.1  内存结构 176

     7.1.1  位、字节和字 176

     7.1.2  二进制和十六进制表示法 176

     7.1.3  内存地址 178

7.2  将内存分配给变量 179

     7.2.1  Rational类的内存图 180

     7.2.2  无用单元收集 184

7.3  原始类型与对象 185

     7.3.1  参数传递 185

     7.3.2  包装类 187

     7.3.3  装箱和拆箱 189

7.4  链接对象 190

     7.4.1  链接结构里的消息传递：

           Gondor灯塔 191

     7.4.2  链接结构的内部表示法 193

7.5  小结 194

7.6  复习题 195

7.7  编程练习 195

第8章  字符串和字符 199

8.1  枚举的原则 200

     8.1.1  在计算机内部表示枚举类型 200

     8.1.2  将枚举类型作为整数表示 201

     8.1.3  定义新的枚举类型 202

8.2  字符 203

     8.2.1  char数据类型 203

     8.2.2  ASCII和Unicode编码系统 203

     8.2.3  字符常量 205

     8.2.4  Unicode表示法的重要属性 205

     8.2.5  特殊字符 206

     8.2.6  字符算法 207

     8.2.7  Character类中有用的方法 208

     8.2.8  包含字符的控制语句 209

8.3  作为抽象概念的字符串 210

     8.3.1  从整体和简化论的观点

           考察字符串 210

     8.3.2  抽象类型的概念 210

8.4  使用String类中的方法 211

     8.4.1  确定字符串长度 212

     8.4.2  从字符串中选择字符 212

     8.4.3  串联 213

     8.4.4  摘录部分字符串 215

     8.4.5  比较两个字符串 215

     8.4.6  在字符串内搜索 216

     8.4.7  大小写字母转换 217

8.5  字符串处理案例研究 218

     8.5.1  应用自顶向下设计 218

     8.5.2  实现translateLine 219

     8.5.3  考虑空格和标点符号 220

     8.5.4  StringTokenizer类 222

     8.5.5  完成实现 223

8.6  小结 226

8.7  复习题 227

8.8  编程练习 228

第9章  面向对象图形 237

9.1  acm.graphics模型 238

9.2  acm.graphics程序包的结构 238

     9.2.1  GCanvas类 239

     9.2.2  Color类的更多细节 241

     9.2.3  GPoint类、GDimension

           类和GRectangle类 241

     9.2.4  GMath类 242

     9.2.5  GObject类及其子类 243

9.3  使用形状类 246

     9.3.1  GLabel类 246

　　

     9.3.2  GRect类及其子类

           (GRoundRect和G3DRect) 248

     9.3.3  GOval类 249

     9.3.4  GLine类 249

     9.3.5  GArc类 250

     9.3.6  GImage类 253

     9.3.7  GPolygon类 257

9.4  创建复合对象 262

     9.4.1  简单的GCompound示例 263

     9.4.2  GCompound坐标系 265

     9.4.3  使用GCompound的对象分解 265

     9.4.4  嵌套GCompound对象 269

9.5  小结 270

9.6  复习题 271

9.7  编程练习 272

第10章  事件驱动程序 279

10.1  Java事件模型 280

10.2  简单的事件驱动程序 281

10.3  响应鼠标事件 283

　　　10.3.1  MouseListener和

　　　　　　MouseMotionListener接口 283

　　　10.3.2  重写侦听器方法 283

　　　10.3.3  画线程序 284

　　　10.3.4  在画布上拖动对象 286

10.4  响应键盘事件 288

10.5  创建简单的GUI 289

10.6  Swing 交互器层次结构 291

　　　10.6.1  JButton类 292

　　　10.6.2  JToggleButton 类 293

　　　10.6.3  JCheckBox类 293

　　　10.6.4  JRadioButton类和

　　　　　　ButtonGroup类 295

　　　10.6.5  JSlider类和JLabel类 296

　　　10.6.6  JComboBox类 297

　　　10.6.7  JTextField类、IntField

　　　　　　类和DoubleField类 300

10.7  管理组件布局 304

　　　10.7.1  Java窗口层次结构 304

　　　10.7.2  布局管理器 305

　　　10.7.3  BorderLayout布局管理器 305

　　　10.7.4  FlowLayout布局管理器 307

　　　10.7.5  GridLayout布局管理器 308

　　　10.7.6  标准布局管理器的不足 309

10.8  使用TableLayout类 309

　　　10.8.1  比较GridLayout与

　　　　　　TableLayout 310

　　　10.8.2  使用TableLayout创建

             温度转换器 310

　　　10.8.3  指定约束 312

　　　10.8.4  使用TableLayout创建

             简单的计算器 313

10.9  小结 319

10.10  复习题 320

10.11  编程练习 321

第11章  数组与ArrayList类 327

11.1  数组简介 328

　　　11.1.1  数组声明 328

　　　11.1.2  数组选择 329

　　　11.1.3  简单数组的示例 330

　　　11.1.4  改变索引范围 331

　　　11.1.5  对象的数组 332

　　　11.1.6  在图形程序中使用数组 332

　　　11.1.7  ++和––运算符的区别 334

11.2  数组的内部表示法 335

11.3  数组作为参数传递 337

11.4  使用数组制作表格 341

11.5  数组初始化 343

11.6  多维数组 344

　　　11.6.1  将多维数组传递给方法 345

　　　11.6.2  初始化多维数组 346

11.7  图像处理 346

　　　11.7.1  图像的表示方式 346

　　　11.7.2  使用GImage类操作图像 347

　　　11.7.3  位操作 348

　　　11.7.4  使用位操作分解像素组件 350

　　　11.7.5  创建灰度图像 350

　　　11.7.6  通过平均使图像变得平滑 351

　　　11.7.7  隐藏复杂性 353

11.8  ArrayList类 354

11.9  小结 358

11.10  复习题 359

11.11  编程练习 360

第12章  搜索与排序 369

12.1  搜索 370

　　　12.1.1  在整数数组中搜索 370

　　　12.1.2  搜索表 370

　　　12.1.3  折半搜索 373

　　　12.1.4  搜索算法的相对效率 375

12.2  排序 376

　　　12.2.1  给整数数组排序 376

　　　12.2.2  选项排序算法 377

　　　12.2.3  评估选项排序的效率 379

　　　12.2.4  测量程序的运行时间 380

　　　12.2.5  分析选项排序算法 381

　　　12.2.6  基数排序算法 382

12.3  评估算法效率 384

　　　12.3.1  big-O表示法 385

　　　12.3.2  big-O的标准简化 385

　　　12.3.3  选项排序计算的复杂性 385

　　　12.3.4  根据代码结构预测计算

　　　　　　的复杂性 386

　　　12.3.5  最坏情况与一般情况的

　　　　　　复杂性 387

12.4  使用数据文件 388

　　　12.4.1  文件的概念 388

　　　12.4.2  阅读Java中的文本文件 389

　　　12.4.3  异常处理 391

　　　12.4.4  倒转文件的程序 393

　　　12.4.5  交互地选择文件 394

　　　12.4.6  使用Scanner类 395

　　　12.4.7  输出文件 397

12.5  小结 397

12.6  复习题 398

12.7  编程练习 400

第13章  数组与ArrayList类 405

13.1  ArrayList类回顾 406

　　　13.1.1  动态分配的能力 406

　　　13.1.2  区分表示法和行为 408

13.2  HashMap类 409

　　　13.2.1  映射的简单示例 409

　　　13.2.2  探讨可能的实现策略 410

　　　13.2.3  实现O(1)性能 411

　　　13.2.4  散列法思想 412

　　　13.2.5  散列码 412

　　　13.2.6  复制散列码 413

　　　13.2.7  映射类的简单实现 413

　　　13.2.8  实现hashCode方法 416

　　　13.2.9  调整存储区的数量 418

13.3  Java集合架构 418

　　　13.3.1  Java集合架构的结构 419

　　　13.3.2  Collection层次结构 420

　　　13.3.3  区分行为和表示法 421

　　　13.3.4  迭代器 422

　　　13.3.5  Arrays和Collections

             方法库 424

13.4  面向对象设计的原则 426

　　　13.4.1  统一主题的重要性 427

　　　13.4.2  简单和信息隐藏的原则 428

　　　13.4.3  满足客户的需要 428

　　　13.4.4  灵活性的好处 429

　　　13.4.5  稳定的意义 429

13.5  小结 430

13.6  复习题 430

13.7  编程练习 431

第14章  展望 435

14.1  递归 436

　　　14.1.1  递归的简单示例 436

　　　14.1.2  Factorial 函数 437

　　　14.1.3  信任的递归式跳跃 440

　　　14.1.4  递归的范例 441

　　　14.1.5  图形递归 442

　　　14.1.6  递归式思考 444

14.2  并发 445

　　　14.2.1  进程与线程 445

　　　14.2.2  并发的简单示例 445

14.3  使用网络 448

14.4  编程模式 448

　　　14.4.1  模型/视图/控制器模式 449

　　　14.4.2  说明性示例：用图表示电子

             数据表的数据 449

　　

14.5  小结 453

14.6  复习题 454

14.7  编程练习 454