算法与数据结构——入门总结与自学资料推荐
博客： 董西城 、V amei
思维导图下载地址： http://pan.baidu.com/s/1gdCqW8r
数据结构资料推荐
数组 ：查找快O(1)，插入删除慢O(n)
链表 ：查找慢O(n)，插入删除快O(1)
块状链表 ：查找插入删除O(sqrt(n))；数组+链表；
队列：先进先出
堆栈：先进后出
双端队列 ：队列与堆栈结合，有head与tail的数组，队首队尾都可以增删。
哈希表 ：
- 集合A到集合B的映射；
- 哈希函数：MD5, SHA；
- 应用：文件对比，密码存储；
- 碰撞解决：open hashing -> 链表；closed hashing -> 数组下标移动到空位（rehashing移动到更大的新数组）hash table
Bit-Map ：一个bit代表一个数字，比如10bit可以代表1~10bitmap
二叉堆/堆 ：高度为(lg^2)n，数组 资料2
最小堆：每个父节点均比子节点小
字典树 （前缀树） ：适合用于字符串检索、字符串最长公共前缀、按字典排序 资料
插入、查找O(N):N为字符串长度，空间O(26^n)
后缀树：适合复杂的字符串操作
后缀树组 ：适合复杂的字符串操作
二叉查找树 ：增删查的复杂度等于深度，深度最多为n，最少为log(n)
数列有序，将会退化成为线性表，即独苗的时候。
删除操作时如果删除节点同时有左右节点，使用删除节点的左子树的最大值或右子树的最小值替换。
B树 ：性能总等于二分法，没有平衡问题。
B+树 ：适合文件索引系统，只在叶子结点命中
B*树 ：在B+树基础上增加兄弟节点指针，增加空间利用率
AVL ：平衡二叉树、深度为O(lgn)、子树深度相差不超过1、单旋转与双旋转 资料
最小深度Math.ceil( log(2)(N+1) )
Treap ：堆树、性能位于普通二叉树与AVL之间
红黑树 ：统计性能比AVL好 资料
splay树 ：伸展树，每次搜索都会进行一次旋转操作，搜索频率大的结点会旋转至根节点。m次搜索复杂度O(mlgn)
线段树 ：高效地询问和修改一个数列中某个区间的信息
树状数组 ：树状数组通过将线性结构转换成伪树状结构（线性结构只能逐个扫描元素，而树状结构可以实现跳跃式扫描），使得修改和求和复杂度均为O(lgn)
图 ：图的表示：二维数组、邻接表
并查集 ：并查集常作为另一种复杂的数据结构或者算法的存储结构。常见的应用有：求无向图的连通分量个数，最近公共祖先（LCA），带限制的作业排序，实现Kruskar算法求最小生成树等。
算法资料推荐
基本思想： 动态规划 、 剪枝 、回溯法
排序： 快速排序 、 归并排序 、 堆排序 、桶排序、 七大排序对比
字符串：KMP、 KMP 、KMP
数论： 排列组合
树：
遍历 ：每个节点都检查
先序遍历：上、左、右
中序遍历：左、上、右
后序遍历：左、右、上
深度优先搜索DFS通过栈来实现
广度优先搜索BFS通过队列来实现
*图片来源于网络~>_<~
正文到此结束
热门推荐
相关文章
近期评论
-
你这基本没有更新呀，最近文章显示还是2019年的文章。不符合要求哈
-
关键词：慕云博客 链接：https://www.lilun.me 描述：分享原创文字的个人博客
-
-
-
可以提供一下源码吗
-
不是商业站，鸡娃学习笔记
-
-
-
-
听他们说很厉害的样子
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
