2.1　數據結構概述

數據結構是計算機中對數據的一種存儲和組織方式，同時也泛指相互之間存在一種或多種特定關系的數據的集合。數據結構是計算機藝術的一種體現，合理的數據結構能夠提高算法的執行效率，還可以提高數據的存儲效率。

2.1.1　什么是數據結構

什么是數據結構，數據結構的具體定義又是什么呢？數據結構是計算機程序設計的產物，其實，到現在為止，計算機技術領域中還沒有一個統一的數據結構的定義。不同的專家往往對數據結構有不同的描述，以下就是幾種典型的定義。

“數據結構是數據對象、存在于該對象的實例以及組成實例的數據元素之間的各種關系，并且這種關系可以通過定義相關的函數來給出。”這是Sartaj Sahni在其經典著作《數據結構、算法與應用》一書中提出的，他將數據對象定義為一個實例或值的集合。

“數據結構是抽象數據類型ADT的物理實現。”這是Clifford A.Shaffer在其《數據結構與算法分析》一書中定義的。其中抽象數據類型的英文全稱為Abstract Data Type，簡稱為ADT。抽象數據類型ADT的概念將在后面講到。

Lobert L.Kruse也給出了數據結構設計過程的概念，他認為一個數據結構的設計過程可以分為抽象層、數據結構層和實現層。其中，抽象層是指抽象數據類型層，即ADT層，主要討論數據的邏輯結構及其運算；數據結構層討論一個數據結構的表示；實現層討論一個數據結構在計算機內的存儲細節及運算的實現。

雖然沒有一個統一的定義，但是這些定義都具有相同的含義。在這里讀者只需了解數據結構的基本含義，并能夠使用其解決問題即可。可以這樣簡單地理解數據結構，一個數據結構是由數據元素依據某種邏輯聯系組織起來的，對數據元素間邏輯關系的描述稱為數據的邏輯結構。由于數據必須在計算機內存儲，數據的存儲結構是其在計算機內的表示，也就是數據結構的實現形式。另外，討論一個數據結構，必須涉及在該類數據上執行的運算。

數據結構是一切算法的基礎，不僅如此，數據結構可以說是程序設計語言的基礎。正是由于對數據結構的深入理解，才導致多種多樣的程序設計語言的誕生，如Java、C++、C#等。其中，面向對象的程序設計語言就是完善處理對象類型數據結構的范例，這在某些方面可以方便地描述和解決實際問題。

2.1.2　數據結構中的基本概念

深入了解數據結構之前，讀者需要簡單掌握數據結構中涉及的一些基本概念，主要包括如下內容。

?數據（Data）：數據是信息的載體，其能夠被計算機識別、存儲和加工處理，是計算機程序加工的“原材料”。數據包括的類型非常廣，如基本的整數、字符、字符串、實數等，此外，圖像和聲音等也都可以認為是一種數據。

?數據元素（Data Element）：數據元素是數據的基本單位，也稱為元素、結點、頂點、記錄等。一般來說，一個數據元素可以由若干數據項組成，數據項是具有獨立含義的最小標識單位。數據項也可稱為字段、域、屬性等。

?數據結構（Data Structure）：數據結構指的是數據之間的相互關系，即數據的組織形式。這就是本章所要討論的主要內容。

2.1.3　數據結構的內容

一般來說，數據結構包括三方面的內容，數據的邏輯結構、數據的存儲結構和數據的運算。下面就將分析這三方面的內容。

?數據的邏輯結構（Logical Structure）：即數據元素（Data Element）之間的邏輯關系。數據的邏輯結構是從邏輯關系上描述數據的，與數據在計算機中如何存儲無關，也就是獨立于計算機的抽象概念。從數學分析的角度來看，數據的邏輯結構可以看作從具體問題抽象出來的數學模型。

?數據的存儲結構（Storage Structure）：即數據元素（Data Element）及其邏輯關系在計算機存儲器中的表示形式。數據的存儲結構依賴于計算機語言，是邏輯結構用計算機語言的實現。一般來說，只有在高級語言的層次上才會討論存儲結構，在低級的機器語言中，存儲結構是具體的。

