自考數(shù)據(jù)結(jié)構(gòu)課件 第一章 緒論

1、教材: 自考數(shù)據(jù)結(jié)構(gòu) 蘇仕華 編著 授課教師：涂風(fēng)華授課教師：涂風(fēng)華開始日期：開始日期：2014年年3月月1日日 1.1 1.1 基本概念和術(shù)語基本概念和術(shù)語 1.2 1.2 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 1.3 1.3 算法的描述和分析算法的描述和分析第1章 概論數(shù)據(jù)數(shù)據(jù)（data)data)是信息的載體。它能夠被計算機(jī)識是信息的載體。它能夠被計算機(jī)識別、存儲和加工處理，是計算機(jī)程序加工的別、存儲和加工處理，是計算機(jī)程序加工的 原料原料 。 數(shù)據(jù)元素數(shù)據(jù)元素（data elementdata element）是數(shù)據(jù)的是數(shù)據(jù)的基本單位基本單位，由若干個數(shù)據(jù)項組成，也稱結(jié)點、元素、頂點或

2、由若干個數(shù)據(jù)項組成，也稱結(jié)點、元素、頂點或記記錄。錄。數(shù)據(jù)項數(shù)據(jù)項（data itemdata item）是具有獨立含義的是具有獨立含義的最小標(biāo)最小標(biāo)識單位識單位，有時也稱為域（，有時也稱為域（fieldfield），即數(shù)據(jù)表中的字），即數(shù)據(jù)表中的字段。段。1.1 基本概念和術(shù)語基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(data structure)(data structure)：指的是數(shù)據(jù)之間指的是數(shù)據(jù)之間的的相互關(guān)系相互關(guān)系，即數(shù)據(jù)的組織形式。，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容： 數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏

3、輯結(jié)構(gòu)（邏輯結(jié)構(gòu)（Logical StructureLogical Structure）； 數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)（存儲結(jié)構(gòu)（Storage Storage StructureStructure）； 數(shù)據(jù)的運算數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作。，即對數(shù)據(jù)施加的操作。 數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機(jī)的。數(shù)據(jù)的邏數(shù)據(jù)的存儲無關(guān)，是獨立于計算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模

4、型。型。 數(shù)據(jù)的數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的實是邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn)（亦稱為映象），它依賴于計算機(jī)語言。對機(jī)現(xiàn)（亦稱為映象），它依賴于計算機(jī)語言。對機(jī)器語言而言，存儲結(jié)構(gòu)是具體的。一般，只在高器語言而言，存儲結(jié)構(gòu)是具體的。一般，只在高級語言的層次上討論存儲結(jié)構(gòu)。級語言的層次上討論存儲結(jié)構(gòu)。 數(shù)據(jù)的數(shù)據(jù)的運算運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運算的集合。最常用的檢索、插輯結(jié)構(gòu)都有一個運算的集合。最常用的檢索、插入、刪除、更新、排序等運算實際上只是在抽象入、刪除、更新、排序等運算實際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。的

5、數(shù)據(jù)上所施加的一系列抽象的操作。 所謂所謂抽象的操作抽象的操作，是指我們只知道這些操作是，是指我們只知道這些操作是做什么做什么，而無須考慮，而無須考慮如何做如何做。只有確定了存。只有確定了存儲結(jié)構(gòu)之后，才考慮如何具體實現(xiàn)這些運算。儲結(jié)構(gòu)之后，才考慮如何具體實現(xiàn)這些運算。 3 3為了增加對數(shù)據(jù)結(jié)構(gòu)的感性認(rèn)識，下面舉例來說明有關(guān)數(shù)據(jù)結(jié)構(gòu)的概為了增加對數(shù)據(jù)結(jié)構(gòu)的感性認(rèn)識，下面舉例來說明有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念。念?！纠纠?1】 學(xué)生成績表，見下表。學(xué)生成績表，見下表。 （1）邏輯結(jié)構(gòu)）邏輯結(jié)構(gòu)表中的每一行是一個數(shù)據(jù)元素（或記錄、結(jié)點），它由學(xué)號、表中的每一行是一個數(shù)據(jù)元素（或記錄、結(jié)點），它由學(xué)號、姓名

