数据结构简介

Python定义的类型（或对象）层次结构在概念上可以划分为四种类别：简单类型、容器类型、代码类型 和内部类型。

可以将 PyObject 类之下的所有 Python 类划分为 Python 运行时解释器可以使用的四个主要类别：

• 简单类型 —— 基本构建块，如 int 和 float。
• 容器类型—— 保存其他对象。
• 代码类型—— 封装 Python 程序的元素。
• 内部类型 —— 程序执行期间使用的类型。

内置的简单类型

Python 有五个内置的简单类型：bool、int、long、float 和 complex。在 Python 中，简单数据类型并不是原始数据类型，而是完善的对象，它们有自已的方法和类。另外，这些简单的内置类型是不可改变的，这意味着：创建对象之后，您无法更改对象的值。如果需要新值，则必须创建新的对象。通过 Python id 函数，可以查看基本 PyObject 标识的变更方式：

清单 3. 使用 Python id 函数

>>> i = 100

>>> id(i)

8403284

>>> i = 101

>>> id(i)

8403296

此方法看似容易丢失对象，会导致内存泄漏。但是，Python 像 C# 和 Java 一样，使用了垃圾回收功能，以释放用于保存不再引用的对象的内存，如上例中用于保存 100 的整数对象。

容器类型

当您的程序需要一次处理多个对象时，就可以利用 Python 容器类：

• tuple
• string
• unicode
• frozenset
• list
• set
• dictionary

有序性：
这些容器类型提供了两种功能。前六个类型是有序的（序列），最后一个类型 dictionary 则是一个映射。

可变性：
前四种容器类型（tuple,string,unicode,frozenset）的顺序是不可变的，这意味着在您创建了这些容器类型之一后，所存储的数据就不可更改。如果出于某种原因需要更改数据，则需要创建一个新容器来保存新的数据。
后三种容器类型（list、set、dictionary）都是可变容器，因此，它们可以根据需要更改保存的任何数据（但在 dictionary 中所使用的密钥是不可变的，就像您房间的钥匙）。
虽然可变容器非常灵活，但它们的动态特性会对性能造成影响。例如，tuple 类型，尽管它是不可变的，灵活性较差，但在同一环境中使用时，它们通常比 list 类型快得多。

之前已经介绍了字符串，下小节我们将会学习如何使用元组、列表和字典，以及它们如何使编程变得简单。

元组

• 元组和列表十分类似，只不过元组和字符串一样是 不可变的 即你不能修改元组。
• 元组通过圆括号中用逗号分割的项目定义。元组通常用在使语句或用户定义的函数能够安全地采用一组值的时候，即被使用的元组的值不会改变。
• 含有0个或1个项目的元组。一个空的元组由一对空的圆括号组成，如myempty = ()。然而，含有单个元素的元组就不那么简单了。你必须在第一个（唯一一个）项目后跟一个逗号，这样Python才能区分元组和表达式中一个带圆括号的对象。即如果你想要的是一个包含项目2的元组的时候，你应该指明singleton = (2 , )。
• tuple 实际上是一个异构容器，创建可以拥有各种类型数据项（其中包括另一 tuple）的 tuple 。

变量zoo是一个元组，我们看到len函数可以用来获取元组的长度。这也表明元组也是一个序列。

>>> t = (0,1,2,3,4,5,6,7,8,9) >>> type(t) <type 'tuple'>

>>> t (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) >>> tt = 0,1,2,3,4,5,6,7,8,9

>>> type(tt) <type 'tuple'>

>>> tt (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) >>> tc=tuple((0,1,2,3,4,5,6,7,8,9)) >>> tc (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) >>> et = ()     # An empty tuple

>>> et () >>> st = (1,)   # A single item tuple

>>> st (1,)

>>> t = (0,1,"two",3.0,"four",(5,6))
>>> tn = t[1:3] + t[3:6]  # Add two tuples

>>> tn (1, 'two', 3.0, 'four', (5, 6)) >>> tn = t[1:3] + t[3:6] + (7,8,9,"ten") >>> tn (1, 'two', 3.0, 'four', (5, 6), 7, 8, 9, 'ten') >>> t2 = tn[:]            # Duplicate an entire tuple, a full slice

>>> t2 (1, 'two', 3.0, 'four', (5, 6), 7, 8, 9, 'ten') >>> len(tn)               # Find out how many items are in the tuple

9

>>> tn[4][0]              # Access a nested tuple

5

• 您还可以从称为打包 的过程的一组现有变量中创建一个tuple。
• 反之亦然，其中，tuple 中的值被指派给变量。这之后的过程称为解包，它是用于许多情形的功能十分强大的技术，其中包括希望从一个函数中返回多个值。在解包 tuple 时，仅有的问题是必须为tuple 中的每个数据项提供一个变量。

