图书
电子书
课程
VIP会员
书课包

数据结构和算法 Python和C++语言描述

978-7-115-52740-0
作者: [美] 戴维·M.瑞德（David M. Reed）约翰·策勒（John Zelle）
译者: 肖鉴明
编辑: 陈冀康
分类: Python C++ 算法

图书目录:

详情

本书使用Python 和C++两种编程语言来介绍数据结构。全书内容共15 章。书中首先介绍了抽象与分析、数据的抽象等数据结构的基本原理和知识，然后结合Python 的特点介绍了容器类、链式结构和迭代器、堆栈和队列、递归、树；随后，简单介绍了C++语言的知识，并进一步讲解了C++类、C++的动态内存、C++的链式结构、C++模板、堆、平衡树和散列表、图等内容；最后对算法技术进行了总结。每章最后给出了一些练习题和编程练习，帮助读者复习巩固所学的知识。 本书适合作为高等院校计算机相关专业数据结构课程的教材和参考书，也适合对数据结构知识感兴趣的读者学习参考。

图书摘要

版权信息

书名：数据结构和算法（Python和C++语言描述）

ISBN：978-7-115-52740-0

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

著　　　　[美] 戴维·M.瑞德（David M. Reed）

　　　　　[美] 约翰·策勒（John Zelle）

译　　　　肖鉴明

责任编辑　陈冀康

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315


Simplified Chinese translation copyright ©2020 by Posts and Telecommunications Press ALL RIGHTS RESERVED

Data Structures and Algorithms Using Python and C++ by David M. Reed, John Zelle.

Copyright © 2009 Franklin, Beedle & Associates Incorporated.

本书中文简体版由Franklin, Beedle & Associates公司授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式或任何手段复制和传播。

版权所有，侵权必究。


本书使用Python和C++两种编程语言来介绍数据结构。全书内容共15章。书中首先介绍了抽象与分析、数据的抽象等数据结构的基本原理和知识，然后结合Python的特点介绍了容器类、链式结构和迭代器、堆栈和队列、递归、树；随后，简单介绍了C++语言的知识，并进一步讲解了C++类、C++的动态内存、C++的链式结构、C++模板、堆、平衡树和散列表、图等内容；最后对算法技术进行了总结。每章最后给出了一些练习题和编程练习，帮助读者复习巩固所学的知识。

本书适合作为高等院校计算机相关专业数据结构课程的教材和参考书，也适合对数据结构感兴趣的读者学习参考。


本书用于高等院校的数据结构课程。Python是一门可以作为入门课程的优秀的计算机语言。它相对简单的语法能够让学生更加专注于解决问题，而不用把很多精力放在对具体的编程语言的语法的理解上。Python的内置数据结构和大型标准库还能够让学生比用其他语言更简便地编写一些更有趣的程序。本书假设学生已经学习了Python的基本语法，并且已经接触过类的用法。大多数使用Python的传统编程导论课程都涵盖了这些基础的内容，有些课程甚至可能涵盖了这本书里所涉及的一些主题。

Python的面向对象特性，让它成为一种非常适合用来学习数据结构课程的语言。我们发现，大多数学习完编程导论课程的学生都已经知道了如何使用类，但是他们中的许多人还需要更多的知识和经验，来学习如何设计和编写自己的类。考虑到在编程导论课程里用来学习设计类的时间非常有限，这样的情形并不奇怪。我们可以通过学习本书前几章里包含的一些关于类的设计的例子来解决这个问题。

学生在数据结构课程里学习使用Python语言，可以继续扩展他们的知识和技能，并且能够通过一种更简单、更熟悉的语言来获得设计和编写类的经验。Python语言也使得学习链式结构变得相对更容易，这是因为Python里的每个名称都是一个引用。因此如果要编写链式结构，学生不用再去学习其他的语法。与学习使用更复杂的语言相比，这些优势能够让主题内容的教学速度更快。

把Python用于数据结构课程的一个潜在缺点是：它隐藏了内存管理的复杂性。这个特性在学习第1门课程的时候是一个优势，但我们认为在学习第2门课程时，学生应该需要开始理解Python解释器隐藏的底层级细节了，这也是非常重要的内容。由于我们学习的是Python，因此可以在更短的时间内完成对基本数据结构的相关内容和知识的掌握。也就是说即使在只需要一个学期的数据结构课程里，学生也是有时间去学习第2种编程语言的。在学生不断提高他们的Python编程技能，并同时学习了本书的前几章之后，他们可以相对更容易地去学习第2种面向对象的编程语言。通过使用C++作为第2种编程语言，学生将接触到比较底层的编译语言。C++的语法比Python更复杂，但是好在学生通过Python的学习已经掌握了基本的编程概念，这使得学习C++的语法不会有非常大的障碍。例如，既然他们已经理解了编程的基本概念以及各个语句（如条件语句和循环语句）的语义，那么他们也就只用重点学习一下这些语句在C++中的语法就行了。

一旦学生学习了基本的C++语法，就可以通过在C++里重写链式结构来涵盖动态内存管理的概念。这部分内容会对基本的数据结构概念进行加强，同时也会开始关注内存管理问题。本书无意提供C++语言的完整介绍，只会引入C++语言的一个比较大的子集，从而方便学生理解内存管理的底层细节，并学会在C++里编写面向对象的代码。在介绍了C++语言的基础知识之后，本书还会提供Python实现，让学生用C++来实现它们，从而介绍一些更高级的数据结构。换句话说，Python代码成了用来呈现关键算法和数据结构的可执行的伪代码。

由于Python能够让我们比其他语言更快地学习完主题内容，因此数据结构课程中用5个学分就可以学完本书的大部分内容。如果用两个学期来教学整本书，每个学期的课程就只需要3个学分。在这两个学期，每个学期3个学分的数据结构课程安排如下：前7章的内容在8周内完成；然后在剩下的7周里完成前3章关于C++的内容，从而让学生有足够的时间来编写大量的C++代码；之后剩下的5章将在第2个学期的3个学分课程里进行详细的介绍。因此，教师可以在课程开始的时候，先进行一周的复习，用更多的时间来讨论在最后3章里提到的高级算法和数据结构。

根据学生使用面向对象编程的经验，本书前3章的教学进度可以安排得很快，也可以更详细地阐述。第1章介绍算法的渐进运行时分析，从而让我们可以分析所有数据结构实现的运行时间。本书较早地介绍了一个Python的单元测试框架，从而可以方便学生比较正式地测试他们的代码。在完成第4章的链式结构的讨论之后，教师可以比较快地介绍一下堆栈和队列的基本概念，或者也可以通过提供的示例应用程序来继续介绍各个算法，以及加强设计技能的教学。虽然一些编程导论课程已经涵盖了递归，但大多数学生在第一次学习的时候，并不能够完全地理解递归。由于对树的研究需要用到递归的概念，因此本书会在第7章的树的内容之前插入关于递归内容的一章（第6章）。

在关于树的一章之后，本书内容就会切换到C++语言。第8章在基于读者已经了解掌握了Python的情况下，开始对C++进行简单的介绍。第9章介绍在C++里编写和使用类的相关细节。第10章和第11章介绍动态内存以及在C++里如何编写链式结构。我们强烈建议读者按顺序来学习第8章到第11章。第12章介绍使用和编写C++模板代码的基础知识，但并没有完全覆盖模板的所有相关内容。由于其他的章节都不需要理解模板，读者也可以选择跳过第12章。最后3章介绍了一些高级算法和数据结构。虽然这3章之间会有一些相互的参考，但是它们可以任意调换顺序。

我们要感谢维滕贝格大学（Wittenberg University）的Nancy Saks和Steve Bogaerts对本书C++章节的早期草稿版本的意见。我们还要感谢Franklin, Beedle& Associates出版社，尤其是Jim Leisy和Tom Sumner。我们还要感谢我们的编辑Stephanie Welch，他发现了许多小错误，帮助我们提高了这本书的质量。

David感谢美国Capital大学提供了休假的支持，这让他开始了这本书的编著。David还要感谢那些使用了本书早期草稿版本，并且提出改进建议的学生们。以下这些美国Capital大学的学生因为提出了很多的合理化建议而值得得到特别认可：Kyle Beal、Michael Herold、Jeff Huenemann、John Larison以及Brenton Wolfe。最后，David要感谢他的妻子Sherri在他完成本书所需的无数个小时里给予的支持和理解。

John感谢他在沃特伯格大学（Wartburg College）的部门的同事们，他们一直为他的努力写作提供支持；也要感谢他的学生们，他们帮助John“尝试体验”了一些学习材料。最重要的是，John感谢他的家人，特别是他的妻子Elizabeth Bingham，感谢她的爱、支持和理解，让这个项目成为可能。


本书由异步社区（https://www.epubit.com/）出品，社区为您提供相关资源和后续服务。

本书提供如下资源：

要获得以上配套资源，请在异步社区本书页面中点击 ，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。

如果您是教师，希望获得教学配套资源，请在社区本书页面中直接联系本书的责任编辑。

作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。

当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“提交勘误”，输入勘误信息，点击“提交”按钮即可，如下图所示。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。

扫描下方二维码，您将会在异步社区微信服务号中看到本书信息及相关的服务提示。

微信服务号

我们的联系邮箱是contact@epubit.com.cn。

如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。

如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/ selfpublish/submission即可）。

如果学校、培训机构或企业想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。

如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。

“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com或扫描下方异步社区二维码。

“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。

异步社区


目标

不论你信不信，计算机编程的第一门课里就已经涵盖了解决任何可以用计算机处理的问题所需要的所有工具了。著名的计算机科学家——艾伦·麦席森·图灵（Alan Mathison Turing）曾经提出过一个现在已被人们普遍接受的猜想：任何可以用计算机解决的问题都只需要用到所有计算机编程语言都包含的基本语句。这些基本语句也就是：条件语句（例如if）、循环语句（例如for和while）以及存储和检索数据的能力。可能你已经知道了这些，想知道还有什么其他的可以学习。这是个好问题，我在下面的内容里回答。

如果将计算机编程看成与造房子类似的过程，那么掌握了编程知识就相当于是知道了如何使用锤子、螺丝刀、锯子和钻头等这些工具。这些工具虽然可以说是建造所有的房子都需要用到的基本工具，但会用它们并不意味着你可以精确高效地建造一个适合居住的房子，更不用说建造一个满足现代建筑规范且有一定规模的房子了。这不是说你不能用这些工具做一些有用的事情，如做一个长凳或鸟笼，只是你还没有准备好应对大型项目所带来的挑战。

编程就像建造房子一样，在处理大型项目的时候是需要更多额外的知识、技术和技能的。本书能让你学习到这些额外的知识和技能，并且打下坚实基础，让你在未来的学习和整个职业生涯中可以不断提高。在你学习本书的过程中，你将会完成从“小作坊”编程慢慢转型到“大型”编程的过渡。

不同的软件项目在很多方面都有各自的特点。就规模而言，它们可以从非常小（例如将温度从摄氏度转换到华氏度）到非常大（例如计算机操作系统）。同样，软件项目在开发系统的关键任务方面也存在很大差异。一个日记网站并不需要设计得像网上银行那样严格遵守规范，也不用像控制生命维持医疗设备的程序那样精益求精。

没有任何一个单独的属性可以决定项目的“大小”或“难度”。但一般而言，有许多特征可以将现实世界里的编程和你迄今为止看到过的简单的课堂练习题区分开来。这些特征如下。

“大型”编程的基本问题其实就是管理相关事务的复杂性。遗憾的是，人们更擅长同时只跟踪少量的几件事情。因此，为了处理复杂的软件系统，我们需要一个可以在任何给定的时间节点上都能限制需要考虑的细节数量的方法。例如忽略一些细节的同时，更专注于与手头问题相关的细节。这一过程我们称之为抽象。高效的软件开发就是构建合适的抽象。因此，本书经常会用到抽象的概念。

处理复杂性的另一个重要技术是会重用之前已有的解决方案。作为程序员，你将需要学习如何通过各种应用程序编程接口（Application Programming Interface，API），来调用你将要使用的工具或库。API是代码库提供的类和方法，以及它们的使用说明（也就是参数和返回类型是什么，以及它们分别代表什么含义）的集合。你可能已经学习过一些简单的API，如Python数学模块（math）中提供的函数以及各种内置数据结构［如列表（list）和字典（dictionary）］的方法。还有一个常见的API的示例就是图形用户界面（Graphical User Interface，GUI）工具包。

大多数编程语言都提供可用于完成许多常见任务的API。当然API也会因语言和操作系统的不同而产生差异。因此这本书不能够涵盖你将会在职业生涯里遇到和使用的所有API，与之相比只是一小部分。但是，通过学习一些API，抑或更重要的是，通过学习开发自己的API，你能够获得使你将来能轻松掌握新的API的实用技能。

另一个和重用API已有的代码同样重要的能力是：能够利用现有的良好设计原则的知识。多年来，计算机科学家们已经开发出了用于解决常见问题（例如搜索和排序）的各种算法，并构建出了在大多数程序中都可以用作基本模块的各类数据集合。在本书里，你将会学习这些算法和数据结构，以便你之后可以编写更大、更复杂、精心设计和因为使用了这些被广泛理解的模块而易于维护的程序。同时，学习这些现有的算法和数据结构还将帮助你了解如何为将来可能会面临的特殊问题创建属于自己的新算法和数据结构。

计算机科学家还发明了用来分析和分类各种算法和数据结构的效率的技巧。利用这些技巧，你就可以预测一个程序是否能够在合理的时间和有限的内存等条件下成功解决问题。当然，你还需要学习算法分析的技巧，从而能够分析你新发明的算法的效率。

不论出于什么原因，拥有多种编程语言的经验是非常重要的。因此，本书将会介绍两种不同编程语言的抽象和数据结构。了解不同编程语言之间的差异，可以让你了解到开发人员可以使用不同的工具来应对不同的任务。拥有大量的工具，能够让你更轻松地解决各种各样的问题。然而，更重要的一个优点是：你还能够看到抽象、重用和分析这些基本原则是如何应用于两种不同的编程语言之中的。只有了解了这些不同的实现，你才能真正理解什么是基本原则，而不仅仅是知道了特定编程语言的细节。无论你将来使用何种语言或环境，这些基本原则都将非常有用。

说到编程语言，在本书即将出版的时候，Python发布了新的版本（Python 3.0）。新版本中包含了大量的重新设计，并且不会向下兼容2.x版本的Python编写的程序。虽然本书中的代码是用Python 2.x风格编写的，但是我们将尽可能地尝试使用与Python 3.0兼容的规范和功能。同时，将代码转换为3.0版本也非常简单，要使代码能够在Python 3.0中运行，你需要记住以下不同。

本书的在线资源中，提供了所有代码的Python 2.x和Python 3.0版本。因此，不论你使用哪个版本的Python，都能够很方便地学习本书。

为了能解决大型软件项目，必须要将其拆分成更小的部分。其中一种可以将问题拆分成较小部分的方法是：将其分解为一组可以相互协作的功能。这一方法被称为功能抽象（functional abstraction），或者叫作过程抽象（procedural abstraction）。

让我们通过一个简单的例子来理解编写函数其实是一个抽象的实例。假设你要写一个需要计算某个值的平方根的程序，你知道应该怎么做吗？你是否知道求平方根的具体算法并不重要，因为Python数学模块（math）中提供了平方根函数。

import math
...
answer = math.sqrt(x)

你可以很有信心地使用sqrt函数来求平方根，因为你知道它会做什么，即使你可能并不知道它是如何完成计算的。在这里，你只关注了sqrt函数的某些方面（做什么），而忽略了另一些细节（如何完成）。这就是抽象。

分离一个组件的能够做什么和它会怎么去完成这一任务的关系，是一种特别强大的抽象形式。如果我们将一个函数想象成一个服务，那么使用这个函数的程序就可以被称为服务的客户端（client），并且这个函数被实际执行的代码就可以被称为服务的实现（implement）。在客户端工作的程序员只需要知道这个函数的功能即可，并不需要知道该函数工作的任何过程细节。因此对于客户端使用者来说，这个函数就像一个能执行所需操作的神奇的黑盒子。类似地，这个函数的实现者也不需要关心应该如何使用该函数，可以自由地专注于这个函数应该如何完成其任务的各种细节，而不用在意实际调用函数的位置和原因。

