数据结构入门教程——从线性表到图

概述

数据结构是计算机科学的核心基础课程，研究数据的逻辑结构、存储结构以及相关算法。好的数据结构选择能够极大地提高程序的运行效率。本教程将系统讲解数据结构的核心知识，从最基本的线性表出发，逐步介绍栈与队列、树与二叉树、图，最后讲解查找与排序算法。

数据结构的学习不仅是编程的基础，更是培养计算思维的关键。理解不同数据结构的特点和适用场景，能够帮助我们在实际开发中做出最优选择。

---

知识点一：线性表

1.1 线性表的定义

线性表：由n（n≥0）个数据元素组成的有限序列。

• 当n=0时，为空表
• 除第一个和最后一个元素外，每个元素有且仅有一个前驱和一个后继

1.2 顺序存储——数组

顺序表：用一段连续的存储空间依次存储线性表中的数据元素。

特点：

• 支持随机访问，通过下标可以直接访问任意位置的元素，时间复杂度 O(1)
• 插入和删除需要移动大量元素，时间复杂度 O(n)
• 存储密度高，不需要额外的指针空间

基本操作及时间复杂度：

操作	时间复杂度
按下标查找	O(1)
按值查找	O(n)
在第i个位置插入	O(n)
删除第i个位置的元素	O(n)

1.3 链式存储——链表

链表：用一组任意的存储单元存放数据元素，通过指针将各元素链接起来。

单链表的结点结构：

[数据域 | 指针域]

单链表的基本操作：

头插法建表（新结点插入到头部）：

def create_list_head(data_list):
    head = None
    for data in data_list:
        node = Node(data)
        node.next = head
        head = node
    return head

尾插法建表（新结点插入到尾部）：

def create_list_tail(data_list):
    head = Node(None)  # 头结点
    tail = head
    for data in data_list:
        node = Node(data)
        tail.next = node
        tail = node
    return head.next

插入操作（在第i个位置插入）：

1. 找到第i-1个结点p
2. 创建新结点s
3. s.next = p.next
4. p.next = s

删除操作（删除第i个位置的结点）：

1. 找到第i-1个结点p
2. q = p.next（要删除的结点）
3. p.next = q.next
4. 释放q

1.4 双向链表与循环链表

双向链表：每个结点有前驱指针和后继指针，可以双向遍历。

循环链表：最后一个结点的指针指向头结点，形成环形结构。

---

知识点二：栈与队列

2.1 栈

栈的定义：只允许在一端（栈顶）进行插入和删除操作的线性表。遵循"后进先出"（LIFO）原则。

基本操作：

• push(x)：将元素x压入栈顶
• pop()：弹出栈顶元素并返回
• top()：获取栈顶元素（不弹出）
• isEmpty()：判断栈是否为空

顺序栈的实现：

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.isEmpty():
            return self.items.pop()
        return None
    
    def top(self):
        if not self.isEmpty():
            return self.items[-1]
        return None
    
    def isEmpty(self):
        return len(self.items) == 0

栈的应用：

• 括号匹配：遇到左括号入栈，遇到右括号出栈并匹配
• 表达式求值：将中缀表达式转换为后缀表达式，再利用栈求值
• 函数调用：系统使用调用栈管理函数调用
• 深度优先搜索（DFS）：用栈实现

2.2 队列

队列的定义：只允许在一端（队尾）插入、另一端（队头）删除的线性表。遵循"先进先出"（FIFO）原则。

基本操作：

• enqueue(x)：将元素x加入队尾
• dequeue()：删除队头元素并返回
• front()：获取队头元素
• isEmpty()：判断队列是否为空

循环队列：

为了解决顺序队列的"假溢出"问题，将数组首尾相连，形成循环队列。

• 队满条件：(rear + 1) % maxsize == front
• 队空条件：rear == front
• 元素个数：(rear - front + maxsize) % maxsize

队列的应用：

• 广度优先搜索（BFS）：用队列实现
• 操作系统中的进程调度：就绪队列、等待队列
• 打印机任务队列

---

知识点三：树与二叉树

3.1 树的基本概念

树：n（n≥0）个结点的有限集合。

• 当n=0时，为空树
• 有且仅有一个特定的称为根的结点
• 其余结点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树

