数据结构

First Post:

2022-12-23

Last Update:

2023-11-21

线性表

顺序表

单链表

数组模拟：

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int e[N], ne[N], head, idx;

//对链表进行初始化
void init() {
    head = -1;//最开始的时候，链表的头节点要指向-1，
    //为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束
    /*
    插句题外话，我个人认为head其实就是一个指针，是一个特殊的指针罢了。
    刚开始的时候它负责指向空结点，在链表里有元素的时候，它变成了一个指向第一个元素的指针

    当它在初始化的时候指向-1，来表示链表里没有内容。
    */
    idx = 0;//idx在我看来扮演两个角色，第一个是在一开始的时候，作为链表的下标，让我们好找
    //第二在链表进行各种插入，删除等操作的时候，作为一个临时的辅助性的所要操作的元素的下
    //标来帮助操作。并且是在每一次插入操作的时候，给插入元素一个下标，给他一个窝，感动！
    /*
    再次插句话，虽然我们在进行各种操作的时候，元素所在的下标看上去很乱，但是当我们访问的
    时候，是靠着指针，也就是靠ne[]来访问的，这样下标乱，也就我们要做的事不相关了。
    另外，我们遍历链表的时候也是这样，靠的是ne[]
    */

}
//将x插入到头节点上
void int_to_head(int x) {//和链表中间插入的区别就在于它有head头节点
    e[idx] = x;//第一步，先将值放进去
    ne[idx] = head;//head作为一个指针指向空节点，现在ne[idx] = head;做这把交椅的人换了
    //先在只是做到了第一步，将元素x的指针指向了head原本指向的
    head = idx;//head现在表示指向第一个元素了，它不在是空指针了。（不指向空气了）
    idx++;//指针向下移一位，为下一次插入元素做准备。
}
//e[idx]=x;
// ne[idx]=head;
// head=idx;
// idx++;
//将x插入到下标为k的点的后面
void add(int k, int x) {
    e[idx] = x;//先将元素插进去    e[idx]=x;ne[idx]=ne[k];ne[k]=idx;idx++;
    ne[idx] = ne[k];//让元素x配套的指针，指向它要占位的元素的下一个位置
    ne[k] = idx;//让原来元素的指针指向自己
    idx++;//将idx向后挪

}

//将下标是k的点后面的点个删掉
void remove(int k) {
    ne[k] = ne[ne[k]];//让k的指针指向，k下一个人的下一个人，那中间的那位就被挤掉了。
}
//ne[k]=ne[ne[k]]//传进来的是k-1
int main() {
    cin >> n;
    init();//初始化
    for (int i = 0; i < n; i++) 
    {
        char s;
        cin >> s;
        if (s == 'H') {
            int x;
            cin >> x;
            int_to_head(x);
        }
        if (s == 'D') {
            int k;
            cin >> k;
            if (k == 0) head = ne[head];//删除头节点
            else remove(k - 1);//注意删除第k个输入后面的数，那函数里放的是下标，k要减去1
        }
        if (s == 'I') {
            int k, x;
            cin >> k >> x;
            add(k - 1, x);//同样的，第k个数，和下标不同，所以要减1
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
    
    return 0;

}

双链表

指针域存下一个和上一个的地址

循环链表

头指尾，尾指头呗

静态链表

使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。

可以融合顺序表和链表各自的优点，从而既能快速访问元素，又能快速增加或删除数据元素。

栈

先进后出

应用：

括号匹配

表达式求值（中缀转后缀/前缀）

队列

先进先出

数组模拟：

我觉得是一个双指针在维护这个数据结构吧
先进的先出后进的后出
tt就是维护队尾位置的下标
如果要队头出列的话 hh++就可以遍历的时候i<=hh就可以了（输出时候队头开始遍历）

#include<iostream>
#include <string>
using namespace std;
const int N = 1e6 + 10;
int qu[N], hh = 0, tt = -1;//初始化很重要！！！
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        string a;
        cin >> a;
        if (a == "push")
            cin >> x, qu[++tt] = x;//元素只能队尾入队
        else if (a == "pop")
            hh++;//注意元素只能队头弹出，且是 ++
        else if (a == "empty")//队内是否为空
        {
            if (tt < hh)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;

        }
        else//查询队头
            cout << qu[hh] << endl;
    }
     
    for (int i = tt; i <= hh; i++)
    {
        printf("%d", qu[i]);
    }
    
    return 0;

}

双端队列

两端都可以出和进

循环队列

