Question

Python中的绝大部分数据结构可以被最终分解为三种类型：标量 （Scaler），序列 （Sequence），映射 （Mapping）。这表明了数据存储时所需的基本单位，其重要性如同欧式几何公理之于欧式空间。在第2.2节中，我们已经详细叙述了“标量”，如整数、浮点数等数据类型。这里需要补充更为复杂的数据结构。

序列是Python中最为基础的内建类型。它分为七种类型：列表、字符串、元组、Unicode字符串、字节数组、缓冲区和xrange对象。常用的是：列表 （List）、字符串 （String）、元组 （Tuple）。

映射在Python的实现是数据结构字典 （Dictionary）。作为第三种基本单位，映射的灵活使得它在多种场合中都有广泛的应用和良好的可拓展性。

集合 （Set）是独立于标量、序列和映射之外的特殊数据结构，它支持数学理论的各种集合的运算。它的存在使得用程序代码实现数学理论变得方便。

建议有能力的读者查看Python数据结构实现的源码，也可以参考《Data Structure and Algorithms with Python》这本书。这能让读者很好认识Python每种数据结构的实现算法及效率。工业代码讲求运行效率，本书由于篇幅限制仅仅介绍Python数据结构的用法，不涉及时间复杂度和空间复杂度，我们极力建议读者补充这方面的知识。

2.4.1 列表

列表 （List）是一个任意类型的对象的位置相关的有序集合。它没有固定的大小，更准确地说，它的大小是可变的。通过对偏移量进行赋值以及其他各种列表的方法进行调用，能够修改列表的大小和内容。

1.创建列表

列表是序列的一种，Python的列表元素没有固定数据类型的约束 。列表是有序的，可以直接通过下标（即索引）访问其元素。注意下标是从0开始，Python的下标允许是负数 ，例如List2[-1]表示List2从后往前数的第一个元素。除了索引 ，列表支持切片 。切片返回一个子列表。切片的索引有两个默认值，第一个索引默认为零，第二个索引默认为切片的列表的大小。代码见代码清单2-8。

代码清单2-8 创建列表

print '''创建列表
'''
List1= ['Python',5,0.2]
List2=['I','love']
print "通过下标访问列表元素
"
print List1[0],List2[1],List2[-1]
# result: Python love love
print List1[0:2],List1[:2] #注意子列表不包含
List1[2]
# result:['Python', 5] ['Python', 5]
print List2[:],List2[0:]
# result:['I', 'love'] ['I', 'love']

*代码详见：示例程序/code/2-4-1.py

2.列表方法

Python的列表与其他语言的数组有些类似，但是Python的列表强大得多，它具有很多灵活的函数。它能够做到像字符串一样自由插入、查找、合并。并且与其他语言，如C、Java等相比，Python的列表常常具有速度上的优势。下面给出Python常用的列表函数说明（见表2-6）及例子（见代码清单2-9），请读者运行例子好好体会。

表2-6 列表函数说明

代码清单2-9 列表多种操作

print '''列表方法
'''
List1.append(3.1)
print List1
# result: ['Python', 5, 0.2, 3.1]
List2.insert(1,'really')
print List2
# result: ['I', 'really', 'love']
List1.remove(3.1)
print List1
# result: ['Python', 5, 0.2]
print List1.index(5),List1.count(5)
# result: 1 1
List2.extend(List1)
print List2
# result: ['I', 'really', 'love', 'Python', 5, 0.2]
List2.reverse()
print List2
# result: [0.2, 5, 'Python', 'love', 'really', 'I']
List3.sort()
print List3
# result: [1,2,3]

*代码详见：示例程序/code/2-4-1.py

3.列表用作栈和队列

列表函数使得列表当作栈非常容易，栈的思想是最先进入的元素最后一个取出（后进后出），使用append（）进行压入，使用pop（）进行弹出。见代码清单2-10。

代码清单2-10 列表用作栈

print '''列表用作栈和队列
'''
stack=[7,8,9]
stack.append(10)
stack.append(11)
print stack#result: [7,8,9,10,11]
stack.pop()
print stack#result: [7,8,9,10]