为了实现这种清晰的分离，客户端使用者和实现者必须对要完成的功能达成一致，也就是说，他们必须对客户端代码和具体实现之间的接口有共同的理解。这个接口就像是一种将函数的两个不同角度的视图分开的抽象屏障。图1.1所示为用图形化的方式呈现Python字符串分割方法（或字符串模块中的等效的分割函数）。图里显示了这个方法/函数需要一个字符串作为必需参数，以及另一个字符串作为可选参数，最后返回一个字符串。使用这个split方法/函数的客户端使用者并不需要关心它的工作方式（也就是框内的内容），只需要知道应该如何使用它。因此，我们需要的是仔细描述函数将做什么，而不必描述函数将会如何完成它的工作。这种描述被称为规范（specification）。

图1.1　split功能的黑箱接口示意图

很明显，描述函数的调用方式是规范的一个重要部分。也就是说，我们需要知道函数的名称、需要什么参数以及函数返回的内容。这些信息也可以被称为函数的签名（signature）。除了签名，规范还需要精确描述函数的功能。我们需要知道调用函数所提供的参数与结果是如何相关的。这种关联信息，很多时候是以非正式的格式完成。例如，假设你正在编写Python数学模块（math）中的平方根函数。让我们来看看下面这个函数的规范。

def sqrt(x):
    """Computes the square root of x"""

这并不是一个很好的函数规范。这种非正式格式描述的问题在于它们往往并不完整，且含糊不清。要知道，一个良好的规范应当可以使客户端使用者和实现者（即使他们是同一个人）仅仅依靠函数的规范，就能够完成各自的任务。这也是抽象过程如此有用的原因。如果这个函数计算了x的平方根，但没有返回结果怎么办？纯理论上来说，这也是符合规范的；但这样的话，这个方法对客户端使用者来说没有任何用处。同样，sqrt(16)可以返回-4吗？如果函数的实现只适用于浮点数，但客户端使用了整数作为参数调用该函数，应该怎么办？如果导致了程序崩溃，那是谁的错？如果客户端使用负数作为参数调用此函数会发生什么？它会返回一个负数，还是会直接崩溃？如果客户端使用字符串作为参数调用此函数会发生什么？可见，这种简单、非正式格式的描述，并没有告诉我们如何理解这个函数。

这可能听起来像是挑刺。因为通常每个人都“理解”平方根功能该做些什么。所以，如果我们有任何疑问，都可以通过查看该函数的源代码或通过实际使用来证明我们的假设（例如尝试计算sqrt(-1)并查看会发生什么）。但是，做这些事情就会打破客户端使用者和实现者之间的抽象隔离。而强制客户端程序员去理解函数的细节实现，也就意味着他或她必须去厘清这些代码的所有细节并进行处理，从而失去抽象的优势。另一方面，如果客户端程序员只是依赖于代码实际执行的结果（通过尝试它），他或她就有可能做出一些实现者无法预期的假设。例如，实现者发现了计算平方根的更好方法，因此修改了代码实现，那么客户端使用者对某些“边缘”行为的假设可能就不再正确。但如果保持抽象隔离，客户端代码和实现代码都可以随意修改，因为抽象隔离能够确保程序继续正常运行。这种理想的情况被称为实现独立性（implementation independence）。

希望下面这个令人刻骨铭心的反例，可以让你深刻地认识到在大型编程时，组件的精确规范是多么重要。美国航空航天局1999年的火星气候轨道飞行任务，由于假设与实现不匹配而造成了巨大的损失。原因很简单，只是因为一个模块需要使用英制单位来获得信息，但被假设为可以用公制单位。在大多数情况下，仔细定义的规范是绝对必要的。因为只要规范没有被明确地说明或者被严格地遵守，意想不到的灾难就会出现。

所以很显然，我们需要一种比非正式描述更好的东西来更好地表述规范。函数规范通常包含先验条件和后置条件。先验条件是关于调用函数时计算状态的假设。后置条件则是关于函数完成后的真实情况的陈述。下面就是sqrt函数包含先验条件和后置条件的示例规范：

def sqrt(x):
    """Computes the square root of x.

    pre: x is an int or a float and x >= 0
    post: returns the non-negative square root of x"""

先验条件用来陈述实现中所做的任意假设，尤其是关于函数参数的假设。为了完整地描述，它一般会使用这个参数的正式名称（在这个例子里是x）来描述参数。后置条件就需要描述函数实现代码中使用输入参数完成了什么。前后条件加在一起，对函数的描述就成为客户端与实现之间的一种契约。如果客户端使用者保证在调用函数时满足先验条件，那么实现者就保证在函数结束时也将满足后置条件。因此，这种使用先验条件和后置条件来描述系统中的模块的方式也被称为契约式设计（design by contract）。

先验条件和后置条件是程序断言（assertion）的一种特定的文档类型。断言，是一段关于计算状态的声明，并且在程序中的特定点处，这个计算状态为真。在函数执行之前，先验条件必须为真，并且后置条件也必须为真。稍后，我们将会看到程序在其他地方非常有价值的文档化断言。

如果你读得足够仔细，你可能会觉得上面sqrt函数的示例中的后置条件有点不对劲，因为它描述了这个函数应该做什么。严格来说，断言不应该说明函数的作用，而是应该说明程序中给定的点，现在什么是真的。因此，将后置条件表示为post：RETVAL ==√x可能更加正确，其中RETVAL用来表示函数的返回值。尽管严格来说，这样描述不太准确，但大多数程序员都倾向于像我们这个例子中一样，提供不太正式的后置条件。鉴于这种非正式风格更受欢迎，而且信息量也没有变少，我们在后面将继续使用这种“返回这个、那个和其他”的形式来表述后置条件。当然，如果你坚持应该严格使用完美的断言的话，可以做一些必要的改变。

现在，我们可以发现一个关于规范中先验条件和后置条件的重要观点：规范的重点在于它提供了对函数或其他组件的简洁和精确的描述。如果规范都模糊不清，或者比实际中实现的代码更长、更复杂的话，我们什么都得不到。数学符号往往是简洁而精确的，所以它们通常在规范中非常有用。实际上，一些软件工程方法采用完全正式的数学符号来描述所有系统组件，即形式化方法（formal method），这样可以允许用数学的方式陈述和证明程序的属性，提高了开发过程的精确性。在最好的情况下，这样也可以证明程序的正确性，也就是程序的代码忠实地实现了它的规范。然而，使用这种方法需要相当强大的数学功底，既然它还没有在整个行业中通用，那么我们目前将继续使用这种不太正式的规范，只在需要、合适且有用的时候使用众所周知的数学和编程符号。

另一个重要的观点就是：在代码中放置规范。在Python里，开发人员有两种方法可以将注释放入代码中：常规注释（用前导的#符号表示）和文档字符串（模块顶部、紧跟在函数名或类名之后的字符串表达式）。文档字符串将和它们附着的各种对象一起被打包，从而方便之后在运行时随时查看。正是由于文档字符串也被同时用于实现Python内部帮助文档，以及被PyDoc标准文档模块用来自动创建API文档，因此它可以成为一个特别好的媒介来定义规范。一般来说，对客户端程序员有用的信息，应当包含在文档字符串中；而仅供函数实现者使用的信息，应该使用内部注释。

契约式设计的基本思想是：如果在调用函数时满足函数的先验条件，则在函数结尾的后置条件也必须满足。如果不能够满足先验条件，则万事皆休。这就产生了一个有趣的问题：当不能满足先验条件时，这个方法应该做些什么？从规范的角度来看，在这种情况下这个方法做什么都无所谓，可以说是“松了一口气”。但如果你是实现者，你可能会想忽略掉不满足的先验条件。这样做的话，有可能会意味着执行这个函数会导致程序立即崩溃；也有可能代码虽然能够继续运行，但会产生一些无意义的结果。不论是哪一种结果，其实都不太好。

一个更好的应对方法是：采用防御性编程实践。因为有未满足的先验条件，说明程序里存在错误，所以你应该能够检测到这种错误并处理它，而不是无动于衷地忽略这种情况。但是这个应对方法应该怎么实现呢？例如，我们可以让它输出错误信息。因此在sqrt函数里就可能会有下面这样的代码：

def sqrt(x):
    ...
    if x < 0:
       print 'Error: can't take the square root of a negative'
    else:
       ...

输出错误消息的弊端是调用程序无法知道出现了什么问题。例如，这个错误消息可能只会出现在程序生成的报告里，甚至可能会被忽视掉。在实际项目中，很可能会在图形程序里调用通用库，如sqrt函数，在这样的情况下，这个错误消息就根本不会出现在任何地方。

在大多数的情况下，方法被设计成向外输出消息的形式并不太合适（除非这个函数的规范里定义了需要输出某些东西）。更理想的状况是：函数能以某种方式表示发生了错误，并且能够让客户端程序决定如何处理这个问题。对于某些程序，遇到错误的正确响应可能会终止程序并输出错误消息；而在其他情况下，程序也许能够从错误中恢复并继续运行。这样的选择结果应该只能由客户端做出。

一个方法可以通过多种方式发出错误信号，例如返回一个超出范围的结果。下面就是这样的一个例子：

def sqrt(x):
    ...
    if x < 0:
       return -1
    ...

既然sqrt函数的规范明确表示返回值不能为负，那么值-1就可以用来指示错误。客户端代码可以凭借它返回的结果来确定是否正常。另一种方法是，使用一个全局（global，程序的所有部分都能访问）变量来记录错误。客户端代码在每次操作后，都会去检查这个全局变量的值，来确认是否存在错误。

当然，用这种特殊的检测方法来“检查错误”有一个问题：客户端程序可能由于决策结构而不断地去检查错误以致变得混乱。例如客户端的代码逻辑可能会变成下面这样：

x = someOperation()
if x is not OK:
    fix x
y = anotherOperation(x)
if y is not OK:
    abort
z = yetAnotherOperation(y)
if z is not OK:
    z = SOME_DEFAULT_VALUE

可以看出，每次操作之后的错误检查，已经多到模糊了原始算法的意图的地步。

大多数现代编程语言都包含异常处理（exception handling）机制，它为程序运行过程中出现的错误提供了一种优雅的处理方法。异常处理背后的基本思想是程序错误不会直接导致“崩溃”，而是将程序的控制权转移到一个被称为异常处理程序（exception handler）的特殊部分。这个异常处理程序特别有用的是：让客户端程序不必显式地去检查是否发生了错误。实际上，客户端只需要说：“如果出现任何错误，这里是我想要执行的代码。”然后，在运行时系统会确保在发生错误时调用适当的异常处理程序。

在Python里，运行时的错误会生成异常对象（exception object）。程序使用try语句来捕获和处理这些错误。例如，取负数的平方根会导致Python生成ValueError（值错误异常）——这是一个Python的通用Exception（异常）类的子类。如果客户端程序没有处理此异常，程序将会终止。下面就是交互时发生的情况：

>>>sqrt(-1)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
ValueError: math domain error
>>>

当然，程序里也可以“捕获”try语句中引起的异常：

>>> try:
...    sqrt(-1)
... except ValueError:
...    print "Ooops, sorry."
...
Ooops, sorry.
>>>

当执行到try下方缩进的这条语句的时候，如果发生错误，Python会查看错误是否与任一except子句中列出的类型匹配。如果有，就执行第一个匹配的except语句块。但是，如果没有匹配到任何一个except子句，则程序将停止并显示错误消息。

要利用异常处理来验证先验条件，我们只需要在判断决策中验证先验条件，并且生成适当的异常对象。这称为引发异常（raising an exception），由Python里的raise语句完成。raise语句非常简单：raise <expr>。其中<expr>是生成包含有关错误信息的异常对象的表达式。当执行raise语句时，它会让Python解释器中断当前操作并将控制权转移到异常处理程序。如果找不到合适的处理程序，则程序终止。

Python库中的sqrt函数会通过这样的检查来确保其参数为非负数，并且参数具有正确的类型（int或float）。因此，sqrt函数的代码可以包含下面这些检查语句：

def sqrt(x):
    if x < 0:
        raise ValueError('math domain error')
    if type(x) not in (type(1), type(1L), type(1.0)):
        raise TypeError('number expected')

    # compute square root here

请注意，用这些条件检查是不需要else语句的。因为当raise语句执行时，它有效地终止了该函数，所以只有满足先验条件时才会执行“计算平方根”的部分。

通常情况下，检测到先验条件违规时引发何种类型的异常并不重要。重要的是，错误应该被尽可能早地诊断出来。Python提供了一个将断言直接嵌入代码的语句——assert（断言）。它输入一个布尔表达式（Boolean expression），当表达式计算结果不为True时，就会引发AssertionError异常。使用assert语句使得强制执行先验条件变得特别容易。

def sqrt(x):
    assert x >= 0 and type(x) in (type(1), type(1l), type(1.0))
    ...

正如你所见，assert语句是一种将断言直接插入代码的非常简便的方法。它非常有效地将先验条件（和其他断言）的文档转换为额外的测试，有助于确保程序依照规范正常运行。

这种防御性编程有个潜在的缺点：它增加了程序执行的额外开销。因为每次调用函数的时候，都会额外消耗几个CPU周期来检查先验条件。然而，鉴于现代处理器的速度不断提高以及错误程序的潜在危险不断增加，这通常是值得付出的代价。另外，assert语句还有一个好处：可以在需要的时候关闭断言检查。在命令行执行Python的时候，加上-O开关就可以让解释器跳过所有断言的检查。也就是说，我们可以在程序测试时使用断言，然后在认为系统能够正常工作并投入到生产环境的时候将其关闭。

当然，在测试过程中检查断言，而在生产系统中将其关闭，就好像在有安全网的时候，在距离地面大约3米的地方练习一个特技，然后在刮风的日子里、没有安全网的情况下，在离地面大约30米的地方表演这个特技。在测试期间捕获错误非常重要，但在系统使用时继续捕获它们更为重要。因此，我们的建议是随时随地地使用断言并随时保持打开断言检查。

你可能已经学会了一种非常流行的程序设计方法——自上而下的设计（top-down design）。自上而下的设计本质上是通过功能抽象来将应用程序的大问题分解为更小、更易于管理的组件。例如，假设你正在开发一个帮助你老师进行评分的程序。你的老师希望这个程序能够输入一组考试成绩，并且输出一份总结学生表现的报告。具体而言，程序输出的报告里应该包含以下有关的统计信息。

即所有的得分（xi表示第i个得分）之和除以统计的分数个数（n）。

在这个公式中，是平均值，xi表示第i个数据值，n是数据值的数量。这个公式看起来很复杂，但计算起来并不难。表达式是单个元素与平均值的“偏差”的平方。分数的分子也就是所有数据值的偏差（平方之后）的和。

在刚开始编写这个程序的时候，你可以开发一个包含以下功能的简单算法：

Get scores from the user
Calculate the minimum score
Calculate the maximum score
Calculate the average (mean) score
Calculate the standard deviation

假设你正在与朋友合作开发此程序，你可以将这个算法划分为多个部分，并且每个部分都能够与程序里的其他部分协作。然而，在开始真正的工作之前，你需要一个更完整的设计来确保每个人开发的部件都能够组合在一起，并且解决整个问题。通过自上而下的设计，你可以把算法中的每一行当作一个单独的函数来编写。这个设计也将会包含每个方法的规范。

一个显而易见的解决方案是：把考试成绩存储在列表中，然后把这个列表作为参数，传递到各个方法里去。使用这种解决方案的话，可以参考下面的设计示例：

# stats.py
def get_scores():
    """Get scores interactively from the user

    post: returns a list of numbers obtained from user"""

def min_value(nums):
    """ find the minimum

    pre: nums is a list of numbers and len(nums) > 0
    post: returns smallest number in nums"""

def max_value(nums):
    """ find the maximum

    pre: nums is a list of numbers and len(nums) > 0
    post: returns largest number in nums"""

def average(nums):
    """ calculate the mean

    pre: nums is a list of numbers and len(nums) > 0
    post: returns the mean (a float) of the values in nums"""

def std_deviation(nums):
    """calculate the standard deviation

    pre: nums is a list of numbers and len(nums) > 1
    post: returns the standard deviation (a float) of the values
          in nums"""

有了这些方法的规范，你和你的朋友就应该能够轻松地分配这些方法并且很快地完成这个程序。让我们实现其中一个方法，看看它应该是什么样的。如std_deviation方法的实现示例：

