基本概念

核心概念定义

数据（Data）：信息的载体，是计算机程序加工处理的原料。数据本身没有意义，只有通过解释才能成为有用的信息。
数据元素（Data Element）：数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。例如：学生记录就是一个数据元素。
数据项（Data Item）：构成数据元素的最小单位，是不可分割的原子数据。例如：学号、姓名、年龄等。
数据对象（Data Object）：具有相同性质的数据元素的集合，是数据的一个子集。例如：所有学生记录构成的集合。

数据类型分类

数据类型（Data Type）：一个值的集合和定义在此集合上的一组操作的总称。

原子类型：其值不可再分的数据类型（如整型、字符型）
结构类型：其值可以再分解为若干成分的数据类型（如数组、结构体）
抽象数据类型（ADT）：一个数学模型及定义在该数学模型上的一组操作。它是对数据的逻辑抽象，定义了数据的取值范围、结构形式以及操作集合，与具体实现无关。

数据结构核心概念

数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。

数据结构三要素：

逻辑结构：数据元素间的逻辑关系
存储结构：数据在计算机中的存储方式
数据运算：定义在逻辑结构上的操作集合

数据结构研究内容：

数据如何组织（逻辑结构设计）
数据如何存储（物理结构选择）
数据如何运算（算法设计与实现）

重要关系：

算法设计取决于选定的逻辑结构
算法实现依赖于采用的存储结构

逻辑结构分类

逻辑结构：数据元素之间的逻辑关系，从逻辑关系上描述数据，与具体存储方式无关。

结构类型	关系特征	典型实例	特点说明
集合结构	无特定关系	数学集合	元素间无逻辑关系
线性结构	一对一	线性表/栈/队列/串	有唯一前驱和后继
树形结构	一对多	树/二叉树	分层次的层次结构
图状结构	多对多	有向图/无向图	任意复杂的网状关系

存储结构分类

存储结构：数据结构在计算机中的表示方式，也称物理结构。包括数据元素的存储和关系的存储两个方面。

存储类型	存储特点	优势	劣势
顺序存储	逻辑相邻的元素物理相邻	支持随机存取，存储密度高	插入删除需移动大量元素
链式存储	用指针显式表示逻辑关系	插入删除操作灵活高效	只能顺序存取，额外指针开销
索引存储	建立索引表存储元素地址	检索速度快	需要额外索引空间
散列存储	通过哈希函数计算存储位置	平均查找时间为O(1)	可能产生哈希冲突

算法和算法评价

算法基本概念

算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。每条指令表示一个或多个操作。

算法本质：

是问题求解过程的精确描述
由一系列明确的计算步骤组成
能够将输入转换为相应的输出

算法的五个基本特性

特性	具体要求	说明与示例
有穷性	算法必须在有限步骤后终止，每步在有限时间完成	区别于操作系统等无限运行程序
确定性	每条指令含义明确，相同输入产生相同输出	不允许有二义性的操作
可行性	每个操作都能通过基本运算在有限时间内实现	算法在理论和实践上都可执行
输入	有零个或多个来自特定对象集合的输入	可以无输入（如随机数生成）
输出	有一个或多个与输入有特定关系的输出	必须有输出，体现算法价值

算法质量评价标准

评价指标	具体要求	评估方法
正确性	能够正确解决问题	理论证明+测试用例验证
可读性	算法易于理解和实现	清晰的逻辑结构和注释
健壮性	能处理异常和边界情况	输入验证和错误处理
时间效率	运行时间尽可能短	时间复杂度分析
空间效率	存储空间占用尽可能少	空间复杂度分析

算法复杂度分析

时间复杂度

基本概念：

语句频度：算法中语句的执行次数
时间函数T(n)：算法执行时间与问题规模n的关系
渐近时间复杂度O(n)：当n趋于无穷大时T(n)的数量级

常见时间复杂度：

