现在的位置: 首页 > 综合 > 正文

数据结构知识点总结整理

2019年11月11日 ⁄ 综合 ⁄ 共 81122字 ⁄ 字号 小 中 大 ⁄ 评论关闭

数据结构知识点总结整理

0、常考基础必知必会

A. 排序：排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法；

B. 查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别？

C. 链表和数组的区别，在什么情况下用链表什么情况下用数组？

D. 栈和队列的区别？

E. 多态，举例说明；overload和override的区别？

F. 字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么的。strcpy和memcpy？

G. 继承、多继承？

H. 面向对象有什么好处？

I. 说说static的与众不同之处，如果一个变量被声明为static，它会被分配在哪里？在什么时候分配空间等？

J. 什么是虚函数、纯虚函数、虚的析构函数，用途？

K. 内存泄漏及解决方法？

网络部分：

OSI模型7层结构，TCP/IP模型结构？

B. TCP/UDP区别？

C. TCP建立连接的步骤？

D. 香农定理？

1、二叉树三种遍历的非递归算法（背诵版）


本贴给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。

1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;

void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile

if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec

2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;

void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile

if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec

3.后序遍历非递归算法
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;

typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;

//后序遍历
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;

do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}

while (!StackEmpty(s) &&s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点
}

if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec

4.层次遍历算法

// 二叉树的数据结构

structBinaryTree

{

int value; // 不写模板了，暂时用整形代替节点的数据类型

BinaryTree *left;

BinaryTree *right;

};

BinaryTree*root; // 已知二叉树的根节点

//层次遍历

voidLevel( const BinaryTree *root )

{

Queue *buf = new Queue(); // 定义一个空队列，假设此队列的节点数据类型也是整形的

BinaryTree t; // 一个临时变量

buf.push_back(root); //令根节点入队

while( buf.empty == false ) // 当队列不为空

{

p = buf.front(); // 取出队列的第一个元素

cout<<p->value<<' ';

if( p->left != NULL ) // 若左子树不空，则令其入队

{

q.push( p->left );

}

if( p->right != NULL ) // 若右子树不空，则令其入队

{

q.push( p->right );

}

buf.pop(); // 遍历过的节点出队

}

cout<<endl;

}

2、线性表

（1） 性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。

（2）单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。

（3）单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。

3、栈与队列

