常见数据结构与代码实现方案

# 创建数组arr = [1, 2, 3, 4, 5]
# 访问元素print(arr[0])  # 输出: 1
# 更新元素arr[1] = 20print(arr)  # 输出: [1, 20, 3, 4, 5]
# 添加元素arr.append(6)print(arr)  # 输出: [1, 20, 3, 4, 5, 6]
# 删除元素arr.pop(2)print(arr)  # 输出: [1, 20, 4, 5, 6]

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 = self.head        while last.next:            last = last.next        last.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

class Stack:    def __init__(self):        self.stack = []
    def push(self, item):        self.stack.append(item)
    def pop(self):        if not self.is_empty():            return self.stack.pop()
    def peek(self):        if not self.is_empty():            return self.stack[-1]
    def is_empty(self):        return len(self.stack) == 0
    def size(self):        return len(self.stack)
# 使用栈s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop())  # 输出: 3print(s.peek())  # 输出: 2print(s.size())  # 输出: 2

class Queue:    def __init__(self):        self.queue = []
    def enqueue(self, item):        self.queue.append(item)
    def dequeue(self):        if not self.is_empty():            return self.queue.pop(0)
    def is_empty(self):        return len(self.queue) == 0
    def size(self):        return len(self.queue)
# 使用队列q = Queue()q.enqueue(1)q.enqueue(2)q.enqueue(3)print(q.dequeue())  # 输出: 1print(q.size())  # 输出: 2

class HashTable:    def __init__(self):        self.table = [None] * 10
    def hash_function(self, key):        return hash(key) % len(self.table)
    def insert(self, key, value):        index = self.hash_function(key)        if not self.table[index]:            self.table[index] = []        self.table[index].append((key, value))
    def get(self, key):        index = self.hash_function(key)        if self.table[index]:            for k, v in self.table[index]:                if k == key:                    return v        return None
# 使用哈希表ht = HashTable()ht.insert('name', 'Alice')ht.insert('age', 25)print(ht.get('name'))  # 输出: Aliceprint(ht.get('age'))  # 输出: 25

class TreeNode:    def __init__(self, data):        self.data = data        self.left = None        self.right = None
def inorder_traversal(root):    if root:        inorder_traversal(root.left)        print(root.data, end=" ")        inorder_traversal(root.right)
# 创建二叉树root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)
# 中序遍历inorder_traversal(root)  # 输出: 4 2 5 1 3

class Graph:    def __init__(self):        self.graph = {}
    def add_edge(self, u, v):        if u not in self.graph:            self.graph[u] = []        self.graph[u].append(v)
    def bfs(self, start):        visited = set()        queue = [start]        while queue:            vertex = queue.pop(0)            if vertex not in visited:                print(vertex, end=" ")                visited.add(vertex)                queue.extend([v for v in self.graph.get(vertex, []) if v not in visited])
# 创建图并进行广度优先搜索g = Graph()g.add_edge(0, 1)g.add_edge(0, 2)g.add_edge(1, 2)g.add_edge(2, 0)g.add_edge(2, 3)g.add_edge(3, 3)
print("广度优先搜索（BFS）:")g.bfs(2)  # 输出: 2 0 3 1