数据结构与算法--常用数据结构与高级数据结构

常用的数据结构

数组

优点：

构建一个数组非常简单

根据小标查找的复杂度是o(1)

缺点：

构建时必须分配一段连续的空间

查询某个元素是否存在时要遍历整个数组，复杂度为o(n)

删除和添加某个元素，时间复杂度为o(n)

链表

优点：

灵活的分配内存空间

能在o(1)的时间复杂度内删除或者添加元素

缺点：

查询元素需要o(n)的时间

栈

特点：

后进先出

队列

特点：

先进先出

常用场景：

广度优先搜索

树

树的共性：

结构直观

通过树问题来考察 递归算法

面试中常见的树的形状：

普通二叉树

平衡二叉树

完全二叉树

二叉搜索树

四叉树

多叉树

遍历：

前序遍历

中序遍历

后序遍历

高级数据结构

优先队列

与普通队列的区别：

保证每次取出的元素是队列中优先级别最高的

优先级可自定义

常用的场景：

从杂乱无章的数据中按一定顺序（或者优先级）筛选数据

图

基本知识点：

阶、度

树、森林、环

有向图、无相图、完全有向图、完全无向图

连通图、连通分量

图的存储和表达方式：邻接矩阵和邻接链表

必须熟练掌握的知识点

图的存储和表达方式：邻接矩阵 邻接链表

图的遍历：深度优先 广度优先

二部图的检测、树的检测、环的检测、有向图、无向图

拓扑排序

联合-查找算法

最短路径

前缀树

也称字典树，广泛运用在字典查找中

重要性质：

children：数组或者集合，罗列出每个分支当中包含的所有字符

isEnd：布尔值，表示该节点是否为某字符串的结尾

最基本的操作：

创建

搜索

线段树

一种按照二叉树形式存储的数据结构，每个节点保存的都是数组里某一段的总和

树状数组

基本特征：

利用数组来表示多叉树的结构

优先队列是用数组来表示完全二叉树，而树状数组是多叉树