简明数据结构

数据结构是一门很重要的计算机基础课,知识点多而且难度不小,这里列出了数据结构中比较容易遗忘的内容。

在这篇博客中,我尽量用我觉得最好理解的方式描述一个算法,简明扼要,相关的代码可能不完全,如果有兴趣的话欢迎访问我的 GitHub

字符串快速匹配 - KMP

  • next 数组的求解,即部分匹配值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int q = 1, k = 0;
    next[0] = 0;
    for (q = 1; q < length; ++q){
    while (k > 0 && pattern[q] != pattern[k])
    k = next[k - 1];
    if (pattern[q] == pattern[k])
    ++k;
    next[q] = k;
    }
  • 根据 next 数组进行匹配跳跃

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 移动位数 = 已匹配的字符数 - 对应的部分匹配值
    int i = -1, q = 0;
    while(++i < source_length) {
    while(q > 0 && pattern[q] != source[i])
    q = next[q-1];
    if (pattern[q] == source[i])
    ++q;
    if (q == pattern_length)
    return i - pattern_length + 1;
    }

参考链接

二叉树的遍历 - 先序,中序,后序

  • 先序,首先访问根结点,然后遍历左子树,最后遍历右子树

    1
    2
    3
    4
    5
    6
    7
    void pre_order(TreeNode* node) {
    if(node != NULL) {
    printf("%d ",node->data);
    pre_order(node->left);
    pre_order(node->right);
    }
    }
  • 中序,首先遍历左子树,然后访问根结点,最后遍历右子树

    1
    2
    3
    4
    5
    6
    7
    void mid_order(TreeNode* node) {
    if(node != NULL) {
    mid_order(node->left);
    printf("%d ",node->data);
    mid_order(node->right);
    }
    }
  • 后序,首先遍历左子树,然后遍历右子树,最后访问根结点

    1
    2
    3
    4
    5
    6
    7
    void post_order(TreeNode* node) {
    if(node != NULL) {
    post_order(node->left);
    post_order(node->right);
    printf("%d ",node->data);
    }
    }

二叉树应用

  • 线索二叉树,利用空的左右指针,加上左右 tag 标志,快速定位二叉树的前趋和后继,使二叉树更容易遍历。
  • 赫夫曼树,所有叶子结点的带权路径长度之和最小的二叉树。
    1
    2
    3
    4
    5
    赫夫曼树构成方法
    1. 将所有节点各看成一颗树;
    2. 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
    3. 从森林中删除选取的两棵树,并将新树加入森林;
    4. 重复 2, 3 步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

二叉查找树

特性

  • 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。

查找

  • 若b是空树,则搜索失败,否则:
  • 若x等于b的根节点的数据域之值,则查找成功;否则:
  • 若x小于b的根节点的数据域之值,则搜索左子树;否则:
  • 查找右子树。

插入

  • 若b是空树,则将s所指结点作为根节点插入,否则:
  • 若s->data等于b的根节点的数据域之值,则返回,否则:
  • 若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则:
  • 把s所指节点插入到右子树中。(新插入节点总是叶子节点)

删除

  • 若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
  • p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点f的左子树(当p是左子树)或右子树(当p是右子树)即可,作此修改也不破坏二叉查找树的特性。
  • p结点的左子树和右子树均不空。在删去p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树,s为p左子树的最右下的结点,而p的右子树为s的右子树;其二是令p的直接前驱(in-order predecessor)或直接后继(in-order successor)替代p,然后再从二叉查找树中删去它的直接前驱(或直接后继)。

图的存储 - 出边表,入边表,邻接矩阵

  • 出边表,每个节点的所有出边用链表表示,表头即本节点,所有节点的出边链表构成一个数组。
  • 入边表,每个节点的所有入边用链表表示,表头即本节点,所有节点的入边链表构成一个数组。
  • 邻接矩阵,节点到节点的距离构成一个矩阵,即二维数组,当边不存在时对应的值为无穷大。

图的遍历 - BFS,DFS

  • BFS 即广度遍历,先访问自己,然后访问所有的子节点,每访问一个子节点将其加入队列,遍历完子节点就出队一个节点,接着遍历其子节点并入队,直到所有能到达的节点都访问完毕且队列为空。
  • DFS 即深度遍历,先访问自己,然后深度优先遍历任意一个未访问过的子节点(递归),直到所有能到达的节点都被访问。

