数据结构和算法总结

2/10/2017来源:ASP.NET技巧人气:841

数据结构和算法总结

数据+数据元之间的关系+数据上的操作(增删改查排)

线性表

按照存储方式分类

1.顺序存储:顺序表、栈、队列。随机访问效率高,随机插入效率低。

2.链式存储:链表。随机访问效率低,随机插入效率高。(只需要定位+修改指针)

按照访问方式分类

1.可以随机访问:一般的线性表。链表、顺序表

2.受限访问:受限线性表。栈、队列

 

各结构细节

1.链表

数据结构里面的入门结构,是树和图的基础,还可以实现栈和队列

1.1常用操作:插入(头插和尾插),删除节点,查找,排序,反转

1.2单链表中带头结点的好处、循环链表中带尾节点的好处

1.3衍生出的复杂结构:双向链表、循环链表、跳跃链表

 

2.栈

只有一端可以操作的数据结构,如栈变量,是最普遍的变量,还有函数栈,递归的时候肯定是要考虑函数栈的大小的,可能遇到的栈溢出(stackoverflow)

2.1常用操作:入栈和出栈

2.2衍生结构:顺序栈(数组形成的栈)、链栈(用链表形成的栈)、共享栈(两个栈但是公用一个区块内存,从两端取)

2.3栈与递归的关系:用递归的函数其实就是在调用函数栈,在一定程度上递归可以理解为就是在使用函数栈

栈的应用(数值表达式计算、前缀、中缀、后缀表达式,括号匹配)

 

3.队列

两端分别只能进行插入和删除操作,在操作系统中广泛使用,如就绪队列,阻塞队列等进程的调用

3.1常用操作:入队和出队

3.2判空判满条件:(针对循环队列)标志位法、牺牲元素空间法

3.3衍生结构:循环队列、双端队列、链队

 

4.树-二叉树为主

基本概念及结论:

1.深度、高度、层次、最多、最少节点数,度(n0=n2+1),(带权)路径长度,满二叉树,完全二叉树

2.存储方式:顺序存储(数组,父子结点下标规律),链式存储(二叉链表)

遍历:

1.按照顺序分类:先序、中序、后序遍历、层次遍历

2.按照编码方式分类:递归和非递归

其他知识点:

1.最优二叉树(哈弗曼树,带权路径长度最短),用于数据压缩和编码

2.树和森林的转换

3.变态二叉树

3.1二叉排序树(二叉搜索树)

3.2二叉平衡树(二叉排序树的强化版)有平衡性,能够自平衡,避免二叉排序树退化成一个链表,将查找性能变成O(N)的最坏情况,而不是想要的logn,其插入、查找、删除的最好最坏时间复杂度都为O(logn)。

3.3红黑树、败者树、KD树、线段树

3.4堆:区分开数据结构里面的堆和内存里面的堆,数据结构里面是所有父节点的值都不大于(小于)子节点的值的完全二叉树称为小(大)顶堆

3.5非二叉树的经典:B树(B-tree)、B+树(B+树所有的值都在叶子层)、B*树,加了指向兄弟节点的指针,使得索引更快(B-树就是B树),数据库的索引很多都是依赖于B+树的,保证了每一个节点上的结点数,保证了层次,还有Trie树、R树、M树

 

5.图

分类:有向图&无向图,完全图、(强)连通图

存储结构:

邻接矩阵:n阶方阵,适用范围是稠密图;对于无向图是一个对称矩阵,只用存储上三角,对于有向图:行数出度,列是入度

邻接表:适合稀疏图,不唯一表示的,顶点表+邻接表,是一个数组+很多链表

遍历:

深度优先遍历(一直找到他不能去的顶点,然后再回一步继续找,借助栈来实现)

广度优先遍历(对于一个顶点全部遍历完,借助的是队列的结构)

和图相关的重要算法:

最小生成树算法:能够权值最小的生成树,PRim算法和kruskal算法

拓扑排序:怎么保证应该在前面,是不唯一的,对于有向图来说是可以有多个拓扑排序序列的

最短路径:Dijkstra算法、Floyd算法

关键路径

 

算法

1.排序

评判排序好不好的标准:时间复杂度、空间复杂度、稳定性(相同键值在同一情况下有没有被改变)

1.1基于关键字比较排序

  1.1.1时间复杂度为O(n^2),空间O(1):插入排序(数据量小并且基本有序,效率较高),冒泡排序(可以优化,最好的情况下能够到O(n)),选择排序(不稳定)

  1.1.2时间复杂度为O(nlogn):

快速排序(不稳定,平均情况下时间复杂度是O(nlogn),平均空间O(logn),这个时候并不是普通意义上申请的空间,而是在递归情况下形成的栈空空间,递归深度,最坏情况时间是O(n^2),空间是O(n),会退化和冒泡差不多,关键在于枢纽元素的选取)

归并排序:稳定,平均和最坏都是时间O(nlogn),空间O(n),分而治之的思想,一般在平时不选用的原因是空间复杂度永远都是O(n)

堆排序:最好最坏时间复杂度都是O(nlogn),空间是O(1),但是不稳定的排序,topK的问题用堆是最快的-->在大量数据中选出前100 使用贪心思想:维护一个你认为最好的100个元素,一直往后遍历一遍就出来了

  1.1.3特殊排序

希尔排序:特点-->书上的是步长:每次除以二  当是100个元素的时候步长为50 25 12 6

时间复杂度O(n^(4/3)),当你所选择的步长O(nlogn)-O(N^2),空间是O(1),不稳定

 

1.2非基于关键字比较的排序

桶排序

计数排序

基数排序

Bitmap排序:时间复杂度是O(n),在一个很小的内存中实现一个整个数的排序

 

2.查找

1.顺序查找

2.数组中的二分查找:边界问题等

3.二叉排序树中的二分查找

4.多路平衡树中的多路/二分查找:B树是其中的一种

5.Trie树的查找(也是多路查找)

6.串的查找(KMP算法)

 

3.散列

散列函数

冲突处理:如何处理映射到同一地址的   二次映射/拉链法/公共池法

用途:文件校验 md5/SHA1值、数字签名、数字加密可以认为是不可逆的(一般情况), 可以加盐

 

4.附加

贪心、动归、分治

 

java

Collection(List、set)、Map