复杂度	名称	典型算法示例	性能特点
O(1)	常数复杂度	数组随机访问	最优，不随n变化
O(log n)	对数复杂度	二分查找	优秀，增长缓慢
O(n)	线性复杂度	顺序查找	良好，线性增长
O(n log n)	线性对数复杂度	归并排序、堆排序	较好，最优比较排序
O(n²)	平方复杂度	冒泡排序、选择排序	一般，适用小规模
O(2ⁿ)	指数复杂度	汉诺塔问题	差，仅适用极小规模

空间复杂度

基本概念：算法执行过程中所需存储空间与问题规模n的关系。

空间组成：

固定空间：算法本身所需的空间（指令、常量、简单变量）
可变空间：算法执行中动态申请的空间（递归栈、动态数组等）

常见空间复杂度：

复杂度	空间特点	典型示例	说明
O(1)	常数空间	冒泡排序	原地算法，最优
O(n)	线性空间	归并排序	需要辅助数组
O(log n)	对数空间	快速排序递归	递归调用栈

算法分析方法

递归算法分析

分析方法	适用场景	核心思想
递推公式法	标准分治算法	建立递推关系T(n)=aT(n/b)+f(n)
递归树法	复杂递归结构	可视化递归调用过程
主定理法	特定递推形式	直接套用公式求解

算法优化策略

优化策略	实现思路	效果示例
时空权衡	用空间换取时间	哈希表：O(n)→O(1)
分治策略	分解子问题并合并	排序：O(n²)→O(n log n)
动态规划	保存子问题解	斐波那契：O(2ⁿ)→O(n)
贪心算法	局部最优选择	某些优化问题的高效解

重点知识总结

核心概念辨析

数据类型分类

分类标准	类型	定义特征	典型示例
按元素类型	单型数据类型	所有元素类型相同	整型数组、字符串
	多型数据类型	可包含不同类型元素	结构体、联合体
按结构复杂度	原子类型	值不可再分	int、char、float
	结构类型	值可分解为多个成分	数组、记录
	抽象数据类型	逻辑结构+操作集合	栈、队列、树

数据结构与数据类型对比

概念	形式化表示	核心要素	关注重点
数据结构	(D, R)	D: 数据对象 R: 数据关系	数据的组织形式
数据类型	(D, R, P)	增加P: 基本操作集	数据的操作接口

易混概念辨析

数据相关概念层次

概念层次	定义	关键特征	实例说明
数据项	数据的最小单位	不可分割的原子数据	学生记录中的”学号”
数据元素	数据的基本单位	由若干数据项组成	完整的学生记录
数据对象	数据元素的集合	性质相同的元素集合	所有学生记录的集合
数据结构	带关系的数据对象	元素间存在特定关系	按学号排序的学生表

结构分类对比

结构类型	关系表示方式	存储特点	典型应用
逻辑结构	抽象的逻辑关系	与存储方式无关	算法设计依据
存储结构	物理存储映射	包含数据和关系存储	算法实现基础

存储结构具体实现：

存储方式	关系表示	优势	劣势
顺序存储	物理位置隐含关系	随机访问，存储紧凑	插入删除代价高
链式存储	指针显式表示关系	动态分配，操作灵活	额外空间，顺序访问

时间复杂度分析

概念	定义	关键点	经典案例
时间复杂度	最坏情况下执行时间的上界	取决于： • 问题规模(n) • 数据初态	汉诺塔O(2ⁿ)
基本操作	最深层循环内的操作	统计执行次数	循环体内的核心操作

常见误区澄清

错误观点	正解	反例
“所有数据结构都有插入、删除、查找”	基本操作取决于结构特性	二维数组无插入删除功能
“存储结构需要额外存储元素关系”	顺序存储通过物理位置隐含关系	数组不需要指针表示相邻关系

设计原则

原则	内涵	实践意义
抽象封装	定义与实现分离	数据结构变化不影响应用
操作独立性	应用与存储结构解耦	便于底层优化调整

