05.数据结构

# 1.内建数据结构
- 序列
字符串、字节序列、
列表、元祖
- 键值对
集合、字典

# 2.线性数据结构
在程序里经常需要将一组数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，一组数据中包含的元素个数可能发生变化，也可能会用元素在序列里的位置和顺序，表示实际应用中的某种有意义信息。线性表就是这样一组元素的抽象，其具体实现方式有两种，顺序表和链接表

```mindmap
# 线性表
## 顺序表的实现
### tuple
### list
### str
### 字符
### bytes
### bytearray
## 链接表的实现
# 非线性表
## SET
```

线性表：一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

根据线性表的实际存储方式，分为两种实现模型：
- 顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
- 链接表，将元素存放在通过链接构造起来的一系列存储块中。

## 顺序表的实现
![](/media/202108/2021-08-23_174446.png)
上图表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：Loc(ei) = Loc(e0) + c*i 。故，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。
一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。
![](/media/202108/2021-08-23_174536.png)
>这里有存在2种结构，一体式结构和分离式结构，当存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。图b为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

### 存储区替换操作
一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。

分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

### 元素存储区扩充
采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

扩充的两种策略
- 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。
特点：节省空间，但是扩充操作频繁，操作次数多。
- 每次扩充容量加倍，如每次扩充增加一倍存储空间。
特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。

### 增加元素
![](/media/202108/2021-08-23_174719.png)
1. 尾端加入元素，时间复杂度为O(1)
1. 非保序的加入元素（不常见），时间复杂度为O(1)
1. 保序的元素加入，时间复杂度为O(n)

### 删除操作
基本和添加操作相似
1. 删除表尾元素，时间复杂度为O(1)
1. 非保序的元素删除（不常见），时间复杂度为O(1)
1. 保序的元素删除，时间复杂度为O(n)

## 链接表的实现
链接表是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。
基于链接技术实现的线性表称为链接表或者链表，用链接关系显式表示元素之间的顺序关系，链接表结构的基本思想如下：
1.把表中的元素分别存储在一批独立的存储块（结点）里 
2.保证从组成表结构中的任一个结点可找到与其相关的下一个结点 
3.在前一结点里用链接的方式显式地记录与下一结点之间的关联

## 链表与顺序表的对比
链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。
虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行

# 3.list
Python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序（即保序），而且还具有以下行为特征：
- 基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)；
为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。
- 允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。
为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时list对象的标识id不变，只能采用分离式实现技术。

在Python的官方实现中，list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

在Python的官方实现中，list实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。

**Python中的list 是其他语言中的数组，由顺序表实现；在其他语言中 list 是链表实现，顺序表更多是数组**

## 3.1.列表list
- 一个队列，一个排列整齐的队伍，列表内的个体称作元素，由若干元素组成的列表，元素可以是任意对象(数字，字符串，对象，列表等)
- 列表内元素有顺序，可以使用索引，线性的数据结构，使用[]表示，列表是可变的
- 列表list、链表、queue、stack的差异

## 3.2.列表list定义和初始化
list() 定义一个空列表  list(iterable)  初始化一个可迭代的列表  列表不能一开始就定义大小
```
>>> l1 = []
>>> l2 = list()   # 放入可迭代的对象进行构建
>>>
>>> type(l1), type(l2)
(<class 'list'>, <class 'list'>)
>>>
>>> l3 = [1, 2, 3]
>>> type(l3)
<class 'list'>
>>>
>>> l4 = [1, 2, 3, True, [3, 4], 'abc']  # 列表支持可变对象
>>> type(l4)
<class 'list'>
>>>
>>> l5 = list(range(5))   # 括号内使用可迭代对象，可以被遍历的对象；list 也是可迭代对象，因为list 是容器
>>> type(l5)
<class 'list'>
>>>
>>> l6 = list([1, 2, 'a'])   # 创建一个列表，将列表中的元素遍历存在新的列表中
>>> print(l6)
[1, 2, 'a']
>>>
```
列表是顺序表实现;可索引即容器内的元素有序;可遍历，即为容器。

