banner
cos

cos

愿热情永存,愿热爱不灭,愿生活无憾
github
tg_channel
bilibili

c++

cover

链式前向星存图、二分图匹配之匈牙利算法 模板&分析(存用)

参考博客:链式前向星 -- 最通俗易懂的讲解、算法讲解:二分图匹配【图论】、趣写算法系列之 -- 匈牙利算法、匈牙利算法与增广路径 暑假整的忘了发 2333 @TOC 1. 是什么 如果说邻接表是不好写但效率好,邻接矩阵是好写但效率低的话,前向星就是一个相对中庸的数据结构…
模板类封装(2)——顺序栈和链式栈
c++ 语言,链栈实现 实验内容: 编程实现栈的如下功能: (1)建立一个长度为 n 的顺序栈,元素类型可自行定义,并输出栈中各元素值。 (2)将数据元素 e 入栈,并输出入栈后的顺序栈中各元素值。 (3)将顺序栈中的栈顶元素出栈,并输出出栈元素的值和出栈后顺序栈中各元素值…
cover

模板类封装(1)——单链表

加入了 ReverseList 函数,逆转单链表操作 改了个 bug,逆转链表时特判一个结点的情况 又改了 N 个 bug,特判空链表的情况 试试模板类加上数据结构 肯定还是会有遗漏的地方的,欢迎指正 不多说,上代码 ps是 c++11 特性,使用时需注意 Copy templ…
cover

状压dp——模板&分析&例题(存用)

状压讲解部分参考博客状压 DP 详解(位运算) 这里是引用 状压 dp,即将状态压缩成 2 进制来保存,如矩阵中将一行的状态压缩成一个二进制串,如 dp [S][v] 中,S 可以代表已经访问过的顶点的集合,v 可以代表当前所在的顶点为 v。S 代表的就是一种状态…
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover

数据结构学习笔记<9> 散列查找

1. 概念引出 编译处理中对变量的管理:动态查找问题 利用查找树进行?—— 两个变量名(字符串)比较效率不高 将字符串转换为数字,再处理?—— 即为散列查找的思想 已知的几种查找方法: 顺序查找 O (N) 二分查找(静态查找) O (log~2~N) 二叉搜索树 O…
cover

归并排序循环实现(存用)

递归的归并排序是很占空间和时间的,而非递归算法就不一样了,额外空间复杂度最少为 O (N)。 陈越姥姥的慕课里就讲得很清楚~戳这儿 这里就直接上代码 + 注释了 Copy #include <iostream> #include <cstdio> #include <queue…
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover
cover

数据结构学习笔记<8> 排序

1. 概念定义 AOV 网络 例如,假定一个计算机专业的学生必须完成图 3-4 所列出的全部课程。从图中可以清楚地看出各课程之间的先修和后续的关系。如课程 C5 的先修课为 C2,后续课程为 C4 和 C6。通常,我们把这种顶点表示活动…
cover

博弈论——模板&分析(存用)

描述 基本的斐波那契博弈(Fibonacci Game)描述如下: 有一堆石子,两个顶尖聪明的人玩游戏,先取者可以取走任意多个,但不能全取完,之后每次可以取的石子数至少为 1,至多为对手刚取的石子数的 2 倍。约定取走最后一个石子的人为赢家,求必败态。 结论 当且仅当总石子…
cover
cover

MOOC浙大数据结构课后题记录——PTA数据结构题目集(全)

原博指路:MOOC 浙大数据结构课后题记录 ——PTA 数据结构题目集 (全) 本博客是为了记录学习数据结构时做的题集,若代码有疏漏欢迎指出! 也相当于是一个数据结构的总结了~ ps:因为已经学过 c++ 了所以都用 c++ 写了,但也有很多 c 语言的东西。 MOOC 传送门…
图论——解决最小生成树问题(Kruskal算法&Prim算法)
上周末的蓝桥杯省模拟赛时最后一题是一道最小生成树的题目,因为恰好在慕课上刚看到这个地方,所以现学了 Prim 算法,解决了这个题目 (大概),赛后就打算多琢磨琢磨这一类题目。题目链接 最小生成树问题,是指给定无向图 G=(V,E),连接 G 中所有点,且边集是 E 的子集的树称为…
cover
cover
cover
cover
cover
cover
cover
cover
cover

数据结构学习笔记<7> 图

1. 什么是图 表示 “多对多” 的关系,包含了: 一组顶点:通常用 V (Vertex) 表示顶点集合 一组边:通常用 E (Edge) 表示边的集合 无向边是顶点对:(v,w) ∈ E,其中 v,w∈V 有向边 <v,w> 表示从 v 指向 w 的边 (单行线) 不考虑重…
动态规划学习笔记(1)
记录一下慕课学习的笔记,以及例题代码 一。递归到动规的一般转化方法 递归函数有 n 个参数就定义一个 n 维的数组, 数组的下标是递归函数参数的取值范围。 这样就可以从边界值开始逐步填充数组,相当于计算递归函数值的逆过程。eg:例题 1 数字三角形 二。动规解题的一般思路 1…
cover
cover
cover
cover
cover
cover

数据结构学习笔记<6> 堆与哈夫曼树与并查集

1. 堆是什么 堆(Heap), 是一个可以被看做一棵完全二叉树的数组对象,有以下性质: 任意节点的值是其子树所有结点中的最大值 / 最小值(有序性) 堆总是一棵用数组表示的完全二叉树。 2. 最大堆的操作函数 定义 Copy typedef struct…
cover
cover

RMQ问题——线段树

上篇说到 RMQ 问题可以用 ST 表算法处理,但需要在线修改的时候,线段树是更好的选择。 如图,很明显线段树是个二叉搜索树 要注意的点如下: 线段树用数组存储,数组空间简单的就一般开到原数组的 4*n 倍(准确的说是将 n 向上扩充到 2 的幂次方然后乘 2,如 5->8-…
cover
cover
cover
cover
cover
cover
cover
cover

数据结构学习笔记<5> 二叉搜索树与平衡二叉树

1. 二叉搜索树是什么 二叉搜索树(BST,Binary Search Tree), 又称二叉排序树或二叉查找树,是一棵二叉树,可以为空,当不为空时满足以下性质: 非空左子树的所有键值小于其根结点的键值 非空右子树的所有键值大于其根结点的键值 左、右子树都为二叉搜索树 2…
cover
cover

RMQ问题——ST表算法

ST 表是什么 ST 表是一个用来解决区间最值问题查询的算法 它用O (nlogn) 复杂度预处理,可以实现 O (1) 复杂度的查询。 缺点:无法支持在线修改 模板题:ST 表 - 洛谷 1. 预处理 用一个二维数组 dp [i][j] 表示下标为 i ~ i + 2^j^ -…
cover
cover
cover
cover
cover

数据结构学习笔记<4> 二叉树

一、什么是树 1. 树的定义 树(Tree):n(n≥0)个结点构成的有限集合。 当 n=0 时,称为空树; 对于任一棵非空树(n>0), 它具备以下性质: 树中有一个称为 “根(Root)” 的特殊结点,用 r 表示。 其余结点可分为 m(m>0)个互不相交的有限集 T1…
cover
cover

数据结构学习笔记<3> 队列

一、队列的抽象数据类型描述 类型名:队列(Queue) 数据对象集:一个有 0 个或多个元素的有穷线性表 操作集:长度为 MaxSize 的堆栈 Q∈Queue, 队列元素 item∈ElementType 1. 生成长度为 MaxSize 的空队列 Queue…
ブログは、創作者によって署名され、ブロックチェーンに安全に保存されています。