第十章：高级数据结构

完成本章学习后，你将能够：

• 掌握collections模块的高级数据结构
• 理解栈、队列、双端队列的应用
• 使用堆和优先队列
• 掌握链表的实现和应用

from collections import Counter
 
# 创建计数器
c = Counter(['a', 'b', 'a', 'c', 'a', 'b'])
print(c)  # Counter({'a': 3, 'b': 2, 'c': 1})
 
# 从字符串创建
c = Counter("mississippi")
print(c)  # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
 
# 常用方法
print(c.most_common(2))  # [('i', 4), ('s', 4)]，最常见的2个
print(c.elements())      # 迭代所有元素
 
# 数学运算
c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)
print(c1 + c2)  # Counter({'a': 4, 'b': 3})
print(c1 - c2)  # Counter({'a': 2})

from collections import defaultdict
 
# 默认值为列表
words = ["apple", "bat", "bar", "atom", "book"]
by_first_letter = defaultdict(list)
 
for word in words:
    by_first_letter[word[0]].append(word)
 
print(dict(by_first_letter))
# {'a': ['apple', 'atom'], 'b': ['bat', 'bar', 'book']}
 
# 默认值为整数（计数）
counts = defaultdict(int)
for word in words:
    counts[word[0]] += 1

from collections import deque
 
# 创建
d = deque([1, 2, 3, 4, 5])
 
# 两端操作（都是O(1)）
d.append(6)        # 右端添加
d.appendleft(0)    # 左端添加
right = d.pop()    # 右端移除
left = d.popleft() # 左端移除
 
# 限制大小（滑动窗口）
d = deque(maxlen=3)
for i in range(10):
    d.append(i)
    print(list(d))  # 始终只保留最后3个元素
 
# 旋转
d = deque([1, 2, 3, 4, 5])
d.rotate(2)   # 向右旋转2位: [4, 5, 1, 2, 3]
d.rotate(-1)  # 向左旋转1位: [5, 1, 2, 3, 4]

import heapq
 
# 创建堆（列表）
heap = []
 
# 添加元素
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
 
# 弹出最小元素
print(heapq.heappop(heap))  # 1
 
# 从列表构建堆
data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data)
 
# 获取n个最大/最小值
print(heapq.nlargest(3, data))  # [9, 6, 5]
print(heapq.nsmallest(3, data)) # [1, 1, 2]
 
# 优先队列应用
tasks = []
heapq.heappush(tasks, (2, "write code"))    # (优先级, 任务)
heapq.heappush(tasks, (1, "design"))
heapq.heappush(tasks, (3, "test"))
 
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"[{priority}] {task}")

class Node:
    """链表节点"""
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    """单向链表"""
    def __init__(self):
        self.head = None
        self.size = 0
 
    def append(self, data):
        """在末尾添加"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1
 
    def prepend(self, data):
        """在头部添加"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
 
    def delete(self, data):
        """删除第一个匹配的节点"""
        if not self.head:
            return
 
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return
 
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                return
            current = current.next
 
    def find(self, data):
        """查找节点"""
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1
 
    def to_list(self):
        """转换为Python列表"""
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result
 
# 使用
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
print(ll.to_list())  # [0, 1, 2, 3]

1. 使用Counter统计文本词频，输出前10 2. 使用deque实现滑动窗口最大值 3. 使用堆合并K个有序列表 4. 实现双向链表 5. 使用优先队列实现任务调度器

下一章：第十一章：函数基础