《数据结构与算法:Python语言描述》一1.4数据结构-阿里云开发者社区

开发者社区> 华章出版社> 正文
登录阅读全文

《数据结构与算法:Python语言描述》一1.4数据结构

简介:

本节书摘来自华章出版社《数据结构与算法:Python语言描述》一书中的第1章,第1.4节,作者 裘宗燕,更多章节内容可以访问云栖社区“华章计算机”公众号查看

1.4数据结构

从程序输入和输出的角度看,用计算机解决问题,可以看作实现某种信息表示形式的转换。如图1.5所示,把以一种形式表示的信息(输入)送给程序,通过在计算机上运行程序,产生出以另一种形式表示的信息(输出)。如果:

具体的“信息表示A”表达了需要求解的某个问题的实例。
得到的“信息表示B”表达了与这个实例对应的求解结果。
那么就可以认为,这个程序完成了该问题实例的求解工作。
为了能用计算机处理与问题有关的信息,就必须采用某种方式表示它,并将相应表示送入计算机。信息通过表示就变成了(计算机处理的)数据。与问题有关的信息可能很复杂,不仅是可能数量庞大,而且信息之间可能存在错综复杂的相互联系。为了能在计算中有效处理,必须以适当的形式把蕴涵了这些信息的数据组织好。需要处理的信息的情况越复杂,处理过程(计算过程)越复杂,数据的良好组织就越重要。


193b6c540281f9dc4cf7cff81806130aa4b90a75

1.4.1数据结构及其分类

这里首先简单介绍几个概念,而后介绍数据结构的一些情况。
信息、数据和数据结构
信息是目前在生活和工作中最经常听到的一个词汇,人们都说今天已经进入信息时代。但是,要想给信息这个概念一个容易理解的确切定义却并不容易。直观地看,任何存在着的事物,其形态和运动都蕴涵着信息,人的思想和行为也产生信息。人们希望用计算机处理的终极对象就是客观存在的各种信息,因此说计算机是处理信息的工具。计算机本质上具有与人类发明的其他工具截然不同的性质。
显然,要用计算机处理信息,首先必须把信息转变成为计算机能处理的形式。这种转换可能由人完成,也可能通过一些物理设备完成。例如,数字照相机把一个客观场景转换为一幅数字化的图像;数字麦克风把一段声音转换成某种编码的一串数字信号;人通过敲击键盘把一段演讲记录下来变成一段标准编码的文本串;通过光学扫描和文字识别,也可以把纸张上的印刷文本转变为计算机可以处理的编码文本形式。
在计算机科学技术领域,数据(data)就是指计算机(程序)能够处理的符号形式的总和,或说是经过了编码的信息(信息的编码表示)。
在讨论计算机处理时,经常要提到数据元素(data element),用于指最基本的数据单位。在计算机硬件层面,所有被存储和处理的数据最终都编码为二进制代码形式。一切数据最终都表现为二进制位的序列,最基本的数据元素就是一个二进制位。但在计算机应用的各个层面上,数据可能具有更加丰富多彩的表现形式,这时说一个数据元素就是指在当前的上下文中作为整体保存和处理的一个数据单元。
实际中需要处理的通常都不是单个数据元素,而是或多或少的一组数据元素。另一方面,这些元素通常也不是独立的互不相关的个体,它们相互之间经常有各种联系。一批数据元素和它们之间的联系一起,反映了需要处理的问题的相关信息。
数据结构(data structure)研究数据之间的关联和组合的形式,总结其中的规律性,发掘特别值得注意的有用结构,研究这些结构的性质,进而研究如何在计算机里实现这些有用的数据结构,以支持相应组合数据的高效使用,支持处理它们的高效算法。在考虑数据结构时,其数据元素作为原子性的单元,可以任意简单或复杂,没有任何限制。
抽象定义与重要类别
首先抽象地考虑数据结构的概念。从逻辑上看,一个数据结构包含一集数据元素,是一个有穷集,在这些元素之间有着某些特定的逻辑关系。按照这种观点抽象地看,一个具体的数据结构就是一个二元组
image