6、、各科成績及平均成績等數(shù)據(jù)項組成。姓名、各科成績及平均成績等數(shù)據(jù)項組成。表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對表中任一個結(jié)點，與它相鄰且表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對表中任一個結(jié)點，與它相鄰且在它前面的結(jié)點（亦稱為直接前趨（在它前面的結(jié)點（亦稱為直接前趨（Immediate Predecessor）最）最多只有一個；與表中任一結(jié)點相鄰且在其后的結(jié)點（亦稱為直接后多只有一個；與表中任一結(jié)點相鄰且在其后的結(jié)點（亦稱為直接后繼（繼（Immediate Successor）也最多只有一個。表中只有第一個結(jié)）也最多只有一個。表中只有第一個結(jié)點沒有直接前趨，故稱為開始結(jié)點；也只有最后一個結(jié)點沒有直接點沒有直接

7、前趨，故稱為開始結(jié)點；也只有最后一個結(jié)點沒有直接后繼。故稱之為終端結(jié)點。例如，表中后繼。故稱之為終端結(jié)點。例如，表中李四李四所在結(jié)點的直接前趨所在結(jié)點的直接前趨結(jié)點和直接后繼結(jié)點分別是結(jié)點和直接后繼結(jié)點分別是張三張三和和王五王五所在的結(jié)點，上述結(jié)點所在的結(jié)點，上述結(jié)點間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)。間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)。（2）存儲結(jié)構(gòu)該表的存儲結(jié)構(gòu)是指用計算機(jī)語言如何表示結(jié)點之間的這種關(guān)系，即表中的結(jié)點是順序鄰接地存儲在一片連續(xù)的單元之中，還是用指針將這些結(jié)點鏈接在一起？（3）數(shù)據(jù)的運算在上面的學(xué)生成績表中，可能要經(jīng)常查看某一學(xué)生的成績；當(dāng)學(xué)生退學(xué)時要刪除相應(yīng)的結(jié)點；

8、進(jìn)來新學(xué)生時要增加結(jié)點。究竟如何進(jìn)行查找、刪除、插入，這就是數(shù)據(jù)的運算問題。 搞清楚了上述三個問題，也就弄清了學(xué)生成績表這個數(shù)據(jù)結(jié)構(gòu)。 2數(shù)據(jù)的邏輯結(jié)構(gòu)分類數(shù)據(jù)的邏輯結(jié)構(gòu)分類 在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類： （1）線性結(jié)構(gòu)）線性結(jié)構(gòu) 線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。最多只有一個直接前趨

9、和一個直接后繼。 線性表是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都線性表是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。是線性結(jié)構(gòu)。（2）非線性結(jié)構(gòu)）非線性結(jié)構(gòu) 非線性結(jié)構(gòu)的邏輯特征是：一個結(jié)點可能有多個直非線性結(jié)構(gòu)的邏輯特征是：一個結(jié)點可能有多個直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。構(gòu)都是非線性結(jié)構(gòu)。 3數(shù)據(jù)的四種基本存儲方法數(shù)據(jù)的四種基本存儲方法 數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法得到：數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法得到：（1）順序存儲方法）順序存儲方法 該方法把邏輯上相鄰的結(jié)點存儲在物理位置上相該方法把邏

10、輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。鄰接關(guān)系來體現(xiàn)。 由此得到的存儲表示稱為由此得到的存儲表示稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)，通常借，通常借助程序語言的數(shù)組描述。助程序語言的數(shù)組描述。 該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實現(xiàn)順序存儲。據(jù)結(jié)構(gòu)也可通過某種線性化的方法實現(xiàn)順序存儲。（2）鏈接存儲方法）鏈接存儲方法 該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系由附