你可以问一下自己是不是已经知道了以下几点：
(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。
(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。
(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。
(4)循环队列中判队空、队满条件，循环队列中入队与出队（循环队列在插入时也要判断其是否已满，删除时要判断其是否已空）算法。

【循环队列的队空队满条件
为了方便起见，约定：初始化建空队时，令
front=rear=0,
当队空时：front=rear，
当队满时：front=rear 亦成立，
因此只凭等式front=rear无法判断队空还是队满。
有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。
队空时： front=rear，
队满时： (rear+1)%maxsize=front】

如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。

////////////////////////////////////////////////////////////////////////////////////////////////

循环队列的主要操作：

　　(1)创建循环队列

　　(2)初始化循环队列

　　(3)判断循环队列是否为空

　　(4)判断循环队列是否为满

　　(5)入队、出队

　　//空出头尾之间的一个元素不用

　　#include

　　#include

　　#define MAXSIZE 100

　　typedef struct

　　{

　　intelem[MAXSIZE];

　　intfront, rear;

　　}Quque; //定义队头

　　int initQue(Quque **q) //初始化

　　{

　　(*q)->front=0;

　　(*q)->rear=0;

　　}

　　int isFull(Quque *q)

　　{

　　if(q->front==(q->rear+1)%MAXSIZE)//判满(空出一个元素不用) 刘勉刚

　　 return 1;

　　else

　　 return 0;

　　}

　　int insertQue(Quque **q,int elem)

　　{

　　if(isFull(*q))return -1;

　　(*q)->elem[(*q)->rear]=elem;

　　(*q)->rear=((*q)->rear+1)%MAXSIZE;//插入

　　return0;

　　}

　　int isEmpty(Quque *q)

　　{

　　if(q->front==q->rear)//判空

　　 return 1;

　　else

　　 return 0;

　　}

　　int deleteQue(Quque ** q,int *pelem)

　　{

　　if(isEmpty(*q))

　　 return 0;

　　*pelem=(*q)->elem[(*q)->front];

　　(*q)->front=((*q)->front +1)%MAXSIZE;

　　return0;

　　}

4、串

串一章需要攻破的主要堡垒有：
1. 串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件；
2. 串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。
3. 顺序串与链串及块链串的区别和联系，实现方式。
4. KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。

5、多维数组和广义表

矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。

熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。

掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。

6、树与二叉树

树一章的知识点包括：
二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。
(1) 二叉树的概念、性质和存储结构
考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树(左右子树无序)的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：

A.第i层的最多结点数，

B.深度为k的二叉树的最多结点数，

C.n0=n2+1的性质，

D.n个结点的完全二叉树的深度，

E. 顺序存储二叉树时孩子结点与父结点之间的换算关系（root从1开始，则左为：2*i，右为：2*i+1）。
二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。
(2) 二叉树的三种遍历算法
这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。
(3) 可在三种遍历算法的基础上改造完成的其它二叉树算法：
求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。
(4) 线索二叉树：
线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。
(5) 最优二叉树（哈夫曼树）：
最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。
(6) 树与森林：
二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树。树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。

7、图

1. 图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。
2. 图的几种存储形式：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。
3. 考查图的两种遍历算法：深度遍历和广度遍历
深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。
4. 生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。
考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。
5. 拓扑排序问题：
拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。
6. 关键路径问题：
这个问题是图一章的难点问题。理解关键路径的关键有三个方面：

一是何谓关键路径；

二是最早时间是什么意思、如何求；

三是最晚时间是什么意思、如何求。

简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。
在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。
7. 最短路径问题：
与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径（单源最短路径）；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法，注意区分。


8、查找（search）

先弄清楚以下几个概念：关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。

一般将search分为三类：在顺序表上的查找；在树表上的查找；在哈希表上的查找。
（1） 线性表上的查找：
主要分为三种线性结构：

顺序表——传统查找方法：逐个比较；

有序顺序表——二分查找法（注意适用条件以及其递归实现方法）；

索引顺序表——对索引结构，采用索引查找算法。注意这三种表下的ASL值以及三种算法的实现。
（2） 树表上的查找：
树表主要分为以下几种：二叉排序树（即二叉查找树），平衡二叉查找树（AVL树），B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树。

二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉排序树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡排序二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。
B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法，因为这两种算法涉及到B树结点的分裂和合并，是一个难点。键树（keywordtree），又称数字搜索树（digitalsearch tree）或字符树。trie树也可说等同于键树或属于键树的一种。键树特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。
（3） 基于哈希表的查找算法：
哈希译自“hash”一词，意为“散列”或“杂凑”。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。

9、内部排序

考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。

排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。

（1）插入排序中又可分为：直接插入、折半插入、2路插入（？）、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。

（2）交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。
（3）选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。

简单选择，是通过简单的数组遍历方案确定最小数；

树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；

而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。

（4）归并排序，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。
（5）基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。
本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的。

//////////////////////////////////////////////稳定性分析////////////////////////////////////////////////

排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

稳定性的好处：若排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。
分析一下常见的排序算法的稳定性，每个都给出简单的理由。
(1) 冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
(2) 选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
(3) 插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
(4) 快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j]> a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和
a[j] 交换的时刻。
(5) 归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
(6) 基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
(7) 希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
(8) 堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

冒泡排序 插入排序 二路插入排序 希尔排序 快速排序 选择排序 归并排序 堆排序算法的C/C++实现//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
using namespace std;

//交换两个数的值
void swap(int &a,int &b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
}

//屏幕输出数组
void display(int array[],int len)
{
cout<<"the resultis:"<<endl;
for (int i = 0 ;i < len;i++ )
{

cout<<array[i]<<" ";
}
cout<<endl;
}

/*
冒泡排序
算法思想：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。
根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R：凡扫描到违反本原则的
轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，
重者在下为止。
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 n(n+1)/2
*/
void bubble_sort(int array[],int len)
{

for (int i = len-1 ;i >= 0;i-- )
{
for(int j = 0;j < i;j++)
if(array[j] > array[j+1])

swap(array[j],array[j+1]);
}
}

/*
直接插入排序
算法思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元
素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它
插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 n(n+1)/2
*/
void insert_sort(int array[],int len)
{
int tmp,i,j;

for(i = 1;i < len;i++)
{
if (array[i] < array[i-1])
{
tmp = array[i];
array[i] = array[i-1];

//插入到相应位置
for (j = i-2;j >= 0;j--)
{
//往后移
if (array[j] > tmp)
array[j+1] =array[j];
else
{
array[j+1] = tmp;
break;
}
}
if(j == -1)
array[j+1] = tmp;
}
}
}

/*
2-路插入排序
算法思想：增加一个辅助空间d,把r[1]赋值给d[1]，并将d[1]看成是排好序后处于中间
位置的记录。然后从r[2]开始依次插入到d[1]之前或之后的有序序列中。
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 n(n+1)/2

*/
void bi_insert_sort(int array[],int len)
{
int* arr_d = (int*)malloc(sizeof(int) * len);

arr_d[0] = array[0];
int head = 0,tail = 0;
for (int i = 1;i < len; i++ )
{
if (array[i] > arr_d[0])
{
int j;
for ( j= tail;j>0;j--)
{
if (array[i] <arr_d[j])
arr_d[j+1] =arr_d[j];
else
break;
}
arr_d[j+1] = array[i];
tail += 1;
}

else
{
if (head ==0)
{
arr_d[len-1] = array[i];
head =len-1;
}
else
{
int j;
for (j = head;j <=len-1;j++)
{
if (array[i] >arr_d[j])
arr_d[j-1] =arr_d[j];
else
break;
}
arr_d[j-1] = array[i];
head -= 1;
}
}
}

for (int i = 0;i < len; i++)
{
int pos = (i + head );
if(pos >= len) pos -= len;
array[i] = arr_d[pos];
}
free(arr_d);
}

/*
希尔排序
算法思想：先将整个待排序记录分割成若干子序列分别进行直接插入排
序，待整个序列中的记录基本有序时，再对全体记录进行一
次直接插入排序
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 ?
*/
void shell_insert(int array[],int d,int len)
{
int tmp,j;
for (int i = d;i < len;i++)
{
if(array[i] < array[i-d])
{
tmp = array[i];
j = i - d;
do
{
array[j+d] = array[j];
j = j - d;
} while (j >= 0 &&tmp < array[j]);
array[j+d] = tmp;
}
}
}
void shell_sort(int array[],int len)
{
int inc = len;
do
{
inc = inc/2;
shell_insert(array,inc,len);
} while (inc > 1);
}

/*
快速排序
算法思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。

递归地解这些子问题，然后将这些子问题的解组合成为原问题的解。
时间复杂度 o(nlogn)
空间复杂度 o(logn)
比较次数 ?
*/

void quick_sort(int array[],int low,int high)
{
if (low < high)
{
int pivotloc =partition(array,low,high);
quick_sort(array,low,pivotloc-1);
quick_sort(array,pivotloc+1,high);
}
}

int partition(int array[],int low,int high)
{
int pivotkey = array[low];
while (low < high)
{
while(low < high &&array[high] >= pivotkey)
--high;
swap(array[low],array[high]);

while(low < high &&array[low] <= pivotkey)
++low;
swap(array[low],array[high]);
}
array[low] = pivotkey;
return low;
}

/*
直接选择排序
算法思想：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中的第i个记录
时间复杂度 o(n^2)
空间复杂度 o(1) ?
比较次数 n(n+1)/2
*/
int SelectMinKey(int array[],int iPos,int len)
{
int ret = 0;
for (int i = iPos; i < len; i++)
{
if (array[ret] > array[i])
{
ret = i;
}
}
return ret;
}

void select_sort(int array[],int len)
{
for (int i = 0; i < len; i++)
{
int j =SelectMinKey(array,i,len);
if (i != j)
{
swap(array[i],array[j]);
}
}
}

/*
归并排序
算法思想：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。
时间复杂度 o(nlogn)
空间复杂度 o(n)
比较次数 ?
*/
void merge(int array[],int i,int m, int n)
{
int j, k;
int iStart = i, iEnd = n;
int arrayDest[256];
for ( j = m + 1,k = i; i <= m&& j <= n; ++k)
{
if (array[i] < array[j])
arrayDest[k] = array[i++];
else
arrayDest[k] = array[j++];
}

if (i <= m)
for (;k <= n; k++,i++)
arrayDest[k] = array[i];
if(j <= n)
for (;k <= n; k++,j++)
arrayDest[k] = array[j];

for(j = iStart; j <= iEnd; j++)
array[j] = arrayDest[j];
}

void merge_sort(int array[],int s,int t)
{
int m;
if (s < t)
{
m = (s + t )/2;
merge_sort(array,s,m);
merge_sort(array,m+1,t);
merge(array,s,m,t);
}
}

/*
堆排序
算法思想：堆排序（Heap Sort）是指利用堆（heaps）这种数据结构来构造的一种排序算法。
堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是
小于（或者大于）它的父节点。
时间复杂度 o(nlogn)
空间复杂度 o(1)
比较次数：较多
*/
void heap_adjust(int array[],int i,int len)
{
int rc = array[i];
for(int j = 2 * i; j <len; j *= 2)
{
if(j < len && array[j]< array[j+1]) j++;
if(rc >= array[j]) break;
array[i] = array[j]; i = j;
}
array[i] = rc;
}

void heap_sort(int array[],int len)
{
int i;
for(i = (len-1)/2; i >= 0; i--)
heap_adjust(array,i,len);
for( i = (len-1); i > 0; i--)
{
swap(array[0],array[i]); //弹出最大值，重新对i-1个元素建堆
heap_adjust(array,0,i-1);
}
}

int main()

{
int array[] = {45, 56, 76, 234, 1, 34,23, 2, 3, 55, 88, 100};
int len = sizeof(array)/sizeof(int);
//bubble_sort(array,len); //冒泡排序
/*insert_sort(array,len);*/ //插入排序
/*bi_insert_sort(array,len);*/ //二路插入排序
/*shell_sort(array,len);*/ //希尔排序
/*quick_sort(array,0,len-1);*/ //快速排序
/*select_sort(array,len);*/ //选择排序
/*merge_sort(array,0,len-1);*/ //归并排序
heap_sort(array,len); //堆排序
display(array,len);

return 0;
}

<|>对排序算法的总结

按平均时间将排序分为四类：

（1）平方阶(O(n2))排序

　一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序

　如快速、堆和归并排序；

（3）O(n1+￡)阶排序

　￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序

　如桶、箱和基数排序。

各种排序方法比较

简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

　因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：

　　①待排序的记录数目n；

　　②记录的大小(规模)；

　　③关键字的结构及其初始状态；

　　④对稳定性的要求；

　　⑤语言工具的条件；

　　⑥存储结构；

　　⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

10、OSI模型7层结构，TCP/IP模型结构？

osi参考模型

osi参考模型中的数据封装过程

下面的图表试图显示不同的TCP/IP和其他的协议在最初OSI模型中的位置：

7

应用层

例如HTTP、SMTP、SNMP、FTP、Telnet、SIP、SSH、NFS、RTSP、XMPP、Whois、ENRP

6

表示层

例如XDR、ASN.1、SMB、AFP、NCP

5

会话层

例如ASAP、TLS、SSH、ISO
8327 / CCITT X.225、RPC、NetBIOS、ASP、Winsock、BSD
sockets

4

传输层

例如TCP、UDP、RTP、SCTP、SPX、ATP、IL

3

网络层

例如IP、ICMP、IGMP、IPX、BGP、OSPF、RIP、IGRP、EIGRP、ARP、RARP、X.25

2

数据链路层

例如Ethernet、Token
ring、HDLC、Frame
relay、ISDN、ATM、802.11
WiFi、FDDI、PPP

1

物理层

例如wire、radio、fiber
optic、Carrier pigeon

tcp/ip参考模型

tcp/ip参考模型分为四个层次：应用层、传输层、网络互连层和主机到网络层：

tcp/ip参考模型的层次结构

通常人们认为OSI模型的最上面三层（应用层、表示层和会话层）在TCP/IP组中是一个应用层。由于TCP/IP有一个相对较弱的会话层，由TCP和RTP下的打开和关闭连接组成，并且在TCP和UDP下的各种应用提供不同的端口号，这些功能能够被单个的应用程序（或者那些应用程序所使用的库）增加。与此相似的是，IP是按照将它下面的网络当作一个黑盒子的思想设计的，这样在讨论TCP/IP的时候就可以把它当作一个独立的层。

4

应用层
（OSI5 到 7层）

例如HTTP、FTP、DNS
（如BGP和RIP这样的路由协议，尽管由于各种各样的原因它们分别运行在TCP和UDP上，仍然可以将它们看作网络层的一部分）

3

传输层
（OSI4 和 5层）

例如TCP、UDP、RTP、SCTP
（如OSPF这样的路由协议，尽管运行在IP上也可以看作是网络层的一部分）

2

网络互连层
（OSI3层）

对于TCP/IP来说这是因特网协议（IP）
（如ICMP和IGMP这样的必须协议尽管运行在IP上，也仍然可以看作是网络互连层的一部分；ARP不运行在IP上）

1

网络接口层
（OSI1和2层）

例如Ethernet、Wi-Fi、MPLS等。

应用层

该层包括所有和应用程序协同工作，利用基础网络交换应用程序专用的数据的协议。应用层是大多数普通与网络相关的程序为了通过网络与其他程序通信所使用的层。这个层的处理过程是应用特有的；数据从网络相关的程序以这种应用内部使用的格式进行传送，然后被编码成标准协议的格式。

一些特定的程序被认为运行在这个层上。它们提供服务直接支持用户应用。这些程序和它们对应的协议包括HTTP（The WorldWide Web）、FTP（文件传输）、SMTP（电子邮件）、SSH（安全远程登陆）、DNS（名称<-> IP 地址寻找）以及许多其他协议。

一旦从应用程序来的数据被编码成一个标准的应用层协议，它将被传送到IP栈的下一层。

在传输层，应用程序最常用的是TCP或者UDP，并且服务器应用程序经常与一个公开的端口号相联系。服务器应用程序的端口由InternetAssigned Numbers Authority（IANA）正式地分配，但是现今一些新协议的开发者经常选择它们自己的端口号。由于在同一个系统上很少超过少数几个的服务器应用，端口冲突引起的问题很少。应用软件通常也允许用户强制性地指定端口号作为运行参数。

连结外部的客户端程序通常使用系统分配的一个随机端口号。监听一个端口并且然后通过服务器将那个端口发送到应用的另外一个副本以建立对等连结（如IRC上的dcc文件传输）的应用也可以使用一个随机端口，但是应用程序通常允许定义一个特定的端口范围的规范以允许端口能够通过实现网络地址转换（NAT）的路由器映射到内部。

每一个应用层（TCP/IP参考模型 的最高层）协议一般都会使用到两个传输层协议之一：面向连接的TCP传输控制协议和无连接的包传输的UDP用户数据报文协议 。

常用的应用层协议有：

运行在TCP协议上的协议：

  • HTTP（HypertextTransfer Protocol，超文本传输协议），主要用于普通浏览。
  • HTTPS（HypertextTransfer Protocol over Secure Socket Layer, or HTTP over SSL，安全超文本传输协议）,HTTP协议的安全版本。
  • FTP（File Transfer Protocol，文件传输协议），由名知义，用于文件传输。
  • POP3（PostOffice Protocol, version 3，邮局协议），收邮件用。
  • SMTP（SimpleMail Transfer Protocol，简单邮件传输协议），用来发送电子邮件 。
  • TELNET（Teletypeover the Network，网络电传），通过一个终端（terminal）登陆到网络。
  • SSH（Secure Shell，用于替代安全性差的TELNET），用于加密安全登陆。

运行在UDP协议上的协议：

  • BOOTP（BootProtocol，启动协议），应用于无盘设备。
  • NTP（Network Time Protocol，网络时间协议），用于网络同步。

其他：

  • DNS（Domain Name Service，域名服务），用于完成地址查找，邮件转发等工作（运行在TCP和UDP协议上）。
  • ECHO（EchoProtocol，回绕协议），用于查错及测量应答时间（运行在TCP和UDP协议上）。
  • SNMP（SimpleNetwork Management Protocol，简单网络管理协议），用于网络信息的收集和网络管理。
  • DHCP（DynamicHost Configuration Protocol，动态主机配置协议），动态配置IP地址。
  • ARP（Address Resolution Protocol，地址解析协议），用于动态解析以太网硬件的地址。

传输层

传输层的协议，能够解决诸如可靠性（“数据是否已经到达目的地？”）和保证数据按照正确的顺序到达这样的问题。在TCP/IP协议组中，传输协议也包括所给数据应该送给哪个应用程序。

在TCP/IP协议组中技术上位于这个层的动态路由协议通常被认为是网络层的一部分；一个例子就是OSPF（IP协议89）。

TCP（IP协议6）是一个“可靠的”、面向连结的传输机制，它提供一种可靠的字节流保证数据完整、无损并且按顺序到达。TCP尽量连续不断地测试网络的负载并且控制发送数据的速度以避免网络过载。另外，TCP试图将数据按照规定的顺序发送。这是它与UDP不同之处，这在实时数据流或者路由高网络层丢失率应用的时候可能成为一个缺陷。

较新的SCTP也是一个“可靠的”、面向连结的传输机制。它是面向纪录而不是面向字节的，它在一个单独的连结上提供了通过多路复用提供的多个子流。它也提供了多路自寻址支持，其中连结终端能够被多个IP地址表示（代表多个物理接口），这样的话即使其中一个连接失败了也不中断。它最初是为电话应用开发的（在IP上传输SS7），但是也可以用于其他的应用。

UDP（IP协议号17）是一个无连结的数据报协议。它是一个“best effort”或者“不可靠”协议——不是因为它特别不可靠，而是因为它不检查数据包是否已经到达目的地，并且不保证它们按顺序到达。如果一个应用程序需要这些特点，它必须自己提供或者使用TCP。

UDP的典型性应用是如流媒体（音频和视频等）这样按时到达比可靠性更重要的应用，或者如DNS查找这样的简单查询／响应应用，如果建立可靠的连结所作的额外工作将是不成比例地大。

DCCP目前正由IEFT开发。它提供TCP流动控制语义，但对于用户来说保留了UDP的数据报服务模型。

TCP和UDP都用来支持一些高层的应用。任何给定网络地址的应用通过它们的TCP或者UDP端口号区分。根据惯例使一些大众所知的端口与特定的应用相联系。

RTP是为如音频和视频流这样的实时数据设计的数据报协议。RTP是使用UDP包格式作为基础的会话层，然而据说它位于因特网协议栈的传输层。

网络互连层

正如最初所定义的，网络层解决在一个单一网络上传输数据包的问题。类似的协议有X.25和ARPANET的Host/IMP Protocol。

随着因特网思想的出现，在这个层上添加了附加的功能，也就是将数据从源网络传输到目的网络。这就牵涉到在网络组成的网上选择路径将数据包传输，也就是因特网。

在因特网协议组中，IP完成数据从源发送到目的基本任务。IP能够承载多种不同的高层协议的数据；这些协议使用一个唯一的IP协议号进行标识。ICMP和IGMP分别是1和2。

一些IP承载的协议，如ICMP（用来发送关于IP发送的诊断信息）和IGMP（用来管理多播数据），它们位于IP层之上但是完成网络层的功能，这表明了因特网和OSI模型之间的不兼容性。所有的路由协议，如BGP、 OSPF、和RIP实际上也是网络层的一部分，尽管似乎它们应该属于更高的协议栈。

网络接口层

网络接口层实际上并不是因特网协议组中的一部分，但是它是数据包从一个设备的网络层传输到另外一个设备的网络层的方法。这个过程能够在网卡的软件驱动程序中控制，也可以在韧体或者专用芯片中控制。这将完成如添加报头准备发送、通过物理媒介实际发送这样一些数据链路功能。另一端，链路层将完成数据帧接收、去除报头并且将接收到的包传到网络层。

然而，链路层并不经常这样简单。它也可能是一个虚拟专有网络（VPN）或者隧道，在这里从网络层来的包使用隧道协议和其他（或者同样的）协议组发送而不是发送到物理的接口上。VPN和隧道通常预先建好，并且它们有一些直接发送到物理接口所没有的特殊特点（例如，它可以加密经过它的数据）。由于现在链路“层”是一个完整的网络，这种协议组的递归使用可能引起混淆。但是它是一个实现常见复杂功能的一个优秀方法。（尽管需要注意预防一个已经封装并且经隧道发送下去的数据包进行再次地封装和发送）。

///////////////////////////////////////////////////////////////////////////////////////////////////////////////

1、物理层（physical layer）　　
　　物理层规定了激活、维持、关闭通信端点之间的机械特性、电气特性、功能特性以及过程特性。该层为上层协议提供了一个传输数据的物理媒体。　　
　　在这一层，数据的单位称为比特（bit）。　　
　　属于物理层定义的典型规范代表包括：eia/tia rs-232、eia/tia rs-449、v.35、rj-45等。
　　2、数据链路层（data link layer）　　
　　数据链路层在不可靠的物理介质上提供可靠的传输。该层的作用包括：物理地址寻址、数据的成帧、流量控制、数据的检错、重发等。　　
　　在这一层，数据的单位称为帧（frame）。　　
　　数据链路层协议的代表包括：sdlc、hdlc、ppp、stp、帧中继等。　　
　　3、网络层（network layer）　　
　　网络层负责对子网间的数据包进行路由选择。此外，网络层还可以实现拥塞控制、网际互连等功能。
　　在这一层，数据的单位称为数据包（packet）。　　
　　网络层协议的代表包括：ip、ipx、rip、ospf等。　　
　　4、传输层（transport layer）　　
　　传输层是第一个端到端，即主机到主机的层次。传输层负责将上层数据分段并提供端到端的、可靠的或不可靠的传输。此外，传输层还要处理端到端的差错控制和流量控制问题。　　 在这一层，数据的单位称为数据段（segment）。　　
　　传输层协议的代表包括：tcp、udp、spx等。　　
　　5、会话层（session layer）　　
　　会话层管理主机之间的会话进程，即负责建立、管理、终止进程之间的会话。会话层还利用在数据中插入校验点来实现数据的同步。　　
　　会话层协议的代表包括：netbios、zip（appletalk区域信息协议）等。　　
　　6、表示层（presentation layer）　　
　　表示层对上层数据或信息进行变换以保证一个主机应用层信息可以被另一个主机的应用程序理解。表示层的数据转换包括数据的加密、压缩、格式转换等。　　
　　表示层协议的代表包括：ascii、asn.1、jpeg、mpeg等。　　
　　7、应用层（application layer）　　
　　应用层为操作系统或网络应用程序提供访问网络服务的接口。
　　应用层协议的代表包括：telnet、ftp、http、snmp等。

集线器hub工作在OSI参考模型的（物理）层；

网卡工作在OSI参考模型的（物理）层；

路由器router工作在OSI参考模型的（网络）层；

交换机Switch工作在OSI参考模型的（数据链路）层。

///////////////////////////////////////////////////////////////////////////////////////////////////////////////

（附）10、tcp建立连接为什么要三次握手？

tcp是一个面向连接的协议，在传送数据以前，必须要首先建立一条连接。连接的建立需要经过三次握手。为什么要经过三次握手呢，每次握手双方都做了些什么？

1）什么是tcp报文？

tcp报文就是通过tcp协议发送的数据包，由tcp头和数据段组成。

tcp头是固定的20个字节，它的格式为：

2）第一次握手做什么？

请求端(客户端)会向服务端(被请求端)发送一个tcp报文，申请打开某一个端口。因为没有数据，所以这个报文仅包含一个tcp头。其中：

SYN=1；当建立一个新的连接时， SYN标志变1。

序号；序号用来标识从客户端向服务端发送的数据字节流。

此时客户端进入SYN_SENT状态。

3）第二次握手做什么？

服务端收到客户端的SYN包，也会发一个只包含tcp头的报文给客户端。

ACK=1；服务端确认收到信息

确认序号；客户端序号+1，作为应答

SYN=1；因为tcp的连接是双向的，服务端作为应答的同时请求建立连接。

此时服务端进入SYN_RECV状态

4）第三次握手做什么？

ACK=1；客户端确认收到信息

确认序号；服务端序号+1，作为应答

此时客户端进入ESTABLISHED状态，服务端收到ACK后也会进入此状态

可见，客户端和服务端都保留了对方的序号，这三次握手缺少任何一步都无法实现这一目标。在三次握手过程中，出现了一些中间状态。

5）什么是半连接队列？

第一次握手完成后，服务端发送ACK+SYN包到客户端，在收到客户端返回前的状态为SYN_RECV，服务端为此状态维护一个半连接队列。当服务端收到客户的确认包时，删除该条目，服务端进入ESTABLISHED状态。Listen中的backlog参数表示这两个状态合的最大值。若客户端完成第一次握手后不再发送ACK包，导致服务端未完成队列溢出，达到Dos攻击的目的。

6）什么是SYN-ACK 重传？

Dos攻击可以达到目的的一个重要因素是服务端在发送完SYN+ACK包后会等待客户端的确认包，如果等待时间内未收到，服务端会进行首次重传，等待一段时间仍未收到客户确认包，会进行第二次重传，直到重传次数超过系统规定的最大值，系统将该连接信息从半连接队列中删除。如果系统删除的频率小于半连接状态的增长频率，服务端就无法正常提供服务。

7）Tcp关闭连接需要四次握手，这又是为什么呢？

这是由tcp半关闭(harf-close)造成的。既然一个TCP连接是全双工(即数据在两个方向上能同时传递)，因此每个方向必须单独地进行关闭。即一方发送一个FIN，另一方收到后发送一个ACK，这就是所谓的四次握手了。

8）第一次握手做什么？

客户端发送一个FIN（这个客户端是主动发起关闭的一端，与建立连接时的客户端不一定是同一主机）

此时客户端进入FIN_WAIT_1状态。

9）第二次握手做什么？

服务端收到FIN，发回客户端一个ACK，确认序号为收到的序号加1（因为FIN和SYN一样，会占用一个序号）；客户端收到ACK之后会进入FIN_WAIT_2状态，服务端会进入CLOSE_WAIT状态。

10）第三次握手做什么？

服务端发送给客户端一个FIN。服务端进入LAST_ACK状态。

11）第四次握手做什么？

客户端收到FIN，发回服务端一个ACK，确认序号为收到的序号加1；客户端会进入TIME_WAIT状态，2MSL超时后进入CLOSE状态。服务端收到ACK后也会进入CLOSE状态。

其实我们通俗的说每次握手其实就是发一次数据包的过程。建立连接时双方共发送了3个包，关闭连接时发送和确认的两次握手决定了一端数据流的关闭，四次握手可以保证两方都关闭。

12）为什么建立连接是三次握手，而关闭连接是四次呢？

建立连接时，服务端可以把应答ACK和同步SYN放在一个报文里进行发送。而关闭连接时，收到FIN通知仅仅表示对方没有数据发送过来了，并不表示自己的数据全部发送给了对方。所以ACK和FIN是分了两次进行发送。如果服务端收到FIN，恰恰自己也没有数据要发，是不是ACK和FIN可以一起发给客户端呢，这样就可以少一次数据流了。世界是美好的，经典的TCP连接状态图中也考虑到了这种情况，tcp关闭连接确实是只有三次数据流动，服务端将ACK和FIN放在一个包里进行发送，但四次握手这个概念却已经根深蒂固无法更改了。

13）Tcp的各个状态是怎样的？

客户端的正常tcp状态：

CLOSED->SYN_SENT（第1次）->ESTABLISHED（第3次）->FIN_WAIT_1（第1次）->FIN_WAIT_2（第2次）->TIME_WAIT（第4次）->CLOSED

服务端的正常tcp状态：

CLOSED->LISTEN->SYN_RCVD（第2次）->ESTABLISHED（第3次）->CLOSE_WAIT（第2次）->LAST_ACK（第3次）->CLOSED（第4次）

tcp还有其他的非正常状态，在此不做讨论，下篇文章再说。

11、数组和链表的优缺点

数组，在内存上给出了连续的空间。链表，内存地址上可以是不连续的，每个链表的节点包括原来的内存和下一个节点的信息(单向的一个，双向链表的话，会有两个)。

数组优于链表的:

A. 内存空间占用的少，因为链表节点会附加上一块或两块下一个节点的信息。

但是数组在建立时就固定了。所以也有可能会因为建立的数组过大或不足引起内存上的问题。

B. 数组内的数据可随机访问，但链表不具备随机访问性。这个很容易理解，数组在内存里是连续的空间，比如如果一个数组地址从100到200，且每个元素占用两个字节，那么100-200之间的任何一个偶数都是数组元素的地址，可以直接访问。

链表在内存地址可能是分散的。所以必须通过上一节点中的信息找能找到下一个节点。

C. 查找速度上。这个也是因为内存地址的连续性的问题，不罗索了。

链表优于数组的:

A. 插入与删除的操作。如果数组的中间插入一个元素，那么这个元素后的所有元素的内存地址都要往后移动。删除的话同理。只有对数据的最后一个元素进行插入删除操作时，才比较快。链表只需要更改有必要更改的节点内的节点信息就够了。并不需要更改节点的内存地址。

B. 内存地址的利用率方面。不管你内存里还有多少空间，如果没办法一次性给出数组所需的要空间，那就会提示内存不足，磁盘空间整理的原因之一在这里。而链表可以是分散的空间地址。

C. 链表的扩展性比数组好。因为一个数组建立后所占用的空间大小就是固定的，如果满了就没法扩展，只能新建一个更大空间的数组；而链表不是固定的，可以很方便的扩展。

12、C++操作符优先级:

记忆方法：
去掉一个最高的，去掉一个最低的，剩下的是一、二、三、赋值；双目运算符中，顺序为算术、关系和逻辑，移位和逻辑位插入其中。

--摘自《C语言程序设计实用问答》
问题：如何记住运算符的15种优先级和结合性？
解答：C语言中运算符种类比较繁多，优先级有15种，结合性有两种。
如何记忆两种结合性和15种优先级？下面讲述一种记忆方法。
结合性有两种，一种是自左至右，另一种是自右至左，大部分运算符的结合性是自左至右，只有单目运算符、三目运算符的赋值运算符的结合性自右至左。
优先级有15种，记忆方法如下：
记住一个最高的：构造类型的元素或成员以及小括号。
记住一个最低的：逗号运算符。
剩余的是一、二、三、赋值——意思是单目、双目、三目和赋值运算符。
在诸多运算符中，又分为：算术、关系、逻辑。
两种位操作运算符中，移位运算符在算术运算符后边，逻辑位运算符在逻辑运算符的前面。

再细分如下：
算术运算符*，/，%高于+，-。
关系运算符中：>，>=，<和<=高于==，!=。
逻辑运算符中，除了逻辑求反（！）是单目外，逻辑与（&&）高于逻辑或（||）。
逻辑位运算符中，除了逻辑按位求反（~）外，按位与（&)高于按位半加（^)，高于按位或（|）。

