ACM竞赛中所用到的数据结构VIP专享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){