acm竞赛所用数据结构

《acm竞赛所用数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、表数组STL队列Queue#includeusingnamespacestd;//STLqueuequeueQ;MemberFunctions:堆栈Stack特点：先进后出FILO入队O(1),出队O(1)不能随机访问中间的元素实现方法：链表数组STL堆栈Stack#includeusingnamespacestd;//STLstackS;链表list特点：插入O(k)删除O(k)查找O(k)最坏情况下都是O(n)实现方法：链表数组->改进块状数组STL链表list#includeusingnamespa

3、cestd;//STLlistS;链表list排序排序快速排序O(n*log(n))堆排序（稳定排序）O(n*log(n))选择排序,冒泡排序O(n^2)桶排序O(M)O(n)随机查找第k小元素std:sortSTL#includeusingnamespacestd;inta[M],b[M];sort(a,a+n);sort(a,a+n,cmp);boolcmp(constintx,constinty){returnx>y;//returnb[x]

4、,inte,intk){if(b==e)returna[b];intx=a[b+rand()%(e-b+1)],i=b-1,j=e+1,tmp;while(ix);if(i

5、配算法简称为KMP算法朴素的串模式匹配的复杂度是O(m*n)长度为m的母串S,匹配长度为n的子串A求母串S中有多少个子串A求母串S中第1个子串A的位置KMP算法的复杂度为O(m+n)总体思想O(n)线性时间预处理子串，求出前缀函数O(m)线性时间扫描母串求出匹配串的模式匹配--KMP//KMP求前缀函数intfail[maxlen];voidmakefail(char*t,intlt){--t;for(inti=1,j=0;i<=lt;i++,j++){fail[i]=j;while(j>0&&t[i]!=t[j])j=fail[j];}}串的模式匹配--KMP/

6、/startmatchingpatternTinS[i..)//returnmatchposorlongestmatchlengthwithcorrespondingposintkmp(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;

7、}串的模式匹配--BM快速的字符串查找算法Boyer-Moore算法BM算法是一个较优的模式匹配算法。一般，如果不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明，BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KMP匹配和BM匹配，进一步提高效率。串的模式匹配--BM算法的关键和KMP类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是

8、ASCII