数据结构(2)常见概念

Ne0inhk

15 Mar 2026 — 13 min read

数据结构(2)常见概念

Author: Once Day Date: 2026年2月10日

一位热衷于Linux学习和开发的菜鸟，试图谱写一场冒险之旅，也许终点只是一场白日梦…

漫漫长路，有人对你微笑过嘛…

全系列文章可参考专栏: 数据结构与算法_Once-Day的博客-ZEEKLOG博客

参考文章:速成读者学习规划 labuladong/fucking-algorithm: 刷算法全靠套路，认准 labuladong 就够了！学习数据结构和算法的框架思维《数据结构（C语言版）》

文章目录

数据结构(2)常见概念

1. 基本概念

程序设计的核心并不在于语法技巧，而在于对问题本质的抽象能力。面对一个确定的问题，开发者需要先识别其中的核心数据及其相互关系，再据此选择合适的数据结构，并设计与之匹配的算法。数据结构决定了数据的组织形态，而算法则定义了在这种组织形态上的操作效率，两者共同影响程序的正确性、可维护性与性能上限。

程序设计的实质是对确定问题选择一种好的数据结构，加上设计一种好的算法。

从计算机科学的角度看，数据是对客观事物的符号化描述，其本质是可被计算机存储、传输和处理的编码形式。无论是整数、字符、图像还是复杂对象，最终都需要映射为二进制序列。正因如此，数据并非抽象概念，而是贯穿程序生命周期的基本载体，决定了后续一切操作的可能性。

数据元素是数据的基本单位，通常对应一个具有完整语义的实体。在工程实践中，数据元素往往表现为结构体或类实例，例如一个学生记录或一条网络报文。当多个性质相同的数据元素按某种方式组合在一起时，就形成了数据对象，这种集合为批量处理和统一建模提供了基础。

structStudent{int id; std::string name;float score;};

数据结构，相互之间存在一种或多种特定关系的数据元素的集合。它描述的是数据元素之间的逻辑关系，例如线性关系、层次关系或网状关系。

数据结构的数学表示可如下：
D a t a S t r u c t u r e = ( D , S ) DataStructure = (D,S) DataStructure=(D,S)
D 是有限的数据元素集合，而 S 则刻画了这些元素之间的约束与联系。不同的 S 会直接导致数组、链表、树或图等结构形态的差异。在算法设计中，对 S 的理解尤为关键。同样的数据集合，如果关系建模不当，可能导致时间复杂度或空间复杂度急剧上升。

2. 数据存储

数据存储讨论的是数据结构在计算机硬件层面的具体呈现形式，也称为数据的物理结构。无论逻辑结构多么抽象，最终都需要映射为以字节为单位的存储布局。由于现代计算机以内存地址作为访问基础，数据的物理组织方式直接影响访问效率与实现复杂度。

顺序映像是最直观的一种存储方式，对应顺序存储结构。其核心特征是数据元素在内存中占据一段连续地址空间，元素之间通过地址偏移即可定位。这种结构充分利用了 CPU 缓存和预取机制，适合频繁随机访问的场景，例如数组和静态表结构，其时间性能通常具有可预测性。

int arr[5]={1,2,3,4,5};// arr[i] 的地址 = &arr[0] + i * sizeof(int)

与之相对的是非顺序映像，对应链式存储结构。链式存储不要求内存连续，而是通过在数据元素中显式保存指针，将逻辑上相邻的元素连接起来。这种方式在插入和删除操作上具有天然优势，避免了大规模数据搬移，但访问任意位置元素时往往需要顺序遍历。

structNode{int data; Node* next;};

在工程实践中，两种存储结构并非对立关系，而是针对不同需求的权衡选择。顺序存储更强调空间局部性和访问速度，链式存储则更关注结构灵活性和操作代价的均衡。

存储方式	内存布局	访问效率	插入删除
顺序存储	连续	高	代价较高
链式存储	离散	较低	代价较低

3. 数据类型

