1.3　數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)的主要任務(wù)就是通過分析數(shù)據(jù)對象的結(jié)構(gòu)特征，包括邏輯結(jié)構(gòu)及數(shù)據(jù)對象之間的關(guān)系，并把邏輯結(jié)構(gòu)表示成計算機(jī)可實現(xiàn)的物理結(jié)構(gòu)，以便設(shè)計、實現(xiàn)算法。

1.3.1　邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)（Logical Structure）是指在數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系。數(shù)據(jù)元素之間存在不同的邏輯關(guān)系，構(gòu)成了以下4種結(jié)構(gòu)類型。

（1）集合結(jié)構(gòu)。集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個集合外，數(shù)據(jù)元素之間沒有其他關(guān)系。這就像數(shù)學(xué)中的自然數(shù)集合，集合中的所有元素都屬于該集合，除此之外，沒有其他特性。例如，數(shù)學(xué)中的正整數(shù)集合{5,67,978,20,123,18}，集合中的數(shù)除了屬于正整數(shù)外，元素之間沒有其他關(guān)系。數(shù)據(jù)結(jié)構(gòu)中的集合關(guān)系就類似于數(shù)學(xué)中的集合。集合結(jié)構(gòu)如圖1-5所示。

（2）線性結(jié)構(gòu)。線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系。線性結(jié)構(gòu)如圖1-6所示。數(shù)據(jù)元素之間存在先后次序關(guān)系，其中，a是b的直接前驅(qū)，b是a的直接后繼。

（3）樹形結(jié)構(gòu)。樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系。樹形結(jié)構(gòu)如圖1-7所示。這就像學(xué)校的組織結(jié)構(gòu)圖，學(xué)校下面是教學(xué)的院系、行政機(jī)構(gòu)及一些研究所。

（4）圖結(jié)構(gòu)。圖結(jié)構(gòu)中的數(shù)據(jù)元素是多對多的關(guān)系。如圖1-8所示就是一個圖結(jié)構(gòu)。城市之間的交通路線圖就是多對多的關(guān)系，a、b、c、d、e、f、g是7個城市，城市a到城市b、e、f都存在一條直達(dá)路線，而城市b到城市a、c、f也存在一條直達(dá)路線。

1.3.2　存儲結(jié)構(gòu)

存儲結(jié)構(gòu)（Storage Structure）也稱為物理結(jié)構(gòu)（Physical Structure），指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的存儲形式。數(shù)據(jù)的存儲結(jié)構(gòu)應(yīng)能正確反映數(shù)據(jù)元素之間的邏輯關(guān)系。

數(shù)據(jù)元素的存儲結(jié)構(gòu)形式通常有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種。順序存儲是把數(shù)據(jù)元素存放在一組地址連續(xù)的存儲單元里，其數(shù)據(jù)元素間的邏輯關(guān)系和物理關(guān)系是一致的。采用順序存儲的字符串“abcdef”地址連續(xù)的存儲結(jié)構(gòu)如圖1-9所示。鏈?zhǔn)酱鎯κ前褦?shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，數(shù)據(jù)元素的存儲關(guān)系并不能反映其邏輯關(guān)系，因此需要借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。字符串“abcdef”的鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖1-10所示。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過程中，你將會發(fā)現(xiàn)，任何一個算法的設(shè)計取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實現(xiàn)則依賴于所采用的存儲結(jié)構(gòu)。

如何描述存儲結(jié)構(gòu)呢？通常是借助Java、C、C++、Python等高級程序設(shè)計語言中提供的數(shù)據(jù)類型進(jìn)行描述的。例如，對于數(shù)據(jù)結(jié)構(gòu)中的順序表，可以用Java語言中的數(shù)組來表示；對于鏈表，可以用Java語言中的類進(jìn)行描述，通過引用類型記錄元素之間的邏輯關(guān)系。