1.1 數據結構概述

數據結構是指所有數據及這些數據之間的關系的集合。對于計算機而言，數據是指能被輸入到計算機中并能被其處理的符號的集合。在使用計算機解決科學計算問題時，通常按以下步驟進行。

（1）分析問題，確定數學模型。

（2）根據模型設計相應的算法。

（3）選擇合適的編程語言實現算法。

（4）調試程序，直到正確解決問題。

但對于設計類似網上訂餐和網上購物的程序，其中有很多問題是很難找到與之對應的數學模型的。這時，第一步需分析程序中所要處理的數據，第二步需根據實際應用判斷這些數據之間存在的邏輯關系，第三步需結合在實際應用中操作這些數據的頻度來確定其整體的組織結構。通過以上3步便能夠確定數據的邏輯結構。最后通過采取一定地策略將數據的邏輯結構在計算機中表示出來，從而對數據進行一系列的操作。

1.1.1 什么是數據結構

數據結構的概念最早由C.A.R.Hoare和N.Wirth在1966年提出，大量關于程序設計理論的研究表明：想要對大型復雜程序的構造進行系統而科學的研究，必須首先對這些程序中所包含的數據結構進行深入的研究。

本小節將對數據結構中的一些基本概念和術語加以定義和解釋，以便于讀者在后續章節中更好地學習。

數據通常用于描述客觀事物，例如，在日常生活中使用的各種文字、數字和特定符號都是數據。而在計算機中，數據是指所有能夠輸入到計算機中存儲并被計算機程序處理的符號的集合，因此對計算機科學而言，數據的含義極為廣泛，如聲音、圖像和視頻等被編碼后都屬于數據的范疇。

數據元素是數據的基本單位，在計算機程序中通常將其作為一個整體進行考慮和處理。在某些情況下，我們也將數據元素稱為元素、結點或記錄等。例如，如果我們以學號、性別和姓名來標識某個學生，那么由學號、性別和姓名組成的記錄將構成一個數據元素；而從另一方面來看，某一學生的學號、性別或姓名也可以被認為是一個數據元素。

數據項是構成數據元素的不可分割的最小單位，也被稱為字段、域或屬性，例如，對于上述學生記錄中的學號、性別和姓名而言，其中任意一項都可以被稱為數據項。

數據對象是性質相同的數據元素的集合，是數據的一個子集，例如，整數的數據對象是集合N={0,±1, ±2, …}，英文字母的數據對象是集合C={‘a’, ‘A’, ‘b’, ‘B’, …}。

數據結構是相互之間存在一種或多種特定關系的數據元素的集合，通常這些數據元素都不是孤立存在的，而是通過某種關系將所有數據元素聯系起來，我們將這種關系稱為結構。數據結構通常包括數據的邏輯結構和存儲結構兩個層次，后面將對其進行詳細介紹。

1.1.2 數據的邏輯結構

數據的邏輯結構是從數據元素的邏輯關系上抽象描述數據，通常是從求解問題中提煉出來的。數據的邏輯結構與數據的存儲無關，是獨立于計算機的，因此數據的邏輯結構可以被看作是從具體問題中抽象出來的數學模型。

數據元素之間的邏輯結構是多種多樣的，根據數據元素之間的不同關系特性，通常可將數據邏輯結構分為4類，即集合、線性結構、樹形結構和圖狀（或網狀）結構，具體如圖1-1所示。

下面每種邏輯結構中的示例均以某校高三年級1班的學生作為數據對象，并以該班學生的某些信息作為數據元素。其中，部分學生的學號、姓名、性別和班級編號如表1-1所示。

（1）集合：如圖1-1（a）所示，該結構中的數據元素除了屬于同一集合以外，兩兩之間并無其他關系。例如，確定某個學生是否屬于本班級，此時需要將班級看作一個集合。

（2）線性結構：如圖1-1（b）所示，該結構中的數據元素之間存在一對一的邏輯關系，并且起始元素和終端元素都是唯一的，除了這兩個元素外，剩余的每一個元素都有且僅有一個在其之前和在其之后的元素。例如，將表1-1中的學號按照從小到大順序進行排列，可以得到一個線性結構的序列{1501, 1502, 1503, 1504, 1505, 1506, 1507}。

