第一部分 数组
一、什么是数组
是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
二、数组相比于容器的优劣
1)优势
- 支持随机访问,根据下标访问的时间复杂度为 $O(1)$。
- 相比容器,数组性能更高。
2)劣势
- 低效的「插入」和「删除」
在插入和删除某个数据时,会有数据的移动操作。
插入操作时间复杂度为 $O(n)$。移动数据采取的技巧是,将插入数据移动到数组最后。
删除操作时间复杂度为 $O(n)$。为了减少移动操作,可以直接记录哪个数据被删除,
当数组中每隔更多的空间时,进行一次整体的数据删除。大大减少了数据搬移带来的时间损耗。
- 数组的访问越界问题
当访问的存储空间已经越界时,可能程序仍然能够运行,这样会造成未知的 bug。
一般会用容器来替代。
Note:对于数组以及 c++ vector 容器的选择问题,对于业务开发,用容器即可。但是对于性能要求特别高的地方,或者追求简洁的表达方式。可以直接操作数组。但是要求自己分配申请内存和删除
第二部分 链表
一、什么是链表与数组有什么不同
一组用指针将零散的内存块串联起来的数据结构。相比于数组的连续内存空间,链表结构是离散的空间,具有更灵活的性质。
二、为什么用链表及其种类
1)用链表的原因
在程序运行时需要一块大的内存空间,存储 1GB 大小的数据,假设此时数组已经满了,如果新来数据时,我们需要申请 1.5GB 的内存空间,然后将 1GB 数据拷贝到 1.5GB 空间中。此时需要耗费很长时间,当然,如果此时没有连续的 1.5GB 空间,数组就无法适用,对于链表来说,我们就可以直接申请一块小的空间存储数据。
2)链表种类及其定义
- 单链表(带有/不带有头指针):增删查找复杂度为 $O(n)$。
- 循环链表(尾 —> 头,适合处理具有环形结构特点的问题):比如约瑟夫问题。
- 双向链表(前后两个指针):可以在时间复杂度为 $O(1)$ 的情况下找到前驱节点。使得在某些情况下插入和删除操作都要比单链表简单高效。
- 双向循环链表
3)链表删除操作两种方式
- 删除节点中「值等于某个给定值」的结点
- 删除给定指针指向的结点
三、链表经典的应用场景 —— LRU 缓存淘汰策略
解决思路:维护一个单链表,越靠近链表尾部的节点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。步骤如下:
- 如果此数据已经在链表中了,那么将数据对应的节点,直接替换到链表的头部。可以是数据交换,或者是节点的交换。
- 如果数据不在链表中,则此时分为两种情况
- 缓存未满,则将此节点直接插入到链表的头部。
- 缓存满了,则链表尾节点去除,然后将新的数据节点插入链表头部。
复杂度:$O(n)$。可以引入散列表(Hash Table)来优化。
四、链表 vs 数组、单链表 vs 双链表,及其注意事项
1)数组 vs 链表
数组:连续存储、占用连续内存,可借助 cpu 缓存机制提高访问效率。但是在声明时就要占用很大的内存。因此在申请内存时,要尽可能与自己的空间相符。
链表:访问效率低,可以支持动态扩容。
2)单向链表 vs 双向链表
删除给定指针指向的结点:插入和删除对于单向链表是 $O(n)$,对于双链表是 $O(1)$。对于有序链表且按值查询的效率,双向链表要高于单向链表。双向链表可以根据值的大小向前或者向后查找。
但是双向链表的占用空间要高于单向链表。但是会提升效率,这是一种空间换取时间的思想!
3)轻松写出正确的链表代码
- 警惕指针丢失和内存泄露(在插入和删除节点时注意指针顺序,以及删除节点的释放空间问题)
- 利用哨兵简化实现难度{比如单链表建立一个头结点使得插入操作统一}
- 重点留意边界条件处理,检验在以下情况时能否顺序工作
- 链表为空时
- 链表只有一个节点时
- 包含两个节点时
- 代码逻辑在处理第一个节点和尾节点时
- 举例画图,辅助思考
- 多写多练是重点!
一、什么是栈
从栈的操作特性来看,是一种“操作受限”的线性表,只允许在端插入和删除数据。
栈有如下特性:
1)栈: 后进先出,仅在一端插入和删除数据。
二、为什么需要栈
任何数据结构都是对特定应用场景的抽象,当某个数据集合只涉及在某端插入和删除数据(或者实际问题可以转化为这种方式)且满足后进者先出,先进者后出的操作特性时,我们应该首选栈这种数据结构。
三、如何实现栈
栈可以由数组和链表来实现。分别叫做顺序栈和链式栈。具体可以参考根目录下 /src/stack/stack.hpp
查看顺序栈的实现。
Note:栈指针永远指向栈顶(无数据)。
复杂度分析
- 固定大小的栈,时间和空间复杂度都为 $O(1)$。
- 支持动态扩容的栈
- 最好时间复杂度:$O(1)$
- 最坏时间复杂度:$O(n)$
- 平均时间复杂度:$O(1)$ ,可以用摊还分析法进行分析。
四、栈的应用
- 函数调用栈
- 栈在表达式求值中的应用
思路:用两个栈来实现,一个保存操作数,一个保存运算符。左到右的遍历表达式,当遇到数字,直接将其压入操作数栈,遇到运算符,就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素优先级高,那么直接将当前运算符压栈,如果比运算符栈栈顶优先级低或者相同,则从运算符栈中取出栈顶元素,从操作数中拿出两个操作数,然后进行运算。在把计算结果压入操作数栈,继续比较当前运算符和运算符栈顶元素。
- 栈在括号匹配中的应用
思路:未匹配的左括号放入栈中,然后遍历括号字符串,如果是左括号,则直接压入栈,如果是右括号,则比较栈顶元素是否和当前括号匹配。如果匹配,就把栈顶元素弹出,然后继续浏览字符串,进行下一个括号的判断。如果不匹配或者栈最后不为空,说明括号不是成对的。
- 栈在浏览器的前进和后退功能上的应用
思路:用两个栈 X,Y。X 保存首次浏览器页面,栈顶元素就是当前正在浏览的页面。当点击后退键,从 X 中拿出一个页面放在 Y 中,当点击前进时,从 Y 中拿出一个页面放在 X 中。
《笔 记 归 档》上有1条评论
评论已关闭。