队列的思想是第一个最先进入的元素最先取出，虽然列表的append（）和pop（）也可以实现此目的。但是列表用作此目的的效率不高。这是因为列表末尾插入元素效率高但开头弹出元素的效率却很低（所有其他元素都必须后移一位）。如果要实现一个队列，可以使用collections.deque，他设计的目的就是能够在两端快速添加和弹出元素。例子见代码清单2-11。

代码清单2-11 deque队列

print "deque用作队列
"
from collections import deque
queue = deque([7,8,9])
queue.append(10)          # 末尾插入元素
10
queue.append(11)          # 末尾插入元素
11
print queue.popleft()     # 开头弹出元素
7
print queue.popleft()     # 开头弹出元素
8
print queue
# result: deque([9, 10, 11])

*代码详见：示例程序/code/2-4-1.py

2.4.2 字符串

字符串（String）是序列的一种，支持其中索引的操作。实际上，字符串是单个字符的序列，简单地理解，字符串是多个单个字符合并而来的。在所有编程语言中，字符串都是最基本的数据结构之一。在Python之中，字符串灵活的方法大大简化了程序。

1.创建字符串

虽然字符串和列表都可以通过[]来访问其中的有序数据，但是字符串具有不可变性 ，每个字符一旦创建，不能通过索引对其做任何修改。字符串与列表一样，支持索引 和切片 。创建字符串最简单的是用单引号或双引号，这两种方法几乎没有区别。如果你的字符串内有单引号，那么创建字符串时就可用双引号避免歧义，反之亦然。字符串支持跨行，一种常用的方法是使用三引号：'''…'''或者"""…"""。行尾换行符会被自动包含到字符串中，但可以在行尾加上“\”来避免这个行为。代码例子见代码清单2-12。

代码清单2-12 创建字符串

print '''创建字符串
'''
str1 = 'learn Python'
print str1,str1[0],str1[-1] #输出整个字符串
,第一个字符，最后一个字符
# result:learn Python,l,n
print str1[:6]  #切片
# result:learn
# str1[0] = 'h' 程序报错，不允许修改字符串
print '-'*70
print '"Hello,my name is Mike"' #当字符串中有双引号，最好用单引号创建
# result:"Hello,my name is Mike"
print 'doesn\'t'  #如果用单引号创建有单引号的字符串，字符串中的单引号前加上
\
# result:doesn\'t
print '-'*70
str2 = '''Python具有丰富和强大的库。它常被昵称为胶水语言，
能够把用其他语言制作的各种模块（尤其是
C/C++）很轻松地联结在一起。
常见的一种应用情形是，使用
Python快速生成程序的原型（有时甚至是程序的最终界面），
然后对其中有特别要求的部分，用更合适的语言改写。
'''
print str2
str3 = '''Python具有丰富和强大的库。它常被昵称为胶水语言
,\能够把用其他语言制作的各种模块（尤其是
C/C++）很轻松地联结在一起。
常见的一种应用情形是，使用
Python快速生成程序的原型（有时甚至是程序的最终界面），
\然后对其中有特别要求的部分，用更合适的语言改写。
\
'''
print str3
# 输出太长这里就不展示了，请读者动手运行感受
str2与
str3的不同
print '-'*70

*代码详见：示例程序/code/2-4-2.py

如果你的字符串包含了特殊字符，如换行符“\n”，制表符“\t”，Python默认会自动识别并转义。如果你想使用不经转义的原始字符串，须在字符串前面加r，见代码清单2-13。

代码清单2-13 特殊字符转义

print 'E:\note\Python.doc'  #\n会被当作换行符处理
# result:E:
#       ote\Python.doc
print r'E:\note\Python.doc' #字符串前加
r，所以特殊字符失效
# result:E:\note\Python.doc

*代码详见：示例程序/code/2-4-2.py

