数据结构——基础

Posted on | In | Visitors:

This is my blog.
数据结构也是十分重要的，在面试中，常常会对数据结构进行考察，了解数据结构的基本原理，掌握如何使用成了一门必须掌握的课程。在本篇博客中，只会点出其优势，且只涉及acm中所需要的内容。

2019.03.19

对于面试基础知识的准备，今天开始复习数据结构部分了，同时将此篇博文进行扩展，相对于原目的acm来说，会增加一些细节部分

前言

数据结构从一般的表、树、图，到扩展的网络、集合代数论、格、关系等方面

数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；一个数据元素可由若干个数据项组成；数据项是数据的不可分割的最小单位

数据对象是性质相同的数据元素的集合，是数据的一个子集

数据结构是相互之间存在一种或多种特定关系的数据元素的集合；通常有4类基本结构：集合（同属于一个集合的关系）、线性结构（一个对一个的关系）、树形结构（一个对多个的关系）、图状结构或网状结构（多个对多个的结构）

其中$D$是数据元素的有限集，$S$是$D$上关系的有限集

数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位。用由若干数据项组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像；由此得到两种不同的存储结构：顺序存储结构（相对位置）和链式存储结构（指针）

数据类型是一个值的集合和定义在这个值集上的一组操作的总称，高级程序语言中可分为非结构的原子型（不可分解的）和结构类型（它的成分可以是非结构的，也可以是结构的）

抽象数据类型 ADT是指一个数学模型以及定义在该模型上的一组操作。分为原子类型、固定聚合类型、可变聚合类型。

其中$P$是对$D$的基本操作集

多形数据类型是指其值的成分不确定的数据类型（感觉像是模版类这种）

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；其含有5个重要特性：有穷性、确定性、可行性、输入（0个或多个）、输出（一个或多个）；算法设计的目标：正确性、可读性、健壮性（输入非法时）、效率与低存储量需求（问题规模、使用的语言、策略、机器、机器代码的质量）

一个算法是由控制结构（顺序、分支和循环）和原操作（固有数据类型的操作）构成的

渐近时间复杂度（asymptotic time complexity），简称时间复杂度，$T(n)=O(f(n))$

语句的频度是指该语句重复执行的次数

空间复杂度，$S(n)=O(f(n))$

若额外空间相对于输入数据量来说是常数，则称此算法为原地工作

线性结构

在数据元素的非空有限集合中：

  • 存在唯一的一个被称做“第一个”的数据元素“
  • 存在唯一的一个被称做”最后一个“的数据元素
  • 除第一个之外，集合中的每个数据元素均只有一个前驱
  • 除最后一个之外，集合中每个数据元素均只有一个后继

线性表

n个数据元素的有限序列

常把数据元素称为记录，含有大量记录的线性表又称文件

操作：访问、插入、删除

顺序表示

用一组地址连续的存储单元依次存储线性表的数据元素

其中$l$为存储宽度

随机存取的存储结构，但是插入或者删除操作，需移动大量元素

1
L.elem = (ELemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));

链式表示

用一组任意的存储单元（可以是连续的，也可以是不连续的）存储线性表的数据元素

数据元素$a_i$的存储映象，称为结点；它包含两个域，其中存储数据元素信息的域称为数据域；存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链

n个结点链结成一个链表，即为线性表的链式存储结构

每个结点中只包含一个指针域，故又称线性链表或单链表

整个链表的存取必须从头指针开始进行，最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）

有时，在单链表的第一个结点之前附设一个结点，称之为头结点；其数据域可以不存储任何信息，也可以存储如线性表的长度等的附加信息；这样可以使对第一个元素结点的操作与表中其他结点操作一致，对空表和非空表操作一致

$p\to next$是指向$a_i$的指针 $p\to next\to data$才是数据元素$a_i$

循环链表，表中最后一个结点的指针域指向头结点，整个链表形成一个环。

双向链表，在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱

栈

所谓栈，限定仅在表尾进行插入或删除操作的线性表，表尾端称为栈顶top，相应地表头断称为栈底bottom；不含元素的空表称为空栈；LIFO结构，后进先出。具有pop出栈、push入栈、top三种基本操作。其头文件为<stack>，用stack<int>s来声明一个栈。

