Python数据结构与算法

Python数据结构与算法详解

1. 数据结构基础

1.1 线性表

1.1.1 数组(Array)

Python中没有原生的数组类型，通常使用列表(list)来模拟数组：

# 创建数组
arr = [1, 2, 3, 4, 5]

# 访问元素
print(arr[0])  # 输出: 1

# 修改元素
arr[2] = 10
print(arr)  # 输出: [1, 2, 10, 4, 5]

# 数组长度
print(len(arr))  # 输出: 5

1.1.2 链表(Linked List)

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
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
    
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用示例
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # 输出: 1 -> 2 -> 3 -> None

1.1.3 栈(Stack)

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 peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# 使用示例
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出: 3
print(stack.peek())  # 输出: 2

1.1.4 队列(Queue)

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
    
    def size(self):
        return len(self.items)

# 使用示例
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 输出: 1
print(queue.size())  # 输出: 2

1.2 非线性表

1.2.1 树(Tree)

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
    
    def add_child(self, child_node):
        self.children.append(child_node)
    
    def display(self, level=0):
        print("  " * level + str(self.value))
        for child in self.children:
            child.display(level + 1)

# 使用示例
root = TreeNode("A")
child1 = TreeNode("B")
child2 = TreeNode("C")
root.add_child(child1)
root.add_child(child2)
child1.add_child(TreeNode("D"))
child1.add_child(TreeNode("E"))
root.display()
"""
输出:
A
  B
    D
    E
  C
"""

1.2.2 二叉树(Binary Tree)

class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if not self.root:
            self.root = BinaryTreeNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = BinaryTreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = BinaryTreeNode(value)
            else:
                self._insert_recursive(node.right