数据结构，是指通过某种方式(例如对元素进行编号)组织在一起的数据元素的集合，这些数据元素可以是数字或者字符，甚至可以是其他数据结构。在Python中，最基本的数据结构是序列(sequence)。序列中的每个元素被分配一个序列号，即元素的位置，也称为索引。索引从0开始。

2.1 序列概述

  在Python中包含6中內建的序列，重点讨论最常用的两种类型：列表和元组。其他內建序列有字符串、Unicode字符串、buffer对象和xrange对象。

  列表和元组的主要区别在于，列表可以修改，元组则不能。也就是说如果要根据要求来添加元素，那么列表可能会更好用；而处于某些原因，序列不能修改的时候，使用元组则更为合适。一般来说，在几乎所有的情况下列表都可以替代元组(使用元组作为字典的键，在这种情况下，因为键不可修改，所以就不能使用列表)。在需要操作一组数值的时候，序列很好用。可以用序列表示数据库中一个人的信息，第一个元素表示姓名，第二个元素表示年龄，如下所示：

>>>edward=['Edward Gumby',42]

  同时序列也可以包含其他序列，因此可以构建如下的一个人员信息列表：

>>>edwrad=['Edward Gumby',42]
>>>john=['John Smith',50]
>>>database=[edward,john]
>>>database
[['Edward Gumby',42],['John Smith',50]]

注意：Python之中还有一种名为容器(container)的数据结构。容器基本上是包含其他对象的任意对象。序列(例如列表和元组)和映射(例如字典)是两类主要的容器。序列中的每个元素都有自己的编号，而映射中的每个元素则有一个名字(也称为键)。

2.2 通用序列操作

  所有的序列类型都可以进行某些特定的操作。这些操作包括：索引(indexing)、分片(sliceing)、加(adding)、乘(multiplying)以及检查某个元素是否属于序列的成员(成员资格)。除此之外，Python还有计算序列长度、找出最大元素和最小元素的內建函数。

  序列中的所有元素都是有编号的(从0递增)。这些元素可以通过编号分别访问，如下例所示：

>>>greeting='Hello'
>>>greeting[0]
'H'

  这就是索引。可以通过索引获取元素，所有序列都可以通过这种方法进行索引。使用负数索引时，Python会从右边，也就是从最后1个元素开始计数。最后一个元素的位置编号为-1(不是-0，因为那会和第一个元素重合)：

>>>greeting[-1]
'o'

  字符串字面值能够直接使用索引，而不需要一个变量引用它们。效果是一样的，如下所示：

>>>'Hello'[1]
'e'

  如果一个函数返回一个序列，那么可以直接对返回金额过进行索引操作，如下所示：

>>>fourth=raw_input('Year:')[3]
Year: 2005
>>>fourth
'5'

  与使用索引来访问单个元素类似，可以使用分片操作来访问一定范围内的元素。分片通过冒号相隔的两个索引来实现:

>>>tag='<a href="http://www.python.org">Python web site</a>'
>>>tag[9:30]
'http://www.python.org'
>>>tag[32:-4]
'Python web site'

  分片操作对于提取序列的一部分是很有用的。而编号在这里尤为重要。第一个索引是需要提取部分的第一个元素的编号，而最后索引则是分片之后剩下部分的第一个元素的编号:

>>>numbers=[1,2,3,4,5,6,7,8,9,10]
>>>numbers[3:6]
[4,5,6]
>>>numbers[0:1]
[1]

  简而言之，分片操作的实现需要提供两个索引作为边界，第一个索引的元素是包含在分片内的，而第二个则不包含在分片内。
  如果分片所得部分包括序列结尾的元素，那么，只需置空最后一个索引即可：

>>>numbers[-3:]
[8,9,10]

同样，如果分片所得部分包含序列开始的元素，只需置空第一个索引：

>>>numbers[:3]
[1,2,3]

实际上，如果需要复制整个序列，可以将两个序列都置空:

>>>numbers[:]
[1,2,3,4,5,6,7,8,9,10]

  进行分片的时候，分片的起始点和结束点需要进行指定(不管是直接还是间接)。而另外一个参数(步长)通常都是隐式设置的。在普通的分片中，步长是1，分片操作就是按照这个步长逐个遍历序列的元素，然后返回开始和结束点之间的所有元素：

#与numbers[0:10]作用一样，步长默认是1
>>>numbers[0:10:1]   
[1,2,3,4,5,6,7,8,9,10]

  在这个例子中，分片包含了另外一个数字，即步长。如果步长设置成比1大的数，那么就会跳过某些元素：

>>>numbers[0:10:2]
[1,3,5,7,9]

>>>numbers[3:6:3]
[4]

  如果需要将每4个元素的第一个提取出来，那么只要将步长设置为4即可：

