第一章：鸿蒙开道｜结构概论

你好呀，我是程序员白菜a（抖音同名），我将从零开始介绍《数据结构与算法》的内容，笔者CSP算法竞赛前1.78%，习惯以最快最通俗的方式去学习知识，下面的内容从武侠玄幻风格来对《数据结构与算法》这本书进行讲解，内容详细而且会进行解释，还有思维导图，跟着我准没错！

天地万象，皆有脉络可循；世间万千讯息，自有排布章法。

鸿蒙初辟，大道雏形初现，数据之道自此缘起。世人观百态、理纷繁，欲将零散信息收纳规整，推演运算玄机，便踏入这结构武学一途。

此路分八重境界，从初识大道法理起步，循序参悟线性根基、进退规制、字符玄奥、树形脉络、寰宇路网，习得寻踪觅迹、规整乾坤之术。步步苦修，勘破存储与运算真谛，终能驾驭数据万法，执掌程序江湖。

不必吹毛求疵，不必深究具体代码，先理解名词意思接触计算机世界的大道法则。新手入门最忌讳死记硬背，先懂逻辑、再懂原理，最后落地代码，这是最快的修行路径。

快速带你过一下名词防止你着急，看完=学会数据结构与算法！！

数组：就是Array[0]，你学习任何一门语言的入门标配，一片连续规整的内存空间，挨个有序存放数据，位置固定、有序可查。

链表：就是你射靶，链表结点都包含数据域和指针域，数据域和数组一样存放数据，指针域拿来指向下一个链表结点，就像你射箭射向一个指定的靶子一样，一环扣一环，无需连续空间，靠指针串联整体。

串（字符串）：就是一整句连贯的文字台词，本质是特殊的字符型数组，专门用来存储文字、符号字符。普通数组可以存数字、各类数据，而串是专一的字符集合，像我们日常输入的一句话、一段文本，单个字符依次排列、连贯有序，整体不可随意拆分乱序，是专为文字场景而生的线性结构。

栈：就是桶装薯片！遵循后进先出规则。最后放进去的薯片一定最先被拿出来，最先放进去的压在最底下，最后才能拿到。只允许在一端操作（入栈/出栈），另一端完全封死，是典型的受限线性表。

队列：就是超市排队结账！遵循先进先出规则。谁先排队谁先结账离开，后面来的人只能排队尾，绝对不能插队。一端入队、一端出队，秩序井然，也是受限线性表。

广义表：就是套娃礼盒！普通数组只能装单一数据，广义表可以表里套表，一层套一层，既能存普通数据，也能嵌套集合，是线性表的超级拓展形态。

集合结构：就是一个大收纳箱！箱子里的东西只是单纯凑在一起，只有归属关系，没有先后、层级关系。谁在前谁在后无所谓，元素之间互不关联。

树形结构：就是家族族谱！典型一对多关系。一个祖宗节点可以衍生多个子孙节点，层层分级、上下级清晰，从上往下发散，不会乱成一团。

图状结构：就是朋友圈社交网！典型多对多关系。你可以加很多好友，你的好友之间也可以互相加好友，人人互联、双向互通，关系最复杂、最自由。

顺序存储：就是电影院连座座位！位置是连续固定的，坐得整整齐齐。想找第几号座位直接直达，支持随机坐；但如果中间空了位置就浪费了，没法填补，容易空座碎片。

链式存储：就是寻宝解谜线索！每个宝藏（数据）自带一张小纸条（指针），写下下一个宝藏的位置。不用扎堆坐一起，散落存放也没关系，跟着线索挨个找就行，不浪费空间，但必须逐个顺着找，不能直接跳着找。

索引存储：就是书本目录！正文是真实数据，目录就是索引表。想看哪一章不用从头翻，直接看目录找页码，跳转超快；但目录需要单独占一页纸，书本更新内容了目录也要同步改。

散列存储（哈希）：就是快递取件码！根据你的手机号（Key）直接算出一个取件位置，不用挨个找，一步到位取快递。速度最快，但偶尔会出现两个人取件码一样（哈希冲突），需要额外处理。