顺序栈、链栈

例题：括号匹配、数值转换、迷宫求解、表达式求值、Hanoi塔问题、UVA12096

队列

（原始）队列

所谓队列，就是FIFO，先进先出。具有pop、push、front三种基本操作。其头文件为<queue>，用queue<int>s来声明一个队列。
例题：UVA540

优先队列

优先队列是一种抽象数据类型，ADT。先出队列的是队列中优先级最高的元素。具有pop、push、top三种基本操作。其头文件为<queue>,用priority_queue<int>pq来声明，在这个例子中，越小的整数优先级越低。而对于自定义类型的优先队列，可以定义一个结构体cmp，重载（）。
例如，要实现一个“个位数大的整数优先级反而小的优先队列。

1
2
3
4
5
6
struct cmp{
		bool operator() (const int a, const int b) const{
				return a%10>b%10;
		}
}
priority_queue<int,vector<int>,cmp>pq;

注 两个>>不要写在一起，编译器可能难以理解。
例题：UVA136

双端队列

双端队列，可以支持快速地在首尾两端进行插入和删除。
具有front、back、pop_front、pop_back、erase、push_front、push_back、insert三种基本操作。其头文件为<deque>，用deque<int>s来声明一个队列。
在xcode上试验了一下，结果如下：
屏幕快照 2017-09-14 下午8.35.17

循环队列

串

字符串一般简称为串，由零个或多个字符组成的有限序列

块链结构，每个结点包含固定的字符，若最后不是整数倍的用#填满，由此产生了串值的存储密度的概念

串的模式匹配

暴力法BF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Index(string s, string t, int pos) {
    int i = pos;
    int j = 1;
    while(i <= s[0] && j <= t[0]) {
        if(s[i] == t[j]) {
            i++; j++;
        }else {
            i = i - j + 2; //j-1一个匹配，本趟起始位置为i-(j-1)，所以下一趟从i-j+1+1开始
            j = 1;
        }
    }
	if(j > t[0]) return i - t[0];
    else return 0;
}

KMP算法（克努特-莫里斯-普拉特）

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
28
29
30
31
32
33
34
35
36
37
38
39
void get_next(string t, int next[]) {
  int i = 1, j = 0;
  next[1] = 0;
  while(i < t[0]) {
    if(j == 0 || t[i] == t[j]) {
      i++; j++;
      next[i] = j;
    }else {
      j = next[j];
    }
  }
}
// 上面的仍有缺陷，如模式“aaaab”和主串“aaabaaaab”，对于234的a这点不匹配的时候，那肯定也和它的next[i]不匹配，因此可以跳过，优化如下
void get_nextval(string t,int nextval[]) {
  int i = 1, j = 0;
  nextval[1] = 0;
  while(i < t[0]) {
    if(j == 0 || t[i] == t[j]) {
      i++; j++;
      if(t[i] != t[j]) nextval[i] = j;
			else nextval[i] = nextval[j];
    }else {
      j = nextval[j];
    }
  }
}
int index_KMP(string s, string t, int pos) {
  int i = pos, j = 1;
  while(i < s[0] && j <= t[0]) {
    if(j == 0 || s[i] == t[j]) {
      i++; j++;
    }else {
      j= next[j];
    }
  }
  if(j > t[0]) return i - t[0];
}

数组

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作

有以列为主序和以行为主序

若以行为主，则：

其中$c_n=L,c_{i-1}=b_i*c_i,1<i\leq n$

一旦确定了数组的各维的长度，$c_i$就是常数。由于计算各元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。称具有这一特点的存储结构为随机存储结构。

矩阵的压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间

假如值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵；反之，称为稀疏矩阵

n阶对称矩阵

我们可以行序为主序存储其下三角

对角矩阵：所有的非零元都集中在以主对角为中心的带状区域中

假设在$mn$的矩阵中，有$t$各元素不为零。则矩阵的稀疏因子$\delta=\frac{t}{mn}$

