本文涉及更多的是概念，代碼部分請(qǐng)參考之前寫過的 2 篇博客

基于Javascript的排序算法
基本數(shù)據(jù)結(jié)構(gòu)和查找算法

本文主要是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法概念，可能部分地方會(huì)涉及更高級(jí)的算法和算法，具體內(nèi)容以后會(huì)單獨(dú)寫的。此外一些性質(zhì)還會(huì)不斷補(bǔ)充，也希望可以得到您的指點(diǎn)，謝謝。

數(shù)據(jù)結(jié)構(gòu)

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

數(shù)據(jù)結(jié)構(gòu)基本概念

1. 數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四種。
2. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間種的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。

在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，沒有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)

數(shù)據(jù)結(jié)構(gòu)的基本操作

插入和刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本操作。此外還有查找、分類、合并、分解、復(fù)制和修改等。

線性結(jié)構(gòu)和非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

• 線性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多只有一個(gè)后件。
• 非線性結(jié)構(gòu)： 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。

本文涉及一下內(nèi)容：

• 四種線性結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)：順序表、鏈表、索引、散列
• 兩種常見的線性邏輯結(jié)構(gòu)：隊(duì)列、棧
• 非線性邏輯結(jié)構(gòu)：循環(huán)隊(duì)列、雙向隊(duì)列、雙向循環(huán)隊(duì)列、樹、圖

存儲(chǔ)結(jié)構(gòu)

順序表

順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
順序表具備如下兩個(gè)基本特征：

1. 順序表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；
2. 順序表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

假設(shè)順序表的每個(gè)元素需占用 K 個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則順序表中第 i+1 個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 LOC(a_i+1) 和第 i 個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 LOC(a_i) 之間滿足下列關(guān)系為:

LOC(a_(i+1)) = LOC(a_i)+K

LOC(a_i) = LOC(a_1)+(i-1)*K

其中，LOC(a_1)是順序表的第一個(gè)數(shù)據(jù)元素 a_1 的存儲(chǔ)位置，通常稱做順序表的起始位置或基地址。順序存儲(chǔ)結(jié)構(gòu)也稱隨機(jī)存取結(jié)構(gòu)。

順序表常見操作(括號(hào)中為算法平均時(shí)間復(fù)雜度，沒有寫明的具體復(fù)雜度依賴不同算法和運(yùn)算規(guī)則)：

插入(O(n))、刪除(O(n))、查找、排序、分解、合并、復(fù)制(O(n))、逆轉(zhuǎn)(O(n))

鏈表

鏈表指線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，因此，為了表示每個(gè)數(shù)據(jù)元素 a_i 與其直接后繼數(shù)據(jù)元素 a_(i+1) 之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素 a_i 來說，除了存儲(chǔ)其本身的信息(數(shù)據(jù)域)之外，還需存儲(chǔ)一個(gè)變量指示其直接后繼的信息(指針域)。這兩部分信息組成數(shù)據(jù)元素 a_i 的存儲(chǔ)映象，稱為結(jié)點(diǎn)。N 個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表。該鏈表就是傳統(tǒng)的單向鏈表。

有時(shí)，我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，它指向表中第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可 以不存儲(chǔ)任何信息，也可存儲(chǔ)如線性表的長度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。在單鏈表中，取得第 I 個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找，因此，鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

以上提到的鏈表指針域只包括一個(gè)指針，指向下一個(gè)數(shù)據(jù)的地址，如果我們將鏈表最后一個(gè)結(jié)點(diǎn)指針域的指針指向鏈表的頭結(jié)點(diǎn)地址，就構(gòu)成了一個(gè)環(huán)狀的存儲(chǔ)結(jié)構(gòu)，我們稱作循環(huán)鏈表。

當(dāng)然我們可以給每個(gè)結(jié)點(diǎn)的指針域再添加一個(gè)指針，使其指向前一個(gè)數(shù)據(jù)結(jié)點(diǎn)的地址，這樣就構(gòu)成了雙向鏈表，而將頭結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)指向尾結(jié)點(diǎn)，同時(shí)將尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向頭結(jié)點(diǎn)就構(gòu)成了雙向循環(huán)鏈表。

如果鏈表的尾結(jié)點(diǎn)的指針域指向了該鏈表之前的任意一個(gè)結(jié)點(diǎn)，我們稱該鏈表為有環(huán)鏈表。環(huán)形鏈表就是其中一個(gè)特例