抽象数据类型(ADT)

特征	说明	设计要点
逻辑特性优先	仅关注数学特性	定义规范接口
实现无关性	不限定内部表示	允许性能优化
稳定性	接口不变则外部无感知	契约式编程

补充说明

汉诺塔复杂度证明：
- 递推式：T(n) = 2T(n-1) + 1
- 解方程得O(2ⁿ)
操作设计准则：
- 基本操作应完备且正交
- 避免暴露内部实现细节
物理结构本质：
- 必须完整存储：
  - 数据元素本身
  - 元素间逻辑关系的物理表示
【习题】数据结构被形式定义为（D，S), 其中D是( )的有限集合，S是D上的( )有限的集合。
A、算法
B、数据元素
C、数据操作
D、逻辑结构
E、操作
F、映像
G、存储
H、关系

正确答案：BH

线性表

线性表的定义

线性表（Linear List）：由n（n≥0）个具有相同数据类型的数据元素组成的有限序列。

数学表示：L = (a₁, a₂, a₃, …, aₙ)

其中aᵢ是线性表中的第i个元素（1≤i≤n）
n为线性表的长度，当n=0时称为空表
a₁是表头元素，aₙ是表尾元素

线性表的逻辑特征

特征	具体描述	重要性说明
有限性	元素个数有限	区别于无限序列
同质性	所有元素具有相同的数据类型	保证操作的一致性
序列性	元素在逻辑上有先后顺序	体现线性关系的本质
唯一性	除首尾元素外，每个元素有唯一前驱和后继	一对一的线性关系
抽象性	只关注逻辑关系，不涉及具体存储方式	便于算法设计和分析

线性表的基本操作

核心操作定义

操作类型	函数原型	功能描述	返回值说明
初始化	`InitList(&L)`	构造一个空的线性表L	成功返回OK
销毁	`DestroyList(&L)`	销毁线性表并释放内存空间	成功返回OK
插入	`ListInsert(&L, i, e)`	在第i个位置插入元素e	成功返回OK
删除	`ListDelete(&L, i, &e)`	删除第i个位置的元素	成功返回OK，e返回删除值
按值查找	`LocateElem(L, e)`	查找值为e的元素位置	返回位置，失败返回0
按位查找	`GetElem(L, i)`	获取第i个位置的元素值	返回元素值
求长度	`Length(L)`	返回线性表的元素个数	返回长度值
判空	`Empty(L)`	判断线性表是否为空	空返回true

操作的前置条件

操作	前置条件	异常处理
插入	1≤i≤n+1，表未满	位置非法或表满时失败
删除	1≤i≤n，表非空	位置非法或表空时失败
按位查找	1≤i≤n，表非空	位置非法时返回错误
按值查找	表非空，元素类型支持比较操作	未找到时返回0

线性表的存储结构

顺序存储结构（顺序表）

基本概念

顺序表（Sequential List）：用一组地址连续的存储单元依次存储线性表的数据元素。

存储特点：

逻辑上相邻的元素在物理上也相邻
可以随机访问表中任一元素
存储密度高（存储密度 = 1）

顺序表的实现方式

实现方式	存储分配	优点	缺点	适用场景
静态分配	编译时确定	实现简单，访问效率高	容量固定，空间利用率低	表长变化不大
动态分配	运行时分配	容量可变，空间利用率高	实现复杂，可能内存碎片	表长变化较大

顺序表的基本操作及复杂度

操作类型	最好情况	最坏情况	平均情况	空间复杂度	操作特点
插入	O(1)	O(n)	O(n)	O(1)	需要移动元素
删除	O(1)	O(n)	O(n)	O(1)	需要移动元素
按位查找	O(1)	O(1)	O(1)	O(1)	随机访问优势
按值查找	O(1)	O(n)	O(n)	O(1)	需要顺序扫描

链式存储结构（链表）

基本概念

链表（Linked List）：用一组任意的存储单元存储线性表的数据元素，通过指针链接各元素。