通常认为$\delta\leq 0.05$时，称为稀疏矩阵

可以只存储非零元的位置和值，也就是用一个三元组$(i,j,a_{ij})$；也可以存储每行每列有几个，第一个开始的位置；十字链表，行列的后继

广义表

与线性表不同的是，$a_i​$不仅限于单个元素，而是可以是广义表；所以有表结点和原子结点

当广义表$LS$非空时，称第一个元素$a_1$为$LS$的表头，称其余元素组成的广义表$(\alpha_2,\alpha_3,\cdot\cdot\cdot,\alpha_n)$是$LS$的表尾

列表可以为其他列表所共享，也可以递归自己

表头可以是单个元素，也可以是列表；表尾一定是列表

树型结构

树是以分支关系定义的层次结构；树是$n(0\leq n)$个结点的有限集

结点

度：结点拥有的子树数称为结点的度

叶子/终端结点：度为0的结点

分支结点/非终端结点：度不为0的结点（除根结点之外，分支结点也称为内部结点）

树的度：树内各结点的度的最大值

孩子：结点的子树的根（相应地，该结点称为孩子的双亲）

兄弟：同一双亲的孩子之间互称兄弟

堂兄弟：其双亲在同一层的结点互为堂兄弟

层次：结点的层次从根开始定义起

深度/高度：树中结点的最大层次

有序树/无序数

森林：$m(0\leq m)$棵互不相交的树的集合（双亲表示法、孩子表示法、孩子兄弟表示法）

森林$\to$二叉树，孩子左结点，兄弟右节点

二叉树

有序树

递归的定义为：二叉树要么为空，要么由根结点、左子树和右子树组成，而左子树和右子树又分别是一颗二叉树。

基本性质

一般所要用的知识，即：其余规律，可以参考数据结构的书本。

  • 第$i$层上至多有$2^{i-1}$个结点$(1\leq i)$
  • 深度为$k$的二叉树至多有$2^k-1$个结点$(1\leq k)$
  • 对任何一棵二叉树$T$，如果其终端结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$
    • 因为$n_0+n_1+n_2=n_0=n_1+2*n_2+1$

特殊的二叉树：满二叉树、完全二叉树（满二叉树一定是完全二叉树）

完全二叉树的性质：

  • 具有n个结点的完全二叉树的深度为$\lfloor log_2 n \rfloor + 1$
  • 左结点 $2k$；右结点 $2k+1$；双亲$\lfloor i/2 \rfloor$

顺序存储：适合完全二叉树

链式存储：

  • 二叉链表（左右孩子指针、数据域）
  • 三叉链表（增加双亲指针）
  • 线索二叉树
    • 若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱
    • 若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继
    • 增加两个标志域
    • 指向前驱后继的指针，称为线索

注 在用内存申请的方法下建树时，勿忘释放空间。
当然在acm中，为了避免指针的出现，我们可以开两个数组，left和right。若是编号跳跃性，则可以定义一个结构体。

遍历方式

先序遍历：DLR 波兰式
中序遍历：LDR
后序遍历：LRD 逆波兰式
层次遍历
这里的序，都是参照根来的。以此衍生出来的题目，有给你两个遍历方式，推出另一种遍历方式，当然，不是任意两种遍历方式都可以的。一般考察的是先序+中序->后序；中序+后续->先序；中序+层次->后序。主要掌握遍历规则，再配合queue和stack应该就能做出来了。

刚学数据结构的时候，做了好多题，好久没碰，就来一发吧！

例题：UVA 548

题意：

