Python 是一种流行的编程语言，具有简单易学、功能强大的特点。它不仅适用于快速开发，还可以用于实现各种数据结构和算法。本文将介绍如何使用 Python 实现一些常见的数据结构和算法，并提供相应的代码示例。

1. 数组

数组是一种基本的数据结构，用于存储一系列元素。在 Python 中，可以使用列表（List）来实现数组的功能。

# 创建一个整数数组array = [1, 2, 3, 4, 5]# 访问数组元素print(array[0])  # 输出：1# 修改数组元素array[0] = 10print(array)  # 输出：[10, 2, 3, 4, 5]# 遍历数组元素for num in array:    print(num)

2. 栈

栈是一种后进先出（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()        else:            return None    def peek(self):        if not self.is_empty():            return self.items[-1]        else:            return None    def is_empty(self):        return len(self.items) == 0def evaluate_expression(expression):    def apply_op(op1, op2, operator):        if operator == '+':            return op1 + op2        elif operator == '-':            return op1 - op2        elif operator == '*':            return op1 * op2        elif operator == '/':            if op2 != 0:                return op1 / op2            else:                raise ValueError("Cannot divide by zero")    operators = Stack()    operands = Stack()    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}    tokens = expression.split()    for token in tokens:        if token.isdigit():            operands.push(int(token))        elif token in '+-*/':            while (not operators.is_empty()) and (precedence[operators.peek()] >= precedence[token]):                operand2 = operands.pop()                operand1 = operands.pop()                operator = operators.pop()                operands.push(apply_op(operand1, operand2, operator))            operators.push(token)    while not operators.is_empty():        operand2 = operands.pop()        operand1 = operands.pop()        operator = operators.pop()        operands.push(apply_op(operand1, operand2, operator))    return operands.pop()# 示例用法result = evaluate_expression('3 + 5 * 2')print(result)  # 输出应为 13

3. 队列

队列是一种先进先出（FIFO）的数据结构，常用于任务调度、广度优先搜索等场景。

from collections import deque# 创建一个队列queue = deque()# 入队queue.append(1)queue.append(2)queue.append(3)# 出队print(queue.popleft())  # 输出：1print(queue.popleft())  # 输出：2

4. 链表

链表是一种动态数据结构，每个元素都包含指向下一个元素的引用。

class Node:    def __init__(self, data):        self.data = data        self.next = Noneclass LinkedList:    def __init__(self):        self.head = None    def append(self, data):        new_node = Node(data)        if not self.head:            self.head = new_node            return        current = self.head        while current.next:            current = current.next        current.next = new_node    def display(self):        current = self.head        while current:            print(current.data, end=' -> ')            current = current.next        print('None')# 创建一个链表llist = LinkedList()llist.append(1)llist.append(2)llist.append(3)# 显示链表元素llist.display()  # 输出：1 -> 2 -> 3 -> None

5. 排序算法

排序算法是计算机科学中的经典问题之一，Python 提供了多种排序算法的实现。

# 冒泡排序def bubble_sort(arr):    n = len(arr)    for i in range(n - 1):        for j in range(n - i - 1):            if arr[j] > arr[j + 1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]    return arr# 测试排序算法arr = [64, 34, 25, 12, 22, 11, 90]print(bubble_sort(arr))  # 输出：[11, 12, 22, 25, 34, 64, 90]

以上是一些常见的数据结构和算法在 Python 中的实现。通过学习和掌握这些内容，可以帮助你更好地理解和应用 Python 编程语言。

6. 应用场景：图搜索算法

图搜索算法是计算机科学中解决许多现实世界问题的重要工具，如社交网络分析、路径规划等。在 Python 中，我们可以使用图搜索算法来解决各种复杂的问题。

6.1 广度优先搜索（BFS）

广度优先搜索是一种用于图的搜索算法，它从起始节点开始，逐层遍历图中的节点，直到找到目标节点或遍历完整个图。

from collections import defaultdict, dequeclass Graph:    def __init__(self):        self.graph = defaultdict(list)    def add_edge(self, u, v):        self.graph[u].append(v)    def bfs(self, start):        visited = set()        queue = deque([start])        while queue:            vertex = queue.popleft()            if vertex not in visited:                print(vertex, end=' ')                visited.add(vertex)                queue.extend(self.graph[vertex])# 创建一个图实例graph = Graph()graph.add_edge(0, 1)graph.add_edge(0, 2)graph.add_edge(1, 2)graph.add_edge(2, 0)graph.add_edge(2, 3)graph.add_edge(3, 3)print("BFS traversal starting from vertex 2:")graph.bfs(2)

6.2 深度优先搜索（DFS）

深度优先搜索是另一种图搜索算法，它从起始节点开始，沿着一条路径一直搜索到底，然后回溯并探索其他路径。

from collections import defaultdictclass Graph:    def __init__(self):        self.graph = defaultdict(list)    def add_edge(self, u, v):        self.graph[u].append(v)    def dfs_util(self, vertex, visited):        visited.add(vertex)        print(vertex, end=' ')        for neighbor in self.graph[vertex]:            if neighbor not in visited:                self.dfs_util(neighbor, visited)    def dfs(self, start):        visited = set()        self.dfs_util(start, visited)# 创建一个图实例graph = Graph()graph.add_edge(0, 1)graph.add_edge(0, 2)graph.add_edge(1, 2)graph.add_edge(2, 0)graph.add_edge(2, 3)graph.add_edge(3, 3)print("\nDFS traversal starting from vertex 2:")graph.dfs(2)

