数据结构链表、哈希表、图、树、搜索算法（Python）

class 数据结构,链表,图,树,搜索算法,排序

数据结构和算法是计算机科学的核心基础，理解这些概念和它们的实现对于高效软件开发至关重要。在本指南中，我们将详细介绍链表、树、图、哈希表、排序和搜索算法，包括它们的理论基础和 Python 代码实现。

1. 链表（Linked List）

理论

链表是一种线性数据结构，由节点组成。每个节点包含数据部分和指向下一个节点的指针。链表分为以下几种类型：

  • 单链表（Singly Linked List）： 每个节点只指向下一个节点。
  • 双链表（Doubly Linked List）： 每个节点有两个指针，分别指向前一个和后一个节点。
  • 循环链表（Circular Linked List）： 最后一个节点指向第一个节点，形成一个环。

单链表的实现

以下是单链表的基本实现，包括插入、删除、搜索等操作：

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(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 delete_node(self, key):
        current_node = self.head

        # 删除头节点
        if current_node and current_node.data == key:
            self.head = current_node.next
            current_node = None
            return

        # 删除非头节点
        prev_node = None
        while current_node and current_node.data != key:
            prev_node = current_node
            current_node = current_node.next

        if current_node is None:
            return

        prev_node.next = current_node.next
        current_node = None

    def search(self, key):
        current_node = self.head
        while current_node:
            if current_node.data == key:
                return True
            current_node = current_node.next
        return False

    def display(self):
        current_node = self.head
        elements = []
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        return elements

# 使用示例
linked_list = SinglyLinkedList()
linked_list.insert_at_beginning(3)
linked_list.insert_at_beginning(2)
linked_list.insert_at_end(4)
linked_list.insert_at_end(5)
linked_list.delete_node(3)

print("链表内容:", linked_list.display()) # 输出: [2, 4, 5]
print("搜索 4:", linked_list.search(4))  # 输出: True
print("搜索 3:", linked_list.search(3))  # 输出: False

双链表的实现

双链表的实现如下：

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = DNode(data)
        new_node.next = self.head
        if self.head:
            self.head.prev = new_node
        self.head = new_node

    def insert_at_end(self, data):
        new_node = DNode(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
        new_node.prev = last_node

    def delete_node(self, key):
        current_node = self.head

        # 删除头节点
        if current_node and current_node.data == key:
            self.head = current_node.next
            if self.head:
                self.head.prev = None
            current_node = None
            return

        # 删除非头节点
        while current_node and current_node.data != key:
            current_node = current_node.next

        if current_node is None:
            return

        if current_node.next:
            current_node.next.prev = current_node.prev
        if current_node.prev:
            current_node.prev.next = current_node.next

        current_node = None

    def display(self):
        current_node = self.head
        elements = []
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        return elements

# 使用示例
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.insert_at_beginning(3)
doubly_linked_list.insert_at_beginning(2)
doubly_linked_list.insert_at_end(4)
doubly_linked_list.insert_at_end(5)
doubly_linked_list.delete_node(3)

print("双链表内容:", doubly_linked_list.display()) # 输出: [2, 4, 5]

2. 树（Tree）

理论

树是一种分层数据结构，由节点组成。它的特点是每个节点有零个或多个子节点，且没有循环。树结构广泛用于组织数据、实现高效查找、插入、删除操作。

  • 二叉树（Binary Tree）： 每个节点最多有两个子节点（左子节点和右子节点）。
  • 二叉搜索树（Binary Search Tree, BST）： 每个节点的左子树包含的值小于该节点的值，右子树包含的值大于该节点的值。
  • 平衡树（Balanced Tree）： 通过各种机制（如 AVL 树、红黑树）保持树的高度平衡，确保高效操作。

二叉树的实现

以下是一个简单的二叉树实现，包括插入和遍历操作：

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

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if not self.root:
            self.root = TreeNode(data)
        else:
            self._insert_recursively(self.root, data)

    def _insert_recursively(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = TreeNode(data)
            else:
                self._insert_recursively(node.left, data)
        else:
            if node.right is None:
                node.right = TreeNode(data)
            else:
                self._insert_recursively(node.right, data)

    def inorder_traversal(self, node):
        if node:
            self.inorder_traversal(node.left)
            print(node.data, end=' ')
            self.inorder_traversal(node.right)

    def preorder_traversal(self, node):
        if node:
            print(node.data, end=' ')
            self.preorder_traversal(node.left)
            self.preorder_traversal(node.right)

    def postorder_traversal(self, node):
        if node:
            self.postorder_traversal(node.left)
            self.postorder_traversal(node.right)
            print(node.data, end=' ')

# 使用示例
binary_tree = BinaryTree()
binary_tree.insert(5)
binary_tree.insert(3)
binary_tree.insert(7)
binary_tree.insert(2)
binary_tree.insert(4)
binary_tree.insert(6)
binary_tree.insert(8)

print("中序遍历:", end=' ')
binary_tree.inorder_traversal(binary_tree.root)  # 输出: 2 3 4 5 6 7 8

print("\n前序遍历:", end=' ')
binary_tree.preorder_traversal(binary_tree.root)  # 输出: 5 3 2 4 7 6 8

print("\n后序遍历:", end=' ')
binary_tree.postorder_traversal(binary_tree.root)  # 输出: 2 4 3 6 8 7 5

二叉搜索树的实现

以下是一个简单的二叉搜索树实现，包括插入、搜索和删除操作：

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if not self.root:
            self.root = TreeNode(data)
        else:
            self._insert_recursively(self.root, data)

    def _insert_recursively(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = TreeNode(data)
            else:
                self._insert_recursively(node.left, data)
        else:
            if node.right is None:
                node.right = TreeNode(data)
            else:
                self._insert_recursively(node.right, data)

    def search(self, data):
        return self._search_recursively(self.root, data)

    def _search_recursively(self, node, data):
        if node is None or node.data == data:
            return node

        if data < node.data:
            return self

._search_recursively(node.left, data)
        return self._search_recursively(node.right, data)

    def delete(self, data):
        self.root = self._delete_recursively(self.root, data)

    def _delete_recursively(self, node, data):
        if node is None:
            return node

        if data < node.data:
            node.left = self._delete_recursively(node.left, data)
        elif data > node.data:
            node.right = self._delete_recursively(node.right, data)
        else:
            # 节点有一个或没有子节点
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left

            # 节点有两个子节点
            min_larger_node = self._find_min(node.right)
            node.data = min_larger_node.data
            node.right = self._delete_recursively(node.right, min_larger_node.data)

        return node

    def _find_min(self, node):
        current_node = node
        while current_node.left:
            current_node = current_node.left
        return current_node

    def inorder_traversal(self, node):
        if node:
            self.inorder_traversal(node.left)
            print(node.data, end=' ')
            self.inorder_traversal(node.right)

# 使用示例
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)
bst.insert(6)
bst.insert(8)

print("中序遍历:", end=' ')
bst.inorder_traversal(bst.root)  # 输出: 2 3 4 5 6 7 8

print("\n搜索 4:", bst.search(4))  # 输出: <__main__.TreeNode object at ...>
print("搜索 9:", bst.search(9))  # 输出: None

bst.delete(4)
print("删除 4 后中序遍历:", end=' ')
bst.inorder_traversal(bst.root)  # 输出: 2 3 5 6 7 8

3. 图（Graph）

理论

图是一种非线性数据结构，由顶点（节点）和边组成。图可以是有向的或无向的，也可以是加权的或无权的。图在建模网络结构（如社交网络、交通网络）中非常有用。

  • 有向图（Directed Graph）： 边有方向，表示从一个顶点指向另一个顶点。
  • 无向图（Undirected Graph）： 边无方向，表示两个顶点之间的连接。
  • 加权图（Weighted Graph）： 边具有权重，表示两个顶点之间的代价或距离。

图的实现

图的实现通常使用邻接表或邻接矩阵。以下是基于邻接表的简单图实现，包括深度优先搜索（DFS）和广度优先搜索（BFS）：

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.adjacency_list and vertex2 in self.adjacency_list:
            self.adjacency_list[vertex1].append(vertex2)
            self.adjacency_list[vertex2].append(vertex1)

    def dfs(self, start_vertex, visited=None):
        if visited is None:
            visited = set()
        visited.add(start_vertex)
        print(start_vertex, end=' ')
        for neighbor in self.adjacency_list[start_vertex]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

    def bfs(self, start_vertex):
        visited = set()
        queue = [start_vertex]
        visited.add(start_vertex)
        while queue:
            vertex = queue.pop(0)
            print(vertex, end=' ')
            for neighbor in self.adjacency_list[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

# 使用示例
graph = Graph()
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')
graph.add_vertex('E')

graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'E')

print("深度优先搜索:", end=' ')
graph.dfs('A')  # 输出: A B D C E

print("\n广度优先搜索:", end=' ')
graph.bfs('A')  # 输出: A B C D E

4. 哈希表（Hash Table）

理论

哈希表是一种通过哈希函数实现快速查找的数据结构。它将键映射到值，支持常数时间复杂度的插入、删除和查找操作。

  • 哈希函数（Hash Function）： 将输入（键）转换为固定大小的整数（哈希值）。
  • 冲突（Collision）： 不同的键映射到相同的哈希值时发生冲突。
  • 解决冲突的方法：
    • 链地址法（Chaining）： 每个桶中保存一个链表来存储冲突的键值对。
    • 开放地址法（Open Addressing）： 冲突时寻找下一个空闲位置。

哈希表的实现

以下是基于链地址法的简单哈希表实现：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])

    def search(self, key):
        index = self._hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

    def delete(self, key):
        index = self._hash_function(key)
        for i, pair in enumerate(self.table[index]):
            if pair[0] == key:
                del self.table[index][i]
                return

# 使用示例
hash_table = HashTable(10)
hash_table.insert('apple', 1)
hash_table.insert('banana', 2)
hash_table.insert('orange', 3)

print("搜索 'apple':", hash_table.search('apple'))  # 输出: 1
print("搜索 'banana':", hash_table.search('banana'))  # 输出: 2

hash_table.delete('apple')
print("删除 'apple' 后搜索 'apple':", hash_table.search('apple'))  # 输出: None

5. 排序算法

排序算法用于将数据按特定顺序排列。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序和归并排序等。

冒泡排序（Bubble Sort）

冒泡排序是一种简单的交换排序算法，反复比较相邻元素并交换。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("冒泡排序结果:", arr)  # 输出: [11, 12, 22, 25, 34, 64, 90]

选择排序（Selection Sort）

选择排序是一种简单的选择排序算法，每次从未排序部分选择最小（或最大）元素并放到排序部分的末尾。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# 使用示例
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("选择排序结果:", arr)  # 输出: [11, 12, 22, 25, 64]

插入排序（Insertion Sort）

插入排序是一种简单的插入排序算法，每次将一个元素插入到已经排序好的部分中。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 使用示例
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("插入排序结果:", arr

)  # 输出: [5, 6, 11, 12, 13]

快速排序（Quick Sort）

快速排序是一种分治排序算法，通过选择一个基准（pivot）将数组分为左右两部分，然后递归排序。

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

# 使用示例
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("快速排序结果:", sorted_arr)  # 输出: [1, 5, 7, 8, 9, 10]

归并排序（Merge Sort）

归并排序是一种分治排序算法，将数组分为两半，分别排序后合并。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    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

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# 使用示例
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("归并排序结果:", sorted_arr)  # 输出: [5, 6, 7, 11, 12, 13]

6. 搜索算法

搜索算法用于在数据结构中查找元素。常见的搜索算法包括线性搜索和二分搜索。

线性搜索（Linear Search）

线性搜索是一种简单的搜索算法，从头到尾逐一比较。

def linear_search(arr, target):
    for i, element in enumerate(arr):
        if element == target:
            return i
    return -1

# 使用示例
arr = [2, 3, 4, 10, 40]
target = 10
result = linear_search(arr, target)
print("线性搜索结果:", result)  # 输出: 3

二分搜索（Binary Search）

二分搜索是一种高效的搜索算法，适用于已排序数组，通过每次将搜索范围减半来查找元素。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 使用示例
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(arr, target)
print("二分搜索结果:", result)  # 输出: 3

总结

在本指南中，我们详细介绍了链表、树、图、哈希表、排序和搜索算法的理论和实现。这些数据结构和算法是软件开发的基础，理解它们的工作原理和应用场景对于编写高效程序至关重要。通过这些示例代码，你可以更好地理解每种数据结构和算法的实现细节，并在实践中应用它们。

评论区
评论列表
menu