1.2　數(shù)據(jù)結(jié)構(gòu)概述

1.2.1　數(shù)據(jù)結(jié)構(gòu)及其數(shù)據(jù)運算的概念

早期的計算機(jī)主要用于數(shù)值計算，20世紀(jì)70年代出現(xiàn)微處理機(jī)后，計算機(jī)被大量用于信息處理，計算機(jī)的應(yīng)用領(lǐng)域被拓寬。90年代計算機(jī)網(wǎng)絡(luò)日益普及，發(fā)展至今已成為集計算、數(shù)據(jù)處理、數(shù)據(jù)傳輸于一體的信息處理系統(tǒng)，并且廣泛應(yīng)用于工業(yè)領(lǐng)域。現(xiàn)代計算機(jī)軟件強(qiáng)調(diào)的是數(shù)據(jù)管理，數(shù)據(jù)結(jié)構(gòu)則是數(shù)據(jù)管理的前提。

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)的重要基礎(chǔ)，近年來已發(fā)展成為一個專門學(xué)科。根據(jù)各種實際問題的需求，人們提出了許多組織數(shù)據(jù)的方法，從而構(gòu)造了不同的數(shù)據(jù)結(jié)構(gòu)，而且隨著實際問題需要的增加，新的更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)還在不斷地被提出。

首先介紹與數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念和技術(shù)術(shù)語。

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

數(shù)據(jù)是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入計算機(jī)中并被計算機(jī)程序處理的符號的總稱。對計算機(jī)而言，數(shù)據(jù)的含義極為廣泛，如數(shù)字、文字、圖形、圖像、聲音等都是數(shù)據(jù)。數(shù)據(jù)與信息不同，數(shù)據(jù)是以機(jī)器可讀的形式存儲的信息，當(dāng)計算機(jī)把這些數(shù)據(jù)處理成人們可以理解的形式時，數(shù)據(jù)就成為信息，信息是特殊的數(shù)據(jù)集。

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

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)集合中的個體，是對事物屬性中基本方面的測量。在不同的應(yīng)用背景下也把數(shù)據(jù)元素稱為結(jié)點、記錄、表目等。一個數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成。

3.數(shù)據(jù)項

數(shù)據(jù)項是具有獨立含義的數(shù)據(jù)的最小單位，在計算機(jī)程序中它通常被作為一個整體來進(jìn)行考慮和處理，是對數(shù)據(jù)元素屬性的描述。數(shù)據(jù)項也被稱為域或字段。例如，在產(chǎn)品檔案管理系統(tǒng)中，可以把一個產(chǎn)品的有關(guān)信息作為一個數(shù)據(jù)元素，它由產(chǎn)品號、名稱、生產(chǎn)日期等數(shù)據(jù)項組成。

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

數(shù)據(jù)類型是指某種程序設(shè)計語言所允許使用的變量種類。各種高級語言所提供的基本數(shù)據(jù)類型有所不同，如C++提供了整型、實型和字符型等基本數(shù)據(jù)類型。除基本類型外，C++還允許數(shù)組型、結(jié)構(gòu)型、聯(lián)合型等構(gòu)造類型。一個數(shù)據(jù)類型不僅定義了相應(yīng)變量可以設(shè)定的值的集合和存儲方法，而且還規(guī)定了對變量允許進(jìn)行的一組運算及規(guī)則。所以，可以把數(shù)據(jù)類型看作程序設(shè)計語言中已實現(xiàn)了結(jié)構(gòu)化的數(shù)據(jù)類別。

5.數(shù)據(jù)對象

數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，所有的字母構(gòu)成的集合C=（'A'，'B'，…，'Z'）是一個字母數(shù)據(jù)對象；在產(chǎn)品質(zhì)量檔案管理系統(tǒng)中由某類產(chǎn)品構(gòu)成的集合是一個產(chǎn)品數(shù)據(jù)對象，如傳動結(jié)構(gòu)對象中就包含了主動軸和從動軸等零件。

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

任何事物都存在結(jié)構(gòu)意義上的限定，因此，數(shù)據(jù)作為對事物的描述載體自然也是存在結(jié)構(gòu)的。數(shù)據(jù)結(jié)構(gòu)是存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是帶有經(jīng)過組織，并形成特定結(jié)構(gòu)的元素的集合，它體現(xiàn)了數(shù)據(jù)之間的相互關(guān)系，即體現(xiàn)了數(shù)據(jù)的組織形式。例如，在描述軸系零件的裝配關(guān)系時，可能會用到堆棧結(jié)構(gòu)，可以描述機(jī)器的裝拆順序。總之，數(shù)據(jù)結(jié)構(gòu)一般包括三方面的內(nèi)容，也被稱為數(shù)據(jù)的三要素：數(shù)據(jù)間的邏輯關(guān)系、數(shù)據(jù)在計算機(jī)中的存儲關(guān)系以及在這些數(shù)據(jù)上定義的運算。

