程式設計師必備：資料結構和演算法知識大綱，全面細緻，架構師熬夜總結

資料結構和演算法是每個程式設計師都應該掌握的技能。

特意給大家總結了一份《資料結構和演算法的知識大綱》，希望對大家有幫助。

文末有福利，會給你一個小小的驚喜！別忘了收哦

一：內容概述

本知識大綱主要內容包含：

1：陣列

有序和無序陣列的操作、二分法查詢、存放物件、大O表示法

2：棧

線形表、棧、棧的操作、棧的例項、字尾表示式（包括轉換和計算）

3：佇列

佇列、佇列的實現、迴圈佇列、雙端佇列、優先順序佇列

4：連結串列

連結串列、單鏈表、雙端連結串列、用連結串列實現棧和佇列、有序連結串列、雙向連結串列

5：遞迴演算法

遞迴、階乘、分治演算法、斐波那契數列、漢諾塔、揹包問題、歸併排序

6：排序演算法

冒泡、選擇、插入法、希爾、快速、基數、物件排序

7：二叉樹

二叉樹概念和性質、二叉樹的實現、哈夫曼編碼、哈夫曼樹、哈夫曼演算法、使用哈夫曼演算法來實現壓縮和解壓的功能

8：紅黑樹

概念和特徵、紅黑樹的規則和修正、紅黑樹的旋轉、紅黑樹的實現

9：2-3-4樹

概念和規則、2-3-4樹的實現、2-3-4樹和紅黑樹的關係和轉換規則

10：B樹

概念和特性、B樹的高度、B樹的實現、B樹的變形

11：堆

概念和特點、堆的實現、堆排序

12：雜湊表

概念和優缺點、Hash函式的構建、衝突解決（開放地址法和鏈地址法）、Hash化字串

13：圖

概念和基本術語、深度和廣度搜索、最小生成樹、有向圖的拓撲、有向圖的連通、Warshall演算法、帶權圖的最小生成樹、普里姆演算法、最短路徑問題、迪傑斯特拉演算法、弗洛伊德演算法

二：Java資料結構和演算法知識大綱

1：陣列

陣列是什麼

對陣列的插入、刪除、查詢操作

無序陣列

重複放值

不重複放值

有序陣列

二分法查詢

存放物件

大O表示法

2：簡單排序

氣泡排序

選擇排序

插入法排序

物件排序

3：棧

線性表

線性表概念

線性表和陣列的關係

什麼是棧

棧的基本操作

push：壓棧或入棧操作

pop：彈棧或出棧操作

peek：檢視棧頂資料，而不彈出資料，也就是不做出棧操作

棧的基本實現

棧的應用例項

字串倒序

括號（小、中、大）匹配

計算算術表示式

字尾表示式

什麼是字尾表示式，也稱波蘭逆序表示式

如何把中綴表示式轉換成字尾表示式

計算字尾表示式求值

棧的效率

4：佇列

什麼是佇列（Queue）

佇列的基本操作

insert：在隊尾插入資料

remove：從隊頭移走資料

peek：檢視隊頭的資料

迴圈佇列

佇列的基本實現

佇列的效率

雙端佇列

優先順序佇列

優先順序佇列就是資料項按照關鍵字排好順序的佇列

優先順序佇列的實現

優先順序佇列的效率

5：連結串列

什麼是連結串列（Linked List）

連結串列和陣列

連結串列的基本操作

向連結串列中插入資料

從連結串列中移走資料

檢視連結串列中所有的資料

查詢指定鏈結點

刪除指定鏈結點

單鏈表

單鏈表的基本實現

單鏈表的效率

雙端連結串列

雙端連結串列是，不僅僅記錄著開始結點，同時也記錄著結束結點

雙端連結串列的實現

使用連結串列來實現棧和佇列

有序連結串列

有序連結串列就是連結串列中的資料是排好順序的

有序連結串列的實現

有序連結串列的效率

使用有序連結串列來實現插入排序

雙向連結串列

什麼是雙向連結串列

雙向連結串列的實現

6：遞迴演算法

什麼是遞迴

