数据结构与算法基础 🧱

Li JiaXin大约 10 分钟

数据结构与算法基础 🧱

嘿！欢迎来到"程序员的乐高世界"！🎮

数据结构就像乐高积木，每种积木都有自己的"超能力"。算法呢？就是用这些积木搭建出各种酷炫建筑的"说明书"！

作为测试开发工程师，掌握这些知识就像武侠小说里的"内功心法"，看起来不起眼，但关键时刻能救命！不信？等你遇到性能问题时就知道了。😏

线性数据结构 - "排队的艺术" 📏

线性数据结构就像各种排队方式，每种都有自己的"个性"。

数组（Array）- "整齐划一的士兵方阵" 🪖

数组就像军队里的士兵方阵，每个士兵都有固定的位置，想找谁直接报编号就行！

特性分析 - "士兵方阵的特点"

时间复杂度：
- 访问：O(1) - "报编号，立刻找到！"
- 搜索：O(n) - "不知道编号？那就一个个问吧"
- 插入：O(n) - "插队？后面的人都要往后挪"
- 删除：O(n) - "有人离队？后面的人都要往前补"
空间复杂度：O(n) - "有多少士兵就占多少位置"

测试应用场景 - "士兵方阵的考验"

边界测试：试试能不能找到"第-1个士兵"（越界访问检测）
性能测试：看看指挥一万个士兵需要多长时间
内存测试：士兵方阵解散后，营地是否清理干净
并发测试：多个指挥官同时下令会不会乱套

测试用例设计 - "士兵方阵的演习"

# 边界值测试示例 - "测试士兵方阵的极限"
def test_array_boundary():
    """测试数组边界，就像测试士兵方阵的边界"""
    soldiers = ["张三", "李四", "王五", "赵六", "钱七"]

    # 正常点名 - "报数正常"
    assert soldiers[0] == "张三"  # 第一个士兵
    assert soldiers[4] == "钱七"  # 最后一个士兵

    # 边界测试 - "试试能不能找到不存在的士兵"
    try:
        ghost_soldier = soldiers[5]  # 试图找第6个士兵
        assert False, "居然找到了第6个士兵？见鬼了！"
    except IndexError:
        print("很好，没有找到不存在的士兵")

链表（Linked List）- "手拉手的小朋友" 👫

链表就像一群手拉手的小朋友，每个小朋友都知道下一个小朋友是谁，但不知道其他人在哪里。

类型与特性 - "不同的手拉手方式"

单向链表：只能向前走，就像单行道 ➡️
双向链表：可以前进后退，就像双向车道 ↔️
循环链表：首尾相连，就像围成圈的小朋友 🔄

时间复杂度 - "找小朋友的效率"

访问：O(n) - "要找第n个小朋友？从头开始数吧"
搜索：O(n) - "找特定的小朋友？一个个问过去"
插入：O(1) - "插队很容易，松开手再牵上就行"
删除：O(1) - "离队也简单，两边的小朋友直接牵手"

测试关注点 - "小朋友队伍的安全检查"

内存泄露：小朋友离队后是否真的"回家"了（内存释放）
指针安全：会不会出现"牵空气"的情况（空指针）
环路检测：圆圈队伍是否真的连成了圈
并发安全：多个老师同时指挥会不会乱套

形象比喻：

数组像电影院的座位（有固定编号）
链表像排队买奶茶（只知道前面是谁）

栈（Stack）- "叠盘子的艺术" 🍽️

栈就像餐厅里叠盘子，最后放上去的盘子最先被拿走。这就是传说中的"后进先出"（LIFO）！

核心操作 - "叠盘子的基本动作"

push()：往上叠一个盘子，O(1) - "啪！放上去"
pop()：拿走最上面的盘子，O(1) - "啪！拿下来"
top()/peek()：看看最上面是什么盘子，O(1) - "瞄一眼"
isEmpty()：看看还有没有盘子，O(1) - "空了吗？"

应用场景 - "叠盘子在哪里有用"

函数调用栈：就像俄罗斯套娃，一层套一层（递归测试）
表达式求值：括号匹配，就像检查括号是否配对 ((()))
浏览器历史：后退按钮，回到上一个页面
撤销操作：Ctrl+Z，撤销最近的操作

测试策略 - "测试叠盘子的极限"

def test_stack_overflow():
    """测试栈溢出 - 看看能叠多少盘子"""
    plate_stack = Stack(max_size=1000)  # 最多叠1000个盘子

    # 正常叠盘子测试
    for i in range(999):
        plate_stack.push(f"盘子{i}")

    # 边界测试 - 叠最后一个盘子
    plate_stack.push("最后一个盘子")  # 应该成功

    # 溢出测试 - 再叠一个试试
    try:
        plate_stack.push("多余的盘子")  # 应该失败
        assert False, "居然还能叠？这盘子是魔法盘子吗？"
    except StackOverflowError:
        print("很好，盘子叠不下了，符合物理定律！")

栈的内心独白："我是个有原则的数据结构，后来的先走，这是规矩！"

队列（Queue）- "排队买奶茶" 🧋

队列就像奶茶店门口的排队，先来的先买到，后来的只能乖乖排在后面。这就是"先进先出"（FIFO）的精神！

类型变种 - "不同的排队方式"

