初探數據結構

在經過一段時間的JAVA基礎學習之後，最近開始學習JAVA中的集合框架，當看到鏈表、散列這些數據結構的時候，總有一些雲里霧裡的感覺，迫不及待的想要瞭解其內部的實現。

目前手上有三本關於數據結構的書籍，《大話數據結構》，《數據結構與演算法分析-C語言描述》，《演算法-第四版》，這些書都經過很多人的推薦，內容應該都很優秀。

好了下麵進入主題，雖然都是很基礎的內容，但是理解掌握好這些基礎的定義，對後面的學習有著很大幫助。

一、基本概念和術語

• 數據：是描述客觀事物的符號，是電腦中可以操作的對象，是能被電腦識別，並輸入給電腦處理的符號集合。
• 數據元素：是組成數據的、有一定意義的基本單位，在電腦中通常作為整體處理。也稱為記錄。
• 數據對象：是性質相同的數據元素的集合，是數據的子集。

上面是一些官方的定義，下麵是我自己的理解。

數據元素也就是一條條記錄，它可以是單一的，也可以是由多個數據項組成。用過資料庫的童鞋應該都知道，數據表中的每一行記錄都是一個數據元素，每一列都是一個數據項，數據項是數據元素的子集。例如下圖：每一個人記錄都是一個數據元素，一個數據元素由姓名、年齡等這些數據項組成。

在數據集合中可以是性質相同的數據元素，也可以是性質不同的數據，而這裡的數據對象其實就是性質相同數據元素的集合。

二、數據結構的分類

數據結構：是相互之間存在一種或多種特定關係的數據元素的集合。

數據結構又可以分為下麵兩種結構：

1. 邏輯結構：是指數據對象中數據元素之間的相互關係。

   邏輯結構又分為以下四種：

   • 集合結構：集合結構中的數據元素除了同屬於一個集合外，它們之間沒有其他關係。
     
   • 線性結構：線性結構中的數據元素之間是一對一的關係。
     
   • 樹形結構：樹形結構中的數據元素之間存在一種一對多的層次關係。
     
   • 圖形結構：圖形結構的數據元素是多對多的關係。
     

2. 物理結構（存儲結構）：是指數據的邏輯結構在電腦中的存儲形式。

   物理結構又分為以下兩種：

   • 順序存儲結構：是把數據元素存放在地址連續的存儲單元里，其數據間的邏輯關係和物理關係是一致的。
     
   • 鏈式存儲結構：是把數據元素存放在任意的存儲單元里，這組存儲單元可以是連續的，也可以是不連續的。
     

從前面我們知道了數據對象是性質相同的數據元素的集合，而數據結構在數據對象的基礎上又多了一種或多種特定關係，這裡的特定關係主要指的就是數據元素之間的邏輯結構和物理結構。

邏輯結構是一種抽象的結構，學過電腦組成的同學可能知道，在程式運行的時候，數據是存儲在記憶體中的，而記憶體中的基本存儲單位就是存儲單元，那我們如何在記憶體中表示邏輯結構呢？

這裡就用到了物理結構，我們可以將物理結構理解成具體的，邏輯結構理解成抽象的，使用物理結構反應數據元素之間的邏輯關係，如何存儲數據元素之間的邏輯關係，是實現物理結構的重點和難點。

數據元素之間的存儲結構形式有兩種：順序存儲和鏈式存儲。我們主要使用這兩種存儲方式來反映數據元素的邏輯結構。

三、抽象數據類型

• 數據類型：是一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

  又分下以下兩種類型：

  • 原子類型：是不可以再分解的基本類型，包括整型、實型、字元型等。
  • 結構類型：由若幹個類型組合而成，是可以再分解的。例如，整型數組是由若幹個整型數據組成的。

• 抽象數據類型（ADT）：是指一個數學模型及其定義在該模型上的一組操作。

抽象數據類型：一個數據對象 + 數據對象中各數據元素的關係 + 數據元素的操作

前文中說了數據對象和數據對象中數據元素的關係組成數據結構有些不妥。這裡我認為數據結構是通過抽象數據類型來實現的，也就是說抽象數據類型是數據結構的骨架。（個人見解）

四、總結

上述內容都是數據結構的基礎，接下來的線性表、隊列、散列表、二叉樹等都是四種邏輯結構的具體實現，每一種數據結構都是相當於一個容器。尤其是線性表兩種實現方式，是學習後面其他數據結構的基礎。

在選擇學習書籍的時候，建議儘量不要一上來就選擇經典的大部頭，經典雖好，但學習也需要循序漸進，理解不了不僅浪費時間，自己長時間無法得到正向反饋，也會嚴重磨滅自己學習情緒，尤其是需要轉行自學的童鞋。我自己本身也是在脫產自學當中，前面一段時間買了很多經典的書籍，現在發現很多暫時都用不到，反而像《大話數據結構》這樣簡單易上手的書籍對自己幫助很大。

文中一些觀點僅是個人見解，由於自己也是初學，有些見解難免產生錯誤，隨著後面學習的深入，也不保證這些見解一直不變，如果你有不同的見解，歡迎一起交流。

原文鏈接：http://www.cnblogs.com/nwgdk/p/9025695.html
參考書籍：《大話數據結構》