《程序员软考专用复习》由会员分享，可在线阅读，更多相关《程序员软考专用复习（99页珍藏版）》请在金锄头文库上搜索。
1、常考基础必知必会常考基础必知必会排序： 排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法;B. 查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别C. 链表和数组的区别，在什么情况下用链表什么情况下用数组D. 栈和队列的区别E. 多态，举例说明;overload 和 override 的区别F. 字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么的。strcpy 和 memcpyG. 继承、多继承H. 面向对象有什么好处I. 说说 static 的与众不同之处，如果一个变量被声明为 static，它会被分配在哪里在什么时候分配空间等J. 什么是虚函
2、数、纯虚函数、虚的析构函数，用途K. 内存泄漏及解决方法网络部分：网络部分：A.OSI 模型 7 层结构，TCP/IP 模型结构B. TCP/UDP 区别C. TCP 建立连接的步骤D. 香农定理二叉树三种遍历的非递归算法二叉树三种遍历的非递归算法( (背诵版背诵版) )1.1.先序遍历非递归算法先序遍历非递归算法#define maxsize 100typedef struct Bitree Elemmaxsize; int top;SqStack;void PreOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t; while (p!=nul
3、l | !StackEmpty(s) while (p!=null) 序遍历非递归算法#define maxsize 100typedef struct Bitree Elemmaxsize; int top;SqStack;void InOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t; while (p!=null | !StackEmpty(s) while (p!=null) 序遍历非递归算法#define maxsize 100typedef enumL,R tagtype;typedef struct Bitree ptr; tag
4、type tag;stacknode;typedef struct stacknode Elemmaxsize; int top;SqStack;ag=R) x = pop(s); p = ; visite(p-data); ag =R; tr-rchild; while (!StackEmpty(s);序遍历非递归算法#define maxsize 100typedef enumL,R tagtype;typedef struct Bitree ptr; tagtype tag;stacknode;typedef struct stacknode Elemmaxsize; int top;S
5、qStack;ag=R) x = pop(s); p = ; visite(p-data); ag =R; tr-rchild; while (!StackEmpty(s);串的基本概念，串与线性表的关系(串是其元素均为字符型数据的特殊线性表)，空串与空格串的区别，串相等的条件;2. 串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。3. 顺序串与链串及块链串的区别和联系，实现方式。4. KMP 算法思想。KMP 中 next 数组以及 nextval 数组的求法。明确传统模式匹配算法的不足，明确
6、next 数组需要改进。可能进行的考查方式是：求 next 和 nextval 数组值，根据求得的 next 或 nextval 数组值给出运用 KMP 算法进行匹配的匹配过程。5 5、多维数组和广义表、多维数组和广义表矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式： 三元组， 带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。6 6、树与二叉树、树与二叉树树一章的知识点包括：二叉树的概念、性质和存储结构，二叉树遍历的三种算法(递归与非递归)，在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索
7、化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。(1) 二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树(左右子树无序)的区别;考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：A.第 i 层的最多结点数，B.深度为 k 的二叉树的最多结点数，=n2+1 的性质，个结点的完全二叉树的深度，E. 顺序存储二叉树时孩子结点与父结点之间的换算关系(root从1开始，则左为：2*i，右为：2*i+1)。二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合
8、，二叉树的三叉链表表示方法。(2) 二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来(比如：求叶子个数)，所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。(3) 可在三种遍历算法的基础上改造完成的其它二叉树算法：求叶子个数
9、，求二叉树结点总数，求度为 1 或度为 2 的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为 n 的某个指定结点，删除值为 n 的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。(4) 线索二叉树：线索二叉树的引出， 是为避免如二叉树遍历时的递归求解。 众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题(如：查
10、找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题)。(5) 最优二叉树(哈夫曼树)：最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。(6) 树与森林：二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为 2 以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的!即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树。 树与森林的遍历，不像二叉树那样丰富，
11、他们只有两种遍历算法：先根与后根(对于森林而言称作：先序与后序遍历)。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟(称孩子兄弟链表)，而森林也是利用二叉链表存储孩子及兄弟。7 7、图、图1. 图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路， (强)连通图，(强)连通分量等概念。2. 图的几种存储形式：邻接矩阵，(逆)邻接表，十字链表及邻接多重表。在考
12、查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。3. 考查图的两种遍历算法：深度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为 K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。4. 生成树、最小生成树的概念以及最小生成树的构造：PRIM 算法和KRUSKAL 算法。考查时，一般不要求写出算法源码，而是要求根据这两种最小生成
13、树的算法思想写出其构造过程及最终生成的最小生成树。5. 拓扑排序问题：拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。6. 关键路径问题：这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径;二是最早时间是什么意思、如何求;三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。在实际设计关键路径的算法时，还应该注
14、意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为 0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。7. 最短路径问题：与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径(单源最短路径);二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用 DIJSKTRA 算法，解决第二个问题用 FLOYD 算法，注意区分。8 8、查找、查找(s
15、earch)(search)先弄清楚以下几个概念：关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区别;平均查找长度 ASL 的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的 ASL 值，应该记住。一般将 search 分为三类：在顺序表上的查找;在树表上的查找;在哈希表上的查找。(1) 线性表上的查找：主要分为三种线性结构：顺序表传统查找方法：逐个比较;有序顺序表二分查找法(注意适用条件以及其递归实现方法);索引顺序表对索引结构，采用索引查找算法。注意这三种表下的ASL 值以及三种算法的实现。(2) 树表上的查找：树表主要分为以下几种：二叉排序树(即二叉查找树)
16、，平衡二叉查找树(AVL 树)，B 树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考 B 树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树。二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉排序树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡排序二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于 1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。B 树是二叉
17、排序树的进一步改进， 也可以把 B 树理解为三叉、 四叉.排序树。 除 B 树的查找算法外， 应该特别注意一下 B 树的插入和删除算法，因为这两种算法涉及到 B 树结点的分裂和合并，是一个难点。 键树(keywordtree)，又称数字搜索树(digitalsearch tree)或字符树。trie 树也可说等同于键树或属于键树的一种。键树特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。(3) 基于哈希表的查找算法：哈希译自“hash”一词，意为“散列”或“杂凑”。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，
18、设计一个 function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。9 9、内部排序、内部排序考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否了如指掌。排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。(1)插入排序中又可分为：直接插入、折半插入、2 路插入()、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的
19、目的。(2)交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。(3)选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数;树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大(小)者，最终选出最小(大)数;而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。(4)归并排序，是通过“归并”这种操作完成排序的目
20、的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是 2 路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。(5)基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序(扑克牌排序)，链式排序(整数排序)。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的。.
21、1 这些个父节点选择元素时，就会破坏稳定性。有可能第 n/2 个父节点交换把后面一个元素交换过去了，而第 n/2-1 个父节点把后面一个相同的元素没有交换， 那么这 2 个相同的元素之间的稳定性就被破坏了。 所以，堆排序不是稳定的排序算法。冒泡排序冒泡排序 插入排序插入排序 二路插入排序二路插入排序 希尔排序希尔排序 快速排序快速排序 选择排序选择排序 归并归并排序排序 堆排序算法的堆排序算法的 C/C+C/C+实现实现#includeusing namespace std;m，Rm+1.high，先将它们合并到一个局部的暂存向量 R1(相当于输出堆)中，待合并完成后将 R1 复制回 Rlow
22、.high中。时间复杂度 o(nlogn)空间复杂度 o(n)比较次数*/void merge(int array,int i,int m, int n)int j, k;int iStart = i, iEnd = n;int arrayDest256;for ( j = m + 1,k = i; i = m& j = n; +k)if (arrayi arrayj)arrayDestk = arrayi+;elsearrayDestk = arrayj+;if (i = m)for (;k = n; k+,i+)arrayDestk = arrayi;if(j = n)for (;k =
23、n; k+,j+)arrayDestk = arrayj;for(j = iStart; j = iEnd; j+)arrayj = arrayDestj;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)这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于
24、(或者大于)它的父节点。时间复杂度 o(nlogn)空间复杂度 o(1)比较次数：较多*/void heap_adjust(int array,int i,int len)int rc = arrayi;for(int j = 2 * i; jif(j len & arrayj= arrayj) break;arrayi = arrayj; i = j;arrayi = 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);
25、 i 0; i-)swap(array0,arrayi); 内存空间占用的少，因为链表节点会附加上一块或两块下一个节点的信息。但是数组在建立时就固定了。所以也有可能会因为建立的数组过大或不足引起内存上的问题。B. 数组内的数据可随机访问，但链表不具备随机访问性。这个很容易理解，数组在内存里是连续的空间，比如如果一个数组地址从 100 到 200，且每个元素占用两个字节，那么 100-200 之间的任何一个偶数都是数组元素的地址，可以直接访问。链表在内存地址可能是分散的。所以必须通过上一节点中的信息找能找到下一个节点。C. 查找速度上。这个也是因为内存地址的连续性的问题，不罗索了。链表优于数组的
26、链表优于数组的: :A. 插入与删除的操作。如果数组的中间插入一个元素，那么这个元素后的所有元素的内存地址都要往后移动。删除的话同理。只有对数据的最后一个元素进行插入删除操作时，才比较快。链表只需要更改有必要更改的节点内的节点信息就够了。并不需要更改节点的内存地址。B. 内存地址的利用率方面。不管你内存里还有多少空间，如果没办法一次性给出数组所需的要空间，那就会提示内存不足，磁盘空间整理的原因之一在这里。而链表可以是分散的空间地址。C. 链表的扩展性比数组好。因为一个数组建立后所占用的空间大小就是固定的，如果满了就没法扩展，只能新建一个更大空间的数组;而链表不是固定的，可以很方便的扩展。121
27、2、C+C+操作符优先级操作符优先级: :记忆方法：记忆方法：去掉一个最高的，去掉一个最低的，剩下的是一、二、三、赋值;双目运算符中，顺序为算术、关系和逻辑，移位和逻辑位插入其中。-摘自C 语言程序设计实用问答问题：如何记住运算符的 15 种优先级和结合性解答： C 语言中运算符种类比较繁多， 优先级有 15 种， 结合性有两种。如何记忆两种结合性和 15 种优先级下面讲述一种记忆方法。结合性有两种，一种是自左至右，另一种是自右至左，大部分运算符的结合性是自左至右，只有单目运算符、三目运算符的赋值运算符的结合性自右至左。优先级有 15 种，记忆方法如下：记住一个最高的：构造类型的元素或成员以及
28、小括号。记住一个最低的：逗号运算符。剩余的是一、二、三、赋值意思是单目、双目、三目和赋值运算符。在诸多运算符中，又分为：算术、关系、逻辑。两种位操作运算符中，移位运算符在算术运算符后边，逻辑位运算符在逻辑运算符的前面。再细分如下：算术运算符*，/，%高于+，-。关系运算符中：，=，和from a pointerptr-age = 34;yesarray4 = 2;yesy) : _x(x), _y(y *yesleft torightyesleft tonorightExampleExampleloadaloadativitytivityAssociaAssocia1:Member acces
29、s.from an objectfor (int i = 0; i yes10; i+) cout yes0; i-) cout i;Y& y =dynamic_ Runtime-checkeddynamic_cast( nocasttype conversionx);Y& y =static_c Unchecked typestatic_cast(x noastconversion);int const* p =reinterp Reinterpretingreinterpret_cast(0x1234);int* q =const_ca Cast away/Addconst_cast( n
30、ostconstnessp);typeidGet typestd:type_infono = 34;no+Post-increment-Post-decrementinformationconst& t =typeid(x);!Logical negationAlternateif (!done) .yesnotspelling for !Bitwisecomplementflags = flags;Alternatecomplspelling for for (i = 0; i 10;yes+i) cout 0;yes-i) cout *selector4Member object.*sel
31、ector*5/%MultiplicationDivisionModulusint i = 2 * 4;float f = / ;yesleft toyesrightint rem = 4 % 3;yesobj.*var = 24;norightptr-*var = 24;yesleft to(int)floatNum;yes+6-AdditionSubtractionBitwise shiftint i = 2 + 3;int i = 5 - 1;int flags = 33 yesyesleft torightrightComparisonless-thanComparison=if (i
32、 1;yesleft torightyesyesless-than-or-eq if (i 42) .greater-thanComparisonyes8Comparison=greater-than-or if (i = 42) .yes-equal-toComparison=equal-to9Alternateeqspelling for =if (i = 42) .yesrightleft toComparison!=not-equal-toif (i != 42) .yesAlternatenot_eqspelling for !=&10bitandspelling for &Bitw
33、ise11exclusive OR(XOR)Alternatexorspelling for Bitwise|12inclusive(normal) ORAlternatebitorspelling for |&13andspelling for &Logical ANDif (conditionA &AlternateyesconditionB) .rightleft toleft toflags = flags | 42; yesrightleft toflags = flags 42; yesrightBitwise ANDleft toAlternateflags = flags &
34、42; yesright|14orLogical ORif (conditionA |Alternatespelling for |TernaryyesconditionB) .rightleft to15 :conditional(if-then-else)Assignmentint i = a b a :nob;right toleft=operatorIncrement and+=assignDecrement and-=assignMultiply and16*=assignDivide and/=assignModulo and%=assignint a = b;yesa += 3;
35、yesb -= 4;yesright toa *= 5;yeslefta /= 2;yesa %= 3;yesBitwise AND and flags &=&=assignnew_flags;yesAlternateand_eqspelling for &=Bitwise=exclusive or(XOR) and assignAlternatexor_eqspelling for =Bitwise normal|=OR and assignAlternateor_eqspelling for |=Bitwise shift=right and assignthrow17throwthrow
36、 exception EClass(“Message”);Sequential18,evaluationfor (i = 0, j = 0;yesi 10; i+,left torightnoflags =yesnew_flags;flags |=yesnew_flags;flags = 2;yesoperatorj+) .1313、B B 树、树、B-B-树、树、B+B+树、树、B*B*树、红黑树和树、红黑树和 trietrie 树树(1)B(1)B 树树: :即二叉搜索树即二叉搜索树. .1.所有非叶子结点至多拥有两个儿子(Left 和 Right);2.所有结点各存储一个关键字;3.非叶
37、子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树;如：如：B 树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中;否则，如果查询关键字比结点关键字小，就进入左儿子;如果比结点关键字大，就进入右儿子;如果左儿子或右儿子的指针为空，则报告找不到相应的关键字;如果 B 树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡)，那么 B 树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是，改变 B 树结构(插入与删除结点)不需要移动大段的内存数据，甚至通常是常数开销;如：如：但 B 树在经过多次插入与删除后，有可能导致不同的结构：右边也是一个 B 树
38、，但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以，使用 B 树还要考虑尽可能让 B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题;实际使用的 B 树都是在原 B 树的基础上加上平衡算法，即“平衡二叉树”;如何保持 B 树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在 B 树中插入和删除结点的策略;(2)B-(2)B-树树是一种多路搜索树(并不是二叉的), 多路平衡查找树：1.定义任意非叶子结点最多只有 M 个儿子;且 M2;2.根结点的儿子数为2, M;3.除根结点以外的非叶子结点的儿子数为M/2, M;4.每个结点存放至少 M/2-1
39、(取上整)和至多 M-1 个关键字;(至少 2 个关键字)5.非叶子结点的关键字个数=指向儿子的指针个数-1;6.非叶子结点的关键字：K1, K2, , KM-1;且 Ki Ki+1;7.非叶子结点的指针：P1, P2, , PM;其中 P1指向关键字小于 K1的子树，PM指向关键字大于 KM-1的子树，其它 Pi指向关键字属于(Ki-1, Ki)的子树;8.所有叶子结点位于同一层;如：如：(M=3)(M=3)B-树的搜索，从根结点开始，对结点内的关键字(有序)序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点;重复，直到所对应的儿子指针为空，或已经是叶子结点;B-B-树的
40、特性：树的特性：1.关键字集合分布在整颗树中;2.任何一个关键字出现且只出现在一个结点中;3.搜索有可能在非叶子结点结束;4.其搜索性能等价于在关键字全集内做一次二分查找;5.自动层次控制;由于限制了除根结点以外的非叶子结点，至少含有 M/2 个儿子，确保了结点的至少利用率，其最底搜索性能为：其中，M 为设定的非叶子结点最多子树个数，N 为关键字总数;所以 B-树的性能总是等价于二分查找(与 M 值无关)， 也就没有 B 树平衡的问题;由于 M/2 的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占 M/2 的结点;删除结点时，需将两个不足 M/2 的兄弟结点合并;(3)B+(3)B
41、+树树B+树是 B-树的变体，也是一种多路搜索树：1.其定义基本与 B-树同，除了：2.非叶子结点的子树指针与关键字个数相同;3.非叶子结点的子树指针 Pi，指向关键字值属于Ki, Ki+1)的子树(B-树是开区间);5.为所有叶子结点增加一个链指针;6.所有关键字都在叶子结点出现;如：如：(M=3)(M=3)B+的搜索与 B-树也基本相同， 区别是 B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中)，其性能也等价于在关键字全集做一次二分查找;B+B+的特性：的特性：1.所有关键字都出现在叶子结点的链表中(稠密索引)，且链表中的关键字恰好是有序的;2.不可能在非叶子结点命中;3.非叶子
42、结点相当于是叶子结点的索引(稀疏索引)，叶子结点相当于是存储(关键字)数据的数据层;4.更适合文件索引系统;(4)B*(4)B*树树是 B+树的变体，在 B+树的非根和非叶子结点再增加指向兄弟的指针;B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为 2/3(代替 B+树的 1/2);B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中 1/2 的数据复制到新结点，最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针;B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中
43、，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制 1/3 的数据到新结点，最后在父结点增加新结点的指针;所以，B*树分配新结点的概率比 B+树要低，空间使用率更高;(5)(5)红黑树红黑树红黑树(Red-Black Tree)是二叉搜索树(BinarySearch Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点之后都会花 O(log N)的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树
44、的查找方法与二叉搜索树完全一样;插入和删除节点的的方法前半部分节与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。map 就是采用红黑树存储的，红黑树(RB Tree)是平衡二叉树，其优点就是树到叶子节点深度一致， 查找的效率也就一样， 为 logN。 在实行查找，插入，删除的效率都一致，而当是全部静态数据时，没有太多优势，可能采用 hash 表各合适。相对来说，hash_map 是一个 hashtable 占用内存更多，查找效率高一些，但是 hash 的时间比较费时。总体而言，hash_map 查找速度会比 map快，而且查找速度基本和数据数据量大小无关，属于常数级别;而 map
45、 的查找速度是 log(n)级别。并不一定常数就比 log(n)小， hash 还有 hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map 可能会让你陷入尴尬，特别是当你的 hash_map 对象特别多时，你就更无法控制了，而且 hash_map 的构造速度较慢。现在知道如何选择了吗权衡三个因素: 查找速度, 数据量, 内存使用。红黑树的每个节点上的属性除了有一个 key、3 个指针：parent、lchild、rchild 以外，还多了一个属性：color。它
46、只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下 4 点性质：1. 根节点是黑色的。2. 空节点是黑色的(红黑树中，根节点的 parent 以及所有叶节点 lchild、rchild 都不指向 NULL，而是指向一个定义好的空节点)。3. 红色节点的父、左子、右子节点都是黑色。4. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。(6)trie(6)trie 树树Trie 树，即 Double Array 字典查找树，既可用于一般的字典搜索，也可用于索引查找。每个节点相当于 DFA 的一个状态，终止状态为查找结束。有序查找的过程相当于
47、状态的不断转换对于给定的一个字符串 a1,a2,a3,.,an.则采用 TRIE 树搜索经过 n 次搜索即可完成一次查找。不过好像还是没有 B 树的搜索效率高，B 树搜索算法复杂度为 logt(n+1/2).当 t 趋向大，搜索效率变得高效。TrieTrie 树的优点举例树的优点举例已知 n 个由小写字母构成的平均长度为 10 的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比 3 种方法：1. 最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为 O(n2)。2. 使用 hash：我们用 hash 存下所有字符串的所有的前缀子串。建立存有子
48、串 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
49、，没有，然后存入 9、91、911，查询 911456，没有然后存入 9114、91145、911456，而程序没有记忆功能，并不知道 911 在输入数据中出现过。所以用 hash必须先存入所有子串，然后 for 循环查询。而 trie 树便可以，存入 911 后，已经记录 911 为出现的字符串，在存入 911456 的过程中就能发现而输出答案;倒过来亦可以，先存入 911456，在存入 911 时，当指针指向最后一个 1 时，程序会发现这个 1 已经存在，说明 911 必定是某个字符串的前缀，该思想是我在做 pku 上的 3630中发现的，详见本文配套的“入门练习”。小结小结B 树：二叉树
50、，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点;B-树：多路搜索树，每个结点存储 M/2 到 M 个关键字，非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中;B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从 1/2 提高到 2/3;1414、最小生成树算法之、最小生成树算法之 PrimPrim 算法算法(C+(C+实现实现) )在无向带权连通图 G 中，如果一个连通子树
51、包含所有顶点，并且连接这些顶点的边权之和最小，那么这个连通子图就是 G 的最小生成树。求最小生成树的一个常见算法是 Prim 算法，该算法的基本思想是：1)设置两个集合 V 和 S，任意选择一个顶点作为起始顶点，将起始顶点放入集合 S，其余顶点存入集合 V 中;2)然后使用贪心策略，选择一条长度最短并且端点分别在 S 和 V 中边(即为最小生成树的中的一条边)， 将这条边在 V 中的端点加入到集合 S 中;3)循环执行第 2)步直到 S 中包含了所有顶点。根据以上思想我们很快可以给出一个 O(N3)的算法， 即选择一条最短边需要 O(N2)的时间复杂度，具体实现代码如下：.,n,cij为(i,
52、j)的权，打印最小生成树的每条边*/void prim (int cMAXVEXMAXVEX, int n)int i,j,k,min,lowcostMAXVEX,closestMAXVEX;for(i=2;i=n;i+) /*从顶点 1 开始*/lowcosti=c1i;closesti=1;closest1=0;for(i=2;i=n;i+) /*从 U 之外求离 U 中某一顶点最近的顶点*/min=MAXCOST;j=1;k=i;while(j=n)if(lowcostjmin=lowcostj;k=j;j+;printf(%d,%d),closestk,k); /*打印边*/close
53、stk=0;/* k 假如到 U 中 */for(j=2;j=n;j+)if(closestj!=0 & ckjLOWCOSTJ)lowcostj=ckj;closestj=k;问题：问题：-1) 为何两个 for 循环都是从下标 2 开始的尤其是第二个想不通。答：因为 Prim 算法可以任选起点，通常选定点 1 为起点，也就是说点 1 一开始就在 U 里面了，自然不必出现在第二个循环(在 V-U 中寻找点)中。2) lowcost 数组顾名思义知道是存放最小代价信息的数组， 但是具体的说 lowcost 放着是什么的最小代价，比如“lowcosti=c1i;”表示的是什么意思(我要带 i 的
54、语言描述)答：存放的是当前从点集 U 到点集 V-U 的最短边长，lowcosti = c1i是初始化，开始时点集 U 中只有点 1，因此当前点集 U 到点集 V-U的各最短边长 lowcosti就等于点 1 到点 i 的边权。3) closesti=1 又是什么含意呢答：closesti记录对应 lowcosti的边的起点，因为 lowcosti是当前终点为 i 的各条边中的最小值，再加上一个 closesti记录起点，就能确定最小生成树的边了。closesti = 1 是初始化，自然每一个边都是从点 1 出发的。4) 求教第二个 for 循环的整层循环是写什么，我要每一行的注释。到底是在作
55、什么答：for (i=2;ipy) rom);y=FindSet(p,edgei.to);if(x!=y)UnionSet(p,x,y);ans+=edgei.cost;if(edge_arr)edge_arrcnt=edgei;cnt+;if(cnt=n-1)return ans;return -1;1616、单源最短路径、单源最短路径(1)Dijkstra 算法可以用来解决非负权重网络的单源点最短路径。Dijkstra 算法的基本思想就是用贪心策略维护一棵最短路径生成树，先用 dist数组维护一个最短路径，distv表示起点 v0 与当前最短路径树中的顶点 v 的最短路径。选择下一个顶点时
56、，我们找一条边 ，x 属于当前最短路径树中的点，y 不属于当前最短路径树中的点，使得 distx+ w(x,y) 最小，将边 加入到最短路径树中，依次进行，最后求得就是从起点 v0 出发的最短路径。最短路径 dijsktra 算法模板：#includeusingnamespace std;constint maxint = 9999999;constint maxn = 1010;intdatamaxnmaxn;dij记录每对顶点间的最短距离;2.对每一个图中的顶点，以其作为基点扫描每一对 dij，检验是否通过该基点可以使得这对顶点间的距离变小。建立二叉最大堆;b. 由于最大值在根部，所以每次
57、取出根部值和最后一个节点交换，堆的 size 减 1，然后重新调整堆为最大堆，调整堆的复杂度为 o(lgn)。如何建立一个二叉最大堆呢根据完全二叉树的特点，可以知道有孩子的节点的节点下标是0, n/2-1,因此我们从 n/2-1 开始向上调整，使之符合父节点大于孩子节点这个最大堆的特点。只要建好最大堆，接下来就是步骤 2 了，注意调整堆要从根节点开始调整，堆的大小要减一。注意：我们的下标从 0 开始的堆排序源码：建哈夫曼代码：我们知道在构建哈夫曼树时，每次要选择集合中两个最小的元素，然后将元素值相加，合并为一个新节点，此时两个最小的元素的取出可以用HeapExtractMin 函数来实现，产出
58、的新节点需要插入到堆中，我们有 MinHeapInsert 函数来实现。2.计算大型浮点数集合的和：我们知道大浮点数和小浮点数相加，很可能会造成精度误差。所以可以每次从优先级队列中取出最小的两个数相加，和 1 的实现差不多。3.将多个小型有序文件合并到一个大型有序文件中：假设有 n 个小型有序文件，建立一个大小为 n 的最小堆，每个有序文件贡献一个(如果有的话)，每次取出最小值插入到大型文件中，并且去掉该最小元素，并将它在文件中的后续元素插入到堆中,能够在 o(lgn)的时间内从 n 个文件中选择要插入到大型文件中的元素。4.在具有 10 亿个数值的集合中找到 100 万个最大的数：建立 10
59、0 万个元素的最小二叉堆，后面的数和根部进行比较，如果大于根部，进行堆调整。m 遍扫描【算法基本描述】nm 遍扫描【算法复杂度】O(nm)【算法思想】每次都扫描一遍数组，取出最大元素，这样扫描 m 遍就能得到 m 个最大的数。2.排序后取最大 m 个数【算法基本描述】对 n 个数排序，对拍完序后的序列取 m 个最大的数【算法复杂度】视排序的复杂度，一般为 O(nlogn)或 O(n2)3.最小堆【算法基本描述】一遍扫描+最小堆【算法复杂度】O(nlogm) 遍历 O(n) 最小堆 O(logm)【算法伪代码】建立一个最小堆(优先队列)，最小堆的大小控制在 m 之内;for 每个数：if 这个数
60、比最小堆的堆顶元素大：弹出最小堆的最小元素，*把这个数插入到最小堆;最小堆中的 m 个元素就是所要求的元素;中最小堆的作用就是保持里面始终有 m 个最大元素，且 m 个元素中最小的元素在堆顶。【其他】如果要求 n 个数中取最小的 m 个，只要大顶堆即可总结：当 n 与 m 差不多大时，采用复杂度较低的排序是比较可取的，因为简单。当 mN 时，排序是很浪费时间的，因为我们不需要后(N-M)个数，所以可以采用最小堆的方法。我不敢说我的算法是最好的，但是它一定是一个复杂度较低的算法。使用用最小堆来找最大的 K 个数源码：1919、kmpkmp 算法算法voidget_nextval(const ch
61、ar *T, int next);intKMP(const char *Text,const char *Pattern) .len-1，可以发现不同的后缀按字典序排列的名词是不一样的(什么是字典序都应该知道吧)，记录这些后缀按字典序排好的结果的数组就叫后缀数组，一般用 sa表示，网络上对 sa的标准定义为：后缀数组：后缀数组 SA 是一个一维数组，它保存 1.n 的某个排列 SA1， SA2， ，SAn，并且保证 Suffix(SAi) Suffix(SAi+1)，1i另外还要用到排名数组，即某一位置的后缀在所有后缀中的排名的数组，一般用 Rank表示，容易发现 Ranksai=i。名次数组
62、：名次数组 Ranki保存的是 Suffix(i)在所有后缀中从小到大排列的“名次”。简单的说，后缀数组是“排第几的是谁”，名次数组是“你排第几”。知道了这些定义，剩下的就是如何构建后缀数组了，可以按照定义来构建，把每个后缀当做一个字符串，用全速排序来排序，不过那样的时间复杂度为 O(n*n)，一般用来构建后缀数组用的是倍增算法(Doubling Algorithm)，说到倍增算法，就要说到 k-前缀的定义，字符串 u 的 k-前缀就是 u 的从 0 开始到 k-1 的字串，u 长度不足 k 时就是整个字符串 u，这样一来我们在比较串 s 的两个位置 i,j 的后缀的 2k-前缀时，就是比较两
63、个后缀的 k-前缀和两个后缀位置+k 的 k-前缀，显然当 k=1 时就是对整个串的单字符进行排序，复杂度 O(nlogn)，当 k=2 时对已排好的 k-前缀进行排序，用快排，复杂度O(nlogn)，用基数排序，复杂度O(n)，容易发现 k是 2 倍增的。所以整个过程的时间复杂度就是 O(nlongn)。倍增算法构建 sa的代码如下：#definemax 10000intRxmax,Rymax,rxmax;intcmp(int *y,int a,int b,int l)return ya = yb & ya+l +yb+l;.有兴趣的朋友可以去钻研钻研再和我交流交流这里给出代码：intran
64、kmaxn,heightmaxn;void calheight(int*r,int *sa,int n)int i,j,k=0;for(i=1;i=n;i+) ranksai=i;for(i=0;ifor(kk-:0,j=saranki-1;ri+k=rj+k;k+);return;3、一些注意事项：height 数组的值应该是从 height1开始的，而且 height1应该是等于 0 的。原因是，因为我们在字符串后面添加了一个 0 号字符，所以它必然是最小的一个后缀。而字符串中的其他字符都应该是大于 0 的(前面有提到，使用倍增算法前需要确保这点)，所以排名第二的字符串和 0 号字符的公共
65、前缀(即 height1)应当为 0.在调用 calheight 函数时，要注意 height 数组的范围应该是1.n。所以调用时应该是 calheight(r,sa,n)而不是 calheight(r,sa,n+1)。 要理解清楚这里的 n的含义是什么。calheight 过程中， 对 rank 数组求值的 for 语句的初始语句是 i=1 而不是 i=0 的原因，和上面说的类似，因为 sa0总是等于那个已经失去作用的 0 号字符，所以没必要求出其 rank 值。当然你错写成 for (i=0.)，也不会有什么问题。(3) 后缀数组解题总结1、求单个子串的不重复子串个数。SPOJ 694、S
66、POJ 705.这个问题是一个特殊求值问题。要认识到这样一个事实：一个字符串中的所有子串都必然是它的后缀的前缀。(这句话稍微有点绕.)对于每一个 sai后缀，它的起始位置 sai，那么它最多能得到该后缀长度个子串(n-sai个)，而其中有 heighti个是与前一个后缀相同的，所以它能产生的实际后缀个数便是 n-sai-heighti。遍历一次所有的后缀，将它产生的后缀数加起来便是答案。2、后缀的最长公共前缀。(记为 lcp(x，y)这是 height 数组的最基本性质之一。具体的可以参看罗穗骞的论文。后缀 i 和后缀 j 的最长公共前缀的长度为它们在 sa 数组中所在排位之间的 height
67、 值中的最小值。 这个描述可能有点乱， 正规的说， 令 x=ranki,y=rankj，x3、最长重复子串(可重叠)要看到，任何一个重复子串，都必然是某两个后缀的最长公共前缀。因为，两个后缀的公共前缀，它出现在这两个后缀中，并且起始位置时不同的，所以这个公共前缀必然重复出现两次以上(可重叠)。而任何两个后缀的最长公共前缀为某一段 height 值中的最小值，所以最大为 height 值中的最大值(即某个 lcp(sai,sai+1)。所以只要算出 height 数组，然后输出最大值就可以了。4、最长重复不重叠子串 PKU1743这个问题和 3 的唯一区别在于能否重叠。加上不能重叠这个限制后，直
68、接求解比较困难，所以我们选择二分枚举答案，将问题转换为判定性问题。假设当时枚举的长度为 k，那么要怎样判断是否存在长度为 k 的重复不重叠子串呢首先，根据 height 数组，将后缀分成若干组，使得每组后缀中，后缀之间的 height 值不小于 k。这样分组之后，不难看出，如果某组后缀数量大于 1，那么它们之中存在一个公共前缀，其长度为它们之间的 height值的最小值。而我们分组之后，每组后缀之间 height 值的最小值大于等于 k。所以，后缀数大于 1 的分组中，有可能存在满足题目限制条件的长度不小于 k 的子串。只要判断满足题目限制条件成立，那么说明存在长度至少为 k 的合法子串。对于
69、本题，限制条件是不重叠，判断的方法是，一组后缀中，起始位置最大的后缀的起始位置减去起始位置最小的后缀的起始位置=k。满足这个条件的话，那么这两个后缀的公共前缀不但出现两次，而且出现两次的起始位置间隔大于等于 k，所以不会重叠。5、最长的出现 k 次的重复(可重叠)子串。 PKU3261使用后缀数组解题时，遇到“最长”，除了特殊情况外(如问题 3)，一般需要二分答案，利用 height 值进行分组。本题的限制条件为出现 k次。只需判断，有没有哪一组后缀数量不少于 k 就可以了。相信有了我前面问题的分析作为基础，这个应该不难理解。注意理解“不少于 k 次”而不是“等于 k 次”的原因。如果理解不了
70、，可以找个具体的例子来分析分析。6、最长回文子串 ural1297这个问题没有很直接的方法可以解决，但可以采用枚举的方法。具体的就是枚举回文子串的中心所在位置 i。注意要分回文子串的长度为奇数还是偶数两种情况分析。然后，我们要做的，是要求出以 i 为中心的回文子串最长为多长。利用后缀数组，可以设计出这样一种求法：求 i 往后的后缀与 i 往前的前缀的最长公共前缀。我这里的表述有些问题，不过不影响理解。要快速地求这个最长前缀，可以将原串反写之后接在原串后面。在使用后缀数组的题目中，连接两个(n 个)字符串时，中间要用不可能会出现在原串中，不一样的非 0 号的字符将它们隔开。这样可以做到不影响后缀
71、数组的性质。然后，问题就可以转化为求两个后缀的最长公共前缀了。具体的细节，留给大家自己思考.(懒.原谅我吧，都打这么多字了.一个多小时了啊 TOT)7、求一个串最多由哪个串复制若干次得到 PKU2406具体的问题描述请参考 PKU2406.这个问题可以用 KMP 解决， 而且效率比后缀数组好。利用后缀数组直接解决本题也很困难(主要是，就算二分答案，也难以解决转变而成的判定性问题。上题也是)，但可以同过枚举模板串的长度 k(模板串指被复制的那个串)将问题变成一个后缀数组可以解决的判定性问题。首先判断 k 能否被 n 整除，然后只要看 lcp(1,k+1)(实际在用 c写程序时是 lcp(0,k)
72、是否为 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,那么 s1.k就可以通过自复制 n/k 次得到整个字符串。找出 k 的最小值，就可以得到 n/k 的最大值了
73、。8、求两个字符串的最长公共子串。Pku2774、Ural1517首先区分好“最长公共子串”和“最长公共子序列”。前者的子串是连续的，后者是可以不连续的。对于两个字符串的问题，一般情况下均将它们连起来，构造 height数组。然后，最长公共子串问题等价于后缀的最长公共前缀问题。只不过，并非所有的 lcp 值都能作为问题的答案。只有当两个后缀分属两个字符串时，它们的 lcp 值才能作为答案。与问题 3 一样，本题的答案必然是某个height 值，因为 lcp 值是某段 height 值中的最小值。当区间长度为 1 时，lcp 值等于某个 height 值。所以，本题只要扫描一遍后缀，找出后缀分属
74、两个字符串的 height 值中的最大值就可以了。判断方法这里就不说明了，留给大家自己思考.9、重复次数最多的重复子串 SPOJ 687，Pku3693难度比较大的一个问题，主要是罗穗骞的论文里的题解写得有点含糊不清。题目的具体含义可以去参考 Pku3693.又是一题难以通过二分枚举答案解决的问题(因为要求的是重复次数)，所以选择朴素枚举的方法。先枚举重复子串的长度k，再利用后缀数组来求长度为 k 的子串最多重复出现多少次。注意到一点，假如一个字符串它重复出现 2 次(这里不讨论一次的情况，因为那是必然的)，那么它必然包含 s0,sk,s2*k.之中的相邻的两个。所以，我们可以枚举一个数 i，
75、然后判断从 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 的整数倍。说明当前重复子串在最后没有多重复出现一次，而重复出现了部
76、分(这里是多重复出现了一个 b)。如果我这样说你没有看懂，那么更具体地：sa2=bababcsa4=babclcp=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)必然大于
77、等于之前求得的 lcp 值，而此时答案的长度只加 1。没有理解的朋友细细体会下上图吧。10.多个串的公共子串问题 PKU3294首先将串连接起来，然后构造 height 数组，然后怎么办呢对，二分答案再判断是否可行就行了。可行条件很直观：有一组后缀，有超过题目要求的个数个不同的字符串中的后缀存在。即，假如题目要求要出现在至少 k 个串中，那么就得有一组后缀，在不同字符串中的后缀数大于等于 k。11、出现或反转后出现所有字符串中的最长子串 PKU122612、不重叠地至少两次出现在所有字符串中的最长子串之所以把两题一起说，因为它们大同小异，方法在前面的题目均出现过。对于多个串，连起来;反转后出现
78、，将每个字符串反写后和原串都连起来，将反写后的串和原串看成同一个串;求最长，二分答案后 height 分组;出现在所有字符串中(反写后的也行)，判断方法和 10 一样，k=n 而已;不重叠见问题 4，只不过这里对于每个字符串都要进行检验而已。13、两个字符串的重复子串个数。 Pku3415我个人觉得颇有难度的一个问题。具体的题目描述参看 Pku3415。14、最后的总结用后缀数组解题有着一定的规律可循，这是后缀的性质所决定的，具体归纳如下：1 N 个字符串的问题(N1)方法：将它们连接起来，中间用不会出现在原串中的，互不相同的，非 0 号字符分隔开。2 无限制条件下的最长公共子串(重复子串算是
79、后缀们的最长公共前缀)方法：height 的最大值。这里的无限制条件是对子串无限制条件。最多只能是两个串的最长公共子串，才可以直接是 height 的最大值。3 特殊条件下的最长子串方法：二分答案，再根据 height 数组进行分组，根据条件完成判定性问题。三个或以上的字符串的公共子串问题也需要二分答案。设此时要验证的串长度为 len，特殊条件有： 出现在 k 个串中条件：属于不同字符串的后缀个数不小于 k。(在一组后缀中，下面省略) 不重叠条件：出现在同一字符串中的后缀中，出现位置的最大值减最小值大于等于 len。 可重叠出现 k 次条件：出现在同一字符串中的后缀个数大于等于 k。若对于每个
80、字符串都需要满足，需要逐个字符串进行判断。4 特殊计数方法：根据后缀的性质，和题目的要求，通过自己的思考，看看用后缀数组能否实现。一般和“子串”有关的题目，用后缀数组应该是可以解决的。5 重复问题知道一点：lcp(i,i+k)可以判断，以 i 为起点，长度为 k 的一个字符串，它向后自复制的长度为多少，再根据具体题目具体分析，得出算法即可。2121、后缀树、后缀树后缀树(Suffix tree)是一种数据结构，能快速解决很多关于字符串的问题。后缀树提出的目的是用来支持有效的字符串匹配和查询。学习后缀树之前， 先了解一下 Trie 这个数据结构 Trie 是一种搜索树，可用于存储并查找字符串。T
81、rie 每一条边都对应一个字符。在 Trie 中查找字符串 S 时，只要按顺序枚举 S 的各个字符，从 Trie 的根节点开始选择相应的边走，如果枚举完的同时恰好走到 Trie 树的叶子节点，说明 S存在于 Trie 中。如果未到达叶子节点，或者枚举中未发现相应的边，则S没有被包含在 Trie 中。后缀树就是一种压缩后的 Trie 树。比如 S：banana，对 S 建立后缀树。首先给出 S 的后缀们0：banana1：anana2：nana3：ana4：na5：a6：空为了更清楚的表示后缀，我们在后缀的后面加上$0：banana$1：anana$2：nana$3：ana$4：na$5：a$6
82、：$然后对其进行分类：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 中最长的重复子串，所谓重复子串，是指出现了两次以上。首先定义节点的“字符深度” = 从后缀树根节点到每个节点所经过的字符串总长。找出有最大字符深度的非叶节点。则从根节点到该非叶节点所经
83、过的字符串即为所求。后缀树的用途，总结起来大概有如下几种 :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
84、 中重复了两次，则 S 应有两个后缀以 T 为前缀，重复次数就自然统计出来了。3. 字符串 S 中的最长重复子串方案：原理同 2，具体做法就是找到最深的非叶节点。这个深是指从 root 所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。为什么要非叶节点呢因为既然是要重复，当然叶节点个数要=2。4. 两个字符串 S1，S2 的最长公共部分方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。大体原理同 3。u 开始，对 w 进行快速定位， 在合适的地方插入新的节点。不断重复以上步骤，即可完成后缀树的构造。后缀树代码如下：Ltag=0
85、 时，表示 Lnode 指向该结点的左孩子;2. Ltag=1 时，表示 Lnode 指向该结点的线性前驱结点;3. Rtag=0 时，表示 Rnode 指向该结点的右孩子;4. Rtag=1 时，表示 Rnode 指向该结点的线性后继结点;中序次序线索化二叉树算法：中序次序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索;(具体看代码)检索中序二叉树某结点的线性前驱结点的算法：1. 如果该结点的 Ltag=1,那么 Lnode 就是它的线性前驱;2. 如果该结点的 Ltag=0，那么该结点左子树最右边的尾结点就是它的线性前驱点;(具体请看代码)检
86、索中序二叉树某结点的线性后继结点和算法：1. 如果该结点的 Rtag=1,那么 Rnode 就是它的线性后继结点;2. 如果该结眯的 Rtag=0,那么该结点右子树最左边的尾结点就是它的线性后继结点(具体请看代码)解决方案中所有到二叉树的中序线索二叉树和中序线索链表的图 ENDL;else if(p-lchild = NULL) p =p-rchild;elseBTreeNode* temp = p;else if(root-data = data)delete_node(root);else if(root-data data)delete_data(root-lchild,data);el
87、se delete_data(root-rchild,data);elsereturn find_data(root,data);elseBTreeNode *q = root;while(q-rchild != NULL)q = q-rchild;return q-data;elseBTreeNode *q = root;while(q-lchild != NULL)q = q-lchild;return q-data;Guibas 和 RobertSedgewick 于 1978 年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在 O
88、(log n)时间内做查找，插入和删除，这里的 n 是树中元素的数目。AVL：AVL 是最先发明的自平衡二叉查找树算法。在 AVL 中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是 O(log n)。 增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。Treap：Treap 是一棵二叉排序树，它的左子树和右子树分别是一个 Treap，和一般的二叉排序树不同的是，Treap 纪录一个额外的数据，就是优先级。Treap 在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注
89、意的是 Treap 和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而 Treap 可以并不一定是。伸展树：伸展树(Splay Tree)是一种二叉排序树，它能在 O(log n)内完成插入、查找和删除操作。它由 Daniel Sleator 和 Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。左偏树：堆结构是一种隐式数据结构(implicit data structure)，用完全二叉树表示的堆在数组中是隐式存贮的(即没有明确的指针或其他数据能够重构这种结构)。由于没有存贮结构信息，这种描述方法空间利用率很高，事实上没有空间浪费
90、。尽管堆结构的时间和空间效率都很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时。因此需要借助于其他数据结构来实现这类应用，左偏树(leftist tree)就能满足这种要求。(3)平衡二叉树为了保证二叉排序树的高度为 lgn，从而保证然二叉排序树上实现的插入、删除和查找等基本操作的平均时间为 O(lgn)，在往树中插入或删除结点时，要调整树的形态来保持树的平衡。使之既保持 BST 性质不变又保证树的高度在任何情况下均为 O(lgn)， 从而确保树上的基本操作在最坏情况下的时间均为 O(lgn)。注意：平衡二叉树(BalancedBinary Tree)是
91、指树中任一结点的左右子树的高度大致相同。任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为 O(1gn)，就可看作是平衡的。平衡的二叉排序树指满足 BST 性质的平衡二叉树。AVL 树中任一结点的左、右子树的高度之差的绝对值不超过 1。在最坏情况下，n 个结点的 AVL 树的高度约为。而完全平衡的二叉树度高约为 lgn，AVL 树是接近最优的。* Throw UnderflowException if empty.*/const Comparable & findMin( ) constif( isEmpty( ) )throw UnderflowEx
92、ception( );return findMin( root )-element;/* Find the largest item in the tree.* Throw UnderflowException if empty.*/const Comparable & findMax( ) constif( isEmpty( ) )throw UnderflowException( );return findMax( root )-element;/* Returns true if x is found in the tree.*/bool contains( const Comparab
93、le & x )constreturn contains( x, root );/* Test if the tree is logically empty.* Return true if empty, false otherwise.*/bool isEmpty( ) constreturn root = NULL;/* Print the tree contents in sorted order.*/void printTree( ) constif( isEmpty( ) )cout Emptytree endl;elseprintTree( root );/* Make the t
94、ree 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 p
95、resent endl;/* Deep copy.*/const AvlTree & operator=( constAvlTree & rhs )if( this != &rhs )makeEmpty( );root = clone( );return *this;private:struct AvlNodeComparable element;AvlNode *left;AvlNode *right;int height;AvlNode( const Comparable &theElement, AvlNode *lt,AvlNode *rt, int h = 0 ): element(
96、 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, N
97、ULL );else if( x element )insert( x, t-left );if( height( t-left ) - height(t-right ) = 2 )if( x left-element )rotateWithLeftChild( t );elsedoubleWithLeftChild( t );else if( t-element right );if( height( t-right ) - height(t-left ) = 2 )if( t-right-elementheight = max( height( t-left), height( t-rig
98、ht ) ) +1;/* Internal method to find the smallestitem in a subtree t.* Return node containing the smallestitem.*/AvlNode * findMin( AvlNode *t ) constif( 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
99、 containing the largest item.*/AvlNode * findMax( AvlNode *t ) constif( 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 ) consti
100、f( t = NULL )return false;else if( x element )return contains( x, t-left );else if( t-element right );elsereturn true;*/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 pri
101、ntTree( AvlNode *t ) constif( t != NULL )printTree( t-left );cout elementright );/* Internal method to clone subtree.*/AvlNode * clone( AvlNode *t ) constif( t = NULL )return NULL;elsereturn new AvlNode( t-element,clone( t-left ), clone( t-right ), t-height );*/int height( AvlNode *t ) constreturn t
102、 = NULL -1 : t-height;int max( int lhs, int rhs ) constreturn 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-r
103、ight = 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 * &
104、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
105、, 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,
106、this is a double rotationfor case 3.* Update heights, then set new root.*/void doubleWithRightChild( AvlNode * &k1 )rotateWithLeftChild( k1-right );rotateWithRightChild( k1 );#endif2525、HashHash 表表( (散列表散列表) )(1)(1)基本概念基本概念若结构中存在关键字和 K 相等的记录，则必定在 f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数(Hash fun
107、ction)，按这个思想建立的表为散列表。对不同的关键字可能得到同一散列地址，即 key1key2，而 f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数 H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function
108、)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。(2)(2)常用的构造散列函数的方法常用的构造散列函数的方法散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。1直接定址法：取关键字或关键字的某个线性函数值为散列地址。即 H(key)=key 或 H(key) = akey + b，其中 a 和 b 为常数(这种散列函数叫做自身函数)2数字分析法： 一般取一些大一点的素数，效果更好点。3平方取中法:计算关键值再取中间 r 位形成一个 2r 位的表4折叠法:把所有字符的 ASCII 码加起来 (对于字符串)5随机数法：选择一个随机函数，取关
109、键字的随机函数值为它的哈希地址，即 H(key)=random(key),其中 random 为随机函数。通常关键字长度不等时采用此法构造哈希函数较恰当。6除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 H(key) = key MOD p,p=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对 p 的选择很重要，一般取素数或 m，若 p 选的不好，容易产生同义词。7针对字符串的一些常用方法， 比如 ELFHash 和 BKDRHash(更易于编写，效率不错)(3)(3)处理冲突的方法处理冲突的方法1开放定址法;Hi=(H(key) +
110、 di) MOD m, i=1,2, k(k=m-1)，其中 H(key)为散列函数，m 为散列表长，di 为增量序列，可有下列三种取法：di=1,2,3, m-1，称线性探测再散列;di=12, -12, 22,-22,32, , k2,(k=m/2)称二次探测再散列;di=伪随机数序列，称伪随机探测再散列。2再散列法：Hi=RHi(key), i=1,2,k RHi 均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。3链地址法(拉链法)4建立一个公共溢出区(4)(4)查找的性能分析查找的性能分析散列表的查找过程
111、基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：1散列函数是否均匀;2处理冲突的方法;3散列表的装填因子。散列表的装填因子定义为：= 填入表中的元素个数 / 散列表的长度
112、是散列表装满程度的标志因子。由于表长是定值， 与“填入表中的元素个数”成正比，所以，越大，填入表中的元素较多，产生冲突的可能性就越大; 越小，填入表中的元素较少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是装填因子 的函数，只是不同处理冲突的方法有不同的函数。/简单的 Hash 表实现#includetemplateclass HashTablepublic:HashTable(int Length)Element = new _TypeLength;for(int i=0;iLENGTH;I+)Elementi = -1;this-Length = Length;Count = 0
113、;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(ElementIndex != -1 &ElementIndex != Data)
114、Index = ReHash(Index,+Count);return Data = ElementIndex 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)ElementIndex = Data;Count+;return true;retur
115、n false;/ 设置 Hash 表长度void SetLength(int Length)delete Element;Element = new _TypeLength;for(int i=0;iLENGTH;I+)Elementi = -1;this-Length = Length;/ 删除某个元素void Remove(_Type Data)int Index = SerachHash(Data);if(Index != -1)ElementIndex = -1;Count-;/ 删除所有元素void RemoveAll()for(int i=0;iLENGTH;I+)Element
116、i = -1;Count = 0;void Print()for(int i=0;iLENGTH;I+)printf(%d,Elementi);printf(n);protected:_Type* Element; / Hash 表int Length; / Hash 表大小int Count; / Hash 表当前大小;void main()HashTable H(10);printf(Hash Length(10)Test:n);int Array6 = 49,38,65,97,13,49;for(int i=0;i6;i+)printf(%dn,(Arrayi);();printf(Find(97):%dn,(97);printf(Find(49):%dn,(49);();(30);printf(Hash Length(30)Test:n);for(int i=0;i6;i+)printf(%dn,(Arrayi);();printf(Find(97):%dn,(97);printf(Find(49):%dn,(49);system(pause);
