====== 第十章：高级数据结构 ======

===== 本章目标 =====

完成本章学习后，你将能够：
  * 掌握collections模块的高级数据结构
  * 理解栈、队列、双端队列的应用
  * 使用堆和优先队列
  * 掌握链表的实现和应用

===== collections模块 =====

==== Counter计数器 ====

<code python>
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})
</code>

==== defaultdict默认字典 ====

<code python>
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
</code>

==== deque双端队列 ====

<code python>
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]
</code>

===== 堆和优先队列 =====

<code python>
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}")
</code>

===== 链表实现 =====

<code python>
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]
</code>

===== 本章练习 =====

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

下一章：[[python_course:chapter11|第十一章：函数基础]]