11、加的指針字段表示。相鄰，結(jié)點間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲表示稱為由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)（Linked Storage Structure）,通常借助于程序語言的指針類型通常借助于程序語言的指針類型描述。描述。元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲地址存儲內(nèi)容存儲內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順序存儲順序存儲1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存儲地址存儲地址 存儲內(nèi)容存儲內(nèi)容 指針指針 1345

12、1345 元素元素1 1 14001400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 15361536 . . . . . 15361536 元素元素3 3 13461346 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?h（3）索引存儲方法）索引存儲方法 該方法通常在儲存結(jié)點信息的同時，還建立附加的索引表。該方法通常在儲存結(jié)點信息的同時，還建立附加的索引表。 索引表由若干索引項組成。若每個結(jié)點在索引表中都有一個索引表由若干索引項組成。若每個結(jié)點在索引表中都有一個索引項，則該索引表稱之為稠密索引（索引項，則該索引表稱之為稠密索引（Dense Index）。若一組）。若一組結(jié)點

13、在索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索引結(jié)點在索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索引(Spare Index)。索引項的一般形式是：。索引項的一般形式是： (關(guān)鍵字、地址關(guān)鍵字、地址)關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。稠密索引中索引關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。稠密索引中索引項的地址指示結(jié)點所在的存儲位置；稀疏索引中索引項的地址項的地址指示結(jié)點所在的存儲位置；稀疏索引中索引項的地址指示一組結(jié)點的起始存儲位置。指示一組結(jié)點的起始存儲位置。（4）散列存儲方法）散列存儲方法 該方法的基本思想是：根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點該方法的基本思想是：根據(jù)結(jié)點的關(guān)鍵字直

14、接計算出該結(jié)點的存儲地址。的存儲地址。 四種基本存儲方法，既可單獨使用，也可組合起來對數(shù)據(jù)結(jié)四種基本存儲方法，既可單獨使用，也可組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲映像。構(gòu)進(jìn)行存儲映像。 同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮運算方便及算法的時空要求。定，主要考慮運算方便及算法的時空要求。 4數(shù)據(jù)結(jié)構(gòu)三方面的關(guān)系數(shù)據(jù)結(jié)構(gòu)三方面的關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算這三方面是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)

15、的運算這三方面是一個整體。孤立地去理解一個方面，而不注意它們之間的聯(lián)系一個整體。孤立地去理解一個方面，而不注意它們之間的聯(lián)系是不可取的。是不可取的。 存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個方面：同一邏輯結(jié)構(gòu)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個方面：同一邏輯結(jié)構(gòu)的不同存儲結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來標(biāo)識。不同存儲結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來標(biāo)識。 【例【例】線性表是一種邏輯結(jié)構(gòu)，若采用順序方法的存儲表示線性表是一種邏輯結(jié)構(gòu)，若采用順序方法的存儲表示，可稱其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒ǎ瑒t可稱其為鏈表；，可稱其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒?，則可稱其為鏈表；若采用散列存儲方法，則可稱為散列表。若采用散列

16、存儲方法，則可稱為散列表。 數(shù)據(jù)的運算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個方面。在給定了數(shù)數(shù)據(jù)的運算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個方面。在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之后，按定義的運算集合及其運算的據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之后，按定義的運算集合及其運算的性質(zhì)不同，也可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)。性質(zhì)不同，也可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)。 【例【例】若對線性表上的插入、刪除運算限制在表的一端進(jìn)行若對線性表上的插入、刪除運算限制在表的一端進(jìn)行，則該線性表稱之為棧；若對插入限制在表的一端進(jìn)行，而刪，則該線性表稱之為棧；若對插入限制在表的一端進(jìn)行，而刪除限制在表的另一端進(jìn)行，則該線性表稱之為隊列。更進(jìn)一步除限制在表的另

