1.1 什么是數據結構

1.1.1 基本概念

（1）數據：信息的載體，是客觀事物的符號表示。數據能夠被計算機識別、存取和處理，數據也是計算機程序加工和處理的“原料”。例如，實數、字符串、圖像和聲音等。

（2）數據項：具有獨立含義的最小標識單位。例如，字段、域、屬性等。

（3）數據元素：數據的基本單位。一個數據元素可由若干個數據項組成。

（4）數據對象：性質相同的數據元素的集合，是數據的一個子集。例如，26個英文字母構成的字符集合，一個學校全體學生或教師構成的學生集合或教師集合等。

（5）數據結構：相互之間存在一種或多種特定關系的數據元素的集合，即數據的組織形式。數據結構的形式化定義通常用一個二元組Data_Structure=(D, R)來表示，式中，D是數據元素的有限集（也即數據對象），R是D上關系的有限集。

1.1.2 數據結構的內涵

數據結構一般包含數據的邏輯結構和存儲結構及數據運算。數據結構的研究內容包括兩方面：一方面是抽象地研究數據集合的結構（抽象數據結構）特點；另一方面是研究如何把抽象數據結構轉化為存儲組織形式（數據的存儲結構）。這兩方面的研究既可獨立于各個領域的應用來研究，也可結合具體應用領域中的特點來進行研究。例如，專門研究計算機圖像識別或定理證明中的數據結構。目前，從抽象數據類型的觀點來討論數據結構已經成為一種新的趨勢，并越來越被人們所重視。

1.數據的邏輯結構

數據的邏輯結構是指數據元素以及它們相互之間的邏輯關系，數據的邏輯結構與數據的存儲無關。根據數據元素之間關系的不同特性，通常有4 類邏輯結構：① 集合，集合的邏輯結構中所有數據元素都屬于同一個集合，所有數據元素雜亂無章地聚集在一起，各個數據元素之間無任何聯系；② 線性結構，邏輯結構中的數據元素之間存在著一個對一個的關系，各個數據元素之間通常有嚴格的先后次序關系；③ 樹形結構，邏輯結構中的數據元素之間存在著一個對多個的關系，各個數據元素之間通常有嚴格的層次關系；④ 圖狀結構，邏輯結構中的數據元素之間存在著多個對多個的關系，各個數據元素之間均可能存在相互聯系。

在不產生混淆的前提下，常將數據的邏輯結構簡稱為數據結構。除了上述4 類邏輯結構之外，根據數據元素（結點）之間的前后相鄰關系，數據的邏輯結構還可分為線性結構和非線性結構兩大類：① 線性結構的邏輯特征是，若結構是非空集，則有且僅有一個開始結點和一個終端結點，并所有結點都最多只有一個直接前驅結點和一個直接后繼結點。線性表是一個典型的線性結構，棧、隊列和串等都是線性結構；② 非線性結構的邏輯特征是，一個結點可能有多個直接前驅和直接后繼。樹和圖都是非線性結構。

【例1-1】 怎樣描述數據的邏輯結構？

對數據元素之間關系的描述是數據的邏輯結構，它可形式地用一個二元組表示為K=(D, R)，式中，D是由有限個結點所構成的集合，R是由有限個關系所構成的集合。有時為了直觀起見，也用以圖示法來表示數據的邏輯結構。邏輯結構與使用的計算機無關。例如，一批數據的邏輯結構K=(D, R)，式中，D={d1, d2, …, d9}，R={<d1, d2>,<d1, d3>,<d1, d4>,<d1, d7>,<d1, d8>,<d4, d5>,<d4, d6>,<d8, d9>}，則該批數據的邏輯結構如圖1.1所示。對于R中包含有多種關系的情況，也可用類似的方法描述。

2.數據的存儲結構

數據的存儲結構（物理結構）是指數據在計算機中的存儲表示，它包括數據元素的表示和關系的表示。數據的存儲結構有以下4種基本存儲方法。

① 順序存儲。該存儲方法把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構（sequential storage structure）。該方法通常借助于高級程序語言中的數組來描述，且主要應用于線性的數據結構。非線性的數據結構也可通過線性化的方法來實現順序存儲。

