1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念

1.2.1 數(shù)據(jù)結(jié)構(gòu)

1.數(shù)據(jù)

數(shù)據(jù)（data）是信息的載體，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合。可以將數(shù)據(jù)分為兩大類：一類是整數(shù)、實(shí)數(shù)等數(shù)值數(shù)據(jù)；另一類是文字、聲音、圖形和圖像等非數(shù)值數(shù)據(jù)。

數(shù)據(jù)是計(jì)算機(jī)程序處理的“原料”，例如，編譯程序處理的數(shù)據(jù)是源程序；學(xué)籍管理程序處理的數(shù)據(jù)是學(xué)籍登記表。

2.數(shù)據(jù)元素

數(shù)據(jù)元素（dataelement）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。構(gòu)成數(shù)據(jù)元素的不可分割的最小單位稱為數(shù)據(jù)項(xiàng)（dataitem）。例如，對(duì)于學(xué)生學(xué)籍登記表，每個(gè)學(xué)生的檔案就是一個(gè)數(shù)據(jù)元素，而檔案中的學(xué)號(hào)、姓名、出生日期等是數(shù)據(jù)項(xiàng)，如圖1-9所示。

數(shù)據(jù)元素具有廣泛的含義，一般來說，能獨(dú)立、完整地描述問題世界的一切實(shí)體都是數(shù)據(jù)元素。例如，對(duì)弈中的棋盤格局、教學(xué)計(jì)劃中的某門課程、一年中的四個(gè)季節(jié)，甚至一次學(xué)術(shù)報(bào)告、一場(chǎng)足球比賽都可以作為數(shù)據(jù)元素。

3.數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)（datastructure）是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。需要強(qiáng)調(diào)的是，數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項(xiàng)一般不予考慮。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。

（1）邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)（logicalstructure）是指數(shù)據(jù)元素之間邏輯關(guān)系的整體，是從實(shí)際問題抽象出的數(shù)據(jù)模型，在形式上可定義為一個(gè)二元組：

Data＿Structure=（D，R）

其中，D是數(shù)據(jù)元素的有限集合，R是D上關(guān)系的集合。實(shí)質(zhì)上，這個(gè)形式定義是對(duì)操作對(duì)象的一種數(shù)學(xué)描述，請(qǐng)看下面的例子。

【例1-8】 圖1-8所示七巧板涂色問題的數(shù)據(jù)模型可表示為：DS＿puzzle=（D，R），其中，D={A，B，C，D，E，F(xiàn)，G}，R={R1}，R1={＜A，B＞，＜A，E＞，＜A，F(xiàn)＞，＜B，C＞，＜B，D＞，＜C，D＞，＜D，E＞，＜D，G＞，＜E，F(xiàn)＞，＜E，G＞}。

根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為四類：

① 集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”，除此之外，沒有任何關(guān)系；

② 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系；

③ 樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系；

④ 圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。

樹結(jié)構(gòu)和圖結(jié)構(gòu)也稱為非線性結(jié)構(gòu)。

通常用邏輯關(guān)系圖來描述數(shù)據(jù)的邏輯結(jié)構(gòu)，其描述方法是：將每一個(gè)數(shù)據(jù)元素看做一個(gè)結(jié)點(diǎn)，用圓圈表示，元素之間的邏輯關(guān)系用結(jié)點(diǎn)之間的連線表示；如果強(qiáng)調(diào)關(guān)系的方向性，則用帶箭頭的連線表示關(guān)系。

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

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（storagestructure）又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示（也稱映像），換言之，存儲(chǔ)結(jié)構(gòu)除了存儲(chǔ)數(shù)據(jù)元素之外，必須隱式或顯式地存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。

通常有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的基本思想是用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來表示。鏈接存儲(chǔ)結(jié)構(gòu)的基本思想是：用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。

【例1-9】 對(duì)于數(shù)據(jù)結(jié)構(gòu)DS＿color=（D，R），其中D={red，green，blue}，R={R1}，R1={＜red，green＞，＜green，blue＞}，DS＿color的順序存儲(chǔ)如圖1-11所示，DS＿color的鏈接存儲(chǔ)如圖1-12所示。

如何描述存儲(chǔ)結(jié)構(gòu)呢？數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)涉及數(shù)據(jù)元素及其邏輯關(guān)系在計(jì)算機(jī)內(nèi)存中的物理位置，本書是在高級(jí)程序設(shè)計(jì)語言的層次上討論數(shù)據(jù)結(jié)構(gòu)及其操作的，因此，可以采用自定義數(shù)據(jù)類型來描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，具體請(qǐng)參見各章存儲(chǔ)結(jié)構(gòu)的定義。