def std_deviation(nums):

    xbar = average(nums)
    sum = 0.0
    for num in nums:
        sum += (xbar - num)**2
    return math.sqrt(sum / (len(nums) - 1))

可以看到，这段代码的运行依赖于average函数。由于我们已经定义了这个方法，因此可以放心地在这里直接使用它，从而避免了重复工作。这里还使用了简化了的+=（加法赋值）运算符；这是求和的简写方式。也就是说x += y语句和x = x + y语句会产生相同的结果。

程序的其余部分将留给你来完成。如你所见，在这个程序里自上而下的设计和方法的规范齐头并进。所以，在设计确定了必要的功能时，规范保证了正式且确定的设计。因此，程序的各个部分可以被单独处理。你肯定能轻而易举地完成这个程序。

为了使规范有效，规范必须同时说明客户端和实现者的期望。任何在客户端可见的影响都应在后置条件中被描述出来。例如，假设std_deviation函数是下面这样实现的：

def std_deviation(nums):
    # This is bad code. Don't use it.
    xbar = average(nums)
    n = len(nums)
    sum = 0.0
    while nums != []:
        num = nums.pop()
        sum += (xbar - num)**2
    return math.sqrt(sum / (n - 1))

这段代码中使用了Python列表的pop方法。对nums.pop()的调用将会返回列表中的最后一个数字，并从列表中删除该项。之后循环继续，直到处理完列表中的所有元素。这个版本的std_deviation能够返回正确的值，因此它似乎符合先验条件和后置条件指定的契约。但是，作为参数传递的列表对象nums是可变的，而且对列表的任何修改都将对客户端可见。所以，这段代码的使用者会非常惊讶，因为他们会发现调用std_deviation (examScores)会导致examScores中的所有值被删除！

这类函数调用和程序其他部分之间的相互影响被称为副作用（side effects）。在这个例子里，删除examScores中的元素是调用std_deviation函数的副作用。一般来说，应当避免方法中的副作用，但完全不准修改又禁止得太严格了。有些方法就是需要产生副作用，列表类中的pop方法就是一个很好的例子。它被用来获取一个值，然后就像副作用一样，从列表中删除这个元素。因此，有一个至关重要的事情需要注意，方法中的任何副作用都应在其后置条件中指出。由于std_deviation的后置条件并没有包含会修改nums的任何内容，因此这个代码实现隐性地违反了契约。方法的可见效果应该只是在后置条件中描述的那些。

顺便说一下，输出消息或将信息放在文件中也是副作用的例子。正如上面提到的，方法通常不应该输出任何东西，除非这是它声明的功能中的一部分，这也是一个（可能）未注明副作用的特殊情况。

当我们开始处理包含数据集合的程序时，除了需要知道它的先验条件和后置条件，通常还需要了解更多。处理一个包含10个甚至100个考试分数的列表倒是没有任何问题的，但是线上商业的客户列表可能包含成千上万个元素；处理生物学问题的程序员可能得处理含有数百万甚至数十亿个核苷酸的DNA序列；搜索和索引网页的应用程序也需要处理类似数量级的数据集。当数据集越来越大时，算法的效率就会和它的正确性同样重要。如果一个算法能够提供正确答案但需要10年计算时间，就明显不太可能有实际用处。

通过算法分析，我们可以根据完成任务所需的时间和内存使用状况来评估算法。在本节中，我们将首先通过搜索数据集来了解算法分析技术。

搜索是指在集合中查找特定值的这一过程。例如一个维护俱乐部成员列表的程序可能需要查找特定成员的相关信息。这就涉及某种形式的搜索。搜索对我们来说是一个很好的问题，因为有许多相对效率不同的搜索算法可以用于对比。

为了透过现象看本质，我们可以用在列表里查找特定数字这一问题来简化我们的搜索问题。而且，在这里使用的原则将同样适用于更复杂的搜索问题，例如搜索客户列表以查找居住在爱荷华州的人。这个简单搜索问题的规范如下所示：

def search(items, target):
    """Locate target in items

    pre: items is a list of numbers
    post: returns non-negative x where items[x] == target, if target in
          items; returns -1, otherwise"""

下面是一些可以说明其行为的交互式示例：

>>> search([3, 1, 4, 2, 5], 4)
2
>>> search([3, 1, 4, 2, 5], 7)
-1

在第一个例子里，函数会返回列表中元素4的索引。而在第二个示例中，返回值-1表示7不在列表中。

利用Python内置的列表函数，我们可以轻松实现search功能：

# search1.py
def search(items, target):
    try:
        return items.index(target)
    except ValueError:
        return -1

index函数用于从列表中找出某个值第一个匹配项的索引位置。如果target不在列表中，则index函数会抛出ValueError异常。在这里，程序捕获这个异常并返回-1。很明显，我们实现的这个函数符合定义的规范；更有趣的一个问题是：这种函数的效率怎么样？

一种用来确定算法效率的方法是进行实证检验。我们可以简单地实现这个算法，并且用不同的数据集来验证它，以查看需要多长时间。在Python里提供了计时相关的代码，可以简单地使用时间模块（time）中的time时间函数来实现，它会返回从1970年1月1日开始到现在所经过的秒数。我们可以在相关代码执行之前和之后调用这个方法，再输出前后之间的差异。当将搜索功能放在名为search1.py的模块中之后，我们可以用下面的代码直接验证它：

# time_search.py
import time
from search1 import search

items = range(1000000) # create a big list

start = time.time()
search(items, 999999) # look for the last item
stop = time.time()
print stop - start

start = time.time()
search(items, 499999) # look for the middle item
stop = time.time()
print stop - start

start = time.time()
search(items, 10) # look for an item near the front
stop = time.time()
print stop - start

你可以在你自己的计算机上运行这段代码，并且记下搜索3个数字的时间。根据这3个时间，你能知道index函数是如何工作的吗？顺便说一下，Python库里还包含了一个名叫timeit的模块，它提供了更为精确和复杂的计时方式。如果你需要进行大量的实证检验，那么值得深入研究一下这个模块。

让我们自己也像计算机一样来思考，尝试开发我们自己的搜索算法。假设有满满一页没有特定顺序的数字，需要判断数字13是否在这个列表中，你会怎么来解决这个问题？你可以像大多数人一样，简单地一个一个元素地扫描整个列表，并且把每个值与13进行比较。然后当你找到13的时候，退出扫描并告诉我你找到了它。而如果直到列表的最后都没有找到13的话，你会告诉我它不在这一页里。

这种策略被称为线性搜索（linear search），即逐个元素地搜索整个列表，直到找到目标值为止。这个算法可以直接写成下面这样简单的代码：

# search2.py
def search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

可以看到在代码里有一个简单的for循环遍历整个列表的有效索引（range (len(items))）。程序在每个位置都会判断这个元素是不是我们的目标（target）。如果找到了目标，则立刻终止循环，并返回这个位置的索引。而如果这个循环直到结束都没有找到目标元素，则该函数返回-1。

这样写函数有一个问题：range表达式会创建一个与要搜索的列表大小相同的索引列表。而由于int通常需要4字节（32位）的存储空间，所以当有一个百万级的数字列表的时候，代码中的索引列表需要4MB的内存。除了内存使用情况，创建这样的第二个大列表也会浪费相当多的时间。Python有另一个名为xrange的表达式可以替代range使用。xrange只能被用在迭代里，而且它在运行的时候也不会创建一个新列表。要注意，在新的Python代码中不再鼓励使用xrange。[1]

如果你的Python版本是2.3或更高版本，你也可以使用enumerate函数。这种优雅的替代方案允许你遍历列表，并且在每次迭代的时候，你都能获得下一个元素和它的索引。下面是使用enumerate进行搜索的方式：

# search3.py
def search(items, target):
    for i,item in enumerate(items):
        if item == target:
            return i
    return -1

还有一种方法是使用while循环来避免使用range/xrange/enumerate时产生的问题：

# search4.py
def search(items, target):
    i = 0
    while i < len(items):
        if items[i] == target:
            return i
        i += 1
    return -1

注意一下，所有这些搜索功能的实现都使用了相同的算法——线性搜索。那么这个算法效率怎么样？要想知道怎么评判，你可以先尝试使用它。就像你已经记录过的3个使用列表index方法的时间一样。你唯一需要更改的是导入前面实现的这些search功能，它们的参数和返回值是相同的。正是因为我们定义了一个规范，所以拥有不同的函数实现，客户端代码也不需要改变。这就是工作中常用到的实现的独立性。很酷，对吧？

线性搜索算法并不难实现，并且它对中等大小的列表处理得很好。对于无序列表来说，线性搜索算法和其他任何算法都一样好。Python里的in和index操作都实现了线性搜索算法。

如果我们遇到的是一个非常大的数据集合，这种情况下可能会希望数据按照某种方式进行组织，这样我们就不用查看每个元素来判断目标值在这个列表中的位置，或者是不是存在于这个列表。假设这个列表按顺序（从低到高）存储。一旦程序遇到了一个大于目标值的值，就可以退出线性搜索了，而不需要继续查看列表的其余部分。平均来说，这能够节约大概一半的工作量。实际上，如果列表已经有序，我们甚至可以做得更好。

当列表已经有序的时候，你可能已经知道了一个更好的搜索策略。还记得玩过的猜数游戏吗？我选择一个1～100的数字，你试着猜它是什么。每次你猜的时候，我都会告诉你你的猜测是正确、太高还是太低。那么你的策略是什么呢？

如果你和一个年纪非常小的孩子一起玩这个游戏，他很可能会采用一种随机猜测数字的策略。而稍微大一些的孩子可能会采用与线性搜索相对应的方法——猜测1、2、3、4等，直到找到那个值。

当然，几乎所有成年人都会先猜50。如果被告知目标值要高一些，那么它可能的范围就是50～100。下一步就可以猜75。每次我们都猜测剩余数字的中间位置来尝试缩小可能的范围。这种策略被称为二分搜索（binary search）。所谓的“二分”，也就是在每一步都把剩下的数字分成两部分。

我们可以使用二分搜索策略来查看一个有序列表。其本质上是使用两个变量来跟踪目标值可能在列表中的范围的两个端点。最初情况下，目标值可以在列表中的任何位置，因此我们将变量low和high分别设置为列表的第一个和最后一个位置。

这个算法的核心是一个查看剩余范围中间元素与x进行比较的循环。如果x小于中间项，那么我们移动high变量，以便搜索缩小到较小的那半个部分；而如果x要大一些，那么我们移动low变量，将搜索范围缩小到较大的那半个部分。当找到了x或不再有任何要检查的地方（即low > high）时，循环终止。下面的代码在相同的搜索API里实现二分搜索：

# bsearch.py
def search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:          # There is still a range to search
        mid = (low + high) // 2 # position of middle item
        item = items[mid]
        if target == item :     # Found it! Return the index
            return mid
        elif target < item:     # x is in lower half of range
            high = mid - 1      #      move top marker down
        else:                   # x is in upper half
            low = mid + 1       #      move bottom marker up
    return -1                   # no range left to search
                                # x is not there

该算法比简单的线性搜索要复杂一些。你可能会希望通过几个示例搜索，来向自己证明它是对的。

到目前为止，我们为简单的搜索问题开发了两种截然不同的算法。哪一个更好，取决于我们究竟认为什么是更好。例如，我们会觉得线性搜索算法更容易理解和实现；同时，我们可以预期二分搜索更为有效，因为它不用去查看列表里的每个值。从直觉上来说，我们可能会认为线性搜索是小型列表的更好选择，而二分搜索则是大型列表的更好选择。我们应该怎样来证实这种直觉呢？

与之前一样，一种方法是进行实证检验。我们可以简单地编写两种算法，通过在不同大小的列表上进行尝试，来查看搜索需要多长时间。这些算法都不长，因此运行一些验证并不困难。当我们用一台计算机（有点过时的笔记本电脑）进行此验证时，对于长度为10或更短的列表，线性搜索更快；对于长度处于10～1 000的范围内的列表来说，两者没有太大的差异；而随着列表长度的增加，二分搜索显然是赢家。对于一个拥有100万个元素的列表，线性搜索平均要花2.5秒来找到一个随机值，而二分搜索平均仅用0.000 3秒。

实证分析证实了我们的直觉，但这是在特定情况下一台特定机器的结果（固定的内存总量、处理器速度、当前负载等）。我们应该怎样保证这个特定的结果具有普适性呢？

还有一种方法是：抽象地分析各种算法来查看它们的效率。在其他因素相同的情况下，我们期望具有最少“步骤”的算法更有效。但是怎么计算步数呢？对于任意一个算法来说，其主循环的执行次数都将取决于特定输入。我们已经猜到了二分搜索的优势会随着列表长度的增加而增加。

为了解决这类问题，计算机科学家会分析算法要解决的特定问题的大小或难度所需采取的步骤。搜索的难度取决于集合的大小。显然，在一个有100万个元素的集合中找到一个数字，比在一个只有10个元素的集合中找到一个数字需要更多的步骤。相关问题是在大小为n的列表里查找值需要多少步骤。我们特别感兴趣的是当n变得非常大的时候会发生什么。

我们先来考虑线性搜索。如果列表有10个元素，算法最多会查看每个元素，因此循环最多迭代10次。假设列表有两倍大，那么算法需要查看两倍的元素。如果列表是3倍大，则需要查看3倍，以此类推。通常，所需的时间量与列表的大小n线性相关。因此，计算机科学家称之为线性时间（linear time）算法。现在，你知道了为什么这个算法被称为线性搜索。

那么二分搜索呢？让我们从一个具体的例子来开始分析。假设有一个列表包含16个元素。每次循环后，剩余的范围减半。一次循环执行之后，还有8个元素需要考虑。下一次之后将还剩4个，然后剩下两个，最后只有1个。循环迭代了多少次取决于在数据耗尽之前我们可以将范围减半的次数。表1.1应该能帮助你解决这个问题。

表1.1　列表大小和对分次数

列表大小

对分次数

1

0

2

1

4

2

8

3

16

4

你能发现表格里的规律吗？每一次额外的循环迭代，都允许我们搜索两倍大的列表。如果二分搜索循环i次，它可以在大小为2i的列表中找到一个值。每次循环时，它都会查看列表中的一个值（在中间位置）。要知道在大小为n的列表中一共检查了多少个元素，我们需要解决这个关系：对于i，有n = 2i。在这个公式中，i是一个基数为2的指数。利用对数，可以得到关系式i = log2n。如果你不太喜欢对数，那就记住这个值是大小为n的集合可以减半的次数就可以了。

这些数学分析告诉我们：二分搜索是对数时间算法的一个示例。解决给定问题所花费的时间随着问题大小的对数增长而增长。在二分搜索的情况下，每次额外的迭代都会使我们可以解决的问题的大小增加一倍。

你可能不太理解二分搜索的有效性。让我们试着把它放在这样一个例子里。假设你有一本纽约市电话簿，其中按字母顺序列出了1 200万个名字。你向走在街上的任何一个纽约人提出这样一个建议（假设已经知道他们的号码）：“我会尝试猜测你的名字。我每猜一个名字，请你告诉我你的名字是在我猜的名字按字母顺序排列的之前还是之后。”你需要多少次猜测？

上面的分析显示，这个问题的答案是log212 000 000。如果你没有计算器在手边，这里有一个快速估算的结果：210 = 1 024或者说大概等于1 000，以及1 000 × 1 000 = 1 000 000。也就是说210 × 210 = 220 ≈ 1 000 000。220大概就是100万。因此，搜索100万个名字只需要20次猜测。然后呢，我们只需要21次就能猜200万个名字，22次猜400万个，23次猜800万个，24次猜测就能搜索1 600万个名字。我们只需要用24次猜测就能成功猜出纽约市任何一个陌生人的名字！相比之下，线性搜索需要（平均）600万次猜测。因此，二分搜索是一个非常棒的算法！

我们之前说过，Python使用线性搜索算法来实现其内置搜索方法。如果二分搜索更好的话，为什么Python不使用它呢？原因是二分搜索不太通用，为了能够正常工作，进行二分搜索的列表必须有序。如果要对无序列表使用二分搜索，首先要做的就是将这个列表按照顺序排列（sort）。这是计算机科学中另一个已经经过充分研究的问题，我们将在稍后讨论它。

