新闻详情

新闻详情

首页 / 资讯中心 / 详情

数据结构-复习

发布时间:2026/9/5 3:54:34来源:尧图网络
数据结构-复习
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.什么是空间复杂度常见空间复杂度
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

Linux 内核高危漏洞解析:bridge 桥接模块组播快速离开路径 UAF 风险 2026/9/5 4:30:40

Linux 内核高危漏洞解析:bridge 桥接模块组播快速离开路径 UAF 风险

2026‑08‑15,NVD 披露 CVE‑2026‑74480 严重级别漏洞,CVSS 评分 9.8,归属 net/bridge 桥接子系统,为组播快速离开逻辑引发的释放后使用漏洞。该缺陷代码最早在 2017 年 1 月提交引入,覆盖此后大量内核版本。目前已有…

阅读更多 →
STM32开发环境优化:VSCode+OpenOCD组合替代CubeIDE的实践指南 2026/9/5 4:30:40

STM32开发环境优化:VSCode+OpenOCD组合替代CubeIDE的实践指南

1. 为什么我放弃纯CubeIDE,改用VSCode这组合如果你用STM32开发超过半年,大概率会经历这样一个过程:刚开始用Keil,后来被ST官方生态吸引转到CubeIDE,用了一阵子觉得代码提示和编辑器体验实在跟不上,于是开始…

阅读更多 →
Cortex-M走向何方:指令集、工具链与AI落地的全面演进 2026/9/5 4:30:40

Cortex-M走向何方:指令集、工具链与AI落地的全面演进

一、Cortex-M 家族这条产品线,为什么会让人越看越迷茫 Cortex-M 这个名字,在嵌入式圈子里几乎是"单片机"的代名词。我接触的很多工程师,手里的活儿从 STM32F103 干到 GD32、国民技术、沁恒,折腾来折腾去,架构…

阅读更多 →
无人机视角航拍河道水面塑料垃圾检测数据集VOC+YOLO格式1320张1类别有增强 2026/9/5 4:30:40

无人机视角航拍河道水面塑料垃圾检测数据集VOC+YOLO格式1320张1类别有增强

注意数据集存在大量增强,原图110张,其他都是通过改变亮度对比度加噪声旋转等形成图片数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件)图片数量(jpg文件个…

阅读更多 →
AI生成头发质感优化:从死气沉沉到生动逼真的技术实践 2026/9/5 4:30:40

AI生成头发质感优化:从死气沉沉到生动逼真的技术实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

阅读更多 →
备战2027国自然,用什么工具才能弯道超车? 2026/9/5 4:27:39

备战2027国自然,用什么工具才能弯道超车?

每一年国自然放榜结束,都会拉开新一轮科研人的差距。有人沉浸在今年落选的遗憾里原地内耗,有人早已抓住放榜黄金窗口期,提前布局来年申报。绝大多数常年陪跑的科研人,并非科研实力不足、实验积累薄弱,而是输在信息闭塞…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