數據結構簡析

張羿九

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

關鍵詞：數據結構；算法；適用

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

1 數據結構的定義

1.1 數據元素

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

1.2 數據結構

1.2.1 邏輯數據結構

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

1.2.2 物理數據結構

那么，是否數據元素真的像邏輯數據結構那樣在電腦里有著紛繁復雜的存儲方式呢？其實電腦才不會那么聰明，數據元素在電腦里存儲的方式叫做物理數據結構也叫存儲結構，再多的數據元素對于電腦只會有兩種結構，一種順序存儲結構（存儲數據元素的地址是連續的），一種鏈式存儲結構（存儲數據元素的地址是任意的，需要指針串起所有數據元素）。物理數據結構面向的是計算機。而邏輯數據結構是一種便于人們理解，處理問題的結構，實際并不是那樣存儲在電腦里，其面向的更多在于程序員和問題本身。但我們在處理問題時，由于有編譯器的存在，我們并不需要過于糾結于計算機該怎樣存儲，而是去分析問題，解決問題。所以后文所說的數據結構，不特別聲明，都指的是邏輯數據結構。

1.3 數據結構分類

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

2 主要數據結構的適用范圍

2.1 鏈表

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

2.2 棧

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

2.3 串

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

3 數據結構的意義

3.1 數據結構的重要性

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

3.2 數據結構與算法的關系

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

3.3 初學者為什么要學習數據結構

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

4 結語

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

參考文獻

[1]沈華.數據結構、算法和程序之間關系的探討[J].計算機教育，2013，（04）：58-61.

[2]董建寅，羅遠.學習數據結構的意義和作用[J].福建電腦，2006，（07）：211-212.endprint