其中的E是数据结构D的元素集合,是某个数据集合 的一个有穷子集,而RE×E是D的元素之间的某种关系。对于不同种类的数据结构,其元素之间的关系具有不同性质。
这个定义非常一般,对于关系R没有任何限制。人们对实际中常用的数据结构做了一些梳理,总结出一批特别有用的典型数据结构,主要有:
集合结构:其数据元素之间没有需要关注的明确关系,也就是说关系R是空集。这样的数据结构也就是其元素的集合,只是把一组数据元素包装为一个整体。这是最简单的一类数据结构。
序列结构:其数据元素之间有一种明确的先后关系(顺序关系)。存在一个排位在最前的元素,除了最后的元素外,每个元素都有一个唯一的后继元素,所有元素排列成一个线性序列。关系R就是这里的线性顺序关系。这种结构也称为线性结构,一个这样的复杂数据对象就是一个序列对象。序列结构还有一些变形,如环形结构和形结构。其特点是每个元素只有(最多)一个后继,如图1.6所示。图中的小圆圈表示数据元素,箭头表示元素之间的关系,说明这种关系是有方向的。
层次结构:其数据元素分属于一些不同的层次,一个上层元素可以关联着一个或者多个下层元素,关系R形成一种明确的层次性,只从上层到下层(通常也允许跨层次)。层次关系又可以分为许多简单或复杂的子类别。
树形结构:层次结构中最简单的一种关系是树形关系,其特点是在一个树形结构中只有一个最上层数据元素,称为根,其余元素都是根的直接或间接关联的下层元素。进一步说,除根元素之外的每个元素,都有且仅有一个上层元素与之关联。树形数据结构简称为树,相应的复杂数据对象称为树形对象。第6章将详细讨论这类结构。树形结构的图示见6.1节和6.7节。
图结构:数据元素之间可以有任意复杂的相互联系。数学领域中的图概念是这类复杂结构的抽象,因此人们把这样的结构称为图结构,把这样的复杂对象称为图对象。第7章将详细讨论图结构。
实际上,可以认为图结构包含了前面几类结构,把那些结构看作图的受限形式。由于其中元素之间的关系受限,可能存在一些有意义的特殊性质。


69efbebd160ca58b493af93121ca28ac80c4c174

算法和程序中的数据结构
抽象的数据结构可以从逻辑结构的角度分析和研究,但人们考虑更多的是用这些结构表现计算机需要处理的信息的特征、存储相关的信息及其内在联系。因此需要研究在面向实用时,各种数据结构表现出的性质和产生的问题。
用数据结构存储信息,不仅要考虑如何把抽象的数据结构映射到计算机或程序可以表达和操作的数据存储形式,还要考虑作用于具体数据结构的各种操作,如结构的建立、其中元素的访问、插入或删除元素等一般性操作。在实际应用中,经常还需要考虑一些面向具体应用问题的特殊操作。
数据结构上的操作需要通过算法实现。对复杂的数据结构,如树结构和图结构,存在许多非常有趣而且有用的算法。图算法已经发展成为算法领域的一个重要分支。在后面章节里讨论某种数据结构时,将介绍该结构上的一些重要算法。
在程序中使用一种数据结构,需要把这种结构映射到编程语言提供的基本数据机制,或者说是用编程语言的数据机制实现所需的数据结构。这一映射称为(抽象)数据结构的物理实现。编程语言系统(编译器或解释器)将把通过语言的数据机制定义的数据结构映射到计算机存储器中。前一层映射由设计和实现程序的人完成,良好的设计能为相应算法的实现提供更好的支持。后一层映射由编程语言的编译器或解释器完成,实际上是由设计和实现解释器/编译器的人们做出的选择。底层实现牵涉到有效利用计算机的存储器,上层实现牵涉到有效利用语言提供的各种数据机制。本章最后几小节将介绍这两方面的一些基本情况,第2章介绍抽象数据类型的思想和Python中与此相关的重要机制,后面各章在抽象地讨论某种数据结构后,都会讨论其Python实现问题。
结构性和功能性的数据结构
前面介绍了数据结构的概念,列举了一些计算中常用的数据结构,如线性结构、树结构和图结构。这些数据结构都对其数据元素之间的相互关系做出了一些规定,元素之间确实满足某种关系才能被称为线性结构或树结构等。也就是说,这些数据结构的最重要特征就是它们的结构,因此本书中将称它们为结构性的数据结构。
本书中还将讨论另一类数据结构,它们并没有对其元素的相互关系提出任何结构性的规定,而是要求实现某种计算中非常有用的功能。作为可以包含一批数据元素的结构,最基本的要求就是支持元素的存储和使用(使用也常称为元素访问)。这个基本要求实际上是功能性的要求,而非结构性的要求,因为它完全不涉及元素如何存储、元素之间如何关联。支持元素存储和访问的数据结构被称为容器。人们已经开发出许多不同的容器数据结构,它们各有一些功能方面的特点,是本书讨论的另一部分数据结构。
在下面讨论中,涉及的功能性数据结构包括栈、队列、优先队列、字典等。这些结构都支持以某一套方式存储和访问元素(包括删除元素),但不同结构提供了不同的元素访问特性,其具体操作表现出各自的特性,这些特性在抽象算法和实际程序里都非常重要。这些功能性数据结构的使用非常广泛。
由于只有功能要求,这类数据结构可以采用任何技术实现。实际中人们通常首先把这类结构映射到某种结构性的数据结构,而后采用相应的实现技术。有时也开发一些专门的实现技术。对这类数据结构的讨论主要在第5章和第8章。
本节剩下部分将集中关注数据结构的实现问题。下面将介绍计算机存储器的基本情况、一般编程语言中数据存储和组织的情况,进而简单综述Python语言的这方面功能。了解这些情况,有助于理解后面各章的内容。

