数据结构

备注

读书笔记和心得源自《数据结构》，「范畅」编著。

一、绪论

截止日期：2024.04.06

1）数据结构基础

关键词

数据（Data）、数据项（Data Item）、数据元素（Data Element）、数据对象（Data Object）、数据结构（Data Structure）、抽象数据类型（ADT）。

逻辑结构：数据的逻辑结构是对数据元素之间关系的描述，分为集合、线性结构、树状结构、图形结构 4 类。

存储结构：逻辑结构在计算机中的存储表示叫数据的存储结构，也叫物理结构。数据的存储结构分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构 4 类。

2）算法的概念

算法是对问题求解的步骤描述。

算法的 5 个特性

有穷性、确定性、可行性、输入性、输出性。

算法设计目标

正确性、健壮性、易读性、高效性、低存储性。

算法描述 可采用 自然语言、程序设计语言、伪代码 来描述。

3）算法分析

算法分析 主要是分析算法的执行时间和存储空间，它们是评判一个算法好与坏的重要指标。从执行时间上分析就是分析算法的时间复杂度；从存储空间上分析就是分析算法的空间复杂度。

提示

随着计算机存储设备的不断发展，我们的算法可能更注重「时间复杂度」这个指标，而「空间复杂度」的重要性可能就要弱化一些。

A、算法的时间复杂度

算法的时间复杂度 是指算法运行所需时间，一般将算法中的执行次数作为时间复杂度的衡量标准。时间复杂度函数记为 T(n) = O(f(n))。

时间复杂度的计算需要考虑 3 个因素：问题规模、语句频率、算法优化。

问题规模：O(f(n))中的 n 为问题规模。
语句频率：是指语句重复执行的次数。
算法优化：是指不同的算法对应不同的时间复杂度，我们应该选择执行效率更高的算法为佳。

提示

判断一个算法好与坏，算法的时间复杂度最坏情况是重要考虑因素。

时间复杂度

从上至下依次的时间复杂度越来越大，执行的效率越来越低。

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

B、算法的空间复杂度

算法的空间复杂度 是指算法及其执行所占用的存储空间。空间复杂度函数记为 S(n) = O(f(n))。

算法的空间复杂度包含以下 3 方面：

算法本身所占存储空间：忽略不计；
输入/输出数据所占存储空间：基本是固定的；
额外需要的辅助存储空间：是算法的空间复杂度的衡量标准。

二、线性表

截止日期：2024.04.06

1）线性表的基本概念

线性表的基本概念

线性表是由 n(n>=0) 个相同类型的数据元素组成的有限序列。「前驱」、「后继」。

2）顺序表

以顺序存储结构进行存储的线性表称为 顺序表。

特点：「数据元素」在逻辑上相邻，在物理存储位置上也相邻。
优点：查找容易。
劣势：删除、插入较麻烦。

思考：顺序表 CRUD？

3）单链表

除了数据 data 外，只有 1 个指针域 next 指向其后继的链表叫 单链表。

特点：「数据元素」在逻辑上相邻，在物理存储位置上不一定相邻。
优点：删除、插入操作时，不需要移动大量数据元素，效率高。
劣势：不能随机存取，查找效率低。

思考：单链表 CRUD？尾插法？头插法？

4）双链表

双链表 有两个指针域，比单链表在节点结构上多了一个指针域 prior--指向前驱节点的指针域，它解决了单链表只能向后操作的问题。

特点：「数据元素」在逻辑上相邻，在物理存储位置上不一定相邻，有两个指针域。
优点：删除、插入操作时，不需要移动大量数据元素，效率高。
劣势：不能随机存取，查找效率低。

思考：双链表 CRUD？尾插法？头插法？「远端优先操作」原则？

5）循环链表

循环链表 基于单链表、双链表改进得来。

特点：首尾相连，形成环。
优点：插入、删除效率高。
劣势：顺序访问而查找效率低。

6）线性表的应用

A、顺序表的应用

TODO

B、单链表的应用

TODO

C、双链表的应用

TODO

D、循环链表的应用

TODO

三、栈和队列

截止日期：2024.04.06

1）栈的基本概念

栈的基本概念

栈是特殊的线性表，它只允许在线性表的一端操作。「栈顶」「栈底」「先进后出」「后进先出」。

根据存储结构不同，栈分为「顺序栈」和「链栈」两大类。

2）顺序栈

以顺序存储结构进行存储的栈称为 顺序栈。

顺序栈：栈判空？栈判满？入栈？出栈？取栈顶数据元素？

3）链栈

以链式存储结构进行存储的栈称为链栈。

链栈：栈判空？栈判满？入栈？出栈？取栈顶数据元素？

4）栈的应用

TODO

