這份清單，既是一份有助于對這些題目做深入研究的快速指南和參考，也算是計算機(jī)科學(xué)課程中不能忘記的基礎(chǔ)知識總結(jié)，因此并不可能全面覆蓋所有內(nèi)容。

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

定義

• 按順序連續(xù)存儲數(shù)據(jù)元素，通常索引從0開始

• 以集合論中的元組為基礎(chǔ)

• 數(shù)組是最古老，最常用的數(shù)據(jù)結(jié)構(gòu)

知識要點

• 索引最優(yōu)；不利于查找、插入和刪除（除非在數(shù)組最末進(jìn)行）

• 最基礎(chǔ)的是線性數(shù)組或一維數(shù)組
  

  數(shù)組長度固定，意味著聲明數(shù)組時應(yīng)指明長度

• 動態(tài)數(shù)組與一維數(shù)組類似，但為額外添加的元素預(yù)留了空間
  

  如果動態(tài)數(shù)組已滿，則把每一元素復(fù)制到更大的數(shù)組中

• 類似網(wǎng)格或嵌套數(shù)組，二維數(shù)組有 x 和 y 索引

時間復(fù)雜度

• O(1)索引：一維數(shù)組：O(1)，動態(tài)數(shù)組：O(1)

• O(n)查找：一維數(shù)組：O(n)，動態(tài)數(shù)組：O(n)

• O(log n)最優(yōu)查找：一維數(shù)組：O(log n)，動態(tài)數(shù)組：O(log n)

• O(n)插入：一維數(shù)組：n/a，動態(tài)數(shù)組：O(n)

定義

• 結(jié)點存儲數(shù)據(jù)，并指向下一結(jié)點
  

  最基礎(chǔ)的結(jié)點包含一個數(shù)據(jù)和一個指針（指向另一結(jié)點）

• 鏈表靠結(jié)點中指向下一結(jié)點的指針連接成鏈

要點

• 為優(yōu)化插入和刪除而設(shè)計，但不利于索引和查找

• 雙向鏈表包含指向前一結(jié)點的指針

• 循環(huán)鏈表是一種終端結(jié)點指針域指向頭結(jié)點的簡單鏈表

• 堆棧通常由鏈表實現(xiàn)，不過也可以利用數(shù)組實現(xiàn)
  

  堆棧是“后進(jìn)先出”（LIFO）的數(shù)據(jù)結(jié)構(gòu)

• 由鏈表實現(xiàn)時，只有頭結(jié)點處可以進(jìn)行插入或刪除操作

• 同樣地，隊列也可以通過鏈表或數(shù)組實現(xiàn)
  

  隊列是“先進(jìn)先出”（FIFO）的數(shù)據(jù)結(jié)構(gòu)

• 由雙向鏈表實現(xiàn)時，只能在頭部刪除，在末端插入

時間復(fù)雜度

• O(n)索引：鏈表：O(n)

• O(n)查找：鏈表：O(n)

• Linked Lists: O(n)最優(yōu)查找：鏈表：O(n)

• O(1)插入：鏈表：O(1)

定義

• 通過鍵值對進(jìn)行儲存

• 哈希函數(shù)接受一個關(guān)鍵字，并返回該關(guān)鍵字唯一對應(yīng)的輸出值
  

  這一過程稱為散列（hashing），是輸入與輸出一一對應(yīng)的概念

• 哈希函數(shù)為該數(shù)據(jù)返回在內(nèi)存中唯一的存儲地址

要點

• 為查找、插入和刪除而設(shè)計

• 哈希沖突是指哈希函數(shù)對兩個不同的數(shù)據(jù)項產(chǎn)生了相同的輸出值
  

  所有的哈希函數(shù)都存在這個問題

• 用一個非常大的哈希表，可以有效緩解這一問題

• 哈希表對于關(guān)聯(lián)數(shù)組和數(shù)據(jù)庫檢索十分重要

時間復(fù)雜度

