之前转载过一篇kuangbin大佬的kmp模板，只会用，但是不清楚原理 现在看了某大佬的文章，发现讲解的非常精彩，但是有一点不足就是没讲清楚KMP时间复杂度问题，但是自己的语言组织能力以及理解能力也不是很好，所以就直接copyt过来了。希望 _july_v博主不介意。 http://www.cnblogs.com/kuangbin/archive/2012/08/14/2638803.html https://blog.csdn.net/v_july_v/article/details/7041827 首先说明：K…
基于贪心算法的马踏棋盘哈密顿回路问题 Github 链接 问题分析 马踏棋盘其实相当于一个解空间的搜索问题，而遍历到每一个节点并要求最后可以回到起点本质上是一个哈密顿回路问题 目前大部分马踏棋盘的相关问题并不要求回到起点，然后实际上在不重复的走完全盘的可行解中寻找最后可以回到起点的最优解更为困难。可行解有非常多个，然而最优解虽然比可行解少得多，但也并不少 问题在于，这个搜索空间十分的庞大，倘若不考虑棋盘位置约束与遍历次数限制，解空间大小将达到指数级的庞大规模。但是即便在这些解中加上棋盘限制与单次访问等的剪枝条件，为…
基于贪心算法的马踏棋盘哈密顿回路问题 Github 链接 问题分析 马踏棋盘其实相当于一个解空间的搜索问题，而遍历到每一个节点并要求最后可以回到起点本质上是一个哈密顿回路问题 目前大部分马踏棋盘的相关问题并不要求回到起点，然后实际上在不重复的走完全盘的可行解中寻找最后可以回到起点的最优解更为困难。可行解有非常多个，然而最优解虽然比可行解少得多，但也并不少 问题在于，这个搜索空间十分的庞大，倘若不考虑棋盘位置约束与遍历次数限制，解空间大小将达到指数级的庞大规模。但是即便在这些解中加上棋盘限制与单次访问等的剪枝条件，为…
程序功能: 1. 图的邻接表存储 2. 递归深度遍历 3. 非递归深度遍历（借助stack） 4. 递归广度遍历 5. 非递归广度遍历（借助queue） 程序中通过条件编译实现，递归与非递归的选择 //#define _RECURSION_TRAVERSE //递归遍历(将下一行注释，此行不注释) #define _NON_RECURSION_TRAVERSE //非递归遍历(节点本身有isVisited域)(将上一行注释，此行不注释) 注释第一行，保留第二行：实现非递归遍历 注释第二行，保留第一行：…
深入浅出理解 图的 DFS 和 BFS 一、邻接表法建立图 创建图的方法有邻接矩阵和邻接表法。 邻接矩阵把边的关系包含在一个矩阵中，虽然很方便，但是，当图中的定点数远大于边数时，浪费了很大的空间。 邻接表把边与顶点的关系存在一个叫弧（边）的数据结构中，有几条边就创建几条弧。节省了内存空间，但也怎加了对各种结构体之间关系的理解难度。 其实图的DFS和BFS就算法上来看，是非常简单的，但是要很流利的写出图的这两种遍历的算法，要对结构体之间关系有较好的理解。 下面先来看数据结构： typedef enum{ DG,DN,…
//图的相关操作 #include<stdio.h> #include<stdlib.h> typedef int Dtype; #define MAXVEX 20 #define INFINITY 32768 int visited[MAXVEX] = { 0 }; //需要一个辅助数组visited来确定已被访问的元素(注： 0号元素不用) typedef struct ArcNode //定义一个邻接表的邻接点结构体变量 { int Adjvex; //Adjvex表示数组下标 str…
BST树、B-树、B+树、B*树 BST树 即二叉搜索树、二叉查找树、二叉排序树BST： 1.所有非叶子结点至多拥有两个儿子（Left和Right）； 2.所有结点存储一个关键字； 3.非叶子结点的左指针指向小于其…
定义： 一棵m阶B-树是拥有以下性质的多路查找树： 1、非叶子结点的根结点至少拥有两棵子树； 2、每一个非根且非叶子的结点含有k－1个关键字以及k个子树，其中⌈m/2⌉≤k≤m； 3、每一个叶子结点都具有k－1个关键字，其中⌈m/2⌉≤k≤m； 4、key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间 5、所有的叶子结点都在同一层。 ps： ⌈m/2⌉是向上取整 建立B-树的节点： template<class K,int M=3> struct BTreeN…
二叉搜索树 插入和删除操作必须先查找，查找效率代表了二叉搜索树中各个操作的性能 最优情况：二叉搜索树为完全二叉树，比较次数Log2^N 最坏情况：二叉搜索树为单支树，平均比较次数N/2 平衡二叉树 平衡树： AVL树，红黑树 AVL树：（二叉搜索树改良版） AVL树条件：具有二叉搜索树的性质，其左右子树高度之差绝对值不超过1 若AVL树，有N个节点，高度为OlogN，平均搜索时间复杂度O(logN) 旋转 每一次的插入数值之后，树的平衡性可能被破坏，需要通过旋转来保持平衡性 插入节点时候分四种情况，对应下面四种旋转…