数据结构第一章怎么学？逻辑结构、存储结构、ADT与时间复杂度全拆解

很多人翻开王道数据结构第一章绪论，第一反应是：这都是什么？全是概念，看不见代码，听得云里雾里。有的同学甚至直接跳过，想着后面做题再回来补。我的建议是：绪论不仅不能跳，还得用“做题”的方式学——只不过这里的题不是写代码，是判断和计算。这篇内容我会从逻辑结构、存储结构、ADT、时间复杂度四个核心板块拆开，配合典型例子和容易踩的坑，把第一章真正变成后面所有章节的地基。

1. 为什么第一章全是概念，却决定你后面能不能读懂代码

1.1 数据、数据元素、数据项：这三层别混

第一章开篇就会给出一连串定义：数据、数据元素、数据项、数据对象、数据结构。很多同学背完就忘，因为不知道背来干嘛。我换个说法：

• 数据就是信息的载体，比如一串数字、一份学生名单。
• 数据元素是数据的基本单位，通常被当做一个整体处理。比如名单里的一个学生。
• 数据项是构成数据元素的不可分割的最小单位，比如一个学生的学号、姓名。

举个例子，教务处维护全年级学生信息。整个年级的花名册是“数据”，其中某个学生“张三”是“数据元素”，而张三的学号“20270001”、姓名“张三”、专业“计算机”这些字段是“数据项”。如果你只关心“张三”这个一人整体，那他就是数据元素；如果你要处理“张三的学号”，那学号就是数据项。

为什么这个区分重要？因为后面学的线性表、树、图，操作对象都是数据元素，而不是数据项。比如单链表删除一个节点，删除的是整个“学生”节点，而不是只删除他的姓名。你在写代码时，结构体对应数据元素，结构体里的成员对应数据项。这个对应关系搞清楚了，之后写代码不会糊涂。

1.2 数据结构定义的三角关系：逻辑结构、存储结构、运算

教材里“数据结构”的定义一般包含三个方面：逻辑结构、存储结构（物理结构）、数据的运算。这三者不是三个独立的知识点，而是一个完整对象的三个侧面。

逻辑结构回答“数据元素之间是什么关系”，比如一对一、一对多、多对多；存储结构回答“这些关系在计算机里怎么放”，是用连续内存还是用指针串起来；数据的运算回答“我能对这个结构做什么”，比如插入、删除、查找、排序。

你要清楚一点：同一个逻辑结构，可以有不同的存储结构；同一种存储结构，也可以支撑不同的逻辑结构。后面学线性表时，你会看到顺序表和链表两种实现，它们逻辑上都是“线性结构”，但物理上一个用数组存，一个用节点指针串。因为实现方式不同，插入删除的时间复杂度也不同。第一章的这层理解，直接决定你后面学栈、队列、串、树、图时，能不能把“逻辑”和“实现”分开想。

2. 逻辑结构只有四种：集合、线性、树、图，怎么一眼分清楚

2.1 看“关系”而不是看“长得像什么”

逻辑结构按数据元素之间的关系分四类，这是单选题的高频考点。

• 集合结构：元素之间除了“属于同一个集合”之外，没有任何其他关系。就像一堆散装零件倒进一个筐，筐里的每个零件彼此独立。
• 线性结构：元素之间是一对一的线性关系，除了第一个没有前驱、最后一个没有后继之外，每个元素都有一个前驱和一个后继。典型代表：线性表、栈、队列、串。
• 树形结构：元素之间是一对多的层次关系，每个元素最多有一个直接前驱（双亲），但可以有多个直接后继（孩子）。典型代表：树、二叉树、堆。
• 图形结构：元素之间是多对多的任意关系，每个元素可以有多个前驱和多个后继。典型代表：图、网。

判断方法很简单：先问元素之间有没有关系；如果没有，就是集合。如果有，看是一对一还是还是一对多还是多对多。这里很容易出迷惑项，比如“数组是不是线性结构”？数组的元素按逻辑顺序排列，每个元素有唯一前驱和唯一后继（除了边界），所以是线性结构。但注意，数组也可以用来存储树和图的结构，这是“存储结构”层面的问题，别和逻辑结构混在一起。