基本术语：

• 结点的度：结点拥有的子树数
• 树的度：树中所有结点的度的最大值
• 叶子结点：度为0的结点
• 深度（高度）：从根到该结点的层数
• 父结点、子结点、兄弟结点

3.2 二叉树

二叉树：每个结点最多有两棵子树的树，且子树有左右之分。

特殊二叉树：

• 满二叉树：每一层的结点数都达到最大值
• 完全二叉树：除最后一层外，其他层的结点数都达到最大值，且最后一层的结点从左到右连续排列

二叉树的性质：

1. 第i层最多有 2^(i-1) 个结点
2. 深度为k的二叉树最多有 2^k - 1 个结点
3. n₀ = n₂ + 1（叶子结点数 = 度为2的结点数 + 1）
4. 完全二叉树中，结点i的父结点为 i/2，左子结点为 2i，右子结点为 2i+1

3.3 二叉树的遍历

先序遍历（根-左-右）：

def preorder(root):
    if root is None:
        return
    print(root.val)      # 访问根
    preorder(root.left)   # 遍历左子树
    preorder(root.right)  # 遍历右子树

中序遍历（左-根-右）：

def inorder(root):
    if root is None:
        return
    inorder(root.left)    # 遍历左子树
    print(root.val)       # 访问根
    inorder(root.right)   # 遍历右子树

后序遍历（左-右-根）：

def postorder(root):
    if root is None:
        return
    postorder(root.left)   # 遍历左子树
    postorder(root.right)  # 遍历右子树
    print(root.val)        # 访问根

层序遍历（从上到下，从左到右）：

from collections import deque

def levelorder(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

3.4 二叉搜索树（BST）

定义：左子树上所有结点的值都小于根结点的值，右子树上所有结点的值都大于根结点的值。

查找：从根开始，小于根往左走，大于根往右走。

def search(root, target):
    if root is None:
        return None
    if target == root.val:
        return root
    elif target < root.val:
        return search(root.left, target)
    else:
        return search(root.right, target)

平均时间复杂度：O(log n)（平衡时），最坏 O(n)（退化为链表）。

---

知识点四：图

4.1 图的基本概念

图：由顶点集合V和边集合E组成，记为 G = (V, E)。

基本术语：

• 无向图：边没有方向
• 有向图：边有方向（弧）
• 完全图：任意两个顶点之间都有边
• 连通图：任意两个顶点之间都有路径
• 度：与顶点相关联的边的数目（有向图分为入度和出度）
• 权：边上的数值（带权图称为网）

4.2 图的存储

邻接矩阵：

用一个二维数组表示图中顶点之间的邻接关系。

# 邻接矩阵
graph = [
    [0, 1, 1, 0],  # 顶点0与1、2相邻
    [1, 0, 1, 1],  # 顶点1与0、2、3相邻
    [1, 1, 0, 0],  # 顶点2与0、1相邻
    [0, 1, 0, 0],  # 顶点3与1相邻
]

邻接表：

为每个顶点建立一个链表，存储与该顶点相邻的所有顶点。

# 邻接表（用字典表示）
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1]
}

4.3 图的遍历

深度优先搜索（DFS）：

从起始顶点出发，沿着一条路径尽可能深地探索，直到无法继续时回溯。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

广度优先搜索（BFS）：

从起始顶点出发，先访问所有相邻顶点，再访问相邻顶点的相邻顶点。

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

4.4 最短路径算法

Dijkstra算法（单源最短路径，适用于非负权图）：

1. 初始化：起点距离为0，其他点距离为∞
2. 选择距离最小的未访问顶点u
3. 更新u的所有邻接顶点的距离
4. 标记u为已访问
5. 重复2-4直到所有顶点都被访问

时间复杂度：O(V²)（朴素实现），O((V+E)logV)（优先队列实现）

---

知识点五：查找与排序

5.1 查找算法

顺序查找：从头到尾逐个比较。

• 时间复杂度：O(n)
• 适用范围：无序表

二分查找：在有序表中，每次将查找范围缩小一半。

def binary_search(arr, target):
    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

• 时间复杂度：O(log n)
• 前提：表必须有序

哈希查找：通过哈希函数将关键字映射到存储位置。

