數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型概念區(qū)別

數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型，這三個術(shù)語在字面上既不同又相近，反映出它們在含義上既有區(qū)別又有聯(lián)系。 

    數(shù)據(jù)結(jié)構(gòu)是在整個計算機科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由哪些成分數(shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)之間的邏輯關(guān)系，物理上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)在計算機內(nèi)的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。

     v數(shù)據(jù)是按照數(shù)據(jù)結(jié)構(gòu)分類的，具有相同數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)屬同一類。同一類數(shù)據(jù)的全體稱為一個數(shù)據(jù)類型。在程序設(shè)計高級語言中，數(shù)據(jù)類型用來說明一個數(shù)據(jù)在數(shù)據(jù)分類中的歸屬。它是數(shù)據(jù)的一種屬性。這個屬性限定了該數(shù)據(jù)的變化范圍。為了解題的需要，根據(jù)數(shù)據(jù)結(jié)構(gòu)的種類，高級語言定義了一系列的數(shù)據(jù)類型。不同的高級語言所定義的數(shù)據(jù)類型不盡相同。Pascal語言所定義的數(shù)據(jù)類型的種類如圖1-8所示。

    其中，簡單數(shù)據(jù)類型對應(yīng)于簡單的數(shù)據(jù)結(jié)構(gòu);構(gòu)造數(shù)據(jù)類型對應(yīng)于復(fù)雜的數(shù)據(jù)結(jié)構(gòu);在復(fù)雜的數(shù)據(jù)結(jié)構(gòu)里，允許成分數(shù)據(jù)本身具有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因而，構(gòu)造數(shù)據(jù)類型允許復(fù)合嵌套;指針類型對應(yīng)于數(shù)據(jù)結(jié)構(gòu)中成分數(shù)據(jù)之間的關(guān)系，表面上屬簡單數(shù)據(jù)類型，實際上都指向復(fù)雜的成分數(shù)據(jù)即構(gòu)造數(shù)據(jù)類型中的數(shù)據(jù)，因此這里沒有把它劃入簡單數(shù)據(jù)類型，也沒有劃入構(gòu)造數(shù)據(jù)類型，而單獨劃出一類

。     數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)內(nèi)部的構(gòu)成方式，它常常用一個結(jié)構(gòu)圖來描述:數(shù)據(jù)中的每一項成分數(shù)據(jù)被看作一個結(jié)點，并用方框或圓圈表示，成分數(shù)據(jù)之間的關(guān)系用相應(yīng)的結(jié)點之間帶箭號的連線表示。如果成分數(shù)據(jù)本身又有它自身的結(jié)構(gòu)，則結(jié)構(gòu)出現(xiàn)嵌套。這里嵌套還允許是遞歸的嵌套。

     由于指針數(shù)據(jù)的引入，使構(gòu)造各種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)成為可能。按數(shù)據(jù)結(jié)構(gòu)中的成分數(shù)據(jù)之間的關(guān)系，數(shù)據(jù)結(jié)構(gòu)有線性與非線性之分。在非線性數(shù)據(jù)結(jié)構(gòu)中又有層次與網(wǎng)狀之分。 由于數(shù)據(jù)類型是按照數(shù)據(jù)結(jié)構(gòu)劃分的，因此，一類數(shù)據(jù)結(jié)構(gòu)對應(yīng)著一種數(shù)據(jù)類型。數(shù)據(jù)類型按照該類型中的數(shù)據(jù)所呈現(xiàn)的結(jié)構(gòu)也有線性與非線性之分，層次與網(wǎng)狀之分。一個數(shù)據(jù)變量，在高級語言中的類型說明必須是讀變量所具有的數(shù)據(jù)結(jié)構(gòu)所對應(yīng)的數(shù)據(jù)類型。

     最常用的數(shù)據(jù)結(jié)構(gòu)是數(shù)組結(jié)構(gòu)和記錄結(jié)構(gòu)。數(shù)組結(jié)構(gòu)的特點是：

     成分數(shù)據(jù)的個數(shù)固定，它們之間的邏輯關(guān)系由成分數(shù)據(jù)的序號(或叫數(shù)組的下標)來體現(xiàn)。這些成分數(shù)據(jù)按照序號的先后順序一個挨一個地排列起來。 每一個成分數(shù)據(jù)具有相同的結(jié)構(gòu)(可以是簡單結(jié)構(gòu)，也可以是復(fù)雜結(jié)構(gòu))，因而屬于同一個數(shù)據(jù)類型(相應(yīng)地是簡單數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型)。這種同一的數(shù)據(jù)類型稱為基類型。 所有的成分數(shù)據(jù)被依序安排在一片連續(xù)的存儲單元中。 概括起來，數(shù)組結(jié)構(gòu)是一個線性的、均勻的、其成分數(shù)據(jù)可隨機訪問的結(jié)構(gòu)。由于這種結(jié)構(gòu)有這些良好的特性，所以最常被人們所采用。在高級語言中，與數(shù)組結(jié)構(gòu)相對應(yīng)的數(shù)據(jù)類型是數(shù)組類型，即數(shù)組結(jié)構(gòu)的數(shù)據(jù)變量必須說明為array [i] of T0 ，其中i是數(shù)組結(jié)構(gòu)的下標類型，而T0是數(shù)組結(jié)構(gòu)的基類型。

     記錄結(jié)構(gòu)是另一種常用的數(shù)據(jù)結(jié)構(gòu)。它的特點是:     與數(shù)組結(jié)構(gòu)一樣，成分數(shù)據(jù)的個數(shù)固定。但成分數(shù)據(jù)之間沒有自然序，它們處于平等地位。每一個成分數(shù)據(jù)被稱為一個域并賦予域名。不同的域有不同的域名。 不同的域允許有不同的結(jié)構(gòu)，因而允許屬于不同的數(shù)據(jù)類型。 與數(shù)組結(jié)構(gòu)一樣，它們可以隨機訪問，但訪問的途徑靠的是域名。 在高級語言中記錄結(jié)構(gòu)對應(yīng)的數(shù)據(jù)類型是記錄類型。記錄結(jié)構(gòu)的數(shù)據(jù)的變量必須說明為記錄類型。

     抽象數(shù)據(jù)類型的含義在上一段已作了專門敘述。它可理解為數(shù)據(jù)類型的進一步抽象。即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在一起，進行封裝。引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類型和運算在程序中的引用隔開，使它們相互獨立。對于抽象數(shù)據(jù)類型的描述，除了必須描述它的數(shù)據(jù)結(jié)構(gòu)外，還必須描述定義在它上面的運算(過程或函數(shù))。抽象數(shù)據(jù)類型上定義的過程和函數(shù)以該抽象數(shù)據(jù)類型的數(shù)據(jù)所應(yīng)具有的數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)。