1.2　數據結構概述

1.2.1　數據結構及其數據運算的概念

早期的計算機主要用于數值計算，20世紀70年代出現微處理機后，計算機被大量用于信息處理，計算機的應用領域被拓寬。90年代計算機網絡日益普及，發展至今已成為集計算、數據處理、數據傳輸于一體的信息處理系統，并且廣泛應用于工業領域。現代計算機軟件強調的是數據管理，數據結構則是數據管理的前提。

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

首先介紹與數據結構相關的概念和技術術語。

1.數據

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

2.數據元素

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

3.數據項

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

4.數據類型

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

5.數據對象

數據對象是性質相同的數據元素的集合，是數據的一個子集。例如，所有的字母構成的集合C=（'A'，'B'，…，'Z'）是一個字母數據對象；在產品質量檔案管理系統中由某類產品構成的集合是一個產品數據對象，如傳動結構對象中就包含了主動軸和從動軸等零件。

6.數據結構

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

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

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

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

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

總之，無論怎樣定義數據結構，都應將該數據的邏輯結構、數據的存儲結構及數據的運算這三方面看成一個整體，要體現它們之間的聯系。

在計算機發展的早期，計算機主要用于科學計算，處理的是數值數據。當時的數據特點是：數據元素之間的關系簡單、數據量小、形式較為一致。因此，程序設計人員更加注重的是算法，而不注重對數據的組織、性質、關系的研究。

隨著計算機產業的飛速發展和計算機應用的日益普及，計算機已越來越廣泛地應用于各種非數值處理問題，其應用已逐步深入事務管理、工業控制、公共通信、教育和軍事等領域。待處理的數據形式多樣，數量越來越大，關系越來越復雜。要想對這些數據進行快速有效的處理，就必須了解數據的性質、組織方式和相互之間的關系。這樣才能采用適當的方式進行存儲，選用高效的算法進行處理。這正是數據結構所要研究的內容。也就是說，數據結構是一門對計算機所處理的數據的表示、組織和操作進行系統研究的學科。

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

程序=數據結構+算法

這一公式揭示了數據結構和算法之間的天然聯系。

數據結構往往是與施加于其上的運算密切相關的。數據按一定的邏輯結構組織起來，再把數據結構用適當的存儲方式存儲到計算機中，其目的就是實現運算過程和提高數據的運算效率，從而更有效地處理數據。各種邏輯結構有其相應的運算，即每種邏輯結構有一個運算的集合。數據的運算是定義在數據的邏輯結構上的，運算的具體實現要在存儲結構上進行。對于數據本身而言，有各種具體的數學運算；對于各類數據結構而言，它們在基本運算方面是相似的。最常用的運算有：

①插入：其含義是在數據結構中增加新的結點。

②刪除：其含義是把指定的結點從數據結構中去除。

③更新：其含義是改變指定結點的值或改變指定的某些結點之間的關系。

④查找：其含義是在數據結構中查找滿足一定條件的結點。

⑤排序：其含義是對數據結構中各個結點按指定數據項的值以升序或降序重新排列。

針對數據結構的復雜運算過程可以是以上各種基本操作的組合。

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