数据结构

🌸 您好，欢迎您的阅读，等君久矣，愿与君畅谈.
🔭 § 始于颜值 § 陷于才华 § 忠于人品 §
📫 希望我们可以进一步交流，共同学习，共同探索未知的技术世界 稀土掘金 OR GitHub.

---

# 数据结构

[TOC]

# 1. 绪论

# 1. 绪论–数据结构介绍

1. 数据结构学习内容表述
   1. 如何使用程序代码把现实世界的问题信息化
   2. 如何使用计算机高效的处理这些信息从而创造价值
2. 发展阶段：人类文明–> 农业革命–> 工业革命–> 信息革命
3. 关于计算机联系图解


# 2. 绪论–概念理解

1. 数据结构基本概念

   1. 数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料

   2. 数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理

   3. 数据项：一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

   4. 数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集（数据元素描述的东西具有相同的性质）

   5. 数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。(数据元素之间的关系)

   6. 数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。如原子类型，其值不可再分的数据类型；结构类型，其值可以再分解为若干成分（分量）的数据类型

      

   7. 抽象数据类型 (Abstract Data Type,ADT)：抽象数据组织及与之相关的操作。ADT 用数学化的语言定义数据的逻辑结构、定义运算。抽象数据类型定义了一个数据结构

2. 数据结构的三要素

   1. 逻辑结构
      1. 集合结构：各个元素同属一个集合，别无其他关系
      2. 线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继
      3. 树形结构：数据元素之间是一对多的关系
      4. 图状结构 (网状结构)：数据元素之间是多对多的关系
   2. 数据运算：针对于某种逻辑结构，结合实际需求，定义基本运算
   3. 物理结构 (存储结构)：使用计算机表示数据元素之间的逻辑关系
      1. 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现
      2. 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系
      3. 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）
      4. 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储
      5. 非顺序存储 (离散存储)：链式存储、索引存储、散列存储
      6. 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。数据的存储结构会影响存储空间分配的方便程度，也会影响对数据运算的速度
   4. 定义一种数据结构包括逻辑结构、数据运算，如何使用计算机实现这种数据结构主要讲的是物理结构
   5. 运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤

3. 算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

   1. 程序 = 数据结构 + 算法
   2. 算法的特性
      1. 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。算法必须是有穷的，而程序可以是无穷的（死循环不是算法）
      2. 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出
      3. 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
      4. 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合
      5. 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量
   3. 算法的衡量角度
      1. 正确性。算法应能够正确地解决求解问题
      2. 可读性。算法应具有良好的可读性，以帮助人们理解
      3. 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
      4. 高效率与低存储量需求。省时：时间复杂度低；省内存：空间复杂度低

4. 算法的时间复杂度：事前预估算法时间开销 T (n) 与问题规模 n 的关系

   1. 最坏时间复杂度：最坏情况下算法的时间复杂度
   2. 平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间
   3. 最好时间复杂度：最好情况下算法的时间复杂度
   4. 计算方法：寻找一个基本操作 (最深层循环)，并计算执行次数
   5. O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

5. 算法的空间复杂度：空间开销（内存开销）与问题规模 n 之间的关系

   1. 判断口诀：常对幂指阶
   2. O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

# 2. 线性表

# 1. 线性表

1. 定义 (逻辑结构)

   1. 线性表是具有相同数据类型的 n（n≥0）个数据元素的有限序列，其中 n 为表长，当 n= 0 时线性表是一个空表
   2. **a_i** 是线性表中的 第i个 元素线性表中的位序 (位序从 1 开始的，数组下标从 0 开始的)
   3. a1 是表头元素；**a_n** 是表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