?數據的運算：即能夠對數據施加的操作。數據的運算的基礎為數據的邏輯結構，每種邏輯結構都可以歸納為一個運算的集合。在數據結構范疇內，最常用的運算包括檢索、插入、刪除、更新、排序等。

1）數據結構的例子

為了便于讀者理解，下面舉一個例子來分析有關數據結構的概念和內容。表2-1所示為某班級學生成績表，這里顯示的是其中一部分。

在表2-1中，每一行可以看作一個數據元素（Data Element），也可以稱為記錄或者結點。這個數據元素由學號、姓名、數學成績、物理成績、英語成績和語文成績等數據項構成。

通過這個表首先來看一下數據元素之間的邏輯關系。下面用數據結構的語言來描述這些邏輯關系。

?對于表中任意一個結點，直接前趨（Immediate Predecessor）結點最多只有一個。直接前趨結點即與它相鄰且在它前面的結點。

?對于表中任意一個結點，直接后繼（Immediate Successor）結點最多只有一個。直接后繼結點即與它相鄰且在它后面的結點。

?表中只有第一個結點沒有直接前趨，即開始結點。

?表中只有最后一個結點沒有直接后繼，即終端結點。

例如，表中“張三”所在的結點就是開始結點，“馬七”所在的結點就是終端結點。表中間的“陳九”所在結點的直接前趨結點是“李四”所在的結點，表中間的“陳九”所在結點的直接后繼結點是“王一”所在的結點。這些結點關系就構成了某班級學生成績表的邏輯結構。

然后再來看一下數據的存儲結構。數據的存儲結構是數據元素及其邏輯關系在計算機存儲器中的表示形式。這就需要采用計算機語言來進行描述，例如，是每個結點按照順序依次存儲在一片連續的存儲單元中呢，還是存儲在分散的空間而使用引用將這些結點鏈接起來呢？這方面的內容將在后面進行詳述。

最后，再來分析數據的運算。當拿到這個表之后，應進行哪些操作呢？一般來說，主要包括如下操作。

?查找某個學生的成績。

?對于新入學的學生，在表中增加一個結點來存放。

?對于退學的學生，將其結點從表中刪除。

當然，還包括計算每個學生的總成績、平均成績、整個班級的平均成績等，不過這些內容就不屬于數據結構的范疇了。上述三種操作就是最基本的數據結構的運算，即數據結點的查找、插入和刪除。

這樣，結合這個簡單的例子讀者便能夠理解數據結構的基本概念和內容。

2）數據結構是一個有機的整體

其實，數據的邏輯結構、數據的存儲結構和數據的運算是一個整體，孤立地去理解這三者中的任何一個都是不全面的。這主要表現在如下方面。

?同一個邏輯結構可以有不同的存儲結構。邏輯結構和存儲結構是兩個概念，同一個邏輯結構可以有不同的存儲結構。例如，線性表是最簡單的一種邏輯結構，如果線性表采用順序方式存儲，這種數據結構就是順序表；如果線性表采用鏈式方式存儲，這種數據結構就是鏈表；如果線性表采用散列方式存儲，這種數據結構就是散列表。

?同一種邏輯結構也可以有不同的數據運算集合。數據的運算是數據結構中十分重要的內容。一個相同的數據邏輯結構和存儲結構采用不同的運算集合及運算性質，將導致全新的數據結構。例如，如果將線性表的插入運算限制在表的一端，而刪除操作限制在表的另一端，那么這種數據結構就是隊列；如果將線性表的插入和刪除操作都限制在表的同一端，那么這種數據結構就是棧。

數據結構中的這三方面是一個有機的整體，缺一不可。數據的邏輯結構、數據的存儲結構和數據的運算任何一個發生變化都將導致一個全新的數據結構出現。

2.1.4　數據結構的分類

數據結構有很多種，一般來說，按照數據的邏輯結構來對其進行簡單地分類，可分為線性結構和非線性結構兩類。

1）線性結構

簡單地說，線性結構就是表中各個結點具有線性關系。如果從數據結構的語言來描述的話，線性結構應該包括如下內容：

?線性結構是非空集；

?線性結構有且僅有一個開始結點和一個終端結點；