2.2 逻辑结构是用户视角，存储结构是实现视角

我见过很多人纠结一个问题：栈到底是用数组还是链表实现？答案是都可以。因为栈的逻辑特征是“后进先出”（LIFO），这是一个规则约定，不是物理要求。数组实现的栈叫顺序栈，链表实现的栈叫链栈，两者在逻辑上都是栈。

这个抽象思想特别重要。你写程序的时候，业务逻辑关心的是“先放进去的后拿出来”，不关心底下一块内存怎么排布。而计算机实现时，必须选择一种物理方式把这种规则落地。所以，逻辑结构是“用户看到的”，存储结构是“机器里实际存在的”。考试中常见的一种错误选项是“树形结构一定用链式存储”，这是错的，树完全可以用数组存，比如堆就是用数组存完全二叉树。

2.3 三种存储结构，其实是从“怎么访问下一个元素”来区分的

教材里通常把存储结构分四类：顺序存储、链式存储、索引存储、散列存储。前两个是重点，后两个理解即可。

• 顺序存储：逻辑上相邻的元素存储在物理位置上也相邻的内存单元里。典型就是数组。访问任意元素的时间都是O(1)（随机访问），但插入删除往往需要移动大量元素。
• 链式存储：逻辑上相邻的元素在物理位置上不一定相邻，每个节点除了存数据，还存指向下一个节点的指针。典型就是链表。插入删除只需要改指针，但访问某个节点必须从头遍历，不支持随机访问。
• 索引存储：在存储元素信息的同时，额外建立一张索引表，索引项指向数据元素存储位置。就像书的目录，查目录能快速定位章节，但目录本身要占额外空间。
• 散列存储：根据元素的关键字通过散列函数直接计算出存储地址。典型就是哈希表，查找速度理论上可以达到O(1)，但可能出现冲突。

把这四种存储结构列成一张对照表会很直观：

这一章的选择题，很多就是在“逻辑结构与存储结构对应关系”上做文章。你做判断时，先分清题目问的是“逻辑关系”还是“物理存储方式”，再去匹配，错误率能降一半。

3. ADT到底抽象了什么？为什么教科书非要绕这么一大圈

3.1 ADT的三元组：数据对象、关系集合、操作集合

抽象数据类型（Abstract Data Type，ADT）是第一章里看起来最“虚”的概念，但恰恰是它最能体现数据结构这门课的思想。ADT通常用一个三元组来表示：

ADT = （D，S，P）

其中D是数据对象，S是D上的关系集合，P是对D的基本操作集合。

用人话说，ADT就是“定义一套数据类型，规定它能装什么数据、数据之间有什么关系、以及能对它做什么操作”，但不规定这些操作内部怎么实现。比如“栈”是一个ADT：数据对象是任意类型元素；关系是线性、且只能从栈顶进出；操作有入栈（push）、出栈（pop）、取栈顶（getTop）、判空（isEmpty）等。

至于栈内部是用数组还是链表，ADT不管。这就是“抽象”的含义：把使用者和实现者分开，使用者只依赖操作接口，不依赖内部细节。

3.2 为什么说ADT的观点是编程的基本功

你可能觉得ADT只是考试名词，其实它对应到工程里就是面向对象里的“接口”思想。比如你做登录模块，调用方只需要知道login(username, password)这个函数签名，不需要知道内部是查数据库还是调第三方服务。这就是把“做什么”和“怎么做”分离。

学第一章时，很多同学对ADT题目的常见困惑是“这个操作算不算基本操作”。我的判断标准是：这个操作是否直接基于数据对象的逻辑关系，能否被用户直接调用。给线性表增加一个“按位查找”操作，这是ADT的一部分；而“对线性表元素排序”如果不在ADT定义里，就可能属于算法而不是基本操作。考试里遇到“以下哪个不属于栈的基本操作”，你按“栈顶操作”这条约束去排除就行。

4. 时间复杂度：第一章里最能拉开差距的内容

4.1 大O记号在描述什么