17、一端進(jìn)行，則該線性表稱之為隊列。更進(jìn)一步，若線性表采用順序表或鏈表作為存儲結(jié)構(gòu)，則對插入和刪除，若線性表采用順序表或鏈表作為存儲結(jié)構(gòu)，則對插入和刪除運算做了上述限制之后，可分別得到順序?；蜴湕?，順序隊列運算做了上述限制之后，可分別得到順序?；蜴湕?，順序隊列或鏈隊列?；蜴滉犃?。 5數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)類型（數(shù)據(jù)類型（Data Type） 自自20世紀(jì)世紀(jì)70年代以來，幾乎所有的高級程序設(shè)計語言都提供了這一年代以來，幾乎所有的高級程序設(shè)計語言都提供了這一概念。在用高級語言編寫的程序中間，程序中出現(xiàn)的每個變量，常量概念。在用高級語言編寫的程序中間，程序中出現(xiàn)的每個變量，常

18、量或表達(dá)式，都必須事先說明它們所屬的數(shù)據(jù)類型，每個類型都明顯或或表達(dá)式，都必須事先說明它們所屬的數(shù)據(jù)類型，每個類型都明顯或隱含的規(guī)定了在程序執(zhí)行期間它的變量，它的表達(dá)式所允許取值的范隱含的規(guī)定了在程序執(zhí)行期間它的變量，它的表達(dá)式所允許取值的范圍，以及允許進(jìn)行的操作，因此圍，以及允許進(jìn)行的操作，因此所謂數(shù)據(jù)類型是一個值的集合以及在這些值上定義的一組操作的總稱。所謂數(shù)據(jù)類型是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。通常數(shù)據(jù)類型可以看作是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?！纠纠?2】C語言的語言的整數(shù)類型整數(shù)類型就定義了一個整數(shù)可取值的范

19、圍（其就定義了一個整數(shù)可取值的范圍（其最大值最大值INT-MAX依賴于具體機(jī)器）以及對整數(shù)可施加的加、減、乘、依賴于具體機(jī)器）以及對整數(shù)可施加的加、減、乘、除和取模等操作。除和取模等操作。 按按值值是否可分解，可將數(shù)據(jù)類型劃分為兩類：是否可分解，可將數(shù)據(jù)類型劃分為兩類：原子類型：原子類型：其值不可分解。通常是由語言直接提供。其值不可分解。通常是由語言直接提供。 【例】【例】C語言的整型、字符型等標(biāo)準(zhǔn)類型及指針等簡單的導(dǎo)出類型；語言的整型、字符型等標(biāo)準(zhǔn)類型及指針等簡單的導(dǎo)出類型；結(jié)構(gòu)類型：結(jié)構(gòu)類型：其值可分解為若干個成分（或稱為分量）。是用戶借助其值可分解為若干個成分（或稱為分量）。是用戶借助于

20、語言提供的描述機(jī)制自己定義的，它通常是由標(biāo)準(zhǔn)類型派生的，故于語言提供的描述機(jī)制自己定義的，它通常是由標(biāo)準(zhǔn)類型派生的，故它也是一種導(dǎo)出類型。它也是一種導(dǎo)出類型。 【例】【例】C的數(shù)組、結(jié)構(gòu)等類型。的數(shù)組、結(jié)構(gòu)等類型。 用戶也可用用戶也可用typedef 自己定義數(shù)據(jù)類型自己定義數(shù)據(jù)類型typedef struct int num; char name20; float score; STUDENT;STUDENT stu1,stu2, *p;抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型ADTADT（Abstract Abstract Data Type)Data Type)定義：是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作。

21、可以看作是數(shù)據(jù)的邏輯結(jié)構(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ù)類型數(shù)據(jù)類型 一個一個ADT可描述為：可描述為：ADT ADT-Name Data: /數(shù)據(jù)說明數(shù)據(jù)說明 數(shù)據(jù)元素之間邏輯關(guān)系的描述數(shù)據(jù)元素之間邏輯關(guān)系的描述 Operations: /操作說明操作說明 Operation1: /操作操作1，它通?？捎?，它通?？捎肅或或C的函數(shù)原的函數(shù)原型來描述型來描述 Input:對輸入數(shù)據(jù)的說明對輸入數(shù)據(jù)的說明 Preconditions:執(zhí)行本操作前系統(tǒng)應(yīng)滿足的狀態(tài)執(zhí)行本操作前系統(tǒng)應(yīng)滿足的狀態(tài)/可看作初可看作初

