1.2.3 基本概念和術語

本小節將給出一些概念和術語的定義，這些概念和術語將多次出現在之后的章節中。

數據是人們利用文字符號、數字符號以及其他規定的符號對現實世界的事物及其活動所做的描述。在計算機中，它泛指所有能輸入計算機中并被計算機程序處理的符號。它是計算機程序加工的原料，文字、表格、聲音、圖像等都稱為數據。

數據元素是數據的基本單位，在程序中通常把數據元素作為一個整體進行考慮和處理。例如，表1-1所示的學生表中，如果把每行當作一個數據元素來處理，此表共包含7個數據元素。一個數據元素可由若干數據項組成，例如表1-1中每一個學生的信息作為數據元素，而學生信息的每一項（如學號、姓名等）都是數據項。數據的最小單位即數據項。

表1-1　學生表

數據結構是指數據及其之間的相互關系，可以看成相互之間存在一種或多種特定關系的數據元素的集合。因此，可以把數據結構看成帶結構的數據元素的集合。數據結構包括以下3個方面。

①數據元素之間的邏輯關系，即數據的邏輯結構。

②數據元素及其關系在計算機存儲系統中的存儲方式，即數據的存儲結構，也稱為數據的物理結構。

③施加在該數據上的操作，即數據的運算。

為了更準確地描述數據結構，通常采用二元組表示，表示方法為

B = (D, R)

其中，B是一種數據結構，它由數據元素的集合D和D中二元關系的集合R組成，即

D = {d_i| 1 ≤ i ≤ n, n ≥ 0}

R = {r_j | 1 ≤ j ≤ m, m ≥ 0}

其中，d_i表示集合D中的第i個結點或數據元素，n為D中結點的個數，特別地，若n=0，則D是一個空集，因而B也就無結構可言，有時把這種情況認為是具有任意結構。rj表示集合R中的第j個關系，m為R中關系的個數，特別地，若m=0，則R是一個空集，表明集合D中的結點間不存在任何關系，彼此是獨立的。

R中的一個關系r是序偶的集合，對于r中的任一序偶<x, y>(x, y∈D)，把x叫作序偶的第一結點，把y叫作序偶的第二結點，稱序偶的第一結點為第二結點的直接前驅，稱第二結點為第一結點的直接后繼。若某個結點沒有直接前驅，則稱該結點為開始結點；若某個結點沒有直接后繼，則稱該結點為終端結點。

數據類型是一個值的集合和定義在這個集合上的一組操作的總稱。例如，Java語言中的整型變量，其值集為某個區間上的整數，定義在其上的操作為加、減、乘、除和模運算等。按“值”的不同特性，高級程序設計語言中的數據類型可分為兩種：原子類型和結構類型。原子類型的值是不可分解的，例如Java語言中的基本類型（整型、布爾型等）；結構類型的值是若干成分按照某種結構組成的，因此是可以分解的，其組成成分既可以是結構的，也可以是非結構的。

抽象數據類型是指一個數學模型以及定義在該模型上的一組操作。抽象數據類型的定義僅取決于它的一組邏輯特性，而與其在計算機內的存儲形式無關，即不論其內部結構如何變化，只要它的邏輯特性不變，都不影響外部使用。

抽象數據類型的范疇十分廣，它不僅包括當前各處理器中已定義并實現的數據類型（固有類型），而且包括用戶在設計軟件時自定義的數據類型。本書定義抽象數據類型格式如下：

ADT 抽象數據類型名{
    數據對象：（數據對象定義）
    數據關系：（數據關系定義）
    數據操作：（數據操作定義）
}ADT 抽象數據類型名