普通队列：老老实实排队，先来先得 📏
优先队列：VIP可以插队，按重要性排序 👑
双端队列：两头都能进出，就像地铁的两个门 🚇
循环队列：排成一个圈，节省空间 🔄

测试应用 - "排队系统的测试"

消息队列测试：确保消息按顺序处理，不能乱套
任务调度测试：任务要按先后顺序执行
缓冲区测试：生产者生产，消费者消费，不能堵车
流量控制测试：队伍满了怎么办？拒绝服务还是扩容？

队列的内心独白："排队要有秩序，先来后到是基本礼貌！"

形象比喻：

栈像叠盘子（后进先出）
队列像排队买票（先进先出）
优先队列像医院急诊（按紧急程度）
双端队列像地铁车厢（两头都有门）

非线性数据结构

树（Tree）

二叉树特性

完全二叉树：除最后一层外都是满的
满二叉树：所有叶子节点在同一层
平衡二叉树：左右子树高度差不超过1

遍历方法

前序遍历：根-左-右
中序遍历：左-根-右
后序遍历：左-右-根
层序遍历：按层从上到下

测试要点

def test_binary_tree_traversal():
    """测试二叉树遍历的正确性"""
    tree = BinaryTree()
    tree.insert(5)
    tree.insert(3)
    tree.insert(7)
    tree.insert(1)
    tree.insert(9)
    
    # 中序遍历应该是有序的
    inorder_result = tree.inorder_traversal()
    assert inorder_result == [1, 3, 5, 7, 9]
    
    # 验证树的平衡性
    assert tree.is_balanced()

图（Graph）

图的表示

邻接矩阵：适合稠密图
邻接表：适合稀疏图

图算法

深度优先搜索（DFS）：O(V+E)
广度优先搜索（BFS）：O(V+E)
最短路径算法：Dijkstra、Floyd-Warshall
最小生成树：Kruskal、Prim

测试场景

网络拓扑测试：验证网络连通性
依赖关系测试：检测循环依赖
路径规划测试：最优路径算法验证

哈希表（Hash Table）

冲突解决方法

链地址法：用链表存储冲突元素
开放地址法：线性探测、二次探测、双重哈希

性能分析

平均情况：O(1)查找、插入、删除
最坏情况：O(n)（所有元素冲突）
负载因子：影响性能的关键指标

测试策略

def test_hash_table_performance():
    """测试哈希表性能"""
    hash_table = HashTable(size=1000)
    
    # 插入大量数据
    start_time = time.time()
    for i in range(10000):
        hash_table.put(f"key_{i}", f"value_{i}")
    insert_time = time.time() - start_time
    
    # 验证查找性能
    start_time = time.time()
    for i in range(10000):
        assert hash_table.get(f"key_{i}") == f"value_{i}"
    search_time = time.time() - start_time
    
    # 性能断言
    assert insert_time < 1.0  # 插入应该在1秒内完成
    assert search_time < 0.5  # 查找应该在0.5秒内完成

排序算法

比较排序算法

冒泡排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定
适用场景：教学演示，小数据集

快速排序

时间复杂度：平均O(n log n)，最坏O(n²)
空间复杂度：O(log n)
稳定性：不稳定
适用场景：大数据集，内存排序

归并排序

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定性：稳定
适用场景：外部排序，稳定性要求高

非比较排序算法

计数排序

时间复杂度：O(n+k)，k为数据范围
适用条件：数据范围有限
测试要点：边界值处理、内存使用

基数排序

时间复杂度：O(d×(n+k))，d为位数
适用场景：整数排序、字符串排序
测试要点：不同进制的处理

排序算法测试框架

def test_sorting_algorithms():
    """通用排序算法测试"""
    test_cases = [
        [],  # 空数组
        [1],  # 单元素
        [1, 2, 3, 4, 5],  # 已排序
        [5, 4, 3, 2, 1],  # 逆序
        [3, 1, 4, 1, 5, 9, 2, 6],  # 随机序列
        [1, 1, 1, 1],  # 重复元素
    ]
    
    algorithms = [bubble_sort, quick_sort, merge_sort]
    
    for algorithm in algorithms:
        for test_case in test_cases:
            original = test_case.copy()
            result = algorithm(test_case.copy())
            expected = sorted(original)
            assert result == expected, f"{algorithm.__name__} failed on {original}"

查找算法

线性查找

时间复杂度：O(n)
适用场景：无序数据、小数据集

二分查找

时间复杂度：O(log n)
前提条件：数据已排序
测试要点：边界处理、重复元素

哈希查找

时间复杂度：平均O(1)
测试要点：冲突处理、负载因子

算法复杂度分析

时间复杂度等级

O(1)：常数时间
O(log n)：对数时间
O(n)：线性时间
O(n log n)：线性对数时间
O(n²)：平方时间
O(2ⁿ)：指数时间

空间复杂度考虑

原地算法：O(1)额外空间
递归算法：考虑调用栈空间
动态规划：权衡时间和空间

性能测试方法

def performance_test(algorithm, data_sizes):
    """算法性能测试"""
    results = []
    
    for size in data_sizes:
        data = generate_random_data(size)
        
        start_time = time.time()
        algorithm(data)
        end_time = time.time()
        
        execution_time = end_time - start_time
        results.append((size, execution_time))
    
    # 分析时间复杂度趋势
    analyze_complexity_trend(results)
    return results