22、始條件始條件 Process:對數(shù)據(jù)執(zhí)行的操作對數(shù)據(jù)執(zhí)行的操作 Output:對返回數(shù)據(jù)的說明對返回數(shù)據(jù)的說明 Postconditions:執(zhí)行本操作后系統(tǒng)的狀態(tài)執(zhí)行本操作后系統(tǒng)的狀態(tài)/系統(tǒng)系統(tǒng)可看作可看作某個數(shù)據(jù)結(jié)構(gòu)某個數(shù)據(jù)結(jié)構(gòu) Operation2:/操作操作2 /ADT v描述方法描述方法形式定義：我們用一個三元組形式定義：我們用一個三元組 （D，S，P）來表示一個來表示一個 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 ，其中，其中D是數(shù)據(jù)對是數(shù)據(jù)對象，象，S是是D上的關(guān)系集，上的關(guān)系集，P是對是對D的基本操作集的基本操作集。 格式：格式： ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義

23、數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 v基本操作的定義格式：基本操作的定義格式： 基本操作名（參數(shù)表）基本操作名（參數(shù)表） 初始條件：初始條件描述初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述操作結(jié)果：操作結(jié)果描述 賦值參數(shù)賦值參數(shù)引用參數(shù)，以引用參數(shù)，以“”打頭打頭例：抽象數(shù)據(jù)類型三元組的定義：例：抽象數(shù)據(jù)類型三元組的定義： ADT Triplet 數(shù)據(jù)對象：數(shù)據(jù)對象：D=e1,e2,e3 |e1,e2,e3Elemset 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1=, 基本操作：基本操

24、作： InitTriplet(&T,v1,v2,v3) 操作結(jié)果：構(gòu)造了三元組操作結(jié)果：構(gòu)造了三元組T， 元素元素e1，e2和和e3分別被賦以分別被賦以 參數(shù)參數(shù)v1,v2和和v3的值。的值。 DestroyTriplet（&T） 操作結(jié)果：三元組操作結(jié)果：三元組T被銷毀。被銷毀。 Get（T,i,&e） 初始條件：三元組初始條件：三元組T已存在，已存在， 1=i=3. 操作結(jié)果：用操作結(jié)果：用e返回返回T的第的第i元的值。元的值。 Put(&T,i,e) 初始條件：三元組初始條件：三元組T已存在，已存在，1=i=3. 操作結(jié)果：改變操作結(jié)果：改變T的第的第i元

25、的值為元的值為e。 IsAscending(T) 初始條件：三元組初始條件：三元組T已存在。已存在。 操作結(jié)果：如果操作結(jié)果：如果T的的3個元素按升序排列個元素按升序排列，則返回，則返回1，否則返回，否則返回0。IsDescending(T) 初始條件：三元組初始條件：三元組T已存在。已存在。 操作結(jié)果：如果操作結(jié)果：如果T的的3個元素按降序排列，則個元素按降序排列，則 返回返回1，否則返回，否則返回0。Max(T,&e) 初始條件：三元組初始條件：三元組T已存在。已存在。 操作結(jié)果：用操作結(jié)果：用e返回返回T的的3個元素中的最大值。個元素中的最大值。Min(T,&e) 初始條

26、件：三元組初始條件：三元組T已存在。已存在。 操作結(jié)果：用操作結(jié)果：用e返回返回T的的3個元素中的最小值。個元素中的最小值。ADT Triplet 抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨立于具體實現(xiàn)。抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨立于具體實現(xiàn)。它的優(yōu)點是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通過它的優(yōu)點是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通過在在ADT里定義的某些操作來訪問其中的數(shù)據(jù)，從而實現(xiàn)了里定義的某些操作來訪問其中的數(shù)據(jù)，從而實現(xiàn)了信息信息隱藏隱藏。在。在C中，我們可以用類（包括模板類）的說明來表中，我們可以用類（包括模板類）的說明來表示示ADT，用類的實現(xiàn)來實現(xiàn)