（1）數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。計算機(jī)加工處理的數(shù)據(jù)元素不是互相孤立的，它們彼此之間應(yīng)當(dāng)存在某些邏輯上的關(guān)聯(lián)，不然，對這些數(shù)據(jù)元素的處理就是無意義的。邏輯結(jié)構(gòu)總是和所要解決的問題相對應(yīng)，并不涉及數(shù)據(jù)元素在計算機(jī)存儲器中的具體存放狀態(tài)，即數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲形式無關(guān)，是獨立于計算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作從具體問題抽象出來的數(shù)據(jù)模型。數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性和非線性結(jié)構(gòu)。當(dāng)數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個線性序列表示出來時，則稱為線性數(shù)據(jù)結(jié)構(gòu)；否則稱為非線性數(shù)據(jù)結(jié)構(gòu)。

（2）數(shù)據(jù)元素在計算機(jī)存儲器中的物理存儲結(jié)構(gòu)，體現(xiàn)的是數(shù)據(jù)元素在物理存儲空間中的實際分布情況。數(shù)據(jù)的物理存儲結(jié)構(gòu)不僅要存儲數(shù)據(jù)元素的內(nèi)容，還要把數(shù)據(jù)元素間的關(guān)聯(lián)體現(xiàn)出來，它是邏輯結(jié)構(gòu)用計算機(jī)所能理解的方式的具體實現(xiàn)。存儲結(jié)構(gòu)是依賴于計算機(jī)程序的，對具體的程序而言，存儲結(jié)構(gòu)是具體的，我們只在高級語言的層次上來討論存儲結(jié)構(gòu)，這使得數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)具有某種程度的同一性。存儲結(jié)構(gòu)主要分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。順序結(jié)構(gòu)以元素在存儲器中的相對位置來表示元素間的邏輯關(guān)系，鏈?zhǔn)浇Y(jié)構(gòu)借助元素存儲地址的指針來表示元素間的邏輯關(guān)系，這是它們在具體程序中的重要區(qū)別。此外，存儲結(jié)構(gòu)還有索引存儲和散列存儲等。

（3）施加在數(shù)據(jù)上的操作，即數(shù)據(jù)的運算。一種特定的數(shù)據(jù)結(jié)構(gòu)其實已經(jīng)限定了施加在其上的運算操作方式。數(shù)據(jù)的運算是在數(shù)據(jù)上所施加的一系列操作，稱為抽象運算。它只考慮這些操作的功能，而不考慮具體的操作步驟。只有在確定了存儲結(jié)構(gòu)后，才會具體實施這些操作，即抽象運算是以邏輯結(jié)構(gòu)為基礎(chǔ)的，具體的實現(xiàn)要在存儲結(jié)構(gòu)上來完成。數(shù)據(jù)的運算是數(shù)據(jù)結(jié)構(gòu)的一個重要成分。研究任何一種數(shù)據(jù)結(jié)構(gòu)都離不開對針對該結(jié)構(gòu)的數(shù)據(jù)運算及算法的討論。

算法是為解決特定問題而采取的有限運算步驟，是對解題方案的準(zhǔn)確而完整的描述。數(shù)據(jù)結(jié)構(gòu)與算法之間存在著密切的關(guān)系。一方面算法的效率受到數(shù)據(jù)結(jié)構(gòu)的影響；另一方面針對不同數(shù)據(jù)結(jié)構(gòu)也會采用不同的算法。數(shù)據(jù)結(jié)構(gòu)和算法是計算機(jī)軟件的兩個不可分割的方面，其內(nèi)容將在本章重點敘述。

總之，無論怎樣定義數(shù)據(jù)結(jié)構(gòu)，都應(yīng)將該數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算這三方面看成一個整體，要體現(xiàn)它們之間的聯(lián)系。

在計算機(jī)發(fā)展的早期，計算機(jī)主要用于科學(xué)計算，處理的是數(shù)值數(shù)據(jù)。當(dāng)時的數(shù)據(jù)特點是：數(shù)據(jù)元素之間的關(guān)系簡單、數(shù)據(jù)量小、形式較為一致。因此，程序設(shè)計人員更加注重的是算法，而不注重對數(shù)據(jù)的組織、性質(zhì)、關(guān)系的研究。

