数据结构

宋涛2025年2月26日大约 5 分钟

数据结构是计算机科学的核心基础，其关心如何以合理且高效的方式组织、存储和操作数据。理解并掌握数据结构是编程能力提升的关键。

1. 数据结构简介

数据结构是计算机存储、组织数据的一种方式，旨在提高程序的运行效率和资源利用率。它是算法设计的基础，与算法配合，用于解决各类实际问题。

一个优秀的数据结构需满足以下特性：

高效性：能高效执行基本操作（如插入、删除、遍历）。
适用性：适合同类问题或特定场景。
灵活性：支持扩展和修改。

2. 数据结构分类

数据结构根据逻辑关系主要分为以下两类：

分类	描述	示例
线性结构	数据逐个链接，呈线性关系	数组、链表、栈、队列
非线性结构	数据之间呈复杂逻辑关系（如层次、图形）	树、图、哈希表

3. 线性数据结构

线性数据结构的特性是元素间具有顺序关系，每个元素最多有一个前驱和一个后继。

3.1 数组 (Array)

特性

存储方式：元素顺序连续存储，使用固定大小的内存空间。
访问效率：通过索引直接访问元素，时间复杂度为 O(1)。
缺点：插入和删除操作需要移动大量元素，时间复杂度为 O(n)。

应用场景

固定长度的数据存储
快速随机访问需求

示例代码（Python）

# 定义数组
arr = [1, 2, 3, 4]
# 随机访问
print(arr[2])  # 3
# 插入
arr.insert(2, 99)
# 删除
arr.remove(99)

3.2 链表 (Linked List)

特性

存储方式：通过指针动态存储，每个元素存储地址指向下一个元素。
访问效率：按序访问任意元素需要遍历，时间复杂度为 O(n)。
插入/删除：常数时间完成，适用于频繁插入/删除场景。

类型

单向链表：只有一个方向指针。
双向链表：每个节点有前驱和后继指针。
循环链表：尾节点指向头节点形成闭环。

示例代码（单链表，Python）

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

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

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

    def display(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next

# 初始化链表
ll = LinkedList()
ll.insert(3)
ll.insert(2)
ll.insert(1)
ll.display()  # 输出：1 -> 2 -> 3 ->

3.3 栈 (Stack)

特性

存储方式：后进先出 (LIFO)。
主要操作：
- push(x)：压栈，时间复杂度 O(1)。
- pop()：出栈，时间复杂度 O(1)。
应用场景：函数调用堆栈、括号匹配、浏览器的前进与后退。

示例代码

stack = []
stack.append(1)   # 压栈
stack.append(2)
print(stack.pop())  # 弹栈，输出：2

3.4 队列 (Queue)

特性

存储方式：先进先出 (FIFO)。
主要操作：
- enqueue(x)：入队。
- dequeue()：出队。
应用场景：任务调度，消息队列。

示例代码

from collections import deque
queue = deque()
queue.append(1)   # 入队
queue.append(2)
print(queue.popleft())  # 出队，输出：1

4. 非线性数据结构

非线性数据结构中，元素之间的关系更加复杂，可以具有层次和网状关系。

4.1 树 (Tree)

定义

树是一个层次化的非线性结构，节点具有父子关系。

基本术语

根节点：树的起始节点。
叶子节点：没有子节点的节点。
深度：从树的根到特定节点的最长路径。
高度：从特定节点到叶子节点的最长路径。

4.1.1 二叉树 (Binary Tree)

每个节点最多有两个子节点（左子树和右子树）。

示例代码

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

遍历方式

前序遍历 (根-左-右)
中序遍历 (左-根-右)
后序遍历 (左-右-根)

4.1.2 二叉搜索树 (BST)

特性：
- 左子树值 < 根值
- 右子树值 > 根值
操作：
- 搜索：时间复杂度 O(h)（h 是树的高度）。
- 插入/删除：时间复杂度 O(h)。

5. 哈希表 (Hash Table)

定义

基于 "键值对" 的数据存储，使用哈希函数将键映射到存储桶。查找、插入和删除的平均时间复杂度为 O(1)。

示例代码（Python）

hash_map = {}
hash_map["key1"] = "value1"
print(hash_map["key1"])  # 输出：value1

6. 总结

数据结构为高效解决问题提供了强大的理论基础和工具，例如提高运行效率，优化存储资源。掌握上述数据结构，并结合场景选择合适的工具，将显著提升您的编程能力和算法设计能力。

推荐学习资源：
- 《算法导论》
- LeetCode
- GeeksForGeeks 数据结构教程