?線性結構所有結點最多只有一個直接前趨結點和一個直接后繼結點。

前面提到的線性表就是典型的線性結構，還有棧、隊列和串等都是線性結構。

2）非線性結構

簡單地說，非線性結構就是表中各個結點之間具有多個對應關系。如果從數據結構的語言來描述，非線性結構應該包括如下內容：

?非線性結構是非空集；

?非線性結構的一個結點可能有多個直接前趨結點和直接后繼結點。

在實際應用中，數組、廣義表、樹結構和圖結構等數據結構都是非線性結構。

2.1.5　數據結構的幾種存儲方式

數據的存儲結構是數據結構的一個重要內容。在計算機中，數據的存儲結構可以采用如下4種方法來實現。

1）順序存儲方式

簡單地說，順序存儲方式就是在一塊連續的存儲區域一個接著一個地存放數據。順序存儲方式把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。順序存儲方式也稱為順序存儲結構（Sequential Storage Structure），一般采用數組或者結構數組來描述。

線性存儲方式主要用于線性邏輯結構的數據存放，而對于圖和樹等非線性邏輯結構則不適用。

2）鏈接存儲方式

鏈接存儲方式比較靈活，其不要求邏輯上相鄰的結點在物理位置上相鄰，結點間的邏輯關系由附加的引用字段表示。一個結點的引用字段往往指向下一個結點的存放位置。

鏈接存儲方式也稱為鏈式存儲結構（Linked Storage Structure），一般在原數據項中增加引用類型來表示結點之間的位置關系。

3）索引存儲方式

索引存儲方式是采用附加的索引表的方式來存儲結點信息的一種存儲方式。索引表由若干索引項組成。索引存儲方式中索引項的一般形式為：（關鍵字、地址）。其中，關鍵字是能夠唯一標識一個結點的數據項。

索引存儲方式還可以細分為如下兩類。

?稠密索引（Dense Index）：這種方式中每個結點在索引表中都有一個索引項，其中，索引項的地址指示結點所在的存儲位置；

?稀疏索引（Spare Index）：這種方式中一組結點在索引表中只對應一個索引項。其中，索引項的地址指示一組結點的起始存儲位置。

4）散列存儲方式

散列存儲方式是根據結點的關鍵字直接計算出該結點的存儲地址的一種存儲方式。

在實際應用中，往往需要根據具體的數據結構來決定采用哪種存儲方式。同一邏輯結構采用不同的存儲方法，可以得到不同的存儲結構。而且這4種基本存儲方法，既可單獨使用，也可組合起來對數據結構進行存儲描述。

2.1.6　數據類型

幾乎每一種程序設計語言都會講到數據類型的概念。簡單地說，數據類型就是一個值的集合及在這些值上定義的一系列操作的總稱。例如，對于C語言的整數類型，其有一定的取值范圍，對于整數類型還定義了加法、減法、乘法、除法和取模運算等操作。

按照數據類型的值是否可以分解，數據類型可以分為基本數據類型和聚合數據類型。

?基本數據類型：其值不能進一步分解，一般是程序設計語言自身定義的一些數據類型，如C語言中的整型、字符型、浮點型等。

?聚合數據類型：其值可以進一步分解為若干分量，一般是用戶自定義的數據類型，如C語言中的結構、數組等。

上述數據類型的概念在一般的程序設計語言中都會講到。在這里將重點看一下另外一個概念，抽象數據類型（Abstract Type，簡稱為ADT）。

抽象數據類型ADT指的是數據的組織及其相關的操作。ADT可以看作數據的邏輯結構及其在邏輯結構上定義的操作。一個抽象數據類型ADT可以定義為如下形式：

抽象數據類型ADT一般具有如下兩個重要特征。

?數據抽象：使用抽象數據類型ADT時，其強調的是實體的本質特征，所能夠完成的功能，以及與外部用戶的接口。

?數據封裝：用于將實體的外部特性和其內部實現細節進行分離，并且對外部用戶隱藏其內部實現細節。

抽象數據類型ADT可以看作描述問題的模型，它獨立于具體實現。ADT的優點是將數據和操作封裝在一起，使得用戶程序只能通過在ADT里定義的某些操作來訪問其中的數據，從而實現了信息隱藏。在Java語言中是使用接口來表示抽象數據類型ADT，用接口的實現類來實現ADT的。