数据类型是高级语言对数据抽象的重要成果，它在程序设计中承担着“约束”和“规范”的双重角色。

明确限定了数据元素可能取值的范围，使编译器能够进行类型检查与内存分配。
定义了数据所允许的操作集合，从而约束了程序对数据的使用方式，减少语义错误并提升代码可读性。

从实现层面看，数据类型并不仅是语法概念，而是语言对底层存储和操作语义的封装。例如 int、float 等原子类型在内存中具有固定大小和确定的解释方式，开发者无需关心具体比特布局即可直接使用。这类类型不可再分解，是构建更复杂结构的基础单元。

int counter =0;float ratio =0.75f;

结构类型则体现了“组合”的思想，它由多个原子类型或其他结构类型聚合而成，用于描述更复杂的数据对象。struct、class 等机制使程序能够直接映射现实世界中的实体模型。这种类型不仅包含数据本身，也隐含了数据成员之间的逻辑关联。

structTime{int hour;int minute;int second;};

当进一步从“如何存储”转向“如何使用”时，抽象数据类型（ADT）的概念便显得尤为关键。ADT 将数据元素抽象为数学模型，并显式定义一组与实现无关的基本操作。使用者只关心“能做什么”，而不关心“如何做到”，这为模块化设计和算法复用提供了理论基础。

在形式化表达中，DataStructure = (D, S, P) 不仅描述了数据集合 D 及其关系 S，还引入了操作集合 P，强调操作与数据的不可分割性。实际开发中，数组、栈、队列、映射等常见类型本质上都是 ADT 的具体实现，只是在不同语言中以不同语法形式呈现。

// 栈这一 ADT 的一种简单实现classStack{public:voidpush(int x);voidpop();inttop()const;};

这是高级语言，如C，java，python等已定义好的一类语言，具有以下特性：

表明了一个数据元素所有可能的取值范围。
表明了一个数据元素可能对应的操作。

这些数据类型可分为两类：

原子类型，如int，float等，不可分解。
结构类型，如stuct，time等，可分割，由一些原子类型的数据组合而成。

4. 算法基本概念

算法是对特定问题求解过程的形式化描述，其本质是一组在逻辑上有序、在执行上可落地的指令序列。与程序不同，算法更强调思想与步骤本身，而非具体语法实现。一个良好的算法应当能够清晰刻画“从输入到输出”的转化过程，并在抽象层面保证该过程具备可实现性与可验证性。

算法一般需要满足如下条件：

有穷性，算法必须在有限步骤后结束，而且每一步都可以在有限时间内完成。
确定性，算法的执行步骤必须是有确切的含义，读者理解时不会产生二义性。
可行性，算法的描述的操作应该都可以通过实现的基本运算执行有限次来实现。
明确的输入和输出。

从理论定义看，算法首先必须满足有穷性，即在有限步内结束，且每一步都能在有限时间内完成。确定性则要求算法中不存在歧义，同一输入在同一条件下必然产生同一执行路径和结果。可行性进一步约束算法中的操作必须能由基本运算组合实现，而非停留在不可执行的理想化描述上。

输入与输出的明确性使算法具备工程意义。输入定义了问题的适用范围，输出刻画了问题的求解目标。即便是某些“无输入”的算法，也隐含了初始状态作为输入条件。缺乏清晰输入输出定义的算法，往往难以验证其正确性，更难以复用或推广。

算法正确性并不等价于“永远正确”，而是要求在问题规格定义的范围内，对所有合法输入都能得到满足要求的结果。在实际开发中，常通过精心设计的测试用例来验证算法行为，这既包括典型场景，也包括边界条件与异常情况，从而增强对算法正确性的信心。

// 计算数组最大值的简单算法intmaxElement(const std::vector<int>& a){int maxv = a[0];for(int x : a){if(x > maxv) maxv = x;}return maxv;}

除了正确性，算法还需要满足工程层面的质量要求。可读性直接影响算法的理解成本和维护成本，清晰的结构和恰当的命名往往比“技巧性写法”更重要。健壮性体现在对非法输入和异常状态的处理能力，避免算法在非理想条件下失效或崩溃。