27、，用類的實現(xiàn)來實現(xiàn)ADT。因此，。因此，C中實現(xiàn)的類相中實現(xiàn)的類相當(dāng)于是數(shù)據(jù)的存儲結(jié)構(gòu)及其在存儲結(jié)構(gòu)上實現(xiàn)的對數(shù)據(jù)的操作。當(dāng)于是數(shù)據(jù)的存儲結(jié)構(gòu)及其在存儲結(jié)構(gòu)上實現(xiàn)的對數(shù)據(jù)的操作。ADT和類的概念實際上反映了程序或軟件設(shè)計的兩層抽象：和類的概念實際上反映了程序或軟件設(shè)計的兩層抽象：ADT相當(dāng)于是在概念層（或稱為抽象層）上描述問題，而類相相當(dāng)于是在概念層（或稱為抽象層）上描述問題，而類相當(dāng)于是在實現(xiàn)層上描述問題。當(dāng)于是在實現(xiàn)層上描述問題。此外，此外，C中的類只是一個由中的類只是一個由用戶定義的普通類型，可用它來定義變量（稱為對象或類的實用戶定義的普通類型，可用它來定義變量（稱為對象或類的實例）。因

28、此，在例）。因此，在C中，最終是通過操作對象來解決實際問中，最終是通過操作對象來解決實際問題的，所以我們可將該層次看作是應(yīng)用層。例如，題的，所以我們可將該層次看作是應(yīng)用層。例如，main程序就程序就可看作是用戶的應(yīng)用程序?？煽醋魇怯脩舻膽?yīng)用程序。由于由于C語言中沒有提供語言中沒有提供類類這一數(shù)據(jù)類型，因此無法實現(xiàn)這一數(shù)據(jù)類型，因此無法實現(xiàn)ADT，故我們不采用，故我們不采用ADT的形式來描述數(shù)據(jù)結(jié)構(gòu)，以節(jié)省篇幅。的形式來描述數(shù)據(jù)結(jié)構(gòu)，以節(jié)省篇幅。大家只要記住，它實際上等價于我們定義的數(shù)據(jù)的邏輯結(jié)構(gòu)以大家只要記住，它實際上等價于我們定義的數(shù)據(jù)的邏輯結(jié)構(gòu)以及在邏輯結(jié)構(gòu)上定義的抽象操作。及在邏輯結(jié)構(gòu)上

29、定義的抽象操作。1.2 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義著名計算機(jī)科學(xué)家、著名計算機(jī)科學(xué)家、PascalPascal語言發(fā)明者語言發(fā)明者N.N.沃思教授提出：沃思教授提出： 程序程序 = = 算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 程序程序: : 處理問題編制一組指令集處理問題編制一組指令集 算法算法: : 處理問題的策略處理問題的策略數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): : 問題的數(shù)學(xué)模型問題的數(shù)學(xué)模型也就是說，計算機(jī)按照程序所描述的算法也就是說，計算機(jī)按照程序所描述的算法對某種結(jié)構(gòu)的數(shù)據(jù)進(jìn)行加工處理。對某種結(jié)構(gòu)的數(shù)據(jù)進(jìn)行加工處理。1 計算機(jī)處理問題的分類計算機(jī)處理問題的分類 （1）數(shù)值計算問題 在計算機(jī)發(fā)展初期，人們使用計算

30、機(jī)主要是處理數(shù)值計算問題?！纠烤€性方程的求解 該類問題涉及的運算對象是簡單的整型、實型或布爾型數(shù)據(jù)。程序設(shè)計者的主要精力集中于程序設(shè)計的技巧，無須重視數(shù)據(jù)結(jié)構(gòu)。 隨著計算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展隨著計算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，“非數(shù)值性問題非數(shù)值性問題”越來越顯得重要。據(jù)統(tǒng)計，越來越顯得重要。據(jù)統(tǒng)計，當(dāng)今處理非數(shù)值性問題占用了當(dāng)今處理非數(shù)值性問題占用了90%以上的機(jī)器時以上的機(jī)器時間，這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)間，這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決此類問題的關(guān)

