《ACM竞赛中所用到的数据结构课件.ppt》由会员分享，可在线阅读，更多相关《ACM竞赛中所用到的数据结构课件.ppt（68页珍藏版）》请在三一文库上搜索。
1、ACM竞赛中所用到的数据结构,ACM竞赛中所用到的数据结构,ACM竞赛中所用到的数据结构,基本数据结构,基础：队列、堆栈、链表 排序与检索：快速排序和归并排序的思想 串的模式匹配：KMP, Boyer-Moore, Trie(*), 有限状态自动机(*) 树：左儿子右兄弟表示法, AVL(用STL实现), 哈夫曼树,Splay Tree(*), 树状数组，线段树 ，PQ树(*) 字典：Hash、并查集(*)、可并优先队列，堆,ACM竞赛中所用到的数据结构,关于堆 Heap,二叉堆（又名最大/最小堆） 二项堆 映射2分堆 Fibonacci堆 Interval heap 左偏树Leftist T
2、ree,ACM竞赛中所用到的数据结构,队列Queue,特点： 先进先出 FIFO 入队O(1), 出队O(1) 不能随机访问中间的元素 实现方法： 链表 数组 STL,ACM竞赛中所用到的数据结构,队列Queue,#include using namespace std; /STL queue queue Q; Member Functions:,ACM竞赛中所用到的数据结构,堆栈Stack,特点： 先进后出 FILO 入队O(1), 出队O(1) 不能随机访问中间的元素 实现方法： 链表 数组 STL,ACM竞赛中所用到的数据结构,堆栈Stack,#include using namespa
3、ce std; /STL stack S;,ACM竞赛中所用到的数据结构,链表list,特点： 插入O(k) 删除O(k) 查找O(k) 最坏情况下都是O(n) 实现方法： 链表 数组-改进块状数组 STL,ACM竞赛中所用到的数据结构,链表list,#include using namespace std; /STL list S;,ACM竞赛中所用到的数据结构,链表list,ACM竞赛中所用到的数据结构,排序,排序 快速排序 O(n*log(n) 堆排序（稳定排序）O(n*log(n) 选择排序,冒泡排序 O(n2) 桶排序 O(M) O(n)随机查找第k小元素,ACM竞赛中所用到的数据结
4、构,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; ,ACM竞赛中所用到的数据结构,随机查找第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 (ix); if (ij) tmp=
5、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); ,ACM竞赛中所用到的数据结构,串的模式匹配-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)线性时间预处理子串，求出前缀函数 O(
6、m)线性时间扫描母串求出匹配,ACM竞赛中所用到的数据结构,串的模式匹配-KMP,/KMP 求前缀函数 int failmaxlen; void makefail( char *t, int lt ) -t; for(int i=1,j=0;i0 ,ACM竞赛中所用到的数据结构,串的模式匹配-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,
7、int ,ACM竞赛中所用到的数据结构,串的模式匹配-BM,快速的字符串查找算法 Boyer-Moore算法 BM 算法是一个较优的模式匹配算法。一般，如果不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明，BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KMP匹配和BM匹配，进一步提高效率。,ACM竞赛中所用到的数据结构,串的模式匹配-BM,算法的关键和 KMP 类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数
8、组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引：positionpatteni=i; 也是相当简单的辅助数组构造。 具体可以见 另外，动态演示程序见附件,ACM竞赛中所用到的数据结构,二叉搜索树,BST（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系,ACM竞赛中所用到的数据结构,二叉搜索树,在输入数据随机的情况下，算法效率大约为n*log(n)。 最坏情况下将退化到链表，O(n2) 推荐题目：FOJ 1353 Hardwood Species,ACM竞赛中所用到的数据结构,平衡树AV
9、L,BST受输入顺序影响 最好O(log n) 最坏O(n2) 怎样使得BST始终保持O(log n)级的平衡状态？ Adelson-Velskii和Landis发明了AVL树 一种平衡的二叉搜索树 任何结点的左子树和右子树高度最多相差1,ACM竞赛中所用到的数据结构,AVL树的性质,可以为空 具有n个结点的AVL树，高度为O(log n) 如果T是一棵AVL树 那么它的左右子树TL、TR也是AVL树 并且| hL-hR|1 hL、hR 是它的左右子树的高度,ACM竞赛中所用到的数据结构,解决不平衡的方法旋转,我们可以使用一系列称为旋转(rotation)的局部操作解决这个问题 LL和RR的情
10、况可以通过单旋转(single rotation)来解决 RL和LR的情况可以通过双旋转(double rotation)来解决 调整的整个过程称之为重构(restructuring),ACM竞赛中所用到的数据结构,AVL的使用,因为旋转的过程较为复杂，需要较大的编码量，在实际比赛中，我们一般使用C+ STL（Standard Template Library）标准模板库 。 定义：map tree; 查找：tree.find(key); 访问：tree.begin().first表示keytype的值 插入、删除：tree.insert(make_pair(key,val);tree.era
11、se(tree.begin();失败返回tree.end(); 插入或更改：treekey=val;,ACM竞赛中所用到的数据结构,红黑树的使用,其插入、删除、修改的算法复杂度均为n*log(n)。 具体实现也比较复杂，可以参考相关数据结构书籍，在比赛中一般也使用STL. 集合 定义：set t;multiset t(a.begin(),a.end(),cmp); 插入：tree.insert(val); multiset返回bool; set返回pair其中.second表示是否插入成功, .first表示新元素或现存同值元素的位置。 改变：该类型内容是只读的，不能改变 查找：tree.fi
12、nd(val);返回值为val的第一个元素的迭代器；tree.lower_bound(val); 返回第一个大于等于val的元素位置 删除：tree.erase(tree.begin();,ACM竞赛中所用到的数据结构,字典树 trie,Trie结构 基于关键码分解的数据结构，叫作Trie结构 “trie”这个词来源于“retrieval” 主要应用 信息检索 用来存储英文字符串，尤其大规模的英文词典 自然语言理解系统中经常用到,ACM竞赛中所用到的数据结构,Trie结构应用字典树,存储字典里面的单词 英文的单词是有26个字母组成的（简单起见，我们忽略大小写） 英文字符树每一个内部结点都有26
13、个子结点 树的高度为最长字符串长度,ACM竞赛中所用到的数据结构,字典树 trie,ACM竞赛中所用到的数据结构,字典树的改进,由于单词可能不等长，所以更好的存储是其内部结点 不存储单词信息，只有叶结点才存储单词信息,ACM竞赛中所用到的数据结构,字典树中的检索,首先用待查关键码的第一个字符与树林的各个根的字符相比较，然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，接着再沿着前次比较相等的分支进行进一步的检索，.，直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现； 若检索一直
14、进行到树叶，那么就在树目录里找到了给定的关键码,ACM竞赛中所用到的数据结构,Trie树的插入,Trie树的插入 首先根据插入纪录的关键码找到需要插入的结点位置 如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录 如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可,ACM竞赛中所用到的数据结构,Trie树的删除,Trie树的删除 根据插入纪录的关键码找到需要删除的结点位置 如果一个被删除结点的父结点没有其他的儿子，那么就需要合并 否则只需要将此分支设置为空即可,ACM竞赛中所用到的数据结构,后缀树和后缀数组,百度百科中 后缀树 后缀
15、数组 附件中相关资料 后缀树.pdf 后缀数组.doc,ACM竞赛中所用到的数据结构,关于后缀数组,字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在ACM比赛中中后缀数组比后缀树要更为实用。,ACM竞赛中所用到的数据结构,树,树的一般表示法 数组父亲表示法 儿子节点表示法（用指针构建多叉树） 比赛的时候常用vector来构造 左儿子右兄弟表示法,ACM竞赛中所用到的数据
16、结构,哈夫曼树,哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。 定义： 结点之间的路径长度：从一个结点到另一个结点之间的分支数目。 树的路径长度：从树的根到树中每一个结点的路径长度之和。(PL),ACM竞赛中所用到的数据结构,哈夫曼树,PL计算,ACM竞赛中所用到的数据结构,哈夫曼树,结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作： WPL为最小的二叉树就称作最优二叉树或哈夫曼树。,ACM竞赛中所用到的数据结构,哈夫曼
17、树,WPL的计算 完全二叉树不一定是最优二叉树。,ACM竞赛中所用到的数据结构,哈夫曼树构造算法（贪心）,（1）根据给定的n个权值w1,w2,.,wn构造n棵二叉树的集合F=T1,T2,.,Tn，其中Ti中只有一个权值为wi的根结点，左右子树为空；（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。,ACM竞赛中所用到的数据结构,哈夫曼树的构造图,ACM竞赛中所用到的数据结构,树状数
18、组,树状数组是一个查询和修改复杂度都为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 +
19、 A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16,ACM竞赛中所用到的数据结构,树状数组,ACM竞赛中所用到的数据结构,树状数组,设节点编号为x，那么这个节点管辖的区间为2k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，所以很明显： Cn = A(n 2k + 1) + + An 算这个2k有一个快捷的办法，定义一个函数如下即可： int lowbit(int x) return x ,ACM竞赛中所用到的数据结构,树状数组,当想要查询一个SUM(n)时，可依据如下算法即可： step1:令s
20、um = 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)的。,ACM竞赛中所用到的数据结构,树状数组推广,二维树状数组 求suma1.m1.n 维护和查询复杂度均为O(logm*logn) 用于动态求子阵和,数组内容保存在sum
21、.a中 还可以进一步推广到三维树状数组,ACM竞赛中所用到的数据结构,*线段树,它是能够在log(MaxLen)时间内完成线段的添加、删除、查询等操作。 参考论文： 数据结构的选择与算法效率 从IOI98试题PICTURE谈起,ACM竞赛中所用到的数据结构,胜者树Winner Tree,一种基于空间分割的数据结构 可以动态求s.t之间的最大/最小值 时间复杂度： 建树 n*log(n) 查询s.t最大/最小值log(t-s+1); 动态更新某个元素的值 log(n); 空间复杂度O(2*n),ACM竞赛中所用到的数据结构,笛卡尔树Cartesian Tree,笛卡尔树，就是一棵树，这棵树的父节
22、点的值小于树的子节点值，并且树的中序遍历满足在原数组中的顺序（一个点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)。
23、,ACM竞赛中所用到的数据结构,笛卡尔树Cartesian Tree,笛卡尔树的建立 Cartesian Tree 笛卡尔树是这样的一棵树，它满足键值的结构是二叉搜索树，而内容就是prio值。 其实它也是个堆。 笛卡尔树主要用于将RMQ问题转化成LCA问题,ACM竞赛中所用到的数据结构,Hash散列,Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 数学表述为：h = H(M)
24、，其中H( )-单向散列函数，M-任意长度明文，h-固定长度散列值,ACM竞赛中所用到的数据结构,Hash散列,当两个或两个以上的关键字散列到同一个值的时候，发生冲突。 解决方法：开散列和闭散列 Hash冲突取决于 Hash函数的选择 散列空间的大小 输入数据 开闭散列,ACM竞赛中所用到的数据结构,字符串散列ELFHash函数,/prime:3001,5003,10007,20011,50021,100003,150001,200003,500009,704447,901963,1009237, 1199993, 1500007,2000003,5000011 int ELFhash(cha
25、r *key) unsigned int g,h=0; while (*key) h=(h24; h/Size要用大质数 ,ACM竞赛中所用到的数据结构,字符串散列SuperFastHash(1),#define get16bits(d) (unsigned int)(d)1)=2; for (;len0;len-) g+=get16bits(key);key+=2; h=(get16bits(key)11; ,ACM竞赛中所用到的数据结构,字符串散列SuperFastHash(2),switch(rem) case 3:g+=get16bits(key);g=g11; break; case
26、 2:g+=get16bits(key);g=g17; break; case 1: g+=*key;g=g1; break; g=g5; g=g17; g=g6; return g%M; ,ACM竞赛中所用到的数据结构,整数Hash函数,常用平方取余数 int IntegerHash(int key) unsigned int p=key*key; /溢出就溢出 return p%Size; /返回0.size-1 ,ACM竞赛中所用到的数据结构,集合set STL,ACM竞赛中所用到的数据结构,集合set STL,ACM竞赛中所用到的数据结构,集合multiset STL,ACM竞赛中所用
27、到的数据结构,集合multiset STL,ACM竞赛中所用到的数据结构,并查集Disjoint Sets,并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。 并查集的主要操作有 1合并两个不相交集合 Union(A,B) 2判断两个元素是否属于同一个集合 Findroot(X),ACM竞赛中所用到的数据结构,Disjoint Sets,Findroot(x)同BST一样，最坏情况为一条链，那么进行一次Find操作的时间复杂度为O(N)，代价太大。 改进方法: 1.启发式合并 将结点少的树合并到结点多的树上。 2.路径压缩 当一条路找到根结点了以后，把所有处于路径中的结点的父亲指针
28、直接指向该集合的父亲。,ACM竞赛中所用到的数据结构,二叉堆,一种特殊的树形数据结构，每个结点都有一个值。二叉堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。 建堆 O(n*log(n)/ O(n); 插入元素 log(n); 删除最大/最小元素log(n); 无论是插入还是删除，最关键的都在于调整。,ACM竞赛中所用到的数据结构,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:
29、n-2 sort_heap(a,a+n,cmp) 将堆an-1化为排序好的数组an-1 bool cmp(int x,int y) return xy; /最大堆 a0为堆顶元素。,ACM竞赛中所用到的数据结构,映射2分堆,二项堆不能删除任意元素 在二项堆的基础上，加上一个索引之后，就成了映射2分堆，这时候就可以在log(n)的时间内删除元素。 而Fibonacci堆也支持插入、删除、查找最大最小元素，算法复杂度都很低，但是编程复杂度却很高。,ACM竞赛中所用到的数据结构,几种堆的比较,ACM竞赛中所用到的数据结构,优先队列,#include #include priority_queue , greater q3;,ACM竞赛中所用到的数据结构,Priority_queue,struct Rec char word20; ; struct CMP /特别的，重载的是() bool operator () (const Rec ,