数据结构

ObjectKaz Lv4
  2021-06-24 05:20 2021-06-24 05 创建   2023-05-25 17:17:17 2023-05-25 17:17 更新    3.3k 字  13 分钟  

介绍

基本概念

  1. 数据元素：数据的基本单位
  2. 数据项：具有独立含义的数据最小单位
  3. 数据对象：性质相同的数据元素的集合
  4. 数据结构：所有数据元素及其关系

逻辑结构和存储结构

逻辑结构

  1. 集合
  2. 线性：线性表、有序表、栈、队列、双端队列、串
  3. 树形：树、二叉树
  4. 图形：图

存储结构

  1. 顺序存储：顺序表、顺序栈等
  2. 链式存储：单向链表、双向链表、循环链表、链栈等
  3. 索引存储：索引
  4. 散列存储：哈希表

线性表

逻辑结构

  1. 有穷性：元素个数有限
  2. 一致性：所有元素性质相同
  3. 序列性：每个元素只有一个前驱节点和后继节点

顺序表

操作时间复杂度空间复杂度
访问O(1)O(1)O(1)O(1)
增加O(N)O(N)O(1)O(1)
删除O(N)O(N)O(1)O(1)

插入算法

  1. 元素后移,最少 0 次，最大 N 次
  2. 赋值

平均移动次数：N2\frac{N}{2}

删除算法

  • 步骤：元素前移,最少 0 次，最大 N-1 次

  • 平均移动次数：N−12\frac{N-1}{2}

分区算法

分区算法是快速排序的一部分。

  1. 设置基准值，通常是第一个值

  2. 备份基准值

  3. 设置双指针：i 指向头, j 指向尾

  4. 向左扫描，寻找一个比基准值小的元素，其索引为 j

    • 扫描过程中可能会出界

  5. 移动这个元素到 i 所在位置上

    • 如果是第一次移动，那么 i 就是初始值，也就是基准值的位置，这个时候可以直接替换，因为基准值已经备份了。
    • 如果这不是第一次移动，那么 i 就是上次使用的值，但它的值已经被放到了另外一个地方。

  6. 向右扫描，寻找一个比基准值小的元素，其索引为 i

    • 扫描过程中可能会出界

  7. 移动这个元素到 j 所在位置上

    • j 就是上次使用的值，但它的值已经被放到了另外一个地方

  8. 重复 4-7，直到 i 小于 j

    • 当循环终止时，i 等于 j
数组-区间版本的分区算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//[low,high)
void partition(int *arr, int low, int high)
{
  int i = low, j = high, mid = arr[low];
  while (i < j)
  {
    while (j > i && arr[j] > mid)
      j--;
    arr[i] = arr[j];

    while (j > i && arr[i] <= mid)
      i++;
    arr[j] = arr[i];
  }

  arr[i] = mid;
}

/*
  usage:
  partition(arr, 0, sizeof(arr) / sizeof(int) - 1);
*/

下面的算法和上面的算法思路差不多，唯一的区别是把两次赋值改成了交换。

需要注意的是：

  • 循环体内交换前需要 判断 i、j 是否相等
  • 循环体外的交换不要使用 mid，因为 mid 和 arr[low] 的地址不同
  • 实际上，在整个过程中， arr[low] 是不变的，因为第一次循环有arr[low] <= mid，增长后i最小也是 low+1。也就是说，这类解法 备份基准元素 是可选的，因为基准元素所在位置不会被赋其他值。
数组-区间版本的分区算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//[low,high)
void partition(int *arr, int low, int high)
{
  int i = low, j = high, mid = arr[low];
  while (i < j)
  {
    while (j > i && arr[j] > mid)
      j--;

    while (j > i && arr[i] <= mid)
      i++;
    swap(arr[0], arr[i]);
  }

  swap(arr[0], arr[i]);
}

/*
  usage:
  partition(arr, 0, sizeof(arr) / sizeof(int) - 1);
*/

单向链表

操作时间复杂度空间复杂度
访问O(N))O(N))O(1)O(1)
增加O(1)O(1)O(1)O(1)
删除O(1)O(1)O(1)O(1)

插入元素

顺序：

  • 非首节点：创建节点->链接后节点->链接前节点
  • 首节点：创建节点->链接后节点->修改首指针

删除元素

顺序：

  • 非首节点：保存节点->前后连接->删除节点
  • 首节点：保存节点->修改首指针->删除节点

创建链表

  1. 头插法
    • 头插法通常会事先准备一个额外的节点，可能是空节点或者链表信息节点
    • 每次插入时，指向这个额外的节点的指针不动
graph LR
NODEH(链表信息)-->NODEI1(A:i-1)-->NODEE(...)-->NODE1(A:1)
1
2
current->next = head->next;
head->next = current;
  1. 尾插法
    • 可以不准备额外的节点
    • 每次插入时，指向这个额外的节点的指针移动到插入节点的末尾
graph LR
NODEH(链表信息)-->NODE1(A:1)-->NODEE(...)-->NODEI1(A:i-1)
1
2
3
// current 即将插入的节点；last 最后一个节点
current->next = last->next;
last->next = current;

