1.2 有關(guān)概念和術(shù)語

在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)之前，先對一些基本概念和術(shù)語賦予確切的定義。

1.數(shù)據(jù)

數(shù)據(jù)（Data）是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理。數(shù)據(jù)是計(jì)算機(jī)程序加工的原料，應(yīng)用程序能處理各種各樣的數(shù)據(jù)，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)是一些整數(shù)、實(shí)數(shù)或復(fù)數(shù)；非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像、語音等。

2.數(shù)據(jù)元素

數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)（Data Item）組成。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。例如，學(xué)生信息檢索系統(tǒng)中學(xué)生信息表中的一個(gè)記錄、教學(xué)計(jì)劃編排問題中的一個(gè)頂點(diǎn)等，都被稱為一個(gè)數(shù)據(jù)元素。

3.數(shù)據(jù)項(xiàng)

數(shù)據(jù)項(xiàng)（Data Item）指不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段（field）或域。例如，學(xué)籍管理系統(tǒng)中學(xué)生信息表的每一個(gè)數(shù)據(jù)元素就是一個(gè)學(xué)生記錄。它包括學(xué)生的學(xué)號、姓名、性別、籍貫、出生年月、成績等數(shù)據(jù)項(xiàng)。這些數(shù)據(jù)項(xiàng)可以分為兩種：一種叫做初等項(xiàng)，如學(xué)生的性別、籍貫等，這些數(shù)據(jù)項(xiàng)是在數(shù)據(jù)處理時(shí)不能再分割的最小單位；另一種叫做組合項(xiàng)，如學(xué)生的成績，它可以再劃分為數(shù)學(xué)、物理、化學(xué)等更小的項(xiàng)。通常，在解決實(shí)際應(yīng)用問題時(shí)把每個(gè)學(xué)生記錄當(dāng)做一個(gè)基本單位進(jìn)行訪問和處理。

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

數(shù)據(jù)結(jié)構(gòu)（Data Structure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素都不會(huì)是孤立的，在它們之間存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間存在的關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有以下4類基本的邏輯結(jié)構(gòu)。

（1）集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是“屬于同一個(gè)集合”。數(shù)據(jù)元素之間除了同屬一個(gè)集合外，不存在其他關(guān)系。

（2）線性結(jié)構(gòu)：在該結(jié)構(gòu)中，數(shù)據(jù)元素除了同屬于一個(gè)集合外，數(shù)據(jù)元素之間還存在著一對一的順序關(guān)系。

（3）樹形結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對多的層次關(guān)系。

（4）圖狀結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的任意關(guān)系，圖狀結(jié)構(gòu)也稱為網(wǎng)狀結(jié)構(gòu)。

上述4類基本結(jié)構(gòu)的示意圖如圖1.5所示。

由于集合是數(shù)據(jù)元素之間極為松散的一種結(jié)構(gòu)，本書不專門討論。因此，本書主要討論線性結(jié)構(gòu)（表、棧、隊(duì)、串等）和非線性結(jié)構(gòu)（樹、圖或網(wǎng)）。

從上面所介紹的數(shù)據(jù)結(jié)構(gòu)的概念中可以知道，一個(gè)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素，二是數(shù)據(jù)元素之間的關(guān)系。因此，數(shù)據(jù)結(jié)構(gòu)通常可以采用一個(gè)二元組來表示：

Data_Structure=（D,R）

其中，D是數(shù)據(jù)元素集合，R是D中元素之間關(guān)系的集合。

【例1.4】 假設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)定義如下：

DS=（D,R）
D={ a, b, c, d, e, f, g }
R={ <a, b>,<a, c>,<a, d>,<c, e>,<c, f>,<d, g> }

則該數(shù)據(jù)結(jié)構(gòu)的邏輯示意如圖1.6所示，顯然是一個(gè)樹形結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看做從具體問題抽象出來的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲(chǔ)無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)（或稱存儲(chǔ)結(jié)構(gòu)），它所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的存儲(chǔ)表示及數(shù)據(jù)元素之間關(guān)系的表示。

在計(jì)算機(jī)中，數(shù)據(jù)的存儲(chǔ)方法包括順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

（1）順序存儲(chǔ)方法通過數(shù)據(jù)元素在計(jì)算機(jī)中存儲(chǔ)位置關(guān)系來表示元素間的邏輯關(guān)系，通常把邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中。順序存儲(chǔ)是一種最基本的存儲(chǔ)表示方法，通常借助程序設(shè)計(jì)語言中的數(shù)組來實(shí)現(xiàn)。

（2）鏈?zhǔn)酱鎯?chǔ)方法對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過指針字段來表示，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助程序設(shè)計(jì)語言中的指針來實(shí)現(xiàn)。

除了順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法外，有時(shí)為了查找方便還采用索引存儲(chǔ)方法和散列表（Hash）存儲(chǔ)方法。

討論數(shù)據(jù)結(jié)構(gòu)的目的就是在計(jì)算機(jī)中實(shí)現(xiàn)對數(shù)據(jù)的操作，因此在討論數(shù)據(jù)的組織結(jié)構(gòu)時(shí)必然要考慮在該結(jié)構(gòu)上進(jìn)行的操作（或稱運(yùn)算）。事實(shí)上，數(shù)據(jù)結(jié)構(gòu)是專門研究某一類數(shù)據(jù)的表示方法及其相關(guān)操作實(shí)現(xiàn)算法的一門學(xué)科。

5.數(shù)據(jù)類型

數(shù)據(jù)類型（Data Type）是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，在高級程序設(shè)計(jì)語言中用以限制變量取值范圍和可能進(jìn)行的操作的總和稱為數(shù)據(jù)類型。因此，所謂數(shù)據(jù)類型，一是限定了數(shù)據(jù)的取值范圍（實(shí)際上與存儲(chǔ)形式有關(guān)）；二是規(guī)定了數(shù)據(jù)能夠進(jìn)行的一組操作（運(yùn)算）。

數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型，原子類型的值是不可再分解的，如C語言中的基本類型（整型、實(shí)型、字符型及指針類型和空類型）；另一類是結(jié)構(gòu)類型，它的成分可以由多個(gè)結(jié)構(gòu)類型組成，并可以分解。結(jié)構(gòu)類型的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。例如，數(shù)組的值由若干分量組成，每個(gè)分量可以是整數(shù)等基本類型，也可以是數(shù)組等結(jié)構(gòu)類型。

6.抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（Abstract Data Type，ADT）是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。即無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，就不影響其外部的使用。

抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。例如，各種計(jì)算機(jī)都擁有的整數(shù)類型就是一個(gè)抽象數(shù)據(jù)類型，盡管它們在不同處理器上的實(shí)現(xiàn)方法可以不同，但由于其定義的數(shù)學(xué)特性相同，在用戶看來都是相同的。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。

抽象數(shù)據(jù)類型的定義可以由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成，而數(shù)據(jù)結(jié)構(gòu)又包括數(shù)據(jù)元素及元素間的關(guān)系，因此抽象數(shù)據(jù)類型一般可以由元素、關(guān)系及操作三個(gè)要素來定義。

本書在討論各種數(shù)據(jù)結(jié)構(gòu)時(shí)，針對其邏輯結(jié)構(gòu)和具體的存儲(chǔ)結(jié)構(gòu)給出相應(yīng)的數(shù)據(jù)類型，并在確定的數(shù)據(jù)類型上通過各種算法實(shí)現(xiàn)各種操作。