一、数据结构绪论：从概念到实战

各位同学好，我是你们这门课的老朋友。今天咱们聊聊数据结构这门课的“开场白”——绪论。别看它叫“绪论”，好像只是些概念，其实它决定了你后面所有代码的“骨架”该怎么搭。

我刚开始学数据结构时，也觉得这些概念太虚了。直到后来做项目，因为没搞清楚“逻辑结构”和“物理结构”的区别，写出来的代码跑起来慢得像蜗牛。嗯，从那以后，我再也不敢小看绪论了。

1.1 数据结构到底是什么？

说白了，数据结构就是“数据怎么组织、怎么存、怎么用”。你想想看，一堆数据散落一地，跟把它们整整齐齐放进抽屉里，效率能一样吗？

我个人习惯把数据结构理解成“数据的收纳术”。比如你写一个学生管理系统，学生信息怎么存？按学号排？按姓名排？还是按成绩排？不同的排法，后面查起来、改起来，速度天差地别。

1.2 逻辑结构与物理结构

这里有个坑，我当年踩过。逻辑结构和物理结构，是两个完全不同的概念，但很多人混为一谈。

逻辑结构：数据元素之间的“抽象关系”。比如你脑子里想的“这些学生按成绩从高到低排”，这就是逻辑结构。它不关心数据在内存里到底怎么放的。

物理结构：数据在计算机内存里“实际怎么存”。比如用数组连续存，还是用链表东一个西一个地存。

我曾经在一个项目中，设计了一个很漂亮的逻辑结构——树形组织架构。结果实现时选了数组存储，插入一个节点就要移动大量数据，性能惨不忍睹。后来改成链表存储，问题迎刃而解。

常见的逻辑结构有四种：

• 集合：数据之间“没关系”，就是一堆东西放一起。
• 线性结构：数据“一对一”排成一条线，比如数组、链表。
• 树形结构：数据“一对多”，比如文件夹目录、公司组织架构。
• 图形结构：数据“多对多”，比如社交网络、地图导航。

物理结构主要就两种：

• 顺序存储：用连续的内存空间，像数组那样。
• 链式存储：用不连续的内存，靠指针串起来，像链表那样。

1.3 抽象数据类型（ADT）

抽象数据类型，听起来很高大上。其实说白了就是：我只管你能干什么，不管你怎么干。

比如你定义一个“栈”的ADT，你只需要说：我能push、pop、查看栈顶。至于底层是用数组实现还是链表实现，那是实现细节，ADT不关心。

我习惯在写代码前，先用ADT把“要做什么”定义清楚。这样后面写代码时，思路特别清晰，不会写着写着就跑偏了。

一个典型的ADT定义包含三部分：

• 数据对象：你要操作的数据是什么。
• 数据关系：这些数据之间有什么关系。
• 基本操作：你能对这些数据做什么。

// 一个简单的栈ADT定义（C语言风格）
// 数据对象：一组元素，后进先出
// 基本操作：
//   initStack(): 初始化一个空栈
//   push(element): 将元素压入栈顶
//   pop(): 弹出栈顶元素
//   top(): 查看栈顶元素（不弹出）
//   isEmpty(): 判断栈是否为空

// 具体实现（用数组）：
#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

void push(Stack *s, int value) {
    if (s->top >= MAX_SIZE - 1) {
        printf("栈已满，无法压入\n");
        return;
    }
    s->data[++(s->top)] = value;
}

int pop(Stack *s) {
    if (s->top == -1) {
        printf("栈已空，无法弹出\n");
        return -1;
    }
    return s->data[(s->top)--];
}

1.4 算法与算法分析

算法，就是解决问题的步骤。但同样是解决问题，有的算法快如闪电，有的慢如蜗牛。怎么衡量？这就引出了算法分析。

我刚开始写代码时，觉得“能跑就行”。直到有一次，我写了一个排序算法，数据量一上去，程序直接卡死。后来一分析，时间复杂度是O(n²)，数据量大了当然扛不住。

时间复杂度：衡量算法运行时间随数据规模增长的趋势。常见的有：

符号	名称	例子
O(1)	常数时间	数组随机访问
O(log n)	对数时间	二分查找
O(n)	线性时间	遍历数组
O(n log n)	线性对数时间	快速排序
O(n²)	平方时间	冒泡排序

空间复杂度：衡量算法运行时占用的内存空间。有时候为了省时间，得多用点空间；为了省空间，得多花点时间。这就是经典的“时空权衡”。

知识体系总览

下面这张图，把本章的核心知识点串起来了。你可以把它当作整个数据结构的“地图”。

小结

这一章的内容，说白了就是给整个数据结构课程“打地基”。你可能会觉得概念有点多，但别急，后面每一章都会反复用到这些概念。

我个人建议你：先把逻辑结构和物理结构的区别刻在脑子里。写代码前，先想清楚“我要用什么逻辑结构”，再想“用什么物理结构实现”。这个习惯养成了，后面学链表、树、图都会轻松很多。

好了，这一章就到这里。记住：数据结构不是背出来的，是用出来的。下一章咱们就开始动手，从线性表开始，真正写代码了。

---