ProApe

分类

OJ题(25) 数据结构(7) 算法(4)

/ 注册

全部文章（共36篇）

Minimum Spanning Tree

题意：有一棵边带有权值的树，定义线图：将这颗树的每一条边缩成一个点，这个点的点权为原先的边权，当原先树中两条边有公用的节点时，则线图中缩成的两个点有边相连，且边的权值为这两个点的点权之和。求形成的线图的最小生成树。解题思路：你会发现在原先的树中，父节点和他紧邻的所有子节点形成的线图是一个完全图，...

2020-01-02

0 524

Line-line Intersection

题意：给了N条线（注意这些线有可能重合），问两条直线有交点的对数，1 3和3 1 属于同一对，两条直线重合也算有交点解题思路：这道题有些细节是很恶心的因为怕卡精度，所以直接用了pair存，用map套一个pair存储斜率，但是只存储斜率是不行的，因为直线有重合的情况，所以还得用map套两个pai...

2020-01-02

0 552

二叉树基本操作的实现

实验项目五：二叉树基本操作的实现课程名称：数据结构实验项目名称：二叉树基本操作的实现实验目的： 1．掌握树的基本操作—遍历。实验要求： 1、分别用递归和非递归的方法实现一棵树的三种遍历。实验过程： 1、创建一棵二叉树（二叉树如下图所示）； 2、用递归算法实现对该树的三种遍历； 3、...

2020-01-02

0 637

串基本操作的实现

实验项目四：串基本操作的实现课程名称：数据结构实验项目名称：串基本操作的实现实验目的： 1．掌握串的模式匹配操作。实验要求： 1、分别使用BF和KMP算法完成串的模式匹配。实验过程： BF算法代码;; 1、设计完成next值的计算函数； 2、设计完成修正next值的函数； 3、 K...

2020-01-02

0 767

二叉树的线索化&&线索二叉树的遍历（中序）

二叉树的线索化：对于N个节点的二叉树，在二叉存储链表中有N+1个空链域，利用这些空链域存放某种遍历次序下的指向该节点的前驱和后继的指针，这些指针成为线索，被线索的二叉树成为线索二叉树。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索...

2020-01-02

0 711

洛谷P2921

刚看到这道题的时候，没有在意复杂度，就直接暴力了，我也真是憨了，这可是提高省选组的题……后来看看算法标签说是记忆化搜索，再仔细看看题，这不就是每个顶点出度只有一的有向图嘛，包括自环，且是多个连通块，然后，每一个顶点停止遍历的时候一定是进入了一个环内或者自身是某个环的一部分，否则遍历是不会停止的，那么...

2020-01-02

0 590