给定中序和后序遍历，找一个叶子使得它到根的路径上的权和最小。如果有多解，该叶子本身的权应尽量小。权值各不相同，且都是小于10000的正整数。
首先我们就需要根据中序和后序遍历，建树。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
const int maxn=10000+10;
int in_order[maxn],post_order[maxn],lch[maxn],rch[maxn];
int n;
bool read_list(int *a){
    string line;
    if(!getline(cin,line))return false;
    stringstream ss(line);
    n=0;
    int x;
    while(ss>>x)a[n++]=x;
    return n>0;
}
int build(int L1,int R1,int L2,int R2){
    if(L1>R1) return 0;
    int root=post_order[R2];
    int p=L1;
    while(in_order[p]!=root)p++;
    int cnt=p-L1;
    lch[root]=build(L1,p-1,L2,L2+cnt-1);
    rch[root]=build(p+1,R1,L2+cnt,R2-1);
    return root;
}
int best,best_sum;
void dfs(int u,int sum){
    sum+=u;
    if(!lch[u]&&!rch[u]){
        if(sum<best_sum||(sum==best_sum&&u<best)){
            best=u;
            best_sum=sum;
        }
    }
    if(lch[u]) dfs(lch[u],sum);
    if(rch[u]) dfs(rch[u],sum);
}
int main() {
    while(read_list(in_order)){
        read_list(post_order);
        build(0, n-1, 0, n-1);
        best_sum=1e9;
        dfs(post_order[n-1], 0);
        cout<<best<<endl;
    }
    return 0;
}

此代码稍微改一改就是我数据结构机考的一题咯！（时隔两年的自己：好傻啊，这孩子(-.-)）

哈夫曼树/最优树/赫夫曼树

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度；树的路径长度是从树根到每一个结点的路径长度之和，通常记为$WPL=\displaystyle\sum^n_{k=1}w_kl_k$

其中WPL最小的二叉树称作哈夫曼树

建立：每一个结点，作为带权值的左右子树均为空的树，然后就是每次取最小，同时设置根的权值为其左右孩子的权值之和，从集合中删除取得两个树，直到剩下一颗树为止

编码：左右用10区分

若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码

图

顶点：数据元素

$V$是顶点的有穷非空集合；$VR$是两个顶点之间的关系的集合

若$\in VR$，则$$表示从$v$到$w$的一条弧，且$v$为弧尾或初始点，$w$为弧头或终端点，此时的图称为有向图

若$\in VR$必有$\in VR$，即$VR$是对称的，则以无序对$(v,w)$代替这两个有序对，表示$v$和$w$之间的一条边，此时的图称为无向图

我们用$n$表示图中顶点数目，用$e$表示边或弧的数目

对于无向图，e的取值范围为$0$到$\frac 1 2n(n-1)$，有$\frac 1 2n(n-1)$条边的无向图称为完全图

对于有图，e的取值范围为$0$到$n(n-1)$，有$n(n-1)$条弧的有向图称为有向完全图

有很少条边或弧（如$e<nlogn​$）的图称为稀疏图，反之称为稠密图

与图的边或弧具有与它相关的数叫做权，带权的图通常称为网

子图

邻接点：一条边的两个顶点的互称 （边）依附（两个顶点），或者说它们边和两个顶点相关联

度 入度 出度

路径 回路/环 简单路径（顶点不重复）

无向图：连通图 连通分量

有向图：强连通图 强连通分量

关节点（删去此点后一个连通分量分割成两个或两个以上的连通分量）【若生成树的根有两个及以上的子树，则根结点必是关节点）

求关节点：

$visited[v]$即为$v$在深度优先生成树的前序序列中的序号

$low[v]$可由后续遍历深度优先生成树求得

其中，$w$是顶点$v$在深度优先生成树上的孩子结点，$k$是顶点$v$在深度优先生成树上的祖先结点

若对于某个结点，存在孩子结点$w$且$visited[v] \leq low[w]$，则该顶点$v$必为关节点。因为当$w$是$v$的孩子结点时，$visited[v]\leq low[w]$，表明$w$及其子孙均无指向$v$的祖先的回边

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
28
29
void FindArticul(AlGraph G) {
  count = 1;
  visited[0] = 1;
  for(int i = 1; i < G.vexnum; i++) { visited[i] = 0; }
  p = G.vertices[0].firstarc;
  v = p -> adjvex;
  DFSArticul(G, v);
  if(count < G.vexnum) {
    printf(0, G.vertices[0].data);
    while(p -> nextarc) {
      p = p -> nextarc;
      v = p -> adjvex;
      if(visited[v] == 0) DFSArticul(g, v);
    }
  }
}
void DFSArticul(ALGraph G, int v0) {
  visited[v0] = min = ++count;
  for(p = G.vertices[v0].first; p; p = p -> nextarc) {
    w = p -> adjvex;
    if(visited[w] == 0) {
      DFSArticul(G, w);
      if(low[w] < min) min = low[w];
      if(low[w] >= visited[v0]) printf(v0, G.vertices[v0].data);
    }else if(visited[w] < min) min = visited[w];
  }
  low[v0] = min;
}

