數(shù)據(jù)結(jié)構(gòu)與算法是什么?
在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)（Data Structure）是計(jì)算機(jī)中存儲(chǔ)、組織數(shù)據(jù)的方式。為什么數(shù)據(jù)結(jié)構(gòu)和算法經(jīng)常放在一起討論？算法用來(lái)設(shè)計(jì)一種使用計(jì)算機(jī)來(lái)解決問(wèn)題的方法。設(shè)計(jì)高效的算法又是怎么來(lái)實(shí)現(xiàn)的？在我們學(xué)習(xí)了計(jì)算機(jī)編程后，也要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法這些基礎(chǔ)內(nèi)容。
一、數(shù)據(jù)結(jié)構(gòu)
我們經(jīng)常會(huì)聽到有人說(shuō)起：程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法，當(dāng)我們遇到一個(gè)問(wèn)題，或有一個(gè)需求時(shí)，在設(shè)計(jì)程序來(lái)解決問(wèn)題時(shí)，其中重要一步就是設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)在問(wèn)題解決中主要用來(lái)：
存放要處理的數(shù)據(jù)
實(shí)現(xiàn)算法策略
數(shù)據(jù)結(jié)構(gòu)可以用一個(gè)四元組來(lái)表示：
DataStructure = (D, L, S, O)
它包括數(shù)據(jù)元素（D）、數(shù)據(jù)元素之間的邏輯關(guān)系（L）、邏輯關(guān)系在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)（S）和所規(guī)定的操作（O）這四部分。
計(jì)算機(jī)中數(shù)據(jù)的相關(guān)術(shù)語(yǔ)：
數(shù)據(jù)（Data）：所有能夠被計(jì)算機(jī)識(shí)別的符號(hào)集合。
數(shù)據(jù)元素（Data Element）：數(shù)據(jù)集合中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。
數(shù)據(jù)項(xiàng)（Data Item）：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。
數(shù)據(jù)對(duì)象（Data Object）：具有相同性質(zhì)的數(shù)據(jù)元素的集合。
1. 邏輯結(jié)構(gòu)
邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間客觀存在的關(guān)系，和數(shù)據(jù)在計(jì)算機(jī)中怎么存儲(chǔ)無(wú)關(guān)，主要用于人們理解和交流以及指導(dǎo)算法的設(shè)計(jì)。邏輯結(jié)構(gòu)分為四類：
線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系
樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系
圖形結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系
集合結(jié)構(gòu)：數(shù)據(jù)元素屬于同一個(gè)集合
學(xué)習(xí)研究了這四種邏輯關(guān)系是如何存儲(chǔ)與操作后，以后我們要解決任何問(wèn)題，只要分析出我們要解決問(wèn)題的數(shù)據(jù)關(guān)系，都可以通過(guò)這四種邏輯關(guān)系來(lái)思考，如果關(guān)系比較復(fù)雜，也是由這四種關(guān)系組成的，只要一層一層地分析就可以了。
2. 存儲(chǔ)結(jié)構(gòu)
邏輯結(jié)構(gòu)主要用于算法設(shè)計(jì)，而存儲(chǔ)結(jié)構(gòu)用于指導(dǎo)算法編程實(shí)現(xiàn)。存儲(chǔ)結(jié)構(gòu)有基本的兩種結(jié)構(gòu)：
順序存儲(chǔ)：邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中
鏈?zhǔn)酱鎯?chǔ)：在數(shù)據(jù)元素中添加一些地址域或輔助結(jié)構(gòu)，用于存放數(shù)據(jù)元素之間的關(guān)系
順序存儲(chǔ)結(jié)構(gòu)在內(nèi)存中的地址是連續(xù)的，所以存取速度很快，但是在插入或刪除操作效率低。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在內(nèi)存中地址可以是不連續(xù)的，插入和刪除操作效率高，但查找和遍歷效率低。同樣的邏輯結(jié)構(gòu)（線性、樹形、圖形、集合）既可以采用順序存儲(chǔ)結(jié)構(gòu)也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)和關(guān)系。存儲(chǔ)結(jié)構(gòu)的選擇主要考慮算法的效率，算法的時(shí)間和空間哪個(gè)更好，具體選擇哪種和需求有關(guān)，基本存儲(chǔ)結(jié)構(gòu)既可以單獨(dú)使用，也可以組合使用。
3. 運(yùn)算操作
數(shù)據(jù)結(jié)構(gòu)中的操作主要是指數(shù)據(jù)元素的查找、插入、刪除、遍歷和排序等等。
二、算法
算法用來(lái)設(shè)計(jì)并實(shí)現(xiàn)一種用計(jì)算機(jī)來(lái)解決問(wèn)題的方法。它滿足下列性質(zhì)：
輸入：有零個(gè)或多個(gè)輸入量
輸出：產(chǎn)生至少一個(gè)輸出量
確定性：算法的指令清晰、無(wú)歧義
有限性：算法的指令執(zhí)行次數(shù)有限，執(zhí)行時(shí)間有限
我們?cè)谑褂糜?jì)算機(jī)解決生產(chǎn)問(wèn)題的過(guò)程可以分為下面五個(gè)步驟：
問(wèn)題的理解：搞清楚問(wèn)題的輸入、要求和輸出。
數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：設(shè)計(jì)能處理問(wèn)題中數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，還要設(shè)計(jì)能支持算法策略的數(shù)據(jù)結(jié)構(gòu)。
算法設(shè)計(jì)：選擇算法策略，用適當(dāng)?shù)姆绞矫枋龊椭鸩郊?xì)化算法步驟。
算法分析：發(fā)現(xiàn)有優(yōu)化的地方，返回第二步，重新設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法
程序?qū)崿F(xiàn)：用計(jì)算機(jī)編程，定義數(shù)據(jù)結(jié)構(gòu)，編寫代碼實(shí)現(xiàn)，并調(diào)試和運(yùn)行。
一個(gè)需求問(wèn)題有多種解決方案，我們經(jīng)常需要通過(guò)不斷嘗試和積累經(jīng)驗(yàn)才能找到最好的方案，如果我們熟練掌握了基本的數(shù)據(jù)結(jié)構(gòu)和算法，對(duì)于在設(shè)計(jì)高效算法中是有很大幫助的，能更高效地解決需求問(wèn)題。
碼匠
微信ID: CodeArtist
1. 點(diǎn)擊公眾號(hào)菜單，查看更多內(nèi)容
2. 長(zhǎng)按右側(cè)二維碼，關(guān)注碼匠公眾號(hào)