数据结构与算法分析张琨PDF_这样理解计算机科学，有趣多了！//Python数据结构与算法分析...

自从第一台利用转接线和开关来传递计算指令的电子计算机诞生以来，人们对编程的认识历经了多次变化。与社会生活的其他许多方面一样，计算机技术的变革为计算机科学家提供了越来越多的工具和平台去施展他们的才能。高效的处理器、高速网络以及大容量内存等一系列新技术，要求计算机科学家掌握更多复杂的知识。然而，在这一系列快速的变革之中，仍有一些基本原则始终保持不变。

计算机科学被认为是一门利用计算机来解决问题的学科。

你肯定在学习解决问题的基本方法上投入过大量的时间，并且相信自己拥有根据问题描述构建解决方案的能力。你肯定也体会到了编写计算机程序的困难之处。大型难题及其解决方案的复杂性往往会掩盖问题解决过程的核心思想。

本文会复习计算机科学以及数据结构与算法的研究必须符合的框架，尤其是学习这些内容的原因以及为什么说理解它们有助于更好地解决问题。

何谓计算机科学

要定义计算机科学，通常十分困难，这也许是因为其中的“计算机”一词。你可能已经意识到，计算机科学并不仅是研究计算机本身。尽管计算机在这一学科中是非常重要的工具，但也仅仅只是工具而已。

计算机科学的研究对象是问题、解决问题的过程，以及通过该过程得到的解决方案。给定一个问题，计算机科学家的目标是开发一个能够逐步解决该问题的算法。算法是具有有限步骤的过程，依照这个过程便能解决问题。因此，算法就是解决方案。

可以认为计算机科学就是研究算法的学科。但是必须注意，某些问题并没有解决方案。对于学习计算机科学的人来说，认清这一事实非常重要。结合上述两类问题，可以将计算机科学更完善地定义为：研究问题及其解决方案，以及研究目前无解的问题的学科。

在描述问题及其解决方案时，经常用到“可计算”一词。若存在能够解决某个问题的算法，那么该问题便是可计算的。因此，计算机科学也可以被定义为：研究可计算以及不可计算的问题，即研究算法的存在性以及不存在性。在上述任意一种定义中，“计算机”一词都没有出现。解决方案本身是独立于计算机的。

在研究问题解决过程的同时，计算机科学也研究抽象。抽象思维使得我们能分别从逻辑视角和物理视角来看待问题及其解决方案。举一个常见的例子。

试想你每天开车去上学或上班。作为车的使用者，你在驾驶时会与它有一系列的交互：坐进车里，插入钥匙，启动发动机，换挡，刹车，加速以及操作方向盘。从抽象的角度来看，这是从逻辑视角来看待这辆车，你在使用由汽车设计者提供的功能来将自己从某个地方运送到另一个地方。这些功能有时候也被称作接口。

另一方面，修车工看待车辆的角度与司机截然不同。他不仅需要知道如何驾驶，而且更需要知道实现汽车功能的所有细节：发动机如何工作，变速器如何换挡，如何控制温度，等等。这就是所谓的物理视角，即看到表面之下的实现细节。

使用计算机也是如此。大多数人用计算机来写文档、收发邮件、浏览网页、听音乐、存储图像以及打游戏，但他们并不需要了解这些功能的实现细节。大家都是从逻辑视角或者使用者的角度来看待计算机。计算机科学家、程序员、技术支持人员以及系统管理员则从另一个角度来看待计算机。他们必须知道操作系统的原理、网络协议的配置，以及如何编写各种脚本来控制计算机。他们必须能够控制用户不需要了解的底层细节。

上面两个例子的共同点在于，抽象的用户(或称客户)只需要知道接口是如何工作的，而并不需要知道实现细节。这些接口是用户用于与底层复杂的实现进行交互的方式。下面是抽象的另一个例子，来看看Python 的math 模块。一旦导入这一模块，便可以进行如下的计算。

>>> import math>>> math.sqrt(16)4.0>>>

这是一个过程抽象的例子。我们并不需要知道平方根究竟是如何计算出来的，而只需要知道计算平方根的函数名是什么以及如何使用它。只要正确地导入模块，便可以认为这个函数会返回正确的结果。由于其他人已经实现了平方根问题的解决方案，因此我们只需要知道如何使用该函数即可。这有时候也被称为过程的“黑盒”视角。我们仅需要描述接口：函数名、所需参数，以及返回值。所有的计算细节都被隐藏了起来，如图1 所示。

何谓编程

编程是指通过编程语言将算法编码以使其能被计算机执行的过程。尽管有众多的编程语言和不同类型的计算机，但是首先得有一个解决问题的算法。如果没有算法，就不会有程序。

