Python数据结构全解析：从列表到图的编程指南
<｜begin▁of▁sentence｜># 1. 什么是数据结构
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
# 2. 数据结构的分类
数据结构按照其逻辑结构可分为线性结构、树结构、图结构
- 线性结构：数据结构中的元素存在一对一的相互关系
- 树结构：数据结构中的元素存在一对多的相互关系
- 图结构：数据结构中的元素存在多对多的相互关系
# 3. 数据结构之列表
## 3.1 列表
列表是Python中最基本的数据结构。列表中的每个元素都分配一个数字 - 它的位置，或索引，第一个索引是0，第二个索引是1，依此类推。
Python有6个序列的内置类型，但最常见的是列表和元组。序列都可以进行的操作包括索引，切片，加，乘，检查成员。此外，Python已经内置确定序列的长度以及确定最大和最小的元素的方法。
列表是最常用的Python数据类型，它可以作为一个方括号内的逗号分隔值出现。列表的数据项不需要具有相同的类型
创建一个列表，只要把逗号分隔的不同的数据项使用方括号括起来即可。如下所示：
```python
list1 = ['physics', 'chemistry', 1997, 2000]
list2 = [1, 2, 3, 4, 5 ]
list3 = ["a", "b", "c", "d"]
```
与字符串的索引一样，列表索引从0开始。列表可以进行截取、组合等。
## 3.2 列表的增删改查
### 3.2.1 访问列表中的值
使用下标索引来访问列表中的值，同样你也可以使用方括号的形式截取字符，如下所示：
```python
list1 = ['physics', 'chemistry', 1997, 2000]
list2 = [1, 2, 3, 4, 5, 6, 7 ]
print "list1[0]: ", list1[0]
print "list2[1:5]: ", list2[1:5]
```
以上实例输出结果：
```python
list1[0]: physics
list2[1:5]: [2, 3, 4, 5]
```
### 3.2.2 更新列表
你可以对列表的数据项进行修改或更新，你也可以使用append()方法来添加列表项，如下所示：
```python
list = ['physics', 'chemistry', 1997, 2000]
print "Value available at index 2 : "
print list[2]
list[2] = 2001
print "New value available at index 2 : "
print list[2]
```
**注意：**我们会在接下来的章节讨论append()方法的使用
以上实例输出结果：
```python
Value available at index 2 :
1997
New value available at index 2 :
2001
```
### 3.2.3 删除列表元素
可以使用 del 语句来删除列表的的元素，如下实例：
```python
list1 = ['physics', 'chemistry', 1997, 2000]
print list1
del list1[2]
print "After deleting value at index 2 : "
print list1
```
以上实例输出结果：
```python
['physics', 'chemistry', 1997, 2000]
After deleting value at index 2 :
['physics', 'chemistry', 2000]
```
**注意：**我们会在接下来的章节讨论remove()方法的使用
### 3.2.4 Python列表脚本操作符
列表对 + 和 * 的操作符与字符串相似。+ 号用于组合列表，* 号用于重复列表。
如下所示：
| Python 表达式 | 结果 | 描述 |
| :--------------------------- | :--------------------------- | :------------------- |
| len([1, 2, 3]) | 3 | 长度 |
| [1, 2, 3] + [4, 5, 6] | [1, 2, 3, 4, 5, 6] | 组合 |
| ['Hi!'] * 4 | ['Hi!', 'Hi!', 'Hi!', 'Hi!'] | 重复 |
| 3 in [1, 2, 3] | True | 元素是否存在于列表中 |
| for x in [1, 2, 3]: print x, | 1 2 3 | 迭代 |
### 3.2.5 Python列表截取
Python 的列表截取实例如下：
```python
>>> L = ['Google', 'Runoob', 'Taobao']
>>> L[2]
'Taobao'
>>> L[-2]
'Runoob'
>>> L[1:]
['Runoob', 'Taobao']
>>>
```
描述：
| Python 表达式 | 结果 | 描述 |
| :------------ | :------------------- | :----------------------- |
| L[2] | 'Taobao' | 读取列表中第三个元素 |
| L[-2] | 'Runoob' | 读取列表中倒数第二个元素 |
| L[1:] | ['Runoob', 'Taobao'] | 从第二个元素开始截取列表 |
### 3.2.6 Python列表函数&方法
Python包含以下函数:
| 序号 | 函数 |
| :--- | :----------------------------------------------------------- |
| 1 | [cmp(list1, list2)](https://www.runoob.com/python/att-list-cmp.) 比较两个列表的元素 |
| 2 | [len(list)](https://www.runoob.com/python/att-list-len.) 列表元素个数 |
| 3 | [max(list)](https://www.runoob.com/python/att-list-max.) 返回列表元素最大值 |
| 4 | [min(list)](https://www.runoob.com/python/att-list-min.) 返回列表元素最小值 |
| 5 | [list(seq)](https://www.runoob.com/python/att-list-list.) 将元组转换为列表 |
Python包含以下方法:
| 序号 | 方法 |
| :--- | :----------------------------------------------------------- |
| 1 | [list.append(obj)](https://www.runoob.com/python/att-list-append.) 在列表末尾添加新的对象 |
| 2 | [list.count(obj)](https://www.runoob.com/python/att-list-count.) 统计某个元素在列表中出现的次数 |
| 3 | [list.extend(seq)](https://www.runoob.com/python/att-list-extend.) 在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表） |
| 4 | [list.index(obj)](https://www.runoob.com/python/att-list-index.) 从列表中找出某个值第一个匹配项的索引位置 |
| 5 | [list.insert(index, obj)](https://www.runoob.com/python/att-list-insert.) 将对象插入列表 |
| 6 | [list.pop([index])](https://www.runoob.com/python/att-list-pop.) 移除列表中的一个元素（默认最后一个元素），并且返回该元素的值 |
| 7 | [list.remove(obj)](https://www.runoob.com/python/att-list-remove.) 移除列表中某个值的第一个匹配项 |
| 8 | [list.reverse()](https://www.runoob.com/python/att-list-reverse.) 反向列表中元素 |
| 9 | [list.sort(cmp=None, key=None, reverse=False)](https://www.runoob.com/python/att-list-sort.) 对原列表进行排序 |
# 4. 数据结构之栈
## 4.1 什么是栈
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈(Stack)是限制插入和删除操作只能在一个位置进行的表，该位置是表的末端，称为栈的顶(top)。栈的基本操作有PUSH(入栈)和POP(出栈)。栈又被称为LIFO(后入先出)表。
## 4.2 栈的基本操作
1. 初始化
2. 进栈
3. 出栈
4. 取栈顶元素
## 4.3 栈的代码实现
```python
class Stack(object):
def __init__(self, limit=10):
self.stack = [] # 存放元素
self.limit = limit # 栈容量极限
def push(self, data): # 判断栈是否溢出
if len(self.stack) >= self.limit:
print('StackOverflowError')
pass
self.stack.append(data)
def pop(self):
if self.stack:
return self.stack.pop()
else:
raise IndexError('pop from an empty stack') # 空栈不能被弹出
def peek(self): # 查看栈的栈顶元素（最上面的元素）
if self.stack:
return self.stack[-1]
def is_empty(self): # 判断栈是否为空
return not bool(self.stack)
def size(self): # 返回栈的大小
return len(self.stack)
```
# 5. 数据结构之队列
## 5.1 什么是队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
## 5.2 队列的基本操作
1. 初始化
2. 入队
3. 出队
4. 取队首元素
## 5.3 队列的代码实现
```python
class Queue(object):
def __init__(self):
self.queue = []
def enqueue(self, data):
self.queue.append(data)
def dequeue(self):
if self.queue:
return self.queue.pop(0)
else:
raise IndexError('queue is empty!')
def getHead(self):
if self.queue:
return self.queue[0]
else:
raise IndexError('queue is empty!')
def getTail(self):
if self.queue:
return self.queue[-1]
else:
raise IndexError('queue is empty!')
def size(self):
return len(self.queue)
def is_empty(self):
return not bool(self.queue)
```
# 6. 数据结构之链表
## 6.1 什么是链表
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
## 6.2 链表的基本操作
1. 初始化
2. 判断链表是否为空
3. 尾部插入
4. 头部插入
5. 删除节点
6. 插入节点
7. 查找节点
## 6.3 链表的代码实现
```python
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def append(self, data):
node = Node(data)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def iter(self):
if not self.head:
return
cur = self.head
yield cur.data
while cur.next:
cur = cur.next
yield cur.data
def insert(self, idx, value):
cur = self.head
cur_idx = 0
if cur is None: # 判断是否是空链表
raise Exception('The list is an empty list')
while cur_idx < idx - 1: # 遍历链表
cur = cur.next
if cur is None: # 判断是不是最后一个元素
raise Exception('list length less than index')
cur_idx += 1
node = Node(value)
node.next = cur.next
cur.next = node
if node.next is None:
self.tail = node
def remove(self, idx):
cur = self.head
cur_idx = 0
if self.head is None: # 空链表时
raise Exception('The list is an empty list')
while cur_idx < idx - 1:
cur = cur.next
if cur is None:
raise Exception('list length less than index')
cur_idx += 1
if idx == 0: # 当删除第一个节点时
self.head = cur.next
cur = cur.next
return
if self.head is self.tail: # 当只有一个节点的链表时
self.head = None
self.tail = None
return
cur.next = cur.next.next
if cur.next is None: # 如果删除的是尾部节点
self.tail = cur
def size(self):
current = self.head
count = 0
if current is None:
return 'The list is an empty list'
while current is not None:
count += 1
current = current.next
return count
def search(self, item):
current = self.head
found = False
while current is not None and not found:
if current.data == item:
found = True
else:
current = current.next
return found
```
# 7. 数据结构之树
## 7.1 什么是树
树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
## 7.2 树的基本操作
1. 初始化
2. 为节点添加子节点
3. 遍历树
## 7.3 树的代码实现
```python
class Node(object):
def __init__(self, data):
self.data = data
self.children = []
def add(self, data):
self.children.append(Node(data))
def remove(self, data):
self.children = [node for node in self.children if node.data != data]
class Tree(object):
def __init__(self):
self.root = None
def traverse_bf(self, func):
nodes = [self.root]
while nodes:
node = nodes.pop(0)
nodes.extend(node.children)
func(node)
def traverse_df(self, func):
nodes = [self.root]
while nodes:
node = nodes.pop(0)
nodes = node.children + nodes
func(node)
```
# 8. 数据结构之图
## 8.1 什么是图
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
## 8.2 图的基本操作
1. 初始化
2. 为图添加节点
3. 为节点添加边
4. 展示图
## 8.3 图的代码实现
```python
class Graph(object):
def __init__(self):
self.nodes = []
self.edges = []
def insert(self, a, b):
if not (a in self.nodes):
self.nodes.append(a)
self.edges.append([])
if not (b in self.nodes):
self.nodes.append(b)
self.edges.append([])
a_index = self.nodes.index(a)
b_index = self.nodes.index(b)
self.edges[a_index].append(b_index)
self.edges[b_index].append(a_index)
def show(self):
for i in range(len(self.nodes)):
print(self.nodes[i], end='->')
for j in range(len(self.edges[i])):
print(self.nodes[self.edges[i][j]], end=' ')
print()
```
# 9. 数据结构之字典
## 9.1 什么是字典
字典是另一种可变容器模型，且可存储任意类型对象。
字典的每个键值 key=>value 对用冒号 : 分割，每个键值对之间用逗号 , 分割，整个字典包括在花括号 {} 中 ,格式如下所示：
```python
d = {key1 : value1, key2 : value2 }
```
键一般是唯一的，如果重复最后的一个键值对会替换前面的，值不需要唯一。
```python
>>> dict = {'a': 1, 'b': 2, '
最新文章
- 智能温控系统提升汽车驾驶舒适度
- 汽车传动系统优化技术
- 自动驾驶技术发展现状、挑战与未来趋势分析
- 汽车摄像头实时监控行车安全
- 车险备胎免赔额详解：如何合理选择保障方案
- 乔治巴顿与汽车传奇
- 汽车安全气囊系统保护乘客安全
- 驾驶技巧与安全指南：从新手到老司机
- 发动机轰鸣汽车飞驰在路上
- 三元锂电池突破300Wh/kg能量密度，L3自动驾驶引领电动化浪潮
- 固态电池与无钴正极技术引领电动车动力电池革命
- 车险省钱攻略：五大因素影响保费，比价技巧全解析
- 高效节能汽车冷却系统优化设计
- Java对象创建与初始化机制深度解析
- 交通事故责任认定与汽车定损全流程指南
- 毫米波雷达助力智能驾驶
- 毫米波雷达：智能汽车的“透视眼”与安全守护神
- 汽车空气滤清器更换周期及保养技巧
- 智能驾驶革命：重塑未来出行的核心技术与发展趋势
- 汽车天窗排水系统维护指南：导水槽与密封胶条保养要点