>>>numbers[::4]
[1,5,9]

  注意，步长不能为0，那不会往下执行，但步长可以是负数，即从右到左提取元素:

>>>numbers[8:3:-1]
[9,8,7,6,5]
>>>numbers[10:0:-2]
[10,8,6,4,2]
>>>numbers[0:10:-2]
[]

  注意，当时用一个负数作为步长时，必须让开始点大于结束点。否则返回一个空列表。
  通过使用加号可以进行序列的连接操作：

>>>[1,2,3]+[4,5,6]
[1,2,3,4,5,6]
>>>'Hello,'+'world!'
'Hello,world!'

  两种相同类型的序列才能进行连接操作。如列表和字符串是无法连接在一起的，尽管他们都是序列。
  用用数字x乘以一个序列会生成新的序列，而在新的序列中，原来的序列将被重复x次：

>>>'python'*5
'pythonpythonpythonpythonpython'
>>>[42]*10
[42,42,42,42,42,42,42,42,42,42]

  空列表可以简单地通过两个中括号表示[]，里面什么都没有。但是如果想创建一个占用十个元素空间，却不包括任何有用内容的列表，可以像前面那样使用[42]10，或者使用[0]10，这会更加实际一些。这就生成了一个包括10个00的列表。可以通过下面的方式来初始化一个长度为10的空列表:

#None是Python的內建值，表示空
>>>sequence=[None]*10
>>>sequence
[None,None,None,None,None,None,None,None,None,None]

  为了检查一个值是否在序列中，可以使用in运算符。该运算符和之前讨论过的有一点不同。这个运算符检查某个条件是否为真，然后返回相应的值：条件为真返回True，条件为假返回False。这样的运算符叫做布尔运算符，而真值则叫做布尔值：

>>>permissions='rw'
>>>'w' in permissions
True
>>>'x' in permissions
False
>>>users=['mlh','foo','bar']
>>>raw_input('Enter your user name: ') in users
Enter your user name: mlh
True
>>>subject='$$$ Get rich now!!! $$$'
>>>'$$$' in subjectt
True

  下面的例子查看用户输入的用户名和PIN码是否存在于数据中：

database=[['albert','1234'],['dilbert','4242'],['smith','7524'],['jones','9843']]
username=raw_input('User name: ')
pin=raw_input('PIN code: ')
if [username,pin] in database:
   print 'Access granted'

  內建函数len、min和max非常有用。len函数返回序列中所包含元素的数量，min函数和max函数则分别返回序列中最大和最小的元素：

>>>numbers=[100,34,678]
>>>len(numbers)
3
>>>max(numbers)
678
>>>min(numbers)
34

>>>max(2,3)
3
>>>min(9,3,2,5)
2

  从上面的例子中，可以看出，max和min函数的参数并不是一个序列，而是以多个数字直接作为参数。
  列表和元组、字符串不同在于列表是可变的，即可以改变列表的内容，并且列表有很多有用的专门的方法。
  因为字符串不能像列表一样被修改，所以有时根据字符串创建列表会很有用。list函数可以实现这个操作：

>>>list('Hello')
['H','e','l','l','o']

  注意，list函数适用于所有类型的序列，而不只是字符串。可以用下面的表达式将一个由字符组成的列表转换为字符串：

#somelist是需要转换的列表
''.join(somelist)

  列表可以使用所有适用于列表的标准操作，例如索引、分片、连接和乘法。有趣的是，列表是可以修改的。改变列表是很容易的，只需要使用普通赋值语句即可。然而，我们并不会使用x=2这样的语句进行赋值，而是使用索引标记来为某个特定的、位置明确的元素赋值，如x[1]=2：

>>>x=[1,1,1]
>>>x[1]=2
>>>x
[1,2,1]

  注意，不能为一个位置不存在的元素进行赋值。
  从列表中删除元素也很容易，使用del语句来实现：

>>>names=['Alice','Beth','Cecil','Dee-Dee','Earl']
>>>del names[2]
>>>names
['Alice','Beth','Dee-Dee','Earl']

  删除后，列表的长度也从5变成了4。除了删除列表中的元素，该语句还能用于删除其他元素。它可以用于字典元素甚至是其他变量的删除操作。
  使用分片赋值时，可以使用与原序列不等长的序列将分片替换：

>>>name=list('Perl')
>>>name
['P','e','r','l']
>>>name[1:]=list('ar')
>>>name
['P','e','a','r']

>>>demo=list('Perl')
>>>name[1:]=list('ython')
>>>name
['P','y','t','h','o','n']

  分片复制语句可以在不需要替换任何原有元素的情况下插入新的元素：

