概念【數(shù)據(jù)】

1、數(shù)據(jù)（Data） 數(shù)據(jù)是信息的載體。它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理，是計(jì)算機(jī)程序加工的"原料"。 隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，數(shù)據(jù)的范疇包括：整數(shù)、實(shí)數(shù)、字符串、圖像和聲音等。數(shù)據(jù)元素（Data Element） 數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。 一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也可稱為字段、域、屬性）組成。 數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)結(jié)構(gòu)（Data Structure） 數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。1數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容： 數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)（Logical Struc

2、ture）； 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（Storage Structure）； 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)（亦稱為映象），它依賴于計(jì)算機(jī)語(yǔ)言。對(duì)機(jī)器語(yǔ)言而言，存儲(chǔ)結(jié)構(gòu)是具體的。一般，只在高級(jí)語(yǔ)言的層次上討論存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作。 數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。最常用的檢索、插入、刪除、更新、排序等運(yùn)算實(shí)際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。 所謂抽象

3、的操作，是指我們只知道這些操作是"做什么"，而無(wú)須考慮"如何做"。只有確定了存儲(chǔ)結(jié)構(gòu)之后，才考慮如何具體實(shí)現(xiàn)這些運(yùn)算。 為了增加對(duì)數(shù)據(jù)結(jié)構(gòu)的感性認(rèn)識(shí)，下面舉例來(lái)說(shuō)明有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念。（1）邏輯結(jié)構(gòu)表中的每一行是一個(gè)數(shù)據(jù)元素（或記錄、結(jié)點(diǎn)），它由學(xué)號(hào)、姓名、各科成績(jī)及平均成績(jī)等數(shù)據(jù)項(xiàng)組成。表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對(duì)表中任一個(gè)結(jié)點(diǎn)，與它相鄰且在它前面的結(jié)點(diǎn)（亦稱為直接前趨（Immediate Predecessor）最多只有一個(gè)；與表中任一結(jié)點(diǎn)相鄰且在其后的結(jié)點(diǎn)（亦稱為直接后繼（Immediate Successor）也最多只有一個(gè)。表中只有第一個(gè)結(jié)

4、點(diǎn)沒(méi)有直接前趨，故稱為開(kāi)始結(jié)點(diǎn)；也只有最后一個(gè)結(jié)點(diǎn)沒(méi)有直接后繼。故稱之為終端結(jié)點(diǎn)。例如，表中"馬二"所在結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)分別是"丁一"和"張三"所在的結(jié)點(diǎn)，上述結(jié)點(diǎn)間的關(guān)系構(gòu)成了這張學(xué)生成績(jī)表的邏輯結(jié)構(gòu)。（2）存儲(chǔ)結(jié)構(gòu)該表的存儲(chǔ)結(jié)構(gòu)是指用計(jì)算機(jī)語(yǔ)言如何表示結(jié)點(diǎn)之間的這種關(guān)系，即表中的結(jié)點(diǎn)是順序鄰接地存儲(chǔ)在一片連續(xù)的單元之中，還是用指針將這些結(jié)點(diǎn)鏈接在一起？（3）數(shù)據(jù)的運(yùn)算在上面的學(xué)生成績(jī)表中，可能要經(jīng)常查看某一學(xué)生的成績(jī)；當(dāng)學(xué)生退學(xué)時(shí)要?jiǎng)h除相應(yīng)的結(jié)點(diǎn)；進(jìn)來(lái)新學(xué)生時(shí)要增加結(jié)點(diǎn)。究竟如何進(jìn)行查找、刪除、插入，這就是數(shù)據(jù)的運(yùn)

5、算問(wèn)題。 搞清楚了上述三個(gè)問(wèn)題，也就弄清了學(xué)生成績(jī)表這個(gè)數(shù)據(jù)結(jié)構(gòu)。2數(shù)據(jù)的邏輯結(jié)構(gòu)分類 在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：（1）線性結(jié)構(gòu) 線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。 線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。（2）非線性結(jié)構(gòu) 非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。3數(shù)據(jù)的四種基本存儲(chǔ)方法 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用以下四種基本存儲(chǔ)方法得到：（1）順序存儲(chǔ)方法 該方法把邏輯上相

6、鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。 由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu) （Sequential Storage Structure），通常借助程序語(yǔ)言的數(shù)組描述。 該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過(guò)某種線性化的方法實(shí)現(xiàn)順序存儲(chǔ)。（2）鏈接存儲(chǔ)方法 該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（Linked Storage Structure）,通常借助于程序語(yǔ)言的指針類型描述。（3）索引存儲(chǔ)方法 該方法通常在儲(chǔ)存結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表

7、。 索引表由若干索引項(xiàng)組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該索引表稱之為稠密索引（Dense Index）。若一組結(jié)點(diǎn)在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引(Spare Index)。索引項(xiàng)的一般形式是： (關(guān)鍵字、地址)關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。稠密索引中索引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲(chǔ)位置；稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。（4）散列存儲(chǔ)方法 該方法的基本思想是：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。 四種基本存儲(chǔ)方法，既可單獨(dú)使用，也可組合起來(lái)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映像。 同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。選擇何種存