算法效率度量有两种：时间复杂度和空间复杂度。考研里时间复杂度几乎是必考，而且不是背诵题，是计算题。

大O记号描述的是：当问题规模n趋向无穷大时，算法执行时间（或所需存储空间）的增长趋势，不考虑低阶项和常数系数。也就是说，n足够大的时候，O(2n)和O(n)实际上是一回事，因为常数2不影响增长率；O(n²+n)和O(n²)也是一回事，因为n相对于n²可以忽略。

常见复杂度从低到高排序：

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

这个排序要背熟。选择题经常给几个复杂度让你比大小，或者让你判断某段程序的复杂度属于哪一档。

4.2 怎么数基本语句的执行次数

算时间复杂度，关键不是逐行加次数，而是找到“基本操作”，也就是最深层循环里的那条语句，看它随n变化执行多少次。我直接给三类典型情况。

第一类，单层循环：

for (int i = 0; i < n; i++) { x++; }

基本操作x++执行n次，复杂度O(n)。

第二类，双层循环：

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { x++; } }

外层跑n次，内层每轮跑n次，总次数n²，复杂度O(n²)。

第三类，循环变量倍增：

for (int i = 1; i < n; i *= 2) { x++; }

i的取值是1、2、4、8……直到超过n。设循环次数为k，则2^(k-1) < n，所以k ≈ log₂n，复杂度O(log₂n)。

注意，如果题目里的底数是2还是10，在大O里没有区别，因为log₂n = log₁₀n / log₁₀2，只差个常数，常数忽略。所以答案统一写O(log n)就行。

4.3 递归的时间复杂度先找递推式

递归复杂度比循环难一层。最简单的方式是把递归调用次数画成一个树形结构，每层有多少次递归，每层深度多少。

比如求斐波那契数列的朴素递归：

int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

每调用一次fib(n)，会分裂成两个规模约为n-1和n-2的子问题，递归树近似是一棵满二叉树，节点数约为2ⁿ量级，所以朴素写法是O(2ⁿ)。这也解释了为什么工程上不会用朴素递归算斐波那契——指数级复杂度根本跑不动。

而如果只是递归深度为k，每次递归只调用一次自己，比如二分查找，那复杂度就是O(k)，k = log₂n，所以是O(log n)。判断递归复杂度时，第一问“递归调用了几次自己”，第二问“递归深度是多少”，比硬记公式靠谱。

4.4 空间复杂度别忘了看递归栈

很多同学只盯时间复杂度，忽略空间复杂度，其实第一章也考。空间复杂度指算法运行过程中额外占用的存储空间（输入数据本身的空间不算）。

最典型的是递归：每次递归调用都要占用栈帧，递归深度是k，空间复杂度就是O(k)。比如上面那个朴素斐波那契，时间O(2ⁿ)，但递归深度最多n，空间是O(n)，不是O(2ⁿ)。很多题就在这里挖坑。

5. 拿几道“模拟题”练手：判断和计算其实是同一件事

5.1 逻辑结构判断型

题目：在数据结构中，从逻辑上可以把数据结构分成哪两类？

你肯定见过这题。答案应该是“线性结构和非线性结构”而不是“顺序结构和链式结构”。前者是逻辑视角，后者是存储视角。这种题考察的就是你是否把两个视角分清楚。如果题目问“从存储结构的角度”，答案才是“顺序结构和链式结构”。

再比如，“一个数据元素可以有多个直接前驱”，这种元素一定处于什么结构中？答案是图形结构，因为只有图允许一个元素有多个前驱、多个后继。树虽然可以有多后继，但前驱只有一个。这个“前驱/后继数量”的判断方法，做逻辑结构选择题非常管用。

5.2 时间复杂度计算型

题目：执行下面程序，求时间复杂度。

int i = 1; while (i <= n) { i = i * 3; }

i的取值是1、3、9、27……每次乘3。设执行次数为t，则3^t > n时退出，所以t ≈ log₃n，忽略底数，复杂度O(log n)。

再看一个迷惑性更强的：

for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { x++; } }

