python教程（三）：python高级数据结构大全（附代码）
Python 中的高级数据结构是基于标准数据结构的扩展，提供了更高效的操作和更复杂的功能。这些数据结构通常用于解决特定的编程问题或优化性能。下面是一些常见的高级数据结构及其应用。
1. 双端队列（deque）
描述：
deque 是双端队列，支持在两端快速添加和删除元素，效率高于列表。
操作：
append(x)：在右端添加元素。
appendleft(x)：在左端添加元素。
pop()：从右端移除元素。
popleft()：从左端移除元素。
extend(iterable)：从右端添加多个元素。
extendleft(iterable)：从左端添加多个元素，顺序反转。
rotate(n)：向右旋转 n 个元素。
应用场景：
用于需要在两端操作的场景，如滑动窗口算法、栈和队列实现。
from collections import deque
d = deque()
d.append('right')
d.appendleft('left')
d.pop() # 移除右端元素
d.popleft() # 移除左端元素
print(d) # deque([])
2. 有序字典（OrderedDict）
描述：
OrderedDict 是保持元素插入顺序的字典。
操作：
popitem(last=True)：移除并返回最后一个键值对，last=False时移除第一个键值对。
move_to_end(key, last=True)：将某个键值对移动到字典的一端。
应用场景：
适用于需要保持键值插入顺序的场景，如实现 LRU 缓存。
from collections import OrderedDict
od = OrderedDict()
od['one'] = 1
od['two'] = 2
od['three'] = 3
for key, value in od.items():
print(key, value)
3. 默认字典（defaultdict）
描述：
defaultdict 是字典的子类，允许设置默认值，当访问不存在的键时，会自动返回默认值。
操作：
与普通字典操作一致，但会自动提供默认值，避免 KeyError。
应用场景：
适合在需要为不存在的键设置默认值的场景，如自动生成列表、计数器等。
from collections import defaultdict
dd = defaultdict(list)
dd['fruits'].append('apple')
dd['fruits'].append('banana')
print(dd['fruits']) # ['apple', 'banana']
4. 计数器（Counter）
描述：
Counter 是字典的子类，用于统计可哈希对象的出现次数。
操作：
elements()：返回计数器中所有元素。
most_common([n])：返回出现次数最多的前 n 个元素。
subtract([iterable-or-mapping])：从计数器中减去元素。
应用场景：
适用于计数场景，如统计词频、投票计数等。
from collections import Counter
c = Counter(['apple', 'banana', 'apple', 'orange'])
print(c) # Counter({'apple': 2, 'banana': 1, 'orange': 1})
print(c.most_common(1)) # [('apple', 2)]
5. 命名元组（namedtuple）
描述：
namedtuple 生成可以通过名称访问字段的元组子类。
操作：
通过字段名或索引访问元素。
_replace(**kwargs)：返回一个新的元组实例，并用新值替换指定字段。
_asdict()：将命名元组转换为字典。
应用场景：
替代轻量类，用于存储结构化数据，如数据库记录。
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(11, y=22)
print(p.x, p.y) # 11 226. 数组（array）
描述：
array 是一种存储相同类型元素的高效数据结构，适用于处理大量数值型数据。
操作：
append(x)：在数组末尾添加元素。
extend(iterable)：扩展数组。
pop([i])：移除并返回指定位置的元素。
insert(i, x)：在指定位置插入元素。
应用场景：
适合大量数值型数据的存储和处理，如图像处理、科学计算。
from array import array
a = array('i', [1, 2, 3, 4])
a.append(5)
print(a) # array('i', [1, 2, 3, 4, 5])
7. 集合（Set）
描述：
Set 是无序且不重复的元素集合。
操作：
add(x)：添加元素。
remove(x)：移除元素。
union(other)：并集操作。
intersection(other)：交集操作。
应用场景：
用于元素去重、快速判断元素是否存在、集合运算等。
s = set([1, 2, 3, 1, 2])
print(s) # {1, 2, 3}
s.add(4)
print(s) # {1, 2, 3, 4}
# 并集
s2 = set([3, 4, 5])
print(s.union(s2)) # {1, 2, 3, 4, 5}
8. 优先队列（Priority Queue）
描述：
优先队列是一种每次取出元素时都会按优先级排序的队列，最低优先级的元素首先出列。
操作：
put(item)：将元素放入队列。
get()：移除并返回优先级最高的元素。
empty()：检查队列是否为空。
应用场景：
任务调度、事件处理中的优先级队列。
import heapq
heap = []
heapq.heappush(heap, (1, 'priority 1'))
heapq.heappush(heap, (3, 'priority 3'))
heapq.heappush(heap, (2, 'priority 2'))
print(heapq.heappop(heap)) # (1, 'priority 1')
9. 堆（Heap）
描述：
堆是一种特殊的二叉树，通常用于实现优先队列，支持高效获取最小值或最大值。
操作：
heapify(iterable)：将可迭代对象转换为堆。
heappush(heap, item)：将元素推入堆。
heappop(heap)：弹出并返回最小元素。
heapreplace(heap, item)：弹出最小元素并将新元素推入堆中。
应用场景：
优先队列、需要快速访问最小值或最大值的场景。
import heapq
nums = [3, 1, 4, 1, 5, 9]
heapq.heapify(nums)
print(heapq.heappop(nums)) # 1
10. 链表（Linked List）
描述：
链表由节点组成，每个节点包含数据以及指向下一个节点的指针。
操作：
insert(data)：在链表头插入数据。
remove(data)：移除包含特定数据的节点。
search(data)：查找链表中包含特定数据的节点。
应用场景：
需要频繁插入、删除操作，尤其是数据量大时的应用场景。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def print_list(self):
node = self.head
while node:
print(node.data, end=" -> ")
node = node.next
ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.print_list() # 输出: 3 -> 2 -> 1 ->
这些数据结构及其操作可以有效地解决不同的编程问题，提高代码的性能和可读性。