Python数据结构与算法¶

概述¶

Python中的数据结构是编程的基础，理解和掌握各种数据结构对于编写高效的代码至关重要。

基本数据类型¶

1. 列表 (List)¶

# 列表的基本操作
numbers = [1, 2, 3, 4, 5]
numbers.append(6)  # 添加元素
numbers.extend([7, 8, 9])  # 扩展列表

# 列表推导式
squares = [x**2 for x in range(10)]
even_squares = [x**2 for x in range(10) if x % 2 == 0]

print(f"平方数列表: {squares}")

2. 字典 (Dictionary)¶

# 字典的使用
student = {
    "name": "张三",
    "age": 20,
    "courses": ["数学", "物理", "计算机科学"]
}

# 字典推导式
word_count = {word: len(word) for word in ["apple", "banana", "cherry"]}

算法复杂度¶

操作	时间复杂度	空间复杂度
列表访问	O(1)	O(1)
列表查找	O(n)	O(1)
字典访问	O(1)	O(1)
字典插入	O(1)	O(1)

高级数据结构¶

栈 (Stack)¶

栈是一种后进先出(LIFO)的数据结构：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """压栈操作"""
        self.items.append(item)

    def pop(self):
        """出栈操作"""
        if not self.is_empty():
            return self.items.pop()
        return None

    def is_empty(self):
        """检查栈是否为空"""
        return len(self.items) == 0

    def peek(self):
        """查看栈顶元素"""
        if not self.is_empty():
            return self.items[-1]
        return None

# 使用示例
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(f"栈顶元素: {stack.peek()}")  # 输出: 3

队列 (Queue)¶

队列是一种先进先出(FIFO)的数据结构：

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        """入队操作"""
        self.items.append(item)

    def dequeue(self):
        """出队操作"""
        if not self.is_empty():
            return self.items.popleft()
        return None

    def is_empty(self):
        return len(self.items) == 0

# 使用示例
queue = Queue()
queue.enqueue("第一个")
queue.enqueue("第二个")
print(queue.dequeue())  # 输出: "第一个"

排序算法¶

快速排序¶

def quicksort(arr):
    """快速排序算法实现"""
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quicksort(left) + middle + quicksort(right)

# 测试
test_array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quicksort(test_array)
print(f"排序结果: {sorted_array}")

数学公式¶

时间复杂度分析¶

快速排序的平均时间复杂度为：

\[T(n) = O(n \log n)\]

最坏情况下的时间复杂度为：

\[T(n) = O(n^2)\]

递推关系式：

\[T(n) = 2T(\frac{n}{2}) + O(n)\]

重要概念¶

Big O记号：用于描述算法的时间复杂度和空间复杂度的上界。它帮助我们理解算法在输入规模增长时的表现。

数据结构的选择：不同的数据结构适合不同的使用场景。选择合适的数据结构是编写高效程序的关键。

总结¶

列表适合需要顺序访问和频繁插入删除的场景
字典适合需要快速查找的场景
栈适合需要LIFO操作的场景
队列适合需要FIFO操作的场景

掌握这些基本数据结构为学习更高级的算法奠定了坚实的基础。

参考资料¶

Python官方文档
《算法导论》- Thomas H. Cormen
《Python数据结构与算法分析》- Brad Miller

目录