在比较线性搜索和二分搜索的时候，我们根据解决特定大小问题所需的抽象步骤的数量来评估两种算法。我们发现线性搜索需要与列表大小成正比的步骤，而二分搜索则需要与列表大小的（基数为2）对数成比例的步骤。利用这种表征的好处是，它能够告诉我们这些算法的一些信息，以及与这些信息无关的任何特定实现。我们预期二分搜索在大问题集上能做得更好，是因为它本身就是一种更高效的算法。

在进行这种分析时，我们通常不用关心解决特定问题的算法所需指令的确切数量，因为这是非常难以确定的。毕竟，不同的计算机机器语言、实现算法的不同语言，以及就像我们在搜索算法中看到的那样，特定输入数据的细节的不同，都会导致指令数量的不同。因此，我们需要抽象出不会影响算法确切运行时间的问题，也就可以忽略掉所有会影响算法在各种大小输入上的相对性能的细节。要知道，我们的目标是确定算法在大数据量输入时的执行性能。现在的计算机速度很快，对于小规模的问题，效率一般不太可能成为瓶颈。

总而言之，在进行算法分析时，我们通常可以进行下面这些简化。

很明显，这里的任何一个简化都会让比较的两个算法的结果和实际运行时间不同，甚至会对同一个算法的不同实现实际运行时间产生显著的影响。但这个结果仍然可以显示我们所期望的对于输入大小的函数值。因此，这个结果会告诉我们更大的问题的性能相对来说是什么样的。计算机科学家们使用大O符号或者说渐近符号（asymptotic notation）来表示基于这些简化的算法的时间复杂度。

在深入大O符号的细节之前，让我们看几个简单的数学函数来获得一些直观感觉。假设函数f (n) = 3n2 + 100n + 50。你要在n很大的时候估计这个函数的值。这时，你应该只考虑多项式的第一项。虽然在n比较小的时候，100n项能够占据主导地位，但n变大之后，第二项和第三项对最终结果的贡献是微不足道的。例如，在n = 1 000 000时，只使用第一项得出的结果和函数的真实结果的差别在0.01%之内。

你只需要看看第一项和第二项的图形“形状”（如图1.2所示），就能够明白为什么第一项在n增加时能占据主导地位了。从图里可以看出，就算在0～1的范围内x＞x2，但只要x＞1，x2就一定会占据主导。所以，当我们将x乘以某个常数（如100）时，虽然会改变那条直线的斜率，但因为函数x2向上弯曲，它仍然会超过100x（在x = 100的时候）。因此，无论我们将x乘以哪个常数，这两个图形的形状都表明，只要值足够大，x2的曲线都将占主导地位。

图1.2　0～1时x2＜x，但对于更大的值来说x2更大

大O符号可以用来表示这种只关注主导地位的函数。例如，当算法被表示为O(n2)时就表明存在某些常数c和n0，当n＞n0的时候，有n＜cn2。只要我们能找到这两个常数，就能够证明算法的时间复杂度是O(n2)。在多数情况下，它非常明显（像上面的例子里一样）。那么，函数3n2+100n+50的常数是什么呢？在这里我们并不需要一个严格的边界。当n＞1 000 000的时候，3n2 + 100n + 50＜1 000 000n2，我们就可以将两个常数都定义为1 000 000。如果算法是2n3，我们能找到两个常数来证明它是O(n3)吗？在实践中，我们通常不太关心去找到这些常数。在大多数情况下，增长率就非常容易让我们相信了。因为对于所有多项式，它最重要的部分都是最大的项，所以任何x次多项式都是O(nx)。

现在你已经从数学细节上了解了大O符号，让我们再看一些简短的例子，并确定它们的运行时间：

n = input('enter n: ')
for i in range(n):
    print i

这个代码片段的时间复杂度是O(n)，因为n的大小会决定有多少次操作——print语句将会被执行n次，而input语句就执行一次。让我们仔细研究一下for语句，range语句将会生成一个包含n个元素的列表，这个生成过程就至少需要n步。每次迭代完for语句之后，变量i都会指向列表里的下一个元素，因此我们可以很容易地得出大约需要2n + 1个基本步骤来执行这个代码片段。这也就足以表明，算法的时间复杂度是O(n)。在这里，我们忽略了在Python里也需要时间来检测是否到达列表的末尾，因为在实际工作中，在得到代码片段的时间复杂度的时候，我们通常不需要深入了解所有的细节。

思考下面这个代码片段。你能确定它运行的时间复杂度吗？

n = input('enter n: ')
for i in range(100):
    print i

晃眼一看，因为有一个for循环，你可能会认为这个代码的时间复杂度也是O(n)。但是，在这种情况下，无论输入的值是什么，for循环都会且只会执行100次。本质上来说，这和100个print语句没有任何区别，也就可以被理解为是100个常量时间的操作。所以，无论输入任何数值，这段代码片段都能以相同的常量时间运行，在这里我们将所有常量操作都简单表达为O(1)。

下面是一个有两个循环的例子：

n = input('enter n: ')
for i in range(n):
    print i
for j in range(n):
    print j

在这个例子里，因为两个循环按顺序一个接一个地执行，所以总共时间复杂度可以表达为O(n + n)。你可以先把它看作O(2n)，而常数乘数不会影响大O符号，因此仍然是O(n)。通常来说，当需要将算法的顺序执行部分的时间复杂度加在一起时，整个算法的大O就是各部分的大O的最大值。这也就意味着，你只需要找到算法执行步骤最多的部分，然后分析它，就能得到整个算法的时间复杂度。

让我们再来看看另一个有两个循环的例子：

n = input('enter n: ')
for i in range(n):
    for j in range(n):
        print i, j

在这个片段中，循环是嵌套的。而且，第二个循环对第一个循环的每次迭代都要迭代n次。也就是说print语句总共要执行n2次，所以代码的时间复杂度为O(n2)。一般来说，对于嵌套循环，时间复杂度是每个循环迭代次数的乘积。

接着来关注下面这个例子：

n = input('enter n: ')
total = 0
for i in range(n):
    for j in range(10):
         print i, j
         total = total + 1

这个例子里也有两个嵌套循环，你可能认为它的时间复杂度也是O(n2)。但要注意，无论n的值是多少，内层循环总是迭代10次。我们仍然可以用“让每个循环迭代次数相乘”的这个规则，因此迭代次数是10n。所以这个代码片段的时间复杂度是O(n)，在渐近分析中会忽略掉常数系数。

让我们尝试一个稍微麻烦一点的嵌套循环案例：

n = input('enter n: ')
for i in range(n):
    for j in range(i, n):
        print i, j

这段代码里还是有两个嵌套循环，但内层循环在外层循环的每次迭代中，都循环不同的次数。在这种情况下，之前那个简单的乘法规则就不起作用了，但好在这种分析并不太难。那么，我们想要知道当输入为n的时候，print语句一共执行了多少次，应该怎么做呢？第一次迭代外层循环的时候，内层循环迭代了n次。第二次的时候，内层循环迭代了n − 1次，以此类推。直到最后，在外层循环的最后一次迭代中，内层循环只迭代1次。那么内层循环的迭代的总次数，只需要将它们全部都加起来就能得出，即：1 + 2 + … + n。

你应该曾经在数学课里见到过这个公式。当然，如果没有的话，下面是解决这个问题的一种方法。先把这个公式与自身相加，然后把它写成下面这样：

每一列的和都是n + 1，一共有n列。所以，所有列的和就是。而这个和是原始公式的两倍，因此除以2就能得出公式。展开公式，就会有二次多项式，所以我们可以得出结论，这段代码片段的时间复杂度为O(2n)。

最后，这里有一个使用while循环的小例子：

n = input('enter n: ')
while n > 1:
    n = n // 2  # // is integer division

这段代码片段与之前的所有其他代码片段都不一样——有一个不会迭代n次的循环。每次迭代的时候，n都会除以2。所以，我们应该去确定n等于1所需要的循环次数。这和我们之前提到的“猜数字游戏”里的二分搜索是同一个问题。每次输入的大小翻倍的时候，迭代次数加1。因此，输入为n时，算法的步数是等式2x = n，其中x表示步数。所以，答案是x = log2n。在许多算法里，输入都会被不断地被分成两半。在这种情况下，我们最终都可以得到O(log2n)这样的时间复杂度。

让我们回到搜索函数，你现在有了能够正式分析代码的所有工具。我们的线性搜索使用了一个会迭代n次的for循环，所以它的时间复杂度是O(n)。这也是它被称为线性搜索的原因：函数的运行时间是一个线性函数（多项式最高次幂为1次）。而且就像前面提到过的，排序列表的二分搜索算法的时间复杂度是O(log2n)。因此循环（最多）迭代log2n次就能够完成整个流程，而且每次循环体执行的操作数都是常量。

时间复杂度能够告诉我们，在面对大数据集的时候，我们的算法效率如何。对于仅仅会执行一两次的代码，效率通常不是一个重要的问题。然而，当你的程序需要两年的时间来解决一个问题的时候，效率就成了一个大问题。大O符号可以让我们推断并确定程序在更大的数据集上需要运行多长时间。如果我们想要知道这个程序在两倍大的输入集的情况下需要执行多长的时间，只需要在函数中插入2n来代替n。比如说，一个算法的分析结果是O(n2)，然后我们让输入集翻倍，我们可以预期它需要4倍的时间来执行，因为(2n)2就是4n2。换句话说，如果我们的算法在大小为100万的输入集上需要执行1min，那么我们完全可以预期它会在200万的输入集上花4min。

从理论上来说，大O符号只给出了算法效率的上限。回顾一下大O符号的定义。如果算法的时间复杂度是O(n)，那么它的复杂度也同样可以表示为O(n2)、O(n3)等。通常来说，绝大多数算法的时间复杂度都是O(2n)，但是当我们想要比较两个特定算法的时候，这样说没有任何意义。而且，当我们对算法进行大O分析时，我们总会试图去找到一个更“严格”的上界。比如我们都知道的，当列表的大小翻倍时，线性搜索要发现一个数字不在列表之中，需要花费两倍的时间。然而，这里提到的线性搜索的渐近增长率是n，但是如果可以知道确切的增长率，显然将会为我们提供更多的信息。

这里，我们引入Θ（Theta符号）来描述更严格的上（下）限。要证明算法的时间复杂度是，必须证明有常数、和，使得算法对于所有，执行步数都会大于且小于。通过将算法的时间复杂度限制在f (n)的两个倍数之间，我们可以明确执行步数将和f (n)以相同速率增长，因此算法的执行步数（对于较大的n）基本上等于f (n)的某个倍数的值。实际上，我们一般不会去找这个常量的确切的值，除非分析的算法特别复杂。有关函数边界的示例，如图1.3所示。

图1.3　0.5x2介于0.25x2和0.75x2之间

在算法分析中，常见的一些函数的增长率如表1.2所示。从这个表格里我们可以看出，算法的复杂度函数对于它能不能在合理的时间内解决问题非常重要。指数级（如2n）增长的算法，并不能用于解决哪怕只是普通大小的问题。如果计算机每秒可以执行10亿次操作，那么当输入的大小是100的时候，完成一个指数算法需要多长时间？利用表1.2所示的信息，我们可以知道2100大约是1030（也就是1后面跟上30个零）。这是一个非常大的数字。将它除以每秒10亿次操作可以得出结论，在输入大小为100的时候，运行这个算法需要1021秒，也就是超过1013年。而宇宙通常被认为是在100亿～200亿年前诞生的，所以这是一个比宇宙生命还要大上千倍的时间！

表1.2　常见函数的近似增长率

n

log2(n)

n log2(n)

n2

n3

2n

100

6.6

10

660

10 000

1 000 000

1030

1 000

10

32

10 000

1 000 000

109

10301

10 000

13

100

130 000

108

1012

103010

100 000

17

320

1 700 000

1010

1015

1030103

1 000 000

20

1 000

2 × 107

1012

1018

10301029

当我们已经知道解决特定大小的问题需要多长时间的时候，就可以使用Θ 符号来估计解决与之相比更大尺寸的问题所需要的时间。比如说，有一个的排序算法需要25秒才能对计算机上的100万个元素进行排序，由此就可以估计出在同样的计算机上使用相同的代码对200万个元素排序需要多长时间。从上面的信息中可以得出方程s。有一点需要注意，Θ 符号（和大O符号一样）不会表示出最大项前面的常数乘数。但是，在列出等式的时候，需要包含这个常数乘数，这样可以求解c：。现在，我们就可以计算，也就是100s。

可能你已经发现，在这个情况下我们甚至都不需要去求解c。因为我们已经知道算法的时间复杂度是，而现在我们想知道当输入大小翻倍时会发生什么。我们可以把2n带入n并展开，得到：。也就是，在使用算法时，需要用4倍的时间来解决两倍的问题。这和我们之前的答案一样（）。

很明显，我们将尽可能地使用Θ 符号来表明算法的性能。对于一些复杂的算法，很难去证明一个严格的边界，在这种情况下我们可能只会去证明一个非严格的上界（大O符号）。通常来说，我们也只会分析算法的最坏情况下的时间复杂度。可能你会觉得平均情况下的时间复杂度更有用，但这个值一般并不太好得到。对于线性搜索，我们可以知道最好的情况是Θ (1)，最坏的情况是Θ (n)，因此很容易得出平均情况也是Θ (n)。因为，当我们在一个不重复的列表中搜索每一个元素的时候，这个元素可能会在第一、第二、第三……一直到最后一个位置上被找到。所以，寻找的元素的总数是n(n + 1)/2，对于平均情况来说，只需要除以搜索的次数n就好了，也就是Θ (n)。而对于二分搜索，确定平均情况的时间复杂度将会更加困难。

这一章里，我们介绍了编写大型软件系统至关重要的基本概念。

1．判断题

（1）为了能够正确地使用库中定义的函数/类/方法，必须要了解它的API（即参数和返回值是什么）。（　　）

（2）假设定义的先验条件、后置条件还有实现的代码都是对的，如果在执行代码之前已经满足了先验条件，则保证在执行代码后后置条件也一定为真。（　　）

（3）当函数检测到其先验条件被违反时，应该输出错误消息。（　　）

（4）函数的签名提供了其行为的完整规范。（　　）

（5）精心设计的功能/方法通常具有未注明的副作用。（　　）

（6）使用相同的计算机、编程语言和输入数据，执行Θ (n)的算法肯定比执行Θ (n2)的算法快。（　　）

（7）使用代码行数多的函数可能比使用代码行数少的函数更快。（　　）

（8）当算法的预期输入大小很小时，Θ 符号是算法效率的有效度量。（　　）

（9）所有的O(n2)算法时间复杂度都是Θ (n2)。（　　）

（10）所有的Θ (n2)算法时间复杂度都是O(n2)。（　　）

2．选择题

（1）以下哪项不属于函数签名的一部分？（　　）

　a．函数的名称

　b．该函数如何工作

　c．参数

　d．返回值

（2）函数中的哪些操作会产生副作用？（　　）

　a．将不可变参数设置为新对象

　b．将可变参数设置为新对象

　c．修改可变参数

　d．返回一个值

（3）下面哪项表明满足了函数的先验条件？（　　）

　a．该函数不会崩溃

　b．该函数返回一个值

　c．该函数抛出了异常

　d．以上都不是

（4）一般来说，以下哪项对算法在大型数据集上执行的时间影响最大？（　　）

　a．算法的效率

　b．用于实现算法的计算机语言

　c．算法中的代码行数

　d．计算机上硬盘的速度

（5）具有两个循环的函数的渐近运行时间是（　　）。

　a．Θ (log2n)

　b．Θ (n)

　c．Θ (n2)

　d．没有足够的信息来确定

（6）如果Θ (n2)的算法需要3s才能处理有100万个元素的输入，那么大约需要多长时间才能处理200万个元素？（　　）

　a．6s

　b．9s

　c．12s

　d．18s

（7）如果Θ (n3)的算法需要4s才能处理有100万个元素的输入，那么大约需要多长时间才能处理200万个元素？（　　）

　a．8s

　b．16s

　c．32s

　d．64s

（8）如果的算法需要20s才能处理有100万个元素的输入，那么大约需要多长时间才能处理200万个元素？（　　）

　a．21s

　b．25s

　c．30s

　d．40s

（9）如果的算法需要10s才能处理有10个元素的输入，那么大约需要多长时间才能处理20个元素？（　　）

　a．20s

　b．100s

　c．1 000s

　d．10 000s

