平衡二叉树介绍 平衡二叉树,是一种二叉排序树,其中每一个节点的左子树和右子树的高度差最多等于1。由3位科学家共同发明,用他们首字母命名 又被称为AVL树。从平衡二叉树的名称,你也可以体会到它是一种高度平衡的二叉排序树。我们将二叉树上结点的左子树深度减去右子树的深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只能是-1,0,1。 平衡二叉树的实现原理 平衡二叉树构建的基本思想就在在构建二叉排序树的过程中,每当插入一个结点时,先检查否是因为插入而破坏了树的平衡性,若是,这找出最小不平衡树,在满足二叉排序树…

2018年4月28日 0条评论 5点热度 阅读全文

插值查找算法介绍 插值查找(Interpolation Search)是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式key-arr[low]/arr[high]-arr[low]。细看是不是key在整序列中的占比哟。所以mid的计算公式为: (high-low)*(key-arr[low])/(arr[high]-arr[low])。对比折半查找的mid = (high-low)/2。 代码和折半查找一模一样,唯独mid的计算方式发生改变。这样的好处在于,对表长较…

2018年2月27日 0条评论 6点热度 阅读全文

折半查找算法介绍 折半查找(Binary Search)又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。从算法名称可以看出算法的思路,先取有序序列中间值与查找值进行比较,中间值小于查找值 就查找后一子表,如果中间值大于查找值 就查前移子表,直到查找到或者子表不存在为止。由于折半查找的查找范围是成倍的缩写,所以折半查找法的算法时间复杂度为logn。 折半查找算法代码 代码简单哟,因为我们并不知道循环次数,所以优先采用的while 循环,当然for、while、do…

2018年2月27日 0条评论 6点热度 阅读全文

算法代码很简单都是用使用递归计算,大家把递归思想领悟到就ok了。 二叉树高度算法 //求二叉树的高度 采用递归的方式 void GetHeight(BiTree tree, int* heightNum) { if (NULL != tree) { int LHeight; int RHight; GetHeight(tree->lchild,&LHeight); GetHeight(tree->rchild,&RHight); *heightNum = LHeight > RHi…

2018年2月21日 0条评论 3点热度 阅读全文

邻接表介绍 邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构比较较浪费存储空间。如果不想浪费存储空间,大家肯定会先到链表。需要空间的时候再才想内存去申请,同样适用于图的存储。我们把这种数组与链表相结合的存储方式成为邻接表(Adjacency List)。关于邻接矩阵的详细介绍请看:图:图的邻接矩阵创建、深度优先遍历和广度优先遍历详解 。 邻接表创建图 我们创建边表的单链表时,可以使用头插法和尾插法创建,不过尾插法要麻烦一点,需要先创建头结点,最后还要释放头结点,不过2种方…

2018年2月20日 0条评论 9点热度 阅读全文

邻接矩阵介绍 直接说,邻接矩阵是图的一种存储结构。那么图是什么呢?图是一种逻辑结构,和线性结构、树形结构、集合结构一样 是一种逻辑结构用来描述数据对象中的数据元素之间的关系。来看下图的定义:图(Graph)是有顶点的有穷非空集和顶点之间边的集合组成,通常表示为G(V,E)其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。 考虑到图是有顶点和边或弧2部分组成。合在一起比较困难,那就自然的考虑到分为2个结构来分别存储。 图的邻接矩阵(Adjacency Matrix)存储方式是用2个数组来表示图。一个一维数…

2018年2月20日 0条评论 6点热度 阅读全文

前言 KMP算法可以说说许多学习算法的同学的第一道坎,要么是领会不到KMP算法的思想,要么是知道思想写不出代码,网上各种查找。关于算法的书籍上也都有KMP算法的实现,可为啥自己写不出来呢?博主看得大话数据结构上的分析,书上的代码都比较精简,但是不易理解 ,跟着代码思路走结果也是对的。那么我们为啥我们不可以多写几行代码 更加容易理解呢。博主今天就用普通程序员的思路 去写KMP算法 采用C语言实现,虽然代码可能会多那么几行,如果你能看懂,那我也就很高兴了,如果看不懂 请看大话数据结构中KMP的实现领略其思想 然后自己实…

2018年2月3日 0条评论 5点热度 阅读全文

进制转换原理 二进制转十进制 二进制是计算机数据的存储形式,它是由一串0和1组成,每个二进制数转换成相应的十进制数方法为: (XnXn-1Xn-2...X3X2X1)2 = X1*2^0+X2*^1+...Xn*2^(n-1)。 二进制转八进制 利用二进制转十进制原理,从低位起将每3位二进制转为1位十进制 然后进行替换即可。 二进制转十六进制 利用二进制转十进制原理,从低位起将每4二进制位转为1位十进制然后进行替换即可,不过在16进制中用 a、b、c、d、e、f 代替10、11、12、13、14、15。 如何用栈实…

2018年1月21日 0条评论 5点热度 阅读全文

有道算法面试题:快速找到未知长度单链表的中间节点。 你可以普通方法也可用比较好的方法,去解决这个问题。 由于单链表不知道长度,必须遍历完整个单链表才知道单恋表的长度,然后根据一般的长度去找中间结点,这是普通方法。 当然题目问的是快速找到,当然要用快速的方法啦。 这里我们快慢指针的方法来解决这个问题,快指针每次走2个结点,慢指针每次走1个结点,当快指针走完链表,慢指针刚好走到中间,这就是快慢指针的核心思想。 下面直接看代码,只要我们知道核心思想,然后把代码完善好,就ok了。代码里面也有注释,使用c写的哈。 #defi…

2018年1月5日 0条评论 3点热度 阅读全文

继续学习数据结构。今天学习循环队列,在学习循环队列之前,我们得先知道什么是队列呀,然后才可以继续往下学习。 首先我们回顾下队列的相关知识。 队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 队列是一种先进先出的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。 队列同样是一种线性表,队列也有类似线性表的各种操作,不同的是插入的数据是在队尾进行,删除数据只能在队头进行。 那么我们同样可以使用顺序存储结构去实现队列。试想下我们使用使用数组进行队列的插入删除操作,会有什么…

2017年12月26日 0条评论 0点热度 阅读全文