Python可用“+”合并字符串，用C++语言说，Python重载了“+”运算符，这使得字符串的合并相当方便。Python支持格式化字符串，“%”的左侧放置一个字符串，简单的格式化字符串，而右侧则放置希望格式化的值，一般会使用元组（后面会详细介绍）。由于这个功能不太重用，本书只举一些简单的例子，如代码清单2-14所示。

代码清单2-14 “+”运算符及格式化字符串

str4 = 'String\t' 
str5 = 'is powerful'
str4 = str4+str5
# 不会报错，实际上这不是修改
str4，而是先消去现有的
str4，再用
"+"返回的新的合并后的字符串去重新创建
str4
print str4
# result:String is powerful
print '-'*70
format_str1 = 'There are %d apples %s the desk.' # %d表示整数而
%s表示字符串
a_tuple = (2,'on')
print format_str1 % a_tuple
# result:There are 2 apples on the desk.
format_str2 = 'There are {0} apples {1} the desk.'.format(3,'on')
print format_str2   #这是另一种写法，更简便
# result:There are 3 apples on the desk.

*代码详见：示例程序/code/2-4-2.py

2.字符串方法

Python字符串方法众多，能够满足程序员的各种要求。表2-7仅仅列出一些读者必须掌握的最重要的方法，相应的例子见代码清单2-15。值得注意的是，count和join方法在列表和字符串中都存在，且功能类似。实际上序列都会有共通的方法，读者在学习的时候要注意系统归类。

表2-7 字符串方法

代码清单2-15 字符串方法

print '''字符串方法
'''
str6 = "Zootopia"
print str6.find('to')# 返回第一个
to的索引，注意
str6[3]='t',str6[4]='o'
# result：
3
print '-'*70
str6_2 = "Z o o t o p i a"print str6_2.split() # 利用空格符分隔开字符
#result: ['Z', 'o', 'o', 't', 'o', 'p', 'i', 'a']
print ''.join(str6_2.split()) # 再通过
join函数又可以还原
# result: Zootopia
print '-'*70
str7 = '54321'
print '>'.join(str7) # 上一个例子是列表的
join，这个是字符串的
join,功能类似
# result: 5>4>3>2>1
print '-'*70
str8 = '"Yes!",I answered.'
print str8.split(',')# split()可以指定一个字符作为分隔符
# result:['"Yes!"', 'I answered.']
# 如果想把多个字符作为分隔符，可用下面这个方法
sep=['!',',','.',""]
for i in sep:
    str8 = str8.replace(i,' ')# 将全部分隔符替换为空格
print str8.split() # 成功提取句子中的所有单词
# result:['Yes', 'I', 'answered']
print '-'*70
str9 = 'A apple'
print str9.count('A') # 注意区分大小写
# result: 1
str9 = str9.lower()
print str9.count('a')
# result: 2
print '-'*70
str10 = '12345'
print str10.isalnum()
# result: True
print '-'*70

*代码详见：示例程序/code/2-4-2.py

3.Unicode字符串

Unicode是一种存储文本数据的类型。Python能够使用Unicode对象来存储和处理Unicode数据。Unicode对象与其他字符串对象有良好的集成，必要时提供自动转换。Unicode的优点在于为现在和古代的每一种字符（包括英文字符和中文字符等）提供了统一的序号。在Unicode出现之前，脚本只有256个可用的字符编码。各国的文字需要映射到字符编码上，这带来了很多麻烦，尤其是软件国际化。Unicode为所有脚本定义了一个代码页，从而解决了这些问题。

创建Unicode字符串只需要在字符串前加u即可。在代码清单2-16中，由于“你”的Unicode的编码是4f60，“好”的Unicode编码是597d，我们可以看到输入print u'\u4f60\u597d'就可以看到中文的“你好”。

在Python，将Unicode转化为比较有名的编码如ASCII、utf-8、utf-16以及中文的gbk编码都是很方便的。encode（）函数能够将Unicode字符串转换为指定编码的字符串，decode（）或unicode（）函数又可以反过来将指定编码的字符串转换为Unicode字符串，例子见代码清单2-16。

代码清单2-16 Unicode字符串