最小生成树 - Prime,Kruskal

  • Prime,典型贪心算法

    1
    2
    3
    4
    Prime
    1. 在 G 中任取一个顶点加入生成树 V ,并在 G 中删除。
    2. 选取一条连接 V 和 G 的权最小的边,将它和另一个端点加进 V 。
    3. 重复步骤 2,直到所有的顶点都进入 V 为止。
  • Kruskal,也是一种贪心算法

    1
    2
    3
    4
    Kruskal
    1. G 去掉所有的边,构成有 n 棵树的森林,同时边的集合为 E。
    2. 在 E 中找到一条权值最小且连接不同的树的边 e,将连接的两棵树变成一棵树,同时在 E 中删除 e。
    3. 重复 2,直到森林只有一棵树。

最短路径

  • Dijkstra

    1
    2
    1. 设定集合 S,S 仅含起点 o 。
    2. 起点为 o ,选取其出边权值最小的边及对应的点 i,添加到 S 中。对于添加进 S 的 i,遍历起每一条出边,如果 A[o][i] + A[i][j] < A[o][j] ,更新 A[o][j] ,重复本次动作,直到能到达的点都遍历完为止。
  • Floyd

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //对于每一对顶点 i j ,考虑一个中间点 k ,看从 i 经过 k 到 j 是否比不经过近,如果近则更新边值。
    for(k=0;k<n;k++) {
      for(i=0;i<n;i++)
      for(j=0;j<n;j++)
      if(A[i][j]>(A[i][k]+A[k][j])) {
    A[i][j]=A[i][k]+A[k][j];
    path[i][j]=k;
    }
    }

二分查找

对于有序列表,给定查找数值,先查找列表中间位置,如果中间数值根据中间位置数值大小进行递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
int binSearch(int array[], int low, int high, int key) {  
if (low<=high) {
int mid = (low + high) / 2;
if(key == array[mid])
return mid;
else if(key < array[mid])
return binSearch(array, low, mid-1,key);
else if(key > array[mid])
return binSearch(array, mid+1, high,key);
}
else
return -1;
}

参考链接

不需要中间数据交换两个数

1
2
3
4
5
6
7
void swap(int &a, int &b) {  
if (a != b) {
a ^= b;
b ^= a;
a ^= b;
}
}

直接插入排序

每次将 第一个 待排序的数据,插入到前面已经排好序的序列之中,直到全部数据插入完成。
参考链接

直接选择排序

每次将 最小的一个 待排序的数据,插入到前面已经排好序的序列的 最后,直到全部数据插入完成。
参考链接

希尔排序

分裂原序列进行 直接插入排序,在逐渐合并子序列,直到合并成一个序列为止。
参考链接

二叉堆

  • 特性:父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值,称为最大堆(最小堆)。
  • 存储:一般都用数组来表示堆,i 结点的父结点下标就为 (i – 1) / 2。它的左右子结点下标分别为2 i + 1和2 i + 2。如第0个结点左右子结点下标分别为 1 和 2 。
  • 插入:将新数据放在数组最后,然后对二叉堆进行调整。
  • 删除:删除第一个节点,然后把最后一个节点赋值给第一个节点,调整。
    参考链接

堆排序

将首节点与末节点交换,然后调整此时的首节点到倒数第二个节点为新的二叉堆,再将首节点与倒数第二节点交换。如此往复,直到堆仅为首节点为止。
最大堆获得升序,最小堆获得降序
参考链接

快速排序

选一个基准数 x,在序列中比它小的放在它前面,比它大的放在它后面,形成 A x B (A , B 为集合)这样的分布,再对 A B 进行同样的操作,直到 A B 只包含一个元素为止。

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
26
27
def qsort(nums_list):
def qsort_exec(nums, left, right):
l = right - left + 1
if l < 2:
return
if l == 2:
if nums[left] > nums[right]:
nums[left], nums[right] = nums[right], nums[left]
return
start, end = left, right
stand = nums[start]
while start < end:
while nums[end] > stand and start < end:
end -= 1
if start < end:
nums[start] = nums[end]
start += 1
while nums[start] < stand and start < end:
start += 1
if start < end:
nums[end] = nums[start]
end -= 1
nums[start] = stand
qsort_exec(nums, left, start - 1)
qsort_exec(nums, start + 1, right)
qsort_exec(nums_list, 0, len(nums_list) - 1)
return nums_list

参考链接

归并排序

递归分解数列直至只含一个元素,然后对分解的数列进行有序合并。
参考链接

参考代码

只知道原理是不行的,很多算法需要自己写出来才有感觉,对于以上的数据结构和算法,这里 Structure 提供一部分参考代码,项目更新中,有兴趣的同学可以跟我一起完善它。

分享到