遞迴示例：階乘

理解遞迴

遞迴示例：斐波那契數列

漢諾塔（河內塔）問題

揹包問題

歸併排序

7：高階排序

希爾排序

快速排序

基數排序

8：二叉樹

樹的基本知識

二叉樹的概念和理解

二叉樹的性質

二叉搜尋樹

二叉搜尋樹是什麼

二叉搜尋樹的查詢、插入、遍歷、查詢最大最小值和刪除操作

二叉搜尋樹操作的效率

用陣列來表示樹

哈夫曼（Huffman）編碼

哈夫曼樹

什麼是哈夫曼樹

哈夫曼樹的構造方法——Huffman演算法

哈夫曼壓縮的編碼部分的實現步驟

統計

建樹

編碼

輸出

哈夫曼壓縮的解碼部分的實現步驟

讀取碼錶的資訊，構建出碼錶來

讀回具體的資料內容

把讀回的位元組還原成對應的整型資料

根據碼錶，把內容組成的哈夫曼編碼，依次轉換回原始的字元，從而得到原始的內容

9：紅黑樹

平衡與非平衡樹

紅黑樹是什麼以及特徵

紅黑樹的規則

紅黑樹的修正手段

紅黑樹的旋轉

紅黑樹的插入演算法

紅黑樹的節點刪除

紅黑樹的刪除演算法

刪除步驟後的調整步驟

紅黑樹的效率

瞭解其它平衡樹：AVL

10：2-3-4樹

多叉樹

2-3-4樹是什麼

2-3-4樹的資料組織規則

2-3-4樹的搜尋演算法

2-3-4樹的插入演算法

2-3-4樹的節點刪除

2-3-4樹和紅黑樹

2-3-4樹轉換成紅黑樹的規則

2-3-4樹的效率

11：B樹

B樹是什麼

回憶磁碟存取資料的知識

B樹的特性

B樹的高度

B樹的搜尋演算法

B樹的插入演算法

B樹的刪除演算法

12：B+樹

B+樹是什麼

B+樹和B樹的特性差異

B+樹的優勢

B+樹的磁碟讀寫代價更低

B+樹的查詢效率更加穩定

B+樹支援基於範圍的查詢

13：Hash表

Hash表是什麼

Hash表的優缺點

什麼是Hash化

Hash函式的基本過程

常用的構造Hash函式的方法

直接定址法

數字分析法

平方取中法

摺疊法

隨機數法

除留餘數法

Hash衝突

Hash衝突的解決

開放地址法

線性探測

二次探測

再雜湊法

鏈地址法

設計好的Hash函式

Hash化字串

Hash化的效率

14：堆

堆是什麼

堆的特點

堆的插入演算法

堆的刪除演算法

堆的查詢

堆的效率

堆排序

堆排序的基本思想

堆排序的效率

15：圖（不帶權）

圖是什麼

圖的基本術語

在程式中表示圖

圖的搜尋（遍歷），演算法並程式碼示例

深度優先

廣度優先

最小生成樹，演算法並程式碼示例

有向圖的拓撲排序，演算法並程式碼示例

有向圖的連通性，演算法並程式碼示例

Warshall演算法，演算法並程式碼示例

16：帶權圖

什麼是權

帶權圖的最小生成樹

普里姆演算法，程式碼示例

最短路徑問題

迪傑斯特拉演算法，程式碼示例

弗洛伊德演算法，程式碼示例

稀疏圖和稠密圖

圖的效率

如果你覺得本系列文章還不錯，能夠給你一些啟發和思考的話，請關注、點贊、收藏加轉發，讓更多的朋友加入到我們的行列，謝謝啦！

更多架構師之路乾貨文章，已在路上，稍後就到！

本文福利：與上面大綱的內容配套的精品影片，免費贈送，獲取方式：

1：還沒有關注我的朋友，請關注我，關注的時候，會自動回覆百度網盤地址

2：已經關注的朋友，請私信傳送關鍵字：演算法 ，就“演算法”兩個字就可以，會自動回覆百度網盤地址

創作不易，多謝你的支援！