数据项：就是单个五官！眼睛、鼻子、嘴巴，拆到最小、不能再细分，是数据最基础的最小颗粒。

数据元素：就是一整张人脸！由五官（多个数据项）拼凑而成，是一个完整的独立个体。

数据对象：就是全班所有人的脸！一堆相同类型的个体集合，统一归类、性质一致。

逻辑结构：就是脑子里的排队规则！我心里规定大家要排成一条直线，这个规则只存在思维里，不管你们是站在一起（顺序存储）还是分散站靠手势串联（链式存储），排队逻辑永远不变。

存储结构：就是现实里真实站队的样子！是规则落地的真实形态，是看得见、存在内存里的真实排布。

抽象数据类型ADT：就是完整的游戏职业模板！不仅定义这个职业有什么属性（数据对象）、属性之间的关系（数据关系），还定义能放什么技能（基本操作），一套完整体系，自成一派。

算法：就是菜谱！解决一道菜的固定步骤，步骤有限、每一步明确，照着做一定能做出成品，不瞎步骤、不无限循环。

时间复杂度：就是做题耗时等级！不精确算几分几秒，只看数据变多后，耗时增长的快慢级别，判断你的方法卡不卡、够不够快。

空间复杂度：就是做题打草稿用的白纸！不算题目本身的纸张，只算你额外临时用的草稿纸，草稿纸不随题目变多就是原地工作O(1)。

查找：就是翻书找知识点！在一堆数据里精准定位目标。

排序：就是整理书架！把杂乱的数据按照大小、先后规则，规整成有序状态。

栈：就是桶装薯片，后进先出。最后放进去的薯片一定最先被拿出来，最先放进去的压在最底部，

一、数据结构核心奥义：何为数据武学？

很多新手初学都会疑惑，数据结构到底学什么、用来干什么？

直白来说，数据结构是一门研究非数值计算程序设计中，计算机操作对象、数据之间关联关系以及对应操作方法的核心学科。

我们日常数学学习，大多是用公式、方程解决数值计算问题，比如加减乘除、函数运算。但在编程世界里，绝大多数问题都没法用数学公式概括——学生信息、社交关系、文件排布、任务排队，这些都是非数值计算问题。

这类零散数据，需要依靠表、树、图这类自带逻辑关系的模型规整，而这，就是数据结构存在的意义。简单说，就是给杂乱无章的数据，定规矩、排顺序、搭框架，让计算机能高效处理。

整套数据结构的修行体系，脉络十分清晰，全程围绕两大核心、两大技术展开：

1. 两大核心结构：线性结构（基础根基）、非线性结构（进阶神通）

2. 两大核心技术：查找技术（寻踪）、排序技术（规整）

二、筑基必备：数据基础核心名词

修行先识道，学数据结构先分清四个最基础的名词，由小到大、层层嵌套，一眼就能看懂区别。

1. 数据：信息的本源载体

所有能被计算机接收、处理的符号集合，都统称为数据。通俗讲，就是计算机的所有操作对象，比如学生信息表、文字、数字、符号，都是数据，是最宽泛的概念。

2. 数据元素：数据的基本单位

它是数据的独立个体，由多个数据项组成。比如学生表中，单独一个学生的全部个人记录，就是一个数据元素，是计算机处理数据的最小独立单元。

3. 数据项：不可拆分的最小单元

这是数据最细碎的组成部分，无法再拆分。学生记录里的姓名、学号、年龄，每一个单独的信息，就是一个数据项。

4. 数据对象：同类数据的集合

就是性质完全相同的一堆数据元素的合集，算是数据的子集。比如全班所有学生的信息记录，组成的整张学生表，就是一个数据对象。

三、数据两大核心结构：逻辑结构与存储结构

所有数据的排布规则，只分两类，对应我开篇说的“脑子里的规则”和“磁盘里的真实排布”，也就是逻辑结构和存储结构。二者相辅相成，构成完整的数据体系。

（一）逻辑结构：存于思维的规则

