本节书摘来自华章出版社《python 与数据挖掘 》一书中的第2章，第2.4节，作者张良均　杨海宏　何子健　杨　征，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4　数据结构

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　列表函数说明

函数名称 函数说明list.append(x) 添加一个元素到列表的末尾，相当于a[len(a):]=[x]list.extend(L) 将参数中的列表添加到自身的列表的末尾，相当于a[len(a):]=Llist.insert(i，x) 在下标为i的元素位置前插入一个元素，所以a.insert(0，x)相当于a.append(x)list.remove(x) 删除列表第一个值为x的元素。如果没有这样的元素会报错list.pop([i]) 删除列表指定位置的元素并返回它。[]表示这个参数是可选的，如果不输入这个参数，将删除并返回列表最后一个元素list.index(x) 返回列表第一个值为x的元素的下标。如果没有这样的元素会报错list.count(x) 返回列表中x出现的次数list.sort(cmp=None，key=None，reverse=False) 排序列表中的元素，可参考2.4.4节字典遍历的代码，里面讲述了一个使用sort()函数的例子list.reverse() 反转列表中的元素

代码清单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:notePython.doc' #n会被当作换行符处理

result:E:

otePython.doc

print r'E:notePython.doc' #字符串前加r，所以特殊字符失效

result:E:notePython.doc

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

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

str4 = 'Stringt' str5 = 'is powerful'str4 = str4+str5

不会报错，实际上这不是修改str4，而是先消去现有的str4，再用"+"返回的新的合并后的字符串去重新创建str4

print str4

result:String is powerful

print '-'*70format_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　字符串方法 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/68e1fef8b2562fa3d8fc85f98fb7bce310f64313.png" > </div> <br/> 函数名称 函数说明 S.find(sub,[,start[,end]]) 返回在字符串中找到的子字符串sub的最低索引，使得sub包含在切片s[start:end]中，如果未找到sub，则返回-1 S.split([sep[,maxsplit]]) 返回字符串中的单词列表，使用sep作为分隔符字符串。如果给出maxsplit，则至多拆分maxsplit次（因此，列表中将最多有maxsplit+1个元素）。如果没有指定maxsplit或为-1，那么分割的数量没有限制（进行所有可能的分割） S.join(iterator) 连接字符串数组。将字符串、元组、列表中的元素以指定的字符（分隔符）连接生成一个新的字符串 S.strip([chars]) 返回字符串的一个副本，删除前导和尾随字符。chars参数是一个字符串，指定要移除的字符集。如果省略或为None，则chars参数默认为删除空白字符 S.lower() 将字符串中所有大写字符变为小写 S.isalnum() 如果字符串中至少有一个字符，并且所有字符都是数字或者字母，则返回true，否则返回false S.count(sub[,start[,end]]) 返回在[start, end]范围内的子串sub非重叠出现的次数。可选参数start和end都以切片表示法解释 S.replace(old,new[,count]) 返回字符串的一个拷贝，其中所有的子串old通过new替换。如果指定了可选参数count，则只有前面的count个出现被替换 代码清单2-15　字符串方法

print '''字符串方法'''str6 = "Zootopia"print str6.find('to')# 返回第一个to的索引，注意str6[3]='t',str6[4]='o'

result：3

print '-'*70str6_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 '-'*70str7 = '54321'print '>'.join(str7) # 上一个例子是列表的join，这个是字符串的join,功能类似

result: 5>4>3>2>1

print '-'*70str8 = '"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 '-'*70str9 = 'A apple'print str9.count('A') # 注意区分大小写

result: 1

str9 = str9.lower()print str9.count('a')

result: 2

print '-'*70str10 = '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'u4f60u597d'print unicode_str #"你好"的Unicode编码

result: 你好

utf8_str = unicode_str.encode('utf-8')print utf8_str

注意"你好"的utf-8编码为'xe4xbdxa0xe5xa5xbd'(在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', 'xcexd2', 6, 6, 'xb5xc4']

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 '-'*70items=[('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　集合运算 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/a943976d2e8fe8422f6cf692a3516e517df20f29.png" > </div> <br/> 表达式 结果 意义 x-y set（[1]） 集合的差，返回包含在x且不包含在y中的元素集合 x|y set（[1，2，3，4]） 集合的并，返回包含在x或y中的元素集合 x&y set（[2，3]） 集合的交，返回既包含在x也在y的中的元素的集合 x^y set（[1，4]） 集合的异或，返回只被x包含或只被y包含的元素的集合 x>y False 如果x真包含y，则返回True，否则返回False 除此之外，集合还有一些常用的方法，见表2-9。由于这些方法都比较简单，本书不再赘述。值得提醒的是，如果集合中已经有元素a，使用add()函数或其他方法向集合再次插入元素a，Python不会报错，但集合依然只有一个a，集合中的元素都是唯一的。 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/ae7ed036bb58214a3ca9a4f78a6d0eac69041933.png" > </div>