> 函数调用那就是在函数名后面加上括号，括号中写上对应的值。

## 3.3.列表索引访问
索引也叫下标
- 正索引：从左至右，从0开始为列表中每一个元素编号  ( 0 ~ length )
- 负索引：从右至左，从-1开始为列表中每一个元素编号 ( length ~ -1 )
- 正负索引不可以越界，否则引发异常IndexError，为了理解方便，可以认为列表是从左至右排列的，左边是头部，右边是尾部，左边是下界，右边是上界
- 列表通过索引访问方式：list[index],index就是索引，使用中括号访问

```
>>> l4 = [1, 2, 3, True, [3, 4], 'abc']
>>> l4[1]
2
>>> l4[4]
[3, 4]
>>>
>>> l4[7]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>>
>>> l4[-7]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>>
```

## 3.4.列表查询
1. list.index(value,[start,[stop])
通过值value，从指定区间查找列表内的元素是否匹配，匹配第一个就立即返回索引，匹配不到，抛出异常ValueError
```
>>> lst = [2,6,9,'ab']
>>> lst.index(2)     # 返回 value 的索引位置
0
>>> lst.index(6,0,3)
1
```

2. list.count(value)
- 返回列表中匹配value的次数
- 时间复杂度
- index和count方法都是O(n)
- 随着列表数据规模的增大而效率下降
- len(lst) 返回列表元素的个数
```
>>> lst = lst = [2,6,9,9,9,'ab']
>>> lst.index(9)   # 从左开始返回搜索到的第一个 value
>>> 2
[2, 6, 9, 9, 9, 'ab']
>>> lst.count(9)    # 返回 value 的个数
3
```

## 3.5.列表元素修改
list[index] = value，索引不要超界

## 3.6.列表增加、插入元素
- list.append(object):列表尾部追加元素，返回None，返回None就意味着没有新的列表产生，就地修改，时间复杂度是O(1)
list 是容器，有容量；列表可以自动扩大；初始化时给定大小，当容量不够，进行2 ~ 4 倍扩容。
append 增加元素时，遇到列表容器扩容，效率降低；当内存中连续空间不足，内存垃圾回收耗时。
append 增加元素在尾部是效率高

- list.insert(index,object) 返回None就意味着没有新的列表产生，就地修改，时间复杂度是O(1)
插入索引越界：超越右边界，尾部追加；超越左边界，头部追加
```
>>> lst = [2,6,9,'ab']
>>> lst.insert(1000, '20')
>>> lst
[2, 6, 9, 'ab', '20']
>>>
>>> lst.insert(-10, '40')
>>> lst
['40', 2, 6, 9, 'ab', '20']
>>>
```
insert 使用 index 的方法来查找插入点；插入点之后的所有数据向后挪动。
规模越大，挪动数据库越大，耗时越长。
插入队首最耗时，插入队尾最快。

- list.extend(iterable) 尾部扩展，返回None，将可迭代对象元素追加进来，返回None，就地修改
```
>>> lst.extend([3, 6, 9])  # 将迭代对象取出，分别 append
>>> lst
['40', 2, 6, 9, 'ab', '20', 3, 6, 9]
>>>
```

- list+list：连接操作，将两个列表拼接起来，产生新的列表，原列表不变，本质上调用的是__add__()方法
```
>>> l1 = [1, 2]
>>> l2 = [3, 4]
>>> l1 + l2
[1, 2, 3, 4]
>>>
>>> l1, l2
([1, 2], [3, 4])
>>>
```

- list* N：重复操作，将本列表元素重复n次，返回新的列表
```
>>> l1 * 3
[1, 2, 1, 2, 1, 2]
>>>
>>> l1
[1, 2]
>>>
>>> [[1]] * 3
[[1], [1], [1]]
>>>
```
python 中一切皆对象，而对象的都是引用类型，可以理解为一个地址指针指向的对象。
你可以认为简单类型是直接存在列表中，而引用类型只是把引用地址存在列表中。
```
>>> a = [1]        # 简单类型，相当于直接复制
>>> b = a *3
>>> b[1] = 100
>>> print(b)
[1, 100, 1]
>>>
>>> a = [[1]]        # 复杂类型，引用类型
>>> b = a *3         # b = [[1], [1], [1]]
>>> b[1][0] = 100    # b[1] = [1], b[1][0] = 100
>>> print(b)
[[100], [100], [100]]
>>>
```

## 3.7.列表删除元素
- list.remove(value):返回None，从左至右查找第一个匹配的value值，移除该元素，返回None，就地修改
- list.pop([index]):不指定索引就从列表尾部弹出一个元素，指定索引，从索引出弹出一个元素，索引超界抛出IndexError错误
- list.clear():清除列表所有元素，返回None，剩下一个空列表

## 3.8.列表其他操作
- list.reversed(): 将列表元素反转，返回None，就地修改

```python
>>> l1 = list(range(10))
>>> l1.reverse()
>>> l1
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>>
>>> l2 = list(range(10,19))
>>> for i  in range(-1, -10, -1):
        print(i, l2[i])
>>>
-1 18
-2 17
-3 16
-4 15
-5 14
-6 13
-7 12
-8 11
-9 10
>>>
```
- list.sort(key=None,reverse=False): 对列表元素进行排序，就地修改，默认升序,reverse=True降序，key是一个函数，指定key如何排序

```python
>>> l2.sort()
>>> l2
[10, 11, 12, 13, 14, 15, 16, 17, 18]
>>> l2.sort(reverse(Ture))
>>> l2
[18, 17, 16, 15, 14, 13, 12, 11, 10]
>>>
>>> l1 = [1, 2, 'a', 3]
>>> l1.sort
<built-in method sort of list object at 0x0000024B8FF93D00>  # TypeError: '<' not supported between instances of 'str' and 'int'
>>>
>>> l1.sort(key=str)   # 进行元素转换，转换后的值进行比较，然后在进行比较，单不影响输出
>>> l1
[1, 2, 3, 'a']
>>>
```

- in 是否在 [3,4] in [1,2,[3,4]]

```python
>>> -1 in l2
False
>>> 2 in l2
True
>>> l2.index(2)
1
>>>
>>> [3,4] in [1,2,[3,4]]   # [3,4] 与 [1,2,[3,4]][3] 进行地址比较，不相同；内容比较，相同
True
>>> for i in [1, 2, 4, 3]
```

## 3.9.列表复制
### copy
也叫浅拷贝：list.copy(), 遇到引用类型，只是复制了一个引用而已

b = a ; 赋值引用，a 和 b 都指向同一个对象。
![](/media/202206/2022-06-14_105150_190119.png)

b = a.copy() ; 浅拷贝, a 和 b 是一个独立的对象，但他们的子对象还是指向统一对象（是引用）。
![](/media/202206/2022-06-14_105155_381435.png)

测试 lst1 = list(range(4))和 lst2 = list(range(4))是否相等？
```python
>>> lst1 = list(range(4))
>>> lst1
[0, 1, 2, 3]
>>> lst2 = list(range(4))
>>> lst2
[0, 1, 2, 3]
>>> lst1 == lst2
True
```
以上测试说明，lst1和 lst2相等，两个列表指向的是同一个引用

简单类型的列表，copy 等于直接复制对象内容。
```python
>>> lst1 = list(range(4))
>>> lst2 = lst1.copy()
>>> lst1
[0, 1, 2, 3]
>>> lst2
[0, 1, 2, 3]
>>> lst2[2] = 10
>>> lst2
[0, 1, 10, 3]
>>> lst1
[0, 1, 2, 3]
>>> lst1 == lst2
False
```
复杂类型的列表，copy 复制对象的地址。
```python
>>> lst1 = [1, 2, [3, 4], 5]
>>> lst2 = lst1.copy()
>>> lst2[2][1] = 10         # 修改引用地址指向的内容，所以的引用内容都发生了变化
>>> lst1
[1, 2, [3, 10], 5]
>>> lst2
[1, 2, [3, 10], 5]
>>> lst1 == lst2
True
>>>
>>> lst1[2] = 4             # 修改内容，其他引用地址指向的内容保持不变
>>> lst2
[1, 2, [3, 10], 5]
>>> lst1
[1, 2, 4, 5]
>>> lst1 == lst2
False
>>>
```

### deepcopy
深拷贝, copy模块提供了deepcopy 方法

b = copy.deepcopy(a); 深度拷贝, a 和 b 完全拷贝了父对象及其子对象，两者是完全独立的。
![](/media/202206/2022-06-14_105200_150808.png)

```python
>>> lst1 = [1,[2,3],4]
>>> lst1
[1, [2, 3], 4]
>>> import copy
>>> lst2 = copy.deepcopy(lst1)
>>> lst2
[1, [2, 3], 4]
>>> lst2[1][1] = 20
>>> lst2
[1, [2, 20], 4]
>>> lst1 == lst2
False
```

# 4.元组（tuple）
## 4.1.元组的定义 初始化
一个有序的元素组成的集合，使用小括号()表示，元组是不可变的
tuple() 空元组  
t = ()  空元组
t = (1,) 定义一个元素元组的定义
t = (i for i in range(1,7,2))  创建一个元组

```
>>> t1 = ()
>>> t2 = tuple()
>>> t1 == t2
True
>>> t1 is t2    # 元祖不可变，空元祖，解释器对不可变的tuple类型进行了优化
True
>>>
```

## 4.2.元组元素的访问
- 元组通过索引访问：tuple[index]，使用中括号访问
- 正索引：从左至右，从0开始为列表中每一个元素编号
- 负索引：从右至左，从-1开始为列表中每一个元素编号
- 正负索引不可以越界，否则引发异常IndexError

## 4.3.元组查询   
- t.index(value,[start,[stop]]) ：通过值value，从指定区间查找列表内的元素是否匹配,匹配第一个就立即返回索引，匹配不到，抛出异常ValueError  
- t.count(value) ： 返回列表中匹配value的次数   
- 时间复杂度 ： index和count方法都是O(n) ， 随着列表数据规模的增大而效率下降
- len(t)  返回元组的个数

元组是只读的，所以增、改、删方法都没有
```
>>> t3 = (1, 2, 3,)
>>> t3[1]
2
>>> t3[1] = 4
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>>
```

# 5.集合（set）
## 5.1.集合set的定义初始化
- 约定set翻译为集合，collection翻译为集合类型，是一个大概念；集合是可变的，无序的，不重复元素的集合
- set() 定义一个空集合
- set(iterable)  定义一个有元素的集合
- set的元素要求必须可以hash，目前学过的不可hash的类型有list，set 
- 元素不可以索引
```
>>> s1 = set()
  >>> s1
  set()
  >>> s2 = set(range(5))
  >>> s2
  {0, 1, 2, 3, 4}
  >>> s3 = set(list(range(10)))
  >>> s3
  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  >>> s4 = {9,101,10}
  >>> s5 = {[1],(1,),1}  #报错，集合元素必须是可hash
```

## 5.2.python的哈希hash
在python中list，set和dict都是可变的，所以他们都是不可hash的
tuple和string是不可变的，只可以做复制或者切片等操作，所以他们是可hash的

## 5.3.集合set元素增加
s.add(value) 增加一个元素到set中，如果元素存在，什么都不做
s.update(*others)  合并其他元素到set集合中来，参数other必须是可迭代对象，就地修改

## 5.4.集合set元素删除
s.remove(value) 从set中移除一个元素，元素不存在，抛出keyError异常
s.discard(value) 从set中移除一个元素，元素不存在什么都不做
s.pop() 移除并返回任意的元素，空集合返回keyError异常
s.clear()  清空集合

## 5.5.集合set元素修改，查询
- set没有修改，要么删除，要么加入新的元素
- set是非线性结构，无法索引查询
- 可以迭代集合中所有元素
- in和not in判断元素是否在set中

## 5.6.集合set和线性结构
- 线性结构的查询时间复杂度是O(n)，即随着数据规模的增大而耗时
- set，dict等非线性结构，内部使用hash值作为key，时间复杂度是O(1)

# 6.字典（dict）
## 6.1.字典dict定义初始化
字典是key-value键值对的数据集合
key的要求和set的元素要求一致，可hash才可以作为key
字典是可变的，无序的，key不可重复
d = dict() 或者d = {} 定义一个空字典
dict(**kwargs) 使用name=value对 初始化一个字典

## 6.2.字典元素的访问
d[key]: 返回key对应的值value，key不存在抛出KeyError异常
d.get(key[,default]): 返回key对应的值value，key不存在返回缺省值，如果没有缺省值返回None
d.setdefault(key[,default]):返回key对应的值value,key不存在，添加kv对；value为default，并返回default，如果没有default,缺省为None

## 6.3.字典增加和修改
d[key] = value: 将key对应的值修改为value，key不存在添加新的kv对
d.update([other]): 使用另一个字典的kv对更新本字典，key不存在，就添加；存在就覆盖已经存在value
d.update(red=1)

## 6.4.字典的删除
d.pop(key):key存在就移除，并返回它的value值，不存在返回默认值，没有默认值就抛异常
d.popitem(): 移除并返回一个任意的键值对，字典为空，抛出异常ValueError
d.clear()：清空字典

## 6.5.字典遍历

遍历key：for k in d或者for k in d.keys()
遍历value： for k in d: print(d[k])
遍历item，即kv对： for item in d.items()或for k,v in d.items()

python3中，keys，values，items方法返回一个类似一个生成器的可迭代对象，不会把函数的返回结果复制到内存中
```
{1: 'a', 2: 'b'}
>>> for k in d:
 print(k)
1
2
>>> for k in d.keys():
 print(k) 
1
2
>>> for k in d:
 print(d[k]) 
a
b
>>> for item in d.items():
 print(item) 
(1, 'a')
(2, 'b')
>>> for k,v in d.items():
 print(k,v) 
1 a
2 b
>>>
```

在实战前，我们需要先创建一个模拟数据的字典。
```
dict_1 = {'Name': 'Zara', 'Age': 7, 'Class': 'First','Address':'Beijing'}
```
1. For 循环 + 索引进行迭代
在 Python 中遍历字典的最简单方法，是将其直接放入for循环中。
Python 会自动将dict_1视为字典，并允许你迭代其key键。然后，我们就可以使用索引运算符，来获取每个value值。
```
for key in dict_1:
    print(key, ":", dict_1[key])
```
如果你想按照字母顺序排列key键，可以使用sorted()方法，具体用法如下所示。
```
for key in sorted(dict_1):
    print(key, ":", dict_1[key])
```
2. .keys( ) + 索引进行迭代
使用.keys()返回包含字典键的 Python 对象的方法，可以获得与方法1相同的结果。同样，它也需要与索引运算符结合使用。
```
for key in dict_1.keys():
    print(key, '-->', dict_1[key])
```
3. .items( ) 进行迭代
其实，遍历字典的最“pythonic”和优雅的方法，是使用.items()方法。
```
print(dict_1.items())
```

## 6.6.有序字典OrderedDict
有序字典可以记录元素插入的顺序，打印的时候也是按照这个顺序输出打印
```
>>> from collections import OrderedDict
>>> import random
>>> d = {'banana':3,'apple':4,'pear':1,'orange':2}
>>> print(d)
{'pear': 1, 'apple': 4, 'orange': 2, 'banana': 3}
>>> keys = list(d.keys())
>>> keys
['pear', 'apple', 'orange', 'banana']
>>> random.shuffle(keys)
>>> print(keys)
['banana', 'orange', 'apple', 'pear']
>>> od = OrderedDict()
>>> for key in keys:
 od[key] = d[key]  
>>> print(od)
OrderedDict([('banana', 3), ('orange', 2), ('apple', 4), ('pear', 1)])
>>> print(od.keys())
odict_keys(['banana', 'orange', 'apple', 'pear'])
>>>
```