順序表常見操作(括號(hào)中為算法平均時(shí)間復(fù)雜度，沒有寫明的具體復(fù)雜度依賴不同算法和運(yùn)算規(guī)則)：

插入(O(n))、刪除(O(n))、查找、排序、分解、合并、復(fù)制(O(n))、逆轉(zhuǎn)(O(n))

索引

索引存儲(chǔ)除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。索引表由若干索引項(xiàng)組成。

對(duì)于索引的理解最好的例子就是《新華字典》，它建立的2套索引表(拼音、部首)。字典的正文就是從“啊”到“做”的每個(gè)字的解釋，有上千頁，就是是數(shù)據(jù)。而前面的拼音/部首就是索引表，索引表告訴你某個(gè)讀音/部首在第幾頁，這就好比是指向數(shù)據(jù)地址的指針。而索引表可以有一級(jí)的也可以是多級(jí)的，比如字典中的部首索引就是兩級(jí)的。

索引存儲(chǔ)結(jié)構(gòu)是用結(jié)點(diǎn)的索引號(hào)來確定結(jié)點(diǎn)存儲(chǔ)地址，其優(yōu)點(diǎn)是檢索速度快，缺點(diǎn)是增加了附加的索引表,會(huì)占用較多的存儲(chǔ)空間。

散列

散列存儲(chǔ)，又稱哈希(hash)存儲(chǔ)，是一種力圖將數(shù)據(jù)元素的存儲(chǔ)位置(預(yù)留連續(xù)存儲(chǔ)區(qū)域)與關(guān)鍵碼之間建立確定對(duì)應(yīng)關(guān)系的查找技術(shù)。散列法存儲(chǔ)的基本思想是由結(jié)點(diǎn)的關(guān)鍵碼值決定結(jié)點(diǎn)的存儲(chǔ)地址。散列技術(shù)除了可以用于存儲(chǔ)外，還可以用于查找。

散列以數(shù)據(jù)中每個(gè)元素的關(guān)鍵字 K 為自變量，通過散列函數(shù) H(k) 計(jì)算出函數(shù)值，以該函數(shù)值作為一塊連續(xù)存儲(chǔ)空間的的單元地址，將該元素存儲(chǔ)到函數(shù)值對(duì)應(yīng)的單元中。由于該函數(shù)值唯一，所以查找時(shí)間復(fù)雜度為 O(1)

線性邏輯結(jié)構(gòu)

線性表

線性表滿足以下特征:

1. 有且只有一個(gè)根結(jié)點(diǎn) a_1,它無前件；
2. 有且只有一個(gè)終端結(jié)點(diǎn) a_n，它無后件；
3. 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù) n 稱 為線性表的長度。當(dāng) n=0 時(shí)稱為空表。

棧

棧實(shí)際上也是一個(gè)線性表，只不過是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂(TOP)，另一端為棧底(BOTTOM)。當(dāng)表中沒有元素時(shí)稱為?？?。 棧頂元素總是后被插入(入棧)的元素，從而也是最先被移除(出棧)的元素；棧底元素總是最先被插入的元素，從而也是最后才能被移除的元素。所以棧是個(gè) 后進(jìn)先出(LIFO) 的數(shù)據(jù)結(jié)構(gòu)

棧的基本運(yùn)算有三種：入棧、出棧與讀棧頂，時(shí)間復(fù)雜度都是O(1)

隊(duì)列

隊(duì)列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做隊(duì)頭，用對(duì)頭指針 front 指向?qū)︻^元素的下一個(gè)元素，允許插入的一端叫做隊(duì)尾，用隊(duì)尾指針 rear 指向隊(duì)列中的隊(duì)尾元素，因此，從排頭指針 front 指向的下一個(gè)位置直到隊(duì)尾指針 rear 指向的位置之間所有的元素均為隊(duì)列中的元素。

隊(duì)列的修改是 先進(jìn)先出(FIFO) 。往隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算。從對(duì)頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。

隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算，復(fù)雜度都是O(1)

循環(huán)隊(duì)列

在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè) 位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)滿還是隊(duì)列空，通常需要增加一個(gè)標(biāo)志 S。

循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算，復(fù)雜度都是O(1)

