| 共 26 篇文章 |
|
如果删除一大块数据，首先要定位数据块首元素和末元素所在的位置，然后分别将它们所在的节点分裂成两个节点，最后删除首元素和末元素之间的节点即可。设块状链表中元素总个数为X，链表长度为n，每个节点中数据长度为m，则当m=n=sqrt(X)时，可保证m和n同时最小，此时各种操作的时间复杂度最低。由于块状链表的每个节点存储的是一个数组，如果数... 阅777 转1 评0 公众公开 12-06-28 03:52 |
并查集（Disjoint set或者Union-find set）是一种树型的数据结构，常用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。上图为两个不相交集合，b图为合并后Father(b):=Father(g)为了避免这种情况，我们需对路径进行压缩，即当我们经过”递推”找到祖先节点后，”回溯”的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find_Set(... 阅91 转0 评0 公众公开 12-06-28 03:51 |
本节介绍了两种比较高效的算法解决这个问题，其中一个是在线算法（DFS+ST），另一个是离线算法（Tarjan算法）。由于RMQ中使用的ST算法是在线算法，所以这个算法也是在线算法。离线算法（Tarjan算法）描述：同上一个算法一样，Tarjan算法也要用到深度优先搜索，算法大体流程如下：对于新搜索到的一个结点，首先创建由这个结点构成的集合，再对当... 阅314 转0 评0 公众公开 12-06-28 03:51 |
线段树的基本操作主要包括构造线段树，区间查询和区间修改。//构造求解区间最小值的线段树 function 构造以v为根的子树 if v所表示的区间内只有一个元素 v区间的最小值就是这个元素, 构造过程结束 end if 把v所属的区间一分为二，用w和x两个节点表示。扩展到二维，需要把线段树进行调整，即首先在横坐标上建立线段树，它的每个节点... 阅604 转1 评0 公众公开 12-06-28 03:50 |
树状数组(binary indexed tree)，是一种设计新颖的数组结构，它能够高效地获取数组中连续n个数的和。树状数组通过将线性结构转换成伪树状结构（线性结构只能逐个扫描元素，而树状结构可以实现跳跃式扫描），使得修改和求和复杂度均为O(lgn)，大大提高了整体效率。3、扩展——二维树状数组。一维树状数组很容易扩展到二维，二维树状数组如下所示... 阅181 转1 评0 公众公开 12-06-28 03:49 |
节点X的父节点Y不是根节点，Y的父节点为Z，X与Y中一个是其父节点的左孩子而另一个是其父节点的右孩子。比如我们要提取区间[a,b]，那么我们将a前面一个数对应的结点转到树根，将b 后面一个结点对应的结点转到树根的右边，那么根右边的左子树就对应了区间[a,b]。方法是：首先利用要插入的数构造一棵伸展树，接着，将a 转到根，并将a 后面一个数对... 阅486 转0 评0 公众公开 12-06-28 03:48 |
『解析』将n 个字符串连起来，中间用不相同的且没有出现在字符串中的字符隔开，求后缀数组。只需要先将每个字符串都反过来写一遍，中间用一个互不相同的且没有出现在字符串中的字符隔开，再将n 个字符串全部连起来，中间也是用一个互不相同的且没有出现在字符串中的字符隔开，求后缀数组。后缀数组实际上可以看作后缀树的所有叶结点按照从左到... 阅137 转1 评0 公众公开 12-06-28 03:48 |
1.素数判定问题。根据素数定义 只需要用2到n-1去除n，如果都除不尽，则n是素数，否则，只要其中有一个数能整除则n不是素数。更高效地素数判断方法应该是将素数预先保存到一个素数表中，当判断一个数是否为素数时，直接查表即可。即欲求n以内的素数，就先把sqrt(n)内的素数求出来，用已经求得的素数来筛出后面的合数。时是素数，这样的数叫费马... 阅134 转1 评0 公众公开 12-06-28 03:47 |
本文介绍了比较初级的图搜索算法，包括深度优先遍历，广度优先遍历和双向广度优先遍历。void dfs1 (graph &g, int i, int n) // 从顶点i 出发遍历 { cout<<g.v[i]; //输出访问顶点 visited[i]=1; //访问标记置1表示已经访问 for(j=1; j<=n; j++) if ((g.arcs[i ][j]= =1)&am... 阅4827 转15 评0 公众公开 12-06-28 03:46 |
