chengxuyuanxiaohui

漫画算法代码片段GoLang实现

原著：

第一版：https://github.com/bjweimengshu/ProgrammerXiaohui

第二版：https://github.com/bjweimengshu/ProgrammerXiaohui-2

数据结构一览图

几种结构

结构	一	二
物理结构	顺序存储结构	链式存储结构
eg	数组	链表
逻辑结构	线性结构	非线性结构
eg	顺序表、栈、队列	树、图
存取结构	顺序存取	随机存取
eg	顺序表	链表

线性表

数组

数组是由有限个相同类型的变量所组成的有序集合。 它的物理存储方式是顺序存储，访问方式是随机访问。 利用下标查找数组元素的时间复杂度是O(1)，中间插入、删除数组元素的时间复杂度是O(n)

链表

链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一个节点的指针。 它的物理存储方式为随机存储，访问方式是顺序访问。 查找链表的时间复杂度为O(n),中国插入、删除节点的时间复杂度是O(1)

栈

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。 栈包含入栈和出栈操作，遵循先入后出的原则

队列

队列是一种线性逻辑结构，可以用数组实现，也可以用链表实现。 队列包括入队和出队操作，遵循先入先出的原则

散列表

散列表也叫哈希表，是存储key-value映射的集合。 对于某一个key，散列表可以在接近O(1)的时间内进行读写操作。 散列表通过哈希函数实现key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突

树

树

树是n个节点的有限集，有且仅有一个特定的称为根的节点。 当n>1时，其他节点可分为m个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树

二叉树

二叉树是树的一种形式，每一个节点最多有两个孩子节点。 二叉树包括完全二叉树和满二叉树两种特殊形式。 满二叉树：所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上。 完全二叉树：树的所有节点和同样深度的满二叉树节点位置相同

二叉树的遍历方式

根据遍历节点之间的关系：前序遍历、中序遍历、后序遍历、层序遍历 更宏观的角度划分：深度优先遍历、广度优先遍历

二叉堆

顺序存储的完全二叉树。 最大堆：任何父节点的值都 >= 左右孩子节点 最小堆：任何父节点的值都 <= 左右孩子节点

优先队列

最大优先队列：最大堆实现，最大元素优先出队 最小优先队列：最小堆实现，最小元素优先出队

算法

标准

• 时间复杂度（更重要）
• 空间复杂度

应用

• 运算
• 查找
• 排序
• 最优决策

五大思想

• 分治（分而治之）
• 动态规划（全局最优解）
• 贪心（局部最优解）
• 回溯（递归）
• 分治界限