重连通图：一个没有关节点的连通图

若在连通图上至少删去k个顶点才能破坏图的连通性，则称此图的连通度为k

存储方式：数组表示法、邻接表（每个结点到其他结点若有边或弧则加入到这个结点的链中）、十字链表（增加弧尾、弧头、弧头相同的下一条弧的信息）、邻接多重链表（增加是否被搜索过）

遍历

深度优先搜索：矩阵$O(n^2)$、邻接表$O(n+e)$

广度优先搜索：时间复杂度相同，只是对顶点访问的顺序不同

无向图由遍历产生生成树

最小生成树

构造连通网的最小代价生成树（简称最小生成树）的问题

Prim

在点集合中寻找以此点开始的最小的边，同时另一个点不在集合中，将这条边加入边集合，将另一个点加入点集合

$O(n^2)$，适用于边稠密的网

Kruskal

每次加入最小的边，且加入这条边不会构成回路

$O(eloge)$

DAG

有向无环图

拓扑排序

偏序：集合中只有部分元素之间可以比较

全序：集合中的任两个元素之间都可以比较

拓扑排序：由偏序定义得到拓扑有序的操作

  • 方法：
    1. 在有向图中选一个没有前驱的顶点且输出之
    2. 从图中删除该结点和所有以它为尾的弧

直至结点全部输出，或者当前图中不存在无前驱的顶点为止（存在环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
status TopologicalSort(ALGraph G) {
  FindInDegree(G, indegree);	//求各顶点的度, O(e)
  InitStack(S);
  for(int i = 0; i < G.vexnum; i++) {	// O(n)
    if(!indegree[i]) Push(S, i);
  }
  count = 0;
  while(!StackEmpty(S)) {
    Pop(S, i);
    printf(i, G.vertices[i].data);
    count++;
    for(p = G.vertices[i].firstarc; p; p = p -> nextarc) {
      k = p -> adjvex;
      if(!(-- indegree[k])) Push(S, k);
    }
  }
  if(count < G.vernum) return ERROR;
  else return OK;
}

时间复杂度分析：每个顶点进栈一次，出栈一次，入度减一的操作在$while$语句中执行$e$次，所以总的时间复杂度$O(n+e)$

AOV-网

用顶点表示活动，用弧表示活动间的有限关系的有向图称为顶点表示活动的网（不存在环，即自己不可以以自己为先决条件）

AOE-网

顶点表示事件，边表示活动的带权（持续时间）的有向无环网

在正常情况下，网中只有一个入度为零的点（称作源点）和一个出度为零的点（称作汇点）

AOE研究的问题是完成整项工程所需要的时间，以及哪些活动是影响工程进度的关键

关键路径：路径长度最长的路径

$e(i)$表示活动$a_i$的最早开始时间 $l(i)$表示活动$a_i$最晚开始的时间

关键活动：$e(i) = l(i)$

首先拓扑正序，求出最早开始时间，同时对于存在环的情况作出出错处理，然后拓扑逆序，求出最晚开始时间，并同时输出关键活动