（3）樹形結構：如圖1-1（c）所示，該結構中的數據元素之間存在一對多的邏輯關系，并且除了起始元素外，其余每一個元素都有且僅有一個在其之前的元素，除了終端元素外，其余每一個元素都有一個或多個在其之后的元素。例如，在班級中只有一個班長，班長對各個組長進行管理，而各個組長則管理自己組內的成員（即組員），由此形成一個樹形結構，如圖1-2所示。

（4）圖狀（或網狀）結構：如圖1-1（d）所示，該結構中的數據元素之間存在多對多的邏輯關系，每個元素都可能有一個或多個在其之前或在其之后的元素。在這一結構中可能沒有起始元素和終端元素，也可能有多個起始元素和多個終端元素。例如，在班級中任意兩個同學都有可能是朋友，從而形成圖狀（或網狀）結構，如圖1-3所示。

集合、樹形結構和圖狀（或網狀）結構都不屬于線性結構，通常我們將其稱為非線性結構。

1.1.3 數據的存儲結構

數據的存儲結構是指數據在計算機中的表示（又稱為映像）方法，是數據的邏輯結構在計算機中的存儲實現，因此在存儲時應包含兩方面的內容——數據元素本身及數據元素之間的關系。在實際應用中，數據有各種各樣的存儲方法，對其進行總結后，可大致劃分為以下4類。

1．順序存儲結構

順序存儲結構是指采用一組物理上連續的存儲單元來依次存放所有的數據元素，如圖1-4所示。在這一存儲結構中，邏輯上相鄰地兩個數據元素的存儲地址也相鄰，因此我們只需要存儲數據元素，而不需要存儲這些數據元素之間的關系，因為它們的關系可以由存儲單元地址間的關系來間接表示。

順序存儲結構將數據元素的邏輯結構直接映射到存儲結構上，這十分有利于實現對數據元素的隨機存取，但由于該結構要求存儲單元在物理上是連續的，因此在進行數據元素的插入及刪除等操作時，可能需要移動一系列的數據元素。

2．鏈式存儲結構

在鏈式存儲結構中，每一數據元素均使用一個結點來存儲，并且每個結點的存儲空間是單獨分配的，因此存儲這些結點的空間不一定是連續的。

在鏈式存儲結構中，我們不僅需要存儲數據元素本身，還需要存儲數據元素之間的邏輯關系，即將結點分為兩部分，一部分是存儲數據元素本身的，我們稱其為數據域；另一部分是存儲下一個結點的地址（即存儲邏輯關系）的，我們稱其為指針域。通過將每一個結點的指針域鏈接起來，從而形成鏈式存儲結構。

在鏈式存儲結構中插入或刪除數據元素時，可以直接通過修改指針域中的地址來實現，而不必移動大量結點。因為鏈式存儲結構需要使用指針表明數據元素之間的邏輯關系，所以存儲空間的利用率較低，并且由于結點的物理地址不一定是相鄰的，因此只能通過結點的指針域找到存儲的數據元素，而不能對數據元素進行隨機存取。

圖1-5（a）所示為采用鏈式存儲結構存儲數據元素的普遍形式，為了讓讀者更好地理解鏈式存儲結構，在后續章節中描述鏈式存儲結構時，我們均采用圖1-5（b）所示的常用形式。

3．索引存儲結構

在索引存儲結構中，不僅需要存儲所有數據元素（稱之為主數據表），還需要建立附加的索引表。在存儲時，每個數據元素都由一個唯一的關鍵字來標識，由該關鍵字和對應的數據元素的地址構成一個索引項，并將其存入索引表中。通常索引表中的所有索引項是按關鍵字有序排列的，在查找數據元素時，首先由關鍵字的有序性，在索引表中查找出關鍵字所在的索引項，并取出該索引項中的地址，再依據此地址在主數據表中找到對應的數據元素。

由于借助索引表可以通過關鍵字快速地定位到數據元素，因此索引存儲結構的查找效率很高，但索引表需要額外的空間進行存儲，導致存儲空間的利用率較低。

4．哈希（或散列）存儲結構

哈希（或散列）存儲結構是指依據數據元素的關鍵字，通過事先設計好的哈希（或散列）函數計算出一個值，再將其作為該數據元素的存儲地址，因此使用哈希（或散列）存儲結構也可以實現快速地查找，并且在采用哈希（或散列）存儲結構時，只需要存儲數據元素，而不需要存儲數據元素之間的關系。

上述4種存儲結構既可以單獨使用也可以組合使用，確定了邏輯結構后，采用何種存儲結構要視具體問題而定，通常需要考慮的是操作的方便性、效率，以及對時間和空間的要求。