圈圈

应用：

bfs

字符串

KMP算法

匹配字符串的一种优化

原始匹配方法缺点：当字串能够与主串部分匹配时，主串的扫描指针i会经常回溯，最坏时间复杂度为O(mn)

kmp算法：当字串能够与主串部分匹配时，不再让主串的指令i回溯，而是让字串的j指针回溯到j=next[j]的位置，算法平均时间复杂度O(m+n)

那么关键就在于如何求解next数组了，手算的方法就是在该位置前的串的最长相等前后缀长度+1，特别的 next[1]=0 next[2]=1

eg：ababaa 在j=6时：最长前后缀aba 所以next[6]=4;

在j=5时：最长前后缀ab 所以 next[5]=3;

也可以看出如果匹配过程中很少出现可以部分匹配的情况，kmp算法和朴素匹配也差不多

初始化：

typedef struct s {
	char ch[1024];
	int length;
}sstring;

KMP算法：

int KMP(sstring s, sstring t)
{
	int i = 1;
	int j = 1;
	int next[1024];
	Get_next(t, next);
	while (i <= s.length && j <= t.length)
	{
		if (j == 0 || s.ch[i] == t.ch[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j > t.length)
	{
		return i - t.length;
	}
	else
		return 0;
}

求解next数组：（这有两个公式）

void Get_next(sstring t,int next[])
{
	int i=1,j=0;
	next[1] = 0;
	while (i < t.length)
	{
		if (j == 0 || t.ch[i] == t.ch[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}

优化求解next：

int nextval[1024];
nextval[1]=0;
for(int j=2;j<t.length;j++)
{
    if(t.ch[next[j]]==t.ch[j])
    {
        nextval[j]=nextval[next[j]];
    }
    else
        nextval[j]=next[j];
}

eg： a b a b a a

序号j 1 2 3 4 5 6

next: 0 1 1 2 3 4

nextval： 0 1 0 1 0 4

从第二个开始，b与其对应的next[2]=1即a比较，不相同，那么保持不动；

第三个a与其next[3]=1即a比较，相同，那么将他的nextval改为前面的next的值，就是循环里的else

以此类推

树

二叉树的存储

顺序存储（满二叉树）

从左到右，由上至下依次将结点存入一个顺序表中，（由1开始）有以下性质：

左儿子：i*2；

右儿子：i*2+1；

父节点：i/2；

struct TreeNode {
	int value;
	bool isEmpty;
};
TreeNode t[100];
for (int i = 0; i < 100; i++)
{
	t[i].isEmpty = true;
}

链式存储

当一颗二叉树不是满二叉树时，如果继续顺序存储，那么他们的下标将变得无序，若是强制补全二叉树（完全二叉树）再来存，那么可能会浪费很多空间，所以采用链式存储的方式：

struct BiTNode{
    int value;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
};

二叉树的遍历

先序遍历

根左右

void Preorder(BiTree T)
{
    if(T!=NULL)
    {
        visit(T);
        Preorder(T->lchild);//递归遍历左子树
        Preorder(T->rchild);//递归遍历右子树
    }
}

中序遍历

左根右

后序遍历

左右根

（这三种就是那三句的顺序变一下就ok）

层序遍历

一层一层遍历

利用一个队列来实现，有种bfs的感觉

线索二叉树

存储

struct BiTNode{
    int value;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
    int ltag,rtag //tag==0 表示指向儿子 ==1 表示指向线索
};

二叉排序树

左子树结点值<根结点值<右子树结点值

在二叉排序树上寻找值为key的结点

BSTNode* BST_Searchh(BSTree T,int k)
{
    while(k!=NULL && k!=T->key)
    {
        if(k<T->key)   T=T->lchild;
        else   T=T->rchild;
    }
    return T;
}

平衡二叉树（AVL树）

任意节点的子树的高度差都小于等于 1

用于解决二叉排序树高度不确定的情况，如果二叉排序树的子树间的高度相差太大，就会让二叉排序树操作的时间复杂度升级为O(n)，为了避免这一情况，为最坏的情况做准备，就出现了平衡二叉树，使树的高度尽可能的小，其本质还是一棵二叉搜索树。

哈夫曼树

路径：指从根结点到该结点的分支序列。
路径长度：指根结点到该结点所经过的分支数目。
结点的带权路径长度：从树根到某一结点的路径长度与该结点的权的乘积。
树的带权路径长度(WPL)：树中从根到所有叶子结点的各个带权路径长度之和。

哈夫曼树是由 n 个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树，又称最优二叉树。

构造方法：每次找最小的两个权值先组成一棵树，这颗树的权值就是两棵树权值的和。循环这个过程。

哈夫曼编码

是一种可变长编码（ VLC）方式，比起定长编码的 ASCII 编码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的。

出现频率为权值，编码方式就是上面构造哈夫曼树的方式，可以使WPL最小（电报）

普通树

普通树存储

双亲表示法（顺序存储）

每个结点的指针指向父亲结点

优点：找父节点方便

缺点：找儿子结点不方便

孩子表示法（顺序＋链式存储）

每个结点的指针指向儿子结点

优点：找儿子节点方便

缺点：找父节点不方便

孩子兄弟表示法（链式存储）

两个指针分别存左孩子和（左孩子的）右兄弟的指针

应用：树和二叉树的相互转换；森林和二叉树的相互转换

普通树的遍历

原理就是二叉树那样遍历的，没有了中序遍历，还剩三种

森林

遍历

先序遍历

等效于依次对子树进行先序遍历

中序遍历

等效于依次对子树进行后序遍历注意是后序

图

概念

有向图

无向图

简单图

不存在重边，不存在顶点到自身的边

多重图

某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联

多重图的定义和简单图是相对的

完全图（也称简单完全图）

对于无向图：有n ( n − 1 ) / 2 条边的无向图称为完全图，即每两个点间均有边的图

对于有向图：有n ( n − 1 ) 条弧的有向图称为有向完全图，即在有向完全图中任意两个顶点之间都存在方向相反的两条弧

连通图

无向图中：若图中任意两个顶点都是连通的，则称图为连通图，否则称为非连通图。

连通分量

无向图中的极大连通子图称为连通分量。

极大连通子图：子图必须连通，并且包含尽可能多的顶点和边

若一个图有n 个顶点，并且边数小于n − 1，则此图必是非连通图。

强连通图

有向图中：若从顶点v 到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通的

强连通分量

有向图中的极大强连通子图称为有向图的强连通分量

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。（边要尽可能少，并要保持连通）

n个顶点n-1条边

生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林

稀疏图稠密图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。

顶点的度入度出度

图中每个顶点的度定义为以该项点为一个端点的边的数目

无向图中：顶点的度就是该顶点上边的数量

有向图中：顶点的度分为入度和出度，入度：指向该顶点的有向边；出度：该顶点指别人的有向边。该点的度为入度和出度的和

图的存储

邻接矩阵

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息

适用于稠密图

邻接表

指对图G中的每个顶点v 建立一个单链表，第i个单链表中的结点表示依附于顶点vi 的边(对于有向图则是以顶点vi为尾的弧)，这个单链表就称为顶点vi 的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表）

例：

适用于稀疏图

十字链表（存储有向图）

邻接多重表（存储无向图）

搜索

DFS

一条路走到黑，不能走就回溯

BFS

类似于层序遍历，利用一个队列来实现。

在DFS中关键点是递归以及回溯，在BFS中，关键点则是状态的选取和标记

搜索比较简单，例题在算法模块有，不细写了

最小生成树

Prim

初始时从图中任取一顶点，如顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。

通俗点说就是：从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当做一个整体或者一个点看待，然后重复“找最短的边并添加”的操作

Kruskal

与Prim算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

初始时为只有n个顶点而无边的非连通图，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。

最短路径

BFS算法

适用于无权图的单源最短路径

就是简单的搜索一遍，搜的过程中可以用一个path数组存路径

Dijkstra算法

适用于无负权图

Dijkstra算法是解决单源最短路径问题的贪心算法
它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径
直到求出从源点到其他各个顶点的最短路径。

Floyd算法

适用于无负权环图

Floyd算法核心利用动态规划，核心就是关于中转点的引入是否会引起最短路径变化

//核心部分 
    //k为中间点 
    for(k = 0; k < n; k++)//中间点
    {
        for(v = 0 ; v < n; v++)//邻接矩阵的行列遍历
        {
            for(w =0; w < n; w++)
            {
                if(D[v][w] > (D[v][k] + D[k][w]))
                {
                    D[v][w] = D[v][k] + D[k][w];//更新最小路径 
                    P[v][w] = P[v][k];//更新最小路径中间顶点 
                }
            }
        }
    }

拓扑排序

适用于有向无环图，也可以判断一个图是否为有向无环图

AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网

bool TopologicalSort(Graph G)
{
    InitStack(S);//初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++)
    {
        if(indegree[i]==0)
            Push(S,i);//将所有入度为0的顶点入栈
    }
    int cnt=0;//记录已经输出的顶点数
    while(!IsEmpty(S))
    {
        Pop(S,i);//栈顶出栈
        print[cnt++]=i;
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)//将所有i指向的顶点入度减1，并将所有入度减为0的顶点压入栈
        {
            v=p->adjvex;
            if(!(--indegree[v])
               Push(S,v);//入度为0，则入栈
        }
    }
    if(cnt<G.vexnum)
               return false;//排序失败，有回路
    else
               return true;//成功
               
}

查找

顺序查找

额，没啥说的

二分查找

有序序列

#include <iostream>
using namespace std;
int main()
{
	int n, num[105], targe;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> num[i];
	}
	cin >> targe;
	int l = 0, r = n - 1;

	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (num[mid] == targe)
		{
			cout << targe << "in index" << mid << endl;
			return 0;
		}
		if (num[mid] < targe)
		{
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << "no" << endl;
	return 0;
}

分块查找

对数据进行分块处理，每一块对应一个索引，实现块内无序，块间有序。

在查找的时候，可以先用二分来找目标元素所对应的块间，再找块间对应的块内元素。

B树

B树和AVL树(平衡二叉树) 的差别就是 B树属于多叉树，又名平衡多路查找树，即一个结点的查找路径不止左、右两个，而是有多个。

B+树

B+树内部有两种结点，一种是索引结点，一种是叶子结点。
B+树的索引结点并不会保存记录，只用于索引，所有的数据都保存在B+树的叶子结点中。而B树则是所有结点都会保存数据。
B+树的叶子结点都会被连成一条链表。叶子本身按索引值的大小从小到大进行排序。即这条链表是从小到大的。多了条链表方便范围查找数据。
B树的所有索引值是不会重复的，而B+树非叶子结点的索引值最终一定会全部出现在叶子结点中

散列表查找（哈希表）

对于冲突，有两种方法，一种是拉链法，另一种是开放定址法，其中开放定址法又分为三种：线性探测法，平方探测法，伪随机序列法。

理论上哈希值设置的越大，查找效率就是o（1），是一种以空间换时间的查找

排序

稳定性

相同关键字在排序后相对位置保持不变为稳定的，反之不稳定

稳定排序：插入、冒泡、基数、归并

不稳定排序：希尔、选择、快排、堆

插入排序

void InsertSort(int A[],int n)
{
    int i,j,tmp;
    for(int i=1;i<n;i++)
    {
        if(A[i]<A[i-1])  //如果这个数比前面的数小
        {
            tmp=A[i];//暂存这个值
            for(j=i-1;j>=0&&A[j]>tmp;j--)//把前面大于该数的值依次往后移
            {
                A[j+1]=A[j];
            }
            A[j+1]=tmp;//把这个值插进去
        }
    }
}

有一个优化就是找该值插入的位置可以用二分，因为前面都是有序的

冒泡排序

不说了

基数排序

是一种非比较的算法

例：原始数据：520 211 438 888 007 111 985 666 996 233 168

创建十个队列（0-9）

先按个位依次存入各个数据（分配）

收集：438 888 168 007 666 996 985 233 211 111 520 （个位由大到小）

再按十位进行分配和收集：996 888 985168 666 438 233 520 211 111 007 （十位由大到小，并且十位相同的，个位大的在前）

再按百位进行分配和收集：996 985 888 666 520 438 233 211 168 111 007 （排序完成）

归并排序

#include <iostream>
using namespace std;
const int N = 100010;
int B[N];
int A[N]={5,4,7,2,1,6,8,3,9,10};

void Merge(int A[], int low, int mid, int high)
{
	int i, j, k;
	for (k = low; k <= high; k++)
	{
		B[k] = A[k];//B数组是一个tmp，先把A数组此时元素对应的拷贝一份
	}
	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)//注意i,j,k三个指针
	{
		if (B[i] <= B[j]) A[k] = B[i++];
		else  A[k] = B[j++];
	}
	while (i <= mid) A[k++] = B[i++];//剩下的直接放进去
	while (j <= high) A[k++] = B[j++];
}

void MergeSort(int A[], int low, int high)
{
	if (low < high)
	{
		int mid = (low + high) >> 1;
		MergeSort(A, low, mid);//递归处理左右两边，直到只剩一个元素
		MergeSort(A, mid + 1, high);
		Merge(A, low, mid, high);//归并
	}
}
int main(void)
{
	MergeSort(A, 0, 9);
	
	return 0;
}

希尔排序

分组加插入排序的循环，循环过程是归并递归的思路…..

#include <iostream>
using namespace std;

void ShellSort(int* arr, int n)
{
	int d = n;
	while (d > 1)
	{
		//每次对d折半操作
		d = d / 2;
		//单趟排序
		for (int i = 0; i < n - d; ++i)
		{
			int end = i;
			int tem = arr[end + d];
			while (end >= 0)
			{
				if (tem < arr[end])
				{
					arr[end + d] = arr[end];
					end -= d;
				}
				else
				{
					break;
				}
			}
			arr[end + d] = tem;
		}
	}
}

int main()
{
	int A[10] = { 4,5,6,7,8,9,0,1,2,3 };
	ShellSort(A, 10);

	return 0;
}

快速排序

一种分治的思想

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n, i, j;
int q[N];
void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;

	int x = q[(l+r)/2]; //随意选择一个基准元素
    i = l - 1; 
    j = r + 1;
while (i<j)
{
	do i++; while (q[i] < x);
	do j--; while (q[j] > x);
	if (i<j) swap(q[i], q[j]);
}
quick_sort(q, l, j);//递归处理左边
quick_sort(q, j + 1, r);//递归处理右边

}

int main()
{
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &q[i]);
	}
	quick_sort(q, 0, n - 1);
	for (i = 0; i < n; i++)
	{
		printf("%d", q[i]);
	}
	return 0;
}

简单选择排序

真的很简单呐

每一趟在待排序元素中选取关键字最小的加入有序序列

void SelectSort(int A[],int n)
{
    for(int i=0;i<n-1;i++)
    {
        int min=i;
        for(int j+1;j<n;j++)//找最小元素
        {
            if(A[j]<A[min]) min=j;
        }
        if(min!=i) swap(A[i],A[min]);
    }
}

堆排序

选择排序的一种

先将初始序列变为大根堆的存储，再进行排序并维持这个堆：

void BuildMaxHeap(int A[],int len)
{
    for(int i=len/2;i>0;i--)//（len/2）前的所有元素，也就是非叶结点
        HeadAdjust(A,i,len);
}

void HeadAdjust(int A[];int k;int len)
{
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2)//初始化就是指向左孩子  如果循环的话，就是不断指向孩子的孩子，效果是小元素的不断下沉
    {
        if(i<len&&A[i]<A[i+1]) //i<len才有右孩子 取较大的孩子
            i++;
        if(A[0]>=A[i]) break;//满足根>=孩子
        else{
            A[k]=A[i];//更新根 
            k=i;//进入下一轮筛选循环
        }
    }
    A[k]=A[0];
}
//堆排序
void HeapSort(int A[],int len)
{
    BuildMaxHeap(A,len);//初始化为大根堆
    for(int i=len;i>1;i--)//n-1趟交换和建堆的过程
    {
        swap(A[i],A[1]);//A[1]为每次的最大元素
        HeadAdjust(A,1,i-1);//交换完A[1]就是原来的堆底，继续下沉建立新堆
    }
}

