[转]算法与数据结构——入门总结与自学资料推荐

时间:2022-12-20 16:23:14

[转]算法与数据结构——入门总结与自学资料推荐

本文转自(http://www.cnblogs.com/jiahuix/p/4868881.html

一、大纲

[转]算法与数据结构——入门总结与自学资料推荐

[转]算法与数据结构——入门总结与自学资料推荐

   

博客董西城Vamei

思维导图下载地址http://pan.baidu.com/s/1gdCqW8r

   

[转]算法与数据结构——入门总结与自学资料推荐

二、数据结构资料推荐

数组:查找快O(1),插入删除慢O(n)

链表:查找慢O(n),插入删除快O(1)

块状链表:查找插入删除O(sqrt(n));数组+链表;

[转]算法与数据结构——入门总结与自学资料推荐

队列:先进先出

堆栈:先进后出

双端队列:队列与堆栈结合,有headtail的数组,队首队尾都可以增删。

[转]算法与数据结构——入门总结与自学资料推荐

哈希表

  • 集合A到集合B的映射;
  • 哈希函数:MD5, SHA
  • 应用:文件对比,密码存储;
  • 碰撞解决:open hashing -> 链表;closed hashing -> 数组下标移动到空位(rehashing移动到更大的新数组) hash table

Bit-Map:一个bit代表一个数字,比如10bit可以代表1~10 bitmap

二叉堆/:高度为(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算法求最小生成树等。

 

三、算法资料推荐

基本思想:动态规划剪枝回溯法

排序:快速排序归并排序堆排序桶排序七大排序对比

字符串:KMPKMPKMP

数论:排列组合

   

树:

遍历:每个节点都检查

先序遍历:上、左、右

中序遍历:左、上、右

后序遍历:左、右、上

   

深度优先搜索DFS通过栈来实现

[转]算法与数据结构——入门总结与自学资料推荐

   

广度优先搜索BFS通过队列来实现

[转]算法与数据结构——入门总结与自学资料推荐

   

   

   

*图片来源于网络~>_<~