（10）如果计算机每秒能够执行10亿次操作，那么一个需要执行n2次操作的算法，面对200万个元素的输入，大约需要执行多长时间？（　　）

　a．400s

　b．2 000s

　c．4 000s

　d．20 000s

3．简答题

（1）函数/方法的副作用是什么？

（2）描述自上而下的设计的基本方法以及它与契约式设计之间的关系。

（3）如果需要重复地对一个有20个元素的随机列表进行搜索以查找用户输入的不同值，应该使用哪种搜索方法？应不应该创建另一个包含相同元素但已经有序的列表来进行搜索？为什么你这样认为？

（4）如果需要重复地对一个有2 000 000个元素的随机列表进行搜索以查找用户输入的不同值，应该使用哪种搜索方法？应不应该创建另一个包含相同元素但已经有序的列表来进行搜索？为什么你这样认为？

（5）对于上面的问题，Python的列表是存储数字最合适的数据类型吗？如果不是的话，你会使用Python的哪一个数据类型？

（6）如果计算机每秒能够执行10亿次操作，那么一个需要执行2n次操作的算法，面对n = 100个元素的输入，大约需要执行多长时间？

（7）如果计算机每秒能够执行10亿次操作，那么一个需要执行n2次操作的算法，面对n = 1 000 000个元素的输入，大约需要执行多长时间？如果算法需要执行n3次操作呢？

（8）对以下代码片段的时间复杂度进行Θ 分析。

a．n = input('enter n: ')
   for i in range(n):
       x = 2 * n
       while x > 1:
             x = x / 2
b．n = input('enter n: ')
   total = 0
   for i in range(n):
       for j in range(10000):
                total += j
   print total
c．total = 0
   n = input('enter n: ')
   for i in range(2 * n):
       for j in range(i, n):
                total += j
   for j in range(n):
       total += j
   print j

（9）书中第一个版本的线性搜索算法使用了Python的index方法，而没有用任何循环。但是，我们也提到了线性搜索算法的时间复杂度是Θ (n)。通常来说，没有循环的算法的时间复杂度应该是Θ (1)。请解释这一（明显的）差异。

4．编程练习

（1）创建一个包含0～999 999的拥有100万个整数的列表。分别用index方法和for语句的线性搜索，以及二分搜索对最好和最坏情况进行计时（像这一章的例子中那样，使用time.time函数）。在注释中列出你使用的计算机规格（CPU芯片和时钟速度、操作系统和Python版本）以及3个搜索在最好和最坏情况下的执行时间。

（2）创建元素为1～1 000万的整数，元素个数为10 000、100 000和1 000 000的随机列表。使用内置的列表sort方法来对每个列表进行排序并计时。在注释中列出你使用的计算机规格（CPU芯片和时钟速度、操作系统和Python版本）以及对每个列表进行排序所需的时间。注释中里还应该包括sort方法的Θ 时间复杂度。

（3）选择排序算法是这样来进行排序操作的：在未排序的序列里找到最小元素，然后和列表的第0个位置的元素互换；之后，再从列表里寻找第二小的元素，然后和列表的第1个位置的元素互换；以此类推，找到第n − 1个最小的元素并将其置于n − 2的位置。这时，最大的元素也就会处于位置n − 1上了。在Python里实现这个算法，并注明算法的Θ 时间复杂度。同样，对上一个问题里创建的那3个列表进行排序，并计时。

（4）设计一个比较对不同大小的列表执行线性搜索和二分搜索的实验。将结果输出成图，看看能不能找到线性搜索胜过二分搜索的那个“交叉”点。由于小列表搜索速度非常快，因此你得发挥一下聪明才智才能得到搜索时间的有效数据（提示：通过计算多次指定的搜索来得到更大的搜索时间总和）。写一份完整的实验报告，解释你的实验设置、方法、数据以及分析。

（5）完成在1.2.3小节里的统计信息程序。请务必在已知结果的数据集上彻底测试你的程序。

（6）在1.2.3小节的程序里添加一个函数，这个函数能够返回5个整数，分别是90分数段、80分数段、70分数段、60分数段和60以下分数段的分数的个数。确保为新函数提供完整的规范，并且包括适当的先验条件与后置条件，以及相应的实现代码。

（7）每当需要一组数据的平均值的时候，通常也需要计算标准差。这样一来，在1.2.3小节里的统计信息程序的现有API在某种程度上是低效的，这是因为在计算平均值和标准差的时候，会导致前者被计算了两次（为什么？）。重新设计这个程序的API来避免这个问题。你的新设计应该允许用户高效地单独计算平均值、单独计算标准差以及同时计算两个值。

（8）设计并实现一个问答程序。这个程序能够从文件里读取问答信息。例如，关于美国各个州的首府的问答程序将会在文件的每一行中找到州名和它的首府的名称（如俄亥俄州：哥伦布市）。你的程序应该询问一定数量的问题并输出正确答案的数量。在你的设计中至少要有3个独立的函数。

（9）编写一个函数的规范和实现，从有序列表中挤出（“squeeze”）重复项。例如：

>>> x = [1, 1, 3, 3, 3, 4, 5, 5, 8, 9, 9, 9, 9, 10]
>>> squeeze(x)
>>> x
[1, 3, 4, 5, 8, 9, 10]

彻底地测试你的函数并分析其效率。

[1]　在Python 3.0中，默认range表达式的行为类似于xrange，也不会创建列表。


目标

算法是程序的基本构建模块中的一员。在第1章里我们了解到了将函数会做什么与其实现细节分开所带来的好处。本章将介绍程序处理中的数据。当我们考虑数据对象时，分离行为和实现的好处会更大。在构建实用软件系统的时候，这种数据抽象（data abstraction）过程将会是一种必须掌握的基本概念。计算机科学家们将数据抽象的概念用抽象数据类型（Abstract Data Type，ADT）来具象化。也可以这样说，抽象数据类型是面向对象编程的基础，而面向对象编程是大型系统的主流开发方法。

我们首先要了解抽象数据类型以及它们与面向对象编程之间的关系。在这个过程中，本书将展示如何使用面向对象编程来扩展编程语言，使其具有新的数据类型，从而能更好地解决新领域之中的问题。对于支持运算符重载（operator overloading）这一能力的语言，新的数据类型将会看起来和语言自身的内置类型一样，并具有类似的行为。

使用抽象数据类型和对象，程序设计就成了把一个问题分解为更小部分的过程：一组互相协作的对象将会提供程序的大部分功能。随着这些较小的部件被一个一个地实现，它们都可以单独地进行测试，从而在将部件组合成更大的系统之前，让开发人员相信各个部件是具有正确性的。学习如何进行有效的测试是软件开发的另一个难题。

任何存储在计算机中的数据都有一个重要属性：数据类型（data type）。对象的数据类型决定了它可以拥有的值以及我们可以用它做什么（如它支持的操作类型有什么）。例如，在32位计算机上，内置类型int可以存储−231～231−1的任意整数，并且可以被用于加法（+）、减法（−）、乘法（*）和除法（/）等操作。在了解了这些信息之后，你就能够在不关心这些数字是怎么存储在计算机上的情况下，也能编写使用int的程序。用上一章中的术语来说，这个操作int数值的程序是一个int数据类型的客户端。

当然，为了使一个数据类型方便好用，必须对这个类型进行一些必要的底层实现。这些实现应该既包括一个可以在底层用来存储该类型的所有可能值的方式，也包括操作这个底层数据的一组函数。让我们回到int数据类型。在今天的计算机里，它通常用32位二进制来存储。而加法和减法之类的操作算法是在底层的机器硬件里定义的，输入和输出int的方法则内置在大多数编程语言里。

利用抽象概念，我们可以将数据存储方式和它的使用方式区分开来。也就是说，我们提供的数据类型的规范，可以和它的任何实际实现都不相关。这样的规范也就描述了一个抽象数据类型。精确而完整的规范描述，能够让客户端程序的编写无须关心抽象数据类型是如何在计算机中具体实现的。通过这种方式，数据抽象扩展了实现的独立性优势。这让我们可以在获得有关如何使用这个数据的足够信息之后，再决定程序中应该如何存储这个数据。而且，我们也可以去修改数据类型的具体存储，抽象的边界可以确保程序的其他部分不会受到任何不好的影响。

对于程序中可能发生变化的部分，数据的抽象尤为重要。重要的设计决策可以被封装在抽象数据类型里，之后抽象数据类型的具体实现可以根据需要来调整，而不会影响到程序的其余部分。之后你会看到，在通常情况下，更改数据的存储方式会对相关操作的效率产生重大影响。所以，在尝试调整程序的效率时，如果有修改存储方法的自由，对程序员来说是一个非常大的利好。

抽象数据类型的另一个优点是它可以促进重用。一旦实现了相关的抽象，它就可以被许多不同的客户端程序使用。这些客户端程序就不用再去重新“发明”这个数据类型，也就免除了许多麻烦。所以，程序员们也就能够为其特定编程领域中有用的新数据创建数据类型，从而实现对编程语言的扩展。同样，在对抽象数据类型进行了全面测试之后，就能够在不用考虑具体的实现细节下放心地使用它。

你可以将抽象数据类型看作操纵底层存储的函数或者方法的集合。存储的内容实际上只是一些数据集合。我们只需要描述抽象数据类型所支持的操作，就能够像之前分辨函数一样，分辨不同的抽象数据类型。唯一的区别是一个抽象数据类型是由一组函数来描述的。

我们来看一个简单的例子。假设我们正在编写一个关于纸牌游戏的程序，比如桥牌或德州扑克。我们可以把一张扑克牌定义为一个简单的抽象数据类型。下面是这个抽象数据类型的描述：

ADT Card:
    A simple playing card. A Card is characterized by two components:
    rank: an integer value in the range 1-13, inclusive (Ace-King)
    suit: a character in 'cdhs' for clubs, diamonds, hearts, and
          spades.

Operations:

    create(rank, suit):
        Create a new Card
        pre: rank in range(1, 14) and suit in 'cdhs'
        post: returns a Card of the given rank and suit.

    suit():
        Card suit
        post: Returns Card’s suit as a single character.

    rank():
        Card rank
        post: Returns Card’s rank as an int.

    suitName():
        Card suit name
        post: Returns one of ('clubs', 'diamonds', 'hearts',
              'spades') corrresponding to Card’s suit.

    rankName():
        Card rank name
        post: Returns one of ('ace', 'two', 'three', ..., 'king')
              corresponding to Card’s rank.

    toString():
        String representation of Card
        post: Returns string naming the Card, e.g. 'Ace of Spades'.

在这个描述扑克牌（Card）的规范里需要注意的是，它使用了一些抽象属性（数字和花色），我们可以用对扑克牌执行的操作来描述这个规范。它并没有描述扑克牌是如何实际存储以及如何实现各个操作的。实际上，规范里甚至没有明确地引用任何扑克牌对象或参数。这隐性地表明了一件事情；规范里的这些操作可以通过某种方式应用于任何扑克牌。

在设计抽象数据类型的过程中，我们的目标是：提供一整套能够使抽象数据类型变得有用的操作。当然，扑克牌（Card）抽象数据类型有许多不同的设计可供选择。例如，我们可以对不同的操作使用不同的名称。一些设计师更喜欢将访问抽象数据类型的函数冠以“get”开头的名称，因此，他们可能会使用getSuit和getRank代替获取花色和获取数字；其他的设计师可能会为各种操作的参数提供不同的类型，比如说，花色或许可以用整型（int）来表示而不是用字符串（string）；或者简单地提供一组用来表示花色和数字的变量，来“隐藏”它们的确切存储方式，比如，可以将叫作CLUBS（梅花）的标识符指定给表示花色的某个值，就像标识符None在Python里代表特殊的None对象一样。同样地，扑克牌的数字也可以用ACE（尖）、TWO（二）、THREE（三）等名字来表示。

随着你不断地获得使用抽象数据类型的经验，你会慢慢发掘自己的设计灵感。要记住，设计抽象数据类型最重要的一点是实现独立性。抽象数据类型仅仅描述了一组操作，而不用去描述这些操作的具体实现方式。一个可以用来“测试”抽象数据类型设计的好方法是：尝试编写一些使用它的客户端算法。例如，这里有一个用来输出一套标准扑克牌里所有牌的数字、花色和名称的算法：

for s in 'cdhs':
    for r in range(1, 14):
        card = create(r, s)
        print 'Suit:', suit(card)
        print 'Rank:', rank(card)
        print toString(card)

这个算法用了类似于Python的语法来表达，并且还加上了前面提到的抽象数据类型的抽象函数。这个算法表明，Card抽象数据类型的操作集能够创建和输出整套52种扑克牌。

在设计抽象数据类型的时候，是可以独立于语言的。但是实现和使用这个抽象数据类型的时候，就需要添加一些特定于某种编程环境的细节。程序员可以通过很多种方式将抽象数据类型转换到特定的编程语言上。实际上，所有的编程语言都提供了定义新函数的能力。所以，实现抽象数据类型的其中一种方法，就是编写一组适当的函数。例如，在Python中，我们可以为扑克牌抽象数据类型（Card）的每个操作都编写一个函数，并且将它们都放在同一个模块文件中。

当然，在编写这些功能的时候，我们需要决定如何在计算机上存储扑克牌抽象数据类型（Card）。这个抽象类型有数字和花色两个组件。在Python里，一个简单的存储方式是：将数字和花色组合起来作为元组（tuple）里的一对值。Python里的元组（tuple）是一个不可变（不可被修改）的值序列类型。它是在括号中使用逗号分隔符来分隔的序列。所以，使用元组之后，梅花尖可以被存储为元组(1，'c')，而黑桃王是(13，'s')。

抽象数据类型的基础存储方式称为具体存储方式（concrete representation）。例如，我们会说元组(5，'d')是抽象扑克牌（方片五）的具体存储方式。

现在，我们已经为扑克牌抽象数据类型（Card）决定了存储方式，编写具体的实现代码就变得非常简单。下面有一个实现的版本：

# cardADT.py
#    Module file implementing the card ADT with functions

_SUITS = 'cdhs'
_SUIT_NAMES = ['clubs', 'diamonds', 'hearts', 'spades']
_RANKS = range(1, 14)
_RANK_NAMES = ['Ace', 'Two', 'Three', 'Four', 'Five', 'Six',
               'Seven', 'Eight', 'Nine', 'Ten',
               'Jack', 'Queen', 'King']

def create(rank, suit):
   assert rank in _RANKS and suit in _SUITS
   return (rank, suit)

def rank(card):
    return card[0]

def suit(card):
    return card[1]

def suitName(card):
    index = _SUITS.index(suit(card))
    return _SUIT_NAMES[index]

def rankName(card):
    index = _RANKS.index(rank(card))
    return _RANK_NAMES[index]

def toString(card):
    return rankName(card) + ' of ' + suitName(card)

先来看看create函数。它使用了一个断言（assert）来检查是否满足创建扑克牌类型的先验条件，然后只返回一个数字花色的元组。通过这种方式，这个函数虽然只返回一个值，但是这个值体现了有关特定扑克牌的所有信息。

数字（rank）和花色（suit）的操作只是简单地打开了扑克牌元组的一部分。元组组件可以通过索引来访问，因此card[0]会给出第一个部分，即扑克牌的数字；同样，card[1]能够给出花色。这两个操作非常简单，所以你甚至可能会想是不是必须保留它们。使用扑克牌抽象数据类型（Card）的客户端能不能通过像myCard[1]这样的方式直接拿到花色呢？答案是，客户端可以做到，但不应该这样做。抽象数据类型的重点是对客户端和具体实现进行解耦。如果客户端直接访问具体存储方式，那么后面如果修改了具体存储的方式，将会导致客户端代码异常。在这里，请记住这一条例：客户端只能通过抽象数据类型提供的操作来使用抽象数据类型。

这段代码还有一个值得注意的地方是，里面使用了一些特殊的值：_RANKS、_SUITS、_RANK_NAMES和_SUIT_NAMES。suitName函数和rankName函数其实可以用一个大型的多路if语句来实现。但在这里，我们采用了表格驱动的方法，通过索引（index）方法来得到数字或花色的位置，然后使用这个索引值来查找相应的名字。这样做缩短了代码，从而使它更容易修改。比如说，我们只需要简单地在_SUITS和_SUIT_NAMES的末尾添加另一个元素，就能轻松地添加第五个花色。

