starcoming

# 算法与数据结构

如何写好程序

程序 = 算法 + 数据结构

⚠️在作者看来，一个会学计算机的人，脑袋里都应该装着一颗知识树，作者会在该部分以Java为例持续更新，不仅是常用数据结构，一些优秀的算法也会记录。

Data Structure 在线演示的平台 (opens new window)

# 数据结构

# 数据结构定义

带有结构特性的数据元素的集合 --摘自百度百科

# 常用的数据结构与算法

# 线性表

  • 数组 顺序存储
  • 链表 链式存储

# 栈与队列

  • 栈

    顺序存储、链式存储

  • 队列

    顺序存储、链式存储

# 树与图

  • 树

    二叉查找树（BST）、二叉平衡树（自平衡二叉查找树（AVL），红黑树（red-black），B树，B+树（MySQL索引）,伸展树（Splay)）

    哈夫曼树

  • 图

    邻接矩阵，邻接表，邻接多重表（无向图）

# 其他

# 算法思想及其应用

# 时间复杂度概念

一个函数，它定性描述该算法的运行时间 --百度百科

# 算法思想及实际应用

  • 暴力 一切皆可暴力

  • 排序

    冒泡，快排，希尔，堆，外部，选择，二路归并，基数，插入（直接，折半）

    手撕JDK Arrays.sort()

  • 贪心 非2021考纲

    贪心策略，最优子结构

    应用：背包问题，活动时间（课表），线段覆盖，找零钱

  • 查找

    有序数组二分查找，二叉查找树，顺序查找，分块查找，折半查找，Hash表

    手撕JDK HashMap与ConcurrentHashMap

    应用：并查集，求开方，大于给定元素的最小元素

  • 分治 非2021考纲

    问题规模大与相同子问题

    应用：MapReduce，大整数乘法，快排，归并排序

  • 搜索

    最小生成树，关键路径，拓扑排序

    应用：好友关系，N皇后，数独

  • 动态规划

    子问题重叠，无后效，最优化原理

    应用：最短路径

线性表 →