最短路径

  1. 从某个源点到其余各顶点的最短路径

    Dijkstra$O(n^2)$

    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
    28
    29
    30
    31
    32
    33
    34
    void Dijkstra(MGraph G, int v0, PathMatrix &P, ShortPathTable &D) {
      //P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点
      for(int v = 0; v < G.vexnum; v++) {
        final[v] = false;
        D[v] = G.arcs[v0][v];
        for(int w = 0; w < G.vexnum; w++) { P[v][w] = false; }
        if(D[v] < INFINITY) {
          P[v][v0] = true;
          P[v][v] = true;
        }
      }
      D[v0] = 0; final[v0] = true;
      
      
      for(int i = 1; i < G.vexnum; i++) {
        min = INFINITY;
        for(int w = 0; w < G.vexnum; w++) {
          if(!final[w]) {
            if(D[w] < min) {
              v = w; min = D[w];
            }
          }
        }
        
        final[v] = true;
        for(int w = 0; w < G.vexnum; w++) {
          if(!final[w] && (min + G.arcs[v][w] < D[w])) {
            D[w] = min + G.arcs[v][w];
            P[w] = P[v];
            P[w][w] = true;
          }
        }
      }
    }

  2. 每一对顶点之间的最短路径

    Floyd$O(n^3)$

    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
    28
    void Floyd(MGraph G, PathMatrix &P[], DistancMatrix &D) {
      //P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点
      for(int v = 0; v < G.vexnum; v++) {
        for(int w = 0; w < G.vexnum; w++) {
          D[v][w] = G.arcs[v][w];
          for(int u = 0; u < G.vexnum; u++) {
            P[v][w][u] = false;
          }
          if(D[v][w] < INFINITY) {
            P[v][w][v] = true;
            P[v][w][w] = true;
          }
        }
      }
      
     	for(int u = 0; u < G.vexnum; u++) {
        for(int v = 0; v < G.vexnum; v++) {
          for(int w = 0; w < G.vexnum; w++) {
            if(D[v][u] + D[u][w] < D[v][w]) {
              D[v][w] = D[v][u] + D[u][w];
              for(int i = 0; i < G.vexnum; i++) {
                P[v][w][i] = P[v][u][i] || P[u][w][i];
              }
            }
          }
        }
      }
    }

动态存储管理

空间表结构：

  1. 每次分配大小相同
  2. 分配块有若干种规格
  3. 分配块大小不固定

分配策略：

  1. 首次拟合法
  2. 最佳拟合法
  3. 最差拟合法

伙伴系统：

占用块和空闲块的大小都是2的k次幂

查找

关键字（可以标识一个数据元素） 主关键字（唯一）

  • 静态查找表

    • 顺序查找
    • 折半查找（有序的情况下）
    • 分块查找（又称索引顺序查找）
      • 最大关键字和指针

  • 动态查找表（元素会改变）

    • 二叉排序树/二叉查找树BST（左结点<根<右节点）

      • 中序遍历，可得到有序序列

      • 删除结点的时候

        • 叶子，直接删除

        • 若只含有左子树或只含有右子树，则让它的孩子继承它所在的位置即可

        • 含有左右孩子的时候

          • 直接前驱（直接后继）代替它
          • 让左子树代替，然后让右子树作为左子树的右子树
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          18
          19
          20
          21
          status Delete(BiTree &p) {
            if(!p -> rchild) {
              q = p;
              p = p -> lchild;
              free(q);
            }else if(!p -> lchild) {
              q = p;
              p = p -> rchild;
              free(q);
            }else{
              q = p;
              s = p -> lchild;
              while(s -> rchild) {
                q = s;
                s = s -> rchild;	//	找直接前驱
              }
              p -> data = s -> data;
              if(q != p) q -> rchild = s -> lchild;
              else q -> lchild = s -> lchild;
            }
          }

    • 平衡二叉树AVL（左右子树的深度差的绝对值不超过1）

      • 建立：四种（右，左，右左，左右）

    • B-树（平衡多路查找树，文件系统中，不太熟）

      • m阶B-树或为空树或需满足：
        • 树中每个结点至多有m棵子树
        • 若根结点不是叶子结点，则至少有2棵子树
        • 除根之外的所有非终端结点至少有$\lceil m/2 \rceil$棵子树
        • 所有的非终端结点需包含以下信息
          • $(n, A_0,K_1,A_1,K_2,A_2,\cdot\cdot\cdot,K_n,A_n)$
          • $K_i$为关键字，且$K_i<K_{i+1}$
          • $A_i$为指向子树根结点的指针，且指针$A_{i-1}$所指子树中所有结点的关键字均小于$K_i$，$A_{n}$所指子树中所有结点的关键字均大于$K_n$
        • 所有的叶子结点都出现在同一层次上，并且不带信息

    • B+树（不太熟，很像目录树）

      • 是一种B-树的变种
      • 两种m阶的差异：
        • 有n棵子树的结点中含有n个关键字
        • 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
        • 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字

    • 键树/数字查找树

      • 内部结点可以是字母
      • 两种存储结构：孩子兄弟链表、树的多重链表

    • 哈希表/散列表

      • 存储位置和关键字之间建立一个确立关系：哈希函数
        • 直接定址法
        • 数字分析法：取关键字的若干数位
        • 平方取中法：取平方后的中间几位
        • 折叠法：分割成数位相同的部分（除最后一部分），然后叠加和
        • 除留余数法：取余
      • 解决冲突的方法：
        • 开放地址法：$H_i=(H(key) + d_i)\ MOD\ m\ i=1,2,\cdot\cdot\cdot,k\ (k\leq m-1)$
          • 线性探测再散列 $d_i=1,2,3,\cdot\cdot\cdot,m-1​$
          • 二次探测再散列 $d_i=1^2,-1^2,2^2,-2^2,3^3,\cdot\cdot\cdot,k^2,-k^2(k\leq m/2)​$
          • 伪随机探测再散列
        • 再哈希法 $H_i=RH_i(key)$
          • $RH_i$均是不同的哈希函数
        • 链地址法：关键字相同的存储在同一链表中
        • 建立公共溢出区