效率性是算法设计中不可回避的核心指标，通常通过时间复杂度和空间复杂度来度量。复杂度分析并不关注具体运行时间，而是关注输入规模增长时算法资源消耗的趋势。在数据规模不断扩大的背景下，合理的复杂度往往比常数级优化更具决定性意义。

5. 算法复杂度

算法复杂度用于刻画算法在输入规模增长时资源消耗的变化趋势，是衡量算法效率的核心指标。常见的复杂度分析主要包括时间复杂度和空间复杂度，两者分别反映算法执行所需的计算步骤数量以及额外占用的存储空间。复杂度分析关注的是数量级而非精确值，从而屏蔽具体硬件、编译器和实现细节的影响。

时间复杂度描述的是算法执行时间随问题规模 N 增长的变化规律。通过统计基本操作的执行次数，并将其表示为 T(N)，可以得到算法的渐进行为。常见的时间复杂度包括 O(1) 的常数级、O(log N) 的对数级、O(N) 的线性级、O(N log N) 的线性对数级，以及 O(N^2)、O(2^N) 等更高复杂度形式，它们在大规模数据下的性能差异极为显著。

// O(N) 时间复杂度intsum(const std::vector<int>& a){int s =0;for(int x : a) s += x;return s;}

空间复杂度则刻画算法在运行过程中对额外内存的需求情况，通常不包含输入本身所占空间。递归算法往往需要额外关注栈空间的消耗，而某些算法通过“以空间换时间”的策略，引入辅助数组或哈希结构，以降低整体时间复杂度。空间复杂度的分析方法与时间复杂度类似，同样关注随 N 增长的渐进趋势。

为了更精确地描述复杂度的上下界关系，引入了多种渐进符号。大 O 记号用于给出算法复杂度的上界，即存在正常数 c 和 n_0，当 N ≥ n_0 时有 T(N) ≤ c f(N)，它刻画的是“至多如此快增长”。在工程实践中，O 记号最为常用，用于评估最坏情况性能。

与之相对，大 Ω 记号给出了复杂度的下界，表示算法至少需要如此多的资源消耗。当 T(N) 同时满足 O(f(N)) 和 Ω(f(N)) 时，便可记为 Θ(f(N))，这意味着算法的增长速度被精确地限定在同一数量级内。相比之下，小 o 记号用于描述严格低阶关系，强调 T(N) 的增长速度显著慢于 p(N)，但又不与其同阶。

有如下的四个定义:

如果存在正常数c和 n 0 n_0 n0,使得当 N ≥ n 0 N\ge n_0 N≥n0时 T ( N ) ≤ c f ( N ) T(N) \le cf(N) T(N)≤cf(N)，则记为 T ( N ) = O ( f ( N ) T(N)=O(f(N) T(N)=O(f(N)。
如果存在正常数c和 n 0 n_0 n0,使得当 N ≥ n 0 N\ge n_0 N≥n0时 T ( N ) ≥ c f ( N ) T(N) \ge cf(N) T(N)≥cf(N)，则记为 T ( N ) = Ω ( f ( N ) T(N)=\Omega (f(N) T(N)=Ω(f(N)。
当前仅当 T ( N ) = O ( h ( N ) ) T(N)=O(h(N)) T(N)=O(h(N))且 T ( N ) = Ω ( h ( N ) ) T(N)=\Omega(h(N)) T(N)=Ω(h(N))时， T ( N ) = Θ ( g ( N ) ) T(N)=\Theta(g(N)) T(N)=Θ(g(N))。
如果 T ( N ) = O ( p ( N ) ) 且 T ( N ) ≠ Θ ( p ( N ) ) T(N)=O(p(N))且T(N)\neq\Theta(p(N)) T(N)=O(p(N))且T(N)=Θ(p(N))，则 T ( N ) = o ( p ( N ) ) T(N)=o(p(N)) T(N)=o(p(N))。