1.2　基本概念和術語

1.2.1　基本概念

1．數據

數據是可被計算機識別并加工處理的對象。數據不僅包括整型、實型等數值數據，還包括聲音、圖像、視頻等非數值數據。例如，MP3格式的文件是常見的音頻聲音數據，BMP格式的文件是典型的圖像數據，RMVB格式的文件是視頻數據。

2．數據元素

數據元素是由數據組成的具有一定意義的基本單位，在計算機中通常作為一個整體來處理。有些情況下，數據元素也稱為元素、記錄。

3．數據項

數據項是組成數據元素的、不可分割的最小單位。

表1.1為學生信息表，其中每個學生的信息可看作一個數據元素，它由學號、姓名、性別、籍貫等數據項組成。

表1.1　學生信息表

1.2.2　數據結構

數據結構（Data Structure）是由某一數據對象及該對象中所有數據元素之間的關系組成的。數據結構包括數據的邏輯結構、存儲結構及數據的運算三方面的內容。接下來從這三方面分別闡述。

1．數據的邏輯結構

數據的邏輯結構是從邏輯關系上描述數據。數據的邏輯結構僅考慮數據之間的內在關系，是面向應用問題的，它是獨立于計算機的。根據數據結構中數據元素之間關系的不同特征，可劃分為四種基本邏輯結構，如圖1.2所示。

（1）線性結構

線性結構中數據元素之間存在一對一的關系。例如，表1.1所示的學生信息表可看成一個線性結構，學生信息按照學號依次排列。

（2）樹形結構

樹形結構中數據元素之間存在一對多的關系。例如，一所學校有多個學院，一個學院有多個專業，構成樹形結構。

（3）圖結構

圖結構中數據元素之間存在多對多的關系。例如，微信朋友圈中，“我”的朋友們彼此之間可能是相識關系，也可能是不相識關系，他們之間存在多對多的朋友關系，從而構成圖結構。

圖1.2　四種基本的邏輯結構示例

（4）集合結構

數據元素之間除了“屬于同一個集合”的聯系之外沒有其他關系。例如，學生存在于某個班級中，若不考慮學生之間的其他關系，則可視班級為一個集合結構。

以上四種基本的邏輯結構還可進一步分成兩類：線性結構和非線性結構。除了線性結構以外，樹形、圖和集合結構可統一歸入非線性結構一類。

2．數據的存儲結構

數據的存儲結構是數據及數據之間的關系在計算機內的表示形式。它是面向計算機的，是數據的邏輯結構在計算機存儲中的影像。數據的存儲結構中，最常見的兩種基本存儲結構分別是順序存儲結構和鏈式存儲結構。

（1）順序存儲結構

順序存儲結構是將邏輯上相關的數據元素依次存儲在地址連續的存儲空間中。這種存儲結構是借助數據元素在存儲空間中的相對位置來表示它們之間的邏輯關系。假定有一線性結構的數據（a0,a1,a2），每個元素占2個存儲單元，連續存儲空間的起始地址是100，則其順序存儲表示如圖1.3（a）所示。

順序表示方法并不僅限于存儲線性結構的數據。例如，樹形結構的數據對象有時也可采用順序存儲的方法表示。這將在以后章節中詳細闡述。

（2）鏈式存儲結構

鏈式存儲結構中，數據元素可以存儲在任意的存儲空間中，可以是連續的存儲空間，也可以是不連續的存儲空間。在這種情況下，數據元素的存儲位置并不能體現它們之間的邏輯關系，需要用指針域存儲邏輯上相關的數據元素的地址。因此，為了存儲一個元素，需要存放數據元素本身和與該元素邏輯上相關的其他元素的地址，這兩部分信息組成一個結點。

假定有一線性結構的數據（a0,a1,a2），其鏈式存儲表示如圖1.3（b）所示。其中，每個結點存儲了數據元素和該元素邏輯上的后繼結點的地址。注意：一個結點的存儲地址通常是指存放該結點的存儲塊的起始存儲單元地址。

圖1.3　兩種基本的存儲表示方法

在此約定，在不會引起混淆的場合，本書將不明確區分結點和元素這兩個術語。但必要時，將包括數據元素和地址在內的整個存儲塊稱為結點，而將其中的數據元素稱為該結點的元素。

3．數據的運算

如果說數據的邏輯結構描述了數據的靜態特性，那么在數據的邏輯結構上定義的一組運算給出了數據被使用的方式，即數據的動態特性。使用數據結構上定義的運算，用戶可對數據結構的實例或組成實例的數據元素實施相應的操作。運算的結果可使數據改變狀態。

數據結構最常見的運算有：

（1）搜索運算——在數據結構中搜索滿足一定條件的元素；

（2）插入運算——在數據結構中插入新元素；

（3）刪除運算——將數據結構中指定元素刪除；

（4）更新運算——將數據結構中指定元素更新為新的元素。