本篇核心知识数据结构四大逻辑结构、两种物理存储、算法三大评价指标时间 / 空间复杂度、排序稳定性、线性表分类、单链表概念、名词释义、节点结构、链表分类、单链表增删改查逻辑 代码一、数据结构概述概念数据结构用来描述数据元素之间的相互逻辑关系 内存存储方式从「逻辑关系」「物理存放」两个维度划分体系是各类算法实现的底层载体。特性逻辑结构只管数据抽象关系和内存怎么存无关物理结构只管数据在内存实际排布同一逻辑结构可选用不同物理实现学习路线逐个吃透每种结构→实现增删改查→结合对应排序算法。二、四大逻辑结构概念1.集合结构所有数据同属一个集合范围元素之间无任何关联关系。2.线性结构元素之间一对一前后相邻排成一条逻辑链。3.树形结构元素一对多的层级从属关系。4.图形结构元素多对多互相连通任意节点可双向建立联系。特性1.集合结构仅归属同一个整体不存在前驱、后继、从属关系。2.线性结构除首元素无前驱、尾元素无后继其余元素各有唯一前驱、唯一后继。3.树形结构一个父节点可以拥有多个子节点子节点仅有一个直接父节点存在唯一根节点逐层向下延伸。4.图形结构无固定头尾节点间连接自由。拓展1.集合结构C 可用数组、容器 set 实现集合存储。2.线性结构典型实现顺序表、链表、栈、队列。3.树形结构典型实现二叉树。三、两种物理存储结构概念1.顺序存储数据在内存占用连续整块空间数组是原生实现。2.链式存储数据分散在内存零散地址依靠指针保存相邻元素地址维系逻辑关系。特性1.顺序存储通过下标随机访问访问效率(O(1))中间插入 / 删除需要批量挪动元素效率低。2.链式存储插入删除仅修改指针指向无需挪动数据不能随机下标访问只能从头依次遍历。代码示例// 顺序存储 int arr[6] {1,2,3,4,5,6}; cout arr[3]; // 下标随机访问 // 链式存储 struct Node{ int data; Node* next; };相似概念比较顺序存连续内存、随机访问快、增删慢链式存离散内存、随机访问慢、增删快。四、算法三大评判标准1时间复杂度概念使用大 O 记法衡量代码执行步数随数据量n的增长趋势忽略常数、低次项。特性由优→劣排序(O(1))常数 (O(logn))对数 (O(n))线性 (O(nlogn))线性对数 (O(n^2))平方 (O(2^n))指数1.(O(1))固定代码行无循环2.(O(logn))循环变量成倍增减i * 23.(O(n))单层循环4.(O(n^2))双层嵌套循环。代码示例// O(1) int a 10; // O(n) for(int i0;in;i); // O(logn) int i1; while(in) i *2; // O(n²) for(int i0;in;i) for(int j0;jn;j);2空间复杂度概念大 O 记法统计算法运行临时开辟的内存开销原始输入内存不计入。特性(O(1))临时变量固定不随 n 变化(O(n))动态开辟数组空间随 n 线性增长。代码示例// O(1) int tmp; // O(n) int* p new int[n];3排序稳定性概念原序列中值相等元素排序后相对先后位置不变 稳定位置颠倒 不稳定。特性稳定排序冒泡、直接插入不稳定排序选择排序。举例原序列[6 (红),6 (绿),5]稳定排序后仍红在前、绿在后。五、线性表概念由同类型数据按一对一逻辑关系构成的线性结构整体元素数量称为线性表长度分为顺序表、链表两类。特性顺序表逻辑线性、物理内存连续数组实现支持下标随机访问中间插入 / 删除需要批量挪动数据效率偏低。链表逻辑线性、物理地址零散不连续依靠指针维系前后关系无法随机下标访问插入删除仅修改指针效率高。相似对比类型访问增删存储顺序表随机 O (1)中间低效连续内存链表只能遍历 O (n)任意位置高效离散内存六、链表基础名词概念链式存储实现的线性表由多个节点串联组成依托指针保存相邻节点地址。特性节点构成数据域存有效数据 指针域存其他节点地址。前驱 / 后继前面 / 后面的所有节点直接前驱紧贴当前的上一个节点直接后继紧贴当前的下一个节点。头指针存储链表首节点地址用来找到整条链表。头结点链表最前端附加节点不存储有效业务数据仅存指针优势链表为空、首节点增删时不用特殊处理头指针统一代码逻辑。尾节点链表最后一个节点后继指针置nullptr。代码示例单链表节点struct Node { int data; // 数据域 Node* next; // 指针域 // 构造函数快速初始化 Node(int val) : data(val), next(nullptr) {} };七、链表四大分类概念根据指针数量与首尾连接形式区分特性单链表仅存后继指针只能从头向后单向遍历本节课重点。双向链表同时存前驱 后继指针可前后双向遍历。循环链表尾节点指针指向头首尾相连成环形。相交链表两条链表部分节点地址重合共享尾部子链。八、单链表常用操作逻辑创建、增、删、改、查、遍历打印1. 尾插法创建链表概念从链表尾部逐个新增节点用尾指针记录末尾优化遍历开销。特性空链表头结点与尾指针同时指向第一个新节点非空新节点接在尾节点后再更新尾指针。代码示例// 参数创建节点个数返回链表头结点 Node* createList(int n) { Node* head new Node(0); // 头结点无有效数据 Node* tail head; for(int i1;in;i){ Node* newNode new Node(i); tail-next newNode; tail newNode; } return head; }2. 遍历打印概念从头结点后继开始循环遍历依次输出数据指针为空结束。特性遍历不修改原链表形参用头指针即可。void print(Node* head) { Node* p head-next; while(p ! nullptr){ cout p-data ; p p-next; } cout endl; }3. 指定位置插入概念在指定下标前插入新节点特性先让新节点指向后继再修改前驱指向新节点防止断链void insert(Node* head, int pos, int val) { Node* p head; // 走到插入位置前一个节点 for(int i0; ipos p-next; i) p p-next; Node* newNode new Node(val); newNode-next p-next; // 新节点先接后面 p-next newNode; // 前驱再接新节点 }4. 按值删除概念查找目标值节点断开链接并释放内存特性先保存待删节点地址修改前驱指针后delete释放避免内存泄漏void delByVal(Node* head, int val) { Node* p head; // 找到待删节点的前驱 while(p-next p-next-data ! val) p p-next; if(p-next nullptr) return; // 无目标 Node* temp p-next; p-next temp-next; delete temp; }5. 修改 查找修改遍历匹配数值直接改写数据域查找找到返回节点指针找不到返回空。//查找 Node* find(Node* head,int key){ Node* phead-next; while(pp-data!key) pp-next; return p; } //修改 void modify(Node* head,int old,int newVal){ Node* pfind(head,old); if(p) p-data newVal; }九、拓展插入顺序不可逆新节点先接后继再改前驱颠倒会丢失整条后续链表删除必须释放delete长期遗漏造成内存泄漏头结点设计规避首节点增删时头指针特殊判断。同一逻辑结构可以选用不同物理实现如线性→数组 / 链表是数据结构灵活设计的核心。
C/C++ 数据结构（一）基础概念、线性表链表
本篇核心知识数据结构四大逻辑结构、两种物理存储、算法三大评价指标时间 / 空间复杂度、排序稳定性、线性表分类、单链表概念、名词释义、节点结构、链表分类、单链表增删改查逻辑 代码一、数据结构概述概念数据结构用来描述数据元素之间的相互逻辑关系 内存存储方式从「逻辑关系」「物理存放」两个维度划分体系是各类算法实现的底层载体。特性逻辑结构只管数据抽象关系和内存怎么存无关物理结构只管数据在内存实际排布同一逻辑结构可选用不同物理实现学习路线逐个吃透每种结构→实现增删改查→结合对应排序算法。二、四大逻辑结构概念1.集合结构所有数据同属一个集合范围元素之间无任何关联关系。2.线性结构元素之间一对一前后相邻排成一条逻辑链。3.树形结构元素一对多的层级从属关系。4.图形结构元素多对多互相连通任意节点可双向建立联系。特性1.集合结构仅归属同一个整体不存在前驱、后继、从属关系。2.线性结构除首元素无前驱、尾元素无后继其余元素各有唯一前驱、唯一后继。3.树形结构一个父节点可以拥有多个子节点子节点仅有一个直接父节点存在唯一根节点逐层向下延伸。4.图形结构无固定头尾节点间连接自由。拓展1.集合结构C 可用数组、容器 set 实现集合存储。2.线性结构典型实现顺序表、链表、栈、队列。3.树形结构典型实现二叉树。三、两种物理存储结构概念1.顺序存储数据在内存占用连续整块空间数组是原生实现。2.链式存储数据分散在内存零散地址依靠指针保存相邻元素地址维系逻辑关系。特性1.顺序存储通过下标随机访问访问效率(O(1))中间插入 / 删除需要批量挪动元素效率低。2.链式存储插入删除仅修改指针指向无需挪动数据不能随机下标访问只能从头依次遍历。代码示例// 顺序存储 int arr[6] {1,2,3,4,5,6}; cout arr[3]; // 下标随机访问 // 链式存储 struct Node{ int data; Node* next; };相似概念比较顺序存连续内存、随机访问快、增删慢链式存离散内存、随机访问慢、增删快。四、算法三大评判标准1时间复杂度概念使用大 O 记法衡量代码执行步数随数据量n的增长趋势忽略常数、低次项。特性由优→劣排序(O(1))常数 (O(logn))对数 (O(n))线性 (O(nlogn))线性对数 (O(n^2))平方 (O(2^n))指数1.(O(1))固定代码行无循环2.(O(logn))循环变量成倍增减i * 23.(O(n))单层循环4.(O(n^2))双层嵌套循环。代码示例// O(1) int a 10; // O(n) for(int i0;in;i); // O(logn) int i1; while(in) i *2; // O(n²) for(int i0;in;i) for(int j0;jn;j);2空间复杂度概念大 O 记法统计算法运行临时开辟的内存开销原始输入内存不计入。特性(O(1))临时变量固定不随 n 变化(O(n))动态开辟数组空间随 n 线性增长。代码示例// O(1) int tmp; // O(n) int* p new int[n];3排序稳定性概念原序列中值相等元素排序后相对先后位置不变 稳定位置颠倒 不稳定。特性稳定排序冒泡、直接插入不稳定排序选择排序。举例原序列[6 (红),6 (绿),5]稳定排序后仍红在前、绿在后。五、线性表概念由同类型数据按一对一逻辑关系构成的线性结构整体元素数量称为线性表长度分为顺序表、链表两类。特性顺序表逻辑线性、物理内存连续数组实现支持下标随机访问中间插入 / 删除需要批量挪动数据效率偏低。链表逻辑线性、物理地址零散不连续依靠指针维系前后关系无法随机下标访问插入删除仅修改指针效率高。相似对比类型访问增删存储顺序表随机 O (1)中间低效连续内存链表只能遍历 O (n)任意位置高效离散内存六、链表基础名词概念链式存储实现的线性表由多个节点串联组成依托指针保存相邻节点地址。特性节点构成数据域存有效数据 指针域存其他节点地址。前驱 / 后继前面 / 后面的所有节点直接前驱紧贴当前的上一个节点直接后继紧贴当前的下一个节点。头指针存储链表首节点地址用来找到整条链表。头结点链表最前端附加节点不存储有效业务数据仅存指针优势链表为空、首节点增删时不用特殊处理头指针统一代码逻辑。尾节点链表最后一个节点后继指针置nullptr。代码示例单链表节点struct Node { int data; // 数据域 Node* next; // 指针域 // 构造函数快速初始化 Node(int val) : data(val), next(nullptr) {} };七、链表四大分类概念根据指针数量与首尾连接形式区分特性单链表仅存后继指针只能从头向后单向遍历本节课重点。双向链表同时存前驱 后继指针可前后双向遍历。循环链表尾节点指针指向头首尾相连成环形。相交链表两条链表部分节点地址重合共享尾部子链。八、单链表常用操作逻辑创建、增、删、改、查、遍历打印1. 尾插法创建链表概念从链表尾部逐个新增节点用尾指针记录末尾优化遍历开销。特性空链表头结点与尾指针同时指向第一个新节点非空新节点接在尾节点后再更新尾指针。代码示例// 参数创建节点个数返回链表头结点 Node* createList(int n) { Node* head new Node(0); // 头结点无有效数据 Node* tail head; for(int i1;in;i){ Node* newNode new Node(i); tail-next newNode; tail newNode; } return head; }2. 遍历打印概念从头结点后继开始循环遍历依次输出数据指针为空结束。特性遍历不修改原链表形参用头指针即可。void print(Node* head) { Node* p head-next; while(p ! nullptr){ cout p-data ; p p-next; } cout endl; }3. 指定位置插入概念在指定下标前插入新节点特性先让新节点指向后继再修改前驱指向新节点防止断链void insert(Node* head, int pos, int val) { Node* p head; // 走到插入位置前一个节点 for(int i0; ipos p-next; i) p p-next; Node* newNode new Node(val); newNode-next p-next; // 新节点先接后面 p-next newNode; // 前驱再接新节点 }4. 按值删除概念查找目标值节点断开链接并释放内存特性先保存待删节点地址修改前驱指针后delete释放避免内存泄漏void delByVal(Node* head, int val) { Node* p head; // 找到待删节点的前驱 while(p-next p-next-data ! val) p p-next; if(p-next nullptr) return; // 无目标 Node* temp p-next; p-next temp-next; delete temp; }5. 修改 查找修改遍历匹配数值直接改写数据域查找找到返回节点指针找不到返回空。//查找 Node* find(Node* head,int key){ Node* phead-next; while(pp-data!key) pp-next; return p; } //修改 void modify(Node* head,int old,int newVal){ Node* pfind(head,old); if(p) p-data newVal; }九、拓展插入顺序不可逆新节点先接后继再改前驱颠倒会丢失整条后续链表删除必须释放delete长期遗漏造成内存泄漏头结点设计规避首节点增删时头指针特殊判断。同一逻辑结构可以选用不同物理实现如线性→数组 / 链表是数据结构灵活设计的核心。