print '''Unicode字符串
'''
unicode_str =  u'\u4f60\u597d'
print unicode_str #"你好
"的
Unicode编码
# result: 你好
utf8_str = unicode_str.encode('utf-8')
print utf8_str
# 注意
"你好
"的
utf-8编码为
'\xe4\xbd\xa0\xe5\xa5\xbd'(在
Python Shell中直接输入
utf8_str会显示这个编码
)
# 但是
print()函数不会自动解码，所以直接输出为乱码
print utf8_str.decode('utf-8')
# result: 你好
print unicode(utf8_str,'utf-8') #这两种方法一样
# result: 你好

*代码详见：示例程序/code/2-4-2.py

2.4.3 元组

元组 （Tuple）与列表和字符串一样，是序列的一种。而元组与列表的唯一不同是元组不能修改，元组和字符串都具有不可变性 。

1.创建元组

元组没有固定的数据类型约束，它们编写在圆括号中而不是方括号中，它们支持常见的序列操作。元组有很多与列表相同的方法，但必须留意的是，append（）和pop（）等修改大小和内容的函数是元组不允许的，如代码清单2-17所示。

代码清单2-17 创建元组

print '''元组
'''
tuple1 = ('A','我
')
print len(tuple1)
# result: 2
tuple2 = tuple1+(6,6,'的
')
print tuple2
# 注意
"我
"在机子系统中的中文默认编码是
cp936，可以使用
'中文
'.decode('cp936')转为
Unicode编码
# result:['A', '\xce\xd2', 6, 6, '\xb5\xc4']
tuple1 = ('A','我
'.decode('cp936'))
print tuple1
# result：
 ('A', u'\u6211')
tuple3 =(1,)          # 创建仅有一个数据的元组
print tuple3
# result:(1,)
tuple4 = 3*(1+5,)          # 一个逗号完全改不了表达式的值
print tuple4
# result: (6, 6, 6)
print tuple(list(tuple4))     #tuple函数可以将其他序列类型转变为元组
# result: (6, 6, 6)
print tuple4[0]          # 同样可以使用索引
tuple4[0] = 7          #错误，不能改变元组的数据
print tuple4.count(6)     # 同样有
count()函数
# result: 3

*代码详见：示例程序/code/2-4-3.py

2.元组的必要性

读者可能会存在这样的疑惑：既然有列表的存在，为什么还需要像元组那样的不可变序列？在初学编程语言的人看来，不可变似乎是一种缺陷。但是，元组的不可变性是关键，从某个角度说是它的天然优势。例如Python的字典（后面会详细介绍）允许元组和字符串作为键值，但不允许列表作为键值。原因就是元组和字符串的不可变性，字典的键值是必须保证唯一的，如果允许修改键值，那么唯一性就无法保证。元组提供了一种完整性 约束，这对于大型程序的编写是很重要的。有时候程序员不希望程序中的某个值被修改，为了避免我们不经意地修改这些内容（实际上在大型程序中经常发生），就应该使用元组而非列表。

2.4.4 字典

字典 （Dictionary）是基础数据结构映射 （Mapping）的一种。序列是按照顺序来存储数据的，而字典是通过键存储数据的。字典的内部实现是基于二叉树 （Binary Tree）的，数据没有严格的顺序。字典将键映射到值，通过键来调取数据。如果键值本来是有序的，那么我们不应该使用字典，如映射： 直接用列表['A'，'B'，'C']即可，字典的效率比列表差得多。但是在很多情形下，字典比列表更加适用。比如我们手机的通讯录（假设人名均不相同）可以使用字典实现，把人的名字映射到一个电话号码，名字是无序的，所以不能直接用一个列表实现。

1.字典的创建与操作

字典最基本的创建方式是：

category = {'apple':'fruit','Zootopia':'film','football':'sport'}

字典内部是一系列的“键：值”对，一组中的键与值用“：”分隔开，不同组的键值对用“，”分割开，整个字典用大括号括起来。上面的例子创建了一个所属类别的字典。字典是无序的，键值与声明的顺序没有关系。另外一种常用的创建字典方法是使用元组和dict（）函数，例子见代码清单2-18。空字典直接用{}创建即可。

字典的基本操作非常简单，假定有字典D：

1）查询键值对D[key]并返回键key关联的值。

2）修改键值对D[key]=new_value，将值new_value关联到key上。

3）插入键值对D[new_key]=new_value，如果字典中不存在键new_key，如此操作便增加了键值对。

4）删除键值对del D[key]，删除键为key的键值对。

代码清单2-18 字典的创建与操作

print '''字典创建与操作
'''
category = {'apple':'fruit','Zootopia':'film','football':'sport'}
print category['apple']     # 查询键值对
# result: fruit
category['lemon'] = 'fruit'     # 插入新的键值对
print category
# result: {'Zootopia': 'film', 'lemon': 'fruit', 'apple': 'fruit', 'football': 'sport'}
del category['lemon']     # 删除键值对
print category
# result: {'Zootopia': 'film', 'apple': 'fruit', 'football': 'sport'}
print '-'*70
items=[('height',1.80),('weight',124)]     # 也可以通过元组和
dict()创建字典
D = dict(items)
print D
# result: {'weight': 124, 'height': 1.8}
print '-'*70

*代码详见：示例程序/code/2-4-4.py

2.字典的遍历

尽管字典是无序的，但是有时候我们需要将它按照一定的规则打印出来。一个经典的办法是首先获取字典所有键，并将它们存储在列表中，然后对列表按照某种偏序关系 进行排序，最后按排序后的结果逐一对字典进行查询并打印。代码清单2-19显示了按照不同的偏序关系对字典进行遍历的结果。

代码清单2-19 字典的遍历

print '''字典的遍历
'''
keys = category.keys()
keys.sort()
print keys  # 按照首字符的
ASCII码排序
# result: ['zootopia', 'football', 'apple']
keys.sort(reverse=True)
print keys  # 排序结果反转
# result: ['zootopia', 'football', 'apple']
# result:
def comp(str1,str2):     # 两个字符串的比较函数
    if str1[0]<str2[0]:     # 如果
str1的首字符比
str2首字符的
ASCII值小，那么
str1排在
str2前，否则排在后面
        return 1
    else:
        return -1
keys.sort(comp)     #自定义偏序关系，同样实现反向排序
print keys
# result: ['zootopia', 'football', 'apple']
for key in keys:     #最后按照反向排序的顺序打印字典
    print (key,'=>',category[key])
# result:
# ('zootopia', '=>', 'film')
# ('football', '=>', 'sport')
# ('apple', '=>', 'fruit')

*代码详见：示例程序/code/2-4-4.py

2.4.5 集合

Python有一种特殊的数据类型称为集合 （Set）。之所以称它特殊，是因为它既不是序列也不是映射类型，更不是标量。集合是自成一体的类型。集合是唯一的，不可变的对象是一个无序集合。集合对象支持与数学理论相对应的操作，如并和交，这也是这种数据类型被创建的最重要的目的。

1.创建集合

创建一个集合很简单，只要在声明集合时把集合的元素包含在大括号内，并用逗号分隔。还有一种方法是使用set（）函数，通过一个列表或元组创建集合，见代码清单2-20。

代码清单2-20 创建集合

# -*- coding:utf-8 -*-
print '''创建集合
'''
set1 = {1,2,3}          # 直接创建集合
set2 = set([2,3,4])     # set()创建
print set1,set2
# result: set([1, 2, 3]) set([2, 3, 4])

*代码详见：示例程序/code/2-4-5.py

2.集合的操作

集合能够通过表达式操作符支持一般的数学集合运算，如表2-8所示（假设集合x=set（[1，2，3]），y=set（[2，3，4]）。这是集合特有的操作，序列和映射不支持这样的表达式。

表2-8 集合运算

除此之外，集合还有一些常用的方法，见表2-9。由于这些方法都比较简单，本书不再赘述。值得提醒的是，如果集合中已经有元素a，使用add（）函数或其他方法向集合再次插入元素a，Python不会报错，但集合依然只有一个a，集合中的元素都是唯一的。

表2-9 集合的方法