>>>numbers=[1,5]
>>>numbers[1:1]=[2,3,4]
>>>numbers
[1,2,3,4,5]

  这个程序只是替换了一个空的分片，因此实际的操作是插入了一个序列。因此，通过分片复制来删除元素也是可以的：

>>>numbers=[1,2,3,4,5]
>>>numbers[1:4]=[]
>>>numbers
[1,5]

  列表方法：方法是一个与某些对象有紧密联系的函数，对象可能是列表/数字，也可能是字符串或者其他类型的对象。一般来说，方法可以这样进行调用：

对象.方法(参数)

  除了对象被放置在方法名之前，并且两者之间有一个点号隔开，方法调用和函数调用很类似。

• append：append方法用于在列表末尾追加新的对象：
  

  lst=[1,2,3]
  lst.append(4)
  lst
  [1,2,3,4]

• count：count方法统计某个元素在列表中出现的次数：
  

  ['to','be','or','not','to','be'].count('to')
  2
  x=[[1,2],1,1,[2,1,[1,2]]]
  x.count(1)
  2
  x.count([1,2])
  1

• extend：extend方法可以在列表的末尾一次性追加另一个序列中的多个值。换句话说，可以用新列表扩展原有的列表：

  a=[1,2,3]
  b=[4,5,6]
  a.extend(b)
  a
  [1,2,3,4,5,6]

  这个操作很像连接操作，两者最主要的区别在于：extend方法些改了被扩展的序列(在这个例子中，也就是a)，而原始的连接操作则不然，它会返回一个全新的列表：

>>>a=[1,2,3]
>>>b=[4,5,6]
>>>a+b
[1,2,3,4,5,6]
>>>a
[1,2,3]

• index：index方法用于从列表中找出某个值第一个匹配项的索引位置：

  knights=['we','are','the','knights','who','say','ni']
  knights.index('who')
  4
  knights.index('herring')
  ValueError:list.index(x):x not in list

• insert:insert方法用于将对象插入到列表中：

  numbers=[1,2,3,4,5,6,7]
  numbers.insert(3,'four')
  numbers
  [1,2,3,'four',5,6,7]

• pop：pop方法会移除列表中的一个元素(默认是最后一个)，并且返回该元素的值：

  x=[1,2,3]
  x.pop()
  3
  x
  [1,2]
  x.pop(0)
  1
  x
  [2]

  pop方法是唯一一个既能修改列表又返回元素值的列表方法。使用pop方法可以实现的一种常用的数据结构--栈。栈的原理就像堆放盘子那样。只能在顶部放一个盘子，同样，也只能从顶部拿走一个盘子。最后被放入堆栈的最先被移除(这个原则称为LIFO，即后进先出)。

  对于上述两个栈操作(放入和移除),即入栈(push)和出栈(pop)。Python没有入栈方法，但可以使用append方法来代替。pop方法和append方法的操作结果恰好相反，如果入栈刚刚出栈的值，最后得到的结果还是原来的栈。

>>>x=[1,2,3]
>>>x.append(x.pop())
>>>x
[1,2,3]

• remove：remove方法用于移除列表中某个值的第一个匹配项：

  x=['to','be','or','not','to','be']
  x.remove('be')
  x
  ['to','or','not','to','be']

  可以看到，只有第一次出现的值被移除了，而不存在于列表中的值是不会移除的。值得注意的是，remove是一个没有返回值的原位置改变方法。它修改了列表却没有返回值，这与pop方法相反。

• reverse：reverse方法将列表中的元素反向存放：

  x=[1,2,3]
  x.reverse()
  x
  [3,2,1]

  注意，该方法也改变了列表但不返回值(就像remove和sort)。如果需要对一个序列进行反向迭代，那么可以使用reverse函数，这个函数并不返回一个列表，而是返回一个迭代器(iterator)对象。尽管如此，使用list函数把返回的对象转换成列表也是可行的。

>>>x=[1,2,3]
>>>list(reverse(x))
[3,2,1]

• sort：sort方法用于在原位置对列表进行排序。在"原位置排序"意味着改变原来的列表，从而让其中的元素能按一定的顺序排列，而不是简单地返回一个已排序的列表副本。

  x=[4,5,2,1,7,9]
  x.sort()
  x
  [1,2,4,6,7,9]

  前面介绍过了几个改变列表却不返回值的方法，在大多数情况下这样的行为方式是很合常理的(例如append方法)。当用户需要一个排好序的列表副本，同时又保留原有列表不变的时候，问题就出现了。

  如果希望元素能按特定的方式进行排序，那么可以通过compare(x,y)的形式自定义比较函数。compare(x,y)函数会在x<y时返回负数，在x>y时返回正数，如果x=y则返回0.定义好该函数后，就可以提供给sort方法作为参数了。内建函数cmp提供了比较函数的默认实现方式：