Precedence

Operator

Description

Example

Overloadable

Associativity

1

::

Scope resolution operator

Class::age = 2;

no

left to right

2

()

Function call

printf(“Hello world\n”);

yes

left to right

()

Member initalization

c_tor(int x, int y) : _x(x), _y(y * 10) {}

yes

[]

Array access

array[4] = 2;

yes

->

Member access from a pointer

ptr->age = 34;

yes

.

Member access from an object

obj.age = 34;

no

++

Post-increment

for (int i = 0; i < 10; i++) cout << i;

yes

--

Post-decrement

for (int i = 10; i > 0; i--) cout << i;

yes

dynamic_cast

Runtime-checked type conversion

Y& y = dynamic_cast<Y&>(x);

no

static_cast

Unchecked type conversion

Y& y = static_cast<Y&>(x);

no

reinterpret_cast

Reinterpreting type conversion

int const* p = reinterpret_cast<int const*>(0x1234);

no

const_cast

Cast away/Add constness

int* q = const_cast<int*>(p);

no

typeid

Get type information

std::type_info const& t = typeid(x);

no

3

!

Logical negation

if (!done) ...

yes

right to left

not

Alternate spelling for !

~

Bitwise complement

flags = ~flags;

yes

compl

Alternate spelling for ~

++

Pre-increment

for (i = 0; i < 10; ++i) cout << i;

yes

--

Pre-decrement

for (i = 10; i > 0; --i) cout << i;

yes

-

Unary minus

int i = -1;

yes

+

Unary plus

int i = +1;

yes

*

Dereference

int data = *intPtr;

yes

&

Address of

int *intPtr = &data;

yes

sizeof

Size (of the type) of the operand in bytes

size_t s = sizeof(int);

no

new

Dynamic memory allocation

long* pVar = new long;

yes

new []

Dynamic memory allocation of array

long* array = new long[20];

yes

delete

Deallocating the memory

delete pVar;

yes

delete []

Deallocating the memory of array

delete [] array;

yes

(type)

Cast to a given type

int i = (int)floatNum;

yes

4

->*

Member pointer selector

ptr->*var = 24;

yes

left to right

.*

Member object selector

obj.*var = 24;

no

5

*

Multiplication

int i = 2 * 4;

yes

left to right

/

Division

float f = 10.0 / 3.0;

yes

%

Modulus

int rem = 4 % 3;

yes

6

+

Addition

int i = 2 + 3;

yes

left to right

-

Subtraction

int i = 5 - 1;

yes

7

<<

Bitwise shift left

int flags = 33 << 1;

yes

left to right

>>

Bitwise shift right

int flags = 33 >> 1;

yes

8

<

Comparison less-than

if (i < 42) ...

yes

left to right

<=

Comparison less-than-or-equal-to

if (i <= 42) ...

yes

>

Comparison greater-than

if (i > 42) ...

yes

>=

Comparison greater-than-or-equal-to

if (i >= 42) ...

yes

9

==

Comparison equal-to

if (i == 42) ...

yes

left to right

eq

Alternate spelling for ==

!=

Comparison not-equal-to

if (i != 42) ...

yes

not_eq

Alternate spelling for !=

10

&

Bitwise AND

flags = flags & 42;

yes

left to right

bitand

Alternate spelling for &

11

^

Bitwise exclusive OR (XOR)

flags = flags ^ 42;

yes

left to right

xor

Alternate spelling for ^

12

|

Bitwise inclusive (normal) OR

flags = flags | 42;

yes

left to right

bitor

Alternate spelling for |

13

&&

Logical AND

if (conditionA && conditionB) ...

yes

left to right

and

Alternate spelling for &&

14

||

Logical OR

if (conditionA || conditionB) ...

yes

left to right

or

Alternate spelling for ||

15

? :

Ternary conditional (if-then-else)

int i = a > b ? a : b;

no

right to left

16

=

Assignment operator

int a = b;

yes

right to left

+=

Increment and assign

a += 3;

yes

-=

Decrement and assign

b -= 4;

yes

*=

Multiply and assign

a *= 5;

yes

/=

Divide and assign

a /= 2;

yes

%=

Modulo and assign

a %= 3;

yes

&=

Bitwise AND and assign

flags &= new_flags;

yes

and_eq

Alternate spelling for &=

^=

Bitwise exclusive or (XOR) and assign

flags ^= new_flags;

yes

xor_eq

Alternate spelling for ^=

|=

Bitwise normal OR and assign

flags |= new_flags;

yes

or_eq

Alternate spelling for |=

<<=

Bitwise shift left and assign

flags <<= 2;

yes

>>=

Bitwise shift right and assign

flags >>= 2;

yes

17

throw

throw exception

throw EClass(“Message”);

no

  

18

,

Sequential evaluation operator

for (i = 0, j = 0; i < 10; i++, j++) ...

yes

left to right

13、B树、B-树、B+树、B*树、红黑树和trie树

（1）B树:即二叉搜索树.

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点各存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如：

B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

如：

但B树在经过多次插入与删除后，有可能导致不同的结构：

右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；

实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的策略；


（2）B-树

是一种多路搜索树（并不是二叉的）, 多路平衡查找树：

1.定义任意非叶子结点最多只有M个儿子；且M>2；

2.根结点的儿子数为[2, M]；

3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5.非叶子结点的关键字个数=指向儿子的指针个数-1；

6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

8.所有叶子结点位于同一层；

如：（M=3）

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B-树的特性：

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.其搜索性能等价于在关键字全集内做一次二分查找；

5.自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；

由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；


（3）B+树

B+树是B-树的变体，也是一种多路搜索树：

1.其定义基本与B-树同，除了：

2.非叶子结点的子树指针与关键字个数相同；

3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

5.为所有叶子结点增加一个链指针；

6.所有关键字都在叶子结点出现；

如：（M=3）

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；


（4）B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

（5）红黑树

红黑树（Red-Black Tree）是二叉搜索树（BinarySearch Tree）的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。而红黑树在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树的查找方法与二叉搜索树完全一样；插入和删除节点的的方法前半部分节与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。

map就是采用红黑树存储的，红黑树(RB Tree)是平衡二叉树，其优点就是树到叶子节点深度一致，查找的效率也就一样，为logN。在实行查找，插入，删除的效率都一致，而当是全部静态数据时，没有太多优势，可能采用hash表各合适。

相对来说，hash_map是一个hashtable占用内存更多，查找效率高一些，但是hash的时间比较费时。总体而言，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小无关，属于常数级别；而map的查找速度是log(n)级别。并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且
hash_map的构造速度较慢。

现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。

红黑树的每个节点上的属性除了有一个key、3个指针：parent、lchild、rchild以外，还多了一个属性：color。它只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下4点性质：
1. 根节点是黑色的。
2. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
3. 红色节点的父、左子、右子节点都是黑色。
4. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。

（6）trie树

Trie树，即Double Array字典查找树，既可用于一般的字典搜索，也可用于索引查找。
每个节点相当于DFA的一个状态，终止状态为查找结束。有序查找的过程相当于状态的不断转换
对于给定的一个字符串a1,a2,a3,...,an.则

采用TRIE树搜索经过n次搜索即可完成一次查找。不过好像还是没有B树的搜索效率高，B树搜索算法复杂度为logt(n+1/2).当t趋向大，搜索效率变得高效。

Trie树的优点举例

已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法：

1. 最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(n^2)。

2. 使用hash：我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)* O(1)= O(n)。

3. 使用trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len)，而建立+查询在trie中是可以同时执行的，建立的过程也就可以成为查询的过程，hash就不能实现这个功能。所以总的复杂度为O(n*len)，实际查询的复杂度只是O(len)。
解释一下hash为什么不能将建立与查询同时执行，例如有串：911，911456输入，如果要同时执行建立与查询，过程就是查询911，没有，然后存入9、91、911，查询911456，没有然后存入9114、91145、911456，而程序没有记忆功能，并不知道911在输入数据中出现过。所以用hash必须先存入所有子串，然后for循环查询。

而trie树便可以，存入911后，已经记录911为出现的字符串，在存入911456的过程中就能发现而输出答案；倒过来亦可以，先存入911456，在存入911时，当指针指向最后一个1时，程序会发现这个1已经存在，说明911必定是某个字符串的前缀，该思想是我在做pku上的3630中发现的，详见本文配套的“入门练习”。


小结

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

14、最小生成树算法之Prim算法(C++实现)

在无向带权连通图G中，如果一个连通子树包含所有顶点，并且连接这些顶点的边权之和最小，那么这个连通子图就是G的最小生成树。求最小生成树的一个常见算法是Prim算法，该算法的基本思想是：

1）设置两个集合V和S，任意选择一个顶点作为起始顶点，将起始顶点放入集合S，其余顶点存入集合V中；

2）然后使用贪心策略，选择一条长度最短并且端点分别在S和V中边（即为最小生成树的中的一条边），将这条边在V中的端点加入到集合S中；

3）循环执行第2）步直到S中包含了所有顶点。

根据以上思想我们很快可以给出一个O（N^3)的算法，即选择一条最短边需要O（N^2)的时间复杂度，具体实现代码如下：

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// O(N^3)
#include <iostream>

using namespace std;

//用邻接矩阵表示无向图
#define N 6 //节点个数
#define M 100000//最大值，表示不可达
int matrix[N][N]=
{
M,6,1,5,M,M,
6,M,5,M,3,M,
1,5,M,5,6,4,
5,M,5,M,M,2,
M,3,6,M,M,6,
M,M,4,2,6,M
};

void prim()

{

bool flag[N]; //标记某个点是否当前生成树集合中

int i,j;

//初始化集合

for(i = 0; i <N; ++i)

flag[i] =false;

flag[0] = true;

int count = 1;

while(count++< N)

{

int min =M;

int e1 = -1,e2 = -1;

for(i = 0; i< N; ++i)

{

if(flag[i])

{

for(j= 0; j < N; ++j)

{

if(!flag[j])

{

if(matrix[i][j] < min)

{

min = matrix[i][j];

e1 = i;

e2 = j;

}

}

}

}

}

cout<<e1 + 1<<"-"<<e2 + 1<<""<<matrix[e1][e2]<<endl;

flag[e2] =true;

}

}

int main(int argc, char* *argv)

{

prim();

system("pause");

return 0;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

上面的算法有三个循环，时间复杂度为O（N^3)，考虑到由于使用的是贪心策略，则每添加一个新顶点到集合S中的时候，才会改变V中每个点到S中点的最小边的长度。因此可以用一个数组nearest[N](N为顶点个数）记录在生成最小数的过程中，记录V中每个点的到S中点的最小变长，用另外一个数组adjecent[N]记录使得该边最小的对应的邻接点。那么O（N）的时间了找到最短的边，并且能在O（N)的时间里更新nearest[N]和adjecent[N]。因此可以得到O(N^2)的算法。

源码实现如下：

//O(N^2)
#include <iostream>

using namespace std;

#define N 6 //节点个数

#define M 100000//最大值，表示不可达

//用邻接矩阵表示无向图

int matrix[N][N] =

{

M,6,1,5,M,M,

6,M,5,M,3,M,

1,5,M,5,6,4,

5,M,5,M,M,2,

M,3,6,M,M,6,

M,M,4,2,6,M

};

void prim()

{

//记当前生成树的节点集合为S

//未使用的节点结合为V

bool flag[N]; //标记某个点是否在S中

int nearest[N];//记录V中每个点到S中邻接点的最短边

intadjecent[N];//记录与V中每个点最邻接近的点

int i,j,min;

//初始化集合

for(i = 0; i <N; ++i)

flag[i] =false;

flag[0] = true;

for(i = 1; i <N; ++i)

{

nearest[i] =matrix[0][i];

adjecent[i] =0;

}

int count = N;

while(--count)

{

min = M;

j = 0;

for(i = 0; i< N; ++i)

{

if(!flag[i] && nearest[i] < min)

{

min =nearest[i];

j =i;

}

}

cout<<j+ 1<<"-"<<adjecent[j] + 1<<""<<matrix[j][adjecent[j]]<<endl;

flag[j] =true;

for(i = 0; i< N; ++i)

{

if(!flag[i] && matrix[i][j] <nearest[i])

{

nearest[i] = matrix[i][j];

adjecent[i] = j;

}

}

}

}

int main(int argc, char* *argv)

{

prim();

system("pause");

return 0;

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

#include <stdlib.h>

#define MAXVEX 30

#define MAXCOST 1000

/*

每一步扫描数组lowcost，在V-U中找出离U最近的顶点，令其为k，并打印边(k,closest[k]), 然后修改lowcost和closest，标记k已经假如U。c表示图邻接矩阵，弱不存在边(i,j),则c[i][j]的值为一个大于任何权而小于无限打的阐述，这里用MAXCOST表示

*/

/*一直图的顶点为{1,2,...,n},c[i][j]为(i,j)的权，打印最小生成树的每条边*/

void prim (int c[MAXVEX][MAXVEX], int n)

{

int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];

for(i=2;i<=n;i++) /*从顶点1开始*/

{

lowcost[i]=c[1][i];

closest[i]=1;

}

closest[1]=0;

for(i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/

{

min=MAXCOST;

j=1;

k=i;

while(j<=n)

{

if(lowcost[j]<min && closest[j]!=0)

{

min=lowcost[j];

k=j;

}

j++;

}

printf("(%d,%d)",closest[k],k); /*打印边*/

closest[k]=0;/* k假如到U中 */

for(j=2;j<=n;j++)

if(closest[j]!=0 && c[k][j]<lowcost[j])

{

lowcost[j]=c[k][j];

closest[j]=k;

}

}

}

问题：--------------------------------------------------------------------------------------

1) 为何两个for循环都是从下标2开始的？尤其是第二个想不通。
答：因为Prim算法可以任选起点，通常选定点1为起点，也就是说点1一开始就在U里面了，自然不必出现在第二个循环(在V-U中寻找点)中。