>>> i = 1

>>> s = "two"

>>> f = 3.0

>>> t = (i, s, f)         # Pack the variables into a tuple

>>> t (1, 'two', 3.0) >>> ii, ss, ff = t        # Unpack the tuple into the named variables

>>> ii 1

>>> ii, ff = t            # Not enough variables to unpack three element tuple

Traceback (most recent call last): File "<stdin>", line 1, in ? ValueError: too many values to unpack

许多其他容器类型具有类似的功能，其中包括分段以及打包或解包，了解 tuple 的工作原理意味着您已经开始完全理解 Python 中的其他容器类型。

元组与打印语句

print语句可以使用跟着%符号的项目元组的字符串。这些字符串具备定制的功能。定制让输出满足某种特定的格式。Python在这里所做的是把元组中的每个项目转换成字符串并且用字符串的值替换定制的位置。print的这个用法使得编写输出变得极其简单，它避免了许多字符串操作。它也避免了我们一直以来使用的逗号。

在大多数时候，你可以只使用%s定制，而让Python来提你处理剩余的事情。这种方法对数同样奏效。然而，你可能希望使用正确的定制，从而可以避免多一层的检验程序是否正确。

在第二个print语句中，我们使用了一个定制，后面跟着%符号后的单个项目——没有圆括号。这只在字符串中只有一个定制的时候有效。

列表

• list是处理一组有序项目的数据结构，即你可以在一个列表中存储一个 序列 的项目。你可以在列表中添加 任何种类的对象 包括数甚至其他列表。在Python中，你在每个项目之间用逗号分割。
• 列表中的项目应该包括在方括号中，这样Python就知道你是在指明一个列表。
• 一旦你创建了一个列表，你可以添加、删除或是搜索列表中的项目。由于你可以增加或删除项目，我们说列表是 可变的 数据类型，即这种类型是可以被改变的。

对象与类的快速入门

• 列表是使用对象和类的一个例子。当你使用变量i并给它赋值的时候，比如赋整数5，你可以认为你创建了一个类（类型）int的对象（实例）i。事实上，你可以看一下help(int)以更好地理解这一点。
• 类也有方法，即仅仅为类而定义的函数。仅仅在你有一个该类的对象的时候，你才可以使用这些功能。例如，Python为list类提供了append方法，这个方法让你在列表尾添加一个项目。例如mylist.append('an item')列表mylist中增加那个字符串。注意，使用点号来使用对象的方法。
• 一个类也有域，它是仅仅为类而定义的变量。仅仅在你有一个该类的对象的时候，你才可以使用这些变量/名称。类也通过点号使用，例如mylist.field。

使用列表

我们也使用了for..in循环在列表中各项目间递归。从现在开始，你一定已经意识到列表也是一个序列。序列的特性会在后面的章节中讨论。

注意，我们在print语句的结尾使用了一个 逗号 来消除每个print语句自动打印的换行符。这样做有点难看，不过确实简单有效。

接下来，我们使用append方法在列表中添加了一个项目。再接下来，我们使用列表的sort方法来对列表排序。需要理解的是，这个方法影响列表本身，而不是返回一个修改后的列表——这与字符串工作的方法不同。这就是我们所说的列表是 可变的 而字符串是 不可变的。

最后，我们指出我们想要删除列表中的哪个项目，而del语句为我们从列表中删除它。我们指明我们想要删除列表中的第一个元素，因此我们使用del shoplist[0]（记住，Python从0开始计数）。

创建单个条目的 tuple 还需要在单个条目后面跟一个逗号。这是区分单个条目 tuple 与方法调用的必要条件，这一点将在以后详细讨论。而对于 list，则是不必要的，尽管也允许使用单个逗号。

>>> el = []    # Create an empty list

>>> len(el) 0 >>> sl = [1]    # Create a single item list

>>> len(sl) 1

>>> sl = [1,]    # Create a single item list, as with a tuple

>>> len(sl) 1

您不仅能够将序列直接传递给构造函数，还可以将拥有元组或字符串的变量传递给 list 构造函数。

>>> l = list((0, 1, 2, 3, 4, 5, 6, 7, 8, 9))    # Create a list from a tuple

>>> l [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> len(l) 10

>>> l = list([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])    # Create a list from a list

>>> l [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> len(l) 10

>>> l = list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)      # Error: Must pass in a sequence

Traceback (most recent call last): File "<stdin>", line 1, in ? TypeError: list() takes at most 1 argument (10 given) >>> l = list("0123456789") # Create a list from a string

>>> l ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] >>> len(l) 10