逻辑结构就是数据元素之间的逻辑关联关系，完全独立于计算机、独立于存储方式，只存在于我们的思维认知里，是我们对数据的排布定义。

这里记一个核心考点、核心误区：有序表是逻辑结构，而顺序表、哈希表、单链表都是存储结构。逻辑结构永远不依赖存储方式，同一个逻辑结构，可以对应多种存储方式。比如线性逻辑结构，既可以顺序存储，也可以链式存储，逻辑不变，存储可变。

逻辑结构整体分为线性、非线性两大派系，对应不同武学境界：

1. 线性结构：单向顺承，一脉相承

顾名思义，数据元素像一条直线，从起点到终点，单向延伸、有序衔接，前后关联清晰，是入门基础结构。

包含普通线性表、受限线性表（栈、队列、串），还有线性表的推广（数组、广义表）。整体规则简单，顺序明确，是所有复杂结构的根基。

2. 非线性结构：多向发散，枝繁叶茂

和线性结构相反，数据元素不再是单一主线，一个节点可以关联多个节点，多向发散。就像一颗种子生根发芽，一根主干衍生无数分支。

主要包含三类：集合结构（元素仅同属一类，无关联）、树形结构（一对多层级关系）、图状结构（多对多复杂关联），是解决复杂场景的核心结构。

（二）存储结构：落地硬件的真实排布

存储结构也叫物理结构，是逻辑结构在计算机磁盘、内存中的真实映射方式。简单说，就是把我们脑子里的逻辑规则，实实在在存到计算机里的具体形式。

存储结构完全依托逻辑结构存在，不能独立存在，且一种逻辑结构可适配多种存储结构。主流分为四种，各有优劣，适配不同场景：

1. 顺序存储：连续排布，有序规整

核心规则：逻辑上相邻的数据元素，在计算机物理内存中也紧密相邻、连续存储。

优点极其突出：支持随机存取，查找指定数据速度极快。

缺点也很明显：需要提前开辟连续内存空间，容易产生内存外部碎片，空间利用率有限。

2. 链式存储：指针串联，灵活自由

不需要连续内存，依靠指针记录下一个元素的存储地址，靠指针串联起所有数据元素的逻辑关系。

优点：无需规整连续空间，不会产生内存碎片，能充分利用所有零散存储单元，空间灵活度极高。

缺点：每个元素都需要额外存储指针信息，占用多余内存；且只能顺序存取，无法快速随机查找。

3. 索引存储：索引映射，快速定位

在存储数据本身的同时，额外建立一张索引表，用索引记录数据的位置信息，就像手机按姓名排序的通讯录，通过索引快速锁定目标。

优点：数据检索、新增、删除操作效率都很高，定位速度快。

缺点：索引表需要单独占用存储空间，且每次增删数据，都需要同步修改索引，增加操作开销。

4. 散列存储：哈希映射，直接寻址

也就是我们常说的哈希存储，通过哈希函数 Hash(Key)，直接根据数据关键字计算出对应的存储地址，一步定位数据位置。

优点：检索、新增、删除结点的速度都是顶尖级别，效率极高。

缺点：极度依赖哈希函数的设计，如果函数规则不合理，会出现存储地址冲突，解决冲突会额外消耗时间和空间资源。

四、数据运算与抽象数据类型

光有数据结构的框架远远不够，搭配对应的操作运算，才算完整的武学体系。数据结构的核心价值，就是依托结构实现高效的数据运算。

1. 数据类型 vs 抽象数据类型

很多新手容易混淆这两个概念，这里通俗区分：

数据类型 = 数据对象 + 基本操作

简单来说，就是规定“这个类型能存什么数据、能做什么操作”。同时会约束数据的取值范围和运算规则，比如字符串类型，只能存储字符文本，不能进行乘除运算，这就是数据类型的约束。

抽象数据类型（ADT） = 数据对象 + 数据关系 + 基本操作

这是更完整、更抽象的结构定义，也是数据结构的核心核心。它不仅规定数据存什么、能做什么，还明确了数据元素之间的逻辑关系。