计算机科学的研究对象并不是编程。但是，编程是计算机科学家所做工作的一个重要组成部分。通常，编程就是为解决方案创造表达方式。因此，编程语言对算法的表达以及创造程序的过程是这一学科的基础。

通过定义表达问题实例所需的数据，以及得到预期结果所需的计算步骤，算法描述出了问题的解决方案。编程语言必须提供一种标记方式，用于表达过程和数据。为此，编程语言提供了众多的控制语句和数据类型。

控制语句使算法步骤能够以一种方便且明确的方式表达出来。算法至少需要能够进行顺序执行、决策分支、循环迭代的控制语句。只要一种编程语言能够提供这些基本的控制语句，它就能够被用于描述算法。

计算机中的所有数据实例均由二进制字符串来表达。为了赋予这些数据实际的意义，必须要有数据类型。数据类型能够帮助我们解读二进制数据的含义，从而使我们能从待解决问题的角度来看待数据。这些內建的底层数据类型(又称原生数据类型)提供了算法开发的基本单元。

举例来说，大部分编程语言都为整数提供了相应的数据类型。根据整数(如23、654 以及–19)的常见定义，计算机内存中的二进制字符串可以被理解成整数。除此以外，数据类型也描述了该类数据能参与的所有运算。对于整数来说，就有加减乘除等常见运算。并且，对于数值类型的数据，以上运算均成立。

我们经常遇到的困难是，问题及其解决方案都过于复杂。尽管由编程语言提供的简单的控制语句和数据类型能够表达复杂的解决方案，但它们在解决问题的过程中仍然存在不足。因此，我们需要想办法控制复杂度以利于找到解决方案。

为何学习数据结构及抽象数据类型

为了控制问题及其求解过程的复杂度，计算机科学家利用抽象来帮助自己专注于全局，从而避免迷失在众多细节中。通过对问题进行建模，可以更高效地解决问题。模型可以帮助计算机科学家更一致地描述算法要用到的数据。

如前所述，过程抽象将功能的实现细节隐藏起来，从而使用户能从更高的视角来看待功能。数据抽象的基本思想与此类似。抽象数据类型(有时简称为ADT)从逻辑上描述了如何看待数据及其对应运算而无须考虑具体实现。这意味着我们仅需要关心数据代表了什么，而可以忽略它们的构建方式。通过这样的抽象，我们对数据进行了一层封装，其基本思想是封装具体的实现细节，使它们对用户不可见，这被称为信息隐藏。

图2 展示了抽象数据类型及其原理。用户通过利用抽象数据类型提供的操作来与接口交互。抽象数据类型是与用户交互的外壳。真正的实现则隐藏在内部。用户并不需要关心各种实现细节。

抽象数据类型的实现常被称为数据结构，这需要我们通过编程语言的语法结构和原生数据类型从物理视角看待数据。正如之前讨论的，分成这两种不同的视角有助于为问题定义复杂的数据模型，而无须考虑模型的实现细节。这便提供了一个独立于实现的数据视角。由于实现抽象数据类型通常会有很多种方法，因此独立于实现的数据视角使程序员能够改变实现细节而不影响用户与数据的实际交互。用户能够始终专注于解决问题。

为何学习算法

计算机科学家通过经验来学习：观察他人如何解决问题，然后亲自解决问题。接触各种问题解决技巧并学习不同算法的设计方法，有助于解决新的问题。通过学习一系列不同的算法，可以举一反三，从而在遇到类似的问题时，能够快速加以解决。

各种算法之间往往差异巨大。回想前文提到的平方根的例子，完全可能有多种方法来实现计算平方根的函数。算法一可能使用了较少的资源，算法二返回结果所需的时间可能是算法一的10 倍。我们需要某种方式来比较这两种算法。尽管这两种算法都能得到结果，但是其中一种可能比另一种“更好”——更高效、更快，或者使用的内存更少。随着对算法的进一步学习，你会掌握比较不同算法的分析技巧。这些技巧只依赖于算法本身的特性，而不依赖于程序或者实现算法的计算机的特性。

最坏的情况是遇到难以解决的问题，即没有算法能够在合理的时间内解决该问题。因此，至关重要的一点是，要能区分有解的问题、无解的问题，以及虽然有解但是需要过多的资源和时间来求解的问题。

在选择算法时，经常会有所权衡。除了有解决问题的能力之外，计算机科学家也需要知晓如何评估一个解决方案。总之，问题通常有很多解决方案，如何找到一个解决方案并且确定其为优秀的方案，是需要反复练习、熟能生巧的。

Python例子