1.4.2计算机内存对象表示

为了理解数据结构的性质,理解数据结构实现和处理中的基本问题,需要对计算机内存结构和计算机存储管理方面的情况有所了解。本小节介绍这方面情况。
内存单元和地址
计算中(程序中)直接使用的数据保存在计算机的内存储器(简称内存)。内存是CPU可以直接访问的数据存储设备。与之相对应的是外存储器,简称外存,如磁盘、光盘、磁带等。保存在外存里的数据必须先装入内存,而后CPU才能使用它们。
内存的基本结构是线性排列的一批存储单元。每个单元的大小相同,可以保存一个单位大小的数据。具体单元大小可能因计算机的不同而有所不同。在目前最常见的计算机中,一个单元可以保存一个字节(8位二进制代码)的数据。因此存放一个整数或者浮点数,需要连续的几个单元。例如标准的浮点数需要8个单元。
内存单元具有唯一编号,称为单元地址,或简称地址。单元地址从0开始连续排列,全部可用地址为从0开始的一个连续的正整数区间,如图1.7所示。
在程序执行中,对内存单元的访问(存取其中数据)都通过单元的地址进行,因此,要访问一个单元,必须先掌握其地址。在许多计算机中,一次内存访问可以存取若干单元的内容。例如目前常见的64位计算机,一次可以存取8个字节的数据,也就是说一次操作访问8个单元的内容。基于地址访问内存单元是一个O(1)操作,与单元的位置或整个内存的大小无关,这是分析与数据结构有关的算法时的一个基本假设。在高级语言层面讨论和分析数据结构问题时,人们通常不关心具体的单元大小或地址范围,只假定所考虑数据保存在内存的某处,而且假定这种访问是常量时间的。


8aa711c22d21a2906acbc74be063ca065e5c1a15

对象存储和管理
在程序运行中,可能需要构造、使用、处理各种各样的对象,它们都将在计算机的线性结构的内存里安排位置。为了表示程序中的一个对象,需要根据情况,在当时空闲的内存中确定一块或几块区域(内存区域指地址连续排列的一个或一些内存单元),把该对象的数据存入其中。在Python程序运行中,建立对象时需要安排存储,还有许多与对象存储和使用有关的管理工作。解释器的一个专门子系统(称为存储管理系统)负责这些工作。这一工作是自动进行的,编写程序的人不必关心。另外,当一个对象不再有用时,存储管理系统也会设法回收其占用的存储,以便在将来用于存储其他对象。
一个程序在运行中将不断建立一些对象并使用它们。建立的每个对象都有一个确定的唯一标识,用于识别和使用这个对象。在一个对象的存续期间,其标识保持不变,这也是一个基本原则。例如,Python标准函数id取得对象的标识,内置操作is和is not通过比较标识的方式判断是否为同一个对象。在具体系统里用什么作为对象标识,是系统设计者的考虑和选择。最简单的方式就是直接使用对象的存储位置(内存地址)。这显然是一种唯一标识,因为不会有两个不同对象存放在同一个存储位置。
对象的访问
在编程语言层面,知道了一个对象的标识就可以直接访问(使用)它。已知对象标识(无论它是否直接为对象地址),访问相应对象的操作可以直接映射到已知地址访问内存单元,这种操作可以在常量时间完成(是O(1)时间操作)。
如果被访问的是一个组合对象,其中包含了一组元素,这些元素被安排在一块内存区域(一块连续的元素存储区)里,而且每个元素的存储量相同。在这种情况下,可以给每个元素一个顺序编号(通常称为下标,index)。对这种组合对象,程序中经常需要访问它们的元素。如果知道了一个组合对象的元素存储区位置,又知道要访问的元素的编号,访问元素也是O(1)时间操作。这件事很容易证明:假设所关心的元素存储区的起始位置是内存地址p,每个元素占用a个内存单元。再假设元素序列中首元素的下标为0。要访问下标为k的元素,通过下式能立刻计算出该元素的位置loc(k):
image

