張羿九

摘要：數(shù)據(jù)結(jié)構(gòu)對(duì)于計(jì)算機(jī)、應(yīng)用數(shù)學(xué)及各類工程領(lǐng)域具有非常重要的作用。然而初學(xué)者在剛接觸數(shù)據(jù)結(jié)構(gòu)時(shí)往往會(huì)忽視其重要性，認(rèn)為還不如學(xué)個(gè)C或者Java來的直接一點(diǎn)。本文針對(duì)學(xué)習(xí)過程中學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)的不理解和不重視，本文首先簡(jiǎn)單形象的介紹了數(shù)據(jù)結(jié)構(gòu)的定義及分類，接著具體對(duì)三種常用的已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了介紹及適用范圍的分析，最后闡述了數(shù)據(jù)結(jié)構(gòu)的重要意義和對(duì)未來的展望。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；算法；適用

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）10-0218-02

1 數(shù)據(jù)結(jié)構(gòu)的定義

1.1 數(shù)據(jù)元素

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，可以由多個(gè)用于表示其屬性的數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是處理數(shù)據(jù)時(shí)的最小單位。在化學(xué)中，原子是由質(zhì)子和中子構(gòu)成的，然而盡管質(zhì)子和中子在尺度上更小，但原子才是研究問題時(shí)的的最小單位，因?yàn)樵邮潜３治镔|(zhì)化學(xué)性質(zhì)的最小的單位，就算分子也是由原子構(gòu)成的。同樣的道理，數(shù)據(jù)元素就好比原子，數(shù)據(jù)項(xiàng)就好比質(zhì)子和中子，數(shù)據(jù)項(xiàng)必須由多個(gè)組合在一起才是一個(gè)完整的、有意義的數(shù)據(jù)元素，所以我們?cè)谔幚頂?shù)據(jù)時(shí)，通常不會(huì)從數(shù)據(jù)項(xiàng)處理起，而是對(duì)數(shù)據(jù)元素這一整體進(jìn)行分析。

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

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

當(dāng)多個(gè)數(shù)據(jù)元素相互之間存在某種特定聯(lián)系，把這些數(shù)據(jù)元素抽象成一個(gè)集合，便形成了一種邏輯數(shù)據(jù)結(jié)構(gòu)。形象的來說，數(shù)據(jù)元素就像是一個(gè)個(gè)結(jié)點(diǎn)，一塊塊磚頭，一條條鋼筋。當(dāng)多個(gè)數(shù)據(jù)元素以特定的關(guān)系組合后，就形成了一種特殊的建筑，這種建筑就是邏輯數(shù)據(jù)結(jié)構(gòu)。當(dāng)我們發(fā)現(xiàn)某種數(shù)據(jù)結(jié)構(gòu)在解決某一類問題時(shí)具有很高的效率時(shí)，我們就把這種邏輯數(shù)據(jù)結(jié)構(gòu)抽象出來，再命名，單獨(dú)開辟封裝出一種抽象數(shù)據(jù)類型。

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

那么，是否數(shù)據(jù)元素真的像邏輯數(shù)據(jù)結(jié)構(gòu)那樣在電腦里有著紛繁復(fù)雜的存儲(chǔ)方式呢？其實(shí)電腦才不會(huì)那么聰明，數(shù)據(jù)元素在電腦里存儲(chǔ)的方式叫做物理數(shù)據(jù)結(jié)構(gòu)也叫存儲(chǔ)結(jié)構(gòu)，再多的數(shù)據(jù)元素對(duì)于電腦只會(huì)有兩種結(jié)構(gòu)，一種順序存儲(chǔ)結(jié)構(gòu)（存儲(chǔ)數(shù)據(jù)元素的地址是連續(xù)的），一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（存儲(chǔ)數(shù)據(jù)元素的地址是任意的，需要指針串起所有數(shù)據(jù)元素）。物理數(shù)據(jù)結(jié)構(gòu)面向的是計(jì)算機(jī)。而邏輯數(shù)據(jù)結(jié)構(gòu)是一種便于人們理解，處理問題的結(jié)構(gòu)，實(shí)際并不是那樣存儲(chǔ)在電腦里，其面向的更多在于程序員和問題本身。但我們?cè)谔幚韱栴}時(shí)，由于有編譯器的存在，我們并不需要過于糾結(jié)于計(jì)算機(jī)該怎樣存儲(chǔ)，而是去分析問題，解決問題。所以后文所說的數(shù)據(jù)結(jié)構(gòu)，不特別聲明，都指的是邏輯數(shù)據(jù)結(jié)構(gòu)。

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

數(shù)據(jù)結(jié)構(gòu)主要分為四大類：（1）集合結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素之間沒有聯(lián)系，只是同屬于一個(gè)集合，和數(shù)學(xué)上的集合定義很相似；（2）線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一一對(duì)應(yīng)關(guān)系，就像一條線一樣串被在一起。如棧、隊(duì)列和線性表都屬于線性結(jié)構(gòu)；（3）樹形結(jié)構(gòu)：數(shù)據(jù)元素間存在一對(duì)多的關(guān)系，猶如樹根，不斷生長(zhǎng)，分叉，再生長(zhǎng)，再分叉；（4）圖形結(jié)構(gòu)：數(shù)據(jù)元素間存在多對(duì)一，一對(duì)多的關(guān)系，猶如地圖上的每個(gè)地點(diǎn)，相互之間有密密麻麻的交通干道連接，從A點(diǎn)出發(fā)可以到很多地方，想回到A也有很多條路。

2 主要數(shù)據(jù)結(jié)構(gòu)的適用范圍

2.1 鏈表

鏈表也是一種更常用的數(shù)據(jù)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素在存儲(chǔ)時(shí)候都會(huì)有一個(gè)地址，就是說，電腦把這個(gè)數(shù)據(jù)元素放在了什么地方。而鏈表的數(shù)據(jù)元素不像數(shù)組里的那樣，只需要把自身的信息存儲(chǔ)好就行了，他還需要存儲(chǔ)一個(gè)指向下一個(gè)數(shù)據(jù)元素所在地址的箭頭（指針）。這就好比小時(shí)候老師給小朋友排隊(duì)，害怕小朋友走丟，就讓小朋友都記得自己后面是誰(shuí)，這樣整個(gè)隊(duì)伍就仿佛被串起來了（當(dāng)然，這和鏈表還有一定的區(qū)別）。這樣的話，我們只要找到了鏈表的第一個(gè)數(shù)據(jù)元素的地址，我們就可以找到整個(gè)鏈表。鏈表非常適合進(jìn)行插入和刪除操作，我們只需要更改前一個(gè)數(shù)據(jù)的指針和被插入數(shù)據(jù)的指針，非常的簡(jiǎn)便快捷。而如果相同操作讓數(shù)組去做，數(shù)組首先判斷數(shù)組是否溢出，再把插入位置及其之后所有元素全部先后推一個(gè)地址，再插入，非常的繁瑣，兩者時(shí)間復(fù)雜度相差一個(gè)次數(shù)級(jí)，如果進(jìn)行多次插入，鏈表會(huì)非常的方便和快捷，而且鏈表占據(jù)的空間也不像數(shù)組那樣需要提前申請(qǐng)并且有大小限制，而鏈表的占的空間就非常靈活，大小變換起來較為方便。

2.2 棧

棧是一種常用的數(shù)據(jù)結(jié)構(gòu)，他的特點(diǎn)是“先入后出”，只允許在隊(duì)尾進(jìn)行操作。這就好比你挖了個(gè)洞，你往里面不斷扔?xùn)|西，你每次扔的只能在最上面，你若想取出最底下，也就是你最先放進(jìn)去的那個(gè)東西，那么你必須把他上面所有的東西先取出來。那個(gè)洞就是我們的棧，而每個(gè)數(shù)據(jù)元素就相當(dāng)于我們的東西。 除了這一基本特點(diǎn)，還有棧鏈、兩棧共享空間等更高級(jí)、更特殊的用法。這一數(shù)據(jù)結(jié)構(gòu)適用于當(dāng)我們需要記錄我們之前每一步做了什么之類操作的時(shí)候，比如我們word的撤銷，網(wǎng)頁(yè)的后退就是類似的原理。棧在進(jìn)行在進(jìn)行壓棧（插入）操作時(shí)，也是非常快捷，如圖1。不需要像數(shù)組那樣繁瑣的操作，與鏈表相比，無需存儲(chǔ)指針使得空間也得到了一定的節(jié)約。再加上其具有將之前每步壓棧的數(shù)據(jù)都記憶下來的能力，棧在非常廣泛的應(yīng)用。

2.3 串

串是一種極其重要的數(shù)據(jù)結(jié)構(gòu)，也叫字符串，顧名思義是將幾個(gè)字符串在一起形成的數(shù)據(jù)結(jié)構(gòu)（其實(shí)可以有零個(gè)字符）。串中的每個(gè)字符都有前驅(qū)和后繼的關(guān)系，就比如你想說“god”這個(gè)字符串，你總不會(huì)打成“dog”吧，那意思就差太遠(yuǎn)了。一個(gè)串中任意一段連續(xù)的字符可以組成一個(gè)新串，叫做這個(gè)串的子串，這個(gè)串也叫做該子串的主串。串看上去和線性表很像，可其與線性表無論是功能還是操作都有很大差別。線性表關(guān)注的單個(gè)元素的插入刪除。而字符串更像是面對(duì)一個(gè)整體，處理時(shí)一般都不會(huì)對(duì)單個(gè)字符進(jìn)行操作，一般都是進(jìn)行子串的插入刪除。比較常用的是串與串之間比大小，就像查英文字典一樣，每個(gè)字符代表著一個(gè)數(shù)字，a最小，排在最前面，這一位相等便比較下一位。而串的優(yōu)越性體現(xiàn)于子串和主串的匹配，比如我們?cè)谒阉饕胬锎蛞粌蓚€(gè)字就會(huì)彈出一系列相關(guān)的結(jié)果，就是軟件用你打的字符去進(jìn)行了比配。由于串的整體性、有序性，使其非常方便與進(jìn)行比較，而線性表雜亂無章，就沒有這么便捷了。endprint

3 數(shù)據(jù)結(jié)構(gòu)的意義

3.1 數(shù)據(jù)結(jié)構(gòu)的重要性

數(shù)據(jù)是計(jì)算機(jī)科學(xué)研究的核心內(nèi)容，計(jì)算機(jī)硬件五大部分中四個(gè)部分都和數(shù)據(jù)有著直接的關(guān)系，運(yùn)算和存儲(chǔ)自然不用說，輸入輸出最終到了計(jì)算機(jī)面前也成了數(shù)據(jù)，從始至終都是在對(duì)數(shù)據(jù)進(jìn)行加工處理。計(jì)算機(jī)從1946年被發(fā)明至今已經(jīng)有了71年的歷史，當(dāng)時(shí)的人們需要處理的數(shù)據(jù)只是簡(jiǎn)單的整型、實(shí)型數(shù)據(jù)，所以關(guān)注點(diǎn)不用放在數(shù)據(jù)元素之間的結(jié)構(gòu)上。時(shí)至今日，隨著計(jì)算機(jī)覆蓋的領(lǐng)域不斷拓寬，具備的功能不斷強(qiáng)大，數(shù)值間加減乘除等的運(yùn)算只占用了機(jī)器很少的時(shí)間。錯(cuò)綜復(fù)雜的難題糾結(jié)在一起，簡(jiǎn)單的數(shù)學(xué)分析、數(shù)學(xué)方程已經(jīng)不能快速高效的解決問題，必須針對(duì)問題設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)。而且數(shù)據(jù)結(jié)構(gòu)也不僅僅是學(xué)習(xí)二叉樹、棧和隊(duì)列等經(jīng)典結(jié)構(gòu)，更重要的是培養(yǎng)一種思維模式，一種將不同數(shù)據(jù)聯(lián)系到一起，整體考慮的思想，在解決問題時(shí)會(huì)用計(jì)算機(jī)的角度看問題。并且用數(shù)據(jù)結(jié)構(gòu)寫出來的程序十分規(guī)整，可讀性非常高，不僅方便自己調(diào)試和修改，還便于他人閱讀、理解與交流。

3.2 數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系

我們首先必須明確的是數(shù)據(jù)的邏輯結(jié)構(gòu)與算法的設(shè)計(jì)相關(guān)，而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與算法的實(shí)現(xiàn)相關(guān)。[1]也就是邏輯數(shù)據(jù)結(jié)構(gòu)更加面向于問題本身，而存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)更加注重于計(jì)算機(jī)怎樣執(zhí)行。算法常常是依賴于某種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的，數(shù)據(jù)結(jié)構(gòu)是算法實(shí)現(xiàn)的基礎(chǔ)。往往是在一個(gè)新算法出現(xiàn)時(shí)，就伴隨著一個(gè)適合于這種算法的數(shù)據(jù)結(jié)構(gòu)。當(dāng)我們應(yīng)用計(jì)算機(jī)解決一個(gè)實(shí)際問題時(shí)，首先要做的是在類比自己掌握的數(shù)據(jù)結(jié)構(gòu)后對(duì)實(shí)際問題進(jìn)行抽象、建模，得到他的數(shù)學(xué)或者抽象模型，通過模型簡(jiǎn)化問題，凸顯出問題的核心與關(guān)鍵。之后通過模型得出解決問題的算法，而問題抽象的好壞直接影響由此產(chǎn)生的算法質(zhì)量。也就是說，邏輯數(shù)據(jù)結(jié)構(gòu)好壞決定問題抽象好壞，問題抽象好壞決定算法好壞，進(jìn)而決定程序好壞。算法的每一個(gè)輸入輸出和運(yùn)算步驟都需要用數(shù)據(jù)結(jié)構(gòu)高效的組織數(shù)據(jù)，每種數(shù)據(jù)結(jié)構(gòu)的內(nèi)部結(jié)構(gòu)可能很相似，但算法決定了其外部性能的差異，構(gòu)成了各種各樣的數(shù)據(jù)結(jié)構(gòu)?？傊?，二者關(guān)系密不可分，同等重要。

3.3 初學(xué)者為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是大學(xué)里計(jì)算機(jī)專業(yè)的一門必修課，也是一名軟件工程師必備的知識(shí)，可也許很多初學(xué)者在剛開始學(xué)的時(shí)候會(huì)覺得，數(shù)據(jù)結(jié)構(gòu)這么枯燥，就用一維數(shù)組一樣可以做到這里面所有的數(shù)據(jù)結(jié)構(gòu)的能做到的事情，那還費(fèi)這么大勁學(xué)它干啥？是的，我們的確可以用數(shù)組做到先入后出，可以做到插入刪除元素，可以做到先入先出……可是，數(shù)據(jù)結(jié)構(gòu)的引入一方面提供了抽象問題時(shí)的靈感和思路，另一方面，它使解決問題所需要的思維過程簡(jiǎn)化，我們不需要糾結(jié)于如何用數(shù)組完成這個(gè)功能，而是更加把思維放在問題本身，看到問題的核心與本質(zhì)，而且更重要的，退一萬步說，就算你腦袋夠用，你就是只用數(shù)組寫出了一個(gè)程序，殊不知這里面有很多算法可以用各種數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)化，這種簡(jiǎn)化不僅僅是輸入量的簡(jiǎn)化，更是空間與時(shí)間的簡(jiǎn)化，可能在你這一個(gè)小程序里還沒有體現(xiàn)，可一旦牽扯到龐大的處理時(shí)，那可是幾個(gè)次數(shù)增長(zhǎng)的時(shí)間，這種巨大的延遲，誰(shuí)會(huì)選擇和使用你的算法呢？如果一直靠別人的示例代碼過活，那別人的代碼對(duì)你來說就是黑盒子，程序運(yùn)行速度慢時(shí)，你就完全不知道如何改造。數(shù)據(jù)結(jié)構(gòu)不是學(xué)了就能立竿見影地看出效果，但它影響著你以后所做的一切。所以，數(shù)據(jù)結(jié)構(gòu)是我們初學(xué)者必須認(rèn)真學(xué)習(xí)的一門課程。

4 結(jié)語(yǔ)

數(shù)據(jù)結(jié)構(gòu)是高級(jí)程序設(shè)計(jì)語(yǔ)言、操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)、人工智能、圖視學(xué)等課程的基礎(chǔ)。在這個(gè)大數(shù)據(jù)時(shí)代，各處都在進(jìn)行著龐大的運(yùn)算，數(shù)據(jù)結(jié)構(gòu)在其中扮演著無比重要的作用。同時(shí)，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。[2]數(shù)據(jù)結(jié)構(gòu)是如此的重要，以至于我們必須在認(rèn)真學(xué)習(xí)好數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)的前提下，不斷實(shí)踐，搞清楚每種數(shù)據(jù)結(jié)構(gòu)最大的優(yōu)點(diǎn)，沒有最強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，只有最適合的數(shù)據(jù)結(jié)構(gòu)。

參考文獻(xiàn)

[1]沈華.數(shù)據(jù)結(jié)構(gòu)、算法和程序之間關(guān)系的探討[J].計(jì)算機(jī)教育，2013，（04）：58-61.

[2]董建寅，羅遠(yuǎn).學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義和作用[J].福建電腦，2006，（07）：211-212.endprint