数据结构与算法—必知必会的50个代码实现

AI研习图书馆，发现不一样的精彩世界

数据
结构

数据结构与算法必知必会知识点

数据结构与算法知识图谱

为了让大家对数据结构与算法能够有一个比较全面的认识，我找了一张图，里面几乎涵盖了所有数据结构与算法参考书籍中都会讲到的知识点，如上图所示。

图中共有10种数据结构：数组、链表、图、栈、队列、散列表、二叉树、堆、跳表、Trie 树；10个算法：递归、排序、搜素、二分查找、哈希算法、贪心算法、回溯算法、分治算法、动态规划、字符串匹配算法。

如果我们掌握了这些基础的数据结构与算法知识点，再学习更加复杂的数据结构，就会非常容易和迅速快。下面附上一张可参考的学习路线图。

数据结构与算法学习路线图，可参考

数据结构与算法是工程师的内功心法和基本功之一。无论是人工智能领域，还是其它计算机科学领域，掌握扎实的数据结构与算法知识，都是从事相关职业必不可少的基本要求！

今天给大家推荐一份非常不错的数据结构与算法学习资源。特点是：全代码实现！

资源的作者王争老师，前 Google 工程师，5 万+人跟着学的《数据结构和算法之美》专栏作者。大佬总结了工程师必备的 50 个数据结构与算法，以及相应的代码实现。开源地址为：

https://github.com/wangzheng0822/algogithub.com

这必备的 50 个数据结构与算法具体包含了如下内容，目录如下。

数组

• 问题1：实现一个支持动态扩容的数组

• 问题2：实现一个大小固定的有序数组，支持动态增删改操作

• 问题3：实现两个有序数组合并为一个有序数组

链表

• 问题1：实现单链表、循环链表、双向链表，支持增删操作

• 问题2：实现单链表反转

• 问题3：实现两个有序的链表合并为一个有序链表

• 问题4：实现求链表的中间结点

栈

• 问题1：用数组实现一个顺序栈

• 问题2：用链表实现一个链式栈

• 问题3：编程模拟实现一个浏览器的前进、后退功能

队列

• 问题1：用数组实现一个顺序队列

• 问题2：用链表实现一个链式队列

• 问题3：实现一个循环队列

递归

• 问题1：实现斐波那契数列求值f(n)=f(n-1)+f(n-2)

• 问题2：实现求阶乘n!

• 问题3：实现一组数据集合的全排列

排序

• 问题1：实现归并排序、快速排序、插入排序、冒泡排序、选择排序

• 问题2：实现O(n)时间复杂度内找到一组数据的第K大元素

二分查找

• 问题1：实现一个有序数组的二分查找算法

• 问题2：实现模糊二分查找算法（比如大于等于给定值的第一个元素）

散列表

• 问题1：实现一个基于链表法解决冲突问题的散列表

• 问题2：实现一个LRU缓存淘汰算法

字符串

• 问题1：实现一个字符集，只包含a～z这26个英文字母的Trie树

• 问题2：实现朴素的字符串匹配算法

二叉树

• 问题1：实现一个二叉查找树，并且支持插入、删除、查找操作

• 问题2：实现查找二叉查找树中某个节点的后继、前驱节点

• 问题3：实现二叉树前、中、后序以及按层遍历

堆

• 问题1：实现一个小顶堆、大顶堆、优先级队列

• 问题2：实现堆排序

• 问题3：利用优先级队列合并K个有序数组

• 问题4：求一组动态数据集合的最大Top K

图

• 问题1：实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法

• 问题2：实现图的深度优先搜索、广度优先搜索

• 问题3：实现Dijkstra算法、A*算法

• 问题4：实现拓扑排序的Kahn算法、DFS算法

回溯

• 问题1：利用回溯算法求解八皇后问题

• 问题2：利用回溯算法求解0-1背包问题

分治

• 问题1：利用分治算法求一组数据的逆序对个数

动态规划

• 问题1：0-1背包问题

• 问题2：最短路径和

• 问题3：实现莱文斯坦最短编辑距离

• 问题4：实现查找两个字符串的最长公共子序列

• 问题5：实现一个数据序列的最长递增子序列

以上所有的数据结构与算法知识点，作者都配备了相应的程序代码，而且项目的一大特点是：代码同时实现了多种编程语言，例如 Python、C、Java、Go、Scala 等等，太强了。