• 入隊(duì)運(yùn)算
  指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素，首先 rear=rear+1, 當(dāng) rear=m+1 時(shí)，置 rear=1,然后將新元素插入到隊(duì)尾指針 指向的位置。當(dāng) S=1, rear=front，說明隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，稱為“上溢”。
• 退隊(duì)運(yùn)算
  指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。首先 front=front+1, 并當(dāng) front=m+1 時(shí)，置 front=1, 然后 將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空 S=0，不能進(jìn)行退隊(duì)運(yùn)算，這種情況成為“下溢”。

非線性邏輯結(jié)構(gòu)

樹

樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)具有以下特點(diǎn)：

1. 每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。
2. 每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)
3. 一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為結(jié)點(diǎn)的度
4. 樹的最大層次稱為樹的深度。

二叉樹

二叉樹是一種樹型結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，滿足以下特性：

1. 它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(即二叉樹中不存在度大于 2 的結(jié)點(diǎn))；
2. 二叉樹的子樹有左右之分，其次序不能任意顛倒。

二叉樹的基本性質(zhì)

• 在二叉樹的第 i 層上至多有 2i-1 個(gè)結(jié)點(diǎn)
• 深度為 k 的二叉樹至多有 2k-1 個(gè)結(jié)點(diǎn)(k <= 1)
• 在任意一個(gè)二叉樹中，度為 0 的結(jié)點(diǎn)總是比度為 2 的結(jié)點(diǎn)多一個(gè)
• 具有 N 個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 floor(log N) + 1
• 霍夫曼樹的帶權(quán)路徑長度 len = 2n+1; n 為所以葉子權(quán)重和。

二叉樹的遍歷

就是遵從某種次序，訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪問一次。分為以下幾種：

1. 前序遍歷(DLR): 首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。
2. 中序遍歷(LDR): 首先遍歷左子樹，然后根結(jié)點(diǎn)，最后右子樹
3. 后序遍歷(LRD): 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。

此外圖的遍歷也可以用在樹上，包括：

1. 廣度優(yōu)先遍歷(層序遍歷): 從根結(jié)點(diǎn)開開始逐層向下，從左到右遍歷。
2. 深度優(yōu)先遍歷: 從根結(jié)點(diǎn)出發(fā)沿左子樹遍歷到葉子結(jié)點(diǎn)再逐層向上向遍歷右子樹。

除此之外還有很多有特點(diǎn)的特殊二叉樹：

• 滿二叉樹：除最后一層以外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。

1. 在滿二叉樹的第 K 層上有 2^(K-1) 個(gè)結(jié)點(diǎn)，且深度為 M 的滿二叉樹有 2M-1 個(gè)結(jié)點(diǎn)

• 完全二叉樹：除最后一層以外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

1. 具有 N 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 floor(log_2 N) + 1
2. 完全二叉樹總結(jié)點(diǎn)數(shù)為 N，則葉子結(jié)點(diǎn)數(shù)為 ceil(N/2)

堆

最常見的完全二叉樹就是 堆 了。堆滿足以下條件

• 堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
• 堆總是一棵完全二叉樹

將根結(jié)點(diǎn)最大的堆叫做 最大堆 或 大根堆 ，根結(jié)點(diǎn)最小的堆叫做 最小堆 或 小根堆 。

堆具有以下基本操作：

• 插入: 向堆中插入一個(gè)新元素
• 獲取: 獲取當(dāng)前堆頂元素的值
• 刪除: 刪除堆頂元素
• 包含: 判斷堆中是否存在某個(gè)元素

哈希表

常用的哈希函數(shù)

1. 直接尋址法: H(k) 是一個(gè)線性函數(shù)，如果該位置已經(jīng)有值就向下尋找到第一個(gè)空的地方作為散列地址
2. 平方取中法: 取 k 平方以后值的中間幾位作為散列地址
3. 數(shù)字分析法: 對(duì)于比較規(guī)律的 k 值，找出其差異較大的部分作為散列地址
4. 折疊法: 將 k 分成很多部分，然后做模二和作為散列地址
5. 留余數(shù)法: H(k)=k % p, p <= m，其中 p 為素?cái)?shù)，m 為表的長度
6. 隨機(jī)數(shù)法: 取鍵字的隨機(jī)值作為散列地址，關(guān)鍵字長度時(shí)使用