存储特点：

逻辑上相邻的元素在物理上不一定相邻
只能顺序访问，不支持随机访问
存储密度小于1（需要额外存储指针）

链表的分类

链表类型	结构特点	优点	缺点	适用场景
单链表	每个节点只有一个指针域	实现简单，空间开销小	只能单向遍历	一般的线性表操作
双链表	每个节点有前驱和后继指针	可双向遍历，删除方便	空间开销大	需要双向操作的场景
循环链表	尾节点指向头节点	便于循环操作	实现稍复杂	循环处理的应用
静态链表	用数组模拟链表结构	不需要指针，便于调试	容量固定	不支持指针的语言

链表的基本操作及复杂度

操作类型	最好情况	最坏情况	平均情况	空间复杂度	操作特点
插入	O(1)	O(n)	O(n)	O(1)	需要先定位到位置
删除	O(1)	O(n)	O(n)	O(1)	需要先定位到位置
按位查找	O(1)	O(n)	O(n)	O(1)	需要顺序遍历
按值查找	O(1)	O(n)	O(n)	O(1)	需要顺序遍历

顺序表与链表的比较

性能对比

比较维度	顺序表	链表	选择建议
存储密度	高（=1）	低（<1）	空间要求高选顺序表
随机访问	支持，O(1)	不支持，O(n)	需要随机访问选顺序表
插入删除	平均O(n)，需移动元素	平均O(n)，但不移动元素	频繁插删选链表
内存分配	连续分配	离散分配	内存紧张选顺序表
缓存性能	好（局部性原理）	差（指针跳转）	性能要求高选顺序表

应用场景选择

应用特点	推荐存储结构	理由说明
表长基本稳定，查找频繁	顺序表	随机访问优势明显
表长变化大，插删频繁	链表	避免大量元素移动
对存储空间要求严格	顺序表	存储密度高，无额外指针开销
需要双向遍历	双链表	支持前驱访问
实现简单，开发效率优先	顺序表	实现和调试相对简单

线性表的应用与算法复杂度分析

理解线性表不仅要掌握其理论定义和基本操作，更要能在实际问题中根据性能需求选择合适的存储结构。本章将深入探讨顺序表和链表的算法复杂度，并结合典型应用场景进行分析。

核心操作复杂度对比

时间复杂度分析

操作类型	顺序表 (平均)	顺序表 (最坏)	链表 (平均)	链表 (最坏)	关键影响因素
按位查找 (GetElem)	O(1)	O(1)	O(n)	O(n)	顺序表：基于地址偏移计算，与位置无关。链表：需从头节点开始顺序遍历。
按值查找 (LocateElem)	O(n)	O(n)	O(n)	O(n)	无论顺序表还是链表，都需要逐一比较元素值。
插入 (Insert)	O(n)	O(n)	O(n)	O(n)	顺序表：主要开销在于移动插入位置后的所有元素。链表：主要开销在于查找到插入位置的前驱节点。
删除 (Delete)	O(n)	O(n)	O(n)	O(n)	顺序表：主要开销在于移动删除位置后的所有元素。链表：主要开销在于查找到待删除节点的前驱节点。
在指定节点后插入	-	-	O(1)	O(1)	链表：若已持有前驱节点的指针，则插入操作仅需修改指针，与表长无关。
删除指定节点	-	-	O(1) (双链表) / O(n) (单链表)	O(1) / O(n)	双链表：若持有待删除节点的指针，可直接获取前驱，O(1)完成。单链表：仍需O(n)查找前驱。

核心结论：

随机访问是顺序表的核心优势。
插入/删除的效率取决于查找的效率。链表在已知节点的情况下进行插入/删除操作具有巨大优势。

空间复杂度分析