31、鍵已不再是分析描述。因此，解決此類問題的關(guān)鍵已不再是分析數(shù)學(xué)和計算方法，而是要設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)和計算方法，而是要設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。，才能有效地解決問題。 程序設(shè)計的實質(zhì)是對實際問題選擇一種好的數(shù)程序設(shè)計的實質(zhì)是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法，而好的算法在據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法，而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。 （2 2）非數(shù)值計算的程序設(shè)計問題：）非數(shù)值計算的程序設(shè)計問題：例例1 1 書目自動檢索系統(tǒng)書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目

32、卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L002,S001,003,索引表線性表算法：需要檢索的書目？如何檢索？用戶算法：需要檢索的書目？如何檢索？用戶界面？界面？ 模型：？模型：？例例2 2 人機(jī)對奕問題人機(jī)對奕問題樹.算法：對奕的規(guī)則算法：對奕的規(guī)則 和策略和策略模型：？模型：？例例3 3 教學(xué)計劃編排問題教學(xué)計劃編排問題 圖課程代號課程名稱先修課程C1C1計算機(jī)導(dǎo)論計算機(jī)導(dǎo)論無無C2C2數(shù)

33、據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)C1,C4C1,C4C3C3匯編語言匯編語言C1C1C4C4C C語言語言C1C1C5C5計算機(jī)圖形學(xué)計算機(jī)圖形學(xué)C2,C3,C4C2,C3,C4C6C6接口技術(shù)接口技術(shù)C3C3C7C7數(shù)據(jù)庫原理數(shù)據(jù)庫原理C2,C9C2,C9C8C8編譯原理編譯原理C4C4C9C9操作系統(tǒng)操作系統(tǒng)C2C2C1C3C4C7C6C5C2C8C9 算法：如何確定課程的次序關(guān)系算法：如何確定課程的次序關(guān)系? ? 模型：？模型：？從上述例子不難看出：從上述例子不難看出：解決問題的一個關(guān)解決問題的一個關(guān)鍵步驟是，選取合適的數(shù)據(jù)結(jié)構(gòu)表示該鍵步驟是，選取合適的數(shù)據(jù)結(jié)構(gòu)表示該問題，然后才能寫出有效的算法。問題，然

34、后才能寫出有效的算法。 1.3 算法的描述和分析v有窮性：有窮性：對于任意一組合法輸入值，在對于任意一組合法輸入值，在執(zhí)行執(zhí)行有窮步有窮步之后結(jié)束，且算法中的每個步之后結(jié)束，且算法中的每個步驟都能在驟都能在有限時間有限時間內(nèi)完成；內(nèi)完成；v確定性：確定性：每條指令都有確切的含義，在每條指令都有確切的含義，在任何條件下算法都只有一條執(zhí)行路徑；任何條件下算法都只有一條執(zhí)行路徑；算法五個重要特性：算法五個重要特性：算法：是對特定問題求解算法：是對特定問題求解步驟的一種描述步驟的一種描述，它是指令的有限序列。它是指令的有限序列。v可行性：可行性：算法中的所有操作都必須算法中的所有操作都必須足夠足夠基本

35、基本，都可以通過已經(jīng)實現(xiàn)的基本操作運，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之；算有限次實現(xiàn)之；v輸入：輸入：有零個或多個輸入，取自特定的有零個或多個輸入，取自特定的對象集合對象集合v輸出：輸出：有一個或多個輸出，是算法進(jìn)行有一個或多個輸出，是算法進(jìn)行信息加工后得到的結(jié)果。信息加工后得到的結(jié)果。二、算法分析二、算法分析1評價算法好壞的標(biāo)準(zhǔn)評價算法好壞的標(biāo)準(zhǔn)求解同一計算問題可能有許多不同的算法，究求解同一計算問題可能有許多不同的算法，究竟如何來評價這些算法的好壞以便從中選出較好的竟如何來評價這些算法的好壞以便從中選出較好的算法呢？算法呢？ 選用的算法首先應(yīng)該是選用的算法首先應(yīng)該是正確正確的。

