如何描述元素與元素間的邏輯關(guān)系？

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

1）集合

在集合中，數(shù)據(jù)元素都屬于這個集合，但數(shù)據(jù)元素之間并沒有什么關(guān)系。它類似于數(shù)學(xué)中的集合，如圖所示。

集合

2）線性結(jié)構(gòu)

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

線性結(jié)構(gòu)分為順序存儲和鏈?zhǔn)酱鎯煞N。

在線性結(jié)構(gòu)中，除頭尾結(jié)點外，可以通過前一個結(jié)點來尋找后一個結(jié)點，也可以通過后一個結(jié)點來尋找前一個結(jié)點。

3）樹形結(jié)構(gòu)

樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在一對多的層次關(guān)系。圖1-4為一棵普通的樹。除根結(jié)點外，樹形結(jié)構(gòu)的每一個結(jié)點都必須有一個且只有一個前驅(qū)結(jié)點，但可以有任意個后繼結(jié)點。這些數(shù)據(jù)元素有自頂向下的層次關(guān)系。

4）圖形結(jié)構(gòu)

圖形結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系，每個結(jié)點的前驅(qū)和后繼結(jié)點都可以是任意個，如圖1-5所示。

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

2.存儲結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)除了按照邏輯結(jié)構(gòu)來分，還可以按照存儲結(jié)構(gòu)來分。

存儲結(jié)構(gòu)反映的是數(shù)據(jù)元素在計算機中的存儲形式，如何在計算機中正確地描述數(shù)據(jù)元素之間的邏輯關(guān)系，才是數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵與重點。常用的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲結(jié)構(gòu)和散列表4種，接下來分別進(jìn)行簡要介紹。

1）順序存儲結(jié)構(gòu)

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

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

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

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

2）鏈?zhǔn)酱鎯Y(jié)構(gòu)

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

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

但鏈?zhǔn)酱鎯Y(jié)構(gòu)無法進(jìn)行元素的隨機訪問。

對鏈?zhǔn)酱鎯Y(jié)構(gòu)而言，空間利用率也較低，因為分配的內(nèi)存單元有一部分被用來存儲結(jié)點之間的邏輯關(guān)系。但鏈?zhǔn)酱鎯υ诖鎯υ貢r沒有空間限制，順序存儲與鏈?zhǔn)酱鎯Χ际前葱璺峙?，只是鏈?zhǔn)酱鎯梢栽谛枰獣r方便地分配新空間，不會造成空間不足或者浪費。

3）索引存儲結(jié)構(gòu)

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

索引存儲結(jié)構(gòu)

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

稀疏索引

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

4）散列存儲結(jié)構(gòu)

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

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