存储结构	空间复杂度	存储密度	内存分配特点
顺序表	O(n)	1	整块分配：需要一块连续的内存空间，可能会因容量不足导致频繁的内存重分配和数据复制。
链表	O(n)	< 1	离散分配：每个节点独立分配内存，通过指针连接。空间利用率更高，但有额外的指针开销。

典型应用场景分析

顺序表的应用场景

顺序表凭借其O(1)的随机访问能力和良好的缓存局部性，在以下场景中表现出色：

应用领域	具体案例	优势分析
科学计算与数据分析	矩阵/向量运算、NumPy/Pandas库	底层采用连续内存数组，完美契合CPU缓存机制，数值计算和数据处理性能极高。
高效查找算法	二分查找、哈希表（开放地址法）	这些算法都要求能够快速访问任意位置的元素，顺序表是其实现的天然基础。
CPU缓存与内存管理	高速缓存行 (Cache Line)	CPU从内存加载数据时，会一次性加载一个连续的数据块（缓存行），顺序表的物理连续性使其缓存命中率远高于链表。
作为其他数据结构的底层实现	堆（Heap）、哈希表	完全二叉树（堆的逻辑结构）可以用数组完美表示，利用索引即可计算父子关系，无需指针。

链表的应用场景

链表的核心优势在于高效的、动态的插入和删除操作，尤其适用于表长频繁变化或需要高效节点操作的场景。

应用领域	具体案例	优势分析
操作系统	进程管理、文件系统	进程的创建和销毁、空闲磁盘块的管理，都涉及频繁的、动态的插入和删除，链表是理想选择。
内存管理	内存池 (Memory Pool)、伙伴系统 (Buddy System)	用于管理空闲内存块，当程序申请或释放内存时，可以高效地从链表中添加或移除相应大小的内存块。
数据结构实现	图的邻接表、哈希表（拉链法）	当图的顶点度数差异很大时，邻接表（由链表数组构成）能有效节省空间。拉链法解决哈希冲突时，每个桶位都是一个链表。
缓存淘汰算法	LRU (Least Recently Used) 缓存	LRU要求能快速将最新访问的元素移到表头，并淘汰表尾元素。使用双向链表配合哈希表，可实现O(1)时间的访问和淘汰操作。

案例研究：LRU缓存淘汰算法

问题描述：设计一个容量有限的缓存，当缓存满时，需要淘汰最近最少使用的数据。

解决方案：使用一个哈希表 (HashMap) 和一个双向链表 (Doubly Linked List)。

哈希表：存储键 (key) 到双向链表节点 (Node) 的映射，实现O(1)时间的快速查找。
双向链表：维护数据的“新鲜度”。链表头部是最新访问的，尾部是最久未访问的。

操作	实现流程	复杂度
访问数据 (get)	1. 通过哈希表找到节点。 2. 将该节点从链表中移动到头部。 3. 返回节点值。	O(1)
插入数据 (put)	1. 若已存在：更新值，并将节点移到链表头部。 2. 若不存在： a. 创建新节点，插入链表头部。 b. 在哈希表中添加映射。 c. 若缓存已满：删除链表尾部节点，并从哈希表中移除对应映射。	O(1)

为什么是双向链表？
因为在移动或删除节点时，需要同时修改其前驱节点和后继节点的指针。双向链表可以在O(1)时间内完成这些操作，而单链表则需要O(n)时间来查找前驱节点。

存储结构选择策略

决策依据	优先选择顺序表	优先选择链表
核心操作	查找/访问操作远多于插入/删除	插入/删除操作远多于查找/访问
表长变化	表长基本固定或变化不大	表长频繁变化，难以预估
内存要求	内存空间有限，要求高存储密度	内存空间充裕，可接受指针开销
性能要求	追求极致的缓存性能和计算速度	对随机访问性能要求不高

常见面试题与解题思路

本章将精选关于线性表的常见面试题，提供详细的解题思路、多种实现方法以及完整的C++代码，帮助你巩固知识，从容应对面试。

单链表反转

问题描述：给定一个单链表的头节点，将其反转，并返回反转后链表的头节点。

