分类 程设计科 下的文章

[card title="声明" color="info"]文章内容来自于《C++ Primer Plus》，本文重新组织语言，选取书本部分内容重新组合。[/card]一、什么是指针指针是一个变量，其存储的是值的地址，而不是值本身。在讨论指针之前，我们先看一看如何找到常规变量的地址。只需对变量应用地址运算符（&），就可以获得它的位置，例如，如果home是一个变量，则&home是它的地址。#include<iostream> using namespace std; int main(){ int home=1; double …

[card title="注意" color="info"]无特殊说明，本文中的读入数据来自键盘，输出到屏幕。[/card]一、printf()用法（格式输入函数）printf()函数主要用于输出，它可以将格式化的数据输出到屏幕上，让我们能够清晰地看到程序运行的结果。printf()是在标准库的头文件stdio.h定义的，使用这个函数之前，必须在源码文件头部引入这个头文件（#include<stdio.h>）printf()不会在尾行自动添加换行符，运行结束后，光标就停留在输出结束的地方，不会自动换行。printf()返回值是整数，是输出字符…

二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。Treap简介特点与作用Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不同，创建的二叉搜索树也不同，在最坏的情况下（比如只有左子树或者只有右子树），会退化为线性。若一个二叉搜索树插入的节点顺序时随机的，则得到的二叉搜索树在大多情况下是平衡的，即使存在一些极端的情况但这种情况发生的概率很小，因此以随机…

[card title="主席树" color="info"]主席树，又叫可持久化权值线段树，也叫函数式线段树，是可持久化线段树的子集。在本文中，我们可以认为主席树等于可持久化线段树[/card]可持久化线段树简介基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。优点解释每次插入操作最多创建的节点数都为$\log n$（从根到叶子），一共执行了$n$次插入操作，可持久化线段树的节点总数为$n \log n$，而$n$棵单独的线段树的总节点数是$n^2$，很明显…

二叉堆简介二叉堆是一种基础数据结构，对于其他数据结构来说，支持的操作有限，也就插入，查询，删除这一类。二叉堆的结构从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存在一个权值。堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。由堆性质，树根存的是最大值。对于堆的每个子树，它同样也是一个堆。考虑使用一个序列h来表示堆，$h_i$的两个儿子分别是$h_{2i}$和$h_{2i+1}$，$1$是根节点：来自于：OI Wiki具体每个节点的对应关系如上图。二叉堆的基本操作插入操作插入操作是指向二叉堆中插入…