抽象數據類型ADT和接口的概念其實很好地表現了程序設計中的兩層抽象。抽象數據類型ADT是概念層上的抽象，而接口則屬于實現層上的抽象。

2.1.7　常用的數據結構

在計算機科學的發展過程中，數據結構也在隨著發展。目前，程序設計中常用的數據結構包括如下內容。

1）數組（Array）

數組是一種聚合數據類型，是將具有相同類型的若干變量有序地組織在一起的集合。數組可以說是最基本的數據結構，在各種編程語言中都有對應。一個數組可以分解為多個數組元素，按照數據元素的類型，數組可以分為整型數組、字符型數組、浮點型數組、對象數組等。數組還可以有一維、二維及多維等表現形式。

2）棧（Stack）

棧是一種特殊的線性表，其只能在一個表的一個固定端進行數據結點的插入和刪除操作。棧按照后進先出的原則來存儲數據，也就是說，先插入的數據將被壓入棧低，最后插入的數據在棧頂，讀出數據時，從棧頂開式逐個讀出。棧在匯編語言程序中經常用于重要數據的現場保護。棧中沒有數據時，稱為空棧。

3）隊列（Queue）

隊列和棧類似，也是一種特殊的線性表。和棧不同的是，隊列只允許在表的一端進行插入操作，而在另一端進行刪除操作。一般來說，進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。隊列中沒有元素時，稱為空隊列。

4）鏈表（Linked List）

鏈表是一種數據元素按照鏈式存儲結構進行存儲的數據結構，這種存儲結構在物理上具有非連續的特點。鏈表由一系列數據結點構成，每個數據節點包括數據域和引用域兩部分。其中，引用域保存了數據結構中下一個元素存放的地址。鏈表結構中數據元素的邏輯順序是通過鏈表中的引用鏈接次序來實現的。

5）樹（Tree）

樹是典型的非線性結構，其是包括n個結點的有窮集合K。在樹結構中，有且僅有一個根結點，該結點沒有前驅結點。在樹結構中的其他結點都有且僅有一個前驅結點，而且可以有m個后繼結點，m≥0。

6）圖（Graph）

圖是另外一種非線性數據結構。在圖結構中，數據結點一般稱為頂點，而邊是頂點的有序偶對。如果兩個頂點之間存在一條邊，那么就表示這兩個頂點具有相鄰關系。

7）堆（Heap）

堆是一種特殊的樹型數據結構，一般討論的堆都是二叉堆。堆的特點是其根結點的值是所有結點中最小的或者最大的，并且根結點的兩個子樹也是一個堆結構。

8）散列表（Hash）

散列表源自于散列函數（Hash function），其思想是如果在結構中存在關鍵字和T相等的記錄，那么必定在F（T）的存儲位置可以找到該記錄，這樣就可以不用進行比較而直接取得所查記錄。

2.1.8　選擇合適的數據結構解決實際問題

計算機給程序員帶來了很大的方便。計算機能夠處理的問題一般可以分為兩類：數值計算問題和非數值計算問題。

數值計算問題在早期的計算機發展中占據了很大的比例。例如，線性方程的求解、矩陣的計算等。這類問題一般需要程序設計的技巧和相應的數學知識，而數據結構方面涉及的內容比較少。

隨著計算機應用范圍的擴大，一些非數值計算問題越來越突出，成為計算機解決的焦點問題。目前來說，非數值計算問題大約占據了80％的計算機工作時間。高效解決這類問題不僅需要數學知識，而且還需要設計合理的數據結構。例如，在一個包含大量數據的電話號碼簿中查找指定號碼的問題，運動比賽的賽程時間安排問題等。這些問題往往不能簡單地用數學公式來表示，還需要合理地選擇數據結構來處理。

在本書中，對于數值計算問題和非數值計算問題都會涉及。數值計算相關的問題主要是一些數學和工程中的計算算法，包括多項式求解、矩陣計算、微分、積分等算法。非數值計算問題主要是本章的數據結構及后面章節中的數據結構問題。