1.2 基本概念和術語

下列概念和術語將在以后各章節(jié)中多次出現(xiàn)，本節(jié)先對這些概念和術語賦予確定的含義。

1.2.1 數據、數據元素、數據項和數據對象

數據（Data）是客觀事物的符號表示，是所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數學計算中用到的整數和實數，文本編輯中用到的字符串，多媒體程序處理的圖形、圖像、聲音及動畫等通過特殊編碼定義后的數據。

數據元素（Data Element）是數據的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數據元素也稱為元素、記錄等。數據元素用于完整地描述一個對象，如前一節(jié)示例中的一名學生記錄，樹中棋盤的一個格局（狀態(tài)），以及圖中的一個頂點等。

數據項（Data Item）是組成數據元素的、有獨立含義的、不可分割的最小單位。例如，學生基本信息表中的學號、姓名、性別等都是數據項。

數據對象（Data Object）是性質相同的數據元素的集合，是數據的一個子集。例如：整數數據對象是集合N={0，±1，±2，…}，字母字符數據對象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，學生基本信息表也可以是一個數據對象。由此可以看出，不論數據元素集合是無限集（如整數集），或是有限集（如字母字符集），還是由多個數據項組成的復合數據元素（如學生表）的集合，只要集合內元素的性質均相同，都可稱之為一個數據對象。

1.2.2 數據結構

數據結構（Data Structure）是相互之間存在一種或多種特定關系的數據元素的集合。換句話說，數據結構是帶“結構”的數據元素的集合，“結構”就是指數據元素之間存在的關系。

數據結構包括邏輯結構和存儲結構兩個層次。

1．邏輯結構

數據的邏輯結構是從邏輯關系上描述數據，它與數據的存儲無關，是獨立于計算機的。因此，數據的邏輯結構可以看作是從具體問題抽象出來的數學模型。

數據的邏輯結構有兩個要素：一是數據元素；二是關系。數據元素的含義如前所述，關系是指數據元素間的邏輯關系。根據數據元素之間關系的不同特性，通常有四類基本結構，如圖1.3所示。它們的復雜程度依次遞進。

下面四種結構中所舉的示例是以某班級學生作為數據對象（數據元素是學生的學籍檔案記錄），來分別考察數據元素之間的關系。

（1）集合結構

數據元素之間除了“屬于同一集合”的關系外，別無其他關系。例如，確定一名學生是否為班級成員，只需將班級看做一個集合結構。

（2）線性結構

數據元素之間存在一對一的關系。例如，將學生信息數據按照其入學報到的時間先后順序進行排列，將組成一個線性結構。

（3）樹結構

數據元素之間存在一對多的關系。例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構成樹形結構。

（4）圖結構或網狀結構

數據元素之間存在多對多的關系。例如，多位同學之間的朋友關系，任何兩位同學都可以是朋友，從而構成圖狀結構或網狀結構。

其中集合結構、樹結構和圖結構都屬于非線性結構。

線性結構包括線性表（典型的線性結構，如例1.1中的學生基本信息表）、棧和隊列（具有特殊限制的線性表，數據操作只能在表的一端或兩端進行）、字符串（也是特殊的線性表，其特殊性表現(xiàn)在它的數據元素僅由一個字符組成）、數組（是線性表的推廣，它的數據元素是一個線性表）、廣義表（也是線性表的推廣，它的數據元素是一個線性表，但不同構，即或者是單元素，或者是線性表）。非線性結構包括樹（具有多個分支的層次結構）和二叉樹（具有兩個分支的層次結構）、有向圖（一種圖結構，邊是頂點的有序對）和無向圖（另一種圖結構，邊是頂點的無序對）。這幾種邏輯結構可以用一個層次圖描述，如圖1.4所示。

2．存儲結構

