算法与数据结构：编程的核心素养

算法与数据结构：编程的核心素养

算法和数据结构是计算机科学的基石，掌握它们对于解决复杂问题、编写高效代码至关重要。本文将深入探讨核心算法思想和数据结构设计。

基础数据结构

数组与链表

数组特点：

• 连续内存存储
• 随机访问O(1)
• 插入删除O(n)

链表特点：

• 非连续内存
• 顺序访问O(n)
• 插入删除O(1)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class 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 reverse(self):
        """反转链表 - 经典面试题"""
        prev = None
        current = self.head
        
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        
        self.head = prev
    
    def has_cycle(self):
        """检测链表是否有环 - Floyd算法"""
        slow = fast = self.head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                return True
        
        return False
​

栈与队列

from collections import deque

class Stack:
    """栈：后进先出(LIFO)"""
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[-1] if self.items else None
    
    def is_empty(self):
        return len(self.items) == 0

class Queue:
    """队列：先进先出(FIFO)"""
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        return self.items.popleft() if self.items else None
    
    def peek(self):
        return self.items[0] if self.items else None

# 应用：有效的括号
def is_valid_parentheses(s: str) -> bool:
    """使用栈检查括号有效性"""
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    
    return len(stack) == 0
​

哈希表

class HashMap:
    """简单哈希表实现"""
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
    
    def _hash(self, key):
        return hash(key) % self.capacity
    
    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        bucket.append((key, value))
        self.size += 1
        
        # 负载因子超过0.75时扩容
        if self.size / self.capacity > 0.75:
            self._resize()
    
    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        raise KeyError(key)
    
    def _resize(self):
        new_capacity = self.capacity * 2
        new_buckets = [[] for _ in range(new_capacity)]
        
        for bucket in self.buckets:
            for key, value in bucket:
                index = hash(key) % new_capacity
                new_buckets[index].append((key, value))
        
        self.capacity = new_capacity
        self.buckets = new_buckets
​

树结构

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert_recursive(self.root, val)
    
    def _insert_recursive(self, node, val):
        if val < node.val:
            if node.left is None:
                node.left = TreeNode(val)
            else:
                self._insert_recursive(node.left, val)
        else:
            if node.right is None:
                node.right = TreeNode(val)
            else:
                self._insert_recursive(node.right, val)
    
    def inorder_traversal(self):
        """中序遍历：左 -> 根 -> 右"""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.val)
            self._inorder_recursive(node.right, result)
    
    def level_order(self):
        """层序遍历 - 使用队列"""
        if not self.root:
            return []
        
        result = []
        queue = [self.root]
        
        while queue:
            node = queue.pop(0)
            result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        return result
    
    def max_depth(self):
        """计算树的最大深度"""
        return self._max_depth_recursive(self.root)
    
    def _max_depth_recursive(self, node):
        if not node:
            return 0
        return 1 + max(
            self._max_depth_recursive(node.left),
            self._max_depth_recursive(node.right)
        )
​

核心算法

排序算法

def quick_sort(arr):
    """快速排序：平均O(n log n)"""
    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 quick_sort(left) + middle + quick_sort(right)

def merge_sort(arr):
    """归并排序：稳定O(n log n)"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def heap_sort(arr):
    """堆排序：原地O(n log n)"""
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < n and arr[left] > arr[largest]:
            largest = left
        
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
    
    n = len(arr)
    
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 逐个提取元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr
​

搜索算法

def binary_search(arr, target):
    """二分搜索：O(log n)，要求数组已排序"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

def bfs(graph, start):
    """广度优先搜索"""
    visited = set()
    queue = [start]
    result = []
    
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            queue.extend(graph[vertex] - visited)
    
    return result

def dfs(graph, start):
    """深度优先搜索"""
    visited = set()
    result = []
    
    def dfs_recursive(vertex):
        visited.add(vertex)
        result.append(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs_recursive(neighbor)
    
    dfs_recursive(start)
    return result
​

动态规划

def fib(n, memo={}):
    """斐波那契数列：记忆化递归"""
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

def longest_common_subsequence(text1, text2):
    """最长公共子序列"""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

def knapsack(weights, values, capacity):
    """0-1背包问题"""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w-weights[i-1]] + values[i-1]
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]
​

贪心算法

def activity_selection(activities):
    """活动选择问题"""
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    last_end = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

def huffman_encoding(text):
    """霍夫曼编码"""
    from heapq import heappush, heappop
    
    # 统计频率
    freq = {}
    for char in text:
        freq[char] = freq.get(char, 0) + 1
    
    # 构建优先队列
    heap = [[weight, [symbol, ""]] for symbol, weight in freq.items()]
    heappush(heap, [0, None])
    
    while len(heap) > 1:
        lo = heappop(heap)
        hi = heappop(heap)
        
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        
        heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    huffman_code = {}
    for pair in heap[0][1:]:
        huffman_code[pair[0]] = pair[1]
    
    return huffman_code
​

