数据结构-复习

1.数据结构所学内容顺序表数组、单项链表、双向链表、内核链表、队列、栈、哈希算法、二叉树、选择排序、插入排序、冒泡排序、快速排序。2.数据结构中的顺序表和链表有什么区别对比维度顺序表链表内存分布连续分散随机访问支持 O (1)不支持 O (n)中间插入删除慢 O (n)移动元素找到节点后 O (1)修改指针空间分配预先申请容量固定动态 malloc按需分配额外开销无需要存储指针适合场景查询多增删少频繁插入删除长度多变3.单向链表和双向链表有什么区别对比维度单向链表双向链表节点结构数据 next (后继指针)数据 next prev (前驱指针)遍历方向只能从头往后单向遍历正向、反向双向遍历查找前驱节点❌不能直接找要从头遍历✅直接访问 prevO (1)删除当前节点需要先找到前驱节点 O (n)直接删O (1)指针修改数量插入 / 删除改 2 个指针插入 / 删除改 4 个指针内存开销小只有一个指针大多占一份前驱指针空间循环链表单向循环链表双向循环链表内核链表就是它4.什么是内存泄露、如何排查和避免内存泄漏动态申请的堆内存 (malloc /calloc/new)使用完没有释放并且丢失了这块内存的地址程序再也无法回收这块内存。内存来自堆 heap不是栈栈自动释放不存在泄漏后果内存越吃越多长期运行程序卡顿、崩溃、被系统杀死所以使用完成之后必须手动free()排查工具valgrindvalgrind --leak-checkfull ./可执行程序输出definitely lost确定泄漏必须修复indirectly lost间接泄漏子节点没释放still reachable内存还留有指针不算严格泄漏如何避免内存泄漏谁申请谁释放malloc 和 free 成对出现每一条退出分支都要检查是否释放堆内存用完立刻 freefree 之后把指针置 NULL防止野指针链表销毁循环逐个 free 每个节点不能只删头结点尽量减少动态内存能用局部数组 (栈) 就不用 malloc使用内存池程序启动时一次性向操作系统申请一大块连续内存自己切成小块管理。需要内存就从池里拿释放时还给池子5.什么是内存碎片如何避免内存碎片1、外部碎片空闲内存总大小足够但是不连续分散成很多小块没法分配一块大的连续内存。举个例子 堆一共 10KB 空闲但是被切成三块2KB | 3KB | 5KB现在你申请一块 6KB 连续内存。 总空闲 10KB6KB却分配失败这就是外部碎片。产生原因频繁交替 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/free7×24 小时运行服务器、嵌入式设备 程序启动一次性把需要的内存开好运行期间不再动态分配释放。6.链表找倒数第 k 个节点——单链表快慢指针双指针法一次遍历 O (n)快指针 fast先走 k 步然后慢指针 slow和快指针 fast 一起往后走当 fast 走到链表末尾NULLslow指向的就是倒数第 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 调用 BB 调用 C先返回 C再 B再 A表达式括号匹配校验遇到左括号入栈右括号弹出对比递归递归底层就是栈保存现场网页后退、软件撤销 (CtrlZ)最后一步操作最先撤销深度优先搜索 DFS树 / 图遍历✅队列FIFO适用场景任务排队、消息队列多线程任务调度先来的任务先执行广度优先搜索 BFS树 / 图遍历层序遍历二叉树IO 缓冲区、打印任务打印队列提交顺序打印生产者‑消费者模型生产的数据放进队列消费者依次取出循环队列串口、缓存缓冲区10.系统栈和数据结构的栈的区别11.如何实现二叉树的深度遍历算法和广度遍历算法参考二叉树笔记二叉树笔记12.什么是时间复杂度常见时间复杂度13.什么是空间复杂度常见空间复杂度