数据结构day1基本概念这堂课我前后看了两遍。第一遍觉得都是名词解释数据、数据元素、数据项、逻辑结构、物理结构看一眼就觉得自己会了第二遍才发现第一天其实把整个学科的骨架全摆出来了后面学的栈、队列、树、图全是往这个骨架上填肉。这篇文章就把我对第一天内容的拆解和补充整理出来给刚开始接触数据结构的朋友做个参考也聊聊哪些地方值得多琢磨。1. 数据、数据元素、数据项把第一节课的“名词三件套”理顺第一节课一定会先铺一批定义。数据、数据元素、数据项、数据对象这四个词看起来差不多实际说的是不同粒度的东西。很多初学者在这里就开始犯迷糊觉得“反正都是数据纠结这么细干嘛”。但如果不把这个粒度关系搞清楚后面学线性表、树、图的时候会遇到一个很实际的问题你到底在操作哪个层面的东西1.1 从一张学生表看数据的三级粒度说个最直观的例子。一张学生信息表里面有学号、姓名、性别、年龄、专业好几列。整张表的所有内容——包括每一行的值——合起来叫“数据”。这是最宽泛的说法指能被计算机识别、存储和处理的符号总称。那“数据元素”是什么呢是表中的一行记录也就是一个学生的完整信息。数据元素是数据的基本单位在程序中通常作为一个整体被处理。比如我要查找某个学生我查的是这“一行”而不是单独某个学号。这里有个容易混淆的点在树和图的结构里数据元素也叫“结点”在链式存储里叫“节点”在文件里叫“记录”不同教材叫法略有差异但本质都是“一个完整的基本单位”。再往下拆“数据项”就是表中的一列比如“学号”这一列。它是数据的不可分割的最小单位但注意这个“不可分割”是相对的。比如“姓名”数据项在有的场景里还要继续拆成“姓”和“名”那它就不再是原子单位了。所以数据项的定义要结合实际问题来看不是死板的。1.2 数据对象与数据集合的关系数据对象是性质相同的数据元素的集合它是数据的子集。继续用学生表举例整张表是数据而表里所有“学生”这一类型的元素集合就是数据对象。如果这张表里还混着教师记录、课程记录那每个类型各自构成一个数据对象。我最初学这块时有个疑问数据对象和“数据的集合”有什么区别后来明白关键在“性质相同”四个字。性质相同意味着这些数据元素共享一样的结构定义和操作方式可以统一处理。这直接为后面抽象数据类型ADT做了铺垫——你先能识别出“同一类元素”才能为它们定义统一的操作。1.3 为什么第一天就要分清这些东西说个实战中容易遇到的场景。你写一个链表里面存的结点结构是struct Student { char id[10]; char name[20]; int age; };这里的struct Student对应数据元素id、name、age就是数据项。你写插入、删除函数时操作的单位是struct Student这个完整元素而不是单独修改age。如果一开始没有“数据元素是基本单位”这个意识很容易在设计函数接口时把数据项当成操作单位后面对话就乱了。第一天把这些词掰扯清楚不是为了考试填空而是为了建立“数据是有粒度层次”的视角。有了这个视角你看到任何实际问题第一反应会变成这里的“数据元素”是什么“数据项”有哪些它们之间什么关系这个习惯比背下任何定义都值钱。2. 逻辑结构的四类关系集合、线性、树形、图形分别解决什么问题逻辑结构是数据元素之间逻辑关系的描述。注意“逻辑”两个字它跟数据在电脑里怎么存无关纯粹讨论元素与元素之间存在什么样的关系。第一天会讲四类逻辑结构集合、线性、树形、图形。这四种分类不是随便来的每一种都对应现实中一类典型问题。2.1 集合结构元素之间“同属一个集合”就够了集合结构的特点是元素之间除了“属于同一个集合”之外没有其他关系。这是四类结构里最松散的一种。这个结构在现实中对应的场景很多。比如一个班里所有学生的名单元素之间不需要排序不需要分层不需要连线它们就只是“都属于这个班”。再比如一个购物车里的商品列表商品之间本身没有先后关系、没有父子关系它们只是因为“都被选中了”才聚在一起。在计算机里集合结构通常通过哈希表来实现因为哈希表天然不关心元素顺序。但第一天讲集合结构不是为了让你马上写哈希表而是让你知道有些数据关系就是平的不要强行给它们发明顺序或层级。2.2 线性结构一对一排队的世界线性结构的特点是元素之间是一对一的关系除了第一个元素和最后一个元素每个元素都有唯一的前驱和唯一的后继。你可以把它理解成排队第一个人后面跟着第二个人第二个人后面跟着第三个人每个人都有前一个和后一个除了队首和队尾。线性结构最典型的实现就是数组和链表后面学的栈和队列也是线性结构的特殊形态。为什么单独把线性结构拎出来因为它覆盖了太多日常场景通讯录是按顺序排列的播放列表是按顺序播放的操作系统的任务队列是按先后执行的。第一天讲线性结构时重点不是代码而是先构建“序列”的概念。一旦你建立了“元素之间存在先后次序”的认知后面学链表的前驱指针、后继指针学队列的先进先出学栈的后进先出都会顺很多。2.3 树形结构一对多金字塔的世界树形结构的特点是元素之间存在一对多的层级关系。一个结点可以有一个或多个子结点但除了根结点之外每个结点有且只有一个父结点。它像公司组织架构一个总经理下面是几个部门总监每个总监下面又有几个主管层层往下。树的出现是为了解决“层级关系”的表达问题。文件系统就是典型的树一个根目录下分几个子目录子目录下还有文件或更深的目录。XML和JSON的嵌套结构也是树。第一堂课讲树形结构不会深入二叉树的性质它更像拉一条主线从今天开始你会遇到一种不再是“排成一队”的结构元素之间存在父子、上下级的层次关系。2.4 图形结构多对多网络的世界图形结构最自由元素之间是多对多的关系任意两个元素之间都可能有关联。它对应的是现实中的网络关系社交网络里任何人之间都可能成为好友地铁线路里各个站点之间有多条连接路径互联网里的路由器之间通过复杂的链路相连。图形结构是四种结构里最复杂的但它描述真实世界最准确。第一天提到图形结构重点在于让你意识到有的问题用线性和树形都表达不了必须上升到多对多。比如导航软件找最短路径你不可能用一棵树来表达路网因为两个路口之间可能有多条路互通。四种逻辑结构从集合到线性到树形到图形其实是一个从“松散”到“紧密”的递进关系越来越多结构越来越复杂能表达的问题也越来越丰富。第一天能把这个谱系建立起来后续不管学哪一块都知道自己学的东西在这个谱系里处于什么位置。3. 物理结构两大流派顺序存储与链式存储怎么选逻辑结构讲的是“元素之间是什么关系”物理结构讲的是“这些元素在内存里到底怎么放”。第一天会介绍两种物理结构顺序存储和链式存储。这个知识点后面会反复用到因为几乎所有数据结构都有顺序实现和链式实现两个版本第一天把这个底层逻辑吃透后面就是在不同的结构里套用同一套思路。3.1 顺序存储像电影院的固定座位顺序存储的核心思想是用一段连续的内存空间按元素的逻辑顺序依次存放。它相当于电影院里的固定座位座位从第1排第1号开始一个挨一个排列你不需要问座号在哪只要知道起始位置和排号规则就能直接算出任意座号的位置。在程序里顺序存储最常见的形态就是数组。比如用数组存5个整数int arr[5] {10, 20, 30, 40, 50};这5个数在内存里是连续排布的。如果要读取arr[3]系统只需要用起始地址加上3 * sizeof(int)就能算出来不需要遍历前面的元素。这种“直接算出位置”的能力让顺序存储在读取上非常有优势。但顺序存储有它的代价。在固定的连续空间里插入一个元素就要把插入位置后面的所有元素都往后挪一步删除一个元素就要把后面的元素往前挪。如果频繁在中间位置插入删除代价就会很大。3.2 链式存储像朋友之间互相介绍找到谁都能串起来链式存储的核心思想是元素在内存里各放各的不需要连续每个元素额外存一个指针指向它的后继元素。这就像你通过朋友介绍认识人你不需要知道所有人的住址只要认识一个朋友请他介绍下一个再下一个就能把一整串人串起来。在程序里链式存储最常见的形态就是链表。每个结点除了存数据还存一个指向下一个结点的指针。读取第3个元素你必须从第1个开始顺着指针走到第3个这个操作叫“遍历”。所以链式存储在随机访问上比顺序存储慢。但链式存储在插入删除上优势明显。只要找到位置改一下指针指向就能完成插入和删除不需要移动其他元素。这正好像认识了一个新朋友只需要让前面的朋友把介绍指向新朋友就行不需要让所有人都重新排一遍座位。3.3 选择的依据读多还是改多顺序存储和链式存储没有绝对的好坏选择取决于实际问题中“读”和“改”哪个更频繁。对比维度顺序存储链式存储内存布局连续非连续随机访问快直接计算地址慢需要遍历插入删除慢需要移动元素快只需修改指针空间利用率高无额外指针开销低每个结点有指针开销适用场景读多改少、元素个数固定频繁插入删除、长度不确定拿通讯录举例如果只是按顺序查看联系人顺序存储合适如果经常要往中间插入新联系人链式存储更灵活。第一天看到这个对比建议不只是记结论而是亲手写两段小程序感受一下。写一个用数组插入元素需要移动多少步再写一个链表插入只需要改一次指针体感非常直接。4. ADT抽象数据类型为什么讲数据突然扯到“操作”数据结构第一天的内容前面刚讲完数据的定义和分类紧接着就引入了抽象数据类型ADTAbstract Data Type。很多初学会觉得突兀明明在讲“数据”怎么突然又冒出一个“操作”的概念这其实是第一天里最该停下来细想的地方。4.1 ADT的三元组数据对象、数据关系、基本操作ADT的定义是一个三元组数据对象、数据关系、基本操作。数据对象和数据关系就是前文讲的逻辑结构层面的事关键是多了“基本操作”。还是拿复数举例。定义复数这个ADT你要说清楚三个东西数据对象一个复数由实部和虚部组成即一对实数a, b。数据关系实部和虚部配合构成一个整体没有更复杂的内部结构。基本操作创建复数、求实部、求虚部、复数加法、复数乘法等。这里有个关键点ADT只约定了“有哪些操作以及操作的结果是什么”完全不关心内部用数组还是结构体实现、不关心实部虚部在内存里怎么放、不关心加法是用一行代码还是十行代码算出来的。使用的人只需要知道“调用复数加法能算出正确结果”这就够了。4.2 把“使用”和“实现”分开是工程思维的第一课为什么ADT这个纯理论概念如此重要因为它背后是“抽象”和“封装”的思想这是程序设计的基本方法论。设想一下你用复数做科学计算你关心的是能创建复数、能相加、能取实部虚部不关心它内部怎么表示。这时候开发人员A用结构体实现了这个ADT开发人员B用两个浮点数数组实现了同一个ADT。对调用者来说代码是完全一样的因为接口没变。这就是ADT的价值使用和实现解耦。往后学的栈、队列都是ADT的经典例子。栈这个ADT定义了入栈、出栈、判空等操作至于是用数组实现还是用链表实现那是实现层面的选择。第一天建立了“先定操作再选实现”的意识后面学每种结构时你就会自然分成两步走先看这个结构对外提供什么操作再想用什么物理结构来实现。4.3 面向对象编程里的ADT类和接口的呼应如果你学过面向对象编程ADT和类的关系其实很自然。类就是把数据成员和成员函数打包在一起成员函数就是对数据对象的操作。接口则更接近ADT的概念——只约定方法签名和行为不暴露实现细节。我当时学到ADT老师给了一道很经典的题目定义一个矩阵的ADT包括创建、转置、相加、相乘操作。写完定义后发现这个ADT设计好了后面用数组实现还是用三元组实现稀疏矩阵调用代码都不需要改。这种“先设计契约再写实现”的思维在第一天建立起来后面写任何模块都会受益。第一天学ADT不要只记住“数据对象数据关系基本操作”这个三元组要理解它为什么把“操作”纳入定义。因为数据结构从来不只是“怎么存”而是“存起来之后要支持哪些操作”操作决定了对物理结构的要求。5. 算法复杂度分析大O到底在算什么怎么算第一天的内容里最有硬核感的部分就是算法和复杂度分析。前面讲的是“数据怎么组织”这部分开始讲“在组织好的数据上算法好不好”。评判算法好坏的两个核心指标是时间复杂度和空间复杂度而大O表示法是描述复杂度的标准方式。5.1 算法的特性与好算法的标准先过一下算法的定义。算法是对特定问题求解步骤的描述它有五个特性有穷性必须在有限步骤内结束、确定性每条指令含义明确无歧义、可行性每条指令都能在有限时间内完成、输入有零个或多个输入、输出至少有一个输出。定义不难难的是“什么叫好算法”。四个字正确、可读、健壮、高效。正确性不用说可读性要求代码能让别人看懂健壮性要求能处理非法输入而不崩溃。高效性就是复杂度分析要解决的问题在同样解决问题的情况下时间消耗和空间消耗尽量小。这里有个很常见的现实问题正确性和可读性都没问题但算法跑得慢用户等得受不了。处理百万级数据时一个O(n²)的算法和一个O(n log n)的算法运行时间可能差几百倍。第一天一定要建立起“算法之间效率差异巨大”的直觉而不是等写出慢代码才后悔。5.2 大O表示法关心的是增长趋势不是精确时间大O表示法用来描述算法执行时间随输入规模增长的渐进趋势。它不关心具体的执行秒数因为同样的代码在不同机器上运行时间本来就不同大O描述的是“当输入规模n变大时时间大概按什么速度增长”。计算规则主要有几条常数项忽略不计。运行时间如果是3n 100大O记为O(n)。低阶项忽略不计。运行时间如果是n² n大O记为O(n²)。系数忽略不计。运行时间如果是5n²大O记为O(n²)。加法规则取较大项。一个代码块执行时间是O(n)另一个是O(n²)整体取O(n²)。乘法规则适用于嵌套循环。外层循环n次内层循环n次总次数是O(n²)。这五条规则的直觉理解是当n足够大时决定算法命运的是增长最快的那个因子其他都是小头。就像你观察一辆车的油耗跑一百公里和一千里差距主要来自百公里油耗这个指标启动那一脚油门的消耗可以忽略。5.3 几个典型复杂度的直观感受第一天最常遇到的复杂度有这么几个最好形成数量级直觉O(1)常数时间。无论n多大操作时间不变。比如数组按下标取元素。O(log n)对数时间。n翻一倍时间只增加一个常数。二分查找是经典例子。O(n)线性时间。n翻倍时间翻倍。顺序查找是典型例子。O(n log n)出现在快速排序、归并排序这类高效排序里。O(n²)平方时间。n翻倍时间变成4倍。简单冒泡排序是这个级别。O(2ⁿ)指数时间。n增加一点时间爆炸式增长。当n1000千级数据时O(n)跑起来大约微秒到毫秒级O(n²)开始有可感知的延迟O(2ⁿ)基本没法跑。第一天不需要做复杂推导给自己标注几个锚点就行n取10、100、1000时这个复杂度的运算次数是多少感受一下差距。5.4 实际算一下从一个双重循环开始直接看一个最简单的例子int sum 0; for (int i 0; i n; i) { for (int j 0; j n; j) { sum i * j; } }内层循环每执行一次是O(1)的操作内层总共执行n次外层执行n次所以总次数约n²时间复杂度O(n²)。如果把内层条件改成j i实际执行次数变成0 1 2 ... (n-1) n(n-1)/2仍然是O(n²)因为常数系数和低阶项都不影响最终增长趋势。再看一个递归的例子斐波那契数列的朴素递归实现f(n) f(n-1) f(n-2)。每次调用分裂成两个子调用调用树接近满二叉树时间复杂度O(2ⁿ)。这就是为什么朴素递归算斐波那契到n50就已经慢得离谱而用数组迭代只需O(n)。第一天能看到这个对比就会对复杂度产生本能的重视。空间复杂度同理看的是算法额外占用的内存随输入规模的增长趋势。迭代求斐波那契只需要几个变量空间O(1)递归求斐波那契的调用栈深度是n空间O(n)。以后学递归、学动态规划这个概念会反复被用到。6. 第一天的常见误区与后续学习建议学习的第一天有一个时间窗口它决定了你后面是越学越顺还是越学越吃力。这里集中说几个常见误区以及我自己的应对方法。6.1 不要陷入名词的抠字眼数据、数据元素、数据项、数据对象、逻辑结构、物理结构、ADT、算法、复杂度第一天抛出来的术语密度很高。有些同学喜欢对着教材逐字推敲试图给每个词一个绝对精确的定义。实际上这些术语在工程里并不总是一板一眼的数据元素叫结点、节点、记录都很常见。我自己的做法是每个概念先能用自己的话讲出来然后马上去代码里找对应物。数据元素对应结构体变量数据项对应结构体的成员逻辑结构对应对象之间的关系物理结构对应内存里的布局。概念落地到代码比死记定义有效得多。6.2 多画图少空想数据结构这门课画图是最被低估的练习方式。逻辑结构四类关系手动画一遍集合、线性、树形、图形比看十遍文字都直观。物理结构里的顺序和链式把数组的下标和链表的指针各画一张图位置关系一目了然。打个比方学数据结构有点像学地图脑子里不装下几幅结构图遇到坑就不知道往哪走。每天学完新东西花几分钟在纸上画一遍这会成为你后面最省力的复习资料。6.3 后续的学习路线参考第一天只是起点。按一般课程的推进节奏接下来会依次接触线性表、栈与队列、串、树与二叉树、图然后是查找和排序。学线性表时你会发现第一天讲的顺序存储和链式存储直接拿来用学栈和队列时你会看到同一个ADT用数组和链表两种实现方式学树和图时逻辑结构的分类会支撑你对结构的理解。一条比较稳的路线是每学一个新结构都按“逻辑结构定义、ADT操作、物理结构实现、复杂度分析、典型应用”这个框架去套。这样框架可以复用学的东西不会散。第一天内容量不大但它是整个学科认知路线的起点。把基本概念当成地图去理解后面学什么都能找到自己的位置。我第二次看第一堂课时才真正把这些名词串起来。如果你正在学数据结构不妨把这篇当作一份预习笔记或复习提纲把概念一个不漏地过一遍再配上几段小代码验证后续的学习会顺利很多。