8、儲(chǔ)結(jié)構(gòu)來(lái)表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮運(yùn)算方便及算法的時(shí)空要求。4數(shù)據(jù)結(jié)構(gòu)三方面的關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算這三方面是一個(gè)整體。孤立地去理解一個(gè)方面，而不注意它們之間的聯(lián)系是不可取的。 存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個(gè)方面：同一邏輯結(jié)構(gòu)的不同存儲(chǔ)結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來(lái)標(biāo)識(shí)。 【例】線性表是一種邏輯結(jié)構(gòu)，若采用順序方法的存儲(chǔ)表示，可稱其為順序表；若采用鏈?zhǔn)酱鎯?chǔ)方法，則可稱其為鏈表；若采用散列存儲(chǔ)方法，則可稱為散列表。 數(shù)據(jù)的運(yùn)算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個(gè)方面。在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之后，按定義的運(yùn)算集合及其運(yùn)算的性質(zhì)不同，也可能導(dǎo)致完全不同的

9、數(shù)據(jù)結(jié)構(gòu)。 【例】若對(duì)線性表上的插入、刪除運(yùn)算限制在表的一端進(jìn)行，則該線性表稱之為棧；若對(duì)插入限制在表的一端進(jìn)行，而刪除限制在表的另一端進(jìn)行，則該線性表稱之為隊(duì)列。更進(jìn)一步，若線性表采用順序表或鏈表作為存儲(chǔ)結(jié)構(gòu)，則對(duì)插入和刪除運(yùn)算做了上述限制之后，可分別得到順序?；蜴湕＃樞蜿?duì)列或鏈隊(duì)列。數(shù)據(jù)類型（Data Type）所謂數(shù)據(jù)類型是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?！纠?2】C語(yǔ)言的"整數(shù)類型"就定義了一個(gè)整數(shù)可取值的范圍（其最大值INT-MAX依賴于具體機(jī)器）以及對(duì)整數(shù)可施加的加、減、乘、除和取模等操作。

10、 按"值"是否可分解，可將數(shù)據(jù)類型劃分為兩類：原子類型：其值不可分解。通常是由語(yǔ)言直接提供。 【例】C語(yǔ)言的整型、字符型等標(biāo)準(zhǔn)類型及指針等簡(jiǎn)單的導(dǎo)出類型；結(jié)構(gòu)類型：其值可分解為若干個(gè)成分（或稱為分量）。是用戶借助于語(yǔ)言提供的描述機(jī)制自己定義的，它通常是由標(biāo)準(zhǔn)類型派生的，故它也是一種導(dǎo)出類型?！纠緾的數(shù)組、結(jié)構(gòu)等類型。抽象數(shù)據(jù)類型（Abstract Type簡(jiǎn)稱ADT） ADT是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作。可以看作是數(shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。一個(gè)ADT可描述為：ADT ADT-Name Data:/數(shù)據(jù)說(shuō)明 數(shù)據(jù)元素之間邏輯關(guān)系的描述 Operatio

11、ns:/操作說(shuō)明 Operation1:/操作1，它通?？捎肅或C的函數(shù)原型來(lái)描述 Input:對(duì)輸入數(shù)據(jù)的說(shuō)明 Preconditions:執(zhí)行本操作前系統(tǒng)應(yīng)滿足的狀態(tài)/可看作初始條件 Process:對(duì)數(shù)據(jù)執(zhí)行的操作 Output:對(duì)返回?cái)?shù)據(jù)的說(shuō)明 Postconditions:執(zhí)行本操作后系統(tǒng)的狀態(tài)/"系統(tǒng)"可看作某個(gè)數(shù)據(jù)結(jié)構(gòu) Operation2:/操作2 /ADT 抽象數(shù)據(jù)類型可以看作是描述問(wèn)題的模型，它獨(dú)立于具體實(shí)現(xiàn)。它的優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通過(guò)在ADT里定義的某些操作來(lái)訪問(wèn)其中的數(shù)據(jù)，從而實(shí)現(xiàn)了信息隱藏。在C中，我們可以用類（包括模板

12、類）的說(shuō)明來(lái)表示ADT，用類的實(shí)現(xiàn)來(lái)實(shí)現(xiàn)ADT【參閱10】。因此，C中實(shí)現(xiàn)的類相當(dāng)于是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及其在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的對(duì)數(shù)據(jù)的操作。ADT和類的概念實(shí)際上反映了程序或軟件設(shè)計(jì)的兩層抽象：ADT相當(dāng)于是在概念層（或稱為抽象層）上描述問(wèn)題，而類相當(dāng)于是在實(shí)現(xiàn)層上描述問(wèn)題。此外，C中的類只是一個(gè)由用戶定義的普通類型，可用它來(lái)定義變量（稱為對(duì)象或類的實(shí)例）。因此，在C中，最終是通過(guò)操作對(duì)象來(lái)解決實(shí)際問(wèn)題的，所以我們可將該層次看作是應(yīng)用層。例如，main程序就可看作是用戶的應(yīng)用程序。由于C語(yǔ)言中沒(méi)有提供"類"這一數(shù)據(jù)類型，因此無(wú)法實(shí)現(xiàn)ADT，故我們不采用ADT的形式來(lái)描述數(shù)據(jù)結(jié)構(gòu)

13、，以節(jié)省篇幅。大家只要記住，它實(shí)際上等價(jià)于我們定義的數(shù)據(jù)的邏輯結(jié)構(gòu)以及在邏輯結(jié)構(gòu)上定義的抽象操作。1.1 簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。 數(shù)據(jù)：指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載體。 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可以由若干數(shù)據(jù)項(xiàng)組成。 數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。 邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。 存儲(chǔ)結(jié)構(gòu)