值得一提的是，这个查找表格的变量名长得这么奇怪是有特殊原因的。常量名使用全大写，通常是常量的编程约定。常量就是被设置一次之后再也不会改变的量。名称前的下划线是Python的一种约定，表示这些名称在模块里是“私有的”。当客户端像下面这样导入模块的时候：

from cardADT import *

以下划线开头的标识符将不会被导入到本地程序。这就使得实现细节（例如查找表格的使用）不会破坏客户端程序的命名空间（定义的标识符集合）。

现在，我们已经有了扑克牌抽象数据类型（Card）实现，那么我们也就能够使用这个抽象数据类型模块来编写输出所有扑克牌的程序了：

# test_cardADT.py
import cardADT

def printAll():
    for suit in 'cdhs':
        for rank in range(1, 14):
            myCard = cardADT.create(rank, suit)
            print cardADT.toString(myCard)

if __name__ == '__main__':
    printAll()

总而言之，实现抽象数据类型的一种方法是：选择一个具体存储方式，然后编写一组操作这个存储方式的函数。如果我们的实现语言支持模块（就像Python一样），我们可以将所有的实现放在一个单独的模块之中，从而让它拥有自己独立的命名空间。

如果用来实现的语言不支持分离模块的思想，那么我们可能会遇到抽象数据类型之间的操作名称“冲突”的问题。例如，在编写玩纸牌游戏的程序的时候，可能还会有一个叫作deckADT的牌组抽象数据类型来代表一整副牌。可以肯定的是，牌组抽象数据类型会有自己的创建方法。但是，因为没有模块分隔，我们就必须依靠命名约定来保持操作的正确性。例如，扑克牌里的所有操作可能都会以card_开头，而牌组里的操作则会以deck_作为开头。因此，这个时候会有两个单独的函数：card_create和deck_create。

就像刚才看到的，抽象数据类型包含了一组操作底层数据存储的行为。你应该对这个概念很熟悉。因为只要你使用的是面向对象的编程语言（例如Python），那么把抽象数据类型当作编程语言里的对象是非常自然的，因为对象里也会包含数据和操作。简单来说，对象“能知道些什么（数据），还能做些什么（操作）”。对象里的数据是存储在实例变量中的，相应的各种操作就是它拥有的函数。所以，我们可以使用变量的实例来存储抽象数据的具体存储表示，编写各种函数来实现各个操作。

就像你已经知道的一样，新的对象类型可以使用类（class）来定义。随着Python语言的发展，它已经能支持两种不同类型的类，它们被称为经典类（classic class）和新式类（new-style class）。对于我们的例子来说，经典类和新式类的行为完全相同。在本书中我们将会使用Python的新式类，因为在编写新代码的时候新式类被强烈推荐。我们可以简单地通过使类继承内置的object对象来指示新式类。你并不需要知道有关继承的任何细节，就能够使用新式类。对于旧代码，你只需稍微改变一下这个类的头部就行了。比如，要创建具有新式类的Card类，我们应该编写class Card(object):而不是class Card:。[1]

在面向对象的编程语言里，可以定义一个新类来创建新的对象数据类型。我们可以把抽象数据类型直接转换描述成一个合适的类规范。下面就是一个关于Card类型的类规范：

class Card(object):
    """A simple playing card. A Card is characterized by two components.
     rank: an integer value in the range 1-13, inclusive (Ace-King)
     suit: a character in 'cdhs' for clubs, diamonds, hearts, and
           spades."""

    def __init__(self, rank, suit):
        """Constructor
        pre: rank in range(1,14) and suit in 'cdhs'
        post: self has the given rank and suit."""

    def suit(self):
        """Card suit
        post: Returns the suit of self as a single character."""

    def rank(self):
        """Card rank
        post: Returns the rank of self as an int."""

    def suitName(self):
        """Card suit name
        post: Returns one of ('Clubs', 'Diamonds', 'Hearts',
        'Spades') corrresponding to self’s suit."""

    def rankName(self):
        """Card rank name
        post: Returns one of ('Ace', 'Two', 'Three', ..., 'King')
        corresponding to self's rank."""

    def __str__(self):
        """String representation
        post: Returns string representing self, e.g. 'Ace of Spades'. """

简单来说，这个规范只是Card类在Python里的轮廓。这个类的文档描述给出了概述，然后各个方法里的文档描述表明了每个方法的作用。依照Python语言的一些约定，以双下划线为开头和结尾的方法名称（__init__和__str__）是特殊方法。Python会将__init__识别为构造函数，而当要求Python将Card对象转换为字符串的时候，__str__方法就会被调用。例如：

>>> c = Card(4, 'c')
>>> print c
Four of Clubs

现在我们已经把抽象数据类型转换成了面向对象的形式。因此这个类的客户端将会使用点操作符来执行抽象数据类型的操作。下面这段代码是用来输出整套52张扑克牌的代码，这些扑克牌都被转换成了对象的形式：

# printcards.py
#   Simple test of the Card ADT

from Card import Card

def printAll():
    for suit in 'cdhs':
        for rank in range(1, 14):
            card = Card(rank, suit)
            print 'Rank:', card.rank()
            print 'Suit:', card.suit()
            print card

if __name__ == '__main__':
    printAll()

要注意的是，使用类名称Card的时候，就会调用构造函数。当要求输出扑克牌对象的时候，Python会隐式调用__str__方法。

我们可以把之前的扑克牌抽象数据类型实现转换成新的基于类的实现，这样扑克牌的数字和花色组件就可以被存储在适当的实例变量里了：

# Card.py
class Card(object):
    """A simple playing card. A Card is characterized by two components:
    rank: an integer value in the range 1-13, inclusive (Ace-King)
    suit: a character in 'cdhs' for clubs, diamonds, hearts, and
    spades."""

    SUITS = 'cdhs'
    SUIT_NAMES = ['Clubs', 'Diamonds', 'Hearts', 'Spades']

    RANKS = range(1,14)
    RANK_NAMES = ['Ace', 'Two', 'Three', 'Four', 'Five', 'Six',
                  'Seven', 'Eight', 'Nine', 'Ten',
                  'Jack', 'Queen', 'King']

    def __init__(self, rank, suit):
        """Constructor
        pre: rank in range(1,14) and suit in 'cdhs'
        post: self has the given rank and suit"""

        self.rank_num = rank
        self.suit_char = suit

    def suit(self):
        """Card suit
        post: Returns the suit of self as a single character"""

        return self.suit_char

    def rank(self):
        """Card rank
        post: Returns the rank of self as an int"""

        return self.rank_num

    def suitName(self):
        """Card suit name
        post: Returns one of ('clubs', 'diamonds', 'hearts',
              'spades') corresponding to self's suit."""

        index = self.SUITS.index(self.suit_char)
        return self.SUIT_NAMES[index]

    def rankName(self):
        """Card rank name
        post: Returns one of ('ace', 'two', 'three', ..., 'king')
              corresponding to self's rank."""

        index = self.RANKS.index(self.rank_num)
        return self.RANK_NAMES[index]

    def __str__(self):
        """String representation
        post: Returns string representing self, e.g. 'Ace of Spades' """

        return self.rankName() + ' of ' + self.suitName()

要注意的是，以前版本里就存在的查找表格现在被设置为了Card类内部的变量，并且这个变量不属于任何一个方法。它们被称为类变量（class variable）。它们“存活”在类的定义之中，因此所有类的实例都会共享同一个副本。使用self.<name>约定，就能像访问实例变量一样去访问这些类变量。当Python被要求检索对象属性的值的时候，它会首先检查这个对象是否已经直接分配了这个属性。如果没有，Python将会继续在对象的类里去检索这个属性。比如说，在suitName方法里访问self.SUITS的时候，Python会知道self实例里没有SUIT属性，因此会使用Card类里的值（因为self是一个Card类）。

现在，程序里可以有3种不同的变量类型来存储信息：常规（本地）变量、实例变量和类变量。在实现一个抽象数据类型的时候，为给定的信息选择正确的变量类型是非常重要的。为了正确选择，你必须回答的第一个问题就是：数据需不需要被不同的方法互相使用？如果不需要，就应该使用本地变量。rankName中使用的索引（index）变量就是本地变量的一个很好的例子。方法一旦结束，这个值就不再被需要。可以看到，在suitName方法里也有一个名叫index的本地变量。即使它们正好具有相同的名称，它们也是两个完全独立的变量。因为，每个变量都只在执行相应的方法时才存在。我们也可以在这两个方法里使用实例变量self.index来编写。但是，这样做会是一个充满误导性的设计，因为我们没有理由在执行rankName或suitName方法的时候保留index变量里的值。在这种情况下，不同方法可以重用这个实例变量，也就意味着方法之间存在一个不应该存在的连接。

需要被不同的方法互相使用的数据应该存储在实例变量或者类变量中。在这种情况下，使用哪种变量类型取决于数据在不同的对象之间是否互不相等，或者对于这个类的所有对象是否都是相同的。在我们的扑克牌示例中，self.rank_num和self.suit_char在不同的扑克牌里拥有不同的值，它们是特定扑克牌实例里的一部分，所以它们必须是实例变量。相应的，花色名称对于扑克牌类的扑克牌实例来说都是相同的，这样使用类变量才是有意义的。常量通常都应该是类变量，因为根据定义，它们在不同的对象之间是相同的。当然，有些情况下，非常量的类变量也是合理的。记住这些简单的规则应该可以帮你轻松地将抽象数据类型转换为工作类。

正如你所见，抽象数据类型的概念与面向对象的类之间存在着自然的相互对应的关系。在使用面向对象的编程语言的时候，一般都会把抽象数据类型实现看成一个类。使用类的好处在于，它能够很自然地将抽象数据类型的两个方面（数据和操作）融合到一个程序结构里。

之前强调过，使用抽象数据类型来设计软件的主要优势是实现独立性。然而，到目前为止，我们讨论的扑克牌示例里并没有真正体现这一点。毕竟，我们只是定义了一张数字是整型（int）、花色是字符的扑克牌，然后把这些值存为实例变量。客户端在操作数字和花色的时候，好像直接就使用了这个存储方式。

在这种情况下，客户端看起来可以直接访问存储方式仅仅是因为：我们选择的具体存储方式直接反映了向抽象数据类型传递的和来自于它的信息的数据类型。但是我们是通过方法（如suit和rank）来访问的数据，因此能够在不影响客户端代码的情况下更改具体存储方式。这个地方，就有了独立性。

假设我们正在为手持设备（如PDA或者手机）开发一款纸牌游戏。在这样的设备上，可能会有更严格的内存限制。目前，我们的扑克牌的存储方式需要每张扑克牌有两个实例变量：数字，这是一个32位的整型int；以及花色，这是一个字符。另一种可以考虑的扑克牌存储方式的方法是给它们编号。由于一共只有52张扑克牌，每张扑克牌都可以用0～51的数字来表示，因此，先考虑按照花色的顺序来排列扑克牌。例如，所有的梅花在前面，方块次之。然后把整套扑克牌按照数字大小的顺序放入。这样，我们就有了一个完整的扑克牌组，在这个牌组里的第一张牌是梅花尖，最后一张是黑桃K。

只要有一个扑克牌的序号，就可以计算出它的数字和花色。由于每个花色都有13张牌，将序号除以13（使用整数除法）就会得到一个0～3（含）的值。这样0将会代表梅花，1将会代表方片，以此类推。此外，这个除法的余数将会给出这个扑克牌在某个花色里的相应位置（也就是扑克牌数字）。比如，如果扑克牌的序号是37，因为37 // 13 = 2，所以花色是红心，而37 % 13 = 11，说明这个扑克牌的数字是Q，因为任意花色里的第一张牌（尖）的余数都会是0。所以，序号为37的扑克牌是红桃Q。通过这种方法，扑克牌抽象数据类型的具体存储方式就变成了单个数字。我们将会把这种更具内存效率的存储方式的Card类作为练习让读者去实现。

你一定已经发现了，抽象数据类型和面向对象编程的思想之间存在密切的对应关系。但面向对象（Object-Orientation, OO）不仅仅能用来实现抽象数据类型。大多数的面向对象专家都谈到了程序开发真正面向对象的3个特性：封装、多态和继承。

2.3.4.1　封装

我们已经知道，对象“能知道些什么，还能做些什么”，它结合了数据和操作。将数据和可以对这些数据进行的操作集打包在一起的过程称为封装（encapsulation）。

封装是使用对象的主要吸引力之一。它提供了一种方便的方法来构建复杂问题的解决方案，这些问题正好和我们对世界运作方式的直观看法相对应。我们会非常自然地认为，我们周围的世界是由能够相互作用的物体所组成。每个对象都会有它自己的身份标识，而知道对象是什么类型，可以让我们理解它的本质和能力。当你望向窗外的时候，你会看到房屋、汽车和树木，而不是大量分子或者无数的原子。

从设计的角度来看，封装还是一个关键服务，被用来区分“是什么”和“如何做”。对象的实际实现和它的使用无关。封装是我们能够实现独立性的原因。封装可能是使用对象最大的好处，但只凭封装，也只能使系统基于对象。对于真正的面向对象，还需要有多态和继承的特性。

2.3.4.2　多态

从字面上来看，多态（polymorphism）这个词代表的是“多种形态”。在面向对象的上下文里使用这个词的时候，它指的是一个对象在响应消息（方法调用）时所做的事情取决于对象的类型或者对象的类。设想这样一个简单的例子：你正在使用一个图形库来绘制二维图形，这个代码库提供了许多可以用来绘制的基础几何图形类，每个图形类都有一个用来绘制这个图形的操作。这时会有类似下面这样的包含若干个类的集合：

class Circle(object):
    def draw(self, window):
        # code to draw the circle

class Rectangle(object):
    def draw(self, window):
        # code to draw the rectangle

class Polygon(object):
    def draw(self, window):
        # code to draw the polygon

当然，除了draw方法，这些类中也会有其他的一些方法。这里只是给出了一个简单的示例。

假设你编写的程序创建了一个包含若干种几何对象的列表，这个混合列表里有圆形、矩形、多边形等。要绘制列表中的所有对象，你可以用下面这个代码：

for obj in objects:
    obj.draw(win)

让我们来看看在循环体中的那一行代码：当执行obj.draw(win)的时候，调用的应该是什么函数？其实，这一行代码调用了几个不同的函数。当obj是圆形（Circle）时，它会调用圆形（Circle）类的draw方法；当obj是矩形（Rectagle）时，它会调用矩形（Rectagle）类里的draw方法；对于多边形（Polygon）类也是一样的。在这里，draw的操作有多种形式，具体使用哪一种，取决于obj的类型。这就是多态。

多态为面向对象系统提供了执行对象的操作的灵活性，就像它很自然地执行对象的方法一样。如果没有对象支持多态，就只能像下面这样做了：

for obj in objects:
   if type(obj) is Circle:
       draw_circle(...)
   elif type(obj) is Rectangle:
       draw_rectangle(...)
   elif type(obj) is Polygon:
       draw_polygon(...)
...

这段代码不仅更加烦琐，而且灵活性也低得多。这样在我们想要向图像库里添加另一种类型的对象的时候，我们就必须根据对象类型找到我们做出这些判断的所有位置，然后再添加另一个分支。在支持多态的版本里，我们只需创建一个包含draw方法的新的几何对象类，而所有其他地方的代码都不用修改。多态的这一特性允许我们在不修改现有代码的情况下扩展程序。

2.3.4.3　继承

面向对象开发的第三个重要特性是继承（inheritance）。顾名思义，继承的含义是一个新类可以在定义的时候，从另一个类里“借用”它的行为。新类（进行借用的类）被称为子类（subclass），已经存在的类（被借用的类）则是它的超类（superclass）。

比如，现在我们要构建一个记录员工信息的系统。我们可能会有一个Employee类，这个类里包含了所有员工共有的一般信息和方法。一个例子是用来返回员工的家庭地址的homeAddress方法。员工也有不同的类别，在这里，我们可以简单地把他们区分为全职员工（SalariedEmployee）和小时工（HourlyEmployee）。我们可以创建基于Employee类的这些子类，这样的话，它们就同样会包含homeAddress方法。同时，因为不同类别的员工的薪酬计算方式各不相同，每个子类都会有它自己的monthlyPay函数。图2.1所示为这种情况的简单类图。单向的箭头表示继承；子类继承了Employee类中定义的homeAddress方法，但每个子类都定义了自己的monthlyPay方法实现。