實(shí)現(xiàn)映射的函數(shù)是哈希函數(shù)，簡(jiǎn)單的 hash 可能會(huì)發(fā)生碰撞(不同輸入得到相同輸出)，為了防止碰撞，考慮以下方法：

• 鏈地址法(拉鏈法): 當(dāng)發(fā)生碰撞時(shí)，將發(fā)生碰撞的數(shù)據(jù)元素連接到同一個(gè)單鏈表中，而新元素插入到鏈表的前端
• 線性探針法: 線性探針法地址增量 d \∈ D_1 = {1,2,3, ... , m-1}, i 為探測(cè)次數(shù)，m 為表的長度，該方法遇到?jīng)_突地址會(huì)依次探測(cè)下一個(gè)地址(d = d_i + 1)直到有空的地址，若找不到空地址，則溢出。

平均查找長度

• 線性探針法平均長度推算(其中 m 為表中數(shù)據(jù)長度，n 為表長度)：

ASL_s = d_1 + d_2 + ... + d_m)/m，查找成功

ASL_u = (d_1 + d_2 + ... + d_n)/n，查找不成功

注：線性探針法查找成功時(shí) d_i 為每次放入元素時(shí)的地址增量，不成功時(shí) d_i 為在表長度內(nèi)依次查找每個(gè)元素到下一個(gè)空地址的地址增量(索引在表長度內(nèi)循環(huán))

• 鏈地址法平均長度推算(其中 k 為最長鏈長度，其中 m 為表中數(shù)據(jù)長度，n 為表長度)：

ASL_s = (∑(1~k)(當(dāng)前級(jí)指針數(shù)量 * 當(dāng)前級(jí)數(shù)))/m，查找成功

ASL_u = (∑(1~n)(當(dāng)前個(gè)位置鏈長度)) / n，查找不成功

哈希表相關(guān)特性

• 線性探針法容易“聚集”，影響查找效率，而鏈地址法不會(huì)
• 鏈地址法適應(yīng)表長不確定情況
• 裝填因子(α) = 哈希表中的記錄數(shù) / 哈希表的長度

圖

圖有兩種定義：

• 二元組的定義：圖 G 是一個(gè)有序二元組 (V,E)，其中 V 稱為頂集(Vertices Set)，E 稱為邊集(Edges set)，E 與 V 不相交。它們亦可寫成 V(G) 和 E(G) 。E 的元素都是二元組，用 (x,y) 表示，其中 x,y &is∈; V
• 三元組的定義: 圖 G 是指一個(gè)三元組(V,E,I)，其中 V 稱為頂集，E 稱為邊集，E 與 V 不相交；I 稱為關(guān)聯(lián)函數(shù)，I 將 E 中的每一個(gè)元素映射到V * V。如果 e 被映射到 (u,v)，那么稱邊 e 連接頂點(diǎn) u,v，而 u,v 則稱作 e 的端點(diǎn)，u,v 此時(shí)關(guān)于 e 相鄰。同時(shí)，若兩條邊 i,j 有一個(gè)公共頂點(diǎn) u，則稱 i,j 關(guān)于 u 相鄰。

圖的分類

圖有不同的分類規(guī)則，具體如下：

分類1

• 有向圖: 如果圖中頂點(diǎn)之間關(guān)系不僅僅是連通與不連通，而且區(qū)分兩邊的頂點(diǎn)的出入(存在出邊和入邊)，則為有向圖。
• 無向圖: 如果圖中頂點(diǎn)之間關(guān)系僅僅是連通與不連通，而不區(qū)分兩邊頂點(diǎn)的出入(不存在出邊和入邊)，則為無向圖。
  單圖

分類2

• 有環(huán)圖: 單向遍歷回可以到已遍歷的點(diǎn)，比如有環(huán)鏈表
• 無環(huán)圖: 單向遍歷不能回到已遍歷的點(diǎn)，比如樹

分類3

• 帶權(quán)圖: 圖的具有邊帶有關(guān)于該邊信息的權(quán)值，比如地圖中兩點(diǎn)間距離
• 無權(quán)圖: 圖的每個(gè)邊都不具有有關(guān)于該邊信息的權(quán)值，其僅表示是否連通

其他

• 單圖: 一個(gè)圖如果任意兩頂點(diǎn)之間只有一條邊且邊集中不含環(huán)，則稱為單圖