隨著計算機(jī)產(chǎn)業(yè)的飛速發(fā)展和計算機(jī)應(yīng)用的日益普及，計算機(jī)已越來越廣泛地應(yīng)用于各種非數(shù)值處理問題，其應(yīng)用已逐步深入事務(wù)管理、工業(yè)控制、公共通信、教育和軍事等領(lǐng)域。待處理的數(shù)據(jù)形式多樣，數(shù)量越來越大，關(guān)系越來越復(fù)雜。要想對這些數(shù)據(jù)進(jìn)行快速有效的處理，就必須了解數(shù)據(jù)的性質(zhì)、組織方式和相互之間的關(guān)系。這樣才能采用適當(dāng)?shù)姆绞竭M(jìn)行存儲，選用高效的算法進(jìn)行處理。這正是數(shù)據(jù)結(jié)構(gòu)所要研究的內(nèi)容。也就是說，數(shù)據(jù)結(jié)構(gòu)是一門對計算機(jī)所處理的數(shù)據(jù)的表示、組織和操作進(jìn)行系統(tǒng)研究的學(xué)科。

在計算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)與算法是密不可分、缺一不可的。算法指的是對計算機(jī)問題的全過程及具體步驟的描述，計算機(jī)程序正是按照算法所描述的步驟對某種結(jié)構(gòu)的數(shù)據(jù)進(jìn)行加工處理的。如果沒有數(shù)據(jù)結(jié)構(gòu)，計算機(jī)就缺少了處理的基礎(chǔ)；而沒有算法，計算機(jī)就缺少了求解問題的方法。因此，著名的計算機(jī)科學(xué)家N.Wirth在論述算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系時就曾指出：

程序=數(shù)據(jù)結(jié)構(gòu)+算法

這一公式揭示了數(shù)據(jù)結(jié)構(gòu)和算法之間的天然聯(lián)系。

數(shù)據(jù)結(jié)構(gòu)往往是與施加于其上的運算密切相關(guān)的。數(shù)據(jù)按一定的邏輯結(jié)構(gòu)組織起來，再把數(shù)據(jù)結(jié)構(gòu)用適當(dāng)?shù)拇鎯Ψ绞酱鎯Φ接嬎銠C(jī)中，其目的就是實現(xiàn)運算過程和提高數(shù)據(jù)的運算效率，從而更有效地處理數(shù)據(jù)。各種邏輯結(jié)構(gòu)有其相應(yīng)的運算，即每種邏輯結(jié)構(gòu)有一個運算的集合。數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，運算的具體實現(xiàn)要在存儲結(jié)構(gòu)上進(jìn)行。對于數(shù)據(jù)本身而言，有各種具體的數(shù)學(xué)運算；對于各類數(shù)據(jù)結(jié)構(gòu)而言，它們在基本運算方面是相似的。最常用的運算有：

①插入：其含義是在數(shù)據(jù)結(jié)構(gòu)中增加新的結(jié)點。

②刪除：其含義是把指定的結(jié)點從數(shù)據(jù)結(jié)構(gòu)中去除。

③更新：其含義是改變指定結(jié)點的值或改變指定的某些結(jié)點之間的關(guān)系。

④查找：其含義是在數(shù)據(jù)結(jié)構(gòu)中查找滿足一定條件的結(jié)點。

⑤排序：其含義是對數(shù)據(jù)結(jié)構(gòu)中各個結(jié)點按指定數(shù)據(jù)項的值以升序或降序重新排列。

針對數(shù)據(jù)結(jié)構(gòu)的復(fù)雜運算過程可以是以上各種基本操作的組合。

在工程軟件系統(tǒng)中，往往要構(gòu)建各類數(shù)據(jù)結(jié)構(gòu)，以描述復(fù)雜的工程對象。數(shù)據(jù)結(jié)構(gòu)的描述通常采用的是面向?qū)ο蟮臄?shù)據(jù)類（Data Class）的描述方法。類不僅可以完整地說明數(shù)據(jù)的結(jié)構(gòu)，而且通過類的封裝機(jī)制能有效地保護(hù)數(shù)據(jù)，降低數(shù)據(jù)結(jié)構(gòu)的界面復(fù)雜度，并使得數(shù)據(jù)結(jié)構(gòu)能以開發(fā)者易用的形式被使用。更為重要的是，類還包含了對所描述的數(shù)據(jù)結(jié)構(gòu)的一系列操作，使得數(shù)據(jù)結(jié)構(gòu)及其操作運算完美地結(jié)合在一起。