5）队列的基本概念

队列的基本概念

队列也是特殊的线性表，它限制在一端插入，在另一端删除。「队尾」「队首」「先进先出」「后进后出」。

6）顺序队列

以顺序存储结构进行存储的队列称为 顺序队列。

顺序队列：队列判空？队列判满？入队？出队？取队首数据元素和取队尾数据元素？

7）链队列

以链式存储结构进行存储的队列称为 链队列。

链队列：队列判空？入队？出队？取队首数据元素和取队尾数据元素？

8）循环队列和优先队列

将顺序队列的首尾相连构成 1 个环，进行队列操作时 front 和 rear 指针在这个环上移动，这样的队列称为 循环队列 或 环形队列。

为队列中的每个元素设置优先级，队首数据元素优先级最高，队尾数据元素优先级最低，即优先级高的先出队，这样的队列称为 优先队列。

优先队列的存储结构可以是顺序存储结构，也可以是链式存储结构。

TODO

9）队列的应用

TODO：杨辉三角

四、字符串

截止日期：2024.04.14

1）字符串的基本概念

基本概念

字符串是有零个或多个字符组成的有限序列，简称串，是一种线性结构。

字符串长度：
空串：
子串：
主串：
串相等：

注意

空格算一个字符，因此，空格串不是空串。

2）顺序串

以顺序存储结构进行存储的字符串称为顺序串。

3）链串

以链式存储结构进行存储的字符串称为链串。

4）字符串的模式匹配

BF 算法、KMP 算法。

字符串的模式匹配，又称字符串匹配，是指子串的定位运算。

假设有两个字符串 s 和 t，s 为主串，也称正文串，t 为子串，也称模式串。在主串 s 中查找与模式串 t 相匹配的子串，如果查找成功，返回匹配的子串第一个字符在主串中的位置。

字符串的模式匹配算法常见的有两种：BF 算法和 KMP 算法。

BF（Brute Force）算法：属于穷举算法，就是穷举主串 s 的所有子串，与模式串 t 进行比较，判断是否存在相等情况。
- 「移动窗口（t 一格一格滑动）」、「主串指针回溯问题」
- 顺序串实现：
- 链串实现：
KMP 算法：是对 BF 算法对改进算法，可解决主串指针回溯问题，从而提高了算法的性能。
- 「移动串口（t 多格滑动）」
- 改进的 KMP 算法：在 t 本身很特殊的情况下其会以更多格数滑动，从而提高了效率。

KMP 算法之所以高效，在于它避免了匹配失败时对主字符串中的字符的重复检查。通过前缀表，算法总是能够跳过那些确定不会匹配的部分，因此，在最坏的情况下，每个字符只被访问一次。

5）字符串的应用

病毒检测：DNA 序列比对

五、递归

截止日期：2024.04.14

1）递归的概念和原理

基本概念

在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。

递归分为直接递归和间接递归，前者是调用自身；后者如 A 调用 B，B 调用 A。如果递归调用语句时最后一条语句，则称为尾递归。

递归过程实质上可分为分解过程和返值过程。

应用条件：

大问题可以转化为若干个小问题来求解，而这些小问题的求解方法与大问题相似，只是在数量规模上不同；
递归调用的次数必须是有限的；
必须有结束递归的条件来终止递归。

2）递归模型

递归模型是递归算法的抽象，它反映一个递归问题的递归结构。它包含递归出口和递归体两部分。递归出口是递归结束的条件，递归体确定递归求解时的递推关系。

3）递归算法的应用

TODO

计算阶乘
计算斐波那契数列
深度复制对象

// 计算阶乘
function factorial(n) {
  if (n === 0) {
    return 1 // 基本情形
  } else {
    return n * factorial(n - 1) // 递归步骤
  }
}

console.log(factorial(5)) // 输出 120

//  计算斐波那契数列
function fibonacci(n) {
  if (n <= 1) {
    return n // 基本情形
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2) // 递归步骤
  }
}

console.log(fibonacci(10)) // 输出 55

// 深度复制对象
function deepCopy(obj) {
  if (obj === null || typeof obj !== 'object') {
    return obj
  }

  let temp = obj.constructor() // 保持继承链
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      temp[key] = deepCopy(obj[key])
    }
  }

  return temp
}

const original = { a: 1, b: { c: 2 } }
const copied = deepCopy(original)
console.log(copied)

4）总结

递归算法总可以转换为用栈结构实现的算法，这是由递归原理推出的。
递归算法的时间复杂度求解有 3 种常见的方法：递推式、master 定理、递归树。
递归算法的时间复杂度=每一次递归的时间复杂度 ✖️ 递归次数；递归算法的空间复杂度=每一次递归的空间复杂度 ✖️ 递归深度。
学会建立递归模型，这是使用递归算法求解问题的关键。