解题思路：
这是链表操作中最经典、最基础的题目之一。核心思想是改变节点的next指针的指向，使其指向其前一个节点。

迭代法：推荐使用此方法，因为它空间复杂度为O(1)，且逻辑清晰。需要三个指针：
- pre：指向当前节点的前一个节点，初始为nullptr。
- cur：指向当前正在处理的节点，初始为head。
- next：临时保存当前节点的下一个节点，防止链表断裂。
遍历链表，依次将cur的next指针指向pre，然后同步向后移动pre和cur。
递归法：思路更巧妙，但空间复杂度为O(n)，且可能因递归深度过大导致栈溢出。
- 递归的终止条件是链表为空或只有一个节点。
- 递归调用reverseList(head->next)，得到反转后的子链表的头节点newHead。
- 将head->next的next指针指向head，再将head的next指针设为nullptr。

C++ 代码实现 (迭代法)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* nextTemp = cur->next; // 临时保存下一个节点
            cur->next = pre;               // 当前节点指向前一个节点
            pre = cur;                     // pre后移
            cur = nextTemp;                // cur后移
        }
        return pre; // 返回新的头节点
    }
};

环形链表检测

问题描述：给定一个链表，判断链表中是否有环。

解题思路：

哈希表法：遍历链表，将每个访问过的节点的地址存入哈希表中。如果遇到一个节点已存在于哈希表中，说明链表有环。时间复杂度O(n)，空间复杂度O(n)。
快慢指针法（Floyd判圈算法）：最优解法。定义两个指针slow和fast，都从头节点出发。
- slow每次走一步。
- fast每次走两步。
- 如果链表中存在环，fast指针最终会从后面追上slow指针，两者相遇。如果fast或fast->next到达nullptr，则说明无环。

C++ 代码实现 (快慢指针法)

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false; // 快指针到达终点，无环
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true; // 快慢指针相遇，有环
    }
};

合并两个有序链表

问题描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路：

迭代法：创建一个哑节点（dummy node）作为新链表的头，简化边界处理。使用一个指针cur指向新链表的尾部。比较两个链表的当前节点值，将较小的节点连接到cur后面，然后移动相应链表的指针和cur指针。当一个链表遍历完后，将另一个链表余下的部分直接拼接到新链表末尾。
递归法：比较两个链表的头节点l1和l2。
- 若l1->val < l2->val，则l1为新链表的头，其next指针指向mergeTwoLists(l1->next, l2)的结果。
- 否则，l2为新链表的头，其next指针指向mergeTwoLists(l1, l2->next)的结果。
- 递归终止条件是任一链表为空。

C++ 代码实现 (迭代法)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1); // 创建哑节点
        ListNode* cur = dummy;

        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }

        // 拼接剩余部分
        cur->next = (l1 != nullptr) ? l1 : l2;

        ListNode* head = dummy->next;
        delete dummy; // 释放哑节点
        return head;
    }
};

删除链表的倒数第 N 个结点

问题描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路：

快慢指针法：这是解决此类问题的经典方法。定义fast和slow两个指针。
1. 让fast指针先从头节点走 n 步。
2. 然后fast和slow指针同时向后走，直到fast指针到达链表末尾（fast->next == nullptr）。
3. 此时，slow指针正好指向倒数第 n+1 个节点，即待删除节点的前一个节点。
4. 修改slow的next指针，slow->next = slow->next->next，即可删除目标节点。
注意边界情况：如果删除的是头节点（即n等于链表长度），fast走完n步后会是nullptr。此时直接返回head->next即可。为了统一处理，可以引入哑节点。

C++ 代码实现 (快慢指针 + 哑节点)

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* fast = head;
        ListNode* slow = dummy;

        // 1. 快指针先走 n 步
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
ß
        // 2. 快慢指针同时走，直到快指针到达末尾
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // 3. 删除目标节点
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;
        delete toDelete;

        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};