如圖1-13所示，數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型，是面向問題的，反映了數(shù)據(jù)元素之間的關(guān)聯(lián)方式或鄰接關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是面向計(jì)算機(jī)的，其基本目標(biāo)是將數(shù)據(jù)及其邏輯關(guān)系存儲(chǔ)到計(jì)算機(jī)的內(nèi)存中。在不致混淆的情況下，常常將數(shù)據(jù)的邏輯結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。

1.2.2 抽象數(shù)據(jù)類型

1.數(shù)據(jù)類型

數(shù)據(jù)類型（datatype）是一組值的集合以及定義于這個(gè)值集上的一組操作的總稱。數(shù)據(jù)類型規(guī)定了該類型數(shù)據(jù)的取值范圍以及能夠執(zhí)行的操作。例如，C語言中整型變量的取值范圍是機(jī)器所能表示的最小負(fù)整數(shù)和最大正整數(shù)之間的任何一個(gè)整數(shù)，允許執(zhí)行的操作有算術(shù)運(yùn)算（+、-、*、/、%）、關(guān)系運(yùn)算（＜、＜=、＞、＞=、==、！=）和邏輯運(yùn)算（&&、‖、！）等。

2.抽象

所謂抽象（abstract），就是抽出問題的本質(zhì)特征而忽略非本質(zhì)的細(xì)節(jié)，是對(duì)具體事物的一個(gè)概括。比如，地圖是對(duì)它所描述地域的一種抽象，中國人是對(duì)所有具有中國國籍的中國公民的一種抽象。

無論在數(shù)學(xué)領(lǐng)域還是程序設(shè)計(jì)領(lǐng)域，抽象的能力都源于這樣一個(gè)事實(shí)：一旦一個(gè)抽象的問題得到解決，則很多同類的具體問題便可迎刃而解。抽象還可以實(shí)現(xiàn)封裝和信息隱藏，例如，C語言將能夠完成某種功能并可重復(fù)執(zhí)行的一段程序抽象為函數(shù)，在需要執(zhí)行這種功能時(shí)調(diào)用這個(gè)函數(shù)，從而將“做什么”和“怎么做”分離開來，實(shí)現(xiàn)了算法細(xì)節(jié)和數(shù)據(jù)內(nèi)部結(jié)構(gòu)的隱藏。

3.抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（AbstractDataType，ADT）是一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。ADT可理解為對(duì)數(shù)據(jù)類型的進(jìn)一步抽象，數(shù)據(jù)類型和ADT的區(qū)別僅在于：數(shù)據(jù)類型指的是高級(jí)程序設(shè)計(jì)語言支持的基本數(shù)據(jù)類型，而ADT指的是自定義的數(shù)據(jù)類型。

在設(shè)計(jì)ADT時(shí)，把ADT的定義和實(shí)現(xiàn)分開。定義部分只包含數(shù)據(jù)的邏輯結(jié)構(gòu)和所允許的基本操作集合，一方面，ADT的使用者依據(jù)這些定義來使用ADT，即通過操作集合對(duì)該ADT進(jìn)行操作；另一方面，ADT的實(shí)現(xiàn)者依據(jù)這些定義來完成該ADT各種基本操作的具體實(shí)現(xiàn)，如圖1-14所示。ADT提供了定義和實(shí)現(xiàn)的不同視圖，實(shí)現(xiàn)了封裝和信息隱藏。例如，整數(shù)的數(shù)學(xué)概念和施加到整數(shù)的運(yùn)算構(gòu)成一個(gè)ADT，C語言的int型是對(duì)這個(gè)ADT的物理實(shí)現(xiàn)，各種程序設(shè)計(jì)語言都提供了整數(shù)類型，盡管它們?cè)诓煌幾g器上實(shí)現(xiàn)的方法不同，但由于其ADT相同，在用戶看來都是相同的。

一個(gè)ADT的定義不涉及它的實(shí)現(xiàn)細(xì)節(jié)，在形式上可繁可簡，本書對(duì)ADT的定義包括抽象數(shù)據(jù)類型名、數(shù)據(jù)元素之間邏輯關(guān)系的定義、每種基本操作的接口（操作的名稱和該操作的前置條件、輸入、功能、輸出、后置條件的定義），形式如下：

            ADT抽象數(shù)據(jù)類型名
            Data
                  數(shù)據(jù)元素之間邏輯關(guān)系的定義
            Operation
            操作1
                  前置條件：執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài)
                  輸入：執(zhí)行此操作所需要的輸入
                  功能：該操作將完成的功能
                  輸出：執(zhí)行該操作后產(chǎn)生的輸出

                  后置條件：執(zhí)行該操作后數(shù)據(jù)的狀態(tài)
            操作2
                  …
            操作n
                  …
            endADT