• 平均时间复杂度：O(1)
• 冲突处理：开放地址法、链地址法

5.2 排序算法

冒泡排序：相邻元素两两比较，将大的元素往后"冒泡"。

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

选择排序：每次从未排序部分选择最小的元素放到已排序部分的末尾。

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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]
    return arr

快速排序：选择一个基准元素，将数组分为两部分（小于基准和大于基准），递归排序。

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)

归并排序：将数组分成两半，分别排序后合并。

def merge_sort(arr):
    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

排序算法比较：

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定

---

练习题

练习一：链表操作

给定单链表 1→3→5→7→9，写出在第3个位置插入元素6后的链表状态。

答案：

原链表：1→3→5→7→9

操作步骤：

1. 找到第2个结点（值为3）
2. 创建新结点（值为6）
3. 新结点的指针指向原第3个结点（值为5）
4. 第2个结点的指针指向新结点

结果：1→3→6→5→7→9

---

练习二：栈的应用

利用栈将中缀表达式 A + B * C - D 转换为后缀表达式。

答案：

转换过程：

读取	栈	输出
A		A
+	+	A
B	+	A B
*	+ *	A B
C	+ *	A B C
-	-	A B C * +
D	-	A B C * + D
结束		A B C * + D -

后缀表达式：A B C * + D -

---

练习三：二叉树遍历

已知二叉树的先序遍历为 ABDGCEFH，中序遍历为 DGBAECFH。请写出后序遍历结果。

答案：

分析：

• 先序遍历的第一个元素A是根
• 在中序遍历中找到A，左边DGB是左子树，右边ECFH是右子树
• 左子树的先序遍历：BDG，中序遍历：DGB → 根是B，左子树DG，右子树为空
• 右子树的先序遍历：CEFH，中序遍历：ECFH → 根是C，左子树E，右子树FH

构建二叉树：

        A
       / \
      B   C
     /   / \
    D   E   F
     \     /
      G   H

后序遍历（左-右-根）：G D B E H F C A

---

练习四：图的遍历

对以下无向图，分别写出从顶点A开始的DFS和BFS遍历结果。

A — B — D
|   |
C — E — F

邻接表：A:[B,C], B:[A,D,E], C:[A,E], D:[B], E:[B,C,F], F:[E]

答案：

DFS（深度优先，假设邻接表按字母序访问）：A → B → D → E → C → F

过程：A→B→D（回溯到B）→E→C（回溯到E）→F

BFS（广度优先）：A → B → C → D → E → F

过程：访问A，入队B、C；访问B，入队D、E；访问C（E已入队）；访问D；访问E，入队F；访问F

---

练习五：排序算法分析

对数组 [38, 27, 43, 3, 9, 82, 10] 进行一趟快速排序（以第一个元素为基准），写出一趟后的结果。

答案：

基准元素：38

初始：[38, 27, 43, 3, 9, 82, 10]

从右向左找小于38的元素：10 从左向右找大于38的元素：43 交换：[38, 27, 10, 3, 9, 82, 43]

从右向左找小于38的元素：9 从左向右找大于38的元素：82 交换：[38, 27, 10, 3, 9, 82, 43]

从右向左找小于38的元素：9（相遇） 将基准放到正确位置：[9, 27, 10, 3, 38, 82, 43]

一趟结果：[9, 27, 10, 3] 38 [82, 43]

---

总结

数据结构是计算机科学的基石，本教程涵盖了从线性表到图的核心数据结构以及查找和排序算法。学习数据结构需要注意以下几点：

1. 理解逻辑结构与存储结构的区别：逻辑结构是数据元素之间的逻辑关系，存储结构是数据在计算机中的实际存储方式
2. 掌握时间复杂度分析：能够分析各种操作的时间复杂度，是评估算法效率的关键
3. 选择合适的数据结构：不同的应用场景需要不同的数据结构，要根据实际需求做出选择
4. 多写代码实践：理论学习与编程实践相结合，通过实现各种数据结构加深理解

数据结构的学习是一个循序渐进的过程，建议同学们从简单到复杂，逐步掌握每种数据结构的特点和应用。同时，要注重算法思维的培养，学会将复杂问题分解为可以用基本数据结构和算法解决的子问题。