• O(1)索引：哈希表：O(1)

• O(1)查找：哈希表：O(1)

• O(1)插入：哈希表：O(1)

定義

• 一種樹形的數(shù)據(jù)結(jié)構(gòu)，每一結(jié)點最多有兩個子樹

• 子結(jié)點又分為左子結(jié)點和右子結(jié)點

要點

• 為優(yōu)化查找和排序而設(shè)計

• 退化樹是一種不平衡的樹，如果完全只有一邊，其本質(zhì)就是一個鏈表

• 相比于其他數(shù)據(jù)結(jié)構(gòu)，二叉樹較為容易實現(xiàn)

• 可用于實現(xiàn)二叉查找樹

• 由于上述原因，二叉查找樹通常被用作一種數(shù)據(jù)結(jié)構(gòu)，而不是二叉樹

• 重復(fù)的結(jié)點可省略

• 右子樹有比雙親結(jié)點更大的鍵值

• 左子樹有比雙親結(jié)點更小的鍵值

• 二叉樹利用可比較的鍵值來確定子結(jié)點的方向

時間復(fù)雜度

• 索引：二叉查找樹：O(log n)

• 查找：二叉查找樹：O(log n)

• 插入：二叉查找樹：O(log n)

• 搜索基礎(chǔ)

  

定義

• 一種在樹（或圖）中進(jìn)行搜索的算法，從根結(jié)點開始，優(yōu)先按照樹的層次進(jìn)行搜索

• 最下層最右端是最末結(jié)點（即該結(jié)點深度最大，且在當(dāng)前層次的最右端）

• 當(dāng)前一層搜索完畢后，轉(zhuǎn)入遍歷下一層中最左邊的結(jié)點

• 進(jìn)行搜索時，同時追蹤當(dāng)前層中結(jié)點的子結(jié)點

• 搜索同一層中的各結(jié)點，通常從左往右進(jìn)行

要點

• 當(dāng)樹的寬度大于深度時，該搜索算法較優(yōu)

• 進(jìn)行樹的遍歷時，使用隊列存儲樹的信息

• 由于需要存儲指針，隊列需要占用更多內(nèi)存

• 原因是：使用隊列比深度優(yōu)先搜索更為內(nèi)存密集

時間復(fù)雜度

• O(|E| + |V|)查找：廣度優(yōu)先搜索：O(|E| + |V|)

• E 是邊的數(shù)目

• V 是頂點的數(shù)目

定義

• 一種在樹（或圖）中進(jìn)行搜索的算法，從根結(jié)點開始，優(yōu)先按照樹的深度進(jìn)行搜索

• 最右的結(jié)點是最末結(jié)點（即所有祖先中最右的結(jié)點）

• 當(dāng)前這一分支搜索完畢后，轉(zhuǎn)入根節(jié)點的右子結(jié)點，然后不斷遍歷左子節(jié)點，直到到達(dá)最底端

• 一旦到達(dá)某一分支的最末端，將返回上一結(jié)點并遍歷該分支的右子結(jié)點，如果可以將從左往右遍歷子結(jié)點

• 從左邊開始一直往下遍歷樹的結(jié)點，直到不能繼續(xù)這一操作

要點

• 當(dāng)樹的深度大于寬度時，該搜索算法較優(yōu)

• 利用堆棧將結(jié)點壓棧

• 一旦不能向左繼續(xù)遍歷，則對棧進(jìn)行操作

• 因為堆棧是“后進(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)，所以無需跟蹤結(jié)點的指針。與廣度優(yōu)先搜索相比，它對內(nèi)存的要求不高。

時間復(fù)雜度

• O(|E| + |V|)查找：深度優(yōu)先搜索：O(|E| + |V|)

• E 是邊的數(shù)目

• V 是結(jié)點的數(shù)目

廣度優(yōu)先搜索 VS. 深度優(yōu)先搜索

• 這一問題最簡單的回答就是，選取何種算法取決于樹的大小和形態(tài)