排序

  • 外部排序
  • 内部排序
    • 插入排序：每次插入1个到已排好的队列中
      • 直接插入排序：一个一个比较，同时移位
      • 折半插入排序：在插入寻找位置的时候用二分的办法
      • 2-路插入排序：first指针和final指针，一个变小一个变大
      • 表插入排序：一个key域，一个next域（下一个的下标位置）
      • 希尔排序：每次不同间隔的序列排序（间隔从大缩小）
    • 交换排序
      • 起泡排序/冒泡排序Bubble sort
        • 每次将目前最大的元素放到最后，若是这一组没有交换的动作或者已是最后一组，则停止
      • 快速排序
        • 每次寻找一个枢轴，然后划分成左右两部分，递归排序
    • 选择排序：每一趟在$n-i+1\ (i=1,2,\cdot\cdot\cdot,n-1)$个记录中选取关键字最小的记录作为有序序列中第$i$个记录
      • 简单选择排序
      • 树型选择排序/锦标赛排序
        • 每次两两比较，如此重复
      • 堆排序（大小顶堆）
        • 建堆：从$\lfloor n/2\rfloor$个元素开始，或是每次加入一个元素重复调整堆
        • 调整：每次和左右孩子比较，若不对，交换并接下来继续比较，直到正确为止
    • 归并排序：将两个或两个以上的有序表组合成一个新的有序表
      • 2-路归并排序：每次两组归并排序
    • 基数排序：多关键字排序
      • MSD：最高位优先
      • LSD：最低位优先（卡片机）
  • 稳定
    • 归并排序
    • 基数排序
  • 不稳定
    • 快速排序
    • 堆排序
    • 希尔排序

其他

STL也是需要进行测试的，虽说STL经过多人的完善，但毕竟是人写的（ 是神啊！），同时也是为了测试之后能更好地了解库的用法和优缺点。
在测试的时候我们可以使用cstdlib中的rand()函数，当然在使用之前需要随机种子srand（一次就够喽）,可以产生[0,RAND_max]内的随机整数，一般来说为2^15-1=32767，如果要在n范围内，可以模n+1。我们还可以使用assert()宏，其作用是，当表达式为真时，无变化，但为假时，终止程序，并且给出错误提示。

注 本文参考刘汝佳的《算法入门经典》。
最后叮嘱一句哦，对于学习数据结构的同学来说，不要在学习时就使用STL，还是需要掌握一下内在构造，当然在机考时，建议使用STL，毕竟可以省代码，还不容易出错。

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