图算法

class Graph:
    def __init__(self):
        self.adjacency_list = {}
    
    def add_edge(self, vertex1, vertex2, weight=None):
        if vertex1 not in self.adjacency_list:
            self.adjacency_list[vertex1] = []
        if vertex2 not in self.adjacency_list:
            self.adjacency_list[vertex2] = []
        
        self.adjacency_list[vertex1].append((vertex2, weight))
        self.adjacency_list[vertex2].append((vertex1, weight))
    
    def dijkstra(self, start):
        """Dijkstra最短路径算法"""
        import heapq
        
        distances = {vertex: float('infinity') for vertex in self.adjacency_list}
        distances[start] = 0
        pq = [(0, start)]
        
        while pq:
            current_distance, current_vertex = heapq.heappop(pq)
            
            if current_distance > distances[current_vertex]:
                continue
            
            for neighbor, weight in self.adjacency_list[current_vertex]:
                distance = current_distance + (weight or 1)
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(pq, (distance, neighbor))
        
        return distances
    
    def prim_mst(self):
        """Prim最小生成树算法"""
        import heapq
        
        if not self.adjacency_list:
            return []
        
        start = next(iter(self.adjacency_list))
        visited = set()
        edges = []
        pq = [(0, start, None)]
        
        while pq:
            weight, vertex, parent = heapq.heappop(pq)
            
            if vertex in visited:
                continue
            
            visited.add(vertex)
            
            if parent is not None:
                edges.append((parent, vertex, weight))
            
            for neighbor, edge_weight in self.adjacency_list[vertex]:
                if neighbor not in visited:
                    heapq.heappush(pq, (edge_weight or 1, neighbor, vertex))
        
        return edges
​

算法设计技巧

分治法

def max_subarray_sum(arr):
    """最大子数组和 - 分治法"""
    def divide_and_conquer(left, right):
        if left == right:
            return arr[left]
        
        mid = (left + right) // 2
        
        # 左半部分最大值
        left_max = divide_and_conquer(left, mid)
        # 右半部分最大值
        right_max = divide_and_conquer(mid + 1, right)
        # 跨中线最大值
        cross_max = max_crossing_sum(left, mid, right)
        
        return max(left_max, right_max, cross_max)
    
    def max_crossing_sum(left, mid, right):
        # 向左扩展
        left_sum = float('-inf')
        total = 0
        for i in range(mid, left - 1, -1):
            total += arr[i]
            left_sum = max(left_sum, total)
        
        # 向右扩展
        right_sum = float('-inf')
        total = 0
        for i in range(mid + 1, right + 1):
            total += arr[i]
            right_sum = max(right_sum, total)
        
        return left_sum + right_sum
    
    return divide_and_conquer(0, len(arr) - 1)
​

回溯法

def n_queens(n):
    """N皇后问题"""
    def solve(row, cols, diagonals, anti_diagonals):
        if row == n:
            return [["Q" if col in cols else "." for col in range(n)] 
                    for row in range(n)]
        
        for col in range(n):
            diag = row - col
            anti_diag = row + col
            
            if (col in cols or diag in diagonals or 
                anti_diag in anti_diagonals):
                continue
            
            cols.add(col)
            diagonals.add(diag)
            anti_diagonals.add(anti_diag)
            
            result = solve(row + 1, cols, diagonals, anti_diagonals)
            if result:
                return result
            
            cols.remove(col)
            diagonals.remove(diag)
            anti_diagonals.remove(anti_diag)
        
        return None
    
    return solve(0, set(), set(), set())
​

位运算技巧

class BitManipulation:
    @staticmethod
    def count_set_bits(n):
        """计算设置位数量（Brian Kernighan算法）"""
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
    
    @staticmethod
    def is_power_of_two(n):
        """检查是否为2的幂"""
        return n > 0 and (n & (n - 1)) == 0
    
    @staticmethod
    def get_single_number(nums):
        """找出只出现一次的数字"""
        result = 0
        for num in nums:
            result ^= num
        return result
    
    @staticmethod
    def swap_numbers(a, b):
        """不使用临时变量交换两个数"""
        a = a ^ b
        b = a ^ b
        a = a ^ b
        return a, b
​

性能分析

时间复杂度

O(1)      常数时间      数组访问
O(log n)  对数时间      二分搜索
O(n)      线性时间      简单循环
O(n log n) 线性对数时间  高效排序
O(n²)     平方时间      冒泡排序
O(n³)     立方时间      三层嵌套循环
O(2ⁿ)     指数时间      递归斐波那契
​

空间复杂度

• O(1)：常数空间
• O(n)：线性空间
• O(log n)：递归栈空间
• O(n²)：二维数组

总结

算法和数据结构是编程的基础，掌握它们能够帮助你：

1. 编写更高效的代码
2. 解决复杂问题
3. 通过技术面试
4. 优化系统性能

通过持续练习和应用，这些概念将成为你的第二天性，帮助你成为一名更优秀的程序员。