第19章数据结构基础

课程目录第19章数据结构基础

一、数据结构到底是什么？

说实话，很多初学者一听到「数据结构」四个字就头大。我当年也一样，觉得这玩意儿太抽象了。但后来做了十几年嵌入式开发，我才真正明白——数据结构说白了就是「组织数据的方式」。

你想想看，我们写程序天天跟数据打交道。数据怎么存、怎么取、怎么管理，这就是数据结构要解决的问题。我做过一个智能家居项目，传感器数据量一大，用数组硬存，结果查个数据要遍历半天。后来换成哈希表，速度直接起飞。

1.1 数据结构的分类

数据结构分两大类：逻辑结构和存储结构。逻辑结构是数据之间的逻辑关系，存储结构是数据在内存里怎么放的。

逻辑结构又分四种：

集合：数据之间没啥关系，就是一堆东西放一起。比如你手机里的联系人，谁跟谁都没关系。
线性结构：数据排成一队，一对一的关系。数组、链表、栈、队列都属于这一类。
树形结构：一对多的关系，像公司组织架构。二叉树、堆、红黑树都是典型。
图形结构：多对多的关系，像地铁线路图。图论里全是这个。

存储结构就两种：

顺序存储：数据在内存里挨着放，数组就是典型。优点是随机访问快，缺点是插入删除麻烦。
链式存储：数据不挨着，靠指针连起来。链表就是典型。优点是插入删除方便，缺点是不能随机访问。

核心要点：逻辑结构是「怎么想」，存储结构是「怎么存」。同一个逻辑结构可以用不同的存储结构实现。比如线性表，既可以用数组实现，也可以用链表实现。

二、算法复杂度分析——到底快不快？

写代码谁都会，但写得好不好，就看你对复杂度的理解深不深。我面试嵌入式工程师时，必问复杂度分析。为什么？因为嵌入式资源有限，一个低效算法可能直接让系统崩溃。

2.1 时间复杂度

时间复杂度不是代码跑了几秒，而是算法执行时间随数据规模增长的变化趋势。说白了，就是数据量翻倍时，你的代码要多跑多久。

举个简单的例子：

// 例1：O(1) 常数时间
int getFirst(int arr[]) {
    return arr[0];  // 不管数组多大，都是一步
}

// 例2：O(n) 线性时间
int sum(int arr[], int n) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += arr[i];  // 数组越大，循环次数越多
    }
    return s;
}

// 例3：O(n²) 平方时间
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

看到没？同样的数据规模，O(n²)的冒泡排序比O(n)的求和慢了不止一个数量级。我在项目中遇到过，一个排序算法没选好，导致系统响应时间从10ms飙到500ms。嗯，后来果断换了快速排序。

2.2 空间复杂度

空间复杂度衡量的是算法运行过程中占用的额外内存。嵌入式开发里，内存比时间更金贵。我曾经在一个STM32项目里，为了省128字节的RAM，把递归改成了迭代。

// 例4：O(1) 常数空间
int add(int a, int b) {
    return a + b;  // 就用了两个参数，不额外占内存
}

// 例5：O(n) 线性空间
int* duplicate(int arr[], int n) {
    int* newArr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        newArr[i] = arr[i];  // 额外分配了n个int的空间
    }
    return newArr;
}

避坑指南：我曾经在递归实现斐波那契数列时，没注意空间复杂度，结果n=50时直接栈溢出。递归虽然代码简洁，但每层调用都要压栈，空间复杂度是O(n)。后来改成迭代，空间复杂度降到O(1)。

三、大O表示法——怎么算？

大O表示法，说白了就是忽略常数和低阶项，只关注增长最快的部分。为什么？因为数据规模足够大时，常数和低阶项的影响可以忽略不计。

比如一个算法执行了 3n² + 5n + 10 步，大O表示法就是 O(n²)。因为 n 很大时，3n² 占绝对主导，5n 和 10 根本不值一提。

计算大O的步骤：

找出基本操作（循环体、递归调用等）
计算基本操作的执行次数
保留最高阶项，去掉常数系数

举个例子：

// 双重循环，基本操作是 arr[i][j] 的访问
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%d ", arr[i][j]);  // 执行 n * n = n² 次
    }
}
// 时间复杂度：O(n²)

小技巧：我习惯先看循环嵌套层数。一层循环大概率O(n)，两层大概率O(n²)，三层大概率O(n³)。当然，递归和分治算法要单独分析，比如二分查找是O(log n)，归并排序是O(n log n)。

四、常见复杂度对比

不同复杂度的算法，性能差距有多大？我直接给你看数据：

大O表示法	名称	n=10	n=100	n=1000	n=10000
O(1)	常数时间	1	1	1	1
O(log n)	对数时间	3	7	10	14
O(n)	线性时间	10	100	1000	10000
O(n log n)	线性对数时间	30	700	10000	140000
O(n²)	平方时间	100	10000	1000000	100000000
O(2ⁿ)	指数时间	1024	巨大	巨大	巨大

看到没？n=10000时，O(n²)需要1亿步，而O(n log n)只需要14万步。差距是700多倍。这就是为什么我总说，选对算法比优化代码细节重要得多。

常见算法的复杂度：

O(1)：数组随机访问、哈希表查找
O(log n)：二分查找、平衡二叉树查找
O(n)：线性查找、数组遍历
O(n log n)：快速排序、归并排序、堆排序
O(n²)：冒泡排序、选择排序、插入排序
O(2ⁿ)：递归斐波那契、旅行商问题暴力解

我的经验：实际开发中，O(n²)以上的算法基本要避免。嵌入式环境尤其如此。如果实在避不开，一定要限制数据规模。我曾经在一个数据采集项目里，用O(n²)的算法处理1000个点，结果MCU直接死机。后来改成O(n log n)的算法，问题解决。

五、知识体系总览

下面这张图，把本章的核心内容串起来了。我建议你多看几遍，建立整体认知。

这张图把数据结构的两大分支和算法复杂度的核心内容都串起来了。你仔细看看，逻辑结构决定你怎么组织数据，存储结构决定你怎么实现，而复杂度分析帮你判断算法好不好。

好了，这一章的内容就到这里。数据结构不是背出来的，是用出来的。我建议你每学一个数据结构，都亲手写代码实现一遍，然后分析它的复杂度。这样印象才深。

📚 课程目录

一、数据结构到底是什么？

1.1 数据结构的分类

二、算法复杂度分析——到底快不快？

2.1 时间复杂度

2.2 空间复杂度

三、大O表示法——怎么算？

四、常见复杂度对比

五、知识体系总览