>>>cmp(42,32)
1
>>>cmp(99,100)
-1
>>>cmp(10,10)
0
>>>numbers=[5,2,9,7]
>>>numbers.sort(cmp)
>>>numbers
[2,5,7,9]

  sort方法有另外两个可选的参数--key和reverse。如果要使用它们，就要通过名字来指定。参数key与cmp类似--必须提供一个在排序过程中使用的函数。然而，该函数并不是直接用来确定对象的大小，而是为每个元素创建一个键，然后所有元素根据键来排序。因此，如果要根据元素的长度进行排序，那么可以使用len作为键函数：

>>>x=['aardvark','abalone','acme','add','aerate']
>>>x.sort(key=len)
>>>x
['add','acme','aerate','abalone','aardvark']

  另外一个关键字参数reverse是简单的布尔值(True或者是False)，用来指明列表是否要进行反向排序。

>>>x=[4,6,2,1,7,9]
>>>x.sort(reverse=True)
>>>x
[9,7,6,4,2,1]

  cmp、key、reverse参数都可以用于sorted函数。在多数情况下，为cmp或key提供自定义函数是非常有用的。
  元组和列表一样，也是序一种序列。唯一不同的是元组不能改变。创建元组的语法如下：

>>>1,2,3
(1,2,3)

  元组是通过圆括号括起来的，空元组可以用没有包含内容的两个圆括号来表示：

>>>()
()

  注意，实现包含一个值的元组有点奇特，必须加一个逗号，即使只有一个值：

>>>42
42
>>>42,
(42,)
>>>(42,)
(42,)

• tuple:tuple函数的功能与list函数基本上是一样的：以一个序列作为参数并把它转换为元组。如果参数就是元组，那么该参数就会被原样返回：

  tuple([1,2,3])
  x.sort()
  >>>x
  [1,2,4,6,7,9]
  
    前面介绍过了几个改变列表却不返回值的方法，在大多数情况下这样的行为方式是很合常理的(例如append方法)。当用户需要一个排好序的列表副本，同时又保留原有列表不变的时候，问题就出现了。
  
    如果希望元素能按特定的方式进行排序，那么可以通过compare(x,y)的形式自定义比较函数。compare(x,y)函数会在x<y时返回负数，在x>y时返回正数，如果x=y则返回0.定义好该函数后，就可以提供给sort方法作为参数了。内建函数cmp提供了比较函数的默认实现方式：
  
  >>>cmp(42,32)
  1
  >>>cmp(99,100)
  -1
  >>>cmp(10,10)
  0
  >>>numbers=[5,2,9,7]
  >>>numbers.sort(cmp)
  >>>numbers
  [2,5,7,9]
  
    sort方法有另外两个可选的参数--key和reverse。如果要使用它们，就要通过名字来指定。参数key与cmp类似--必须提供一个在排序过程中使用的函数。然而，该函数并不是直接用来确定对象的大小，而是为每个元素创建一个键，然后所有元素根据键来排序。因此，如果要根据元素的长度进行排序，那么可以使用len作为键函数：
  
  >>>x=['aardvark','abalone','acme','add','aerate']
  >>>x.sort(key=len)
  >>>x
  ['add','acme','aerate','abalone','aardvark']
  
    另外一个关键字参数reverse是简单的布尔值(True或者是False)，用来指明列表是否要进行反向排序。
  
  >>>x=[4,6,2,1,7,9]
  >>>x.sort(reverse=True)
  >>>x
  [9,7,6,4,2,1]
  
    cmp、key、reverse参数都可以用于sorted函数。在多数情况下，为cmp或key提供自定义函数是非常有用的。
    元组和列表一样，也是序一种序列。唯一不同的是元组不能改变。创建元组的语法如下：
  
  >>>1,2,3
  (1,2,3)
  
    元组是通过圆括号括起来的，空元组可以用没有包含内容的两个圆括号来表示：
  
  >>>()
  ()
  
    注意，实现包含一个值的元组有点奇特，必须加一个逗号，即使只有一个值：
  
  >>>42
  42
  >>>42,
  (42,)
  >>>(42,)
  (42,)
  
  - tuple:tuple函数的功能与list函数基本上是一样的：以一个序列作为参数并把它转换为元组。如果参数就是元组，那么该参数就会被原样返回：
  
  >>>tuple([1,2,3])
  (1,2,3)
  tuple('abc')
  ('a','b','c')
  tuple((1,2,3))
  (1,2,3)

  元组其实并不复杂--除了创建元组和访问元组元素之外，也没有太多其他操作，可以参照其他类型的序列来实现：

>>>x=1,2,3
>>>x[1]
2
>>>x[0:2]
(1,2)

  元组的分片还是元组，就像列表的分片还是列表一样