数据结构和算法（上）：https://developer.aliyun.com/article/1529453
1.4.2 图
1）图的定义和术语
图是比树结构更复杂的一种数据结构，任意两个结点之间都可能有直接的关系，所以图中一个结点的前驱和后继的数目是没有限制的。图结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有非常广泛的应用。
图的相关术语如下：
有向图：每条边都是有方向的。
无向图：每条边都是无方向的。
完全图：一个无向图具有n个顶点，而每一个项点与其他n-1个项点之间都有边。显然，含有n个顶点的无向完全图共有n(n-1)/2条边。类似地，有n个项点的有向完全图中弧的数目为n(n-1)，即任意两个不同顶点之间都存在方向相反的两条弧。
度、出度和入度：度是指关联于该顶点的边的数目；顶点的入度是以该项点为终点的有向边的数目，而项点的出度指以该顶点为起点的有向边的数目。若为有向图，顶点的度表示该顶点的入度和出度之和。
路径：路径长度是路径上边或弧的数目。第一个顶点和最后一个项点相同的路径称为回路或环。若一条路径上除了开始顶点和结束顶点可以相同外，其余顶点均不相同，这种路径称为一条简单路径。
子图：两个图，若一个图被包含于另一个图。
连通图：无向图中任意两个顶点都是连通的。
强连通图：有向图中，两个顶点互通都有路径。
网：边(或弧)具有权值的图称为网。
2）图的存储结构
常用的存储结构有邻接矩阵和邻接表。
缺点是有许多为0的，造成浪费。
邻接链表表示法是首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。
优点是容易找度和关系，存放空间减少了。
3）图的遍历
深度优先遍历(DFS)，类似于树的前序遍历。根据上图遍历示例有V1,V2,V4,V8,V5,V3,V6,V7
- 首先访问出发顶点V；
- 依次从V出发搜索V的任意一个邻接点W；
- 若W未访问过，则从该点出发继续深度优先遍历。
广度优先，类似于树的层序遍历。根据上图遍历示例有V1,V2,V3,V4,V5,V6,V7,V8
- 首先访问出发顶点V
- 然后访问与顶点V邻接的全部未访问顶点W、X、Y…；
- 然后再一次访问W、X、Y…邻接的未访问的顶点。
2. 算法基础知识
2.1 基础概念
算法是问题求解过程的精确描述，它为解决某一特定类型的问题规定了一个运算过程，并且具有下列特性:
- 有穷行。一个算法必须在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。
- 确定性。算法中每一条指令都必须有确切的含义，不能含糊不清。
- 输入。(>=0) 一个算法有零个或多个输入。
- 输出。(>=1) 一个算法有一个或多个输出，与输入有特定关系的量。
- 有效性（可行性）。算法的每个步骤都能有效执行并能在执行有限次后得到确定的结果。例如a=0，b/a就无效。
常用的算法描述方法有流程图、N/S盒图、伪代码和决策表等。
1）流程图
流程图(flow chart)即程序框图，是历史最久、流行最广的一种算法的图形表示方法。每个算法都可由若干张流程图描述。流程图给出了算法中所进行的操作以及这些操作执行的逻辑顺序。
程序流程图包括三种基本成分：加工步骤，用方框表示；逻辑条件，用菱形表示：控制流，用箭头表示。常用的几种符号如下：
示例. 求正整数m和n的最大公约数，流程图如下：
2）N/S 盒图
盒图是结构化程序设计出现之后，为支持这种设计方法而产生的一种描述工具。N/S 盒图的基本元素与控制结构如下：
在N/S图中，每个处理步骤用一个盒子表示，盒子可以嵌套。对于每个盒子，只能从上面进入，从下面走出，除此之外别无其他出入口，所以盒图限制了随意的控制转移，保证了程序的良好结构。
示例. 求正整数m和n的最大公约数，盒图如下：
3）伪代码
伪代码是一种算法描述语言，介于自然语言与编程语言之间，不用拘泥于具体的实现。
示例. 输入3个数，打印输出其中最大的数。
begin （算法开始） 输入 a,b,c if a>b 则 a->max 否则 b->max if c>max 则c->max print max end （算法结束）
4）决策表
决策表是一种图形工具，它将比较复杂的决策问题简洁、明确、一目了然地描述出来 。
示例. 如果订购金额超过500元，以前没有欠账，则发出批准单和提货单；如果订购金额超过500元，但以前的欠账尚未还清，则发不予批准的通知；如果订购金额低于500元，则不论以前的欠账是否还清都发批准单和提货单，在欠账未还清的情况下还要发出“催款单”。处理该问题的决策表如下：
2.2 排序
1）内部排序
常见的内部排序有如下：
void insertSort(int datall, int n ) /*将数组data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列*/ {int i, j; int tmp; for (i=1;i<n;i++){ if (data[i]<data[i-1]){ tmp = data[i];data[i] = data[i-1]; for (j = i-1; j >= 0 && data[j] > tmp; j--) data[j+1] = data[j]; data[j+1] = tmp; }/*if*/ }/*for*/ }/*insertSort*/
void bubblesort(int datall, int n) /*将数组data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列*/ {int i,j,tag; /*用tag表示排序过程中是否交换过元素值*/ int tmp; for(i= 1,tag= 1;tag == 1 && i < n;i++){ tag = 0; for(j=0;j < n-1;j++) if (data[j]>data[j+1]){ tmp = data[j]; data[j] = data[j+1]; data[j+1] = tmp; tag = 1; }/*if*1 }/*for*/ }/*bubblesort*/
void selectsort(int datall, int n) /*将数组data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列*/ {int i,j,k; int tmp; for(i=1;i < n;i++){ k= i; for(j = i+1;j <= n;j++) /*找出最小元素的下标，用k表示*/ if (data[j]< data[k]) k=j; if (k != i ) { tmp = data[i]; data[i] = data[k]; data[k] = tmp; }/*if*/ }/*for*/ }/*selectSort*/
- 希尔排序：又称“缩小增量排序”，是对直接插入排序方法的改进。先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
- 归并排序：将两个或两个以上的有序文件合并成为一个新的有序文件。
2）外部排序
外部排序就是对大型文件的排序，待排序的记录存放在外存。在排序的过程中，内存只存储文件的一部分记录，整个排序过程需要进行多次内外存间的数据交换。常用的外部排序方法是归并排序，一般分为两个阶段：在第一阶段，把文件中的记录分段读入内存，利用某种内部排序方法对这段记录进行排序并输出到外存的另一个文件中，在新文件中形成许多有序的记录段，称为归并段；在第二阶段，对第一阶段形成的归并段用某种归并方法进行一趟趟地归并，使文件的有序段逐渐加长，直到将整个文件归并为一个有序段时为止。
2.3 查找
查找是非数值数据处理中一种常用的基本运算，查找运算的效率与查找表所采用的数据结构和查找方法密切相关。
五大查找如下：
- 顺序表查找：顺序查找、二分查找、索引顺序查找
- 树表查找：二叉查找树（排序）
- 散列表查找：哈希查找
1）顺序查找
从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。适用于顺序存储和链式存储方式的查找表。
等概率情况下，顺序查找成功的平均查找长度为(n+1)/2。即成功查找的平均比较次数约为表长的一半，若所查记录不在表中，则至少进行n次比较才能确定失败。
缺点查找效率低，优点是算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排序均可应用。
2）二分查找
基本思想是：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时 (表明查找不成功)为止。中间位置为mid=[(low+high)/2]向下取整；
折半查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列。因此，折半查找适用于表不易变动，且又经常进行查找的情况。
3）索引顺序查找
索引顺序查找又称分块查找，是对顺序查找方法的一种改进。
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序。
查找过程分为两步：第一步在索引表中确定待查记录所在的块；第二步在块内顺序查找。
查找效率较顺序查找要好得多，但远不及二分查找。
4）二叉查找树（排序）
基本思想是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后再去和每个结点比较大小，查找最合适的范围。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
二叉排序树的定义：二叉排序树或者是一颗空树；或者是具有如下特性的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
- 它的左、右子树也都分别是二叉排序树。
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的序列。
二叉平衡树，又称AVL树，或者是一颗空树，或者是具有下列性质的二叉树，它的左子树或右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
平衡因子，二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。哈夫曼树是给定N个权值作为N个叶子结点，构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树。哈弗慢树是带权路径长度最短的树，权值较大的结点离根较近。
一般可以按下面步骤构造：
- 将所有左、右子树都为空的作为根结点。
- 在森林中选取两颗根结点的权值最小的树作为一颗新树的左、右子树，且置新树的附加根结点的权值为其左、右子树上根结点的权值之和。
- 从森林中删除这两颗树，同时把新树加入到森林中。
- 重复2，3步骤，直到森林中只有一颗树为止，此树就是哈夫曼树。
应用场景是对字符集中的字符进行编码和译码。
B树，可以写B-树或B_树，其中-或者_只是连字符，一颗m阶的B树是一颗平衡的多路搜索树，它或者是空树，或者是满足下列性质的树：
- 树中每个结点最多有m课子树；
- 若根结点不是叶子结点，则最少有两颗子树；
- 除根之外的所有非终端结点至少有[m/2]向上取整颗子树；
- 所有非终端结点中包含下列信息
