1. Python 内置数据结构
Python 内置了很多数据结构(容器), 供我们直接进行使用，在学习结构之前，有一些小的知识点进行补充。
1.1. 数值型
- int、float、complex、bool 都是 class（类），1、5.0、2+3j 都是对象即实例
- int：Python3 的 int 就是长整型，且没有大小限制，受限于内存区域大小
- float：有整数和小数部分组成。支持十进制和科学计数法表示。
- complex：复数，有实属和虚数部分组成，实数部分和虚数部分都是浮点数
- bool：int 的子类，仅有 2 个实例，True 和 False，其中 True 表示 1，False 表示 0
In : int(10.12) # 直接取整
Out: 10
In : int(-12)
Out: -12
In : float(10) # 转换为浮点数
Out: 10.0
In : float(-9)
Out: -9.0
In : bool(1) # 1 表示 True（非 0 都为 True)
Out: True
In : bool(0) # 0 表示 False
Out: False
1.2. math 模块
数学之中，除了加减乘除四则运算之外，还有其它更多的运算，比如乘方、开方、对数运算等等，Python 提供了一个专门辅助计算的模块：math, 模块方法及常量如下：
-
math.ceil：向上取整（天花板除） -
math.floor：向下取整（地板除） -
math.pi：数字常量，圆周率 -
math.pow(x, y)：返回 x 的 y 次方，即 x**y -
math.sqrt(x)：求 x 的平方根
In : import math # 导入模块
In : math.pi
Out: 3.141592653589793
In : math.pow(2,3) # 2**3
Out: 8.0
In : math.ceil(-10.6) # 往数轴右边取整
Out: -10
In : math.ceil(12.3)
Out: 13
In : math.floor(12.3) # 往数轴左边取整
Out: 12
In : math.floor(-12.3)
Out: -13
In : math.sqrt(10)
Out: 3.1622776601683795
注意：
- int 取整：正负数都只取整数
- 整除(向下取整)
如下例所示：
In : int(-12.1) # 只会取整数部分
Out: -12
In : int(10.5)
Out: 10
In : 1 // 3 # 向下取整
Out: 0
In : 10 // 3
Out: 3
1.3. round 圆整
在 Python 中有一个 round() 函数，用于对小数进行取整，不过在 Python 中的 round() 有些特别，总结一句话就是 4 舍 6 入 5 取偶。即当小数点后面的数字 小于 5 会直接 舍去，大于 5 则会直接 进位，等于 5 则会 取数轴上距离最近的偶数。
In : round(1.2)
Out: 1
In : round(-1.2)
Out: -1
In : round(1.5)
Out: 2
In : round(-2.5)
Out: -2
In : round(0.5)
Out: 0
In : round(-5.5)
Out: -6
In : round(1.6)
Out: 2
In : round(-1.500001)
Out: -2
1.4. 常用的其他函数
-
max()：常用来在可迭代对象中求最大值 -
min(): 常用来在可迭代对象中求最小值 -
bin()：把对象转换为二进制 -
oct()：把对象转换为八进制 -
hex()：把对象转换为十六进制
1.5. 类型判断
由于 Python 是一种强类型语言，在数据比较时，只有相同数据类型，才可以进行比较。这时我们就需要知道对象到底是什么类型，type 就是用来查看类型的。
In : type('123')
Out: str
In : type(123)
Out: int
In : type(True)
Out: bool
从上面代码结果可以看出 type 返回的是类型，并不是字符串，而在数据判断时我们需要的是判断结果，比如判断某个变量是某个类型的，那么这个时候就需要用到 isinstance() 了。
# 基本用法
Signature: isinstance(obj, class_or_tuple, /) --> bool
# 接受两个参数，返回一个布尔值
# obj：要判断的对象
# class_or_tuple：一个类，或者多个类组成的元组
In : isinstance(123, str) # 判断 123 是 str 类型吗？
Out: False
In : isinstance(123, (str, int)) # 判断 123 是 str 或者 int 类型中的一种吗？
Out: True
2. 列表
列表是 Python 中最基本的数据结构。什么是序列呢？我们可以认为它是一个队列，一个排列整齐的队伍。列表内的个体称为元素，它可以是任意对象(数字、字符串、对象、列表)，多个元素组合在一起，使用逗号分隔，中括号括起来，就是列表。它有如下特点：
- 列表内的元素是 有序的，可以使用 索引(下标) 获取元素，第一个索引是 0，第二个索引是 1，依此类推。
- 线性的存储结构，从左至右依次存储
- 列表是可变的，我们可以对其内的元素进行任意的增删改查
创建一个列表，只要把逗号分隔的不同的数据项使用方括号括起来即可。如下所示：
In : a = [] # 空列表
In : b = list() # 空列表
In : c = list(range(3)) # 接受一个可迭代对象，转换为列表。[0, 1, 2]
注意：列表无法在初始化时就指定列表的大小
2.1. 索引访问
列表的索引有如下特点：
- 正索引：从左至右，从 0 开始，为列表中每一个元素编号
- 负索引：从右至左，从 -1 开始
- 正负索引不可以超界，否则会抛出异常 IndexError
- 为了理解方便，可以认为列表是从左至右排列的，左边是头部，右边是尾部，左边是下界，右边是上界
- 列表通过索引访问，例如：
list[index]，index 就是索引，使用中括号访问。
2.2. 列表和链表的区别
我们通常会把列表和链表拿来做对比，它俩虽然都是有序的可以被索引，但是内部实现方法以及适用场景有很大区别。
列表在内存中的存储方式是线性的，而链表是非线性的，他们的差别如下：
由上图我们可以得到如下结论：
- 列表：线性结构，顺序结构，可以被索引，数据存放的是连续的内存空间，取值时，只需要进行偏移量计算即可，属于一步到位型，但是在增删数据时，需要针对其后所有的数据进行移动，所以性能不高。
- 链表：线性结构，顺序结构，可以被索引，放数据的地方，在内存地址上并不是连续的。增删数据时，只需断开前后两个元素先前的连接，增加新元素后，建立新的连接即可，但由于其不连续的空间，索引起来效率低，需要从头开始寻找。
注意：列表的增删如果是在队伍当中，那么相对效率比较低，但是如果在尾部增删，效率很快。链表还分为单向和双向，表示索引方向
扩展： 下面是其他基于列表 / 链表特性的实现：
- queue：队列(一般是从队首或者队尾获取数据) 分为：
先进先出队列和先进后出队列及优先级队列 - stack：栈。后进先出的就被叫做栈(主要应用于函数的压栈)
2.3. 列表的查询
列表提供了很多的方法，使我们可以方便的对它进行查询、统计等操作。
# 基本用法
L.index(value, [start, [stop]]) --> integer
# 在列表中获取传入元素的索引值，如果元素不存在，会报异常，如果存在多个，只返回找到的第一个匹配元素的索引值，其中 start，stop 为表示查找区间，默认为整个列表
L.count(value) --> integer
# 统计传入元素在列表中出现的次数并返回
index 和 count 的时间复杂度都是 O(n), 都会遍历列表，即随着列表的规模增加，效率会依次下降。
什么是时间复杂度？这是在计算算法优劣时的主要参考值，我们主要使用大写的 O 来表示时间复杂度，由于 index 和 count 函数都需要遍历列表，所以如果这个列表有 n 个元素的话，那么它的时间复杂度就为 O(n), 详细的解释，建议自行搜索了解，这里知道这样表示即可。
由于 list[1] 通过偏移量进行快速数据访问，可以理解为一步到位，所以这种方式的时间复杂度为 O(1)，不会随着规模增大而改变。
In : lst
Out: [1, 2, 3, 1, 2, 3, 3, 2, 4, 5, 7]
In : lst.index(3) # 获取元素 3 的索引值
Out: 2
In : lst.count(2) # 统计元素 2 出现的次数
Out: 3
扩展： 如果我们要获取列表的元素总数，我们需要怎么设计呢？
- 设计一个获取元素总量的函数，当调用时，对列表进行遍历获取元素的总数，并返回值
- 设置一个计数器，随着元素的增加和减少对计数器进行修改
很明显第一个方法的时间复杂度是 O(n)，而第二个方法由于事先存储着列表元素的总数，所以它的时间复杂度是 O(1)，列表使用的就是方式 2，而通过 Python 内置的 len 函数 就可以获取列表内元素的个数(不仅仅针对列表，其他元素也可以)
In : lst
Out: [1, 2, 3, 1, 2, 3, 3, 2, 4, 5, 7]
In : len(lst) # 获取列表内元素的个数
Out: 11
2.4. 列表元素修改
我们使用索引可以获取列表中对应索引位置的元素，同时我们也可以通过索引直接将对应索引位的元素进行修改
In : lst
Out: [1, 2, 3, 1, 2, 3, 3, 2, 4, 5, 7]
In : lst[2] = 100
In : lst
Out: [1, 2, 100, 1, 2, 3, 3, 2, 4, 5, 7]
需要注意的是，索引不要越界，否则会报异常
2.5. 列表的追加和插入
列表提供了对其进行追加或插入的函数，即 append 和 insert。先来看看这两个函数的使用方法。
L.append(object) --> None # 接受一个元素，用于追加到列表的末尾。
L.insert(index, object) --> None # 接受两个变量：索引，元素。在列表中指定的索引位置插入元素。
说明：
- 列表尾部追加元素时，append 的返回值是 None，会直接对原列表进行操作（就地修改），对应的时间复杂度是 O(1)
- 列表插入元素时，与 append 相同，返回 None，直接对原列表进行操作（就地修改），对应的时间复杂度是 O(n), 因为在列表首部插入元素时，会使其他元素整体移动。当索引超界时会有如下两种情况
- 超越上界，尾部追加
- 超越下界，首部追加
In : lst
Out: [1, 2, 3]
In : lst.insert(-500,500)
In : lst
Out: [500, 1, 2, 3]
In : lst.insert(500,500)
In : lst
Out: [500, 1, 2, 3, 500]
很多场景下我们对列表操作不是一个一个元素的追加，更多的时候，我们可能需要的是批量的操作，列表提供了一个 extend 函数用于满足这种需求。
L.extend(iterable) --> None # 从一个可迭代对象中把元素扩展追加到当前列表中
说明：
- extend 直接操作原列表，所以其返回值为 None
- 如果扩展的可迭代对象过于大，那么可能会引起 GC 进行内存整理，因为扩充起来的元素，有可能会比当前列表所申请的内存空间更大。建议少用
- 扩充列表还有其他方法比如列表相 +, 列表相 *, 当使用这两种方式会返回新的列表，不会修改原列表
# extend
In : lst
Out: [500, 1, 2, 3, 500]
In : lst.extend('abc')
In : lst
Out: [500, 1, 2, 3, 500, 'a', 'b', 'c']
# 列表相 +, 列表相 *
In : lst
Out: [500, 1, 2, 3, 500]
In : lst + ['a','b','c']
Out: [500, 1, 2, 3, 500, 'a', 'b', 'c']
In : lst * 2
Out: [500, 1, 2, 3, 500, 500, 1, 2, 3, 500]
注意：使用 + 进行列表拼接的时候，由于返回了新的列表，原来相加的两个列表可能就没有用了，而如果这两个列表非常大，那么等于重复占用了新的内存空间，内存资源很宝贵，省着点用
2.6. 列表使用 * 重复带来的问题
我们使用 * 可以快速的生成一些特定的列表形式，比如我需要一个 6 个元素的列表，每个元素的值为 1，我就可以这样写 lst = [1]; lst * 6，这样写的确没什么问题，但是在某些场景下会产生意想不到的问题，比如在列表嵌套的时候。
In : lst = [[1,2,3]]
In : lst1 = lst * 3
In : lst1
Out: [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
In : lst1[1][1] = 20
In : lst1
Out: [[1, 20, 3], [1, 20, 3], [1, 20, 3]]
有没有发现什么问题？我明明修改的是 lst1 的第二个元素的第二个值为 20，为什么全都改变了？这是因为在列表是一个引用类型，lst 中实际上存储的是 [1,2,3] 的内存地址，而我们使用 * 3 的时候，等于复制了三份这个地址，所以 lst1 的 3 个元素，其实都指向了一个内存地址，所以我们随便修改一个元素，其他的也都会跟着被改变(毕竟是 1 个地址啊)，我们一般称这种复制为 影子复制(shadow copy)，知道了原因，我们就可以想办法解决了，既然你复制的是门牌号，那有没有办法复制门牌号里面的数据呢？答案当然是可以的，我们使用 copy 模块的 deepcopy 完成，它可以帮我们一层一层的找到元素真正的位置，然后进行复制。我们称 deepcopy 为深拷贝。
In : import copy # 导入 copy 模块
In : lst
Out: [[1, 20, 3]]
In : lst1 = lst # 复制一个新的列表
In : lst1[0][1] = 1000 # 对新列表进行赋值
In : lst1
Out: [[1, 1000, 3]] # 会同时影响 lst 和 lst1
In : lst
Out: [[1, 1000, 3]]
In : lst2 = copy.deepcopy(lst) # 这里使用深 copy
In : lst2
Out: [[1, 1000, 3]]
In : lst2[0][1] == 2000 # 对 lst2 进行修改后，不会影响原列表，因为已经把元素拷贝过来了
In : lst2
Out: [[1, 2000, 3]]
In : lst1
Out: [[1, 1000, 3]]
In : lst
Out: [[1, 1000, 3]]
2.7. 删除元素
列表对象同时提供了专门的方法用于对列表元素进行删除：remove、pop、clear。
L.remove(value) --> None # 删除列表中匹配 value 的第一个元素
L.pop([index]) --> item # 删除并返回 index 对应的 item, 索引超界抛出 IndexError 错误，如果不指定 index, 默认是列表的最后一个
L.clear() --> None # 清空列表，不建议进行操作，可以等待 GC 自行进行销毁
当我们使用 remove 和 pop 时，依然需要考虑
效率问题，remove 删除一个元素的时候，它首先要遍历这个列表，查找到匹配的元素后移除，它的时间复杂度是 O(n)， 使用 pop 指定 index 删除时，虽然可以 1 步定位到元素，但是如果删除的列表是首部或者中间的元素，那么将会使列表中的后续数据集体搬家， 但当你使用 pop 不指定 index 时，它默认会在列表的尾部删除，这种操作的时间复杂度为O(1)。所以建议如果需要频繁的对列表进行增删改，建议使用链表类型，而如果需要频繁的查或者只是从末尾弹出，就可以使用列表，因为这样效率更高。
In : lst = [1,2,3,4]
In : lst.remove(2)
In : lst
Out: [1, 3, 4]
In : lst.pop()
Out: 4
In : lst
Out: [1, 3]
In : lst.pop(1)
Out: 3
In : lst
Out: [1]
In : lst.clear()
In : lst
Out: []
2.8. 其他操作
当我们的列表中存储的是 int 类型的数据，而我们想要对其进行排序，那么就可以使用列表的排序，当我们想要判断一个元素是否存在于列表中时，就可以使用成员判断。
in: 成员判断，判断元素是否在列表中 1 in [1,2,3]，由于要遍历，所以它的时间复杂度为 O(n)
L.reverse() # 原地反转，原地将列表元素进行反转
L.sort(key=None, reverse=False) --> None # 原地修改，对列表进行排序，默认升序
sort 比较特别，它有两个参数，其中 key 可以接受一个函数，使列表中的元素按照函数处理过后的类型进行排序，默认为空，即不处理。reverse 则有两个值 True 和 False, 表示正序或者反序，默认为 False 表示正序。
线性数据结构的通病，找元素，需要进行遍历。
# 列表是顺序结构，但凡是顺序不一致，那么两个列表就不相等
In : l1 = [1,2,3,[4,5]]
In : [4,5] in l1
Out: True
In : [5,4] in l1 # 顺序改变，所以不相等
Out: False
In : lst = [2, 1 ,3 ,4 ,5]
In : lst.reverse()
In : lst
Out: [5, 4, 3, 1, 2]
In : lst.sort()
In : lst
Out: [1, 2, 3, 4, 5]
In : lst.sort(reverse=True) # 就地修改
In : lst
Out: [5, 4, 3, 2, 1]