六、数组和特殊矩阵

截止日期：2024.04.14

1）数组的基本概念

基本概念

数组是由相同类型数据元素构成的有限集合，是一个二元组（idx, value）的集合，对每个下标 idx，都有一个 value 值与之对应，下标含有 d（d>=1）个整数时称维数是 d。

数组分为一维数组、二维数组和多维数组。

2）数组的存储结构

数组是以顺序存储方式进行存储的。

数组（一维、二维和多维）均具有随机存取特点；
二维数组的存储可以分为按行优先存储和按列优先存储。

3）数组的基本操作

基本操作包括：创建、初始化、插入、查找、更新、删除、清空、判空等。

4）数组的应用

TODO

5）特殊矩阵的基本概念

基本概念

将 m ✖️ n 的二维数组看作矩阵，则当 m=n 时称为方阵。方阵中的数据元素按照其位置分为 3 个部分：上三角部分、主对角线部分和下三角部分。

对称矩阵：
三角矩阵：若一个 n 阶方阵 A 的下/上三角部分为常数 C，则称其为上/下三角矩阵。
对角矩阵：若一个 n 阶方阵 A 中所有非零数据元素都集中在以主对角线为中心的带状区域，其他数据元素均为 0，则称其为对角矩阵。
稀疏矩阵：

6）特殊矩阵压缩存储

特殊矩阵压缩存储算法，本质上是将其线性化，并计算出压缩前后位置下标的对应关系。

对称矩阵压缩存储：
- 应用场景：金融领域
三角矩阵压缩存储：
- 应用场景：数值线性代数
对角矩阵压缩存储：
- 应用场景：量子力学、信号处理
稀疏矩阵压缩存储：
- 应用场景：社交网络分析（图数据处理）

7）特殊矩阵的应用

TODO

七、树和二叉树

截止日期：2024.04.21

1）TODO

八、图

截止日期：2024.04.21

九、排序

截止日期：2024.04.28

十、查找

截止日期：2024.04.28

数据结构 ​

一、绪论 ​

1）数据结构基础 ​

2）算法的概念 ​

3）算法分析 ​

A、算法的时间复杂度 ​

B、算法的空间复杂度 ​

二、线性表 ​

1）线性表的基本概念 ​

2）顺序表 ​

3）单链表 ​

4）双链表 ​

5）循环链表 ​

6）线性表的应用 ​

A、顺序表的应用 ​

B、单链表的应用 ​

C、双链表的应用 ​

D、循环链表的应用 ​

三、栈和队列 ​

1）栈的基本概念 ​

2）顺序栈 ​

3）链栈 ​

4）栈的应用 ​

5）队列的基本概念 ​

6）顺序队列 ​

7）链队列 ​

8）循环队列和优先队列 ​

9）队列的应用 ​

四、字符串 ​

1）字符串的基本概念 ​

2）顺序串 ​

3）链串 ​

4）字符串的模式匹配 ​

5）字符串的应用 ​

五、递归 ​

1）递归的概念和原理 ​

2）递归模型 ​

3）递归算法的应用 ​

4）总结 ​

六、数组和特殊矩阵 ​

1）数组的基本概念 ​

2）数组的存储结构 ​

3）数组的基本操作 ​

4）数组的应用 ​

5）特殊矩阵的基本概念 ​

6）特殊矩阵压缩存储 ​

7）特殊矩阵的应用 ​

七、树和二叉树 ​

1）TODO ​

八、图 ​

九、排序 ​

十、查找 ​

数据结构

一、绪论

1）数据结构基础

2）算法的概念

3）算法分析

A、算法的时间复杂度

B、算法的空间复杂度

二、线性表

1）线性表的基本概念

2）顺序表

3）单链表

4）双链表

5）循环链表

6）线性表的应用

A、顺序表的应用

B、单链表的应用

C、双链表的应用

D、循环链表的应用

三、栈和队列

1）栈的基本概念

2）顺序栈

3）链栈

4）栈的应用

5）队列的基本概念

6）顺序队列

7）链队列

8）循环队列和优先队列

9）队列的应用

四、字符串

1）字符串的基本概念

2）顺序串

3）链串

4）字符串的模式匹配

5）字符串的应用

五、递归

1）递归的概念和原理

2）递归模型

3）递归算法的应用

4）总结

六、数组和特殊矩阵

1）数组的基本概念

2）数组的存储结构

3）数组的基本操作

4）数组的应用

5）特殊矩阵的基本概念

6）特殊矩阵压缩存储

7）特殊矩阵的应用

七、树和二叉树

1）TODO

八、图

九、排序

十、查找