笔 记 归 档

第一部分 数组

一、什么是数组

---

是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

二、数组相比于容器的优劣

---

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 中。