如何描述元素與元素間的邏輯關系？

邏輯結構反映的是數據元素之間的關系，它們與數據元素在計算機中的存儲位置無關，是數據結構在用戶面前所呈現(xiàn)的形式。根據不同的邏輯結構來分，數據結構可分為集合、線性結構、樹形結構和圖形結構4種形式，接下來分別進行簡要介紹。

1）集合

在集合中，數據元素都屬于這個集合，但數據元素之間并沒有什么關系。它類似于數學中的集合，如圖所示。

集合

2）線性結構

線性結構中的元素具有一對一的關系，通過前一個結點可以找到后一個結點，圖1-1的學生信息表就是一個線性結構，數據元素逐個排列。線性結構中前后兩個結點互有聯(lián)系。

線性結構分為順序存儲和鏈式存儲兩種。

在線性結構中，除頭尾結點外，可以通過前一個結點來尋找后一個結點，也可以通過后一個結點來尋找前一個結點。

3）樹形結構

樹形結構中，數據元素之間存在一對多的層次關系。圖1-4為一棵普通的樹。除根結點外，樹形結構的每一個結點都必須有一個且只有一個前驅結點，但可以有任意個后繼結點。這些數據元素有自頂向下的層次關系。

4）圖形結構

圖形結構中的數據元素存在多對多的關系，每個結點的前驅和后繼結點都可以是任意個，如圖1-5所示。

按照邏輯結構，數據結構可以分為上述4種類型，在后續(xù)的深入學習中，本書會逐一詳細講解。

2.存儲結構

數據結構除了按照邏輯結構來分，還可以按照存儲結構來分。

存儲結構反映的是數據元素在計算機中的存儲形式，如何在計算機中正確地描述數據元素之間的邏輯關系，才是數據結構的關鍵與重點。常用的存儲結構有順序存儲結構、鏈式存儲結構、索引存儲結構和散列表4種，接下來分別進行簡要介紹。

1）順序存儲結構

順序存儲結構是把邏輯上相鄰的結點存儲在地址連續(xù)的存儲單元里，數據元素之間的關系由存儲單元是否相鄰來體現(xiàn)。這種存儲結構通常用高級語言上的數組來描述，數據的邏輯關系與物理關系是一致的。以數組inta[5]={100，20，3，56，266}為例，其中的元素a[0]~a[4]在邏輯上是連續(xù)的，在存儲器中的物理地址也是連續(xù)的，如圖1-6所示。

使用順序存儲結構存儲數據時，系統(tǒng)為數據元素分配一段連續(xù)的地址空間。順序存儲結構可以提高空間利用率，而且對于隨機訪問元素，其效率非常高，因為邏輯上相鄰的數據元素，其存儲地址也是緊鄰的，所以可以按元素序號來快速查找到某一個元素。

但也正因如此，如果要對順序存儲結構實現(xiàn)元素的插入和刪除，效率則非常低。因為如果要插入一個元素，需要將這個位置之后的所有元素都向后移動一個位置；同樣，如果要刪除一個元素，需要將這個位置之后的所有元素都向前移動一個位置。

順序存儲結構在使用時有空間限制，當需要存取元素的個數多于預先分配的空間時，會出現(xiàn)“溢出”問題；當元素個數少于預先分配的空間時，又會造成空間浪費。

2）鏈式存儲結構

鏈式存儲結構在空間上是一些不連續(xù)的存儲單元，這些存儲單元的邏輯關系通過附加的指針字段來表示，例如C/C++語言中的指針類型，通過這些指針的指向來表明結點之間的聯(lián)系。圖1-3（b）為鏈式存儲結構的示意圖，但在此圖中沒有標明指針的指向。在鏈式存儲結構中，可以有指向后繼元素的指針字段，也可以有指向前驅元素的指針字段，如圖1-7和圖1-8所示。

這樣在插入元素時不必移動任何一個元素，高效簡潔。同理，當刪除某一個元素時，只需將其前后兩個元素連接起來即可，也無須移動其他元素。

但鏈式存儲結構無法進行元素的隨機訪問。

對鏈式存儲結構而言，空間利用率也較低，因為分配的內存單元有一部分被用來存儲結點之間的邏輯關系。但鏈式存儲在存儲元素時沒有空間限制，順序存儲與鏈式存儲都是按需分配，只是鏈式存儲可以在需要時方便地分配新空間，不會造成空間不足或者浪費。

3）索引存儲結構

這種存儲結構主要是為了方便查找數據，它通常是在存儲結點信息的同時，還建立附加的索引表。索引表中的每一項稱為索引項，它由兩個字段組成：關鍵字與地址。其中關鍵字唯一標識一個結點，地址是指向結點的指針。這種結構類似于人們常用的字典，如圖所示。

索引存儲結構

這種索引表一個索引項對應一個結點，叫作稠密索引。如果索引表中一個索引項對應一組結點，叫作稀疏索引，稀疏索引表如圖1-11所示。

稀疏索引

索引表可以快速地對數據進行隨機訪問。又因為在進行數據的插入和刪除時，只需要更改索引表中的地址值，不必移動結點，所以在數據更改方面也具有較高的效率。但是索引存儲結構在建立結點時會額外分配空間來建立一個索引表，因此降低了空間利用率。

4）散列存儲結構

散列（hash）存儲又稱為哈希存儲，是一種力圖將數據元素的存儲位置與關鍵字之間建立確定對應關系的查找技術。它的基本思想是通過一定的函數關系（散列函數，也稱為哈希函數）計算出一個值，將這個值作為元素的存儲地址。

散列存儲的訪問速度是非常迅速的，只要給出相應結點的關鍵字，它會立即計算出該結點的存儲地址。因此它是一種非常重要的存儲方法。數據存儲的幾種方式各有其優(yōu)點，也各有其用途，不能說哪一種存儲結構就比另一種好。在使用時，它們既可以單獨使用，也可以組合起來使用，具體要根據操作和實際情況來決定采取哪一種方式，或者哪幾種方式結合使用。