• 切片 是一个非常有用的概念，其一般形式为 l[start:end:step]，其中 start 和 end 分别是开始和结束索引，step 是在切片时要跨过的条目数量。
• 此外，还可以对结束索引使用负值，即从序列的结尾往回计数。
• 另一个有用的功能是以一种很合适的方式处理错误（如超过序列的长度）。如前一个例子所示，您还可以选择忽略切片中使用的三个值中的一个或多个值。例如，我在切片 l[0::2] 中没有使用结束索引。

>>> l[0::2]      # Get every second item

[0, 2, 4, 6, 8] >>> l[0], l[1], l[2] (0, 1, 2)

list 和 tuple 之间的主要区别在于 list 是一个可变的序列，

• 这就意味着您不但可以方便地访问 list 中的条目，而且可以方便地修改它们。
• 但这会引起一个并发症状：您只能修改序列中的条目。若要向序列中添加条目（而不仅仅是修改条目），可使用 append 方法

>>> l = [] >>> l[0] = 0      # The list is empty

Traceback (most recent call last): File "<stdin>", line 1, in ? IndexError: list assignment index out of range >>> l.append(0) >>> l [0] >>> l[0] = 1

>>> l [1]

• 修改 list 中的条目相当容易：您可以适当地设置条目的值，甚至设置成另一种不同的类型（当然list和tuple一样都是异构的），如 string 或另一 list。
• 您还可以使用重复运算符*，以便从小片段中构建更大的列表。
• 删除条目的第一个方法是使用 del 方法。使用此方法可以删除一个条目或一个条目范围。
• 您还可以使用灵活而强大的切片方法从 list 中删除切片。

