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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ACM竞赛中所用到的数据结构,ACM竞赛中所用到的数据结构,1,基本数据结构,基础：队列、堆栈、链表,排序与检索：快速排序和归并排序的思想,串的模式匹配：KMP, Boyer-Moore, Trie(*), 有限状态自动机(*),树：左儿子右兄弟表示法, AVL(用STL实现),哈夫曼树,Splay Tree(*), 树状数组，线段树,，PQ树(*),字典：Hash、并查集(*)、可并优先队列，堆,基本数据结构基础：队列、堆栈、链表,2,关于堆 Heap,二叉堆（又名最大/最小堆）,二项堆,映射2分堆,Fibonacci堆,Interval heap,左偏树Leftist Tree,关于堆 Heap二叉堆（又名最大/最小堆）,3,队列Queue,特点：,先进先出 FIFO,入队O(1), 出队O(1),不能随机访问中间的元素,实现方法：,链表,数组,STL,队列Queue特点：,4,队列Queue,#include using namespace std; /STL queue,queue Q;,Member Functions:,队列Queue#include using n,5,堆栈Stack,特点：,先进后出 FILO,入队O(1), 出队O(1),不能随机访问中间的元素,实现方法：,链表,数组,STL,堆栈Stack特点：,6,堆栈Stack,#include using namespace std; /STL,stack S;,堆栈Stack#include using n,7,链表list,特点：,插入O(k),删除O(k),查找O(k) 最坏情况下都是O(n),实现方法：,链表,数组-改进块状数组,STL,链表list特点：,8,链表list,#include using namespace std; /STL,list S;,链表list#include using nam,9,链表list,链表list,10,排序,排序,快速排序 O(n*log(n),堆排序（稳定排序）O(n*log(n),选择排序,冒泡排序 O(n2),桶排序 O(M),O(n)随机查找第k小元素,排序排序,11,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;,std:sortSTL,12,随机查找第k小元素,随机第k小元素,int select(int *a,int b,int e,int k),if(b=e) return ab;,int x=ab+rand()%(e-b+1),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);,随机查找第k小元素随机第k小元素,13,串的模式匹配-KMP,由D.E.,K,nuth,J.H.,M,orris和V.R.,P,ratt同时发现的改进的模式匹配算法简称为KMP算法,朴素的串模式匹配的复杂度是O(m*n),长度为m的母串S, 匹配长度为n的子串A,求母串S中有多少个子串A,求母串S中第1个子串A的位置,KMP算法的复杂度为O(m+n),总体思想,O(n)线性时间预处理子串，求出前缀函数,O(m)线性时间扫描母串求出匹配,串的模式匹配-KMP由D.E.Knuth,J.H.Morr,14,串的模式匹配-KMP,/KMP 求前缀函数,int failmaxlen;,void makefail( char *t, int lt ),-t;,for(int i=1,j=0;i0 ,串的模式匹配-KMP/KMP 求前缀函数,15,串的模式匹配-KMP,/ start matching pattern T in Si.),/ return match pos or longest match length with corresponding pos,int kmp(char *s, int ls, char *t, int lt, int i,int &longest,int &lp),longest = lp = 0; -s; -t;,for(int j=1; i0 ,if( jlongest ) longest = j; lp = i-j; ,if( j=lt ) return i-lt;,return -1;,串的模式匹配-KMP/ start matching p,16,串的模式匹配-BM,快速的字符串查找算法 Boyer-Moore算法,BM 算法是一个较优的模式匹配算法。一般，如果不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明，BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KMP匹配和BM匹配，进一步提高效率。,串的模式匹配-BM快速的字符串查找算法 Boyer-Moo,17,串的模式匹配-BM,算法的关键和 KMP 类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引：positionpatteni=i; 也是相当简单的辅助数组构造。,具体可以见,http:/www-igm.univ-mlv.fr/lecroq/string/node14.html,另外，动态演示程序见附件,串的模式匹配-BM算法的关键和 KMP 类似，也是构造一个,18,二叉搜索树,BST,（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系,二叉搜索树BST（二叉搜索树）不是一棵平衡的树，它的树结构与,19,二叉搜索树,在输入数据随机的情况下，算法效率大约为n*log(n)。,最坏情况下将退化到链表，O(n2),推荐题目：FOJ 1353,Hardwood Species,二叉搜索树在输入数据随机的情况下，算法效率大约为n*log(,20,平衡树AVL,BST,受输入顺序影响,最好,O(log,n,),最坏,O(,n2,),怎样使得,BST,始终保持,O(log,n,),级的平衡状态？,Adelson-Velskii和Landis发明了AVL树,一种平衡的二叉搜索树,任何结点的左子树和右子树高度最多相差1,平衡树AVLBST受输入顺序影响,21,AVL,树的性质,可以为空,具有,n,个结点的,AVL,树，高度为,O(log,n,),如果,T,是一棵,AVL,树,那么它的左右子树,TL,、,TR,也是,AVL,树,并且,| hL-hR|,1,hL,、,hR,是它的左右子树的高度,AVL树的性质可以为空,22,解决不平衡的方法,旋转,我们可以使用一系列称为旋转,(rotation),的局部操作解决这个问题,LL和RR的情况可以通过单旋转,(single rotation),来解决,RL和LR的情况可以通过双旋转,(double rotation),来解决,调整的整个过程称之为重构(,restructuring,),解决不平衡的方法旋转我们可以使用一系列称为旋转(rota,23,AVL的使用,因为旋转的过程较为复杂，需要较大的编码量，在实际比赛中，我们一般使用C+ STL（Standard Template Library）标准模板库 。, 定义：map tree;, 查找：tree.find(key);, 访问：tree.begin().first表示keytype的值, 插入、删除：tree.insert(make_pair(key,val);tree.erase(tree.begin();失败返回tree.end();, 插入或更改：treekey=val;,AVL的使用因为旋转的过程较为复杂，需要较大的编码量，在实际,24,红黑树的使用,其插入、删除、修改的算法复杂度均为n*log(n)。,具体实现也比较复杂，可以参考相关数据结构书籍，在比赛中一般也使用STL.,集合, 定义：set,double,greater t;multiset t(a.begin(),a.end(),cmp);, 插入：tree.insert(val); multiset返回bool; set返回pair其中.second表示是否插入成功, .first表示新元素或现存同值元素的位置。, 改变：该类型内容是只读的，不能改变, 查找：tree.find(val);返回值为val的第一个元素的迭代器；tree.lower_bound(val); 返回第一个大于等于val的元素位置, 删除：tree.erase(tree.begin();,红黑树的使用其插入、删除、修改的算法复杂度均为n*log(n,25,字典树 trie,Trie,结构,基于关键码分解的数据结构，叫作,Trie,结构,“trie”,这个词来源于,“retrieval”,主要应用,信息检索,用来存储英文字符串，尤其大规模的英文词典,自然语言理解系统中经常用到,字典树 trieTrie结构,26,Trie,结构应用字典树,存储字典里面的单词,英文的单词是有,26,个字母组成的（简单起见，我们忽略大小写）,英文字符树每一个内部结点都有,26,个子结点,树的高度为最长字符串长度,Trie结构应用字典树存储字典里面的单词,27,字典树 trie,字典树 trie,28,字典树的改进,由于单词可能不等长，所以更好的存储是其内部结点,不存储单词信息，只有叶结点才存储单词信息,字典树的改进由于单词可能不等长，所以更好的存储是其内部结点,29,字典树中的检索,首先用待查关键码的第一个字符与树林的各个根的字符相比较，然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，接着再沿着前次比较相等的分支进行进一步的检索，,.，,直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现；,若检索一直进行到树叶，那么就在树目录里找到了给定的关键码,字典树中的检索首先用待查关键码的第一个字符与树林的各个根的字,30,Trie树的插入,Trie,树的插入,首先根据插入纪录的关键码找到需要插入的结点位置,如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录,如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可,Trie树的插入Trie树的插入,31,Trie树的删除,Trie树的删除,根据插入纪录的关键码找到需要删除的结点位置,如果一个被删除结点的父结点没有其他的儿子，那么就需要合并,否则只需要将此分支设置为空即可,Trie树的删除Trie树的删除,32,后缀树和后缀数组,百度百科中,后缀树, 哈夫曼树又称最优树（二叉树），是一类带权路径最短,36,哈夫曼树,PL计算,哈夫曼树PL计算,37,哈夫曼树,结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。,树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：,WPL为最小的二叉树就称作最优二叉树或哈夫曼树。,哈夫曼树结点的带权路径长度：从该结点到树根之间的路径长度与结,38,哈夫曼树,WPL的计算,完全二叉树不一定是最优二叉树。,哈夫曼树WPL的计算,39,哈夫曼树构造算法（贪心）,（1）根据给定的n个权值w1,w2,.,wn构造n棵二叉树的集合F=T1,T2,.,Tn，其中Ti中只有一个权值为wi的根结点，左右子树为空；（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。,哈夫曼树构造算法（贪心） （1）根据给定的n个权值w1,40,哈夫曼树的构造图,哈夫曼树的构造图,41,树状数组,树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组a1.n，那么查询a1 + + ai 的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。 令这棵树的结点编号为C1，C2Cn。令每个结点的值为这棵树的值的总和，那么容易发现： C1 = 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,树状数组树状数组是一个查询和修改复杂度都为log(n)的数据,42,树状数组,树状数组,43,树状数组,设节点编号为x，那么这个节点管辖的区间为2k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，所以很明显： Cn = A(n 2k + 1) + + An 算这个2k有一个快捷的办法，定义一个函数如下即可： int lowbit(int x) return x ,树状数组设节点编号为x，那么这个节点管辖的区间为2k（其中,44,树状数组,当想要查询一个SUM(n)时，可依据如下算法即可：,step1:令sum = 0，转第二步；,step2:假如n = 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；,step3: 令n = n lowbit(n)，转第二步。,可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？,以下给出证明： n = n lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。,树状数组当想要查询一个SUM(n)时，可依据如下算法即可：,45,树状数组推广,二维树状数组,求suma1.m1.n,维护和查询复杂度均为O(logm*logn),用于动态求子阵和,数组内容保存在sum.a中,还可以进一步推广到三维树状数组,树状数组推广二维树状数组,46,*线段树,它是能够在log(MaxLen)时间内完成线段的添加、删除、查询等操作。,参考论文：,数据结构的选择与算法效率 从IOI98试题PICTURE谈起,*线段树它是能够在log(MaxLen)时间内完成线段的添加,47,胜者树Winner Tree,一种基于空间分割的数据结构,可以动态求s.t之间的最大/最小值,时间复杂度：,建树 n*log(n),查询s.t最大/最小值log(t-s+1);,动态更新某个元素的值 log(n);,空间复杂度O(2*n),胜者树Winner Tree一种基于空间分割的数据结构,48,笛卡尔树Cartesian Tree,笛卡尔树，就是一棵树，这棵树的父节点的值小于树的子节点值，并且树的中序遍历满足在原数组中的顺序（一个点i左子树中的所有数，在原数组中，在这个点i的左边；点i的左孩子left-i的右子树中的所有数，在原数组中，在点left-i的右边并且在点i的左边）,建立这棵树的平均复杂度是O(n)，存储的时候用内存池的线性结构，每加入一个节点i（原数组从左向右扫描），如果大于上一个加入的点i-1，就连在它(i)右面，小于的话，就找到第一个比它大的点k，把以这个比它大的点(k)为根节点的树连在节点i的左边，这样构造出来的这棵树就是笛卡尔树。若有n个点，则有n-1条边，每条边最多向下向上各走一次，也就是2*(n-1)次，所以平均复杂度是O(n)。,笛卡尔树Cartesian Tree 笛卡尔树，就是一棵树，,49,笛卡尔树Cartesian Tree,笛卡尔树的建立,Cartesian Tree,笛卡尔树是这样的一棵树，它满足键值的结构是二叉搜索树，而内容就是prio值。,其实它也是个堆。,笛卡尔树主要用于将RMQ问题转化成LCA问题,笛卡尔树Cartesian Tree笛卡尔树的建立,50,Hash散列,Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。,数学表述为：h = H(M) ，其中H( )-单向散列函数，M-任意长度明文，h-固定长度散列值,Hash散列Hash，一般翻译做“散列”，也有直接音译为“,51,Hash散列,当两个或两个以上的关键字散列到同一个值的时候，发生冲突。,解决方法：开散列和闭散列,Hash冲突取决于,Hash函数的选择,散列空间的大小,输入数据,开闭散列,Hash散列当两个或两个以上的关键字散列到同一个值的时候，,52,字符串散列,ELFHash函数,/prime:3001,5003,10007,20011,50021,100003,150001,200003,500009,704447,901963,1009237,1199993,1500007,2000003,5000011,int ELFhash(char *key) ,unsigned int g,h=0;,while (*key),h=(h24;,h,return h%Size;/Size要用大质数,字符串散列ELFHash函数/prime:3001,500,53,字符串散列,SuperFastHash(1),#define get16bits(d) (unsigned int)(d)1)0;len-),g+=get16bits(key);key+=2;,h=(get16bits(key)11)g; key+=2;,g=(g11;,字符串散列SuperFastHash(1)#define g,54,字符串散列,SuperFastHash(2),switch(rem),case 3:g+=get16bits(key);g=g11;,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;,字符串散列SuperFastHash(2)switch(,55,整数Hash函数,常用平方取余数,int IntegerHash(int key),unsigned int p=key*key; /溢出就溢出,return p%Size; /返回0.size-1,整数Hash函数常用平方取余数,56,集合set STL,集合set STL,57,集合set STL,集合set STL,58,集合multiset STL,集合multiset STL,59,集合multiset STL,集合multiset STL,60,并查集Disjoint Sets,并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。,并查集的主要操作有,1合并两个不相交集合 Union(A,B),2判断两个元素是否属于同一个集合 Findroot(X),并查集Disjoint Sets并查集是一种树型的数据结构，,61,Disjoint Sets,Findroot(x),同BST,一样，最坏情况为一条链，那么进行一次Find操作的时间复杂度为O(N)，代价太大。,改进方法:,1.,启发式合并,将结点少的树合并到结点多的树上。,2.,路径压缩,当一条路找到根结点了以后，把所有处于路径中的结点的父亲指针直接指向该集合的父亲。,Disjoint SetsFindroot(x)同BST一样,62,二叉堆,一种特殊的树形数据结构，每个结点都有一个值。,二叉堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。,建堆 O(n*log(n)/ O(n);,插入元素 log(n);,删除最大/最小元素log(n);,无论是插入还是删除，最关键的都在于调整。,二叉堆一种特殊的树形数据结构，每个结点都有一个值。二叉堆的特,63,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 x q3;,优先队列#include #includev,67,Priority_queue,struct Rec,char word20;,;,struct CMP /特别的，重载的是(),bool operator () (const Rec &a,const Rec &b) const,return strcmp(a.word,b.word) pq;,Priority_queuestruct Rec,68,