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

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

1）集合

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

集合

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

線性結(jié)構(gòu)中的元素具有一對(duì)一的關(guān)系，通過(guò)前一個(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)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種。

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

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

樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在一對(duì)多的層次關(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ù)元素存在多對(duì)多的關(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í)中，本書會(huì)逐一詳細(xì)講解。

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

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

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

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

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

使用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)時(shí)，系統(tǒng)為數(shù)據(jù)元素分配一段連續(xù)的地址空間。順序存儲(chǔ)結(jié)構(gòu)可以提高空間利用率，而且對(duì)于隨機(jī)訪問(wèn)元素，其效率非常高，因?yàn)檫壿嬌舷噜彽臄?shù)據(jù)元素，其存儲(chǔ)地址也是緊鄰的，所以可以按元素序號(hào)來(lái)快速查找到某一個(gè)元素。

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

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

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

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

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

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

對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)而言，空間利用率也較低，因?yàn)榉峙涞膬?nèi)存單元有一部分被用來(lái)存儲(chǔ)結(jié)點(diǎn)之間的邏輯關(guān)系。但鏈?zhǔn)酱鎯?chǔ)在存儲(chǔ)元素時(shí)沒(méi)有空間限制，順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)都是按需分配，只是鏈?zhǔn)酱鎯?chǔ)可以在需要時(shí)方便地分配新空間，不會(huì)造成空間不足或者浪費(fèi)。

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

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

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

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

稀疏索引

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

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

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

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