循环条件

1
2
//current 迭代结点
current != NULL;

循环链表

循环链表在单链表的基础上，将首尾节点连接起来。

循环条件

1
2
//head 头结点,current 迭代节点
current->next != head;

栈

一种后进先出的数据结构 LIFO。

主要操作： 入栈、出栈。

应用：表达式解析、括号匹配、DFS

队列

一种先进先出的数据结构 FIFO。

主要操作： 入队、出队

应用：BFS

循环队列

设 head 为队首，tail 为队尾，size 为队列的长度，i 为数组下标。

  1. 队空条件：head == tail
  2. 队满条件：(tail+1)%size=head
  3. 迭代器：(i+1)%size(递增迭代) 和 (i-1+size)%size（递减迭代）

数组和广义表

矩阵的压缩存储

  1. 对称矩阵的压缩存储：存储一半就行。

K=i(i+1)2+jK=\frac{i(i+1)}{2}+j,（i>ji>j）

K=j(j+1)2+iK=\frac{j(j+1)}{2}+i,（j>=ij>=i），（i,j）调换就行

  1. 三角矩阵的压缩存储：

下三角：k=i(i+1)2+jk=\frac{i(i+1)}{2}+j

树

表示

  1. 树形
  2. 文氏图
  3. 凹入表示
  4. 括号表示

基本概念

  1. 节点的度：结点子树个数
  2. 树的度：所有结点度的最大值
  3. m 次树：度数为 m 的树
  4. 树的结点等于度数加一

存储结构

  1. 双亲存储结构：一个数组，存储某个数据的父下标
  2. 孩子链存储结构
  3. 孩子兄弟链存储结构

二叉树

介绍

满二叉树

  1. 所有分支结点都有左右孩子
  2. 叶子结点在二叉树的底下
  3. 只有度为 0 和度为 2 的节点

完全二叉树

  1. 只有最下面两层结点度数小于 2，度数为 1 的只能在最后一层最左边的位置

二叉树的性质

  1. 非空二叉树：叶子节点数=双分支结点数+1，n0=n2+1n_0=n_2+1

二叉树与普通树的转换

左孩子，右兄弟

存储结构

完全二叉树顺序存储

  1. 求父元素：$\left \lfloor \frac{i}{2} \right \rfloor $
  2. 求左子元素：2i2i
  3. 第 i 行第一个元素：2i−12^{i-1}

遍历

  1. 前序遍历：访问根节点->访问左子树->访问右子树

  2. 中序遍历：访问左子树->访问根节点->访问右子树

  3. 后序遍历：访问左子树->访问右子树->访问根节点

  4. 层次遍历：BFS

  5. 求序列问题：先写根节点（前序在开头，中序在中间，后序在末尾，然后留空位置），再写左节点，再写右节点

  6. 由序列构造树：

    • 条件：中序序列+（前/后）序列任意一个
    • 方法：
      • 中序序列中间的某个位置对应着根
      • 前后序列的起始（或终止）位置对应着根

  7. 线索二叉树：

    • 方法：把空的左指针指向遍历序列的前驱结点，空的右指针指向遍历序列的后继
    • 提高遍历的空间效率
    • 遍历方法：指向首节点、寻找右子树

哈夫曼树

  1. 目的：求最小带权路径长度 WPL，其中WPL=∑i=1nwiliWPL=\sum_{i=1}^{n} w_il_i，wiw_i 为权重，lil_i 为路径长度，nn为叶子结点数

  2. 步骤

    • 定义一个森林FF，包含所有叶子节点
    • 选择最小的两个节点，组合在一起，形成的新树，放入森林
    • 重复操作，直到森林只有一棵树

  3. 哈夫曼编码：左边路径标 0，右边路径标 1，按照路径组合成编码

图

存储结构

  1. 邻接矩阵
  2. 邻接表

遍历

深度优先遍历 DFS

  • 过程：访问初始点 v->寻找未被访问的点 w->以 w 为初始点进行深度优先遍历
  • 应用：寻找路径、寻找所有路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool visited[MAX_SIZE];

template <typename T>
void dfs(Graph<T> *g, int node = 0)
{

  visited[node] = true;
  cout << g->arr[node].data;

  GraphLinkNode *gn = g->arr[node].head;
  while (gn != NULL)
  {
    if (!visited[gn->edge_id])
    {
      dfs(g, gn->edge_id, false);
    }
    gn = gn->next;
  }


}

广度优先搜索

  • 过程：初始点 v 入队->若队列不为空，则循环从队列中取出一个元素 w->寻找 w 相邻的所有未访问的元素，并入队
  • 应用：寻找最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <typename T>
void bfs(Graph<T> *g, int node = 0)
{
  Queue<int> qu;

  qu.enqueue(node);
  visited[node] = true;

  while (!qu.isEmpty())
  {
    int current_node = qu.dequeue();
    GraphLinkNode *node = g->arr[current_node].head;
    cout << g->arr[current_node].data;
    while (node != NULL)
    {
      if (!visited[node->edge_id])
      {
        visited[node->edge_id] = true;
        qu.enqueue(node->edge_id);
      }
      node = node->next;
    }
  }

}

