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

邏輯結(jié)構(gòu)反映的是數(shù)據(jù)元素之間的關(guān)系，它們與數(shù)據(jù)元素在計(jì)算機(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ù)元素都屬于這個(gè)集合，但數(shù)據(jù)元素之間并沒有什么關(guān)系。它類似于數(shù)學(xué)中的集合，如圖所示。

集合

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

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

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

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

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

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

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

圖形結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系，每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)都可以是任意個(gè)，如圖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ù)元素在計(jì)算機(jī)中的存儲形式，如何在計(jì)算機(jī)中正確地描述數(shù)據(jù)元素之間的邏輯關(guān)系，才是數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵與重點(diǎ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é)點(diǎn)存儲在地址連續(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ù)時(shí)，系統(tǒng)為數(shù)據(jù)元素分配一段連續(xù)的地址空間。順序存儲結(jié)構(gòu)可以提高空間利用率，而且對于隨機(jī)訪問元素，其效率非常高，因?yàn)檫壿嬌舷噜彽臄?shù)據(jù)元素，其存儲地址也是緊鄰的，所以可以按元素序號來快速查找到某一個(gè)元素。

但也正因如此，如果要對順序存儲結(jié)構(gòu)實(shí)現(xiàn)元素的插入和刪除，效率則非常低。因?yàn)槿绻迦胍粋€(gè)元素，需要將這個(gè)位置之后的所有元素都向后移動一個(gè)位置；同樣，如果要?jiǎng)h除一個(gè)元素，需要將這個(gè)位置之后的所有元素都向前移動一個(gè)位置。

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

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

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

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

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

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

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

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

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

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

稀疏索引

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

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

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

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