导语：本文章记录了本人在学习Python基础之数据结构篇的重点知识及个人心得，以加深自己的理解。
本文重点：
1、了解列表、元组、字节序列、数组等数据结构；
2、了解上述数据结构相对应的迭代、切片、排序、拼接操作；
3、如果想把代码写的Pythonic，在保证代码可读性的前提下，代码行数越少越好。
一、内置序列类型概览
- 容器序列：list、tuple、collections.deque
- 扁平序列：str、bytes、bytearray、memoryview、array.array
- 可变序列：list、bytearray、array.array、collections.deque、memoryview
- 不可变序列：tuple、str、bytes
容器序列能够存放不同类型的数据，比扁平序列更灵活；
扁平序列只能存放一种类型的原子性的数据，体积更小速度更快。eg：数字，字符字节
二、列表推导（list comprehension）和生成器表达式（generator expression）
1、列表推导：在[]中使用命令语句加for甚至if实现迭代推导出新列表的操作。
列表推导运用得当将使得代码清晰优雅。
Python3中不存在Python2的列表推导变量泄漏问题，即列表推导中的局部变量与主程序的同名变量引用冲突问题。
eg1:利用ord()把单词apple的ASCII码以列表存起来。
list_a=[ord(x)for x in "apple"]#ord()是返回字符对应ASCII码的函数。
print(list_a)#输出：[97, 112, 112, 108, 101]eg2:使用列表嵌套循环求笛卡尔积。
Clothes=["T-shirt","sweater"]
Color=["red","yellow","blue"]
Product=[(x,y)for x in Clothes for y in Color]#嵌套循环
print(Product)#输出：[('T-shirt', 'red'), ('T-shirt', 'yellow'), ('T-shirt', 'blue'), ('sweater', 'red'), ('sweater', 'yellow'), ('sweater', 'blue')]句法提示：Python会忽略[ ],{ },( )中的换行符" "，把括号内的多行内容视为一行。因此可在列表、列表推导、字典、生成器表达式中省略换行符。
2、学习生成器表达式应先了解的概念：
迭代器协议：对象必须提供next方法，执行该方法会返回迭代中的下一项，直到引起stopiteration停止迭代。
可迭代对象：实现迭代器协议的对象（实现方法：对象内部定义__iter__方法）任何可迭代对象都可以使用for循环。由此看出Python的for循环抽象程度高于Java。
使用Iterable判断一个对象是否可迭代：
from collections import Iterable
print(isinstance("apple", Iterable))#True可迭代
print(isinstance(100, Iterable))#False不可迭代3、生成器表达式：按需返回一个结果对象，而非先构建一个完整的列表。表达方法：语句格式与列表推导类似，但须在圆括号()中书写。特点：按需产值，延迟计算，节省内存，在生成大规模序列类型具备优势。
eg1:用生成器表达式初始化元组
tuple_a=(ord(x)for x in "apple")
for i in tuple_a:
print(i)eg2:用生成器表达式初始化数列
from array import array
ascii=array('I',(ord(x)for x in "apple"))
for i in ascii:
print(i)eg3:用生成器表达式计算笛卡尔积
Clothes=["T-shirt","sweater"]
Color=["red","yellow","blue"]
tuple_Product=((x,y)for x in Clothes for y in Color)
for i in tuple_Product:#生成器表达式是按需产值，无法用print直接一次性输出，需要配合for迭代输出
print(i)三、元组功能
元组有两重功能，一是当作记录来用的数据模型，二是充当不可变的列表，
1、用作记录：
元组用作记录时，可以理解为数据+位置。之所以提位置是因为有序的位置赋予了数据独特的意义。如果此时对元组进行排序等打乱位置的操作，会使得元组丢失原本所携带的信息。
Traveler_ids=[("hoya","85236669"),("Dennis","O7856P77"),("Sky","L336636")]
for i in Traveler_ids:
print("%s/%s"%i)#平行赋值，元组拆包
#输出：
hoya/85236669
Dennis/O7856P77
Sky/L336636 for name,_ in Traveler_ids:#对于拆包中不感兴趣的一类元素可以用占位符“_"
print(name)
#输出：
hoya
Dennis
Sky2、元组拆包：从元组中按位置顺序提取元素。
元组拆包可以应用到任何可迭代对象上，唯一的硬性要求是，被可迭代对象中的元素数量必须与接受这些元素的元组的空挡数一致。
t=(9,4)
print(divmod(*t))#利用*可以把一个可迭代对象拆开作为函数的参数，输出为(2, 1)
a=3
b=5
a,b=b,a#不使用中间变量实现值的交换
print(a,b)用*来处理剩下的元素：星号*可以把不确定参数装到一起。注意在平行赋值中，星号*只能用在一个变量名前面，但是这个变量可以出现在赋值表达式的任意位置。
a,b,*rest=range(5)
print(a,b,rest)#输出为：0 1 [2, 3, 4]
a,*rest,b=range(5)
print(a,rest,b)#输出为0 [1, 2, 3] 43、嵌套元组拆包要求：接受元组的嵌套结构符合表达式本身的嵌套结构
format函数输出一般格式：.
一般格式[fill,align,sign,0,width,.precision,type],每一处都是可选的.
- fill，冒号+填充字符。填充字符可选,用于填充空白,默认为空格;
- align,对齐方式.<,>,^分别代表左,右,居中对齐,默认为右对齐;
- sign,取值为:
- +,所有数字签名都要加上符号;
- -,默认值,只在负数签名加符号;
- 空格,在正数前面加上一个空格;
- 0,在宽度前面加0表示用0来填充数值前面的空白;
- width,宽度;
- .precision,精度的位数（注意前面有小数点".")
- type,数据类型,如d(整数),s(字符串)等
format函数字符串映射方式：
- 通过位置
print("{1}|{2}|{1}".format("a","b","c"))#通过位置填充。输出：b|c|b
print("{}|{}|{}".format("a","b","c"))#也可以不填写位置索引，默认按照顺序填充。输出：a|b|c- 通过关键字
print("{Greeting},My name is {name}".format(Greeting="Hello",name="Hoya"))
#输出：Hello,My name is Hoya
Fruit_number={"apple":15,"pear":10,"strawberry":20}
print("We have {x[apple]} apples,{x[pear]} pears,and {x[strawberry]} strawberries.".format(x=Fruit_number))#字典的key也能填充字符串。注意x是局部变量！
#输出：We have 15 apples,10 pears,and 20 strawberries.- 通过下标
Friends=["Daniel","Dennis"]
print("I have two best friends,one is {x[0]},the other is {x[1]}".format(x=Friends))
#输出：I have two best friends,one is Daniel,the other is Dennis本质上是位置索引，因为传入的对象非具体元素而是列表，故用下标填充。
- 通过对象属性
class Students:
def __init__(self,x,y):
self.x=x
self.y=y
def __str__(self):
return "Hello,My name is {self.x},I come from {self.y}".format(self=self)
print(Students("Hoya","China"))#传入类，把类的属性值填充到字符串中format&嵌套元组实例综合运用：
cities=[("New York","USA",(40.8086,-74.0204)),
("Mexico City","Mexico",(19.4333,-99.1333)),
("Tokyo","Japan",(35.6899,169.3254)),
("Sao Paul","USA",(-23.5478,-46.6358))]
print("{:15}|{:^9}|{:^9}".format("","lat","long"))
x="{:15}|{:^9.2f}|{:^9.2f}"#对经纬度小数点后保留两位数字
for city,_,(lat,long) in cities :#平行赋值，对应结构一致。
if long < 0:
print(x.format(city,lat,long))#输出如下：
| lat | long
New York | 40.80 |-74.02
Mexico City | 19.43 |-99.13
Sao Paul |-23.54 |-46.63namedtuple:具名元组，来自标准库中的collections模块中的方法。它可以构建一个带字段名的元组和一个有名字的类。特点：能够直接使用名字访问元素。
注意：
- 创建namedtuple需要两个参数，第一个参数是类名，二是类字段的名字。后者可以是数个字符串组成的可迭代对象，或者由空格分开的字段名组成的字符串。
- 存储到类字段的数据要以一串参数的形式传入到构造函数中。
- 可以通过字段名或者位置读取字段信息。
与tuple相同，namedtuple属性不可变！
namedtuple属性与方法：
- _fields类属性：返回这个类包含所有字段的元组
- _make(iterable)类方法：接受一个可迭代对象来生成这个类的实例
- _asdict()实例方法：以collections.OrderedDict的形式返回一个有序词典
应用实例：
from collections import namedtuple
Star=namedtuple("Star", "name country coordinates age")
hoya=Star("Hoya","China",(20,30),18)
print(hoya.name)#读取信息的两种方式
print(hoya[0])
print(Star._fields)
Jack_data=("Jack","Russia",(100,36),14)
# Jack=Star(*Jack_data)#此方法与_make(iterable)类方法效果相同
Jack=Star._make(Jack_data)
print(Jack.age)
print(Jack._asdict())
for key,value in Jack._asdict().items():#字典内置方法items()而非item()
print(key+":",value)#加号前后字符类型一致4、用作不可变列表：
元组除了不支持增减，逆序，就地修改等直接或间接改变元素信息及位置的方法之外，支持列表其他的所有方法。
由于方法过多不便展示，详情参考Fluent Python P27以及Python基础教程笔记列表方法。
四、切片
1、切片和区间忽略最后一个元素的原因：
- Python和C以0作为起始下标。当只有最后一个位置信息时，可以快速看出切片中有几个元素。eg:range(3)有3个元素
- 已知切片区间的起止位置后，通过stop-start能快速计算出切片和区间的长度。
- 如此可以利用任意一个下表把序列分割成不重叠的两部分。eg:list[:x]和list_2[x:]
2、多维切片和省略
- 多维切片:对一维切片推广到多维。在numpy中会用到多维切片。eg:a[m:n,u:v]
- 省略：切片规范的一部分。eg:x[m,...]等价于x[m, :, :, :]
3、切片赋值
切片一般格式s[a:b:c],c取值为负意味着反向取值。
注意：如果赋值对象是切片，赋值号另一端的对象也必须是可迭代对象。即使单独一个值，也要把它转换成可迭代的序列。
反例：
list1=[1,3,6,9,10]
list1[1:3]=2#正确形式：list1[1:3]=[2]
Traceback (most recent call last):
File "F:\xuexi\Fluent Python\section 2-4.py", line 3, in <module>
list1[1:3]=2
TypeError: can only assign an iterable#切片右端必须是可迭代对象。五、其它数据结构
列表尽管具有灵活简单的特点，但并不能适用于各种需求，为此我们要寻找更好的选择。下面介绍三种在某些情况下可以替换列表的数据类型。
1、数组：
如果我们需要一个只包含数字的列表，那么array.array比list更高效。
构造数组的一般格式：array(typecode，[ initializer])
typecode指数组类型，常用的如下：initializer类似列表推导
| Type code | C Type | Python Type | Minimum size in bytes |
|---|---|---|---|
| 'b' | signed char | int | 1 |
| 'B' | unsigned char | int | 1 |
| 'i' | signed int | int | 2 |
| 'I' | unsigned int | int | 2 |
| 'l' | signed long | int | 4 |
| 'L' | unsigned long | int | 4 |
| 'f' | float | float | 4 |
| 'd' | double | float | 8 |
数组方法：数组支持所有跟可变序列有关的操作，可参考Fluent Python P42以及array的Python官方library.数组从Python3.4开始不支持诸如list.sort()这种就地排序的方法。另外数组提供读写文件更快的方法，如.frombytes和.tofile
eg:综合运用
from random import random
from array import array
array1=array("d",(random()for x in range(10^5)))#构建数组
fp=open("array1.bin","wb")#以二进制形式存储文件
array1.tofile(fp)#打开文档导入数据
fp.close()#关闭文档
print(array1[-1])
array2=array("d")
fp=open("array1.bin","rb")
array2.fromfile(fp, 10^5)
fp.close()
print(array2[-1])
print(array1==array2)#输出True，说明存取无误。2、双向队列
collections.deque类（双向队列）是一个线程安全、可以快速从两端添加或者删除的数据类型。
deque构造：deque([initializer],maxlen=some_number)#传入初值和maxlen参数。初值可在中括号中，也可采取类似列表推导的方法；maxlen限制deque的元素数量，选填。
deque方法：
- 增
extend() 一次性从右端添加多个元素
append() 从右端添加一个元素
extendleft() 从左端添加多个元素，注意是逆序输入（因为是逐个迭代插入的关系）
appendleft() 从左端添加一个元素 - 删
pop() 从右端移除元素
popleft() 从左端移除元素
注意，deque是线程安全的，所以可以在不同的线程中同时从两端移除元素。 - 旋转与统计
rotate(n)
当参数为正整数n时，rotate()将向右移动n位，并将队列右端的n个元素移到左端，当参数为负数-n是，rotate()将向左移动n位，并将队列左边的n个元素移动到右边。
count(e):统计队列中某个元素的个数。
To learn more:参考 Python标准library和Fluent Python P48
eg：
from collections import deque
deque1=deque([x*x for x in range(3)],maxlen=5)
print(deque1)#deque([0, 1, 4], maxlen=5)
deque1.extendleft([9,16,25])#队列满元素后，一端添加的元素会使得另一端删除同等数量的元素保持maxlen不变
print(deque1)#deque([25, 16, 9, 0, 1], maxlen=5)
deque1.rotate(-3)
print(deque1)#deque([0, 1, 25, 16, 9], maxlen=5)
deque1.popleft()
print(deque1)#deque([1, 25, 16, 9], maxlen=5)deque实现了大部分列表所拥有的方法，具有灵活多用和线程安全的特点；但deque从中间删除元素的操作会慢一些。注：deque不支持切片操作（个人实践经验）
3、内存视图
memoryview其实是泛化和去数学化的NumPy数组。
它让你在不需要复制内容的前提下在数据结构之间共享内存；数据结构可以是任何形式。
六、其它知识
1、初始化嵌套列表
list1=[["_"]*3 for x in range(3)]
list2=[["_"]3]3
list11=1
list21=1
print(list1)#[['_', '_', '_'], ['_', 1, '_'], ['_', '_', '_']]
print(list2)#[['_', 1, '_'], ['_', 1, '_'], ['_', 1, '_']]
上文代码是两种初始化嵌套列表的方式，仔细观察发现list2的赋值后在3个子列表中均有赋值，这是错误的初始化方法。原因在于list2初始化的子列表引用一致，这种列表往往不是我们想要的结果。
教训：a*n语句中，如果序列a的里的元素是对其他可变对象的引用，就需要额外当心。原因是会产生指向同一个可变对象的多次引用！
2、元组嵌套列表的两点问题
- 不要把可变对象放到列表中
- 增量赋值不是原子操作
原子操作：不会被线程调度机制打断的操作，一旦执行将运行到结束。
3、list.sort和sorted
- list.sort是就地排序，返回None。返回none的原因是提示你此方法不会新建列表，让调用者知道传入的参数发生了改动，这其实是Python的一个惯例。
- sorted与之相反。它接受任何形式的可迭代对象作为参数，返回一个列表。
- 两者都有两个参数供选择。一是reverse，默认False升序排列，设定为True会降序输出；二是key,设置比较的关键字参数。
eg:
cities=["New York","Mexico City","Tokyo","Sao Paul"]
print(sorted(cities,key=len,reverse=True))#['Mexico City', 'New York', 'Sao Paul', 'Tokyo']
cities.sort(reverse=True)
print(cities)#['Tokyo', 'Sao Paul', 'New York', 'Mexico City']sorted一般格式：
sorted(iterable,[,key[,reverse=True]]])eg:
students = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 13)]
print(sorted(students, key=lambda s: s[0]))#lambda是匿名函数；s(0)代表把可迭代对象中待排序元素中的第一个元素取出比较排序，这里是诸如"john"的英文字符串。
#输出：[('dave', 'B', 13), ('jane', 'B', 12), ('john', 'A', 15)]4、bisect模块：利用二分查找算法管理已排序的序列
bisect.bisect(haystack,needle):返回一个在haystack中插入needle保持序列升序的位置。
bisect.insort(seq,item):返回一个在seq中插入item保持序列升序的新序列。
bisect和insort一样，可以额外填写lo和hi两个参数控制
To learn more:https://docs.python.org/3/lib...
eg:
import bisect
list3=[1,3,5,7,9]
s=8
print(bisect.bisect(list3,s))#输出：4
bisect.insort(list3,s)
print(list3)#输出：[1, 3, 5, 7, 8, 9]
