数据结构例题选讲

《数据结构例题选讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1数据结构例题选讲L7we二叉堆二叉堆是一种完全二叉树，树的每个节点有一个权值，对于树的每棵子树都有：其根节点的权值不差于该子树上任何点的权值功能：O(1)得到堆中的最优值，log(n)的维护由于二叉堆是完全二叉树，可以像线段树一样用一维数组存储，当数组从下标1开始存储时，对于每个点（下标为i），其父亲结点的下标为i/2，左儿子结点下标为i*2，右儿子结点下标为i*2+1基本操作：插入，删除二叉堆插入：voidpush(intx){heap[++heap_size]=x;intcur=heap_size;intfather=cur/2;whil

2、e(father>=1){if(cmp(heap[cur],heap[father])){swap(heap[cur],heap[father]);cur=father;father=cur/2;}elsebreak;}}二叉堆删除：intpop(){intans=heap[1];heap[1]=heap[heap_size--];intcur=1;intchild=cur*2;while(child<=heap_size){if(child+1<=heap_size&&cmp(heap[child+1],heap[child]))child+

3、+;if(cmp(heap[child],heap[cur])){swap(heap[cur],heap[child]);cur=child;child=cur*2;}elsebreak;}returnans;}树状数组应用树状数组功能：log(n)复杂度解决区间问题树状数组中的每个点管辖一段区间，通过某种规则可以方便的把1~n这种区间分成几块，每一块刚好是一个点的管辖区间，于是统计就方便了每个点记录管辖区域内的和，可以log(n)复杂度求得区间和每个点记录管辖区域内最值，可以log(n)复杂度求得区间最值每个点记录值落在管辖区域内的数的个数，

4、可以log(n)复杂度求得值在某个区间内的数的个数等等Enemyisweek给定n个数a1、a2、a3……an，求满足i,j,k(iaj>ak成立的i,j,k的三元组个数(n<=10^6,ai<=10^6)枚举i,j,k，复杂度n^3枚举j，对于每个j寻找满足的i,k，复杂度n^2Enemyisweek需要至少nlog(n)算法枚举j，需要优化寻找i,k的办法树状数组每个点记录有多少个数的值落在其管辖区域内从前向后扫一遍数组，维护树状数组，对每个j用log(n)复杂度计算满足ai>aj的i从后向前扫一遍数组，维护树状数组，对

5、每个j用log(n)复杂度计算满足ak=bi且两不等式不同时取等号的二元组(aj,bj)的个数把每个二元组映射为二维空间里的点，a为x坐标，b为y坐标，即是对每个点求位于其左上方，包含正上方、正左方，但不包含重叠点的点的个数把点按y从大到小排序，y相等时按x从小到大排序，树状数组维护x值落在管辖区域内的点的个数注意处理重点情况字典树给定一些单词apple，banana，orange，pear，strawber

6、ry……给出一些询问，每个询问为一个单词pear，people，orange…对于每个询问，回答其是否在给定的单词中出现过字典树枚举复杂度n*m*L，n为给定单词数，m为询问数，L为平均单词长度，一般不可接受假如把单词换成数字，即给定一些数，询问查询某个数是否出现过，假如数的范围不大，直接开数组记录即可，假如数比较大，需要加哈希重点是如何记录字符串使之可以方便存取字典树字典树是一颗t元有序树t元：t为字符串中可能出现的字符种类数。比如，要用字典树表示纯由小写字母组成的字符串，t为26有序树：结点的每个儿子互不等价。比如二叉树，左儿子与右儿子有区

7、别每个结点代表一个字符串，其儿子所代表的字符串为该点代表的字符串后面加一个字符，加的字符与它是父亲的第几个儿子有关字典树t=3空aacbacbbcbaaccacaabacbabbbccacbcc字典树如何表示一棵树堆&线段树，由于是完全二叉树，故可以用一维数组表示假如用一维数组表示字典树，需要空间复杂度量级在t^L，一般不可取动态分配内存，需要链表基础字典树typedefstructN{intflag;//记录该结点表示的字符串是否存在structN*next[26];}Node;Node*Create(){Node*p=(Node*)mall

8、oc(sizeof(Node));for(inti=0;i<26;i++)p->next[i]=NULL;p->flag=0;return0;}字典树