最小生成树

  1. 概念：生成树中各边权值最小的树称为最小生成树

Prim 算法

  1. 用两个集合 U,V 分别表示找到的点集，和未找到的点集；
  2. 以 U 中的点为起点 a，在 V 中找一个点为终点 b，要求这两个点构成的边（a，b）的权值是其余不成环的边中最小的
  3. 重复第二步，直至 V 中的点集为空，U 中的点集为满

Kruskal 算法

每次找最小的且不成环的一条边

最短路径

Dijkstra 算法

过程：

  1. 定义一个 dist 数组表示起始点到下标为 i 的节点的最短路径，一个 path 数组表示当前下标为 i 的节点的上一个节点位置，集合 U 表示已加入的节点
  2. 计算起始点链接到的各个边的权值，并写入 dist 数组，如果没有边则设置 -1
  3. 从 dist 数组中寻找未走过且路径最短的点 p
  4. 将 p 加入 U，然后重新计算 距离(距离[i] = dist[p]+p到i的距离)，如果距离下降则修改 dist，对发生改动的下标，在 path 相应下标下，修改值为 p
  5. 重复操作，直到 U 满了

求解：

  1. 到 i 的最短路径长度：dist[i]
  2. 求具体路径：path[i] 的值为上一个节点的位置，一直寻找，直到值为 0

拓扑排序

步骤：

  1. 找一个没有前驱的节点并输出它
  2. 删掉这个节点
  3. 重复前两步，直到找不到没有前驱的节点

结果：如果输出了全部元素，则图中没有回路，否则有回路

查找

线性表的查找

  1. 顺序查找
    • 成功查找长度：n+12\frac{n+1}{2}
  2. 折半查找：找中点->改区间 循环
    • 求查找长度：画二叉排序树

树表的查找

  1. 二叉排序树的创建：

    • 小的放左边，大的放右边
    • 左子树元素都比根小，右子树都比根大
    • 其中序序列递增有序

  2. 计算查找长度

    • 成功：路径权值和取平均
    • 失败：补上树中所有空缺的节点，计算空缺的节点路径权值和取平均

哈希表

  1. 概念：h(k)h(k) 把关键字kk 映射为kk 的地址

  2. 哈希冲突：

    • 线性探测法：遇到冲突就右移，右边没有了再从数组开始位置开始找
    • 平方探测法：只探测下标 d 中，d±i0modmd \pm i_0 mod m 的位置
    • 拉链法：把冲突的元素用链表进行连接

  3. 查找长度计算：探测次数之和

小结

排序

直接插入排序

每次将无序区的第一个元素插入到有序区的指定位置

折半插入排序

每次将无序区的第一个元素插入到有序区的指定位置，不同的是找插入位置的方式为二分查找

希尔排序

每次排序时指定一个 d,将表中的元素分成 d 组，每组进行直接插入排序，再取更小的 d 进行排序，直到 d 等于 1

冒泡排序

每轮排序比较相邻两个元素，前面大于后面则交换，直到不发生交换为止。

快速排序

找一个基准，将表分成小于基准值和大于基准值两部分，然后分别对这两部分进行快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//[low,high)
int partition(int *arr, int low, int high)
{
  int i = low, j = high, mid = arr[low];
  while (i < j)
  {
    while (j > i && arr[j] > mid)
      j--;
    arr[i] = arr[j];

    while (j > i && arr[i] <= mid)
      i++;
    arr[j] = arr[i];
  }

  arr[i] = mid;
  return i;
}

void qsort(int *arr,int low, int high){
  if (low >= high) return;
  int i = partition(arr,low,high);
  qsort(arr,low,i-1);
  qsort(arr,i+1,high);
}

各种排序算法的比较

  • 标题: 数据结构
  • 作者: ObjectKaz
  • 创建于: 2021-06-24 05:00:20
  • 更新于: 2023-05-25 17:17:17
  • 链接: https://www.objectkaz.cn/1e06366eacac.html
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
此页目录
数据结构
  1. 介绍
    1. 基本概念
    2. 逻辑结构和存储结构
  2. 线性表
    1. 逻辑结构
    2. 顺序表
    3. 单向链表
    4. 循环链表
  3. 栈
  4. 队列
    1. 循环队列
  5. 数组和广义表
    1. 矩阵的压缩存储
  6. 树
    1. 表示
    2. 基本概念
    3. 存储结构
  7. 二叉树
    1. 介绍
    2. 存储结构
    3. 遍历
    4. 哈夫曼树
  8. 图
    1. 存储结构
    2. 遍历
    3. 最小生成树
    4. 最短路径
    5. 拓扑排序
  9. 查找
    1. 线性表的查找
    2. 树表的查找
    3. 哈希表
    4. 小结
  10. 排序
    1. 直接插入排序
    2. 折半插入排序
    3. 希尔排序
    4. 冒泡排序
    5. 快速排序
    6. 各种排序算法的比较