轉自：微點閱讀（www.weidianyuedu.com）http://www.weidianyuedu.com

數據結構和算法是程序員的內功心法和基本功。無論是人工智能還是其它計算機科學領域，掌握扎實的數據結構和算法知識，往往會助力不少！今天給大家推薦一份不錯的數據結構與算法資源。特點是：全代碼實現！

這份資源的作者王爭老師是前 Google 工程師，5 萬+人跟著學的《數據結構和算法之美》專欄作者。他總結了程序員必備的 50 個數據結構與算法，以及相應的代碼實現。開源地址為：

https://github.com/wangzheng0822/algo

我們來看一下這必備的 50 個數據結構與算法究竟包含了哪些內容。

數組?

• 問題：實現一個支持動態擴容的數組

• 問題：實現一個大小固定的有序數組，支持動態增刪改操作

• 問題：實現兩個有序數組合并為一個有序數組

鏈表?

• 問題：實現單鏈表、循環鏈表、雙向鏈表，支持增刪操作

• 問題：實現單鏈表反轉

• 問題：實現兩個有序的鏈表合并為一個有序鏈表

• 問題：實現求鏈表的中間結點

棧?

• 問題：用數組實現一個順序棧

• 問題：用鏈表實現一個鏈式棧

• 問題：編程模擬實現一個瀏覽器的前進、后退功能

隊列?

• 問題：用數組實現一個順序隊列

• 問題：用鏈表實現一個鏈式隊列

• 問題：實現一個循環隊列

遞歸?

• 問題：編程實現斐波那契數列求值f(n)=f(n-1)+f(n-2)

• 問題：編程實現求階乘n!

• 問題：編程實現一組數據集合的全排列

排序?

• 問題：實現歸并排序、快速排序、插入排序、冒泡排序、選擇排序

• 問題：編程實現O(n)時間復雜度內找到一組數據的第K大元素

二分查找?

• 問題：實現一個有序數組的二分查找算法

• 問題：實現模糊二分查找算法（比如大于等于給定值的第一個元素）

散列表?

• 問題：實現一個基于鏈表法解決沖突問題的散列表

• 問題：實現一個LRU緩存淘汰算法

字符串?

• 問題：實現一個字符集，只包含a～z這26個英文字母的Trie樹

• 問題：實現樸素的字符串匹配算法

二叉樹?

• 問題：實現一個二叉查找樹，并且支持插入、刪除、查找操作

• 問題：實現查找二叉查找樹中某個節點的后繼、前驅節點

• 問題：實現二叉樹前、中、后序以及按層遍歷

堆?

• 問題：實現一個小頂堆、大頂堆、優先級隊列

• 問題：實現堆排序

• 問題：利用優先級隊列合并K個有序數組

• 問題：求一組動態數據集合的最大Top K

圖?

• 問題：實現有向圖、無向圖、有權圖、無權圖的鄰接矩陣和鄰接表表示方法

• 問題：實現圖的深度優先搜索、廣度優先搜索

• 問題：實現Dijkstra算法、A*算法

• 問題：實現拓撲排序的Kahn算法、DFS算法

回溯?

• 問題：利用回溯算法求解八皇后問題

• 問題：利用回溯算法求解0-1背包問題

分治?

• 問題：利用分治算法求一組數據的逆序對個數

動態規劃?

• 問題：0-1背包問題

• 問題：最小路徑和

• 問題：編程實現萊文斯坦最短編輯距離

• 問題：編程實現查找兩個字符串的最長公共子序列

• 問題：編程實現一個數據序列的最長遞增子序列

以上所有的數據結構與算法都配備相應的程序代碼。一大特點是代碼配備多種編程語言，例如 Python、C、Java、Go、Scala 等。

舉例來說，關于常見的排序算法，例如冒泡排序、插入排序、選擇排序，作者給出了相應的 Python 代碼實現：

""" Bubble sort, insertion sort and selection sort 冒泡排序、插入排序、選擇排序 Author: Wenru"""from typing import List# 冒泡排序def bubble_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(length): made_swap = False for j in range(length - i - 1): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] made_swap = True if not made_swap: break# 插入排序def insertion_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(1, length): value = a[i] j = i - 1 while j >= 0 and a[j] > value: a[j + 1] = a[j] j -= 1 a[j + 1] = value# 選擇排序def selection_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(length): min_index = i min_val = a[i] for j in range(i, length): if a[j] < min_val: min_val = a[j] min_index = j a[i], a[min_index] = a[min_index], a[i]def test_bubble_sort(): test_array = [1, 1, 1, 1] bubble_sort(test_array) assert test_array == [1, 1, 1, 1] test_array = [4, 1, 2, 3] bubble_sort(test_array) assert test_array == [1, 2, 3, 4] test_array = [4, 3, 2, 1] bubble_sort(test_array) assert test_array == [1, 2, 3, 4]def test_insertion_sort(): test_array = [1, 1, 1, 1] insertion_sort(test_array) assert test_array == [1, 1, 1, 1] test_array = [4, 1, 2, 3] insertion_sort(test_array) assert test_array == [1, 2, 3, 4] test_array = [4, 3, 2, 1] insertion_sort(test_array) assert test_array == [1, 2, 3, 4]def test_selection_sort(): test_array = [1, 1, 1, 1] selection_sort(test_array) assert test_array == [1, 1, 1, 1] test_array = [4, 1, 2, 3] selection_sort(test_array) assert test_array == [1, 2, 3, 4] test_array = [4, 3, 2, 1] selection_sort(test_array) assert test_array == [1, 2, 3, 4]if __name__ == "__main__": array = [5, 6, -1, 4, 2, 8, 10, 7, 6] bubble_sort(array) print(array) array = [5, 6, -1, 4, 2, 8, 10, 7, 6] insertion_sort(array) print(array) array = [5, 6, -1, 4, 2, 8, 10, 7, 6] selection_sort(array) print(array)

當然，還有其它編程語言的代碼實現，這里就不一一列舉了！

目前，這份資源已經在 GitHub 上收獲了 6000 星了。是一份不錯的數據結構與算法參考代碼。值得一看。

?

總結

以上是生活随笔為你收集整理的数据结构与算法必备的 50 个代码实现。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。