划重点：只有抽象数据类型能完整定义一套数据结构，单独的数据元素、数据对象、数据关系都做不到。

2. 基本操作的完整规则

每一个抽象数据类型的操作，都有标准规范，包含三大核心要素：

- 参数：分为赋值参数（输入数据）、引用参数（带&，可返回操作结果）

- 初始条件：执行操作之前，数据结构、参数必须满足的前置要求

- 操作结果：操作执行完成后，数据结构的变化、最终返回的结果

五、算法：数据结构的实操心法

如果说数据结构是“招式框架”，那算法就是“运功心法”。数据结构搭好框架，算法负责具体解题，二者相辅相成，缺一不可。

1. 算法的核心概念与五大特性

算法就是针对特定问题的有限求解步骤，是一套有序的指令序列，每一条指令对应一个或多个操作，目的是用固定步骤解决对应问题。

合格的算法，必须满足五大核心特性：

有穷性：所有执行步骤、运行时间都是有限的，绝对不能出现无限死循环，最终一定会结束。

确定性：每一步操作都唯一确定、没有歧义，相同的输入，一定会得到相同的执行步骤和结果。

可行性：所有步骤都能通过计算机基本运算实现，落地可行，不是空想规则。

输入：支持0个或多个外部数据输入，灵活适配不同场景。

输出：必须至少有1个确定的输出结果，无输出的算法没有任何意义。

2. 优质算法的四大设计要求

能运行的算法不代表是好算法，优质算法需要满足四大标准：

正确性：核心底线，能精准解决问题，满足全部题目和业务要求。

可读性：代码逻辑清晰、注释完善，方便自己复盘、他人阅读修改，拒绝晦涩冗余写法。

健壮性：能兼容非法输入、异常数据，不会轻易崩溃、报错，具备容错能力。

高效性：分为时间效率（运行速度快、耗时短）和空间效率（占用内存资源少），二者兼顾。

3. 算法效率度量：时间复杂度与空间复杂度

我们评判算法好坏，不靠主观感觉，靠两套标准：时间复杂度、空间复杂度。

（1）时间复杂度：渐进运行耗时

核心定义：算法中重复执行最多的基本语句，执行次数是问题规模n的函数，记作 T(n)=O(f(n))。

这里纠正一个新手误区：O(f(n))不是代表执行时间等于n²、n，而是指算法运行时间的渐进上限，代表运行时间和对应数量级成正比，而非绝对相等。

时间复杂度分为最好、平均、最坏三种情况，日常评判默认看最坏时间复杂度。比如if-else分支，if耗时n²、else耗时n，整体算法的时间复杂度就取最坏的O(n²)。

通用计算方法：先找到执行频次最高的基本语句，再推导其关于n的函数，最后取数量级即可。

常见时间复杂度（由快到慢排序）：O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

常见场景速记：顺序代码O(1)、单层循环O(n)、双层嵌套循环O(n²)、二分查找O(log₂n)、快排/归并排序O(nlog₂n)、递归全遍历O(2ⁿ)。

同时遵循两大计算法则：加法规则（取最大值）、乘法规则（数量级相乘）。

（2）空间复杂度：渐进内存占用

定义：算法运行所需存储空间的度量，记作 S(n)=O(f(n))，主要统计算法运行所需的辅助空间（算法本身固定占用空间不计入）。

重点概念：算法原地工作，指辅助空间为常量O(1)。注意：O(1)不代表不需要任何空间，而是辅助空间大小和问题规模n无关，恒定不变。

六、本章小结

第一章作为鸿蒙开道的基础篇章，核心就是搭建起数据结构与算法的整体认知。我们不用纠结复杂代码，只需吃透核心逻辑：数据的基础定义、逻辑与存储的双层结构、抽象数据类型的本质、算法的特性与效率评判标准。

所有后续的线性表、栈队列、树、图、查找排序算法，都是在本章基础规则上的延伸。筑基扎实，后续的高阶武学才能一点就通、快速上手。