>>> l=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> l [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> l[2] = 2

>>> type(l[2]) <type 'int'>

>>> l[2] = "two"      # Change the type of an element

>>> type(l[2]) <type 'str'>

>>> l [0, 1, 'two', 3, 4, 5, 6, 7, 8, 9] >>> l[2] = l[2:5] * 2

>>> l [0, 1, ['two', 3, 4, 'two', 3, 4], 3, 4, 5, 6, 7, 8, 9] >>> del(l[2])         # Remove single element

>>> l [0, 1, 3, 4, 5, 6, 7, 8, 9] >>> l[1:3] = []       # Remove a slice

>>> l [0, 4, 5, 6, 7, 8, 9]

使用 list 保持二维 (2-D) 或三维 (3-D) 数组

>>> al = [[0, 1, 2], [3, 4, 5], [6, 7, 8]] >>> al[0][0]          # First element in 2D array

0 >>> al[2][2]          # Last element in 2D array

8

>>> al[1][2] 5

>>> al = [[[0, 1], [2, 3]], [[4, 5], [6, 7]]] >>> al[0][0][1] 1

>>> len(al)           # Length of outer dimension

2

>>> len(al[0])        # Length of middle dimension

2

>>> len(al[0][0])     # Length of inner dimension

2

可以反转 list 中的所有条目或排序 list：不过，要记住这些操作的一个重点在于，它们是就地（in place） 操作，这意味着它们会修改调用它们所针对的 list。因此，如果您尝试创建新列表，并将其设置为对这些方法之一调用所产生的结果，则会得到一个空列表。

>>> l=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> id(l) # This is the object id for our current list

4525432

>>> l.reverse()       # Reverse the list

>>> l [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] >>> id(l) # The id is the same, modified list in place.

4525432

>>> l.sort()          # Sort the list in numerical order

>>> l [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> id(l) # Modified the existing list

4525432

>>> l.index(5)        # Same as l[5]

5

>>> l.count(0)        # How

many times does '0' occur in the list 1

list 除可以用于模拟数组外，还可以用于模拟其他数据结构。例如，append 和 pop 方法对 list 函数的操作要么是先进先出 (FIFO) 数据结构（也称为队列），要么是后进先出 (LIFO) 数据结构（也称为堆栈）。通过允许您将条目设置为从 list 中弹出（删除并返回），pop 方法支持这些功能。如果弹出 list 的第一项，则是一个队列；反之，如果弹出 list 的最后一项，则是一个堆栈。

>>> l.pop()           # Take off the last item (Stack)

9

>>> l [0, 1, 2, 3, 4, 5, 6, 7, 8] >>> l.pop(5)          # Take out the fifth element

5

>>> l [0, 1, 2, 3, 4, 6, 7, 8] >>> l.pop(0)          # Take the first item off the list (Queue)

0 >>> l [1, 2, 3, 4, 6, 7, 8]

如果你想要知道列表对象定义的所有方法，可以通过help(list)获得完整的知识。

序列

列表、元组和字符串都是序列。序列的神奇之处在于你可以用相同的方法访问元组、列表和字符串。

序列的两个主要特点是索引操作符和切片操作符。

• 索引操作符让我们可以从序列中抓取一个特定项目。
• 切片操作符让我们能够获取序列的一个切片，即一部分序列。

使用索引操作符来取得序列中的单个项目（下标操作）。Python从0开始计数。索引同样可以是负数，可以想象序列是一个首尾相连的环，0表示序列的首元素）。因此，t[-1]表示序列的最后一个元素。

切片操作符是序列名后跟一个方括号，方括号中有一对可选的数字，并用冒号分割。记住数是可选的，而冒号是必须的。切片操作符中的第一个数（冒号之前）表示切片开始的位置，第二个数（冒号之后）表示切片到哪里结束。如果不指定第一个数，Python就从序列首开始。如果没有指定第二个数，则Python会停止在序列尾。

注意，返回的序列从开始位置 开始 ，刚好在 结束 位置之前结束。即开始位置是包含在序列切片中的，而结束位置被排斥在切片外。切片的工作方式是声明开始索引、结束索引和一个可选的步骤大小，全部都用分号分隔。因此，t[2:7] 将 tuple 中的第三到第七个数据项分段，而 t[2:7:2] 则对每两个数据项进行分段，从 tuple 中的第三个数据项开始一直到第七个数据项。

2 (0, 9, 9) (2, 3, 4, 5, 6) (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) (2, 4, 6) (2, 4, 6, 8) (0, 1, 2, 3, 4, 5, 6, 7, 8)

这样，t[1:3]返回从位置1开始，包括位置2，但是停止在位置3的一个序列切片，因此返回一个含有两个项目的切片。类似地，t[:]返回整个序列的拷贝。

你可以用负数做切片。负数用在从序列尾开始计算的位置。例如，t[:-1]会返回除了最后一个项目外包含所有项目的序列切片。

使用Python解释器交互地尝试不同切片指定组合，即在提示符下你能够马上看到结果。

字典

• 字典类似于你通过联系人名字查找地址和联系人详细情况的地址簿，即，我们把键（名字）和值（详细情况）联系在一起。
• 注意，键必须是唯一的，就像如果有两个人恰巧同名的话，你无法找到正确的信息。
• 注意，你只能使用不可变的对象（比如字符串）来作为字典的键，但是你可以不可变或可变的对象作为字典的值。基本说来就是，你应该只使用简单的对象作为键。
• 键值对在字典中以这样的方式标记：d = {key1 : value1, key2 : value2 }。注意它们的键/值对用冒号分割，而各个对用逗号分割，所有这些都包括在花括号中。
• 记住字典中的键/值对是没有顺序的。如果你想要一个特定的顺序，那么你应该在使用前自己对它们排序。
• 字典是dict类的实例/对象。

我们可以使用索引操作符来寻址一个键并为它赋值，这样就增加了一个新的键/值对，就像在上面的例子中我们对Guido所做的一样。

我们可以使用del语句来删除键/值对。我们只需要指明字典和用索引操作符指明要删除的键，然后把它们传递给del语句就可以了。执行这个操作的时候，我们无需知道那个键所对应的值。

接下来，我们使用字典的items方法，来使用字典中的每个键/值对。这会返回一个元组的列表，其中每个元组都包含一对项目——键与对应的值。我们抓取这个对，然后分别赋给for..in循环中的变量name和address然后在for－块中打印这些值。

我们可以使用in操作符来检验一个键/值对是否存在，或者使用dict类的has_key方法。你可以使用help(dict)来查看dict类的完整方法列表。

关键字参数与字典 如果换一个角度看待你在函数中使用的关键字参数的话，你已经使用了字典了！只需想一下——你在函数定义的参数列表中使用的键/值对。当你在函数中使用变量的时候，它只不过是使用一个字典的键（这在编译器设计的术语中被称作 符号表）。

参考

当你创建一个对象并给它赋一个变量的时候，这个变量仅仅 参考 那个对象，而不是表示这个对象本身！也就是说，变量名指向你计算机中存储那个对象的内存。这被称作名称到对象的绑定。

大多数解释已经在程序的注释中了。你需要记住的只是

如果你想要复制一个列表或者类似的序列或者其他复杂的对象（不是如整数那样的简单 对象），那么你必须使用切片操作符来取得拷贝。

如果你只是想要使用另一个变量名，两个名称都 参考 同一个对象，那么如果你不小心的话，可能会引来各种麻烦。

from: http://www.cnblogs.com/wei-li/archive/2012/03/26/2417296.html