≡

数据结构

线性表

顺序表

单链表

双链表

循环链表

静态链表

栈

应用：

队列

双端队列

循环队列

应用：

字符串

KMP算法

树

二叉树的存储

顺序存储（满二叉树）

链式存储

二叉树的遍历

先序遍历

中序遍历

后序遍历

层序遍历

线索二叉树

二叉排序树

平衡二叉树（AVL树）

哈夫曼树

哈夫曼编码

普通树

普通树存储

双亲表示法（顺序存储）

孩子表示法（顺序＋链式存储）

孩子兄弟表示法（链式存储）

普通树的遍历

森林

遍历

先序遍历

中序遍历

图

概念

有向图

无向图

简单图

多重图

完全图（也称简单完全图）

连通图

连通分量

强连通图

强连通分量

生成树

生成森林

稀疏图 稠密图

顶点的度 入度 出度

图的存储

邻接矩阵

邻接表

十字链表（存储有向图）

邻接多重表（存储无向图）

搜索

DFS

BFS

最小生成树

Prim

Kruskal

最短路径

BFS算法

Dijkstra算法

Floyd算法

拓扑排序

查找

顺序查找

二分查找

分块查找

B树

B+树

散列表查找（哈希表）

排序

稳定性

插入排序

稀疏图稠密图

顶点的度入度出度