内层循环次数是1+2+3+...+n = n(n+1)/2，所以是O(n²)。不是O(n³)，因为内层不是每次跑到n，而是跑到i。

有些同学会把“看到两层循环就直接写O(n²)”，这在一半情况下是对的，但遇到上面这种内层随外层变化的题就会翻车。正确做法是老老实实把执行次数写成一个求和式，再化简。

5.3 概念辨析型

题目：以下说法正确的是？

A. 数据元素是数据的最小单位
B. 数据项是数据的基本单位
C. 数据结构是带有结构的数据元素的集合
D. 数据对象可以是任意类型的数据

正确选项是C。A错在“最小单位”，最小单位是数据项；B错在“基本单位”，基本单位是数据元素；D错在“任意类型”，数据对象是具有相同性质的数据元素的集合。这种题没有技巧，就是概念必须抠字眼。我当时的办法是：把“数据元素是基本单位、数据项是不可分割的最小单位”抄在笔记本第一页，每次做题前扫一遍。

6. 第一章作为考研复习起点，时间和精力怎么分配

6.1 这一章值得花多久

如果你在准备2027考研，现在开始看数据结构，第一章建议控制在3到5天。一天看概念和逻辑结构，一天看存储结构和ADT，两天练时间复杂度。千万不要因为它是“绪论”就快进，也不要因为内容少就死磕一个月。

为什么说时间要控制？因为数据结构真正的重头戏在线性表、树、图、排序和查找，第一章只是预备知识。但预备知识不牢固，后面学树的遍历时，你会分不清“递归深度”和“节点个数”谁决定复杂度；学图的时候，你会搞不清邻接矩阵和邻接表到底属于存储结构还是逻辑结构。这些混淆全都能在绪论找到根源。

6.2 笔记应该记什么

第一，记下每个概念的“一句话定义”和“典型例子”。不要抄教材原话，用自己的话压缩成一行，后面复习时扫一眼就能想起来。

第二，把“逻辑结构—存储结构—操作”这张关系图画一遍。注意，我这里说的是“关系图”，不是教材里的结构图。左边写四种逻辑结构，右边写四种存储结构，中间用箭头标出“可以搭配使用”，比如线性结构可以用顺序存储和链式存储，树形结构可以用顺序存储也可以用链式存储。

第三，把所有复杂度从低到高抄下来，并在旁边写一个能生成该复杂度的代码片段。以后做复杂度题时，先对照这个清单缩小范围。

第四，错题本上记录那些“看起来对，其实是偷换概念”的选项。第一章的题不难，但陷阱非常固定，无非是“最小单位变基本单位”“存储结构变逻辑结构”“常数项当成复杂度一部分”。把这些陷阱集中记下来，比盲目刷题有效得多。

6.3 怎么把第一章和后面的章节串联起来

学完绪论后，每学一个后继章节，你都可以回头做一次“归档”：

• 这个结构属于哪类逻辑结构？
• 教材里用它时选择了哪种存储结构？
• 为什么选择这种存储结构？时间复杂度是什么？

比如学二叉树的时候，问自己：二叉树属于树形结构（一对多）；可以用顺序存储（数组）实现完全二叉树，也可以用链式存储（二叉链表）实现；普通二叉树如果缺节点多，用顺序存储浪费空间，所以一般用链式存储。这一连串问题，就是绪论知识在具体场景里的应用。

我个人的做法是，每学完一章，就拿张白纸，把这一章的数据结构的“逻辑结构—存储结构—核心操作复杂度”画成一个表格。到复习后期，整个学科被压缩成几张表，考前翻起来特别顺手。你会发现，绪论里那些当时觉得抽象的定义，最后都变成了表格的表头和分类依据，没有一步是白学的。

如果第一章现在让你觉得迷茫，不用慌，这是正常的。数据结构本来就是一门“先见森林，再见树木”的课，很多概念要到后面章节才会真正落地。你只要把逻辑结构、存储结构、ADT、时间空间复杂度这四件事的基础打牢，后面每学一章都是对它们的重复深化。这套功夫下在开头，性价比远比你想象的高。