图2.1　继承的简单示例，其中子类的继承共享了一个方法，每个子类也有单独实现的一个方法

继承提供了两个好处。一个是我们可以构建系统里的类的关系来避免重复操作，在上面这个例子里，我们不需要为HourlyEmployee类和SalariedEmployee类都编写单独的homeAddress方法。另一个好处是新类通常可以基于已经存在的类，从而促进代码重用。

现在，我们已经知道了抽象数据类型和面向对象的原则，让我们回过头来看看第1章中提到的统计信息程序。只不过这一次，我们会用面向对象的办法来解决这个问题。

设计的本质是：用“黑箱”和它的接口来描述系统。每个组件都通过接口来提供一个服务或者一套服务集合。在自上而下的设计中，函数/方法起到了这个“黑箱”的作用。客户端程序可以使用函数，只要它能够理解这个函数/方法能做什么就行了，具体这个函数/方法是怎样完成这个功能的，详细信息被封装在函数的定义之中。相应的，在面向对象设计（Object-oriented Design，OOD）中，对象就是这个“黑箱”。

因为每个类都能够独立存在，所以如果我们可以将一个庞大的问题分解为一组相互协作的类，那么我们就能够大大降低必须要考虑的问题的复杂性，从而方便地理解程序的任何部分。面向对象设计是分析和定义某个给定的问题，从而得到一组有用的类的过程。像所有设计工作一样，面向对象设计也有着一部分的艺术和一部分的科学。

面向对象设计有很多种方法，每种方法都有一套属于它的特殊技巧、符号、关键点和注释。了解设计的最佳方法应该就是不断地去尝试。你设计得越多，你就能够掌握得越好。下面是面向对象设计的一些非常直观的指南，应该能够让你更快地入门。

1．寻找候选的对象。目标是定义一组有助于解决问题的对象。首先来仔细考虑一下问题的描述。对象通常都是用名词来描述的。因此，你可以把问题描述里的所有名词都加上下划线，然后再一一考虑它们。它们中的哪一个会在程序里被存储起来？哪一个有一些“有趣”的行为？可以用基础数据类型（数字或字符串）来存储的东西，一般来说不会是对象的重要候选者。而涉及一组相关数据项（比如点的坐标，或者是关于员工的个人数据）的东西，一般可能会是一个比较好的候选者。

2．找出实例变量。在发现了一些潜在候选对象之后，就要考虑这些对象要完成其自身工作所需要的相关信息。实例变量里应该有哪些值？一些对象可能只会包含基础的元数据；而其他的一些对象可能本身就是个复杂类型，表示其他有用的对象或者类。要努力为你的程序中的所有数据都找到一个合适的“家”（类）。

3．考虑一下接口。当你确定了潜在的候选对象/类以及和它们相关联的一些数据之后，就要开始去考虑这些类的对象应该有什么有用的操作。和之前类似，你可以从问题描述里的动词开始，因为动词会被用来描述动作——这个对象必须要去做什么。这样，你就能够列出这个类所需要的所有方法。记住一件事情：对象的所有数据操作，都应该通过你提供的方法来完成。

4．优化那些庞大的方法。有些方法看起来可能只需要几行代码就能够完成。与此相对的是，其他的一些方法则需要大量的工作来开发相应的算法。我们可以用自上而下的设计和逐步细化来实现复杂方法的细节。随着设计工作的进展，你可能会发现，这个类需要与其他类进行一些新的交互，而这就会让你只能在其他类里添加新的方法。当然，有些时候，你也会发现可能需要一个全新的对象来定义另一个类的调用。

5．迭代设计。在完成设计之后，你可能会在设计新类和向现有类添加新的方法之间来回反复。这是正常的，接着做你需要做的事情就好了。没人可以完美地、一次性就自上而下地把一个程序设计出来。所以，做你需要做的事情就好了。

6．尝试替代方案。当遇到一个看起来不起作用的方法，或者去验证一个想法的时候，不要害怕废弃这个方案。好的设计会经历大量的反复试验。当你看别人的程序的时候，你看到的是一个已经完成了的工作，而不是他们设计编写实现这个结果的过程。如果一个程序被设计得非常好，那么它很有可能不是第一次尝试就得到的结果。传奇软件工程师弗雷德·布鲁克斯（Fred Brooks）创造了这样一句格言：“把扔掉也加进计划。”通常来说，在你还没有错误地构建系统的经验时，你并不会真正地知道应该怎样去构建一个系统。

7．把事情简单化。在设计的每一步，都应该尝试找到最简单的方法来解决手上的问题。除非明确地知道需要更复杂的方法来实现，不然不要为设计带来额外的复杂性。

还是回到之前那个统计信息程序里。我们的目标是：报告一组代表考试分数的简单统计数据。这个程序里最有可能的候选者对象是什么？从问题描述来看，我们需要对分数（名词）进行操作。那么分数应该是一个对象吗？一般来说，分数只是一个数字，看起来Python内置的其中一个数字类型能够被用在这里，比如说浮点数float类型。那还有什么问题呢？为了计算需要的统计数据，我们需要跟踪整组分数。在统计里，我们把这些分数称为数据集（dataset）。集合往往是抽象数据类型的一个良好候选者。那么在这里，我们尝试使用一个数据集（Dataset）类。同样，根据问题里要求的统计信息，很明显我们需要一些方法来返回数据集中的最小值、最大值、平均值和标准差。

最后一个问题是：怎样才能把数字输入到数据集（Dataset）里？数据集（Dataset）类提供了一个简单的方法add来在数据集中放置一个数字。因此，我们可以在构造函数里初始化一个空的集合，然后一个一个地添加数字。这里有一个关于数据集（Dataset）的规范的例子：

# Dataset.py
class Dataset(object):
    """Dataset is a collection of numbers from which simple
    descriptive statistics can be computed."""

    def __init__(self):
        """post: self is an empty Dataset"""

    def add(self, x):
        """add x to the data set
        post: x is added to the data set"""

    def min(self):
        """find the minimum
        pre: size of self >= 1
        post: returns smallest number in self"""

    def max(self):
        """find the maximum
        pre: size of self >= 1
        post: returns largest number in self"""

    def average(self):
        """calculate the mean
        pre: size of self >= 1
        post: returns the mean of the values in self"""

    def std_deviation(nums):
        """calculate the standard deviation
        pre: size of self >= 2
        post: returns the standard deviation of the values in self"""

只需要看一看这个规范，我们就会知道，我们应该在抽象数据类型里添加一个新操作。这是因为，很多操作都需要基于数据集中有多少元素这个前提条件，所以我们应该有一个返回这个值的操作。保证抽象数据类型操作的先验条件的有效性，总是不会错的。这样做，能够允许客户端正确地使用抽象数据类型，同时也能让执行的代码更方便地检查先验条件。因此，让我们再添加一个方法：

def size(self):
    """
    post: returns the size of self (number of values added)
    """

和以前一样，我们可以通过编写一些使用该方法的代码来“测试”我们的设计。在这个例子里，可以直接利用数据集（Dataset）抽象数据类型来为我们的应用程序编写主程序。我们所需要的只是一个能够监听输入数据的循环：

# test_Dataset.py
def main():
    print 'This is a program to compute the min, max, mean and'
    print 'standard deviation for a set of numbers.\n'
    data = Dataset()
    while True:
        xStr = raw_input('Enter a number (<Enter> to quit): ')
        if xStr == '':
            break
        try:
            x = float(xStr)
        except ValueError:
            print 'Invalid Entry Ignored: Input was not a number'
            continue
        data.add(x)
    print 'Summary of', data.size(), 'scores.'
    print 'Min:', data.min()
    print 'Max:', data.max()
    print 'Mean:', data.average()
    print 'Standard Deviation:', data.std_deviation()

if __name__ == '__main__':
    main()

为了实现我们的数据集（Dataset）抽象数据类型，我们需要为这组数字提供具体存储方式。一种显而易见的方法是：使用一个数字列表，就像我们在使用自上而下设计开发的那个最初版本里做的一样。在这种实现里，add方法只是把一个数字添加到列表之中，然后，每个统计方法会循环遍历数字列表中的所有元素来执行计算。

当然，和几乎任何抽象数据类型一样，这里也可以用一些其他可能的具体存储方式。比如，我们真的需要在数据集（Dataset）里储存所有列表里所有的数字吗？实际上，这些方法里，没有一个真的需要知道在集合里的每一个具体的数字，它们只是需要一些关于这些数字的摘要信息。比如说，很显然，min（最小值）和max（最大值）方法只需要分别知道到目前为止已经添加到集合里的最小值和最大值；average（平均值）只需要知道所有数字的和以及整个数据集的尺寸就能实现。因此，我们可以将诸如数据集尺寸、最小值、最大值和所有数据之和这类的摘要信息储存为实例变量。那么，在将新数字添加到数据集（Dataset）的时候，add方法将会更新这些实例变量，而不需要单独存储所有的数字。

但是在这个时候，我们没办法得出标准差。最早我们使用的标准差公式需要计算每个数字与平均值之间的差值。显然，在我们得到所有数据之前，我们无法知道平均值是什么，因此在计算标准差的时候，我们需要在知道平均值之后再次遍历每一个数字，从而得到它们与平均值之间的差值。然而，这里有一个称为“捷径公式”的等价标准差公式，它的计算方法是这样的：

这个公式不需要我们知道每个xi，只需要知道所有数字的和以及它们的平方和就行了。因此，我们只需要再增加一个额外的实例变量来存储平方和，就能使用这个公式了。

那么，我们现在有两种可能的数据集（Dataset）类的具体存储方式：第一个版本基于之前的设计，通过维护一个包含所有数字的列表的实例变量（如self.data）来实现；第二个版本则是通过维护一组表示数字的摘要信息的实例变量（self._size、self._min、self._max、self._sum、self._sum_squares）来实现。[2]

使用任何一个具体存储方式来实现数据集（Dataset）类，对你来说应该都没什么问题了。你可以在练习里编写实际的代码。但是，即使没有代码，也可以分析这两种存储方式的相对效率。与最初使用的自上而下设计所开发的版本相比，第二种存储方式具有几个优点。比如，最明显的，因为它不需要记住已添加到集合中的数字列表，所以它在存储空间方面会更加有效。实际上，当添加更多数据时，这种更高效的数据集（Dataset）对象的内存占用量甚至不会发生改变。

非常有趣的是，第二种存储方式在执行时间方面也更加有效。在第一个版本里，每个统计操作都必须循环遍历整个数字列表，因此时间复杂度是Θ (n)的效率，其中n是数据集的大小。而第二个版本不需要循环，所有操作都是常量时间，因此是Θ (1)。

希望通过之前的例子，你能知道如何通过使用对象来设计以及实现抽象数据类型。新的类型能够让我们扩展可用的词汇量来解决新的问题。在本节中，我们将会通过一个新的数值数据类型来介绍扩展Python的实用技术。

你已经知道了，含有小数的数字通常用float数据类型来表示。使用浮点数（float）的一个缺点是：底层存储方式只是一个近似值，而不是精确值。数字会首先被转换为二进制（基数2），因此不以2的幂作为分母的任何分数，都将会转换成具有无限循环的商。而当这个商数为了放进有限的存储器位置而被截断时，就会丢失一些精度。对于某些应用程序，最好能有一个可以直接操作分数的数据类型，这样可以准确地存储和使用诸如这样的值。让我们用一个表示有理数（分数）的新的有理数（Rational）类来扩展Python语言。

抽象地来说，有理数（Rational）类应该像数学中的有理数一样。一个有理数有分子和分母，它们都是整数，而且也能支持常用的数字运算。所以，具体来说，我们将在新的有理数（Rational）类里实现有理数这个抽象数据类型。

在构建新的有理数（Rational）类的时候，我们希望让它的行为尽可能地和现有的数字类型一样。通常来说，我们会用数学运算符，比如+、−、*和/来执行整数和浮点数的操作。从技术上来讲，这些运算符在Python（以及许多其他语言）中被重载（overloaded）了，因为每个运算符都根据数字类型的不同被用来做不同的操作。例如，运算符+能被用于整数的加法和浮点数的加法。这个时候，执行的具体操作取决于操作的数字的数据类型。在用加法运算符的时候，我们可能不会注意到这些，但是在使用除法运算符的时候，我们就能发现他们之间存在很大的差异。[3]

在我们设计自己的类的时候，让新的数据类型能够使用已有的运算符是非常有意义的。一些面向对象的语言（比如Python和C++）支持这样一种机制，它允许程序员使用现有的运算符调用新函数，从而可以将运算符重载，扩展到程序定义的新的类型。而其他的一些语言（比如Java）则不支持这样的操作。

如果我们在不能重载运算符的语言里实现有理数（Rational）类的话，我们只能编写代码来实现add方法，然后使用语法r3 = r1.add(r2)来调用它，从而让两个有理数相加，然后把结果存储在r3中。这本身并没有任何问题，但是我们会更熟悉r3 = r1 + r2这样的表示方法，而且它有更好的可读性。所以，运算符重载并不是必需的，但如果使用得当可以提高可读性。当然，如果使用不当，它也可能导致可读性降低。想想看，如果有人编写的代码导致加法运算符实际上是让两个对象相减，或者去执行一些完全不相关的函数会意味着什么。

在Python里，定义以双下划线开头和结尾的特殊名称的方法，就能够在新类里重载某些内置的运算符。Python参考手册里指定了可以扩展的完整运算符列表。表2.1所示是其中的部分列表，可以为你自己的类提供运算符功能。从这个表里我们可以知道，如果我们希望让类的实例能够被写为c = a + b，就需要在类里编写方法__add__(self, other)。只要我们这样做了，代码c = a + b就会相当于c = a.__add__(b)。在Python中，a和b不必是相同的数据类型，但在大多数情况下，他们应该是相同的数据类型。

表2.1　一些可以在Python类里重载的运算符方法

Method

Returns

__add__(self, other)

self + other

__sub__(self, other)

self - other

__mul__(self, other)

self * other

__div__(self, other)

self / other

__neg__(self)

-self

__and__(self, other)

self & other

__or__(self, other)

self | other

__iadd__(self, other)

self += other

__isub__(self, other)

self -= other

__imul__(self, other)

self *= other

__idiv__(self, other)

self /= other

__lt__(self, other)

self < other

__le__(self, other)

self <= other

__gt__(self, other)

self > other

__ge__(self, other)

self >= other

__eq__(self, other)

self == other

__ne__(self, other)

self != other

使用Python的运算符重载，可以非常容易地编写有理数类。下面的代码显示了有理数（Rational）类的开始部分。它实现了__mul__和__str__方法，还实现了除了self参数之外，支持零个、一个或两个参数的构造函数。与之前一样，每个方法的先验条件和后置条件描述都被放在文档字符串里。这个示例里有两个实例变量：num和den。要注意的是，__mul__方法会创建一个新的有理数（Rational）对象，而不会去修改self或other里的实例变量。当重载运算符的时候，保留运算符的“标准”语义非常重要，也就是说它们都是在不修改原始数据的情况下去生成新值。当我们看到代码c = a + b的时候，我们并不认为a和b的值会改变。

# Rational.py
# demonstrates operator overloading

class Rational(object):

    def __init__(self, num = 0, den = 1):

        """creates a new Rational object
        pre: num and den are integers
        post: creates the Rational object num / den"""

        self.num = num
        self.den = den

    def __mul__(self, other):

        """* operator
        pre: self and other are Rational objects
        post: returns Rational product: self * other"""

        num = self.num * other.num
        den = self.den * other.den
        return Rational(num, den)

    def __str__(self):

        """return string for printing
        pre: self is Rational object
        post: returns a string representation of self"""

        return str(self.num) + '/' + str(self.den)

当然，完整的有理数（Rational）类应该为所有的基本数值操作都实现相应的方法。你可能会很想深入挖掘里面的细节从而完成这个类。这是一个很好的想法，但是在这里，我们建议你能够先把下一节中的内容学会。

因为我们将程序开发分解成了一个一个单独的类，所以要是能够在每个类的开发之后都能测试它是否有效就很好了。而且，如果我们可以边开发边测试正在开发的类，那就会更加方便。在Python里，一种不错的用来测试正在开发之中的类的方法是：交互式地在Python的命令行里进行测试。比如，我们可以这样来测试有理数（Rational）类的乘法：

