树 一、树 什么是树? N个结点构成的有限集合。 树中有一个称为”根(Root)”的特殊结点,其余结点可分为若干个互不相交的树,称为原来结点的”子树”。 二、常用概念 高度:从叶结点开始自底向上逐层累加的。 深度:从根节点开始自上向下逐层累加的。 层数: 完全二叉树 定义:如果一个树,除去最后一层为满二叉树,而且最后一层节点依次从左至右分布,则为完全二叉树 特性:对于一个完全二叉树从左至右按层次编号 2019-04-23 数据结构 > 树 #数据结构 #树
散列表 概念 散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。 2019-04-20 数据结构 > 散列表 #数据结构 #散列表
跳表 概念 在单链表的基础上,增加多级索引,每级索引都是下一级索引的1/2大小。 查找速度 第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,那第 k级索引结点的个数就是 n/(2k)。 设索引有 h 级,最高级的索引有 2 个结点。通过上面的公式,我们可以得到 n/(2h)=2,从而求得 h=log2n-1。如果包含原始链表这一层,整个跳表的高度就是 log2n。我们在跳表中查询某个数 2019-04-19 数据结构 > 跳表 #数据结构 #跳表
二分查找法 概念 二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。 查找速度 时间复杂度也是 O(logn) 二分查找的递归与非递归实现 非递归 12345678910111213141516func Bsearch(arr []int, n, value int) int { 2019-04-18 算法 > 排序 #算法 #排序
递归 递归 重复将问题分解为同类的子问题而解决问题的办法,表现为函数调用函数本身。 需要满足的三个条件 一个问题可以分解为几个子问题的解 这个问题和子问题除了数据规模,求解思路完全一样 存在递归终止条件 如何编写递归代码? 写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。 如果一个问题 A 可以分解为若干子问题 2019-04-17 数据结构 > 递归 #数据结构 #递归
数组 定义 数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。 线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。 连续的内存空间和相同类型的数据。 2019-04-10 数据结构 > 数组 #数据结构 #数组