1.1 什么是數(shù)據(jù)結(jié)構(gòu)（Data Structure）

數(shù)據(jù)結(jié)構(gòu)是對(duì)現(xiàn)實(shí)世界中數(shù)據(jù)及其關(guān)系的某種映射，既可以表示數(shù)據(jù)本身的物理結(jié)構(gòu)，也可以表示計(jì)算機(jī)中的邏輯結(jié)構(gòu)。

1.1.1 數(shù)據(jù)的邏輯結(jié)構(gòu)（Logical Structure）

數(shù)據(jù)的邏輯結(jié)構(gòu)由數(shù)據(jù)結(jié)點(diǎn)（Node）和連接兩個(gè)結(jié)點(diǎn)的邊（Edge）組成

1. 結(jié)點(diǎn)的數(shù)據(jù)類型：

• 整型（integer）：1-4個(gè)字節(jié)
• 實(shí)數(shù)（real）：4-8個(gè)字節(jié)
• 布爾（boolean）
• 字符（char）：ASCII字符集中的字符，不包含漢子符號(hào)
• 指針（pointer）：指向某一內(nèi)存單元的地址

2. 結(jié)點(diǎn)的分類

• 線性結(jié)構(gòu)（Linear Structure）：每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)
• 樹形結(jié)構(gòu)（Tree Structure）： 每個(gè)結(jié)點(diǎn)均有且只有唯一的前驅(qū)結(jié)點(diǎn)，但可以有多個(gè)后繼結(jié)點(diǎn)
• 圖結(jié)構(gòu)（Graph Structure）：每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)不做任何約束

線性結(jié)構(gòu)和樹形結(jié)構(gòu)的區(qū)別：每個(gè)結(jié)點(diǎn)是否具有一個(gè)直接后繼；樹形結(jié)構(gòu)和圖結(jié)構(gòu)的區(qū)別：每個(gè)結(jié)點(diǎn)是否僅僅從屬于一個(gè)直接前驅(qū)

1.1.2 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)就是建立一種邏輯結(jié)構(gòu)到物理結(jié)構(gòu)的映射。4種常用存儲(chǔ)映射的方法：

• 順序：緊湊存儲(chǔ)結(jié)構(gòu)
• 鏈接
• 索引
• 散列：散列函數(shù)（Hash Function）關(guān)鍵：如何選擇和設(shè)計(jì)恰當(dāng)?shù)纳⒘泻瘮?shù)、構(gòu)造散列表、研究構(gòu)造散列表的碰撞解決方案

1.2 算法與算法設(shè)計(jì)

1.2.1 算法的概念

算法（Algorithm）是為解決某一特定問(wèn)題而采取的具體而有限的操作步驟。程序是算法的一種實(shí)現(xiàn)，計(jì)算機(jī)按照程序逐步執(zhí)行算法，實(shí)現(xiàn)對(duì)問(wèn)題的求解。算法性質(zhì)：

• 通用性
• 有效性
• 確定性
• 有窮性

1.2.2 算法設(shè)計(jì)

• 窮舉法（也稱為枚舉法）（Enumeration）：需要有明確的窮舉范圍和窮舉規(guī)則，浪費(fèi)時(shí)間，效率低。
• 回溯法（Backtrack）（也稱為試探法）：放棄當(dāng)前候選解，尋找下一個(gè)候選解的過(guò)程叫做回溯。擴(kuò)大當(dāng)前候選解的范圍，以繼續(xù)試探的過(guò)程稱為向前試探。
• 分治法（Divide and Conquer）和遞歸法（Recursion）：大問(wèn)題分割成小問(wèn)題，以便各個(gè)擊破，分而治之，然后把各個(gè)子問(wèn)題的解合并起來(lái)，得出整個(gè)問(wèn)題的解。分治法是一種自頂向下的設(shè)計(jì)方法。反復(fù)利用分治手段，使問(wèn)題規(guī)模不斷縮小，最終縮小到容易直接求解的規(guī)模，這自然會(huì)導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治法和遞歸法如同一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)中，并由此產(chǎn)生很多高校算法。
• 貪心法（Greedy）和動(dòng)態(tài)規(guī)劃法（Dynamic Programming）：貪心法所做出的選擇只是在某種意義上的局部最優(yōu)解，寄希望于由局部最優(yōu)解構(gòu)建全局最優(yōu)解。DP也是求解某種最優(yōu)性質(zhì)的問(wèn)題。

1.3 算法分析

1.3.1 算法的漸進(jìn)分析

o（1）、o（n）、o（nlogn）、o（n^2）、o（a ^ n）（指數(shù)增長(zhǎng)）：在n很大的時(shí)候其大小差別非常大。
具有指數(shù)增長(zhǎng)率的算法簡(jiǎn)稱指數(shù)爆炸型算法，在應(yīng)用時(shí)需要謹(jǐn)慎使用。
循環(huán)中嵌套循環(huán)會(huì)增加算法的復(fù)雜度，但也并非總是如此。

for (i = 4; i < n; i++) 
for (j = i - 3; sum = a[i - 4]; j <= i; j++)
    sum += a[i];

此時(shí)，外層循環(huán)n-4次，對(duì)每個(gè)i而言，內(nèi)層循環(huán)只執(zhí)行4次，每次的操作次數(shù)與i的大小無(wú)關(guān)，盡管存在循環(huán)嵌套，但算法的整體時(shí)間復(fù)雜度依然呈線性增長(zhǎng)。

1.3.2 最壞、最好和平均情況

最好情況：幫助了解某個(gè)算法在何種情況下使用好。
最壞情況：幫助了解某個(gè)算法至少能做多快，這點(diǎn)在實(shí)時(shí)系統(tǒng)中尤其重要。因?yàn)樵谝恍┲匾膱?chǎng)景下不能在規(guī)定時(shí)間內(nèi)解決問(wèn)題的算法的是不可接受的。

1.3.3 時(shí)間和空間資源開銷

對(duì)于靜態(tài)數(shù)據(jù)結(jié)構(gòu)（一旦輸入數(shù)據(jù)和問(wèn)題規(guī)模確定下來(lái)，它的數(shù)據(jù)結(jié)構(gòu)大小也就確定下來(lái)）：一般將僅限于討論時(shí)間開銷。
在算法運(yùn)行過(guò)程中，數(shù)據(jù)結(jié)構(gòu)所占用的空間有時(shí)會(huì)有數(shù)量級(jí)的增大或縮小，對(duì)于這種情況，空間開銷的分析和估計(jì)是十分必要的。

時(shí)間資源的折中原理：時(shí)空折中。指為了改善一個(gè)算法的時(shí)間開銷，往往可以通過(guò)增大空間開銷為代價(jià)。如：用散列函數(shù)，將問(wèn)題時(shí)間復(fù)雜度由線性增長(zhǎng)改善為常數(shù)時(shí)間，而空間開銷方面則增添了一個(gè)線性增長(zhǎng)的存儲(chǔ)空間。在設(shè)計(jì)算法時(shí)，經(jīng)常采用這種空間換時(shí)間的辦法。當(dāng)然也有犧牲計(jì)算機(jī)運(yùn)行時(shí)間，通過(guò)增大時(shí)間開銷來(lái)?yè)Q取存儲(chǔ)空間的節(jié)省的時(shí)間換空間的算法，如樹的順序存儲(chǔ)。