ACM竞赛中所用到的数据结构VIP免费

ACM竞赛中所用到的数据结构基本数据结构基础：队列、堆栈、链表排序与检索：快速排序和归并排序的思想串的模式匹配：KMP,Boyer-Moore,Trie(*),有限状态自动机(*)树：左儿子右兄弟表示法,AVL(用STL实现),哈夫曼树,SplayTree(*),树状数组，线段树，PQ树(***)字典：Hash、并查集(*)、可并优先队列，堆关于堆Heap二叉堆（又名最大/最小堆）二项堆映射2分堆Fibonacci堆Intervalheap左偏树LeftistTree队列Queue特点：先进先出FIFO入队O(1),出队O(1)不能随机访问中间的元素实现方法：链表数组STL队列Queue#includeusingnamespacestd;//STLqueuequeueQ;MemberFunctions:堆栈Stack特点：先进后出FILO入队O(1),出队O(1)不能随机访问中间的元素实现方法：链表数组STL堆栈Stack#includeusingnamespacestd;//STLstackS;链表list特点：插入O(k)删除O(k)查找O(k)最坏情况下都是O(n)实现方法：链表数组->改进块状数组STL链表list#includeusingnamespacestd;//STLlistS;链表list排序排序快速排序O(n*log(n))堆排序（稳定排序）O(n*log(n))选择排序,冒泡排序O(n^2)桶排序O(M)O(n)随机查找第k小元素std:sortSTL#includeusingnamespacestd;inta[M],b[M];sort(a,a+n);sort(a,a+n,cmp);boolcmp(constintx,constinty){returnx>y;//returnb[x]x);if(i0&&t[i]!=t[j])j=fail[j];}}串的模式匹配--KMP//startmatchingpatternTinS[i..)//returnmatchposorlongestmatchlengthwithcorrespondingposintkmp(char*s,intls,char*t,intlt,inti,int&longest,int&lp){longest=lp=0;--s;--t;for(intj=1;i<=ls;i++,j++){while(j>0&&s[i]!=t[j])j=fail[j];if(j>longest){longest=j;lp=i-j;}if(j==lt)returni-lt;}return-1;}串的模式匹配--BM快速的字符串查找算法Boyer-Moore算法BM算法是一个较优的模式匹配算法。一般，如果不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明，BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KMP匹配和BM匹配，进一步提高效率。串的模式匹配--BM算法的关键和KMP类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引：position[patten[i]]=i;也是相当简单的辅助数组构造。具体可以见http://www-igm.univ-mlv.fr/~lecroq/string/node14.html另外，动态演示程序见附件二叉搜索树BST（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系二叉搜索树在输入数据随机的情况下，算法效率大约为n*log(n)。最坏情况下将退化到链表，O(n^2)推荐题目：FOJ1353HardwoodSpecies平衡树AVLBST受输入顺序影响最好O(l...