笔 记 归 档

第一部分 数组

一、什么是数组


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

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


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

发布者

王药酒

本站采用 知识共享署名4.0 国际许可协议进行许可 本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名

《笔 记 归 档》上有1条评论

评论已关闭。