1.2.4 數據的邏輯結構

數據的邏輯結構是從邏輯關系（主要是指相鄰關系）上描述數據的，它與數據的存儲無關，是獨立于計算機的。因此，數據的邏輯結構可以看作是從具體問題抽象出來的數學模型。在不會產生混淆的前提下，常將數據的邏輯結構簡稱為數據結構。數據的邏輯結構主要分為以下幾類。

1. 集合

集合是指數據元素之間除了“同屬于一個集合”的關系，別無其他關系。

2. 線性結構

線性結構是指該結構中的結點之間存在一對一的關系，其特點是開始結點和終端結點都是唯一的。除了開始結點和終端結點，其余結點都有且僅有一個直接前驅，有且僅有一個直接后繼。順序表就是一種典型的線性結構。

3. 樹形結構

樹形結構是指該結構中結點之間存在一對多的關系，其特點是每個結點最多只有一個直接前驅，但可以有多個直接后繼，可以有多個終端結點。二叉樹就是一種典型的樹形結構。

4. 圖形結構

圖形結構或稱為網狀結構，是指該結構中的結點之間存在多對多的關系，其特點是每個結點的直接前驅和直接后繼的個數都可以是任意的。因此，圖形結構可能沒有開始結點和終端結點，也可能有多個開始結點和多個終端結點。

樹形結構和圖形結構統稱為非線性結構，該結構中的結點之間存在一對多或多對多的關系。由線性結構、樹形結構和圖形結構的定義可知，線性結構是樹形結構的特殊情況，而樹形結構又是圖形結構的特殊情況，以上各類結構對應的示例如圖1-2所示。

例1-2　有數據結構B₁=(D, R)，其中：

D = {a, b, c, d, e, f, g, h, i, j}

R = {r}

r = {(a, b), (a, c), (a, d), (b, e), (c, f), (c, g), (d, h), (d, i), (d, j)}

畫出其邏輯結構。

解　對應B₁的邏輯結構如圖1-3所示。從該例中可以看出，每個結點有且僅有一個直接前驅（除根結點外），但有多個直接后繼（葉子結點可看作具有0個直接后繼）。這種數據結構的特點是數據元素之間的關系為一對多關系，即層次關系，因此是一種樹形結構。

例1-3　有數據結構B₂=(D, R)，其中：

D = {a, b, c, d, e}

R = {r}

r = {(a, b), (a, c), (b, c), (c, d), (c, e), (d, e)}

畫出其邏輯結構。

解　對應B₂的邏輯結構如圖1-4所示。從該例中看出，每個結點可以有多個直接前驅和多個直接后繼。這種數據結構的特點是數據元素之間的關系為多對多關系，即圖形關系，因此是一種圖形結構。