-
『数据结构』RMQ 问题
所属栏目：[安全] 日期：2020-12-15 热度：149
RMQ (Range Minimum/Maximum Query)，即区间最值问题。 对于长度为 n 的数列 A ，回答若干查询 RMQ(A,i,j)(i,j=n) ，返回数列 A 中下标在 i,j 里的最大(小)值。 相关算法 朴素（搜索），时间复杂度： O ( n ) ? O ( q × n ) ，online 线段树，时间复杂度：[详细]
-
【数据结构】三遍读书法的成果-思维导图
所属栏目：[安全] 日期：2020-12-15 热度：104
第一轮：（粗略翻书，用时2天） 第二轮：（仔细阅读，用时7天） 【第一章】 【第二章】 【第三章】 【第四章】 【第五章】 【第六章】 【第七章】 小结 1以上的思维导图有不足是肯定的，会在更进一步的深入体会中不断完善 2这是第4次备考了，一切驾轻就熟，[详细]
-
TYVJ1463 智商问题【数据结构】【分块】
所属栏目：[安全] 日期：2020-12-15 热度：117
描述 某个同学又有很多小姊妹了 他喜欢聪明的小姊妹 所以经常用神奇的函数来估算小姊妹的智商 他得出了自己所有小姊妹的智商 小姊妹的智商都是非负整数 但是这个同学看到别的同学的小姊妹 也喜欢用神奇的函数估算一下 然后看看这个小姊妹在自己的小姊妹群体[详细]
-
【数据结构】树 的实现代码
所属栏目：[安全] 日期：2020-12-15 热度：69
传送门：https://github.com/whq703/DataStructure 目前实现了： 1、二叉搜索树 2、AVL树 3、红黑树 只想说很多博客的代码是没测试过的。。[详细]
-
【数据结构】树状数组笔记
所属栏目：[安全] 日期：2020-12-15 热度：149
树状数组（Binary Indexed Tree,BIT） 转自大牛柳婼 の bloghttps://www.liuchuo.net/archives/2268 本质上是按照二分对数组进行分组，维护和查询都是O(lgn)的复杂度 树状数组与线段树：树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树[详细]
-
【数据结构】【并查集模板】
所属栏目：[安全] 日期：2020-12-15 热度：150
void init()//初始化函数 {int i;for(i = 1; i = n; i ++)f[i] = i;return;}int find(int v)//查找根结点 {if(f[v] == v)return v;else{//这里是路径压缩，每次在函数返回时，把遇到的结点改为根结点的编号//提高找到根结点的速度 f[v] = find(f[v]);return[详细]
-
【数据结构】【堆排序】
所属栏目：[安全] 日期：2020-12-15 热度：99
这里是先建立最大堆，再从小到大输出堆元素。具体实现及其解释见代码。 总结：像这样支持插入元素和寻找最大（小）值元素的数据结构称为优先队列。堆就是优先队列的实现，很大程度的降低了时间复杂度。 另外Dijkstra算法每次找离源点最近的一个顶点也可以用[详细]
-
HDU 5239 Doom [线段树,更新有上界]【数据结构】
所属栏目：[安全] 日期：2020-12-15 热度：184
好久没有更新博客了 更新一波吧，，， 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5239 —————————————————————————————————————— Doom Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 524288/524[详细]
-
【数据结构】后缀表达式-->表达式树
所属栏目：[安全] 日期：2020-12-15 热度：166
原文，转载如下： 用到了栈，并且递归实现了中序遍历，后序遍历，前序遍历。 同时应该学会union的使用方法。 基础知识： 一、表达式树 表达式树的树叶是操作数(operand)，加常数或变量名字，而其他的结点为操作数(operator)。由于这里所有的操作都是二元的，[详细]
-
【数据结构】中缀表达式转换为后缀表达式
所属栏目：[安全] 日期：2020-12-15 热度：78
原文，转载如下： 一、后缀表达式求值 后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为： 6 5 2 3 + 8 * + 3 + *， 则其求值过程如下： 1）遍历表达式，遇到的数字首先放入栈中，此时栈如下所示： 2）接着读到“+”[详细]
-
【数据结构】务实篇
所属栏目：[安全] 日期：2020-12-15 热度：104
数据结构 名词定义 指 相互之间存在着一种或多种关系的 数据 元素的集合+该集合中数据 元素 之间的关系组成。记为： Data_Structure=(D,R) 其中 D 是数据元素的 集合 ， R 是该集合中所有元素之间的关系的 有限集合 。 指的是 数据的存储形式 ，常见的有 线[详细]
-
【数据结构】揭开面纱（摘抄）
所属栏目：[安全] 日期：2020-12-15 热度：89
学习背景 1976年瑞士计算机科学家Niklaus Wirth曾提出一个著名公式：Algorithm+Data Structures=Programs（算法+数据结构=程序），并以此为书名写了一本书。他本人也于1984 年获得了图灵奖，是瑞士学者中唯一获此殊荣的人。 数据结构基本认识 数据结构是计算[详细]
-
【数据结构】Treap的实现与应用
所属栏目：[安全] 日期：2020-12-15 热度：72
本篇博客作者：czj Treap的本质是一颗二叉查找树，只是在每个结点上都附加了一个优先级的信息。保证每个点的优先级都比左右儿子小，利用优先级，我们可以把这颗树看成一个小根堆。 Treap树在随机给优先级的情况下，可以在期望O(logn)的时间复杂度里完成： 一[详细]
-
【数据结构】搜索二叉树
所属栏目：[安全] 日期：2020-12-15 热度：81
手写实现搜索二叉树： 树的节点定义： class TreeNode{ public : TreeNode ( int v) : value (v){}; TreeNode* left_son = NULL; TreeNode* right_son = NULL; TreeNode* p = NULL; //一定保存双亲的指针 int value = 0 ;}; 节点插入： bool TreeInsert(Tree[详细]
-
【数据结构】 三元组的转置
所属栏目：[安全] 日期：2020-12-15 热度：141
#include stdio.h#define maxsize 100//三元组结点：typedef int datatype;typedef struct{ int x;int y;datatype value;} Triple;//稀疏矩阵：typedef struct { Triple data[maxsize];int row;int val;int num;/*行、列、非零元素个数*/ } TsMatrix;void ma[详细]
-
【数据结构】二叉树的层次遍历2
所属栏目：[安全] 日期：2020-12-15 热度：60
#includestdio.h#includestdlib.htypedef char DataType;//树结点的数据类型定义typedef struct BTnode{DataType data;struct BTnode* lchild,*rchild;}BTree;//队列的结点数据类型定义typedef struct node{ BTree * tdata; //存放树结点类型的指针 struct n[详细]
-
【数据结构】 二叉树 非递归遍历
所属栏目：[安全] 日期：2020-12-15 热度：79
以下是我自己的一些写法，由于本人修行尚浅，因此代码难免有不当之处，如有发现，敬请指出，如有雷同纯属巧合。 /* 先序遍历 * 思路： 先输出根 并一直寻找左子树，同时，若存在右子树，则右子树入栈。 * 找完所有的左子树之后，栈顶出栈，重复上述工作，一[详细]
-
【数据结构】普里姆算法
所属栏目：[安全] 日期：2020-12-15 热度：98
学习比较痛苦的一个普里姆算法，别废话了！上码如下： /*名称：普里姆算法 语言：数据结构C语言版 编译环境：VC++ 6.0日期：2014-3-25 */#include stdio.h#include limits.h#include malloc.h #includecstdlib #include string.h #define MAX_VERTEX_NUM 20/[详细]
-
【数据结构】平衡二叉树[AVL树](一)——插入
所属栏目：[安全] 日期：2020-12-15 热度：162
AVL 树是带有平衡条件的二叉查找树，所谓的平衡条件就是每个节点的左子树和右子树的高度最大差别为1。平衡二叉树的实现大部分过程和二叉查找树是一样的，区别在于要时刻保持树的平衡，所以在插入和删除之后要添加一个旋转算法来保持平衡，保持平衡需要借助一[详细]
-
【数据结构】双向链表表示和实现
所属栏目：[安全] 日期：2020-12-15 热度：51
数据结构 双向链表表示和实现 参考代码如下： /*名称：双向链表表示和实现编译环境：VC++6.0日期： 2014-3-27*/#include stdio.h#include malloc.h#include stdlib.htypedef int ElemType;// 线性表的双向链表存储结构 typedef struct DuLNode{ElemType data[详细]
-
【数据结构】栈应用之进制转换
所属栏目：[安全] 日期：2020-12-15 热度：158
进制转换就是将十进制数转换成相应的二进制、八进制和十六进制。原理是将十进制模二进制或者八进制或者十六进制所得的余数按从低到高的顺序入栈后，再按从高到底的顺序出栈，就可以将要得到的进制数输出。 #include stdio.h#include stdlib.h#include malloc[详细]
-
【数据结构】二叉树、AVL树
所属栏目：[安全] 日期：2020-12-15 热度：172
二叉树 二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。 二叉树有几点重要的性质[详细]
-
【数据结构】[luoguP1440]求m区间内的最小值
所属栏目：[安全] 日期：2020-12-15 热度：68
题目 线段树做了一遍 t了三个点可能是我太弱 代码如下 #includeiostream #includecstdio #includecctype using namespace std; # define in = read() typedef long long ll; const ll size = 8000000 + 10000 ; # define left (rt1) # define right (rt1|1)[详细]
-
【数据结构】算法时间复杂度分析
所属栏目：[安全] 日期：2020-12-15 热度：111
【前言】 从一开始接触数据结构的时候，就对时间复杂度了解不清晰，后来的多次考试中都有接触，但还是感觉没有把握时间复杂度的要点所在。最近学习考研专业课，又一次碰上了时间复杂度，感觉这次学习还是有了收获和进步，特此总结下来，希望对读者有帮助。[详细]
-
【数据结构】[luoguP1886]滑动窗口
所属栏目：[安全] 日期：2020-12-15 热度：71
题目 接近于单调队列的模板了 根据大小之类的入队出队 代码好理解 代码如下 #includeiostream #includecstdio #includecctype using namespace std; #define in = read() typedef long long ll; const ll size = 1000000 + 1000 ; ll n,k; ll a[size]; ll h,[详细]
