「数据结构」学习笔记

0
tec

模块一：代码效率优化方法论

复杂度是衡量代码运行效率的重要度量因素

复杂度通常包括「时间复杂度」与「空间复杂度」，其中

  • 时间复杂度与「代码的结构设计」高度相关
  • 空间复杂度与「代码中的数据结构的选择」高度相关

一、时间复杂度

1. 降低时间复杂度的必要性

实际的在线环境中，用户的访问请求可以看作一个流式数据。假设这个数据流中，每个访问的平均时间间隔是 t。如果你的代码无法在 t 时间内处理完单次的访问请求，那么这个系统就会一波未平一波又起，最终被大量积压的任务给压垮。这就要求工程师必须通过优化代码、优化数据结构，来降低时间复杂度。

2. 通常，复杂度的计算方法遵循以下几个原则

  • 复杂度与具体的常系数无关
  • 多项式级的复杂度相加时，选择高者作为结果
  • O(1)也是一个特殊复杂度

3. 一些试验性的结论

  • 一个顺序结构的代码，时间复杂度是 O(1)。
  • 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)。
  • 一个简单的 for 循环，时间复杂度是 O(n)。
  • 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)。（复杂度与具体的常系数无关的原则）
  • 两个嵌套的 for 循环，时间复杂度是 O(n²)。

二、空间复杂度

1. 降低空间复杂度的核心思路

  • 能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构

2. 程序优化的最核心的思路

  1. 暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。

  2. 无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。

    （学会并掌握递归、二分法、排序算法、动态规划等常用的算法思维）

  3. 时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。

    （对数据的操作进行细分，全面掌握常见数据结构的基础知识）

模块二：数据结构基础

什么叫数据结构？

  • 数据结构是一门研究「非数值计算」的程序设计问题中的所涉及数据的「数据元素及其关系」的科学。😓
  • 数据结构=数据元素+关系（结构）

数据结构

增删查

增和删又可以细分为在数据结构中间的增和删，以及在数据结构最后的增和删。区别就在于原数据的位置是否发生改变。查找又可以细分为按照位置条件的查找和按照数据数值特征的查找。几乎所有的数据处理，都是这些基本操作的组合和叠加。

模块三：数据结构的分类

线性表（linear list）

1. 什么是线性表

  • 线性表是n个数据元素的有限序列，最常用的是链式表达，通常也叫做线性链表或者链表
  • 线性表真正的价值在于，它对数据的存储方式是按照顺序的存储
    1. 如果数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适
    2. 如果数据的元素大小确定，删除插入的操作并不多，那么数组可能更适合些

2. 线性表的分类

  • 顺序表

    • 定义：顺序表是指采用「顺序存储」的方式来存储数据元素的线性表
    • 特点：在顺序存储结构中，把线性表 的结点按逻辑顺序依次存放在 一组地址连续的存储单元里

  • 链表

    • 定义：采用「链式结构」来存储数据元素的线性表
    • 特点：
      1. 在每个节点创建时，主动向系统申请相应的存储空间，通过「指针」来链接各个包含数据元素的结点
      2. 链表实现了存储空间的动态管理
      3. 链表在执行插入与删除操作时，只需修改指针即可
    • 分类：单链表、双向链表、循环链表
      • 单链表
      • 双向链表
      • 循环链表

  • 顺序表与链表的区别

栈（Stack）

1. 栈是什么？

  • 定义 - 一种特殊的线性表
  • 特性 - 栈的数据结点必须后进先出，
  • 劣势 - 栈限定降低了操作的灵活性
  • 优势 - 处理只涉及一端新增和删除数据的问题时，效率更高
  • 栈与线性表的不同 - 体现在：增和删的操作，数据新增和删除操作只能在线性表的表尾进行，即“在线性表的基础上加了限制”

2. 栈的分类

  • 顺序栈

    • 栈的顺序存储可以借助数组来实现
    • 定义一个「top指针」来指示「栈顶元素在数组中的位置」
    • 一般以「top」是否为「-1」来判定是否为空栈
    • 假如栈中只有一个数据元素，则「top=0」
    • 入栈时，新增元素放在栈顶，栈顶指针增加1
    • 出栈时，top-1

  • 链栈

    • 用链表的方式对栈的表示

      image-20210303102225900

    • 压栈时，

    • 出栈时，「top指针」指向栈顶元素的「next指针」

    • 新增删除操作的时间复杂度均为O(1)

3. 总结

  • 栈是一个限制版的线性表，只允许数据「从栈顶进出」
  • 时间复杂度，新增、删除操作都是O(1)，查找操作是O(n)
  • 应用场景：浏览器的后退与前进，括号匹配等

队列

顺序队列

链式队列

数组

串

顺序串

链式串

表

广义表

树与二叉树

树

二叉树

森林

哈夫曼树

图

哈希表

模块四

查找

排序

  • 插入排序
  • 交换排序
  • 选择排序
  • 归并排序
  • 基数排序


1774 字