36、此外，主要考的。此外，主要考慮如下三點：慮如下三點： 執(zhí)行算法所耗費的時間；執(zhí)行算法所耗費的時間； 執(zhí)行算法所耗費的存儲空間，其中主要考慮輔助執(zhí)行算法所耗費的存儲空間，其中主要考慮輔助存儲空間；存儲空間； 算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。v2算法性能選擇算法性能選擇一個占存儲空間小、運行時間短、其它性能一個占存儲空間小、運行時間短、其它性能也好的算法是很難做到的。原因是上述要求有時也好的算法是很難做到的。原因是上述要求有時相互抵觸：要節(jié)約算法的執(zhí)行時間往往要以犧牲相互抵觸：要節(jié)約算法的執(zhí)行時間往往要以犧牲更多的空間為代價；而為了節(jié)省空間可能要耗費

37、更多的空間為代價；而為了節(jié)省空間可能要耗費更多的計算時間。因此我們只能根據(jù)具體情況有更多的計算時間。因此我們只能根據(jù)具體情況有所側(cè)重：所側(cè)重： 若該程序使用次數(shù)較少，則力求算法簡明易懂；若該程序使用次數(shù)較少，則力求算法簡明易懂； 對于反復(fù)多次使用的程序，應(yīng)盡可能選用快速對于反復(fù)多次使用的程序，應(yīng)盡可能選用快速的算法；的算法； 若待解決的問題數(shù)據(jù)量極大，機(jī)器的存儲空間若待解決的問題數(shù)據(jù)量極大，機(jī)器的存儲空間較小，則相應(yīng)算法主要考慮如何節(jié)省空間。較小，則相應(yīng)算法主要考慮如何節(jié)省空間。v3算法的時間性能分析算法的時間性能分析（1）算法耗費的時間和語句頻度）算法耗費的時間和語句頻度一個算法所耗費的時間

38、一個算法所耗費的時間=算法中每條語句的執(zhí)算法中每條語句的執(zhí)行時間之和行時間之和每條語句的執(zhí)行時間每條語句的執(zhí)行時間=語句的執(zhí)行次數(shù)語句的執(zhí)行次數(shù)(即頻度即頻度(Frequency Count)語句執(zhí)行一次所需時間語句執(zhí)行一次所需時間 算法轉(zhuǎn)換為程序后，每條語句執(zhí)行一次所需的時算法轉(zhuǎn)換為程序后，每條語句執(zhí)行一次所需的時間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量等難以確定的因素。代碼質(zhì)量等難以確定的因素。 若要獨立于機(jī)器的軟、硬件系統(tǒng)來分析算法的時若要獨立于機(jī)器的軟、硬件系統(tǒng)來分析算法的時間耗費，則設(shè)每條語句執(zhí)行一次所需的時間均是單間耗費，則設(shè)每條語句執(zhí)行一次所需的時間均是單位時間，一個算法的時間耗費就是該算法中所有語位時間，一個算法的時間耗費就是該算法中所有語句的頻度之和。句的頻度之和。算法執(zhí)行時間的衡量方法和準(zhǔn)則算法執(zhí)行時間的衡量方法和準(zhǔn)則 有有兩種兩種衡量算法效率的方法衡量算法效率的方法: : 1. 1.事后統(tǒng)計法：利用計算機(jī)內(nèi)記時功事后統(tǒng)計法：利用計算機(jī)內(nèi)記時功能，用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)能，用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分。分。 2.2.事前分析估計法：求出算法的一個事前分析估計法：求出算法的一個時間界限函數(shù)。時間