>>> from Rational import Rational
>>> r1 = Rational(1,2)
>>> r2 = Rational(1,3)
>>> print r1 * r2
1/6

像这样单独测试一个组件被称为单元测试（unit testing）。通过测试单独的一个组件，我们可以很轻松地隔离出发生错误的位置。当我们对每个组件都充满信心的时候，我们就可以开始将它们组合到一个系统里了。

交互式单元测试的一个问题是，每次修改了组件之后，我们都只能从头创建测试。假设我们的乘法测试给了我们一个不正确的结果，我们就要回到代码里，找到错误，修复代码。完成修复之后，我们只能重新输入这4行测试代码。对于小型测试来说这是可以接受的，但是当测试变得更庞杂的时候，这样做就会变得非常烦琐。

交互式单元测试的替代方法是，把单元测试编写成一个可以在需要时运行的实际程序。这是一个十分常见的任务，因此已经有许多的框架被开发出来了，这也就使得我们编写单元测试越来越容易了。Python的库里包含了两个不同的单元测试框架：unittest和doctest。Python的unittest模块基于一个流行的框架（通常被称为xUnit），这个框架已经被移植到了许多面向对象的编程语言之中。我们在之后的单元测试示例里将会使用这个框架。下面是一些使用unittest模块来测试我们这个简单的有理数（Rational）类的代码：

# test_Rational.py
# unittest example

import sys
import unittest

sys.path.insert(0, '..')
from Rational import *

class RationalTest(unittest.TestCase):

    def testConstructorOneInt(self):

        r = Rational(-3)
        self.assertEqual(str(r), '-3/1')

    def testConstructorTwoInt(self):

        r = Rational(3, 4)
        self.assertEqual(str(r), '3/4')

    def testMul(self):

        r1 = Rational(2, 3)
        r2 = Rational(3, 4)
        r3 = r1 * r2
        self.assertEqual(str(r3), '6/12')

def main(argv):
    unittest.main()

if __name__ == '__main__':
    main(sys.argv)

虽然这个例子里的代码并不多，但是里面有些代码你以前可能并没有见过。比如说，在代码顶部的sys.path.insert这句代码。很多程序员都遵循创建一个名为test的子目录来包含测试代码的惯例，这样能让程序的生产代码和仅仅是为测试而编写的代码分隔开。依照这个约定，我们假设test_rational.py会放在这个子目录中，因而这个子目录会位于放置有理数（Rational）类代码的文件（Rational.py）的目录之下。

当我们把测试代码放在它自己的一个目录里会导致一个问题，那就是当测试代码需要导入有理数（Rational）模块的时候，Python并不会知道应该去哪里找到它。Python通过搜索来查找模块的目录序列被称为路径（path）。通常来说，这个路径会包含Python在系统目录中所存放的所有标准库模块，以及执行Python的本地目录。因此，只要我们导入的是系统范围的模块或者是和正在运行的程序位于同一文件夹里面的模块，就都没有问题。那么，为了让测试代码能够导入有理数（Rational）模块，我们就需要修改这个标准路径。Python允许程序员把需要的路径插入系统模块sys.path里的列表之中。它只是一个字符串列表，指定了Python模块所在的各种目录。执行代码sys.path.insert(0，'..')会将'..'放在路径列表的最前面。'..'是一个用来指示当前目录（顺便说一下，用'.'表示）的父级的约定。这样就能允许测试代码在执行from Rational import *这一行的时候，在父目录中去搜索Rational.py文件。

这个测试代码的核心在于这一行class RationalTest(unittest.TestCase):定义的是名为RationalTest的类。这个声明表明了RationalTest类继承自unittest模块中的TestCase类。我们换一种说法：RationalTest类是unittest模块中定义的TestCase类的子类。基于继承，RationalTest的任何实例也将是超类TestCase的一个实例。你可以把TestCase的实例当作要运行的一系列测试。

TestCase超类为单元测试定义了许多非常有用的方法。最常用的两个是assertEqual（也称为failUnlessEqual）和assertNotEqual（也称为failIfEqual）。每个方法都接受两个用来测试相等性的参数，以及一个可选的用来显示测试失败时要显示的消息的第三个参数。如果前两个参数不相等，则测试assertEqual会失败；而如果两个参数相等，则测试assertNotEqual会失败。TestCase类还支持很多其他的测试方法，你可以通过查阅unittest的文档来了解这些方法。

回到我们的RationalTest类里，当测试代码运行的时候，unittest框架将会自动调用以test这4个字母作为开头的所有方法。单元测试的思想是编写方法来测试你所有的代码。因此，你会发现测试代码里的方法甚至比Rational类里的方法还要多。这是一个很常见的现象，因为只靠一个测试通常来说并不能确保方法的正常工作。要运行这些测试，只需要调用unittest模块里的main函数就行了。这个函数会自动创建文件里的所有测试类（所有unittest.TestCase的子类）的实例，然后执行每个测试方法。要注意的一点是，每个测试方法都会使用一个“全新”的测试实例来运行，因此每个测试都是相互独立的。也就是说，测试运行的顺序对测试的结果没有任何影响。

下面这个输出是所有测试都通过时test_Rational.py测试代码的输出：

...
----------------------------------------------------------------------
Ran 3 tests in 0.001s

OK

那3个点表明了我们3个测试方法的结果。点代表测试成功完成了，而如果测试代码发生了未处理的异常，则结果为“E”，“F”则说明测试里的验证失败了。

当然，当测试失败的时候，结果会更有趣。比如，我们修改了__mul__方法，那一行代码现在成了den = self.den * other.num。当我们再一次执行测试程序的时候，就会得到下面这个输出：

..F
======================================================================
FAIL: testMul (__main__.RationalTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./test_Rational.py", line 39, in testMul
    self.assertEqual(str(r3), '6/12')
  File "/usr/lib/python2.2/unittest.py", line 286, in failUnlessEqual
    raise self.failureException, \
AssertionError: '6/9' != '6/12'

----------------------------------------------------------------------
Ran 3 tests in 0.004s

FAILED (failures=1)

这时你应该能发现，输出结果的最上面的状态行显示第三个测试失败了，之后输出了一个回溯来说明是哪一行导致了这个测试的失败。

以这种方式进行编码为单元测试提供了诸多好处：最明显的是，它能够允许我们在修改代码的时候很简单地运行测试。因为我们可以保存所有的测试，之后当我们对代码进行了任何更改时，我们都能够轻松地重新运行所有测试，甚至是之前已经通过了的测试。让修改过的程序去运行之前已经成功的测试被称为回归测试（regression testing）。回归测试有助于确保程序在开发的时候，是在不断地改进的（也就是说，新的修改没有破坏掉之前的功能）。

在编写一个类的同时去编写单元测试的另一个好处是：可以帮助我们去完成类的设计。测试代码代表了应该如何去使用这个类，编写测试有助于我们确定我们的类是不是具有良好的设计且易于使用。当前，一些现代的软件开发方法主张测试驱动开发（test-driven development）。测试驱动开发代表着在将任何实际生产代码添加到系统之前，首先添加的会是测试代码。按照这样一个流程，每个函数/方法被添加的时候，它都能够被立刻测试。在编写下一个函数/方法之前，你就可以确定这个函数/方法是不是能够正常工作了（通过这部分代码的测试）。

我们认为测试驱动开发是一种非常好的技术。因此，我们建议你在编写一个新类的时候，一开始在每个方法里只使用pass语句；然后去编写其中一个方法的测试代码；接下来再去这个类里实现这个方法从而让它能够通过测试；之后，不断地去重复编写新的测试和修改类的这一个过程，直到完成整个类并且通过所有的测试。每次对类进行修改的时候都应该能够通过所有的已经存在的测试，这样会让你在尝试新的设计理念时充满信心。像这样的测试框架有助于实现独立性，而且你会惊讶地发现，采用编写实现代码然后测试这样一前一后的流程来完成程序编码是多么地快速。

这一章里，我们介绍了数据抽象和面向对象编程的基本思想。下面是关于这些关键思想的摘要。

1．判断题

（1）在Python里，必须使用类来实现一个抽象数据类型。（　　）

（2）如果编程语言支持类，那么在实现抽象数据类型的时候通常应该使用类。（　　）

（3）类变量可以被类的所有实例共享。（　　）

（4）在设计程序的时候，一种定位潜在对象的方法是在系统描述里查找动词。（　　）

（5）封装是指将数据和方法组合成一个句法单元。（　　）

（6）通过使用多态，程序员将会编写多路if语句来查验对象的类型，从而确定应该调用哪一个方法。（　　）

（7）子类会继承其超类中定义的方法。（　　）

（8）运算符重载能够允许程序做一些在没有运算符重载的情况下不能做的事情。（　　）

（9）要在Python中重载运算符，就必须使用类。（　　）

（10）每次修改类的时候，都应该执行所有的单元测试。（　　）

2．选择题

（1）在开发大型软件系统的时候，你应该（　　）。

　a．马上坐下来，开始编写代码

　b．设计系统的一部分，编写一部分代码，在需要的时候重新设计这部分代码，并且在编写代码时测试这部分组件

　c．在编写任何代码之前先设计整个系统

　d．在测试任何代码之前先实现整个系统

（2）程序描述里的哪些部分对于找到系统设计时可能的对象最有帮助？（　　）

　a．形容词

　b．名词

　c．动词

　d．以上所有内容

（3）程序描述里的哪些部分对于找到系统设计时可能的方法最有帮助？（　　）

　a．形容词

　b．名词

　c．动词

　d．以上所有内容

（4）如何分辨方法里的实例变量和本地变量？（　　）

　a．实例变量是特定对象的数据的一部分，并且在多个方法里都是必需的，而本地变量仅仅在该方法里被需要

　b．一个类应该永远不使用本地变量，方法中使用的所有变量都应该是实例变量

　c．一个类应该永远不使用实例变量，方法中使用的所有变量都应该是本地变量

　d．实例变量只应该被用于常量

（5）如果你正在检查其他人编写的Python类，你应该如何确定一个变量是本地变量还是实例变量？（　　）

　a．在多个方法里都使用了相同的变量名

　b．在变量名前前置self.来访问这个变量

　c．在__init__方法里用到的变量

　d．实例变量总是以下划线开头

（6）在什么时候应该使用类变量？（　　）

　a．当类的每个实例都需要自己的数据副本时

　b．当类的每个实例可以共享相同的数据副本时

　c．数据是个常量时

　d．选项b和c

（7）如果需要设计一个表示多项式的类，以下哪个应该是实例变量？（　　）

　a．系数

　b．用于多项式计算的值

　c．多项式依照某个特定值计算出的结果

　d．以上所有内容

（8）如果需要设计一个表示多项式的类，以下哪个应该是类变量？（　　）

　a．系数

　b．用于多项式计算的值

　c．多项式依照某个特定值计算出的结果

　d．以上都不是

（9）在使用Python的unittest框架编写单元测试时，测试代码的编写会？（　　）

　a．有许多功能

　b．有一个单独的类，它是你的类的子类

　c．有一个单独的类，它继承自unittest.TestCase

　d．属于正在被测试的类的一部分

（10）单元测试的目的是什么？（　　）

　a．帮助你思考你的设计

　b．帮助你在代码中发现错误

　c．允许你在每次修改代码时轻松地测试代码

　d．以上所有内容

3．简答题

（1）类的接口和类的实现有什么区别？

（2）在编写类的代码之前编写单元测试代码的原因是什么？

（3）在编写类的代码时同时编写单元测试代码的原因是什么？

（4）在编写类的代码之后编写单元测试代码的原因是什么？

（5）如果实例变量和方法使用了相同的名称，Python会怎么处理？写一个简短的例子来试试吧。

（6）为模拟一整套扑克牌的Deck类提供两个不同的规范（列出各个实例变量和方法名称，但不用实现方法），包括模拟纸牌游戏所需要使用的各个方法。

（7）在一个玩tic-tac-toe的程序里，哪个类或哪些类可能会有用？你的类应该包含哪些实例变量和哪些方法？

（8）编写单元测试有什么好处？

（9）运算符重载的目的是什么？

4．编程练习

（1）编写2.3节里的扑克牌（Card）类的单元测试代码。

（2）使用2.3.3小节里讨论的另一种存储方式来实现扑克牌（Card）类。用上一个练习里的单元测试来对其进行测试。

（3）写一个扑克牌组的简单实现来随机发牌。这个扑克牌组（Deck）类应该包含一个扑克牌对象的列表。一开始的时候，扑克牌组里会包含52张可能的扑克牌的实例。你的扑克牌组应该实现一个叫作deal的方法，它会从列表中选择一个随机位置并“弹出”这张扑克牌。你还应该实现一个叫作cardsLeft的方法，这个方法可以告知牌组里剩下的牌数。要注意：在第3章里，我们实现了一个更复杂的Deck类，不要直接使用那个设计。

（4）使用上一个练习中的扑克牌组（Deck）类，编写一个让两个玩家玩二十一点的程序。

（5）使用练习3里的扑克牌组（Deck）类，编写一个简单的玩单人纸牌游戏的程序。游戏首先从扑克牌组面朝上地发出几张扑克牌。之后，如果有两张牌具有相同的数字，则从牌组里再面朝上发出另外两张牌。重复这一过程，直到所有的牌都被发出，或者不再有相同数字的扑克牌。如果已经发出了所有牌，则玩家“获胜”。你的程序应该能够让用户选择游戏开始时的牌数，然后模拟整个过程直到游戏结束。

（6）修改上一个练习，从而计算任何给定数量的牌数的获胜概率。

（7）使用本章里建议的两个具体存储方法来各自实现一个DataSet类。需要包含测试所有方法的代码。

（8）编写这样一个程序，它能够让两个玩家在计算机上玩奥赛罗棋（也称为黑白棋）游戏。如果你对这个游戏并不熟悉，你可以上网搜索相关的游戏规则。你可以通过创建这样一个类来设计你的程序：这个类能够用来记录棋盘上的各个棋子，并提供判断这一步棋是否合法的方法，根据合法的棋步来更新棋盘，以及以文本或图形方式来显示棋盘。同时，这个类还应该提供一个用于确定棋盘上每个位置的棋子的方法。

（9）为你的奥赛罗棋/黑白棋类编写单元测试，从而测试检查合法的棋步的方法以及能否根据合法的棋步来更新棋盘。

（10）完成有理数（Rational）类，使得它能够支持加号运算符、减号运算符、除法运算符和6个比较运算符，并且编写单元测试类来测试所有方法。在这里，比较运算符应返回True或False。如果你能够让你的类始终以简化形式存储分数的话，可以获得奖励积分。［提示：在类的构造函数里使用欧几里德的最大公约数（Euclid’s GCD）算法。］

（11）用有理数（Rational）类来编写一个理解古埃及分数的程序。古埃及分数是不同的单位分数（也就是分子为1，分母为各不相同的正整数）的和。比如可以被表示为这样的和：。你的程序要能够让用户输入任意分数，然后输出相应的古埃及分数。你可以先进行一些研究来找出相应的转换算法。

（12）编写一个类来表示多项式。这个类应该保存一个系数的列表以及多项式的次数。编写相应的加法、减法和乘法方法。编写__str__方法来以字符串的形式返回多项式。再提供一个方法来计算在某个特定值处的多项式的结果。同时，为这个多项式类编写相应的单元测试。

[1]　Python 3.0已经移除了对经典类的支持，因此类的头部定义将只能用新式类。

[2]　在实例变量名中使用前导下划线是一种通常的约定，这样做会将它们“标记”为实例变量，从而防止它们与名字类似的方法（max方法，vs._max实例变量）产生冲突。

[3]　在Python 3.0中，单斜杠（/）是浮点除法，而双斜杠（//）则用于整数除法。


相关图书

深度学习的数学——使用Python语言
深度学习的数学——使用Python语言
动手学自然语言处理
动手学自然语言处理
Python高性能编程（第2版）
Python高性能编程（第2版）
图像处理与计算机视觉实践——基于OpenCV和Python
图像处理与计算机视觉实践——基于OpenCV和Python
Python数据科学实战
Python数据科学实战
Web应用安全
Web应用安全

相关文章

相关课程

异步社区-致力于优质IT知识的出版和分享

京ICP备05035396号-6

京公网安备11010602100305号

增值电信业务经营许可证（京B2-20201559）Powered by 人民邮电出版社▪出版云