有了元素位置就能直接访问该元素了。上述公式是统一的,只需做一次乘法和一次加法,所用时间与元素的下标无关,与组合对象中的元素个数也无关。
考虑另一种情况,假设某类组合对象都包含同样的一组元素,元素连续存放在一块存储区里,但不同元素的大小可能不同。进而,在同属这类的不同对象里,排在同样位置的元素的大小相同。进一步说,这类对象都采用同样存储方式。显然,在上面条件下,根据元素的排列顺序,可以事先算出这类对象里各元素在对象存储区中的相对位置,称为元素的存储偏移量。假设一个对象o的地址为p,o的元素ei的偏移量为ri,立即可以算出ei的地址为p+ri,有关情况参见图1.8(显然,e0的偏移量为0)。易见,在这种情况下,已知一个这种组合对象,访问其中元素的操作也可以在O(1)时间完成。
上面两种情况概括了数据结构中组合对象成分存储和访问操作的基本情况,解释了对象访问和对象元素访问的时间复杂度问题。在下面有关数据结构的讨论中,这两种操作很重要,也是对与数据结构有关的算法做复杂度分析的基础。


8a754dd4e9f19b99dc949a650f78cf6c0c502b87

对象关联的表示
基本类型数据(如字符、整数和浮点数)的内存表示方式由编程语言和计算机硬件确定,一项数据占据确定数目的几个连续单元,例如一个浮点数通常占连续的8个字节单元。
复杂数据对象(数据结构)包含了一批元素(数据成员),这些元素本身也是数据对象,可能是基本数据,也可能是具有较简单内部结构的复杂对象,元素间通常有某些联系。要表示这样的复杂结构,就需要表示两方面的信息:数据元素和元素之间的联系。具体元素的情况由对象的实际情况确定,元素之间的联系以及如何表示这些联系则是一般性的问题,是数据结构研究和实践中关注的主要问题。
在计算机内存里表示数据元素之间的联系,只有两种基本技术:
1)利用数据元素的存储位置隐式表示。由于内存是单元的线性序列,知道了前一个元素的位置及其大小(存储占用量),就能确定下一元素的位置。如果存储的是一系列大小相同的元素,就可以利用前面公式直接算出序列中任何一个元素的位置。显然,序列数据类型中元素的线性关系可以用这种方式表示。
2)把数据元素之间联系也看作一种数据,显式地保存在内存中。用这种方式可以表示数据元素之间任意复杂的关系,因此这种技术的功能更强大。
第一种方式称为元素的顺序表示:在一个内存存储块里保存复杂结构中的多个数据元素,整个结构的整体也是一个数据对象,可以统一地安排和管理。
这种方式的最典型例子之一是简单字符串。假设每个字符用一个字节存储,为了创建一个字符串,首先为需要存储的字符确定一块足够大的内存块,然后把这个字符串的内容复制进去,得到的情况如图1.9a所示。图中箭头表示这块内存的起始位置(即是该字符串的标识),由它出发可以找到并使用该字符串的内容,可以把它赋给变量或传给函数。
但是,实际上上述做法通常还不够。内存单元里存储的都是二进制编码,对于字符串而言,存储的就是各字符的编码。由于字符串长短不一,仅从一串单元里保存的内容无法判断这一字符串到哪里结束。为了解决这个问题,通常需要约定一种存储安排。对于字符串,一种可能的方式是在其存储块的开始,用一个确定大小的部分记录该字符串的实际长度,随后部分保存字符串的实际内容。如图1.9b所示。