2) lowcost数组顾名思义知道是存放最小代价信息的数组，但是具体的说lowcost放着是什么的最小代价，比如“lowcost[i]=c[1][i];”表示的是什么意思（我要带i的语言描述）？
答：存放的是当前从点集U到点集V-U的最短边长，lowcost[i] = c[1][i]是初始化，开始时点集U中只有点1，因此当前点集U到点集V-U的各最短边长lowcost[i]就等于点1到点i的边权。

3) closest[i]=1 又是什么含意呢？
答：closest[i]记录对应lowcost[i]的边的起点，因为lowcost[i]是当前终点为i的各条边中的最小值，再加上一个closest[i]记录起点，就能确定最小生成树的边了。closest[i] = 1是初始化，自然每一个边都是从点1出发的。
4) 求教第二个for循环的整层循环是写什么，我要每一行的注释。到底是在作什么？？
答：
for (i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/

{

min=MAXCOST; // 这一段是在U之外找最小值，closest[j] != 0表示是U之外

j=1;

k=i;

while (j<=n)

{

if(lowcost[j]<min && closest[j]!=0)

{

min=lowcost[j];

k=j;

}

j++;

}

printf("(%d,%d)",closest[k],k); /*打印边，这里就看出closest[k]的用途了嘛*/

closest[k]=0; /*将点k加入集合U */

for(j=2;j<=n;j++) //更新最短边和相应起点

{

if (closest[j]!=0&& c[k][j]<lowcost[j]) //若点j在集合U外(cloest[j]!= 0)，而且从U中的 点k出发， //到达点j的边权小于当前以j为终点的最小权值(c[k][j] < lowcost[j])

{

lowcost[j]=c[k][j]; //更新最小权值

closest[j]=k; //记录新边的起点

}

}

}

15、最小生成树之kruskal算法

最小生成树两个重要的算法：Prim 和 Kruskal。

Prim：时间复杂度O(n^2)，适用于边稠密的网络。

Kruskal：时间复杂度为O(e*log(e))，适用于边稀疏的网络。

kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O（eloge）的排序算法时，克鲁斯卡算法的时间复杂度即为O（eloge），因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好！Kruskal

从所有边中找到一个最小的边，且将改变放入后不会生成圈，重复n-1次后求出最小生成树。我们首先将所有边排序，然后从小到大判断，如果不产生圈就加入树中，当加入n-1条边时停止。为了判断是否组成圈，我们要用到并查集，相关知识可以在本站或任一本竞赛书中找到，这里不赘述。算法复杂度是(eloge+eα)，α是做一次并查集的复杂度，可以认为是常数。

/*

并查集的一个特性:

用一个数组p[]表示每一个元素的父级元素

最父级的元素的父级元素是一个负数,这个负数的绝对值是这个集合下的元素的个数

*/

#include<algorithm>

#include<iostream>

usingnamespace std;

constint N=1001; //定义能处理的最大点的个数

template<class T>

structEdge

{

int from;

int to;

T cost;

};

template<class T>

booloperator <(const Edge<T> & a,const Edge<T> & b)

{

return a.cost<b.cost;

}

/*

找到x所在集合的最父级代表元素

如果这个集合只有x自己,那么最父级代表元素当然就是它自己

*/

intFindSet(int * p,int x)

{

int tmp,px=x;

while(p[px]>=0) //找到x所在集合的代表元素

px=p[px];

/*

路径压缩,可选,如果需要频繁查询,压缩之后可以提高速度

即把从x到代表元素路径上的所有的元素的父节点都表示为代表元素

*/

while(p[x]>=0)

{

tmp=p[x];

p[x]=px;

x=tmp;

}

return px; //x元素所在集合的代表元素

}

/*

合并x和y所在的集合.

*/

voidUnionSet(int * p,int x,int y)

{

int tmp;

x=FindSet(p,x);

y=FindSet(p,y);

if(x==y)

return ;

tmp=p[x]+p[y];

if(p[x]>p[y]) //将小树合并到大树下

{

p[y]=tmp;

p[x]=y;

}

else

{

p[x]=tmp;

p[y]=x;

}

return ;

}

/*

最小生成树算法之Kruskal算法:

算法思想:每次找最小的边,如果在已有的森林中加入该边后会形成回路,则舍弃,否则加入然后合并森林

n:点的个数;

edge_cnt:边的个数

edge[]:保存边的数组

edge_arr:保存选择边的数组,可选功能

*/

template<class T>

TMST_Kruskal(const int & n, const int & edge_cnt,Edge<T> edge[], Edge<T>* edge_arr = NULL)

{

T ans=0;

int i,x,y,p[N],cnt=0;

memset(p,-1,sizeof(p));

sort(edge,edge+edge_cnt);

for(i=0;i<edge_cnt;i++)

{

x=FindSet(p,edge[i].from);

y=FindSet(p,edge[i].to);

if(x!=y)

{

UnionSet(p,x,y);

ans+=edge[i].cost;

if(edge_arr)

edge_arr[cnt]=edge[i];

cnt++;

if(cnt==n-1)

return ans;

}

}

return -1;

}

16、单源最短路径

（1）Dijkstra 算法可以用来解决非负权重网络的单源点最短路径。

Dijkstra 算法的基本思想就是用贪心策略维护一棵最短路径生成树，先用dist[]数组维护一个最短路径，dist[v]表示起点 v0 与当前最短路径树中的顶点 v 的最短路径。选择下一个顶点时，我们找一条边 <x,y>，x 属于当前最短路径树中的点，y不属于当前最短路径树中的点，使得 dist[x]+ w(x,y) 最小，将边 <x,y> 加入到最短路径树中，依次进行，最后求得就是从起点
v0 出发的最短路径。

最短路径 dijsktra 算法模板：

#include<iostream>

usingnamespace std;

constint maxint = 9999999;

constint maxn = 1010;

intdata[maxn][maxn];//data存放点点之间的距离，

intlowcost[maxn]; //lowcost存放点到start的距离, 从0开始存放

boolused[maxn];//标记点是否被选中

intn; //顶点的个数

voiddijkstra(int start)//初始点是start的dij算法

{

int i,j;

memset(used, 0, sizeof(used));

//init

for(i = 0; i < n; i++)

lowcost[i] = data[start][i];

used[start] = true;

lowcost[start] = 0;

for(i = 0; i < n-1; i++)

{

//choose min

int tempmin = maxint;

int choose;

for(j = 0; j < n; j++)

{

if(!used[j] && tempmin >lowcost[j])

{

choose = j;

tempmin = lowcost[j];

}

}

used[choose] = true;

//updata others

for(j = 0; j < n; j++)

{

if(!used[j] &&data[choose][j] < maxint && lowcost[choose]+data[choose][j] <lowcost[j])

{

lowcost[j] =lowcost[choose]+data[choose][j];

}

}

}

}

intmain()

{

int start , i , j;

cin>>n;

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)//输入顶点信息

{

cin>>data[i][j];

}

cin>>start;

dijkstra(start);

int min = 0;

for(i = 0; i < n; i++)

{

cout<<lowcost[i]<<" "; //输出各结点间的最小路径长度

if(min < lowcost[i])

min = lowcost[i];

}

cout<<endl;

cout<<min<<endl;

return 0;

}

/*

3

0 12

3 04

5 60

1

输出：

3 04

4

*/

m为边数，n为定点数 ，时间复杂度O(n*n)

可以用二叉堆（优先队列）优化，时间复杂度O((m+n)log(n))

或者斐波那契堆优化，时间复杂度O(m+nlog(n))

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

constint MAXSIZE=100;

constint INF=1000000;//除对角线外最初都要初始化为无穷

intdist[MAXSIZE];

voidDijkstra(int cost[][MAXSIZE],int n,int v)//求v到各个顶点的最短路径

{

int i,j,k,min,set[MAXSIZE];

memset(set,0,sizeof(set));初始化

set[v]=1;

for(i=0;i<n;i++)

dist[i]=cost[v][i];

for(i=0;i<n;i++)

{

min=INF;

k=-1;

for(j=0;j<n;j++)

{

if(dist[j]<min&&set[j]!=1)/*选取不在set中且具有最小距离的顶点k*/

{

min=dist[j];

k=j;

}

set[k]=1;

for(j=0;j<n;j++)

{ /*修改不在s中的顶点的距离*/

if(cost[k][j]!=INF&&dist[j]>(dist[k]+cost[k][j])&&set[j]!=1)

dist[j]=dist[k]+cost[k][j];

}//dist数组存的就是v到个点的最短路径

}

}

}

Dijstra与prim在写法上有很大相似之处，把prim算法的代码也贴出来：

constint MAXSIZE=100;

constint INF=1000000;//对角线外最初都要初始化为无穷

intlowcost[MAXSIZE];

voidprim(int cost[][MAXSIZE],int n,int v)//从任意点v出发生成最小树