數據對象在計算機中的存儲表示稱為數據的存儲結構，也稱為物理結構。把數據對象存儲到計算機時，通常要求既要存儲各數據元素的數據，又要存儲數據元素之間的邏輯關系，數據元素在計算機內用一個結點來表示。數據元素在計算機中有兩種基本的存儲結構，分別是順序存儲結構和鏈式存儲結構。

（1）順序存儲結構

順序存儲結構是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系，通常借助程序設計語言的數組類型來描述。

對于前面的“學生基本信息表”，假定每個結點（學生記錄）占用50個存儲單元，數據從0號單元開始由低地址向高地址方向存儲，對應的順序存儲結構如表1.2所示。

（2）鏈式存儲結構

順序存儲結構要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈式存儲結構，無需占用一整塊存儲空間。但為了表示結點之間的關系，需要給每個結點附加指針字段，用于存放后繼元素的存儲地址。所以鏈式存儲結構通常借助于程序設計語言的指針類型來描述。

假定給前面的“學生基本信息表”中的每個結點附加一個“下一個結點地址”，即后繼指針字段，用于存放后繼結點的首地址，則可得到如表1.3所示的鏈式存儲結構。從表中可以看出，每個結點占用兩個連續(xù)的存儲單元，一個存放結點的信息，另一個存放后繼結點的首地址。

為了更清楚地反映鏈式存儲結構，可采用更直觀的圖示來表示，如“學生基本信息表”的鏈式存儲結構可用如圖1.5所示的方式表示。

1.2.3 數據類型和抽象數據類型

1．數據類型

數據類型（Data Type）是高級程序設計語言中的一個基本概念，前面提到過順序存儲結構可以借助程序設計語言的數組類型描述，鏈式存儲結構可以借助指針類型描述，所以數據類型和數據結構的概念密切相關。

一方面，在程序設計語言中，每一個數據都屬于某種數據類型。類型明顯或隱含地規(guī)定了數據的取值范圍、存儲方式以及允許進行的運算，數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。例如，C語言中的整型變量，其值集為某個區(qū)間上的整數（區(qū)間大小依賴于不同的機器），定義在其上的操作為加、減、乘、除和取模等算術運算；而實型變量也有自己的取值范圍和相應運算，比如取模運算是不能用于實型變量的。程序設計語言允許用戶直接使用的數據類型由具體語言決定，數據類型反映了程序設計語言的數據描述和處理能力。C語言除了提供整型、實型、字符型等基本類型數據外，還允許用戶自定義各種類型數據，例如數組、結構體和指針等。

2．抽象數據類型

抽象就是抽取出實際問題的本質。在計算機中使用二進制數來表示數據，在匯編語言中則可給出各種數據的十進制表示，它們是二進制數據的抽象，使用者在編程時可以直接使用，不必考慮實現(xiàn)細節(jié)。在高級語言中，則給出更高一級的數據抽象，出現(xiàn)了數據類型，如整型、實型、字符型等，可以進一步利用這些類型構造出線性表、棧、隊列、樹、圖等復雜的抽象數據類型。

抽象數據類型（Abstract Data Type，ADT）一般指由用戶定義的、表示應用問題的數學模型，以及定義在這個模型上的一組操作的總稱，具體包括三部分：數據對象、數據對象上關系的集合以及對數據對象的基本操作的集合。

抽象數據類型的定義格式如下：

ADT 抽象數據類型名{
   數據對象：〈數據對象的定義〉
   數據關系：〈數據關系的定義〉
   基本操作：〈基本操作的定義〉
}ADT 抽象數據類型名

其中，數據對象和數據關系的定義采用數學符號和自然語言描述，基本操作的定義格式為：

基本操作名（參數表）
   初始條件：〈初始條件描述〉
   操作結果：〈操作結果描述〉

基本操作有兩種參數：賦值參數只為操作提供輸入值；引用參數以“&”打頭，除可提供輸入值外，還將返回操作結果。“初始條件”描述了操作執(zhí)行之前數據結構和參數應滿足的條件，若初始條件為空，則省略。“操作結果”說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。