image

这一做法结合了两个层次的表示:在上层看这是两项数据,一个整数表示字符串长度,紧接它的一块内存区域里保存字符串的内容;后一区域又是一系列单元,其中存储着字符串的各个字符。由于整数占用的内存单元数已知,根据前面讨论,知道了整个存储块的开始位置(对象标识),只需常量时间就能找到字符串里的任何一个字符。
这个例子说明,程序里使用的任何一种对象,即使简单如字符串,也需要设计一种合适的内存表示方式。要在程序中生成和处理任何对象,都需要设计好它们的存储方式。这种方式及其效果称为该对象的表示(representation)。图1.9及其讨论就说明了如何为字符串设计一种存储表示方式。如果需要自己从底层出发实现一类数据对象,第一件事就是为其确定一种表示方式,在C语言里写程序时经常需要做这种工作。在Python语言里,一些常用组合对象(包括字符串)已经有了现成的实现。由于其他人(Python系统开发者)已经做了这部分工作,用Python编程序的人可以坐享其成。
字符串的结构比较简单,可以用一块连续存储区表示,类似情况如数学里的n维向量,可以表示为n个浮点数的序列。此外,数学中的矩阵是数据的二维阵列,元素类型相同,也可以考虑采用连续存储的表示方式。但是,并非所有对象都如此。
假设现在需要为记录书籍的信息设计一种对象。有关书籍的信息包含两个成分:作者和书名。表示它的对象也应该有两个成员,而且这两个成员都是字符串。对不同的书籍,这两个成员字符串的长度显然可能不同。虽然可以把两个字符串存放在一起,采用某种特殊分隔符做成一个字符串,但那种表示使用不方便,也影响操作效率。
一种合理的表示方式如图1.10所示,采用三个独立部分的组合表示一个完整的书籍对象。首先是一个二元结构,它表示书籍对象的整体,另外两个独立的字符串分别表示书籍对象的两个成分。在二元结构里记录两个成分字符串的引用信息(记录两个字符串对象的标识),这就是前面说的表示数据元素之间联系的第二种技术。这样,掌握了这个二元结构,通过其中记录的数据关联就可以找到有关书籍的所有信息了。


66cb75dedc45bd53b18ed1b5154c5da595bdff9e

总结一下,这种表示技术是用一组独立的存储块(对象)表示一个复杂的数据对象,数据对象的成员用独立的成员对象表示,在一些块里记录与之相关的对象的关联信息(标识)。这种技术称为对象的链接表示技术,通过链接方式形成的复杂结构称为链接结构。链接技术经常被用来表示复杂的组合对象。图示中常用箭头表示对象间的关联,本书后面将一直这样做。关联是单向的,也称为链接或引用。
实际上,图1.10中出现的结构不仅仅是链接结构,作为书籍对象主体的二元结构本身又是一个连续表示的结构,这个结构包含了两个成分,其中记录了两个链接,它们的顺序位置确定了到哪里寻找作者信息、到哪里寻找书名。两个字符串对象都采用连续表示,整个对象又是由三个独立部分通过链接构成的。实际上,复杂数据对象的表示经常是连续结构和链接结构的组合,需要很好地结合这两种技术。
连续结构和链接结构是所有数据结构构造的基础。在后面章节里,读者将会看到如何基于这两种构造方式组合出一批最重要的数据结构。

1.4.3Python对象和数据结构