下面我们将复习Python，并且为前面提到的思想提供更详细的例子。如果你刚开始学习Python或者觉得自己需要更多的信息，建议你查看《Python数据结构与算法分析(第2版)》结尾列出的Python 资源。

Python 是一门现代、易学、面向对象的编程语言。它拥有强大的內建数据类型以及简单易用的控制语句。由于Python 是一门解释型语言，因此只需要查看和描述交互式会话就能进行学习。

你应该记得，解释器会显示提示符>>>，然后计算你提供的Python 语句。例如，以下代码显示了提示符、print 函数、结果，以及下一个提示符。

>>> print("Algorithms and Data Structures")>>> Algorithms and Data Structures>>>

一、数据

前面提到，Python 支持面向对象编程范式。这意味着Python 认为数据是问题解决过程中的关键点。在Python 以及其他所有面向对象编程语言中，类都是对数据的构成(状态)以及数据能做什么(行为)的描述。由于类的使用者只能看到数据项的状态和行为，因此类与抽象数据类型是相似的。在面向对象编程范式中，数据项被称作对象。一个对象就是类的一个实例。

1. 内建原子数据类型

我们首先复习原子数据类型。Python 有两大內建数据类实现了整数类型和浮点数类型，相应的Python 类就是int 和float。标准的数学运算符，即+、-、*、/以及**(幂)，可以和能够改变运算优先级的括号一起使用。其他非常有用的运算符包括取余(取模)运算符%，以及整除运算符//。注意，当两个整数相除时，其结果是一个浮点数，而整除运算符截去小数部分，只返回商的整数部分。

>>> 2+3*414>>> (2+3)*420>>> 2**101024>>> 6/32.0>>> 7/32.3333333333333335>>> 7//32>>> 7%31>>> 3/60.5>>> 3//60>>> 3%63>>> 2**1001267650600228229401496703205376>>>

Python 通过bool 类实现对表达真值非常有用的布尔数据类型。布尔对象可能的状态值是True 或者False，布尔运算符有and、or 以及not。

>>> TrueTrue>>> FalseFalse>>> False or TrueTrue>>> not (False or True)False>>> True and TrueTrue

布尔对象也被用作相等(==)、大于(>)等比较运算符的计算结果。此外，结合使用关系运算符与逻辑运算符可以表达复杂的逻辑问题。表1-1 展示了关系运算符和逻辑运算符。

>>> 5 == 10False>>> 10 > 5True>>> (5 >= 1) and (5 <= 10)True

标识符在编程语言中被用作名字。Python 中的标识符以字母或者下划线(_)开头，区分大小写，可以是任意长度。需要记住的一点是，采用能表达含义的名字是良好的编程习惯，这使程序代码更易阅读和理解。

当一个名字第一次出现在赋值语句的左边部分时，会创建对应的Python 变量。赋值语句将名字与值关联起来。变量存的是指向数据的引用，而不是数据本身。来看看下面的代码。

>>> theSum = 0>>> theSum0>>> theSum = theSum + 1>>> theSum1>>> theSum = True>>> theSumTrue

赋值语句theSum = 0 会创建变量theSum，并且令其保存指向数据对象0 的引用(如图3 所示)。Python 会先计算赋值运算符右边的表达式，然后将指向该结果数据对象的引用赋给左边的变量名。在本例中，由于theSum 当前指向的数据是整数类型，因此该变量类型为整型。如果数据的类型发生改变(如图4 所示)，正如上面的代码给theSum 赋值True，那么变量的类型也会变成布尔类型。赋值语句改变了变量的引用，这体现了Python 的动态特性。同样的变量可以指向许多不同类型的数据。

2. 内建集合数据类型

除了数值类和布尔类，Python 还有众多强大的內建集合类。列表、字符串以及元组是概念上非常相似的有序集合，但是只有理解它们的差别，才能正确运用。集(set)和字典是无序集合。

列表是零个或多个指向Python 数据对象的引用的有序集合，通过在方括号内以逗号分隔的一系列值来表达。空列表就是[]。列表是异构的，这意味着其指向的数据对象不需要都是同一个类，并且这一集合可以被赋值给一个变量。下面的代码段展示了列表含有多个不同的Python 数据对象。

>>> [1,3,True,6.5][1, 3, True, 6.5]>>> myList = [1,3,True,6.5]>>> myList[1, 3, True, 6.5]

注意，当Python 计算一个列表时，这个列表自己会被返回。然而，为了记住该列表以便后续处理，其引用需要被赋给一个变量。

由于列表是有序的，因此它支持一系列可应用于任意Python 序列的运算，如表1-2 所示。

需要注意的是，列表和序列的下标从0 开始。myList[1:3]会返回一个包含下标从1 到2的元素列表(并没有包含下标为3 的元素)。