• 就深度而言，較窄的樹適用深度優(yōu)先搜索

• 就寬度而言，較淺的樹適用廣度優(yōu)先搜索

細(xì)微的區(qū)別

• 由于廣度優(yōu)先搜索（BFS）使用隊列來存儲結(jié)點的信息和它的子結(jié)點，所以需要用到的內(nèi)存可能超過當(dāng)前計算機(jī)可提供的內(nèi)存（不過其實你不必?fù)?dān)心這一點）

• 如果要在某一深度很大的樹中使用深度優(yōu)先搜索（DFS），其實在搜索中大可不必走完全部深度?？稍?xkcd 上查看更多相關(guān)信息。

• 廣度優(yōu)先搜索趨于一種循環(huán)算法。

• 深度優(yōu)先搜索趨于一種遞歸算法

• 高效排序基礎(chǔ)

  

定義

• 一種基于比較的排序算法

• 重復(fù)上述過程，直到歸并成只有一個數(shù)據(jù)集

• 一旦所有的數(shù)對都完成排序，則開始比較最左兩個數(shù)對中的最左元素，形成一個含有四個數(shù)的有序集合，其中最小數(shù)在最左邊，最大數(shù)在最右邊

• 依次比較每個數(shù)字，將最小的數(shù)移動到每對數(shù)的左邊

• 將整個數(shù)據(jù)集劃分成至多有兩個數(shù)的分組

要點

• 這是最基礎(chǔ)的排序算法之一

• 必須理解：首先將所有數(shù)據(jù)劃分成盡可能小的集合，再作比較

時間復(fù)雜度

• O(n)最好的情況：歸并排序：O(n)

• 平均情況：歸并排序：O(n log n)

• 最壞的情況：歸并排序：O(n log n)

定義

• 一種基于比較的排序算法

• 在左半部分重復(fù)上述操作，直到左邊部分的排序完成后，對右邊部分執(zhí)行相同的操作

• 通過選取平均數(shù)將整個數(shù)據(jù)集劃分成兩部分，并把所有小于平均數(shù)的元素移動到平均數(shù)左邊

• 計算機(jī)體系結(jié)構(gòu)支持快速排序過程

要點

• 盡管快速排序與許多其他排序算法有相同的時間復(fù)雜度（有時會更差），但通常比其他排序算法執(zhí)行得更快，例如歸并排序。

• 必須理解：不斷通過平均數(shù)將數(shù)據(jù)集對半劃分，直到所有的數(shù)據(jù)都完成排序

時間復(fù)雜度

• O(n)最好的情況：歸并排序：O(n)

• O(n log n)平均情況：歸并排序：O(n log n)

• 最壞的情況：歸并排序：O(n2)

定義

• 一種基于比較的排序算法

• 重復(fù)上述步驟，直到不再把元素左移

• 從左往右重復(fù)對數(shù)字進(jìn)行兩兩比較，把較小的數(shù)移到左邊

要點

• 盡管這一算法很容易實現(xiàn)，卻是這三種排序方法中效率最低的

• 必須理解：每次向右移動一位，比較兩個元素，并把較小的數(shù)左移

時間復(fù)雜度

• O(n)最好的情況：歸并排序：O(n)

• O(n2)平均情況：歸并排序： O(n2)

• O(n2)最壞的情況：歸并排序： O(n2)

歸并排序 VS. 快速排序

• 在實踐中，快速排序執(zhí)行速率更快

• 歸并排序首先將集合劃分成最小的分組，在對分組進(jìn)行排序的同時，遞增地對分組進(jìn)行合并

• 快速排序不斷地通過平均數(shù)劃分集合，直到集合遞歸地有序

  
  

本文來源網(wǎng)絡(luò)，歡迎分享閱讀！

黑馬程序員基礎(chǔ)班火熱報名中

0元幫你夯實編程基礎(chǔ)，助你輕松入學(xué)黑馬程序員。