圖的表示采用鄰接矩陣和類似樹的形式(頂點(diǎn)指針域是個(gè)指針數(shù)組)的形式，其具有以下特點(diǎn)：

• 無向圖的鄰接矩陣是對(duì)稱矩陣
• 帶權(quán)圖的矩陣中元素為全職，無權(quán)圖中用0/1分別表示不連通/連通
• 主對(duì)角線有不為零元素，該圖一定有環(huán)

圖的遍歷

• 廣度優(yōu)先遍歷: 廣度優(yōu)先遍歷是連通圖的一種遍歷策略。因?yàn)樗乃枷胧菑囊粋€(gè)頂點(diǎn) V_0 開始，輻射狀地優(yōu)先遍歷其周圍較廣的區(qū)域。
• 深度優(yōu)先遍歷:

圖的相關(guān)性質(zhì)：

• N 個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為 N-1
• N 個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有 N
• 廣度優(yōu)先遍歷用來找無權(quán)圖最短路徑（有權(quán)圖其實(shí)也行，多點(diǎn)東西唄）

簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)的增刪改查

算法

算法基本概念

1. 算法的基本特征：可行性，確定性，有窮性
2. 算法的基本要素：算法中對(duì)數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。
3. 算法設(shè)計(jì)的基本方法：窮舉法、動(dòng)態(tài)規(guī)劃、貪心法、回溯法、遞推法、遞歸法、分治法、散列法，分支限界法。
4. 算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求
5. 算法的基本結(jié)構(gòu)：順序、循環(huán)、選擇

算法復(fù)雜度

1. 算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量(不代表算法實(shí)際需要時(shí)間)
2. 算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的額外內(nèi)存空間(代表算法實(shí)際需要的空間)

復(fù)雜度表示方法: 使用大寫 O 表示：O(n)表示時(shí)間復(fù)雜度時(shí)指 n 個(gè)數(shù)據(jù)處理完成使用 n 個(gè)單位的時(shí)間；表示空間復(fù)雜度時(shí)指 n 個(gè)數(shù)據(jù)處理完成使用了 n 個(gè)單位的輔助空間。

字符串算法

字符串算法除了增刪改查以外，還有很多匹配算法，比如最耳熟能詳?shù)?KMP 算法(不屬于基礎(chǔ)部分)，這里整理一些相關(guān)算法的性質(zhì)：

• 一個(gè)長為 n 的字符串有 n(n+1)/2+1 個(gè)子串
• n的字符串，其中的字符各不相同，則S中的互異的非平凡子串有 \frac{1}{2}n^2+\frac{1}{2}n-1 個(gè)

排序算法

排序算法實(shí)際上可以分為內(nèi)排序和外排序：

• 內(nèi)排序：在排序過程中，所有元素調(diào)到內(nèi)存中進(jìn)行的排序，稱為內(nèi)排序。內(nèi)排序是排序的基礎(chǔ)。內(nèi)排序效率用比較次數(shù)來衡量。按所用策略不同，內(nèi)排序又可分為插入排序、選擇排序、堆排序、歸并排序、冒泡排序、快速排序、希爾排序及基數(shù)排序等等。
• 外排序：在數(shù)據(jù)量大的情況下，只能分塊排序，但塊與塊間不能保證有序。外排序用讀/寫外存的次數(shù)來衡量其效率。

排序算法時(shí)間復(fù)雜度

排序算法分為以下幾類：

1. 插入類排序：插入排序、希爾排序
2. 交換類排序：冒泡排序、快速排序
3. 選擇類排序：選擇排序、堆排序
4. 歸并排序
5. 基數(shù)排序

注:

1. 基數(shù)排序的復(fù)雜度中，r 代表關(guān)鍵字基數(shù)，d 代表長度，n 代表關(guān)鍵字個(gè)數(shù)
2. 排序算法的穩(wěn)定性指在原序列中，r_i=r_j，且 r_i 在 r_j 之前，而在排序后的序列中，r_i 仍在 r_j 之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

查找算法

查找算法時(shí)間復(fù)雜度

平均查找長度(ASL) = 查找表中第 i 個(gè)元素概率(P_i) * 找到第 i 個(gè)元素時(shí)已經(jīng)比較的次數(shù)(C_i)