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

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

定義

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

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

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

知識(shí)要點(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)存儲(chǔ)數(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)

定義

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

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

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

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

要點(diǎn)

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

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

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

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

• 哈希表對(duì)于關(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ì)列存儲(chǔ)樹的信息

• 由于需要存儲(chǔ)指針，隊(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ù)遍歷,，則對(duì)棧進(jìn)行操作

• 因?yàn)槎褩Ｊ恰昂筮M(jìn)先出”的數(shù)據(jù)結(jié)構(gòu),，所以無需跟蹤結(jié)點(diǎn)的指針。與廣度優(yōu)先搜索相比,，它對(duì)內(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ì)列來存儲(chǔ)結(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ù)對(duì)都完成排序,，則開始比較最左兩個(gè)數(shù)對(duì)中的最左元素,，形成一個(gè)含有四個(gè)數(shù)的有序集合，其中最小數(shù)在最左邊,，最大數(shù)在最右邊

• 依次比較每個(gè)數(shù)字,，將最小的數(shù)移動(dòng)到每對(duì)數(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ù)上述操作,，直到左邊部分的排序完成后,，對(duì)右邊部分執(zhí)行相同的操作

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

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

要點(diǎn)

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

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

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

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

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

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

定義

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

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

• 從左往右重復(fù)對(duì)數(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í)行速率更快

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

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