如果需要快速初始化列表，可以通过重复运算来实现，如下所示。

>>> myList = [0] * 6>>> myList[0, 0, 0, 0, 0, 0]

非常重要的一点是，重复运算返回的结果是序列中指向数据对象的引用的重复。下面的例子可以很好地说明这一点。

>>> myList = [1,2,3,4]>>> A = [myList]*3>>> A[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]>>> myList[2] = 45>>> A[[1, 2, 45, 4], [1, 2, 45, 4], [1, 2, 45, 4]]>>>

变量A 包含3 个指向myList 的引用。myList 中的一个元素发生改变，A 中的3 处都随即改变。

列表支持一些用于构建数据结构的方法，如表1-3 所示。后面的例子展示了用法。

>>> myList[1024, 3, True, 6.5]>>> myList.append(False)>>> myList[1024, 3, True, 6.5, False]>>> myList.insert(2,4.5)>>> myList[1024, 3, 4.5, True, 6.5, False]>>> myList.pop()False>>> myList[1024, 3, 4.5, True, 6.5]>>> myList.pop(1)3>>> myList[1024, 4.5, True, 6.5]>>> myList.pop(2)True>>> myList[1024, 4.5, 6.5]>>> myList.sort()>>> myList[4.5, 6.5, 1024]>>> myList.reverse()>>> myList[1024, 6.5, 4.5]>>> myList.count(6.5)1>>> myList.index(4.5)2>>> myList.remove(6.5)>>> myList[1024, 4.5]>>> del myList[0]>>> myList[4.5]

你会发现，像pop 这样的方法在返回值的同时也会修改列表的内容，reverse 等方法则仅修改列表而不返回任何值。pop 默认返回并删除列表的最后一个元素，但是也可以用来返回并删除特定的元素。这些方法默认下标从0 开始。你也会注意到那个熟悉的句点符号，它被用来调用某个对象的方法。myList.append(False)可以读作“请求myList 调用其append 方法并将False 这一值传给它”。就连整数这类简单的数据对象都能通过这种方式调用方法。

>>> (54).__add__(21)75>>>

在上面的代码中，我们请求整数对象54 执行其add 方法(该方法在Python 中被称为__add__)，并且将21 作为要加的值传给它。其结果是两数之和，即75。我们通常会将其写作54+21。稍后会更多地讨论这些方法。

range 是一个常见的Python 函数，我们常把它与列表放在一起讨论。range 会生成一个代表值序列的范围对象。使用list 函数，能够以列表形式看到范围对象的值。下面的代码展示了这一点。

>>> range(10)range(0, 10)>>> list(range(10))[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>>> range(5,10)range(5, 10)>>> list(range(5,10))[5, 6, 7, 8, 9]>>> list(range(5,10,2))[5, 7, 9]>>> list(range(10,1,-1))[10, 9, 8, 7, 6, 5, 4, 3, 2]>>>

范围对象表示整数序列。默认情况下，它从0 开始。如果提供更多的参数，它可以在特定的点开始和结束，并且跳过中间的值。在第一个例子中，range(10)从0 开始并且一直到9 为止(不包含10)；在第二个例子中，range(5,10)从5 开始并且到9 为止(不包含10)；range(5,10,2)的结果类似，但是元素的间隔变成了2(10 还是没有包含在其中)。

字符串是零个或多个字母、数字和其他符号的有序集合。这些字母、数字和其他符号被称为字符。常量字符串值通过引号(单引号或者双引号均可)与标识符进行区分。

>>> "David"'David'>>> myName = "David">>> myName[3]'i'>>> myName*2'DavidDavid'>>> len(myName)5>>>

由于字符串是序列，因此之前提到的所有序列运算符都能用于字符串。此外，字符串还有一些特有的方法，表1-4 列举了其中一些。

>>> myName'David'>>> myName.upper()'DAVID'>>> myName.center(10)' David '>>> myName.find('v')2>>> myName.split('v')['Da', 'id']

split 在处理数据的时候非常有用。split 接受一个字符串，并且返回一个由分隔字符作为分割点的字符串列表。在本例中，v 就是分割点。如果没有提供分隔字符，那么split 方法将会寻找如制表符、换行符和空格等空白字符。

列表和字符串的主要区别在于，列表能够被修改，字符串则不能。列表的这一特性被称为可修改性。列表具有可修改性，字符串则不具有。例如，可以通过使用下标和赋值操作来修改列表中的一个元素，但是字符串不允许这一改动。

>>> myList[1, 3, True, 6.5]>>> myList[0]=2**10>>> myList[1024, 3, True, 6.5]>>>>>> myName'David'>>> myName[0]='X'Traceback (most recent call last):File "