引言

經(jīng)常能夠聽到這樣的聲音，都知道數(shù)據(jù)結(jié)構(gòu)重要，但是開發(fā)中，幾乎用不到。其實(shí)我們每天都在用，只是不關(guān)注。或者說換成了另外的一種形式，比如STL。

程序設(shè)計(jì)

還記得這個(gè)經(jīng)典公式嗎？
程序=算法+數(shù)據(jù)結(jié)構(gòu)

• 數(shù)據(jù)結(jié)構(gòu)（Data Structure）：邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表達(dá)，支持相應(yīng)的操作
• 算法（algorithhm）：對(duì)特定問題求解過程的描述方法
• 程序（program）：算法在計(jì)算機(jī)程序設(shè)計(jì)語言中的實(shí)現(xiàn) 。

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

**數(shù)據(jù)結(jié)構(gòu)定義：**數(shù)據(jù)結(jié)構(gòu)是一種存儲(chǔ)和組織數(shù)據(jù)的方式，以便于訪問和修改。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算，即按照某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映射方式把它存放在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。

• 數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系。有集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)。
• 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和元素之間關(guān)系的表示。有順序存儲(chǔ)結(jié)構(gòu)（數(shù)組）、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）、索引存儲(chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)等。
• 數(shù)據(jù)的運(yùn)算：對(duì)數(shù)據(jù)施加的操作，通過算法描述。

二.算法的基本概念

算法定義

計(jì)算機(jī)求解一個(gè)問題所需的一系列步驟

算法的基本特性：

1. 輸入：一個(gè)算法有0個(gè)或者多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身給出了初始條件；
2. 輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；
3. 有窮性：算法必須能在執(zhí)行有限個(gè)步驟之后終止；
4. 確切性：算法的每一步驟必須有確切的定義；
5. 可行性：算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步，即每個(gè)計(jì)算步都可以在有限時(shí)間內(nèi)完成。

算法設(shè)計(jì)的要求：

1. 正確性：設(shè)計(jì)的算法能滿足具體問題的需求，并且任何合法的輸入都會(huì)得出正確的輸出；
2. 可讀性：是指算法被寫好之后，該算法理解的難易程度，一個(gè)算法可讀性的好壞十分重要。如果一個(gè)算法比較抽象且難以理解，那么這個(gè)算法就不利于交流和推廣使用，對(duì)于修改、擴(kuò)展、維護(hù)來說都十分不方便，因此，在追求高效的同時(shí)，也應(yīng)是算法盡量簡明易懂。
3. 健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也會(huì)做出相應(yīng)的判斷，而不會(huì)因?yàn)檩斎氲腻e(cuò)誤而造成癱瘓。
4. 時(shí)間效率高（時(shí)間復(fù)雜度）和需要的存儲(chǔ)空間少（空間復(fù)雜度）

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

程序大概的執(zhí)行次數(shù)（不是執(zhí)行時(shí)間）。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度

空間復(fù)雜度：

該算法所耗費(fèi)的存儲(chǔ)空間，它也是問題規(guī)模n的函數(shù)。其是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面。

數(shù)據(jù)結(jié)構(gòu)與算法思維導(dǎo)圖