数据结构与算法(文末附思维导图)

数据结构与算法的重要性，不管你学什么编程语言，不管你从事前端、后台、算法、数据挖掘、机器学习、人工智能等岗位，数据结构和算法是绕不过去的。语言无关性，岗位无关性。数据结构与算法在面试中也是频频出现，基本一场面试有50%以上的时间再问这方面的内容。

基本概念&术语

数据&数据元素&数据项&数据对象

逻辑结构&存储结构

逻辑结构 线性结构   线性表    一般线性表     线性表   特殊线性表     栈和队列     字符串   线性表的推广     数组     广义表非线性结构    树结构   树   二叉树   图结构   有向图   无向图存储结构   顺序存储结构   链式存储结构

数据类型&抽象数据类型

算法&算法分析

算法是为了解决某类问题而规定的一个有限长的操作序列 算法特性  有穷性  确定性  可行性  有效的输入  算法输出评价算法优劣  正确性  可读性  健壮性  高效性算法效率分析  算法的时间复杂度  算法的空间复杂度

线性结构

线性表

顺序表示顺序表:逻辑&物理 次序上均相邻 链式表示单链表双链表循环链表链表和顺序表的比较 空间维度比较 时间维度比较 链表和顺序表的面试笔试题 线性表的推广数组广义表

栈

栈的定义&特性 后入先出 栈的表示&常用操作 顺序栈&链式栈 入栈&出栈 栈与递归栈的应用

队列

队列的定义&特性 先入先出 队列的表示&常用操作 循环队列&链式队列 出队&入队 队列的应用

串

串的概念 串的结构 顺序存储 链式存储 串的匹配算法 BF算法 KMP算法

非线性结构

树

树的基本概念 二叉树 性质&存储结构 二叉树的遍历 线性二叉树 二叉树的建立 哈弗曼树 基本概念 构造算法 哈夫曼编码 AVL树B树

图

概念存储结构邻接表邻接矩阵十字链表邻接多重表边集数组遍历深度优先遍历广度优先遍历应用最小生成树 最短路径拓扑排序关键路径

高级数据结构

• 自顶向下的伸展树
• 红黑树

插入插入时的旋转经常考删除

• 确定性跳跃表
• AA树
• treap树
• k-d树
• 配对堆

算法

• 查找

概念 线性表查找 顺序查找 二分查找 分块查找 树形查找 二叉树查找 AVL树查找 B-树B+树 哈希查找 冲突解决

• 排序

概念冒泡排序选择排序插入排序希尔排序堆排序归并排序快速排序基数排序桶式排序大型数据结构的排序 外部排序(非内存的方式排序)

• 图论算法
• 贪婪算法
  
• 分治算法
  
• 动态规划
  
• 随机化算法
  
• 回溯算法