ACM竞赛中所用到的数据结构课件.ppt

1、ACM竞赛中所用到的数据结构基本数据结构 基础：队列、堆栈、链表 排序与检索：快速排序和归并排序的思想 串的模式匹配：KMP,Boyer-Moore,Trie(*),有限状态自动机(*)树：左儿子右兄弟表示法,AVL(用STL实现),哈夫曼树,Splay Tree(*),树状数组，线段树，PQ树(*)字典：Hash、并查集(*)、可并优先队列，堆关于堆 Heap 二叉堆（又名最大/最小堆）二项堆 映射2分堆 Fibonacci堆 Interval heap 左偏树Leftist Tree队列Queue 特点：先进先出 FIFO入队O(1),出队O(1)不能随机访问中间的元素 实现方法：链表数组

2、STL队列Queue#include using namespace std;/STL queue queue Q;Member Functions:堆栈Stack 特点：先进后出 FILO入队O(1),出队O(1)不能随机访问中间的元素 实现方法：链表数组STL堆栈Stack#include using namespace std;/STL stack S;链表list 特点：插入O(k)删除O(k)查找O(k)最坏情况下都是O(n)实现方法：链表数组-改进块状数组STL链表list#include using namespace std;/STL list S;链表list排序 排序快速排

3、序 O(n*log(n)堆排序（稳定排序）O(n*log(n)选择排序,冒泡排序 O(n2)桶排序 O(M)O(n)随机查找第k小元素std:sort STL#include using namespace std;int aM,bM;sort(a,a+n);sort(a,a+n,cmp);bool cmp(const int x,const int y)return xy;/return bxby;随机查找第k小元素随机第随机第k小元素小元素int select(int*a,int b,int e,int k)if(b=e)return ab;int x=ab+rand()%(e-b+1),

4、i=b-1,j=e+1,tmp;while(ij)while(a+ix);if(ij)tmp=ai,ai=aj,aj=tmp;if(j=e)j-;i=j-b+1;if(k=i)return select(a,b,j,k);else return select(a,j+1,e,k-i);串的模式匹配-KMP 由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法 朴素的串模式匹配的复杂度是O(m*n)长度为m的母串S,匹配长度为n的子串A求母串S中有多少个子串A求母串S中第1个子串A的位置 KMP算法的复杂度为O(m+n)总体思想O(n)线性时

5、间预处理子串，求出前缀函数O(m)线性时间扫描母串求出匹配串的模式匹配-KMP/KMP 求前缀函数求前缀函数 int failmaxlen;void makefail(char*t,int lt)-t;for(int i=1,j=0;i0&ti!=tj)j=failj;串的模式匹配-KMP/start matching pattern T in Si.)/return match pos or longest match length with corresponding posint kmp(char*s,int ls,char*t,int lt,int i,int&longest,int&

6、lp)longest=lp=0;-s;-t;for(int j=1;i0&si!=tj)j=failj;if(jlongest)longest=j;lp=i-j;if(j=lt)return i-lt;return-1;串的模式匹配-BM 快速的字符串查找算法 Boyer-Moore算法 BM 算法是一个较优的模式匹配算法。一般，如果不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明，BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KM

7、P匹配和BM匹配，进一步提高效率。串的模式匹配-BM 算法的关键和 KMP 类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引：positionpatteni=i;也是相当简单的辅助数组构造。具体可以见http:/www-igm.univ-mlv.fr/lecroq/string/node14.html 另外，动态演示程序见附件二叉搜索树 BST（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系二叉搜索树 在输入数据随机

8、的情况下，算法效率大约为n*log(n)。最坏情况下将退化到链表，O(n2)推荐题目：FOJ 1353 Hardwood Species 平衡树AVL BST受输入顺序影响最好O(log n)最坏O(n2)怎样使得BST始终保持O(log n)级的平衡状态？Adelson-Velskii和Landis发明了AVL树一种平衡的二叉搜索树任何结点的左子树和右子树高度最多相差1AVL树的性质树的性质 可以为空 具有n个结点的AVL树，高度为O(log n)如果T是一棵AVL树那么它的左右子树TL、TR也是AVL树并且|hL-hR|1hL、hR 是它的左右子树的高度解决不平衡的方法解决不平衡的方法旋转

9、旋转 我们可以使用一系列称为旋转(rotation)的局部操作解决这个问题LL和RR的情况可以通过单旋转(single rotation)来解决RL和LR的情况可以通过双旋转(double rotation)来解决 调整的整个过程称之为重构(restructuring)AVL的使用 因为旋转的过程较为复杂，需要较大的编码量，在实际比赛中，我们一般使用C+STL（Standard Template Library）标准模板库。定义：map tree;查找：tree.find(key);访问：tree.begin().first表示keytype的值 插入、删除：tree.insert(make_

10、pair(key,val);tree.erase(tree.begin();失败返回tree.end();插入或更改：treekey=val;红黑树的使用 其插入、删除、修改的算法复杂度均为n*log(n)。具体实现也比较复杂，可以参考相关数据结构书籍，在比赛中一般也使用STL.集合 定义：setdouble,greater t;multiset t(a.begin(),a.end(),cmp);插入：tree.insert(val);multiset返回bool;set返回pair其中.second表示是否插入成功,.first表示新元素或现存同值元素的位置。改变：该类型内容是只读的，不能改

11、变 查找：tree.find(val);返回值为val的第一个元素的迭代器；tree.lower_bound(val);返回第一个大于等于val的元素位置 删除：tree.erase(tree.begin();字典树 trie Trie结构基于关键码分解的数据结构，叫作Trie结构“trie”这个词来源于“retrieval”主要应用信息检索用来存储英文字符串，尤其大规模的英文词典 自然语言理解系统中经常用到Trie结构应用结构应用字典树字典树 存储字典里面的单词 英文的单词是有26个字母组成的（简单起见，我们忽略大小写）英文字符树每一个内部结点都有26个子结点树的高度为最长字符串长度字典树

12、trie字典树的改进由于单词可能不等长，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息字典树中的检索字典树中的检索 首先用待查关键码的第一个字符与树林的各个根的字符相比较，然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，接着再沿着前次比较相等的分支进行进一步的检索，.，直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现；若检索一直进行到树叶，那么就在树目录里找到了给定的关键码Trie树的插入树的插入 Trie树的插入 首先根据插入纪录的关键码找到需要插入的结

13、点位置 如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录 如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可Trie树的删除 Trie树的删除 根据插入纪录的关键码找到需要删除的结点位置 如果一个被删除结点的父结点没有其他的儿子，那么就需要合并 否则只需要将此分支设置为空即可后缀树和后缀数组 百度百科中 后缀树http:/ 后缀数组http:/ 附件中相关资料后缀树.pdf 后缀数组.doc关于后缀数组 字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是

14、后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在ACM比赛中中后缀数组比后缀树要更为实用。树 树的一般表示法数组父亲表示法儿子节点表示法（用指针构建多叉树）比赛的时候常用vector来构造左儿子右兄弟表示法哈夫曼树 哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。定义：结点之间的路径长度：从一个结点到另一个结点之间的分支数目。树的路径长度：从树的根到树中每一个结点的路径长度之和。(PL)哈夫曼树 PL

15、计算哈夫曼树 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WPL为最小的二叉树就称作最优二叉树或哈夫曼树。哈夫曼树 WPL的计算 完全二叉树不一定是最优二叉树。哈夫曼树构造算法（贪心）（1）根据给定的n个权值w1,w2,.,wn构造n棵二叉树的集合F=T1,T2,.,Tn，其中Ti中只有一个权值为wi的根结点，左右子树为空；（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）将新的二叉树加入到F中，删除原两棵根结点权值最小

16、的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。哈夫曼树的构造图树状数组 树状数组是一个查询和修改复杂度都为树状数组是一个查询和修改复杂度都为log(n)的数据结构，的数据结构，假设数组假设数组a1.n，那么查询，那么查询a1+ai 的时间是的时间是log级别的，而且是一个在线的数据结构，支持随时修改级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为某个元素的值，复杂度也为log级别。级别。令这棵树的结点编号为令这棵树的结点编号为C1，C2Cn。令每个结点的值。令每个结点的值为这棵树的值的总和，那么容易发现：为这棵树的值的总和，那么容易发现：C1=

17、A1 C2=A1+A2 C3=A3 C4=A1+A2+A3+A4 C5=A5 C6=A5+A6 C7=A7 C8=A1+A2+A3+A4+A5+A6+A7+A8 C16=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12+A13+A14+A15+A16树状数组 树状数组 设节点编号为x，那么这个节点管辖的区间为2k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，所以很明显：Cn=A(n 2k+1)+An 算这个2k有一个快捷的办法，定义一个函数如下即可：int lowbit(int x)return x&(x (x 1);树状数组 当想要查

18、询一个当想要查询一个SUM(n)时，可依据如下算法即可：时，可依据如下算法即可：step1:令令sum=0，转第二步；，转第二步；step2:假如假如n=0，算法结束，返回，算法结束，返回sum值，否则值，否则sum=sum+Cn，转第三步；，转第三步；step3:令令n=n lowbit(n)，转第二步。，转第二步。可以看出，这个算法就是将这一个个区间的和全部可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是加起来，为什么是效率是log(n)的呢？的呢？以下给出证明：以下给出证明：n=n lowbit(n)这一步实际上等这一步实际上等价于将价于将n的二进制的最后一个的二进制的

19、最后一个1减去。而减去。而n的二进制的二进制里最多有里最多有log(n)个个1，所以查询效率是，所以查询效率是log(n)的。的。树状数组推广 二维树状数组二维树状数组求求suma1.m1.n维护和查询复杂度均为维护和查询复杂度均为O(logm*logn)用于动态求子阵和用于动态求子阵和,数组内容保存在数组内容保存在sum.a中中 还可以进一步推广到三维树状数组还可以进一步推广到三维树状数组*线段树 它是能够在log(MaxLen)时间内完成线段的添加、删除、查询等操作。参考论文：数据结构的选择与算法效率 从IOI98试题PICTURE谈起 胜者树Winner Tree 一种基于空间分割的数据

20、结构 可以动态求s.t之间的最大/最小值 时间复杂度：建树 n*log(n)查询s.t最大/最小值log(t-s+1);动态更新某个元素的值 log(n);空间复杂度O(2*n)笛卡尔树Cartesian Tree 笛卡尔树，就是一棵树，这棵树的父节点的值小于树的笛卡尔树，就是一棵树，这棵树的父节点的值小于树的子节点值，并且树的中序遍历满足在原数组中的顺序子节点值，并且树的中序遍历满足在原数组中的顺序（一个点（一个点i左子树中的所有数，在原数组中，在这个点左子树中的所有数，在原数组中，在这个点i的的左边；点左边；点i的左孩子的左孩子left-i的右子树中的所有数，在原数组的右子树中的所有数，在

21、原数组中，在点中，在点left-i的右边并且在点的右边并且在点i的左边）的左边）建立这棵树的平均复杂度是建立这棵树的平均复杂度是O(n)，存储的时候用内存池，存储的时候用内存池的线性结构，每加入一个节点的线性结构，每加入一个节点i（原数组从左向右扫描），（原数组从左向右扫描），如果大于上一个加入的点如果大于上一个加入的点i-1，就连在它，就连在它(i)右面，小于的右面，小于的话，就找到第一个比它大的点话，就找到第一个比它大的点k，把以这个比它大的点，把以这个比它大的点(k)为根节点的树连在节点为根节点的树连在节点i的左边，这样构造出来的这棵树的左边，这样构造出来的这棵树就是笛卡尔树。若有就是笛

22、卡尔树。若有n个点，则有个点，则有n-1条边，每条边最多条边，每条边最多向下向上各走一次，也就是向下向上各走一次，也就是2*(n-1)次，所以平均复杂度次，所以平均复杂度是是O(n)。笛卡尔树Cartesian Tree 笛卡尔树的建立笛卡尔树的建立 Cartesian Tree 笛卡尔树是这样的一棵树，它满足键值的笛卡尔树是这样的一棵树，它满足键值的结构是二叉搜索树，而内容就是结构是二叉搜索树，而内容就是prio值。值。其实它也是个堆。其实它也是个堆。笛卡尔树主要用于将笛卡尔树主要用于将RMQ问题转化成问题转化成LCA问题问题Hash散列 Hash，一般翻译做“散列”，也有直接音译为“哈希”

23、的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。数学表述为：h=H(M)，其中H()-单向散列函数，M-任意长度明文，h-固定长度散列值 Hash散列 当两个或两个以上的关键字散列到同一个值的时候，发生冲突。解决方法：开散列和闭散列 Hash冲突取决于Hash函数的选择散列空间的大小输入数据开闭散列字符串散列ELFHash函数函数/prime:3001,5003,10007,20011,50021,100003,150001,20

24、0003,500009,704447,901963,1009237,1199993,1500007,2000003,5000011int ELFhash(char*key)unsigned int g,h=0;while(*key)h=(h24;h&=g;return h%Size;/Size要用大质数要用大质数字符串散列SuperFastHash(1)#define get16bits(d)(unsigned int)(d)1)=2;for(;len0;len-)g+=get16bits(key);key+=2;h=(get16bits(key)11)g;key+=2;g=(g11;字符串散

25、列SuperFastHash(2)switch(rem)case 3:g+=get16bits(key);g=g16;g=key211;break;case 2:g+=get16bits(key);g=g17;break;case 1:g+=*key;g=g1;break;g=g5;g=g17;g=g6;return g%M;整数Hash函数 常用平方取余数 int IntegerHash(int key)unsigned int p=key*key;/溢出就溢出 return p%Size;/返回0.size-1 集合set STL集合set STL集合multiset STL集合multi

26、set STL并查集Disjoint Sets 并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。并查集的主要操作有1合并两个不相交集合 Union(A,B)2判断两个元素是否属于同一个集合 Findroot(X)Disjoint Sets Findroot(x)同BST一样，最坏情况为一条链，那么进行一次Find操作的时间复杂度为O(N)，代价太大。改进方法:1.启发式合并将结点少的树合并到结点多的树上。2.路径压缩当一条路找到根结点了以后，把所有处于路径中的结点的父亲指针直接指向该集合的父亲。二叉堆 一种特殊的树形数据结构，每个结点都有一个值。二叉堆的特点是根结点的值最小（或最

27、大），且根结点的两个子树也是一个堆。建堆 O(n*log(n)/O(n);插入元素 log(n);删除最大/最小元素log(n);无论是插入还是删除，最关键的都在于调整。STL heap make_heap(a,a+n,cmp)默认是最大堆化，即cmp为真时a做叶子 pop_heap(a,a+n,cmp)将堆顶元素移至an-1且a0:n-2仍为堆 push_heap(a,a+n,cmp)将an-1加入堆a0:n-2 sort_heap(a,a+n,cmp)将堆an-1化为排序好的数组an-1 bool cmp(int x,int y)return xy;/最大堆 a0为堆顶元素。映射2分堆 二

28、项堆不能删除任意元素 在二项堆的基础上，加上一个索引之后，就成了映射2分堆，这时候就可以在log(n)的时间内删除元素。而Fibonacci堆也支持插入、删除、查找最大最小元素，算法复杂度都很低，但是编程复杂度却很高。几种堆的比较优先队列#include#include priority_queue int,vector,greater q3;Priority_queue struct Rec char word20;struct CMP /特别的，重载的是特别的，重载的是()bool operator()(const Rec&a,const Rec&b)const return strcmp(a.word,b.word)0;priority_queueRec,vector,CMP pq;