本书用Python作为编程语言讨论数据结构和算法的问题,这里简单概述Python语言中与数据表示有关的一些基本情况。在后面章节的讨论中,还将重点介绍Python的一些重要内置数据结构的实现和性质,以帮助读者更好地理解Python语言本身,并能在写程序时更好地使用它们,更好地思考(估计)其可能行为。
Python变量和对象
高级语言里的变量(全局变量、函数的局部变量和参数)是内存及其地址的抽象。变量本身也需要在内存中安排位置,每个变量占用若干存储单元。语言系统需要有一套系统化的安排方式处理这个问题,下面讨论中不考虑。为了理解程序的行为,只需要假定在程序运行中总能找到根据作用域可见的变量,取得或修改它们的值。
在Python程序里,可以通过初始化(或提供实参)给变量(或函数参数)约束一个值,还可以通过赋值修改变量的值。这里的值就是对象,给变量约束一个对象,就是把该对象的标识(内存位置)存入该变量。图1.11形象地表示了几个变量及其约束值的情况,其中右边云状图形表示内存,几个对象有各自的存储位置,箭头表示变量与其值的约束关系。图1.11中只画了几个简单类型的对象,复杂组合对象的情况也类似。从变量出发访问其值是常量时间操作,这是在Python里分析程序的时间代价的基础。
Python变量的值都是对象,可以是基本整数、浮点数等类型的对象,也可以是组合类型的对象,如list等。程序中建立和使用的各种复杂对象,包括Python函数等,都基于独立的存储块实现,通过链接相互关联。程序里的名字(变量、参数、函数名等)关联着作为其值的对象,这种关联可以用赋值操作改变。
Python语言中变量的这种实现方式称为变量的引用语义,在变量里保存值(对象)的引用。采用这种方式,变量所需的存储空间大小一致,因为其中只需要保存一个引用。有些语言采用的不是这种方式,它们把变量的值直接保存在变量的存储区里,称为值语义。这样,一个整数类型的变量就需要保存一个整数所需的空间,一个浮点数变量就需要足够的空间存储一个浮点数。如果一个变量中需要保存很大的数据对象,它就需要占据更大的存储空间。例如C语言采用的就是变量的值语义。


12f599894b6ab6b8c17687a80a8de668c8c3a1fb