7. 数据结构应用

字典树（Trie）是一种树形数据结构，用于高效地存储和检索字符串数据集中的键值。在实际应用中，字典树可以用于实现自动完成功能，即根据用户输入的前缀，快速地提供可能的完整词汇列表。

7.1 实现基于字典树的自动完成

class TrieNode:    def __init__(self):        self.children = {}        self.is_end_of_word = Falseclass Trie:    def __init__(self):        self.root = TrieNode()    def insert(self, word):        node = self.root        for char in word:            if char not in node.children:                node.children[char] = TrieNode()            node = node.children[char]        node.is_end_of_word = True    def search(self, prefix):        node = self.root        for char in prefix:            if char not in node.children:                return []            node = node.children[char]        return self._get_words_with_prefix(node, prefix)    def _get_words_with_prefix(self, node, prefix):        results = []        if node.is_end_of_word:            results.append(prefix)        for char, child in node.children.items():            results.extend(self._get_words_with_prefix(child, prefix + char))        return results# 示例应用trie = Trie()words = ["apple", "app", "application", "apricot", "banana", "bat", "batman"]for word in words:    trie.insert(word)prefix = "app"print(f"Words with prefix '{prefix}':", trie.search(prefix))

7.2 实现基于优先队列的任务调度器

优先队列是一种常见的数据结构，它可以按照优先级对元素进行排序，并支持高效地插入和删除操作。在任务调度器中，我们可以使用优先队列来管理各种任务，并按照优先级执行它们。

import heapqclass TaskScheduler:    def __init__(self):        self.tasks = []        self.counter = 0    def add_task(self, priority, task):        heapq.heappush(self.tasks, (priority, self.counter, task))        self.counter += 1    def execute_next_task(self):        if self.tasks:            priority, _, task = heapq.heappop(self.tasks)            print(f"Executing task: {task}")        else:            print("No tasks to execute.")# 示例应用scheduler = TaskScheduler()scheduler.add_task(3, "Task 1")scheduler.add_task(1, "Task 2")scheduler.add_task(2, "Task 3")scheduler.execute_next_task()  # 执行 Task 2scheduler.execute_next_task()  # 执行 Task 3scheduler.execute_next_task()  # 执行 Task 1scheduler.execute_next_task()  # 没有任务可执行

7.3 实现基于红黑树的高效映射

红黑树是一种自平衡的二叉查找树，它能够在O(log n)时间内完成插入、删除和查找操作，适用于需要高效查找和有序遍历的场景。下面我们将实现一个基于红黑树的高效映射，支持常见的键值对操作。

class RedBlackTreeNode:    def __init__(self, key, value, color='red'):        self.key = key        self.value = value        self.color = color        self.left = None        self.right = None        self.parent = Noneclass RedBlackTree:    def __init__(self):        self.nil = RedBlackTreeNode(None, None, color='black')        self.root = self.nil    def insert(self, key, value):        new_node = RedBlackTreeNode(key, value)        parent = None        current = self.root        while current != self.nil:            parent = current            if key < current.key:                current = current.left            else:                current = current.right        new_node.parent = parent        if parent is None:            self.root = new_node        elif key < parent.key:            parent.left = new_node        else:            parent.right = new_node        new_node.left = self.nil        new_node.right = self.nil        new_node.color = 'red'        self._insert_fixup(new_node)    def _insert_fixup(self, node):        while node.parent and node.parent.color == 'red':  # 添加额外的检查来避免空指针异常            if node.parent == node.parent.parent.left:                uncle = node.parent.parent.right                if uncle.color == 'red':                    node.parent.color = 'black'                    uncle.color = 'black'                    node.parent.parent.color = 'red'                    node = node.parent.parent                else:                    if node == node.parent.right:                        node = node.parent                        self._left_rotate(node)                    node.parent.color = 'black'                    node.parent.parent.color = 'red'                    self._right_rotate(node.parent.parent)            else:                uncle = node.parent.parent.left                if uncle.color == 'red':                    node.parent.color = 'black'                    uncle.color = 'black'                    node.parent.parent.color = 'red'                    node = node.parent.parent                else:                    if node == node.parent.left:                        node = node.parent                        self._right_rotate(node)                    node.parent.color = 'black'                    node.parent.parent.color = 'red'                    self._left_rotate(node.parent.parent)        self.root.color = 'black'    def _left_rotate(self, x):        y = x.right        x.right = y.left        if y.left != self.nil:            y.left.parent = x        y.parent = x.parent        if x.parent is None:            self.root = y        elif x == x.parent.left:            x.parent.left = y        else:            x.parent.right = y        y.left = x        x.parent = y    def _right_rotate(self, y):        x = y.left        y.left = x.right        if x.right != self.nil:            x.right.parent = y        x.parent = y.parent        if y.parent is None:            self.root = x        elif y == y.parent.right:            y.parent.right = x        else:            y.parent.left = x        x.right = y        y.parent = x    def search(self, key):        current = self.root        while current != self.nil:            if key == current.key:                return current.value            elif key < current.key:                current = current.left            else:                current = current.right        return None# 示例应用rb_tree = RedBlackTree()rb_tree.insert(10, "A")rb_tree.insert(5, "B")rb_tree.insert(15, "C")rb_tree.insert(3, "D")rb_tree.insert(7, "E")print("Value associated with key 10:", rb_tree.search(10))print("Value associated with key 3:", rb_tree.search(3))print("Value associated with key 20:", rb_tree.search(20))