锐客网

  1. 首页 > it技术 > >

（数据结构入门）2018-06-23

1.哈希表（Hash Table）
基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
计数排序（复杂度 O(n+max)）优于比较排序。
桶排序是多个桶的快速排序。
计数排序桶多浪费空间，但是速度快；桶排序桶数自由，但需要二次排序；基数排序适用于大数据的排序。
三种排序都用到了Hash
2.队列（Queue） 先进先出
var q = [ ]//声明一个队列
q.push('张三')
1 //让张三来排队
q.push('李四')
2 //让李四来排队
q.shift()
"张三" //张三先出列
q.shift()
"李四" //李四后出列
基数排序事实上在出桶时是队列
3.栈（Stack） 先进后出
var stack = [ ]//声明一个栈
stack.push('第一层')
1
stack.push('第二层')
【（数据结构入门）2018-06-23】2
stack.pop() //pop：弹出
"第二层梦" //第二层梦先弹出
stack.pop()
"第一层梦" //第一层梦后弹出
Hash是一个数组，队列和栈都可以用数组实现
4.链表（Linked List） 链表主要为理解树做准备
链表图解（用hash 实现）
（数据结构入门）2018-06-23
文章图片
链表 其较于数组的优势是，数组想要删掉中间某个数十分麻烦，而链表只需改变链（中间箭头）的指向
（数据结构入门）2018-06-23
文章图片
去掉a2 如图a1的下一个为a3，a2被删除了，十分方便。
但链表的缺点是，用函数表示时候，取到第an个数，需要链a.next(n-1)次，与数组只需a[n]表示显得十分不便，因此在JS里不常用。
head 表头即a1所在表；node 除表头外的其他表
5.树（tree） 这里用HTML示例
（数据结构入门）2018-06-23
文章图片
html标签的树 树是多链的链表
层数：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；（上图为3）
深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；（上图为2）
节点个数：所有节点个数。（上图为9，无子节点的节点称为叶子节点）
二叉树（Binary tree）
（数据结构入门）2018-06-23
文章图片
二叉树 满二叉树：叶子满的二叉树
（数据结构入门）2018-06-23
文章图片
满二叉树 完全二叉树：除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，此二叉树称为完全二叉树。
（数据结构入门）2018-06-23
文章图片
这种不是完全二叉树 上图情况右边有节点，因此不是完全二叉树
完全二叉树和满二叉树可以用数组实现
堆排序 (Heap Sort)
堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。
伪代码如下
（数据结构入门）2018-06-23
文章图片
堆排序

    推荐阅读


    上一篇：jenkins节点

    下一篇：看三十年职场老手给新人的三条建议！