Python对象的表示
虽然在写Python程序时可以不关心各种对象的具体表示方式。但对这方面情况有所了解,可以帮助人们更清晰地理解程序的行为,特别是与执行效率有关的行为。基于前面的讨论,现在对Python的对象表示做一个概貌性的介绍。后面章节里讨论具体的数据结构时,还会介绍Python中一些结构的表示细节。
Python语言的实现基于一套精心设计的链接结构。变量与其值对象的关联通过链接的方式实现,对象之间的联系同样也通过链接。一个复杂对象内部也可能包含几个子部分,相互之间通过链接建立联系。例如,如果一个list里包含了10个字符串,那么在实现中,在这个list对象里就会记录这10个字符串的链接关系(参看图1.10)。
Python里的组合对象可以具有任意大的规模(例如,list/tuple都可以包含任意多个元素),每个对象需要的存储单元数可能不同(显然,不同的list有长有短),还可能有复杂的内部结构(也就是说,其元素可能又是复杂的数据对象)。在这类复杂对象的创建和使用中,存储安排和管理是比较麻烦的事情。好在Python程序内部有一个存储管理系统,负责管理可用内存,为各种对象安排存储,支持灵活有效的内存使用。程序中要求建立对象时,管理系统就会为其安排存储;某些对象不再有用时则回收其占用的存储。存储管理系统屏蔽了具体内存使用的细节,大大减少了编程人员的负担。
实际上,各种数据对象的具体表示方式,将对相关对象的各种操作的效率产生直接影响,间接影响着用Python开发的程序的效率。显然,Python语言系统的实现者必定认真考虑了各种需要,选择了最合适的实现方式。但是由于实际中的需要千差万别,相互依赖,有些还相互冲突。在这种情况下,语言实现者只能权衡利弊,采用某些折中方案,这就导致某些使用方式更加高效,而另一些方式则较差。了解这方面的一些情况,可以帮助人们更有效地使用Python语言,写出更好的、执行效率更高的Python程序。
一般而言,在使用较低级的编程语言(例如C语言)工作时,人们可以更多地根据需要,自己设计各种数据结构的表示(实现)方法,设法得到较好的效果。在很多常规的数据结构课程和书籍中特别关注了这方面的问题。当然,这些设计和实现工作的细节繁多,编程相当复杂而琐碎,需要花费很多时间和精力。
在使用Python等高级编程系统进行程序开发工作,特别是做与复杂数据结构有关工作时,情况很不一样。由于Python语言提供了很多高级结构,编程中用起来很方便,大大减轻了开发的负担。但是,如不加注意地随意写程序,也很容易做出效率很差,甚至根本无法实际使用的程序。要避免这种情况,在用Python写程序时,就需要关注两方面的问题。一方面,人们也经常需要自己设计一些数据结构,这时需要考虑实现的效率问题,需要对构造的数据结构的基本技术有所了解。第2章将介绍所用的一种重要技术。另一方面,使用语言本身提供的各种高级结构,例如Python的list和dict等,也需要对这些结构的基本性质,以及实现它们的基本原理有准确理解,才能正确有效地使用它们。对于用Python开发较复杂的程序而言,上面所说的两方面理解都非常重要。随着本书中对各种数据结构问题的讨论,也会介绍一些与Python中具体数据类型有关的情况,帮助读者在这些方面建立起正确的认识。
Python的几个标准数据类型
Python语言提供了丰富的标准数据类型,每个类型都提供了大量相关操作。本书中实际使用的类型比较有限,使用的操作也不多。另外,为定义各种数据结构,本书中广泛使用了Python的面向对象机制,使用方式比较规范,第2章将详细介绍有关情况。下面简单概述一下本书中使用的Python组合类型。
list(表)是书中使用最多的组合数据类型。list对象可以包含任意多个任意类型的元素,元素访问和修改都是常量时间操作。此外,list对象是可变对象,在对象的存在期间可以任意地加入或删除元素。因此,程序中经常需要从空表开始,通过逐步加入元素的方法构造任意大的表。在后面一些数据结构的实现中,也使用这种技术。
tuple(元组)在保存元素和元素访问方面的性质与表类似,但其对象是不变对象,只能在创建时一下子构造出来,不能逐步构造。因此在本书中使用较少。
dict(字典)支持基于关键码的数据存储和检索,这里的关键码只能是不变对象(例如,可以是元组、字符串,但不能是表)。如果关键码是组合对象,其元素仍然必须是不变对象。在一个字典里可以容纳任意多的关键码/值关联,支持高效检索(平均时间为O(1))。后面讨论字典数据结构时,将说明怎样实现这种奇妙的对象。
其余组合数据类型在本书中几乎未使用,基本类型的情况很简单,不再赘述。
练习
一般练习
1.设法证明求平方根的牛顿迭代法一定收敛。
2.修改红绿灯安排实例中的算法,使之最后给出的各个分组最大,可以考虑从本章算法给出的分组出发,给每个分组加入不冲突的所有行驶方向。
3.请完整写出采用高斯消元法求矩阵行列式的算法,并仔细分析其时间复杂度。
4.解决同一问题有两个算法,一个算法的时间开销约为100n3,另一个约为0.5×2n。问题规模为多大的情况下后一算法更快?
5.假设现在需要对全世界的人口做一些统计工作,希望在1天之内完成工作。如果采用的算法具有线性复杂度,多快的计算机就足以满足工作需求?如果所用算法具有平方复杂度呢?用天河二号超级计算机大约能处理什么复杂度的算法?
6.如果在宇宙大爆炸的那一刻启动了一台每秒十亿次的计算机执行斐波那契数列的递归算法,假设每条指令计算一次加法。到今天为止它可以算出第几个斐波那契数?这个数的数值应该是多少?
7.假设你从3岁开始手工操作计算器每秒可以完成3次加法或乘法。执行求斐波那契数的递归算法,到今天为止你可能算出哪个斐波那契数?假设执行本章求矩阵乘积的算法,到今天为止能做出两个多大的矩阵的乘积?
8.根据本章的讨论和自己的认识,设法对数据结构和算法的关系做一个综述和总结,并给出自己的认识,讨论其中的问题。
编程练习
1.请回忆(查阅)基础数学中求平方根的方法。请定义一个Python函数,其中采用基础数学中的方法求平方根。从各方面比较这个函数和基于牛顿迭代法的函数。
2.基于1.3.4节中构造整数表的几个函数做一些试验,对一组参数值统计它们的执行时间。修改这些函数,重复试验,对Python中构造表的各种方法做一个总结。
3.用Python字典表示冲突图结构,以关键码 (A, B) 关联的值为True表示冲突,没有值表示不冲突。用这种技术完成本章求无冲突分组的程序。
4.基于前一题的类似设计,设法编写一个程序,使之能枚举出一个冲突图上的各种分组组合,从中找出最佳的无冲突分组。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: