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

張羿九

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2017）10-0218-02

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

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

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，可以由多個用于表示其屬性的數(shù)據(jù)項組成，數(shù)據(jù)項是處理數(shù)據(jù)時的最小單位。在化學中，原子是由質(zhì)子和中子構(gòu)成的，然而盡管質(zhì)子和中子在尺度上更小，但原子才是研究問題時的的最小單位，因為原子是保持物質(zhì)化學性質(zhì)的最小的單位，就算分子也是由原子構(gòu)成的。同樣的道理，數(shù)據(jù)元素就好比原子，數(shù)據(jù)項就好比質(zhì)子和中子，數(shù)據(jù)項必須由多個組合在一起才是一個完整的、有意義的數(shù)據(jù)元素，所以我們在處理數(shù)據(jù)時，通常不會從數(shù)據(jù)項處理起，而是對數(shù)據(jù)元素這一整體進行分析。

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

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

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

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

那么，是否數(shù)據(jù)元素真的像邏輯數(shù)據(jù)結(jié)構(gòu)那樣在電腦里有著紛繁復雜的存儲方式呢？其實電腦才不會那么聰明，數(shù)據(jù)元素在電腦里存儲的方式叫做物理數(shù)據(jù)結(jié)構(gòu)也叫存儲結(jié)構(gòu)，再多的數(shù)據(jù)元素對于電腦只會有兩種結(jié)構(gòu)，一種順序存儲結(jié)構(gòu)（存儲數(shù)據(jù)元素的地址是連續(xù)的），一種鏈式存儲結(jié)構(gòu)（存儲數(shù)據(jù)元素的地址是任意的，需要指針串起所有數(shù)據(jù)元素）。物理數(shù)據(jù)結(jié)構(gòu)面向的是計算機。而邏輯數(shù)據(jù)結(jié)構(gòu)是一種便于人們理解，處理問題的結(jié)構(gòu)，實際并不是那樣存儲在電腦里，其面向的更多在于程序員和問題本身。但我們在處理問題時，由于有編譯器的存在，我們并不需要過于糾結(jié)于計算機該怎樣存儲，而是去分析問題，解決問題。所以后文所說的數(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)：每個數(shù)據(jù)元素之間沒有聯(lián)系，只是同屬于一個集合，和數(shù)學上的集合定義很相似；（2）線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一一對應(yīng)關(guān)系，就像一條線一樣串被在一起。如棧、隊列和線性表都屬于線性結(jié)構(gòu)；（3）樹形結(jié)構(gòu)：數(shù)據(jù)元素間存在一對多的關(guān)系，猶如樹根，不斷生長，分叉，再生長，再分叉；（4）圖形結(jié)構(gòu)：數(shù)據(jù)元素間存在多對一，一對多的關(guān)系，猶如地圖上的每個地點，相互之間有密密麻麻的交通干道連接，從A點出發(fā)可以到很多地方，想回到A也有很多條路。

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

2.1 鏈表

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

2.2 棧

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

2.3 串

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻

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

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