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

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

定義

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

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

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

知識要點(diǎn)

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

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

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

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

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

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

時(shí)間復(fù)雜度

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

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

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

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

定義

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

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

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

要點(diǎn)

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

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

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

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

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

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

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

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

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

時(shí)間復(fù)雜度

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

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

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

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

定義

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

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

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

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

要點(diǎn)

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

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

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

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

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

時(shí)間復(fù)雜度

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

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

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

定義

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

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

要點(diǎn)

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

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

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

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

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

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

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

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

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

時(shí)間復(fù)雜度

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

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

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

• 

  搜索基礎(chǔ)

  

定義

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

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

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

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

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

要點(diǎn)

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

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

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

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

時(shí)間復(fù)雜度

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

• E 是邊的數(shù)目

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

定義

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

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

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

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

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

要點(diǎn)

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

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

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

• 因?yàn)槎褩Ｊ恰昂筮M(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)，所以無需跟蹤結(jié)點(diǎn)的指針。與廣度優(yōu)先搜索相比，它對內(nèi)存的要求不高。

時(shí)間復(fù)雜度

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

• E 是邊的數(shù)目

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

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

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

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

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

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

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

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

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

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

• 

  高效排序基礎(chǔ)

  

定義

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

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

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

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

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

要點(diǎn)

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

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

時(shí)間復(fù)雜度

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

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

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

定義

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

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

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

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

要點(diǎn)

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

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

時(shí)間復(fù)雜度

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

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

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

定義

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

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

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

要點(diǎn)

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

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

時(shí)間復(fù)雜度

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

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

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

歸并排序 VS. 快速排序

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

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

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