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

ACM竞赛中所用到的数据结构 基本数据结构 基础：队列、堆栈、链表 排序与检索：快速排序和归并排序的思想 串的模式匹配：KMP, Boyer-Moore, Trie(*), 有限状态自动机(*) 树：左儿子右兄弟表示法, AVL(用STL实现), 哈夫曼树,Splay Tree(*), 树状数组，线段树 ，PQ树(***) 字典：Hash、并查集(*)、可并优先队列，堆 关于堆 Heap 二叉堆（又名最大/最小堆） 二项堆 映射2分堆 Fibonacci堆 Interval heap 左偏树Leftist Tree 队列Queue 特点： 先进先出 FIFO 入队O(1), 出队O(1) 不能随机访问中间的元素 实现方法： 链表 数组 STL 队列Queue #includequeue using namespace std; //STL queue queue int Q; Member Functions: 堆栈Stack 特点： 先进后出 FILO 入队O(1), 出队O(1) 不能随机访问中间的元素 实现方法： 链表 数组 STL 堆栈Stack #includestack using namespace std; //STL stack int S; 链表list 特点： 插入O(k) 删除O(k) 查找O(k) 最坏情况下都是O(n) 实现方法： 链表 数组-改进块状数组 STL 链表list #includelist using namespace std; //STL listint S; 链表list 排序 排序 快速排序 O(n*log(n)) 堆排序（稳定排序）O(n*log(n)) 选择排序,冒泡排序 O(n^2) 桶排序 O(M) O(n)随机查找第k小元素 std:sort STL #includealgorithm using namespace std; int a[M],b[M]; sort(a,a+n); sort(a,a+n,cmp); bool cmp(const int x,const int y){ return xy; //return b[x]b[y]; } 随机查找第k小元素 随机第k小元素 int select(int *a,int b,int e,int k){ if(b==e) return a[b]; int x=a[b+rand()%(e-b+1)],i=b-1,j=e+1,tmp; while (ij){ while(a[++i]x); while(a[--j]x); if (ij) tmp=a[i],a[i]=a[j],a[j]=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)线性时间预处理子串，求出前缀函数 O(m)线性时间扫描母串求出匹配 串的模式匹配--KMP //KMP 求前缀函数 int fail[maxlen]; void makefail( char *t, int lt ) { --t; for(int i=1,j=0;i=lt;i++,j++){ fail[i]=j; while(j0 t[i]!=t[j]) j=fail[j]; } } 串的模式匹配--KMP // start matching pattern T in S[i..) // 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; i=ls; i++,j++) { while( j0 s[i]!=t[j] ) j=fail[j]; if( jlongest ) { longest = j; l