2. 基本操作 (运算)

   1. InitList (&L)：初始化表。构造一个空的线性表 L，分配内存空间
   2. DestroyList (&L)：销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间
   3. ListInsert (&L,i,e)：插入操作。在表 L 中的第 i 个位置上插入指定元素 e
   4. ListDelete (&L,i,&e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值
   5. LocateElem (L,e)：按值查找操作。在表 L 中查找具有给定关键字值的元素
   6. GetElem (L,i)：按位查找操作。获取表 L 中第 i 个位置的元素的值
   7. Length (L)：求表长。返回线性表 L 的长度，即 L 中数据元素的个数
   8. PrintList (L)：输出操作。按前后顺序输出线性表 L 的所有元素值
   9. Empty (L)：判空操作。若 L 为空表，则返回 true，否则返回 false
   10. & : 引用数据类型，对参数的修改结果需要 "带回来"，内存地址复制还是指向原地址
   11. 线性表在存储结构上分为顺序表、链表

   

# 2. 顺序表

1. 定义

   1. 顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
   2. 使用 sizeof() 可以获取数据元素占用内存的大小
   3. 静态分配（表长不可调）
      1. 内存中会遗留 脏数据 ，需要设置数据的默认值即 L.length = 0
      2. 若数组存满数据，直接舍弃，因为顺序表的表长确定后无法修改（存储空间是静态的）
   4. 动态分配
      1. malloc函数 ：动态申请内存空间
      2. free函数 ：动态释放内存空间
      3. 练习：手写 malloc、free 这两个函数 L.data=(ElemType*)malloc(sizeof(ElemType)* InitSize);
   5. 特点
      1. 随机访问，即可以在 O (1) 时间内找到第 i 个元素
      2. 存储密度高，每个节点只存储数据元素
      3. 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
      4. 插入、删除操作不方便，需要移动大量元素

2. 插入

   1. 代码实现
   2. 时间复杂度
      1. 最好：O (1)
      2. 最坏：O (n)
      3. 平均：O (n)

3. 删除

   1. 代码实现
   2. 时间复杂度
      1. 最好：O (1)
      2. 最坏：O (n)
      3. 平均：O (n)

4. 查找

   1. 按位查找
      1. 代码实现
      2. 时间复杂度：O (1)
   2. 按值查找
      1. 代码实现
      2. 时间复杂度
         1. 最好：O (1)
         2. 最坏：O (n)
         3. 平均：O (n)

5. 差异

   

# 3. 单链表

1. 定义
   1. 单链表：
   2. 代码实现
   3. 两种实现方式
      1. 带头结点 (代码实现方便)：头指针指向的元素为 null，下一个元素存储数据 L->next==null
      2. 不带头结点 (代码实现不方便)：头指针指向的元素就存储数据 L==null
2. 插入
   1. 按位序插入
      1. 带头结点
      2. 不带头结点
   2. 指定结点的后插操作
   3. 指定结点的前插操作
3. 删除
   1. 按位序删除
   2. 指点结点的删除
4. 查找（三个时间复杂度都是 O(n) ）
   1. 按位查找
      1. 单链表不具备随机访问的特性，只能依次扫描
   2. 按值查找
   3. 求单链表长度
5. 建立（设置一个指向表尾的指针）：核心是初始化操作、指定结点的后插操作
   1. 尾插法：
   2. 头插法：重要应用：链表的逆置

# 4. 双链表

1. 单链表无法逆向检索，双链表可进可退，存储密度较低一些
2. 初始化
3. 插入
4. 删除
5. 遍历：双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度 O (n)
6. 空表：前后指针都指向 null

# 5. 循环链表

1. 循环单链表
   1. 单链表：表尾结点的 next 指针指向 NULL。单链表：从一个结点出发只能找到后续的各个结点
   2. 循环单链表：表尾结点的 next 指针指向头结点。循环单链表：从一个结点出发可以找到其他任何一个结点
   3. 从头结点找到尾部，时间复杂度为 O (n)。从尾部找到头部，时间复杂度为 O (1)
   4. 空表：单手抱住空虚的自己；非空链表：
2. 循环双链表
   1. 双链表：表头结点的 prior 指向 NULL；表尾结点的 next 指向 NULL
   2. 循环双链表：表头结点的 prior 指向表尾结点；表尾结点的 next 指向头结点
   3. 空表：双手抱住空虚的自己；非空链表：
3. 代码问题：如何判断空表？如何判断指定结点是否为表尾结点 / 表头节点？如何在表头、表中、表尾插入 / 删除一个结点

# 6. 静态链表

1. 静态链表
   1. 分配一整片连续的内存空间，各个结点集中安置
   2. 静态链表也可看作用数组的方式实现的链表
   3. 在静态链表中游标充当指针，游标为 - 1 时就是到达表尾
   4. 优点：增、删操作不需要大量移动元素
   5. 缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
   6. 适用场景：①不支持指针的低级语言；②数据元素数量固定不变的场景（如操作系统的文件分配表 FAT）
2. 定义静态链表
3. 基本操作的实现

# 7. 顺序表和链表比较

	顺序表	链表
逻辑结构	都属于线性表，都是线性结构	都属于线性表，都是线性结构
存储结构 / 物理结构	优点：支持随机存取、存储密度高 缺点：大片连续空间分配不方便，改变容量不方便	优点：离散的小空间分配方便，改变容量方便 缺点：不可随机存取，存储密度低
数据运算 / 基本操作
创建	需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源	只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展
增	插入 / 删除元素要将后续元素都后移 / 前移时间复杂度 O (n) 时间开销主要来自移动元素	插入 / 删除元素只需修改指针即可 时间复杂度 O (n), 时间开销主要来自查找目标元素
删
查
弹性	❌	✅
增、删	❌	✅
查	✅	❌
技巧	表长可预估、查询（搜索）操作较多	表长难以预估、经常要增加 / 删除元素