文档文库

手机版

投诉建议

首页 > 严蔚敏数据结构复习整理完整版

严蔚敏数据结构复习整理完整版

发布时间：2019-01-05 16:16:49 来源：文档文库

小中大

字号：

手机查看

1.复杂性分析

对各种操作的时间复杂性的分析。

主要是链表，树，排序等简单一些的分析。

分析的时候，从简单的入手，学会方法。

后续的各种豆可能让你分析时间复杂度。

线性链表（顺序表和单链表）

链表循环链表

双向链表

2.线性结构队列（循环队列）

栈

链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。

栈：查找，插入（位置固定），删除（位置固定）

队列：查找，插入（位置固定），删除（位置固定）

顺序表（可以视为一个数组）

单链表：

（删除）

（插入）

倒置：

（查找）

循环链表

双向链表

栈：

（插入删除查找）

队列

（插入删除查找）

循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。

3.二叉树

基本概念

二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。

二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：

1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——如图(a)；

(2)只有一个根结点的二叉树——如图(b)；

(3)只有左子树——如图(c)；

(4)只有右子树——如图(d)；

(5)完全二叉树——如图(e)

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形

性质

(1) 在非空二叉树中，第i层的结点总数不超过, i>=1；

(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则如果I>1，则其父结点的编号为I/2；

如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；

如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

存储结构

顺序存储表示

二叉树可以用数组或线性表来存储，而且如果这是满二叉树，这种方法不会浪费空间。用这种紧凑排列，如果一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor((i-1)/2)找到（假设根节点的索引为0）。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。

/* 二叉树的顺序存储表示 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */ typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根节点 */ typedef struct { int level,order; /* 节点的层，本层序号(按满二叉树计算) */ }position;

二叉链表存储表示

/* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ }BiTNode,*BiTree;

遍历算法

二叉树的遍历三种方式，如下：

（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。

（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。

（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

例1：如上图所示的二叉树，若按前序遍历，则其输出序列为。若按中序遍历，则其输出序列为。若按后序遍历，则其输出序列为。

前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH

中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。

再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC

后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA

深度优先遍历

在深度优先中，我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是，不需记住访问过的每一个结点，因为树中不会有环。

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。

完全二叉树，满二叉树

1. 满二叉树：一棵深度为k，且有个节点称之为满二叉树

2. 完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树

4.树

基本概念

树（tree）是包含n（n>0）个结点的有穷集，其中：

（1）每个元素称为结点（node）；

（2）有一个特定的结点被称为根结点或树根（root）。

（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

我们可以形式地给出树的递归定义如下:

单个结点是一棵树，树根就是该结点本身。

设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为 n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称 T1,T2,..,Tk为结点n的子树。

空集合也是树，称为空树。空树中没有结点。

术语

1. 节点的度：一个节点含有的子树的个数称为该节点的度；

2. 树的度：一棵树中，最大的节点的度称为树的度；

3. 叶节点或终端节点：度为零的节点；

4. 非终端节点或分支节点：度不为零的节点；

5. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；

8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

9. 树的高度或深度：树中节点的最大层次；

10. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；

11. 节点的祖先：从根到该节点所经分支上的所有节点；

12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

13. 森林：由m（m>=0）棵互不相交的树的集合称为森林；

存储

父节点表示法

/* 树节点的定义 */#define MAX_TREE_SIZE 100typedef struct{ TElemType data; int parent; /* 父节点位置域 */} PTNode;typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; /* 节点数 */} PTree;

孩子链表表示法

/*树的孩子链表存储表示*/typedef struct CTNode { // 孩子节点 int child; struct CTNode *next;} *ChildPtr;typedef struct { ElemType data； // 节点的数据元素 ChildPtr firstchild； // 孩子链表头指针} CTBox;typedef struct { CTBox nodes[MAX_TREE_SIZE]； int n, r； // 节点数和根节点的位置} CTree;

5.森林

6.森林、树与二叉树的转换

将树转换为二叉树

　树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：

　　①在所有兄弟结点之间加一连线；

　　②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。

注意：

　由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。

2）将一个森林转换为二叉树

具体方法是：

　　① 将森林中的每棵树变为二叉树

　　② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。

二叉树到树、森林的转换

　把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。

图

二元组的定义

图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。

E的元素都是二元组，用(x,y)表示，其中x,y∈V。

三元组的定义

图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函数，I将E中的每一个元素映射到

。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。

有/无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。

简单图

一个图如果

1. 没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；

2. 每条边所关联的是两个不同的顶点

则称为简单图（Simple graph）。简单的有向图和无向图都可以使用以上的“二元组的定义”，但形如的序对不能属于E。而无向图的边集必须是对称的，即如果，那么。

基本术语

阶（Order）：图G中顶集V的大小称作图G的阶。

子图（Sub-Graph）：当图G'=(V',E')其中V‘包含于V，E’包含于E，则G'称作图G=(V,E)的子图。每个图都是本身的子图。

生成子图（Spanning Sub-Graph）：指满足条件V(G') = V(G)的G的子图G。

导出子图（Induced Subgraph）：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。

度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。

入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。

自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。

路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。

行迹（Trace）：如果路径P(u,v)中的边各不相同，则该路径称为u到v的一条行迹。

轨道（Track）：如果路径P(u,v)中的顶点各不相同，则该路径称为u到v的一条轨道。

闭的行迹称作回路（Circuit），闭的轨称作圈（Cycle）。

（另一种定义是：walk对应上述的path，path对应上述的track。Trail对应trace。）

桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。

图的存储表示

1.数组（邻接矩阵）存储表示（有向或无向）

2.邻接表存储表示

邻接表是图的一种链式存储结构。

邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。

邻接表中的表结点和头结点结构：

有向图的邻接表和逆邻接表

（一）在有向图的邻接表中，第i个单链表链接的边都是顶点i发出的边。

（二）为了求第i个顶点的入度，需要遍历整个邻接表。因此可以建立逆邻接表。

（三）在有向图的逆邻接表中，第i个单链表链接的边都是进入顶点i的边。

邻接表小结

◆ 设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。

◆ 在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数。

◆ 在有向图中，第i个链表中的结点个数只是顶点vi的出度。在逆邻接表中的第i个链表中的结点个数为vi的入度。

◆ 建立邻接表的时间复杂度为O(n+e)。

3.有向图的十字链表存储表示

十字链表表示特点

1.针对弧结点，增加入弧链表结构和出弧链表结构；

2.容易求得任意顶点的出度和入度，专用于有向图的操作； 3.结构实现比较复杂。

4.无向图的邻接多重表存储表示

邻接多重表(Adjacency Multilist)主要用于存储无向图。因为，如果用邻接表存储无向图，每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中，这给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删除图中某一条边等，都需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。

邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如图

其中，顶点表由两个域组成，vertex 域存储和该顶点相关的信息firstedge 域指示第一条依附于该顶点的边；边表结点由六个域组成，mark 为标记域，可用以标记该条边是否被搜索过；ivex 和jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点ivex的边;jlink 指向下一条依附于顶点jvex 的边，info 为指向和边相关的各种信息的指针域。

一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。

在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。

在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作，它表示从顶点vi到顶点vj有一条边。

若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。

路径长度是指路径上边或弧的数目。

若第一个顶点和最后一个顶点相同，则这条路径是一条回路。

若路径中顶点没有重复出现，则称这条路径为简单路径。

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。

在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。

图的遍历

图的遍历方法有深度优先搜索法和广度（宽度）优先搜索法。

深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。

广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

图的连通性问题

无向图的连通分量和生成树

有向图的强连通分量

最小生成树

边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。

最小生成树（MST）：权值最小的生成树。

生成树和最小生成树的应用：要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。

构造网的最小生成树必须解决下面两个问题：

1、尽可能选取权值小的边，但不能构成回路；

2、选取n－1条恰当的边以连通n个顶点；

MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。

1.prim算法

基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：

在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。

此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

Prim算法的核心:始终保持TE中的边集构成一棵生成树。

注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。

看了上面一大段文字是不是感觉有点晕啊，为了更好理解我在这里举一个例子，示例如下：

大家可能已经看出来了，kruskal算法寻找安全边的方式，就是在所有的边中找最小的表，只要两个节点是两个不相交集合，就加入到最小生成树中，直到所有的节点都连接起来。

有向无环图

关键路径

最短路径

迪杰斯特拉算法

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

　　Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

例如，对下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。

先给出一个无向图

用Dijkstra算法找出以A为起点的单源最短路径步骤如下

弗洛伊德算法

1.定义概览

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

2.算法描述

1)算法思想原理：

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）

从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

2).算法描述：

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。　　

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

∙ 因为迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径，但弗洛伊德算法是求所有顶点到所有顶点的最短路径。

∙ 弗洛伊德算法非常简洁优雅。

为了能讲明白弗洛伊德算法的精妙所在，我们先来看最简单的案例：

弗洛伊德算法

D1[0][2] = min{D0[0][2],D0[0][1]+D[1][2]}

查找（包括各种查找方法的性能分析平均查找长度）

顺序表的查找

顺序表的存储

typedef struct{

ElemType *elem; //定义了顺序表中元素类型的数组指针，指向顺序表存储空间的基址

int length; //顺序表的长度(也即元素个数)

int listsize; //当前分配给顺序表的存储容量

}SqList;

顺序查找

顺序表可以看做第一部分的单链表和顺序表，这样的话查找问题就可以解决了。

主要是：平均查找长度的计算

有序表的查找（理解有序表和顺序表的不同）

有序表就是因为存储的数据是有续的，所以可以进行折半查找。

顺序表可以是单链表存储和顺序表存储。

而有序表的存储必须是顺序表存储。这样才能找到中点。

折半查找

索引顺序表的查找

二叉排序树

定义

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；

查找

步骤：

若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

插入

二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

首先执行查找算法，找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

删除

在二叉排序树删去一个结点，分三种情况讨论：

1.若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

2.若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。

3.若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：

其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；

其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让*f的左子树(如果有的话)成为*p左子树的最左下结点(如果有的话)，再让*f成为*p的左右结点的父结点。

性能分析

每个结点的C(i)为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为，其平均查找长度为 (n+1)/2(和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比

平衡二叉树

定义

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

查找

和二叉排序树的查找是一样的。

插入

若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。

失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。

（1）LL型平衡旋转法

由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

（2）RR型平衡旋转法

由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。

（3）LR型平衡旋转法

由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。

如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为LL型，再按LL型处理成平衡型。

（4）RL型平衡旋转法

由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。

如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按RR型处理成平衡型。

平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意的是，左旋的时候p->right一定不为空，右旋的时候p->left一定不为空，这是显而易见的。

如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf == 2或者 bf == -2的节点。

删除

虽然平衡二叉树的节点删除操作的代码比较复杂，代码量也比较大，但是其删除过程只有以下3种情况：[注：只要牢牢把握住以下3点，理解平衡二叉树的删除操作不是太难]

① 被删的节点是叶子节点

处理思路：将该节点直接从树中删除，并利用递归的特点和高度的变化，反向推算其父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再变化。

② 被删的节点只有左子树或只有右子树

处理思路：将左子树（右子树）替代原有节点的位置，并利用递归的特点和高度的变化，反向推算父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再发生变化。

③ 被删的节点既有左子树又有右子树

处理思路：找到被删节点的左子树的最右端的节点rnode，将rnode的值赋给node，再把rnode的左孩子替换rnode的位置，在把rnode 释放掉，并利用递归特点，反向推断rnode的父节点和祖父节点是否失衡。如果失衡，则判断是哪种类型的失衡（LL、LR、RR、RL），再对失衡的节点进行旋转处理，直到根节点或高度不再发生变化。

B-树和B+树

定义和分析，算法要求程度不高。

哈希表

定义

构造方法

处理冲突的方法

查找

排序

插入排序

直接插入排序

1．直接插入排序的基本思想

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

设数组为a[0…n-1]。

1.初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3.i++并重复第二步直到i==n-1。排序完成。

折半插入排序

算法的基本过程：

1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置到中间值的位置，这样很简单的完成了折半；

2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；

3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

2—路插入排序

表插入排序

希尔排序

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素，每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。

快速排序

冒泡排序

冒泡排序算法的运作如下：（从后往前）

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

快速排序是对冒泡排序的一种改进

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。

总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

初始时，i = 0; j = 9; X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从 j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当 i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

选择排序

简单选择排序

设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第1个记录交换。执行n-1趟后就完成了记录序列的排序。

最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。

简单选择排序是不稳定排序。

树形选择排序

堆排序

1.堆

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：

Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

2.堆排序的思想

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

其基本思想为(大顶堆)：

1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；

2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

操作过程如下：

1)初始化堆：将R[1..n]构造为堆；

2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。

首先根据该数组元素构建一个完全二叉树，得到

然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：

20和16交换后导致16不满足堆的性质，因此需重新调整

这样就得到了初始堆。

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

此时3位于堆顶不满堆的性质，则需调整继续调整

继续调整：：：

这样整个区间便已经有序了。

从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为 nlogn。堆排序为不稳定排序，不适合记录较少的排序。

归并排序

归并排序(MergeSort)的基本思想是：将待排序文件看成为n个长度为1的有序子文件，把这些子文件两两归并，使得到「n/2」个长度为2的有序子文件；然后再把这「n/2」个有序文件的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止，这种排序方法成为二路归并排序。例如，有初始关键字序列：72,18,53,36,48,31,36，其二路归并排序过程如下所示。

　　　　n=7 [72] [18] [53] [36] [48] [31] [36]

　　一趟归并： [18 72] [36 53] [31 48] [36]

　　二趟归并： [18 36 53 72] [31 36 48]

　　三趟归并： [18 31 36 36 48 53 72]

自底向上的归并排序：归并排序主要是完成将若干个有序子序列合并成一个完整的有序子序列；自底向上的排序是归并排序的一种实现方式，将一个无序的N长数组切个成N个有序子序列，然后再两两合并，然后再将合并后的N/2（或者N/2 + 1）个子序列继续进行两两合并，以此类推得到一个完整的有序数组。下图详细的分解了自底向上的合并算法的实现过程：

平均时间复杂度：O(nlog2n)

空间复杂度：O(n) (用于存储有序子序列合并后有序序列)

稳定性：稳定

基数排序

多关键字的排序

1．多关键字排序思想

   多关键字排序也就是对一个序列中每项数据都包含有多个关键字的序列进行排序。比如说对一幅扑克牌进行排序，扑克牌就包括花色和面值这两个关键字。有两种排序方法：

   第一种方法：按照花色我们将扑克牌分成四堆。然后再对每堆扑克按照面值的大小进行排序。最后，按照花色大小顺序将这四队扑克牌收成一堆。这样扑克牌就排序好了。

   第二种方法：首先按照面值我们将扑克牌分成13堆。然后每堆按照花色顺序排列。也就是说，这13堆的最上面一张扑克的花色均为梅花(若小的排在上面，大的排在下面)。接着，我们将这最上面的13张梅花按照面值从小到大收集起来最为最下面的13张扑克，接着收集方块的13张扑克，以此直到收集完毕所以的扑克。这时，扑克的排序也进行完毕。

从上面的排序过程可以总结出多关键字排序的思想：首先按照某一个关键字进行排序，使序列按照一个关键排列有序，然后再在基础上对下一个关键进行排序，使得下一个关键字也有序，如此，只到所有的关键字均有需。

从上面的排序过程还可以看出多关键字的排序实际上包括两个过程：分配和收集。