{

int i,j,k,min,set[MAXSIZE];

memset(lowcost,INF,sizeof(lowcost));//初始化为无穷

memset(set,0,sizeof(set));

set[v]=1;

for(i=0;i<n;i++)

dist[i]=cost[v][i];

for(i=0;i<n;i++)

{

min=INF;

k=-1;

for(j=0;j<n;j++)

{

if(lowcost[j]<min&&set[j]!=1)/*选取不在lowcost中具有最小距离的顶点k*/

{

min=dist[j];

k=j;

}

set[k]=1;

for(j=0;j<n;j++)

{

if(lowcost[j]>cost[k][j]&&set[j]!=1)

lowcost[j]=cost[k][j];

}//lowcost数组存的就是v到各个点的最短路径权值

}

}

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

对于有向图G={V,E},带权，注意Dijkstra算法要求所有的权值非负，假设我们的源是s，源点要到达的点集合是S，我们每次选择具有最短路径估计的顶点u(u在V-S中，并将u加入到S中，然后此时要对u所有的出边进行处理，怎么处理，我们要最短路径，所以此时要判断s经过u到达V-S中的点会不会比不经过u到达来的小，更新呵呵..
那么怎么写成代码呢？
1.我们需要二维数组graph[][]表示图，用distance[]数组来表示源点V0到其它顶点的最短路径distance[v]，我们还要保存具体路径，我们用path[][]二维bool数组来表示,path[1]就表示源点到顶点V1的路径，path[1][0,n-1]数组里面的元素如果为true表示V0有经过那些顶点到达V1。
2.我们还要考虑到顶点是否已经加到S中，用一个flag数组来标志顶点是否已经求的最短路径了。 还要分清是有向图还是无向图，这对于入边和出边在程序处理的时候要注意。

#defineMAXN 100

#defineINF 0xfffffff

//注意graph里面的数据，两顶点i指向j有边，长为r，则graph[i][j]=r,其余情况graph为INF，包括i==j

voiddijkstra(int graph[MAXN][MAXN],bool path[MAXN][MAXN],int distance[],int n)

{

int i,j,min,vertex;

bool flag[MAXN];

for(i=0;i<n;i++)//初始化

{

distance[i]=graph[0][i];

flag[i]=false;

for(j=0;j<n;j++)

path[i][j]=false;

if(distance[i]<INF)//路径必定至少有v0和vi两个顶点

{

p[i][0]=true;p[i][i]=true;

}

}

flag[0]=true;

distance[0]=0;//注意一定要初始化distance[0]

for(i=1;i<n;i++)

{

min=INF;

for(j=1;j<n;j++)

{

if(!flag[j]&&distance[j]<min)//找到最近的点

{

min=distance[j];

vertex=j;

}

}

flag[vertex]=true;

for(j=1;j<n;j++)

{

if(!flag[j]&&graph[vertex][j]+min<distance[j])//如果可以通过vertex更近的话,更新

{

distance[j]=graph[vertex][j]+min;

for(int k=0;k<n;k++)

path[j][k]=path[vertex][k];

path[j][j]=true;

}

}

}

}

请读者务必自己举个例子，运行看看，这样子才能理解好理解的根深蒂固，还有一定要自己不断的写，自己平常要锻炼。

（2）最短路径bellman-ford(贝尔曼-福特)算法

Bellman-Ford算法是求解单源最短路径问题的一种算法。

单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。

与迪科斯彻算法不同的是，在Bellman-Ford算法中，路径的权值可以为负数。设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有路径的权值之和为负。那么通过这个环路，环路中任意两点的最 短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。

算法描述

设G为加权有向图 V是所有结点的集合 E是所有路径的集合 S表示源点 n表示V中所有结点的数目weight(u,v)表示从结点u到结点v的路径的权值。 Distanz（v）表示从源点s出发到结点v的最短路径的距离，（或者说是从s到v所有的路径中权值的最小值）。Predecessor(v)表示节点 v的父结点在Bellman-Ford算法结束之后，可以输出，G是不是包含一个负环路。如果G不包含负环路，那么Distanz就存储了从s出发到所有结点的距离。

Bellman-Ford算法的伪代码如下：

------------------------------------------------

for 每一个结点v 属于 V

Distanz(v) := 无穷大， Predecessor(v) :=null

Distanz(s) := ，Predecessor(s):=null;

循环 n- 次

for 每一条路径 （u,v）属于E

if Distanz(u) + weight(u,v) <Distanz(v)

then

Distanz(v) := Distanz(u) +weight(u,v)

Predecessor(v) := u;

for 每一条路径 （u，v）属于E

if Distanz(u) + weight(u,v) <Distanz(v)

then

中止程序并且返回 “找到负循环”

返回

-----------------------------------------------------------

//算法代码~

#include<cstdio>

constint M = 10;

constint MAX = 0x7fffffff;

constint NIL = -1;

inta[M][M];//邻接矩阵

intver_amount;//顶点数

intd[M];//暂存当前点到源点的距离

intP[M];//求最短路径中当先点的前驱点

voidInitialize_Single_Source(int s)//初始化d[]和P[]

{

int i,j;

for(i=0;i<ver_amount;i++)

{

d[i]=MAX;

P[i]=NIL;

}

d[s]=0;

}

voidRelax(int u,int v)//松弛

{

if(d[v]>d[u]+a[u][v])

{

d[v]=d[u]+a[u][v];

P[v]=u;

}

}

boolBellman_Ford(int s)//求任意图的单源最短路径，若存在负权回路则返回假，否则返回真。

{

Initialize_Single_Source(s);

int i,j,k;

for(k=0;k<ver_amount-1;k++)//最多只需执行ver_amount-1躺即可

{

for(i=0;i<ver_amount;i++)//二重for循环实际是遍历所有边

for(j=0;j<ver_amount;j++)

{

if(a[i][j]!=MAX &&i!=j)

Relax(i,j);

}

}

for(i=0;i<ver_amount;i++)//二重for循环实际是遍历所有边

for(j=0;j<ver_amount;j++)

if(a[i][j]!=MAX && i!=j&& d[j]<d[i]+a[i][j])

return false;//存在负权回路

return true;//正常返回

}

intmain()

{

int i,j,w,edge_amount;

scanf("%d%d",&ver_amount,&edge_amount);

for(i=0;i<ver_amount;i++)

{

for(j=0;j<ver_amount;j++)

a[i][j]=MAX;

for(i=0;i<ver_amount;i++)

a[i][i]=0;

while(edge_amount--)

{

scanf("%d%d%d",&i,&j,&w);

a[i][j]=w;

}

Bellman_Ford(0);

for(i=0;i<ver_amount;i++)

{

printf("dist:%d\t",d[i]);

printf("path: %d",P[i]);

printf("\n");

}

}

return 0;

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

17、求任意两个节点之间最短距离——Floyd算法

Floyd算法：给出一个图（通常可以在任何图中使用，包括有向图、带负权边的图），求最短路径问题的一个O(n^3)算法。

优点：容易理解，可以算出任意两个节点之间最短距离的算法，程序容易写；

缺点：复杂度达到三次方，不适合计算大量数据；

它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。注意单独一条边的路径也不一定是最佳路径。

Floyd-Warshall算法的基本思路是：

1.用d[i][j]记录每对顶点间的最短距离；

2.对每一个图中的顶点，以其作为基点扫描每一对d[i][j]，检验是否通过该基点可以使得这对顶点间的距离变小。

//dist(i,j) 为从节点i到节点j的最短距离

Fori←1 to n do

For j←1 to n do

dist(i,j) = weight(i,j)

Fork←1 to n do // k为“媒介节点”

For i←1 to n do

For j←1 to n do

if (dist(i,k) + dist(k,j) < dist(i,j))then // 是否是更短的路径？

dist(i,j) = dist(i,k) + dist(k,j)

我们实际是很容易就可以写出这个算法的代码：

#defineN 100

voidFloyd(int dist[N][N],int n)

{

int i,j,k;

for(k=0;k<n;k++)

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(dist[i][k]+dist[k][j]<dist[i][j])

dist[i][j]=dist[i][k]+dist[k][j];

}

即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许的话(只要有放的下邻接矩阵的空间，时间上就没问题)。

对上面的代码来说，我们还面临一个保存路径的问题，如何来做呢？

/*多源最短路径floyd_warshall算法*/

#defineN 100

intmap[N][N];

voidFloyd(int dist[N][N],int path[N][N],int n)

{

int i,j,k;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

dist[i][j]=map[i][j], path[i][j]=0;

for(k=0;k<n;k++)

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(dist[i][k]+dist[k][j]<dist[i][j])

{

dist[i][j]=dist[i][k]+dist[k][j];

path[i][j]=k;

}

}

voidoutput(int i,int j)

{

if(i==j)

return;

if(path[i][j]==0)

cout<<j<<" ";

else

{

output(i, path[i][j]);

output(path[i][j], j);

}

}

18、二叉堆及其应用

（1）堆排序
<1> 二叉堆：二叉堆实际上一个完全二叉树。
在最大堆中，父节点的值大于等于子节点的值，所以堆的最大值在根部；
在最小堆中，父节点的值小于等于子节点的值，所以堆的最小值在根部；

上图是一个最小堆

<2>二叉堆可用于排序——复杂度为O(nlgn)
基本步骤有:
a. 建立二叉最大堆；
b. 由于最大值在根部，所以每次取出根部值和最后一个节点交换，堆的size减1，然后重新调整堆为最大堆，调整堆的复杂度为o(lgn)。

如何建立一个二叉最大堆呢？
根据完全二叉树的特点，可以知道有孩子的节点的节点下标是[0, n/2-1],因此我们从n/2-1开始向上调整，使之符合父节点大于孩子节点这个最大堆的特点。
只要建好最大堆，接下来就是步骤2了，注意调整堆要从根节点开始调整，堆的大小要减一。注意：我们的下标从0开始的

堆排序源码：

//i节点的父节点的下标

inlineint Parent(int i)

{

return (i-1)/2;

}

//i节点的左孩子的下标

inlineint Left(int i)

{

return 2*i+1;

}

//i节点的右孩子的下标

inlineint Right(int i)

{

return 2*i+2;

}

voidMaxHeapify(int a[],int heap_size,int i)

{

int left=Left(i);

int right=Right(i);

int largest=i;

if(left<heap_size&&a[left]>a[largest])

largest=left;

if(right<heap_size&&a[right]>a[largest])

largest=right;

if(largest!=i)

{

swap(a,i,largest);

MaxHeapify(a,heap_size,largest);

}

}

voidBuildMaxHeap(int a[],int n)

{

int i;

for(i=n/2-1;i>=0;i--)

MaxHeapify(a,n,i);

}

voidHeapSort(int a[],int n)

{

int i;

BuildMaxHeap(a,n);

for(i=n-1;i>0;i--)

{

swap(a,i,0);

MaxHeapify(a,i,0);

}

}

（2）优先级队列

<1>以最小二叉堆为例：

我们知道二叉堆的根节点最小值，正好符合了最小优先级队列每次取出最小值的特征，又我们知道优先级队列通常是里面的key值会有所变化，或者会加入新的节点而二叉堆o(lgn)的重新调整为最小二叉堆的能力，使得二叉堆完美的实现了优先级队列的需求。

<2>实现描述

优先级队列通常有如下操作：

HeapMinimum :返回队列中的最小值

HeapExtractMin ：返回队列中最小值并且去掉该最小值

HeapDecreaseKey ：对某个节点值进行key值的变化

MinHeapInsert ：插入一个新节点

MinHeapify :不可或缺的堆调整

优先级队列源码：

#include<iostream>

usingnamespace std;

#defineINFINITY 0xfffffff

//i节点的父节点的下标

inlineint Parent(int i)

{

return (i-1)/2;

}

//i节点的左孩子的下标

inlineint Left(int i)

{

return 2*i+1;

}

//i节点的右孩子的下标

inlineint Right(int i)

{

return 2*i+2;

}

//swapa[i] and a[j]

inlinevoid Swap(int a[],int i,int j)

{

int temp=a[i];

a[i]=a[j];

a[j]=temp;

//another solution

//a[i]^=a[j];a[j]^=a[i];a[i]^=a[j];

}

//Makethe subtree with the root a[i] be the Min Heap

voidMinHeapify(int a[],int heap_size,int i)

{

int left=Left(i);

int right=Right(i);

int min=i;

if(left<heap_size&&a[left]<a[min])

min=left;

if(right<heap_size&&a[right]<a[min])

min=right;

if(min!=i)

{

Swap(a,i,min);

MinHeapify(a,heap_size,min);

}

}

//returnthe min of the heap

intHeapMinimum(int a[])

{

return a[0];

}

//Extractthe min and return the min

intHeapExtractMin(int a[],int& heap_size)

{

if(heap_size<1)

return -1;

int min=a[0];

a[0]=a[heap_size-1];

heap_size-=1;

MinHeapify(a,heap_size,0);

return min;

}

//Decreasethe key value of a[i]

voidHeapDecreaseKey(int a[],int i,int key)

{

if(key>=a[i])

return;

a[i]=key;

while(i>0&&a[Parent(i)]>a[i])

{

Swap(a,i,Parent(i));

i=Parent(i);

}

}

voidMinHeapInsert(int a[],int& heap_size,int key)

{

heap_size+=1;

a[heap_size-1]=INFINITY;

HeapDecreaseKey(a,heap_size-1,key);

}

（3）其他应用

可使用堆解决下列问题：

<>1.构建哈夫曼代码：

我们知道在构建哈夫曼树时，每次要选择集合中两个最小的元素，然后将元素值相加，合并为一个新节点，此时两个最小的元素的取出可以用HeapExtractMin函数来实现，产出的新节点需要插入到堆中，我们有MinHeapInsert函数来实现。

<>2.计算大型浮点数集合的和：

我们知道大浮点数和小浮点数相加，很可能会造成精度误差。所以可以每次从优先级队列中取出最小的两个数相加，和1的实现差不多。

<>3.将多个小型有序文件合并到一个大型有序文件中：

假设有 n个小型有序文件，建立一个大小为n的最小堆，每个有序文件贡献一个(如果有的话），每次取出最小值插入到大型文件中，并且去掉该最小元素，并将它在文件中的后续元素插入到堆中,能够在o(lgn)的时间内从n个文件中选择要插入到大型文件中的元素。

<>4.在具有10亿个数值的集合中找到100万个最大的数：

建立100万个元素的最小二叉堆，后面的数和根部进行比较，如果大于根部，进行堆调整。

1.n×m遍扫描

【算法基本描述】n×m遍扫描

【算法复杂度】O(nm)

【算法思想】每次都扫描一遍数组，取出最大元素，这样扫描m遍就能得到m个最大的数。

2.排序后取最大m个数

【算法基本描述】对n个数排序，对拍完序后的序列取m个最大的数

【算法复杂度】视排序的复杂度，一般为O(nlogn)或O(n^2)

3.最小堆

【算法基本描述】一遍扫描+最小堆

【算法复杂度】O(nlogm) 遍历O(n) 最小堆O(logm)

【算法伪代码】

建立一个最小堆（优先队列），最小堆的大小控制在m之内；

for 每个数：

if 这个数比最小堆的堆顶元素大：

弹出最小堆的最小元素，

*把这个数插入到最小堆；

最小堆中的m个元素就是所要求的元素；

中最小堆的作用就是保持里面始终有m个最大元素，且m个元素中最小的元素在堆顶。

【其他】如果要求n个数中取最小的m个，只要大顶堆即可

总结：当n与m差不多大时，采用复杂度较低的排序是比较可取的，因为简单。当m<<n时，排序是很浪费时间的，因为我们不需要后(n-m)个数，所以可以采用最小堆的方法。

我不敢说我的算法是最好的，但是它一定是一个复杂度较低的算法。

使用用最小堆来找最大的K个数源码：

19、kmp算法

voidget_nextval(const char *T, int next[]);

intKMP(const char *Text,const char *Pattern) //const 表示函数内部不会改变这个参数的值

{

if( !Text||!Pattern|| Pattern[0]=='\0' ||Text[0]=='\0' )

return -1;//空指针或空串，返回-1

int len=0;

const char *c=Pattern;

while(*c++!='\0')//移动指针比移动下标快。

{

++len;//字符串长度。

}

int *next = new int[len+1];

get_nextval(Pattern, next); //求Pattern的next函数值

int i=0, j=0;

while(Text[i]!='\0' &&Pattern[j]!='\0' )

{

if(j = -1 || Text[i]== Pattern[j])

{

++i; // 继续比较后继字符

++j;

}

else

{

j=next[j]; // 模式串向右移动

}

}//while

delete []next;

return Pattern[j]=='\0' ? (len - i) :-1; //返回

}

voidget_nextval(const char *T, int next[])

{

//求模式串T的next函数值并存入数组 next。

int j = 0,;

int k = next[0] = -1;

while ( T[j/*+1*/] != '\0' )

{

if (k == -1 || T[j] == T[k])

{

++j;

++k;

if (T[j] != T[k])

next[j] = k;

else

next[j] = next[k];

}// if

else

k = next[k];

}// while

}//get_nextval　

20、后缀数组

(1)什么是后缀数组呢？

直观来说，后缀数组是记录一个字符串的后缀的排名的数组，什么是后缀呢，设一个字符串的长度是len（我们约定字符串下标从0开始，所以到len-1结束，比较符合我们日常编程习惯），某一位置i的后缀的就是从i开始到len-1结束的字符串，用suffix(i)表示，即对字符串s来说，suffix(i) =s[i,i+1....len-1]，可以发现不同的后缀按字典序排列的名词是不一样的（什么是字典序都应该知道吧），记录这些后缀按字典序排好的结果的数组就叫后缀数组，一般用sa[]表示，网络上对sa[]的标准定义为：

后缀数组：后缀数组SA 是一个一维数组，它保存1..n 的某个排列SA[1]，SA[2]，……，SA[n]，并且保证Suffix(SA[i])< Suffix(SA[i+1])，1≤i<n。也就是将S的n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA 中。

另外还要用到排名数组，即某一位置的后缀在所有后缀中的排名的数组，一般用Rank[]表示，容易发现Rank[sa[i]]=i。

名次数组：名次数组Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。

简单的说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。

知道了这些定义，剩下的就是如何构建后缀数组了，可以按照定义来构建，把每个后缀当做一个字符串，用全速排序来排序，不过那样的时间复杂度为O(n*n)，一般用来构建后缀数组用的是倍增算法(Doubling Algorithm)，说到倍增算法，就要说到k-前缀的定义，字符串u的k-前缀就是u的从0开始到k-1的字串，u长度不足k时就是整个字符串u，这样一来我们在比较串s的两个位置i,j的后缀的2k-前缀时，就是比较两个后缀的k-前缀和两个后缀位置+k的k-前缀，显然当k=1时就是对整个串的单字符进行排序，复杂度O(nlogn)，当k>=2时对已排好的k-前缀进行排序，用快排，复杂度O(nlogn)，用基数排序，复杂度O(n)，容易发现k是2倍增的。所以整个过程的时间复杂度就是O(nlongn)。

倍增算法构建sa[]的代码如下：

#definemax 10000

intRx[max],Ry[max],rx[max];

intcmp(int *y,int a,int b,int l)

{

return y[a] == y[b] && y[a+l] +y[b+l];

}

//对于串约定最后一位是小于串中其他任何元素的元素，这样cmp的时候就不用担心y[a+l]

//越界了，因为y[a]= y[b]就暗含了他们长度相等，都没有包含最后一位。

voidget_sa(char *s,int *sa)

{

int len = strlen(s),*Rank_x = Rx,*Rank_y =Ry,bar[max],*result_x = rx;

int i,j,k,p,*t,m=255;

for (i = 0; i<= m; i++)//对字符排序不会超过255，根据实际情况m值自定

bar[i] = 0;

for (i = 0; i< len; i++) bar[Rank_x[i] =s[i]]++;

for (i = 1; i<= m; i++) bar[i] +=bar[i-1];

for (i = len-1; i>= 0; i--)sa[--bar[Rank_x[i]]] = i;

//这段代码用到桶排序思想，就是先进桶，再从不同桶里一个一个往外倒

//sa[]保存的是1-前缀排序结果，Rank_x[]保存的是1-前缀时的各位置的排名

for (k = 1,p = 1; p < len; k *= 2, m = p)

{

for (p = 0,i = len - k; i < len;i++) Rank_y[p++] = i;

for (i = 0; i< len; i++) if (sa[i]>= k) Rank_y[p++] = sa[i] - k;

//这段代码对1-前缀时做第二关键字排序

for (i = 0; i< len; i++) result_x[i]= Rank_x[Rank_y[i]];

for (i = 0; i<= m; i++) bar[i] =0;

for (i = 0; i< len; i++)bar[result_x[i]]++;

for (i = 1; i<= m; i++) bar[i] +=bar[i-1];

for (i = len-1; i>= 0; i--)sa[--bar[result_x[i]]] = Rank_y[i];

//又用到了一次桶排序，注意体会，是在对第二关键字排好序的序列上对

//第一关键字进行桶排序求得了新的sa[]，result_x[]保存的是关于第二关键字

//排好序的序列的第一关键字排名，为桶排序做好准备

for (t = Rank_x,Rank_x = Rank_y,Rank_y= t,p = 1,Rank_x[sa[0]]= 0,i = 1; i <len; i++)

Rank[sa[i]] =cmp(Rank_y,sa[i],sa[i-1],k)?p-1:p++;

//求新的名次数组，可以发现名次可能一样，当名次各不一样时就是排序完成时。

}

}

(2)后缀数组的应用--height数组

在介绍后缀数组的应用前，先介绍后缀数组的一个重要附属数组：height数组。

1、height 数组：定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。height数组是应用后缀数组解题是的核心，基本上使用后缀数组解决的题目都是依赖height数组完成的。

2、height数组的求法：具体的求法参见罗穗骞的论文。对于height数组的求法，我并没有去深刻理解，单纯地记忆了而已...有兴趣的朋友可以去钻研钻研再和我交流交流

这里给出代码：

intrank[maxn],height[maxn];

void calheight(int*r,int *sa,int n)

{

int i,j,k=0;

for(i=1;i<=n;i++) rank[sa[i]]=i;

for(i=0;i<n;height[rank[i++]]=k)

for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);

return;

}

3、一些注意事项：height数组的值应该是从height[1]开始的，而且height[1]应该是等于0的。原因是，因为我们在字符串后面添加了一个0号字符，所以它必然是最小的一个后缀。而字符串中的其他字符都应该是大于0的（前面有提到，使用倍增算法前需要确保这点），所以排名第二的字符串和0号字符的公共前缀（即height[1]）应当为0.在调用calheight函数时，要注意height数组的范围应该是[1..n]。所以调用时应该是calheight(r,sa,n)而不是calheight(r,sa,n+1)。要理解清楚这里的n的含义是什么。

calheight过程中，对rank数组求值的for语句的初始语句是i=1而不是i=0的原因，和上面说的类似，因为sa[0]总是等于那个已经失去作用的0号字符，所以没必要求出其rank值。当然你错写成for (i=0..)，也不会有什么问题。

(3) 后缀数组解题总结

1、求单个子串的不重复子串个数。SPOJ 694、SPOJ 705.

这个问题是一个特殊求值问题。要认识到这样一个事实：一个字符串中的所有子串都必然是它的后缀的前缀。（这句话稍微有点绕...）对于每一个sa[i]后缀，它的起始位置sa[i]，那么它最多能得到该后缀长度个子串（n-sa[i]个），而其中有height[i]个是与前一个后缀相同的，所以它能产生的实际后缀个数便是n-sa[i]-height[i]。遍历一次所有的后缀，将它产生的后缀数加起来便是答案。

代码及题解：http://hi.baidu.com/fhnstephen/blog/item/68f919f849748668024f56fb.html

2、后缀的最长公共前缀。（记为lcp（x，y））

这是height数组的最基本性质之一。具体的可以参看罗穗骞的论文。后缀i和后缀j的最长公共前缀的长度为它们在sa数组中所在排位之间的height值中的最小值。这个描述可能有点乱，正规的说，令x=rank[i],y=rank[j]，x<y,那么lcp(i,j) = min(height[x+1],height[x+2]...height[y])。lcp(i,i)=n-sa[i]。解决这个问题，用RMQ的ST算法即可（我只会这个，或者用最近公共祖先那个转化的做法）。

3、最长重复子串（可重叠）

要看到，任何一个重复子串，都必然是某两个后缀的最长公共前缀。因为，两个后缀的公共前缀，它出现在这两个后缀中，并且起始位置时不同的，所以这个公共前缀必然重复出现两次以上（可重叠）。而任何两个后缀的最长公共前缀为某一段height值中的最小值，所以最大为height值中的最大值（即某个lcp(sa[i],sa[i+1]））。所以只要算出height数组，然后输出最大值就可以了。

一道题目和代码：http://hi.baidu.com/fhnstephen/blog/item/4ed09dffdec0a78eb801a0ba.html

4、最长重复不重叠子串 PKU1743

这个问题和3的唯一区别在于能否重叠。加上不能重叠这个限制后，直接求解比较困难，所以我们选择二分枚举答案，将问题转换为判定性问题。假设当时枚举的长度为k，那么要怎样判断是否存在长度为k的重复不重叠子串呢？

首先，根据height数组，将后缀分成若干组，使得每组后缀中，后缀之间的height值不小于k。这样分组之后，不难看出，如果某组后缀数量大于1，那么它们之中存在一个公共前缀，其长度为它们之间的height值的最小值。而我们分组之后，每组后缀之间height值的最小值大于等于k。所以，后缀数大于1的分组中，有可能存在满足题目限制条件的长度不小于k的子串。只要判断满足题目限制条件成立，那么说明存在长度至少为k的合法子串。

对于本题，限制条件是不重叠，判断的方法是，一组后缀中，起始位置最大的后缀的起始位置减去起始位置最小的后缀的起始位置>=k。满足这个条件的话，那么这两个后缀的公共前缀不但出现两次，而且出现两次的起始位置间隔大于等于k，所以不会重叠。

深刻理解这种height分组方法以及判断重叠与否的方法，在后面的问题中起到举足轻重的作用。

练习及题解：http://hi.baidu.com/fhnstephen/blog/item/85a25b208263794293580759.html

5、最长的出现k次的重复（可重叠）子串。 PKU3261

使用后缀数组解题时，遇到“最长”，除了特殊情况外（如问题3），一般需要二分答案，利用height值进行分组。本题的限制条件为出现k次。只需判断，有没有哪一组后缀数量不少于k就可以了。相信有了我前面问题的分析作为基础，这个应该不难理解。注意理解“不少于k次”而不是“等于k次”的原因。如果理解不了，可以找个具体的例子来分析分析。

题目及题解：http://hi.baidu.com/fhnstephen/blog/item/be7d15133ccbe7f0c2ce79bb.html

6、最长回文子串 ural1297

这个问题没有很直接的方法可以解决，但可以采用枚举的方法。具体的就是枚举回文子串的中心所在位置i。注意要分回文子串的长度为奇数还是偶数两种情况分析。然后，我们要做的，是要求出以i为中心的回文子串最长为多长。利用后缀数组，可以设计出这样一种求法：求i往后的后缀与i往前的前缀的最长公共前缀。我这里的表述有些问题，不过不影响理解。

要快速地求这个最长前缀，可以将原串反写之后接在原串后面。在使用后缀数组的题目中，连接两个（n个）字符串时，中间要用不可能会出现在原串中，不一样的非0号的字符将它们隔开。这样可以做到不影响后缀数组的性质。然后，问题就可以转化为求两个后缀的最长公共前缀了。具体的细节，留给大家自己思考...（懒...原谅我吧，都打这么多字了..一个多小时了啊TOT）

题目及题解：http://hi.baidu.com/fhnstephen/blog/item/68342f1d5f9e3cf81ad576ef.html

7、求一个串最多由哪个串复制若干次得到 PKU2406

具体的问题描述请参考PKU2406.这个问题可以用KMP解决，而且效率比后缀数组好。

利用后缀数组直接解决本题也很困难（主要是，就算二分答案，也难以解决转变而成的判定性问题。上题也是），但可以同过枚举模板串的长度k（模板串指被复制的那个串）将问题变成一个后缀数组可以解决的判定性问题。首先判断k能否被n整除，然后只要看lcp(1,k+1)（实际在用c写程序时是lcp(0,k)）是否为n-k就可以了。

为什么这样就行了呢？这要充分考虑到后缀的性质。当lcp（1，k+1）=n-k时，后缀k+1是后缀1（即整个字符串）的一个前缀。（因为后缀k+1的长度为n-k）那么，后缀1的前k个字符必然和后缀k+1的前k个字符对应相同。而后缀1的第k+1..2k个字符，又相当于后缀k+1的前k个字符，所以与后缀1的前k个字符对应相同，且和后缀k的k+1..2k又对应相同。依次类推，只要lcp(1,k+1)=n-k,那么s[1..k]就可以通过自复制n/k次得到整个字符串。找出k的最小值，就可以得到n/k的最大值了。

题目及题解：http://hi.baidu.com/fhnstephen/blog/item/5d79f2efe1c3623127979124.html

8、求两个字符串的最长公共子串。Pku2774、Ural1517

首先区分好“最长公共子串”和“最长公共子序列”。前者的子串是连续的，后者是可以不连续的。

对于两个字符串的问题，一般情况下均将它们连起来，构造height数组。然后，最长公共子串问题等价于后缀的最长公共前缀问题。只不过，并非所有的lcp值都能作为问题的答案。只有当两个后缀分属两个字符串时，它们的lcp值才能作为答案。与问题3一样，本题的答案必然是某个height值，因为lcp值是某段height值中的最小值。当区间长度为1时，lcp值等于某个height值。所以，本题只要扫描一遍后缀，找出后缀分属两个字符串的height值中的最大值就可以了。判断方法这里就不说明了，留给大家自己思考...

题目及题解：

http://hi.baidu.com/fhnstephen/blog/item/8666a400cd949d7b3812bb44.html

http://hi.baidu.com/fhnstephen/blog/item/b5c7585600cadfc8b645aebe.html

9、重复次数最多的重复子串 SPOJ 687，Pku3693

难度比较大的一个问题，主要是罗穗骞的论文里的题解写得有点含糊不清。题目的具体含义可以去参考Pku3693.

又是一题难以通过二分枚举答案解决的问题（因为要求的是重复次数），所以选择朴素枚举的方法。先枚举重复子串的长度k，再利用后缀数组来求长度为k的子串最多重复出现多少次。注意到一点，假如一个字符串它重复出现2次（这里不讨论一次的情况，因为那是必然的），那么它必然包含s[0],s[k],s[2*k]...之中的相邻的两个。所以，我们可以枚举一个数i，然后判断从i*k这个位置起的长度为k的字符串能重复出现多少次。判断方法和8中的相似，lcp(i*k,(i+1)*k)/k+1。但是，仅仅这样会忽略点一些特殊情况，即重复子串的起点不在[i*k]位置上时的情况。这种情况应该怎么求解呢？看下面这个例子：

aabababc

当k=2，i=1时，枚举到2的位置，此时的重复子串为ba(注意第一位是0),lcp(2，4)=3，所以ba重复出现了2次。但实际上，起始位置为1的字符串ab出现次数更多，为3次。我们注意到，这种情况下，lcp(2,4)=3，3不是2的整数倍。说明当前重复子串在最后没有多重复出现一次，而重复出现了部分（这里是多重复出现了一个b）。如果我这样说你没有看懂，那么更具体地：

sa[2]=bababc

sa[4]=babc

lcp=bab

现在注意到了吧，ba重复出现了两次之后，出现了一个b，而a没有出现。那么，不难想到，可以将枚举的位置往前挪一位，这样这个最后的b就能和前面的一个a构成一个重复子串了，而假如前挪的一位正好是a，那么答案可以多1。所以，我们需要求出a=lcp(i*k,(i+1)*k)%n，然后向前挪k-a位，再用同样的方法求其重复出现的长度。这里，令b=k-a,只需要lcp(b,b+k)>=k就可以了。实际上，lcp(b,b+k)>=k时，lcp(b,b+k)必然大于等于之前求得的lcp值，而此时答案的长度只加1。没有理解的朋友细细体会下上图吧。

题目及题解：http://hi.baidu.com/fhnstephen/blog/item/870da9ee3651404379f0555f.html

10.多个串的公共子串问题 PKU3294

首先将串连接起来，然后构造height数组，然后怎么办呢？

对，二分答案再判断是否可行就行了。可行条件很直观：有一组后缀，有超过题目要求的个数个不同的字符串中的后缀存在。即，假如题目要求要出现在至少k个串中，那么就得有一组后缀，在不同字符串中的后缀数大于等于k。

题目及题解：http://hi.baidu.com/fhnstephen/blog/item/49c3b7dec79ec5e377c638f1.html

11、出现或反转后出现所有字符串中的最长子串 PKU1226

http://hi.baidu.com/fhnstephen/blog/item/7fead5020a16d2da267fb5c0.html

12、不重叠地至少两次出现在所有字符串中的最长子串

spoj220http://hi.baidu.com/fhnstephen/blog/item/1dffe1dda1c98754cdbf1a35.html

之所以把两题一起说，因为它们大同小异，方法在前面的题目均出现过。对于多个串，连起来；反转后出现，将每个字符串反写后和原串都连起来，将反写后的串和原串看成同一个串；求最长，二分答案后height分组；出现在所有字符串中（反写后的也行），判断方法和10一样，k=n而已；不重叠见问题4，只不过这里对于每个字符串都要进行检验而已。

13、两个字符串的重复子串个数。 Pku3415

我个人觉得颇有难度的一个问题。具体的题目描述参看Pku3415。

大家可以移步到这：http://hi.baidu.com/fhnstephen/blog/item/bf06d001de30fc034afb51c1.html

14、最后的总结

用后缀数组解题有着一定的规律可循，这是后缀的性质所决定的，具体归纳如下：

[1] N个字符串的问题（N>1）

方法：将它们连接起来，中间用不会出现在原串中的，互不相同的，非0号字符分隔开。

[2] 无限制条件下的最长公共子串（重复子串算是后缀们的最长公共前缀）

方法：height的最大值。这里的无限制条件是对子串无限制条件。最多只能是两个串的最长公共子串，才可以直接是height的最大值。

[3] 特殊条件下的最长子串

方法：二分答案，再根据height数组进行分组，根据条件完成判定性问题。三个或以上的字符串的公共子串问题也需要二分答案。设此时要验证的串长度为len，特殊条件有：

<3.1> 出现在k个串中

条件：属于不同字符串的后缀个数不小于k。（在一组后缀中，下面省略）

<3.2> 不重叠

条件：出现在同一字符串中的后缀中，出现位置的最大值减最小值大于等于len。

<3.3> 可重叠出现k次

条件：出现在同一字符串中的后缀个数大于等于k。若对于每个字符串都需要满足，需要逐个字符串进行判断。

[4] 特殊计数

方法：根据后缀的性质，和题目的要求，通过自己的思考，看看用后缀数组能否实现。一般和“子串”有关的题目，用后缀数组应该是可以解决的。

[5] 重复问题

知道一点：lcp(i,i+k)可以判断，以i为起点，长度为k的一个字符串，它向后自复制的长度为多少，再根据具体题目具体分析，得出算法即可。

21、后缀树

后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀树提出的目的是用来支持有效的字符串匹配和查询。

学习后缀树之前，先了解一下Trie这个数据结构Trie是一种搜索树，可用于存储并查找字符串。Trie每一条边都对应一个字符。在Trie中查找字符串S时，只要按顺序枚举S的各个字符，从Trie的根节点开始选择相应的边走，如果枚举完的同时恰好走到Trie树的叶子节点，说明S存在于Trie中。如果未到达叶子节点，或者枚举中未发现相应的边，则S没有被包含在Trie中。

后缀树就是一种压缩后的Trie树。

比如 S：banana，对S建立后缀树。

首先给出S的后缀们

0：banana

1：anana

2：nana

3：ana

4：na

5：a

6：空

为了更清楚的表示后缀，我们在后缀的后面加上$

0：banana$

1：anana$

2：nana$

3：ana$

4：na$

5：a$

6：$

然后对其进行分类：

5:a$

3:ana$

1:anana$

0:banana$

4:na$

2:nana$

6: $

后缀树的应用：

example 1：在树中查找an(查找子字符串)

example 2：统计S中出现字符串T的个数

每出现一次T，都对应着一个不同的后缀，而这些后缀们又对应着同一个前缀T，因此这些后缀必定都属于同一棵子树，这棵子树的分支数就是T在S中出现的次数。

example 3：找出S中最长的重复子串，所谓重复子串，是指出现了两次以上。首先定义节点的“字符深度” = 从后缀树根节点到每个节点所经过的字符串总长。找出有最大字符深度的非叶节点。则从根节点到该非叶节点所经过的字符串即为所求。

后缀树的用途，总结起来大概有如下几种 :

1. 查找字符串o是否在字符串S中

方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。

原理：若o在S中，则o必然是S的某个后缀的前缀。

听起来有点拗口，举个例子。例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀。有了这个前提，采用trie搜索的方法就不难理解了。

2. 指定字符串T在字符串S中的重复次数

方案：用S+'$'构造后缀树，搜索T节点下的叶节点数目即为重复次数 。

原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。

3. 字符串S中的最长重复子串

方案：原理同2，具体做法就是找到最深的非叶节点。

这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。

4. 两个字符串S1，S2的最长公共部分

方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。大体原理同3。

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

后缀树的存储：为了节省空间，我们不在边上存储字符串，而是存储该字符串在原串中的起止位置，空间复杂度O（n）。

后缀树的构造：最简单的方法，使用Trie的构造方法，时间复杂度为O（n^2）；

后缀树也可以在O（n）的时间复杂度内构造，但比较复杂。

如，基本思路：先向后缀树中插入最长的后缀串（S本身），其次插入次长的后缀串，以此类推，最后插入空串。定义后缀链接（Suffix Link）=从节点A指向节点B的指针，B所表示的子串是A所表示的子串的最长后缀。既，根节点到A所经过的字符串s=aw，则从根节点到B所经过的字符串为w。

算法所用符号描述：

后缀树的构造，算法流程：

1）定义SL（root）=root，首先插入S，此时后缀树仅有两个节点。

2）设已经插入了S(i),现在要插入S（i+1），分两种情况讨论：

1：P（S（i））在插入之前已经存在，（如，na，ana，a是na的parent），则P（S（i））有后缀链接，令u=SL（P（S（i））），从u开始沿着树往下查找，在合适的地方插入。

2：P（S（i））是插入S（i）过程中产生的，此时G（S（i））必定存在并有后缀链接，比如（na，ana，bana），令u=SL（G（S（i））），w=W(G（S（i））,P（S（i））).从u开始，对w进行快速定位， 在合适的地方插入新的节点。

不断重复以上步骤，即可完成后缀树的构造。

后缀树代码如下：

//SuffixTree.h
typedef struct node //声明节点的结构

{

string strdata; //存储节点上的字符串

vector<node*> Child; //存储该节点的子节点的地址

int flag; //辅助标志位,用0和1表示该节点是否有子节点

int breakpoint; //辅助变量,当该节点需要分裂时,用于记录分裂点的位置

}*mynode;

classCSuffixTree

{

public:

mynode ST; //ST生成的后缀树的根节点

mynode point; //point节点指针，搜索时指向搜索节点的父节点，搜索结束时根据搜索

//结果指向要操作的节点

CSuffixTree(string str);

~CSuffixTree(void);

int Search(string str);

void CreatTree();

void Show(mynode ST);

void PrintNode(mynode p, int c, vector<BOOL>& isend);

private:

string data; //data源字符串变量，在构造函数中初始化

string left; //left用于记录每次搜索结束后，目标字符串中的剩余字符串

};

//SuffixTree.cpp
//构造函数，初始化data变量和ST,point指针并产个根节点的第一个子节点，ST的flag置1

CSuffixTree::CSuffixTree(stringstr)

{

data = str;

ST = (mynode) new node;

point = (mynode) new node;

point->strdata = data[0];

point->flag = 0;

ST->Child.push_back(point);

ST->flag = 1;

}

//析构函数

CSuffixTree::~CSuffixTree(void)

{

}

voidCSuffixTree::CreatTree()

{

int i, j, n, h, ic, jc;

string temp;

string tempuse;

mynode cnode;

for (i = 1; i <= (data.length()-1); i++)//调用两层循环，产生目标字符串每一个前缀的所 有后缀

{

for (j = 0; j <= i; j++)

{

temp.erase(temp.begin(),temp.end());

ic = i;

jc = j;

for (; jc <= ic; jc++)

{

temp.insert(temp.end(), data[jc]);

}

n = Search(temp); //调用Search函数搜索生成的字符串

switch (n)

{

case (-1)://分裂节点，父分裂点为point->breakpoint

tempuse =point->strdata;

cnode=(mynode) new node;

if (point->Child.size() !=0)

{

cnode->Child =point->Child;

}

cnode->flag =point->flag;

point->Child.erase(point->Child.begin(),point->Child.end());

point->strdata.erase(point->strdata.begin(),point->strdata.end());

for (h = 0; h<(point->breakpoint); h++)

{

point->strdata.insert(point->strdata.end(),tempuse[h]);

}

for (h =(point->breakpoint); h <tempuse.length(); h++)

{

cnode->strdata.insert(cnode->strdata.end(), tempuse[h]);

}

point->Child.push_back(cnode);

cnode = (mynode) new node;

cnode->strdata = left;

cnode->flag = 0;

point->Child.push_back(cnode);

point->flag = 1;

break;

case (0)://do nothing

break;

case (1)://在叶节点point处追加left字符串

point->strdata =point->strdata+left;

break;

case (2)://在父节点point下添加子节点cnode

cnode = (mynode) new node;

cnode->strdata = left;

cnode->flag = 0;

point->Child.push_back(cnode);

point->flag = 1;

break;

}

}

}

}

//返回1: 则在指针point所指向的节点的strdata后追加 left字符串

//返回2: 则生成point所指向的节点的子节点，子节点的strdata值为left字符串

//返回0: 则donothing

//返回-1:则分裂节点将分裂点写入point指针所指向的 节点的breakpoint，并将目标字符串的剩余字符串写入left

intCSuffixTree::Search(string str)

{

stack<char> s;

int i, n = 0;

mynode child;

char target;

point = ST; //初始搜索位置为根

child = NULL;

for (i = (str.length()-1); i >= 0; i--)//将目标字符串str压栈

{

s.push(str[i]);

}

while(!s.empty())//直到搜索完str串

{

//寻找point所指向的节点下与str首字母相同的子节点

for (i = 0; i <=(point->Child.size()-1); i++)

{

if(point->Child[i]->strdata[0] == s.top())

{

child =point->Child[i]; //child指针指向与str具有相同首字母的节点

break;

}

}

if (child == NULL)//父节点point下没有首字母相同的子节点

{ //将str中剩余的字符串保存在left中

left.erase(left.begin(),left.end());

while(!s.empty())

{

left.insert(left.end(),s.top());

s.pop();

}

return (2);

}

target = s.top(); //

s.pop();

if (1)

{

//child节点下的每个字符与str中的字符顺序比较

for (i = 0; i <=(child->strdata.length()-1); i++)

{

if (child->strdata[i] ==target)

{

if (!s.empty())

{

target = s.top();

s.pop();

continue;

}

else return(0); //若str中的字符串先于strdata中的字符串完成比较，则说明该字符 //串已经包含在树中

}

else //比较中出现不同，需要分裂节点

{

point = child; //point指向要分裂的节点

left.erase(left.begin(),left.end()); //将str中剩余的字符串写入left

s.push(target);

while(!s.empty())

{

left.insert(left.end(),s.top());

s.pop();

}

point->breakpoint =i; //写入父节点point的分裂点

return (-1); //分裂节点

}

}

point = child; //走出循环则进行下一个节点的搜索

if (!point->flag)//判断刚刚搜索的是否为叶节点，若是则停止搜索

{

left.erase(left.begin(),left.end());

s.push(target);

while(!s.empty())

{

left.insert(left.end(),s.top());

s.pop();

}

return (1);

}

s.push(target);

child = NULL;

}

}

//字符串str搜索完成，仍没有到达叶节点，返回0

return(0);

}

voidCSuffixTree::Show(mynode m_pSTreeRoot)

{

vector<bool> bIsEnd;

bIsEnd.push_back(0);

cout << "Root" << endl;

for(int i = 0; i <(int)m_pSTreeRoot->Child.size(); i++)

{

if(i ==(int)m_pSTreeRoot->Child.size() - 1)

{

bIsEnd[0] = 1;

}

PrintNode(m_pSTreeRoot->Child[i], 1,bIsEnd);

}

cout << endl;

}

voidCSuffixTree::PrintNode(mynode p, int c, vector<bool>& isend)

{

for(int j=0; j<c; j++)

{

if(isend[j] == 0)

{

if(j != c-1)

cout << "│";

else

cout << "├";

}

else

{

if(j != c-1)

cout << " ";

else

cout << "└";

if(j != c-1)

cout << " ";

else

cout <<""; //最后一个

}

}

cout << " " <<p->strdata;

//if(p->Child.size() == 0)cout <<" (" << p->nIndex << ")";

cout << endl;

for(int i=0; i<(int)p->Child.size();i++)

{

if(isend.size() == c)

{

isend.push_back(0);

}

else

{

isend[c]=0;

}

if(i == (int)p->Child.size() - 1)

{

if(isend.size() == c)

isend.push_back(1);

else

isend[c]=1;

}

PrintNode(p->Child[i], c + 1,isend);

}

}

//mian.cpp

intmain(int argc, char* argv[])

{

string a;

cout << "Please input astring:";

cin >> a; //通过输入获得目标字符串a

CSuffixTree mytree(a); //产生CsuffixTree类的实例mytree

mytree.CreatTree(); //调用CreatTree方法创建一棵后缀树

mytree.Show(mytree.ST); //调用Show方法输出生成的后缀树

}

22、线索二叉树

（1）以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结构，叫做线索二叉链表；指向结点的线性前驱或者线性后继结点的指针叫做线索；加上线索的二叉树称为线索二叉树（Threaded Binary Tree）；对二叉树以某种次序(前序、中序、后序)遍历使其变为线索树的过程叫做线索化。

（2）［为什么要有线索二叉树］二叉树是一种非线性结构，对二叉树的遍历实际上是将二叉树这种非线性结构按某种需要转化为线性序列，以便以后在对二叉树进行某种处理时直接使用。因此如何保存遍历二叉树后得到的线性序列，以避免对二叉树的重复遍历，是一个需要解决的问题。　　

一种最简单的方法是将得到的遍历序列存放在另外的存储空间内，但这需要付出额外的存储花销。我们能不能在不增加存储空间的前提下，在原来二叉链表的存储空间内反映出某种遍历后结点的逻辑关系，即遍历后某个结点的直接前驱和直接后继呢？

另一种方法就是：当我们用标准形式存储一棵二叉树时，树中有一半以上的指针是空的。对于一棵具有n个结点的二叉树，如果按标准形式来存储，那么总共有2n个指针（用来存放左孩子、右孩子的指针）其中只有(n-1)个用来指向子结点，另外(n+1)个指针时空的。这显然是浪费，我们应该设法利用这些空的指针来实现保存遍历二叉树后得到的线性序列。

由此，我们产生了线索二叉树的概念。

线索二叉树主要是为了解决查找结点的线性前驱与后继不方便的难题。它只增加了两个标志性域，就可以充分利用没有左或右孩子的结点的左右孩子的存储空间来存放该结点的线性前驱结点与线性后继结点。两个标志性域所占用的空间是极少的，所有充分利用了二叉链表中空闲存的储空间。

对一棵给定的二叉树，按不同的遍历规则进行线索化所得到的线索树是不同的，分别用前序、中序、后序遍历规则，对给定二叉树进行线索化得到的二叉树，分别称之为前序线索树、中序线索树、后序线索树。

要实现线索二叉树，就必须定义二叉链表结点数据结构如下（定义请看代码）：

Lnode

Ltag

Data

Rtag

Rnode

说明：

1. Ltag=0时，表示Lnode指向该结点的左孩子；

2. Ltag=1时，表示Lnode指向该结点的线性前驱结点；

3. Rtag=0时，表示Rnode指向该结点的右孩子；

4. Rtag=1时，表示Rnode指向该结点的线性后继结点；

中序次序线索化二叉树算法：

中序次序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索；(具体看代码)

检索中序二叉树某结点的线性前驱结点的算法：

1. 如果该结点的Ltag=1,那么Lnode就是它的线性前驱；

2. 如果该结点的Ltag=0，那么该结点左子树最右边的尾结点就是它的线性前驱点；

（具体请看代码）

检索中序二叉树某结点的线性后继结点和算法：

1. 如果该结点的Rtag=1,那么Rnode就是它的线性后继结点；

2. 如果该结眯的Rtag=0,那么该结点右子树最左边的尾结点就是它的线性后继结点

（具体请看代码）

解决方案中所有到二叉树的中序线索二叉树和中序线索链表的图

//二叉树线索化

//输入二叉树先序，建树，然后中序线索化，遍历输出

#include<iostream>

usingnamespace std;

enumPointerTag

{

Link,Thread //枚举值Link和Thread分别为0，1

};

structBiThrNode //线索二叉树的结点类型

{

char data;

PointerTag LTag; //左标志

PointerTag RTag; //右标志

BiThrNode *lchild; //左孩子指针

BiThrNode *rchild; //右孩子指针

};

typedefBiThrNode* BiThrTree;

BiThrNode*pre=NULL; //全局量

voidInOrderThreading(BiThrTree & Thrt,BiThrTree T);//线索化

voidInThreading(BiThrTree p);//中序遍历线索化

boolPreOrderCreatBiTree(BiThrTree &T);//先序建立树

voidInOrderTraverse_Thr(BiThrTree T);//中序遍历线索树

intmain()

{

BiThrTree T,Thrt;

printf("输入先序序列('#'表示空节点)建立二叉树：\n");

PreOrderCreatBiTree(T);//先序建立树

InOrderThreading(Thrt,T);//中序线索化

printf("中序线索化，中序遍历得中缀式：\n");

InOrderTraverse_Thr(Thrt);//中序遍历线索树

printf("\n");

return 0;

}

voidInOrderThreading(BiThrTree & Thrt,BiThrTree T)

{

Thrt=new BiThrNode;

Thrt->LTag=Link;

Thrt->RTag=Thread;

Thrt->rchild=Thrt;

if(!T) Thrt->lchild=Thrt;

else{

Thrt->lchild=T;

pre=Thrt;

InThreading(T);

pre->rchild=Thrt;

pre->RTag=Thread;

Thrt->rchild=pre;

}

}

voidInThreading(BiThrTree p)

{

if(p)

{

InThreading(p->lchild);

if(!p->lchild){ p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild){pre->RTag=Thread; pre->rchild=p; }

pre=p;

InThreading(p->rchild);

}

}

boolPreOrderCreatBiTree(BiThrTree &T)

{//该节点非空返回true，双亲节点对应标志Link，空时返回false，双亲节点对应标志应为Thread

char ch;

scanf("%c",&ch);

if(ch=='#')

{

T=NULL;

return false;

}else {

T=new BiThrNode;

T->data=ch;

if(PreOrderCreatBiTree(T->lchild))T->LTag=Link; //左孩子存在则左标志为Link

else T->LTag=Thread;

if(PreOrderCreatBiTree(T->rchild))T->RTag=Link; //右孩子存在则右标志为Link

else T->RTag=Thread;

}

return true;

}

voidInOrderTraverse_Thr(BiThrTree T)

{

BiThrNode *p;

p=T->lchild;

while(p!=T)

{

while(p->LTag==Link) p=p->lchild;

printf("%c", p->data);

while(p->RTag==Thread &&p->rchild!=T) //if(p->RTag==Thread && p->rchild!=T)

{

p=p->rchild;

printf("%c", p->data);

}

p=p->rchild;

}

}

23、二叉排序树(BST, Binary SortTree) 的C++实现

二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。

（1）二叉排序树定义：二叉排序树或者是空树，或者是满足如下性质的二叉树： 　　

①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 　　

②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 　　

③左、右子树本身又各是一棵二叉排序树。 　　

上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。 　　
（2）二叉排序树的特点 　　

由BST性质可得：

[1]二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。

[2]二叉排序树中，各结点关键字是惟一的。 注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质[1]里的"小于"改为"小于等于"，或将BST性质[2]里的"大于"改为"大于等于"，甚至可同时修改这两个性质。

[3]按中序遍历该树所得到的中序序列是一个递增有序序列。

(3)在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：

　　①在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是(n+1)/2。

　　②在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn。

　　③插入、删除和查找算法的时间复杂度均为O(lgn)。

(4)二叉排序树和二分查找的比较

就平均时间性能而言，二叉排序树上的查找和二分查找差不多。

就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(lgn)，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，则应选择二叉排序树作为其存储结构。

//二叉查找树代码

//BTreeNode.h二叉树结点抽象类型

#ifndefBTREENODE_H

#defineBTREENODE_H

#include<cstdlib>

//template<classT> class BTree;

template<classT> class SortBTree;

template<classT> class BTreeNode

{

//friend class BTree<T>;

friend class SortBTree<T>;

public:

BTreeNode():lchild(NULL),rchild(NULL){ };

BTreeNode(const T&dt,BTreeNode<T> *lch =NULL , BTreeNode<T> *rch = NULL)

:data(dt),lchild(lch),rchild(rch){};

T get_data()const {return data; };

BTreeNode<T>* get_lchild()const{return lchild; };

BTreeNode<T>* get_rchild()const{return rchild; };

void set_data(const T& d) { data =d;};

protected:

private:

T data;

BTreeNode<T> *lchild, *rchild;

};

#endif

/************************************************************************

*SortBTree.h

* 根据给定的字符串构造一个排序二叉树

* 从排序二叉树中寻找最大值，最小值，不存在时抛出invalid_argument异常

* 从排序二叉树中删除某一元素，不存在时抛出invalid_argument 异常

* 往排序二叉树中添加一个新元素

************************************************************************/

#ifndefSORTBTREE_H

#defineSORTBTREE_H

#include"BTreeNode.h"

#include<cstdlib>

#include<stdexcept>

template<classT>

classSortBTree

{

public:

SortBTree(T* p , int n);

const T& max()const; // return themaximum

const T& min()const; // return theminimum

BTreeNode<T>* find_data(const T&data)const; //return the node of data, if data is not exist, throw error

//delete the node of data, if data is notexist, throw error

void delete_data(const T& data) {delete_data(root,data); };

void insert_data(const T& data) { insert_data(root,data);};

BTreeNode<T>* get_root()const {returnroot; }; // return the root of tree

void display()const { display(root,visit); cout <<endl;}; // print the data of tree

protected:

static void insert_data(BTreeNode<T> *&root, const T& ndata); //这里必须是对指针的引用,切记，切记

static BTreeNode<T>*find_data(BTreeNode<T>* r,const T& data);

static void delete_node(BTreeNode<T>* &p);

static void delete_data(BTreeNode<T>*&r, const T& data);

static void display(BTreeNode<T>*p,void visit(BTreeNode<T>* p));

private:

BTreeNode<T> *root;

};

//constructionfunction

template<classT>

SortBTree<T>::SortBTree(T*p, int n)

{

root = new BTreeNode<T>;

root = NULL; //注意这行很必要，BTreeNode没有默认设置为NULL的构造函数

for(int i = 0; i != n; ++i)

{

insert_data(root,p[i]);

}

}

//insert a new data

template<classT>

voidSortBTree<T>::insert_data(BTreeNode<T> *&rt,const T& ndata)

{

if(rt == NULL)

{

rt = newBTreeNode<T>(ndata,NULL,NULL);

//rt->data = ndata; //这三条语句不等于上面那条

//rt->lchild = NULL; //用这三条语句是错的

//rt->rchild = NULL;

}

else if(rt->data == ndata) return;

else if(rt->data > ndata)insert_data(rt->lchild, ndata);

else insert_data(rt->rchild, ndata);

}

//delete a node from tree(improved)

// 如果p没有左子树，则让p的右子树的根代替p即可。

// 如果p有左子树，找出左子树中结点值最大的节点temp(最右下角的结点，也是中序遍历最后一个结点， 他没有右子树)

// 用temp的结点值替换下p的结点值

// 删除temp(因为temp的右子树为空，从而直接用其左子树根代替本身就可达到删除结点的目的)

// 注： 一般的方法用temp替换p，但是这样可能导致树很不平衡。

template<classT>

voidSortBTree<T>::delete_node(BTreeNode<T> * &p)

{

if(p == NULL) cout << "There isnot this node." <<endl;

else if(p->lchild == NULL) p =p->rchild;

else

{

BTreeNode<T>* temp = p;

//记录左子树中序遍历的最后一个结点（值最大的点）

while(temp->rchild != NULL)

temp = temp->rchild;

//删除这个结点，等价于用这个结点的做子树代替这个结点（因为这个结点没有右子树）

BTreeNode<T>* parent;

parent = temp;

while(parent->rchild != NULL)

{

parent = temp;

temp = temp->rchild;

}

parent = temp->lchild;

p->set_data(temp->data);

}

}

//deletea data

template<classT>

voidSortBTree<T>::delete_data(BTreeNode<T>* &root, const T&data)

{

if(root == NULL)

throw std::invalid_argument("Thisdata is not exsit.");

else if(root->data == data)delete_node(root);

else if(root->data > data)delete_data(root->lchild,data);

else delete_data(root->rchild,data);

}

//find a specific data

template<classT>

BTreeNode<T>* SortBTree<T>::find_data(BTreeNode<T>*r,const T& data)

{

if(r == NULL) return r;

else if(r->data == data) return r; //注意这两行是不能合并在一起的，不然可能会出现NULL->data呢

else if(r->data > data) returnfind_data(r->lchild,data);

else return find_data(r->rchild,data);

}

//find a specific data in tree

template<classT>

BTreeNode<T>*SortBTree<T>::find_data(const T& data)const

{

if(find_data(root,data) == NULL)

throw std::invalid_argument("Thisdata is not exist.");

else

return find_data(root,data);

}

//return the maximum value

template<classT>

constT& SortBTree<T>::max()const

{

if(root == NULL)

throw std::invalid_argument("Thisis an empty Tree.");

else

{

BTreeNode<T> *q = root;

while(q->rchild != NULL)

q = q->rchild;

return q->data;

}

}

//returnthe minimum value

template<classT>

constT& SortBTree<T>::min()const

{

if(root == NULL)

throw std::invalid_argument("Thisis an empty Tree.");

else

{

BTreeNode<T> *q = root;

while(q->lchild != NULL)

q = q->lchild;

return q->data;

}

}

//printthe sort tree

template<class T>

voidSortBTree<T>::display(BTreeNode<T>*p, voidvisit(BTreeNode<T>* p))

{

if(p != NULL)

{

display(p->lchild,visit);

visit(p);

display(p->rchild,visit);

}

}

#endif

24、平衡二叉树（就等于平衡二叉查找树？？等于AVL树？？）

（1）定义：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

（2）构造与调整方法　

平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树、左偏树等。

红黑树：红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 LeoJ. Guibas 和 RobertSedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

AVL：AVL是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

Treap：Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。

伸展树：伸展树（Splay Tree）是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

左偏树：堆结构是一种隐式数据结构（implicit data structure），用完全二叉树表示的堆在数组中是隐式存贮的（即没有明确的指针或其他数据能够重构这种结构）。由于没有存贮结构信息，这种描述方法空间利用率很高，事实上没有空间浪费。尽管堆结构的时间和空间效率都很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时。因此需要借助于其他数据结构来实现这类应用，左偏树（leftist
tree）就能满足这种要求。

(3)平衡二叉树

为了保证二叉排序树的高度为lgn，从而保证然二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn)，在往树中插入或删除结点时，要调整树的形态来保持树的"平衡。使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn)，从而确保树上的基本操作在最坏情况下的时间均为O(lgn)。

注意：

　 ①平衡二叉树(BalancedBinary Tree)是指树中任一结点的左右子树的高度大致相同。

　②任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。

　③平衡的二叉排序树指满足BST性质的平衡二叉树。

　④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn，AVL树是接近最优的。

//AVL代码

#ifndefAVL_TREE_H

#defineAVL_TREE_H

#include"dsexceptions.h"

#include<iostream> // For NULL

usingnamespace std;

//AvlTree class

//

//CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds

//

//******************PUBLIC OPERATIONS*********************

//void insert( x ) --> Insert x

//void remove( x ) --> Remove x(unimplemented)

//bool contains( x ) --> Return trueif x is present

//Comparable findMin( ) --> Returnsmallest item

//Comparable findMax( ) --> Returnlargest item

//boolean isEmpty( ) --> Return trueif empty; else false

//void makeEmpty( ) --> Remove allitems

//void printTree( ) --> Print treein sorted order

//******************ERRORS********************************

//Throws UnderflowException as warranted

template<typename Comparable>

classAvlTree

{

public:

AvlTree( ) : root( NULL ) { }

AvlTree( const AvlTree & rhs ) : root(NULL )

{

*this = rhs;

}

~AvlTree( )

{

makeEmpty( );

}

/**

* Find the smallest item in the tree.

* Throw UnderflowException if empty.

*/

const Comparable & findMin( ) const

{

if( isEmpty( ) )

throw UnderflowException( );

return findMin( root )->element;

}

/**

* Find the largest item in the tree.

* Throw UnderflowException if empty.

*/

const Comparable & findMax( ) const

{

if( isEmpty( ) )

throw UnderflowException( );

return findMax( root )->element;

}

/**

* Returns true if x is found in the tree.

*/

bool contains( const Comparable & x )const

{

return contains( x, root );

}

/**

* Test if the tree is logically empty.

* Return true if empty, false otherwise.

*/

bool isEmpty( ) const

{

return root == NULL;

}

/**

* Print the tree contents in sorted order.

*/

void printTree( ) const

{

if( isEmpty( ) )

cout << "Emptytree" << endl;

else

printTree( root );

}

/**

* Make the tree logically empty.

*/

void makeEmpty( )

{

makeEmpty( root );

}

/**

* Insert x into the tree; duplicates areignored.

*/

void insert( const Comparable & x )

{

insert( x, root );

}

/**

* Remove x from the tree. Nothing is doneif x is not found.

*/

void remove( const Comparable & x )

{

cout << "Sorry, removeunimplemented; " << x <<

" still present"<< endl;

}

/**

* Deep copy.

*/

const AvlTree & operator=( constAvlTree & rhs )

{

if( this != &rhs )

{

makeEmpty( );

root = clone( rhs.root );

}

return *this;

}

private:

struct AvlNode

{

Comparable element;

AvlNode *left;

AvlNode *right;

int height;

AvlNode( const Comparable &theElement, AvlNode *lt,

AvlNode *rt, int h = 0 )

: element( theElement ), left( lt ),right( rt ), height( h ) { }

};

AvlNode *root;

/**

* Internal method to insert into asubtree.

* x is the item to insert.

* t is the node that roots the subtree.

* Set the new root of the subtree.

*/

void insert( const Comparable & x,AvlNode * & t )

{

if( t == NULL )

t = new AvlNode( x, NULL, NULL );

else if( x < t->element )

{

insert( x, t->left );

if( height( t->left ) - height(t->right ) == 2 )

if( x <t->left->element )

rotateWithLeftChild( t );

else

doubleWithLeftChild( t );

}

else if( t->element < x )

{

insert( x, t->right );

if( height( t->right ) - height(t->left ) == 2 )

if( t->right->element< x )

rotateWithRightChild( t );

else

doubleWithRightChild( t );

}

t->height = max( height( t->left), height( t->right ) ) + 1;

}

/**

* Internal method to find the smallestitem in a subtree t.

* Return node containing the smallestitem.

*/

AvlNode * findMin( AvlNode *t ) const

{

if( t == NULL )

return NULL;

if( t->left == NULL )

return t;

return findMin( t->left );

}

/**

* Internal method to find the largest itemin a subtree t.

* Return node containing the largest item.

*/

AvlNode * findMax( AvlNode *t ) const

{

if( t != NULL )

while( t->right != NULL )

t = t->right;

return t;

}

/**

* Internal method to test if an item is ina subtree.

* x is item to search for.

* t is the node that roots the tree.

*/

bool contains( const Comparable & x,AvlNode *t ) const

{

if( t == NULL )

return false;

else if( x < t->element )

return contains( x, t->left );

else if( t->element < x )

return contains( x, t->right );

else

return true; // Match

}

/****** NONRECURSIVEVERSION*************************

bool contains( const Comparable & x,AvlNode *t ) const

{

while( t != NULL )

if( x < t->element )

t = t->left;

else if( t->element < x )

t = t->right;

else

return true; // Match

return false; // No match

}

*****************************************************/

/**

* Internal method to make subtree empty.

*/

void makeEmpty( AvlNode * & t )

{

if( t != NULL )

{

makeEmpty( t->left );

makeEmpty( t->right );

delete t;

}

t = NULL;

}

/**

* Internal method to print a subtreerooted at t in sorted order.

*/

void printTree( AvlNode *t ) const

{

if( t != NULL )

{

printTree( t->left );

cout << t->element<< endl;

printTree( t->right );

}

}

/**

* Internal method to clone subtree.

*/

AvlNode * clone( AvlNode *t ) const

{

if( t == NULL )

return NULL;

else

return new AvlNode( t->element,clone( t->left ), clone( t->right ), t->height );

}

// Avl manipulations

/**

*Return the height of node t or -1 if NULL.

*/

int height( AvlNode *t ) const

{

return t == NULL ? -1 : t->height;

}

int max( int lhs, int rhs ) const

{

return lhs > rhs ? lhs : rhs;

}

/**

* Rotate binary tree node with left child.

* For AVL trees, this is a single rotationfor case 1.

* Update heights, then set new root.

*/

void rotateWithLeftChild( AvlNode * &k2 )

{

AvlNode *k1 = k2->left;

k2->left = k1->right;

k1->right = k2;

k2->height = max( height(k2->left ), height( k2->right ) ) + 1;

k1->height = max( height(k1->left ), k2->height ) + 1;

k2 = k1;

}

/**

* Rotate binary tree node with rightchild.

* For AVL trees, this is a single rotationfor case 4.

* Update heights, then set new root.

*/

void rotateWithRightChild( AvlNode * &k1 )

{

AvlNode *k2 = k1->right;

k1->right = k2->left;

k2->left = k1;

k1->height = max( height(k1->left ), height( k1->right ) ) + 1;

k2->height = max( height(k2->right ), k1->height ) + 1;

k1 = k2;

}

/**

* Double rotate binary tree node: firstleft child.

* with its right child; then node k3 withnew left child.

* For AVL trees, this is a double rotationfor case 2.

* Update heights, then set new root.

*/

void doubleWithLeftChild( AvlNode * &k3 )

{

rotateWithRightChild( k3->left );

rotateWithLeftChild( k3 );

}

/**

* Double rotate binary tree node: firstright child.

* with its left child; then node k1 withnew right child.

* For AVL trees, this is a double rotationfor case 3.

* Update heights, then set new root.

*/

void doubleWithRightChild( AvlNode * &k1 )

{

rotateWithLeftChild( k1->right );

rotateWithRightChild( k1 );

}

};

#endif

25、Hash表(散列表)

（1）基本概念

若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

（2）常用的构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

[1]直接定址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数（这种散列函数叫做自身函数）

[2]数字分析法： 一般取一些大一点的素数，效果更好点。

[3]平方取中法:计算关键值再取中间r位形成一个2^r位的表

[4]折叠法:把所有字符的ASCII码加起来 (对于字符串)

[5]随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H（key）=random(key),其中random为随机函数。通常关键字长度不等时采用此法构造哈希函数较恰当。

[6]除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

[7]针对字符串的一些常用方法，比如ELFHash和BKDRHash（更易于编写，效率不错）

(3)处理冲突的方法

[1]开放定址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

di=1,2,3,…, m-1，称线性探测再散列；

di=1^2, -1^2, 2^2,-2^2,3^2, …, ±k^2,(k<=m/2)称二次探测再散列；

di=伪随机数序列，称伪随机探测再散列。

[2]再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

[3]链地址法(拉链法)

[4]建立一个公共溢出区

(4)查找的性能分析

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

[1]散列函数是否均匀；

[2]处理冲突的方法；

[3]散列表的装填因子。

散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

//简单的Hash表实现

#include <iostream>

template <typename _Type>

class HashTable

{

public:

HashTable(int Length)

{

Element = new _Type[Length];

for(int i=0;i<Length;i++)

Element[i] = -1;

this->Length = Length;

Count = 0;

}

~HashTable()

{

delete[] Element;

}

// Hash函数

virtual int Hash(_Type Data)

{

return Data % Length;

}

// 再散列法

virtual int ReHash(int Index,int Count)

{

return (Index + Count) % Length;

}

// 查找某个元素是否在表中

virtual bool SerachHash(_TypeData,int& Index)

{

Index = Hash(Data);

int Count = 0;

while(Element[Index] != -1 &&Element[Index] != Data)

Index = ReHash(Index,++Count);

return Data == Element[Index] ? true :false;

}

virtual int SerachHash(_Type Data)

{

int Index = 0;

if(SerachHash(Data,Index)) returnIndex;

else return -1;

}

// 插入元素

bool InsertHash(_Type Data)

{

int Index = 0;

if(Count < Length &&!SerachHash(Data,Index))

{

Element[Index] = Data;

Count++;

return true;

}

return false;

}

// 设置Hash表长度

void SetLength(int Length)

{

delete[] Element;

Element = new _Type[Length];

for(int i=0;i<Length;i++)

Element[i] = -1;

this->Length = Length;

}

// 删除某个元素

void Remove(_Type Data)

{

int Index = SerachHash(Data);

if(Index != -1)

{

Element[Index] = -1;

Count--;

}

}

// 删除所有元素

void RemoveAll()

{

for(int i=0;i<Length;i++)

Element[i] = -1;

Count = 0;

}

void Print()

{

for(int i=0;i<Length;i++)

printf("%d",Element[i]);

printf("\n");

}

protected:

_Type* Element; // Hash表

int Length; // Hash表大小

int Count; // Hash表当前大小

};

void main()

{

HashTable<int> H(10);

printf("Hash Length(10)Test:\n");

int Array[6] = {49,38,65,97,13,49};

for(int i=0;i<6;i++)

printf("%d\n",H.InsertHash(Array[i]));

H.Print();

printf("Find(97):%d\n",H.SerachHash(97));

printf("Find(49):%d\n",H.SerachHash(49));

H.RemoveAll();

H.SetLength(30);

printf("Hash Length(30)Test:\n");

for(int i=0;i<6;i++)

printf("%d\n",H.InsertHash(Array[i]));

H.Print();

printf("Find(97):%d\n",H.SerachHash(97));

printf("Find(49):%d\n",H.SerachHash(49));

system("pause");

}

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