6小时掌握虚幻引擎C++开发：从语法基础到实战应用
2026/9/5 4:35:41
1.数据结构所学内容
顺序表数组、单项链表、双向链表、内核链表、队列、栈、哈希算法、二叉树、选择排序、插入排序、冒泡排序、快速排序。
2.数据结构中的顺序表和链表有什么区别
| 对比维度 | 顺序表 | 链表 |
|---|---|---|
| 内存分布 | 连续 | 分散 |
| 随机访问 | 支持 O (1) | 不支持 O (n) |
| 中间插入删除 | 慢 O (n)，移动元素 | 找到节点后 O (1)，修改指针 |
| 空间分配 | 预先申请，容量固定 | 动态 malloc，按需分配 |
| 额外开销 | 无 | 需要存储指针 |
| 适合场景 | 查询多，增删少 | 频繁插入删除，长度多变 |
3.单向链表和双向链表有什么区别
| 对比维度 | 单向链表 | 双向链表 |
|---|---|---|
| 节点结构 | 数据 + next (后继指针) | 数据 + next + prev (前驱指针) |
| 遍历方向 | 只能从头往后单向遍历 | 正向、反向双向遍历 |
| 查找前驱节点 | ❌不能直接找，要从头遍历 | ✅直接访问 prev，O (1) |
| 删除当前节点 | 需要先找到前驱节点 O (n) | 直接删，O (1) |
| 指针修改数量 | 插入 / 删除改 2 个指针 | 插入 / 删除改 4 个指针 |
| 内存开销 | 小，只有一个指针 | 大，多占一份前驱指针空间 |
| 循环链表 | 单向循环链表 | 双向循环链表（内核链表就是它） |
4.什么是内存泄露、如何排查和避免
内存泄漏：动态申请的堆内存 (malloc /calloc/new)，使用完没有释放，并且丢失了这块内存的地址，程序再也无法回收这块内存。内存来自堆 heap，不是栈（栈自动释放，不存在泄漏）
- 后果：内存越吃越多，长期运行程序卡顿、崩溃、被系统杀死，所以使用完成之后必须手动
free()
排查工具：valgrind
valgrind --leak-check=full ./可执行程序输出：
- definitely lost：确定泄漏（必须修复）
- indirectly lost：间接泄漏，子节点没释放
- still reachable：内存还留有指针，不算严格泄漏
如何避免内存泄漏：
- 谁申请，谁释放，malloc 和 free 成对出现
- 每一条退出分支，都要检查是否释放堆内存
- 用完立刻 free，free 之后把指针置 NULL，防止野指针
- 链表销毁：循环逐个 free 每个节点，不能只删头结点
- 尽量减少动态内存，能用局部数组 (栈) 就不用 malloc
- 使用内存池，程序启动时一次性向操作系统申请一大块连续内存，自己切成小块管理。需要内存就从池里拿；释放时还给池子
5.什么是内存碎片，如何避免内存碎片
1、外部碎片
空闲内存总大小足够，但是不连续，分散成很多小块，没法分配一块大的连续内存。
举个例子： 堆一共 10KB 空闲，但是被切成三块：2KB | 3KB | 5KB现在你申请一块 6KB 连续内存。 总空闲 10KB>6KB，却分配失败，这就是外部碎片。
产生原因：频繁交替 malloc、free，小块内存不断释放又分配。
2、内部碎片
给你分配的内存块，比你实际需要的大，多出来的那一部分空间你用不上，也不能给别人用。 例：内存分配器最小粒度是 8 字节，你只申请 3 字节，系统给你 8 字节，多出 5 字节浪费 = 内部碎片。
怎么避免 / 减少内存碎片
方案 1：使用内存池（嵌入式首选）
定长内存池：所有分配出来的块大小一模一样。 释放后放回空闲链表，几乎不会产生外部碎片。STM32、FreeRTOS 大量对象创建销毁优先用内存池，少用 malloc。
方案 2：尽量大块分配，减少小块频繁申请
不要短时间反复 malloc‑free 很小的内存； 能一次性分配好就不要拆成多次小块申请。
方案 3：内存合并（malloc 自带机制）
标准库 malloc/free，释放内存时会尝试把相邻空闲块合并，缓解碎片； 但是频繁随机分配释放，合并也救不了碎片问题。
方案 4：尽量生命周期对齐
一起申请的内存，尽量一起释放。 不要交替：A 申请‑A 释放‑B 申请‑B 释放。
方案 5：使用伙伴系统、slab 分配（Linux 内核）
内核里的 SLAB 内存池，专门管理频繁创建释放的结构体对象，对抗碎片。
方案 6：避免长期运行程序反复 malloc/free
7×24 小时运行服务器、嵌入式设备： 程序启动一次性把需要的内存开好，运行期间不再动态分配释放。
6.链表找倒数第 k 个节点——单链表
快慢指针：双指针法，一次遍历 O (n)
快指针 fast，先走 k 步
然后慢指针 slow和快指针 fast 一起往后走
当 fast 走到链表末尾
NULL，slow指向的就是倒数第 k 个节点
7.双向链表的插入和删除
新节点插入：
1、新插入节点的pnext指向首节点 2、首节点的prev指向新插入的节点
3、头节点的pnext指向新插入节点 4、新插入节点的prev指向头节点
删除节点：
1、被删节点的上一节点的pnext指向被删节点的下一节点
2、被删节点的下一节点的prev指向被删节点的上一节点
3、删除释放被删节点
8.如何判断一个链表有环
快慢指针法
- 慢指针 slow：一次走 1 步
- 快指针 fast：一次走 2 步
- 如果链表无环：fast 最终走到
NULL，结束。 - 如果链表有环：fast 一定会进入环里绕圈，最后追上 slow，两个指针相遇。
9.队列和栈有什么区别？什么场景下使用
| 对比项 | 栈 Stack | 队列 Queue |
|---|---|---|
| 规则 | 后进先出 LIFO，最后进来最先出去 | 先进先出 FIFO，最先进来最先出去 |
| 出入口 | 同一个口：栈顶，只能在栈顶增删元素 | 两个口：队尾入队，队头出队 |
| 形象比喻 | 手枪弹夹，后压进去的子弹先打出去 | 排队买票，先来的人先买到票 |
| 遍历顺序 | 逆序输出 | 顺序输出 |
✅栈（LIFO）适用场景
函数调用栈：函数 A 调用 B，B 调用 C；先返回 C，再 B，再 A
表达式括号匹配校验：遇到左括号入栈，右括号弹出对比
递归：递归底层就是栈保存现场
网页后退、软件撤销 (Ctrl+Z)：最后一步操作最先撤销
深度优先搜索 DFS（树 / 图遍历）
✅队列（FIFO）适用场景
任务排队、消息队列：多线程任务调度，先来的任务先执行
广度优先搜索 BFS（树 / 图遍历，层序遍历二叉树）
IO 缓冲区、打印任务：打印队列，提交顺序打印
生产者‑消费者模型：生产的数据放进队列，消费者依次取出
循环队列：串口、缓存缓冲区
10.系统栈和数据结构的栈的区别
11.如何实现二叉树的深度遍历算法和广度遍历算法
参考二叉树笔记：二叉树笔记