② 鏈接存儲。該方法不要求邏輯上相鄰的結點在物理位置上也相鄰，結點之間的邏輯關系由附加的指針字段表示。由此得到的存儲表示稱為鏈式存儲結構（linked storage structure），通常借助于高級程序語言的指針類型來描述。

③ 索引存儲。該方法通常在存儲結點信息的同時，還要建立附加的索引表。索引表由若干索引項組成。若每個結點在索引表中都有一個索引項，則該索引表稱之為稠密索引（dense index）。若一組結點在索引表中只對應一個索引項，則該索引表稱為稀疏索引（spare index）。索引項的形式一般是（關鍵字，地址），關鍵字是能唯一標識一個結點的那些數據項。稠密索引中索引項的地址指示結點所在的存儲位置，稀疏索引中索引項的地址指示一組結點的起始存儲位置。

④ 散列存儲。該方法根據結點的關鍵字直接計算出該結點的存儲地址。

以上述4 種基本存儲方法既可單獨使用，也可組合起來對數據結構進行存儲映射。同一種邏輯結構采用不同的存儲方法，可得到不同的存儲結構。選擇何種存儲結構來表示相應的邏輯結構，要視具體的應用要求而定，主要考慮運算方便和算法的時空效率要求。

3.數據的運算

數據的運算是對數據施加的操作。數據的運算定義在數據的邏輯結構上，每種邏輯結構都有一個運算的集合。在數據結構中，運算不僅僅是加、減、乘、除等運算，大多數的運算都涉及算法的實現問題，算法的實現與數據的存儲結構是密切相關的。

1.1.3 數據類型和抽象數據類型

數據類型是一個值的集合和定義在這個值的集合上的一組操作的總稱，通常它可看作是高級程序設計語言中已經實現的數據結構。例如，C語言中的整型變量，其值的集合為某個區間上的整數（區間大小依賴于不同的機器），定義在其上的操作為加、減、乘、除和取模等算術運算。按“值”的不同特性，在高級程序語言中可分為：① 原子類型，其值不可分解，例如，C語言中的基本類型（整型、實型、字符型和枚舉類型）、指針類型和空類型；② 結構類型，其值是由若干個成分按某種結構組成的，故可分解，其成分可以是非結構的，也可以是結構的，例如，數組的值由若干分量組成，每個分量可能是整數，或者是數組。

抽象數據類型（abstract data type，ADT）是指一個數學模型以及定義在該模型上的一組操作。抽象數據類型的定義僅取決于它的一組邏輯特性，而與其在計算機內部如何表示和實現無關，也即，不論其內部結構如何變化，只要它的數學特性不變，都不會影響其外部的使用。抽象數據類型可表示為一個三元組（D, R, P），式中，D是數據對象，R是D上的關系集，P是對D的基本操作集。本書采用以下格式定義抽象數據類型：

ADT抽象數據類型名{ 數據集合：<數據對象的定義>

數據關系：<數據關系的定義>

數據操作：<數據操作的定義>

} ADT抽象數據類型名

其中，數據對象和數據關系的定義用偽碼描述，基本操作的定義格式為：

數據操作名（參數表）

輸入：<輸入條件描述>

輸出：<輸出結果描述>

【例1-2】 抽象數據類型（ADT）的定義、特點、實現與數據結構的區別是什么？

ADT是高級程序設計語言中數據類型概念的推廣，它是一個數學模型和定義在該模型上操作集合的總稱。ADT的實現方法是，將ADT轉換成現有高級程序設計語言的說明語句，加上對應于該ADT中每個操作的過程或函數，也即，用現有高級程序設計語言能夠支持的適當數據結構來表示ADT中的數學模型，并用一組過程或函數來實現定義在該模型上的各個操作。數據結構則是利用該語言的基本數據類型和復合數據的構造機制來構成的。例如，數組和記錄就是C++語言中兩種主要的復合數據的構造機制。根據ADT定義，如果在相同的數學模型上定義兩個不同的操作集，則認為它們代表兩個不同的抽象數據類型。故相同的數學模型以及在其上所定義的操作有可能在不同的ADT中出現。