數(shù)據(jù)結(jié)構(gòu)教案清華大學(xué)

1、1,第一章 數(shù)據(jù)結(jié)構(gòu)概念,數(shù)據(jù)結(jié)構(gòu)電子教案,殷人昆 王 宏,2,什么是數(shù)據(jù)結(jié)構(gòu) 抽象數(shù)據(jù)類型及面向?qū)ο蟾拍?算法定義 模板 算法簡(jiǎn)單性能分析與度量,第一章 數(shù)據(jù)結(jié)構(gòu)概念,3,“學(xué)生”表格,4,“課程”表格,5,學(xué)生 (學(xué)號(hào),姓名,性別,籍貫),課程 (課程號(hào),課程名,學(xué)分),選課 (學(xué)號(hào),課程號(hào),成績(jī)),“選課單”包含如下信息 學(xué)號(hào) 課程編號(hào) 成績(jī) 時(shí)間 學(xué)生選課系統(tǒng)中實(shí)體構(gòu)成的網(wǎng)狀關(guān)系,6,UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖,7,數(shù)據(jù)（data）,數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。 數(shù)據(jù)的分類： 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù),8,

2、數(shù)據(jù)元素 (data element),數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。 有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng) (Data Item)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。 數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。,9,什么是數(shù)據(jù)結(jié)構(gòu),定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成。記為： Data_Structure = D, R 其中，D 是某一數(shù)據(jù)元素的集合，R 是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。,10,例：N 個(gè)網(wǎng)點(diǎn)之間的連通關(guān)系,樹(shù)形關(guān)系,網(wǎng)狀關(guān)系,11,數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式,包括三個(gè)方面： 數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)

3、； 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)內(nèi)的表示，即數(shù)據(jù)的存儲(chǔ)表示； 數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作。,12,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型； 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無(wú)關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置無(wú)關(guān)。,13,數(shù)據(jù)的邏輯結(jié)構(gòu)分類,線性結(jié)構(gòu) 線性表 非線性結(jié)構(gòu) 樹(shù) 圖（或網(wǎng)絡(luò)）,14,線性結(jié)構(gòu),樹(shù)形結(jié)構(gòu),樹(shù) 二叉樹(shù) 二叉搜索樹(shù),15,堆結(jié)構(gòu),“最大”堆 “最小”堆,16,圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu),17,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)； 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴

4、于計(jì)算機(jī)語(yǔ)言。 順序存儲(chǔ)表示 鏈接存儲(chǔ)表示 索引存儲(chǔ)表示 散列存儲(chǔ)表示,主要用于內(nèi)存的存儲(chǔ)表示,主要用于外存 (文件) 的存儲(chǔ)表示,18,抽象數(shù)據(jù)類型及面向?qū)ο蟾拍?數(shù)據(jù)類型 定義：一組性質(zhì)相同的值的集合, 以及定義于這個(gè)值集合上的一組操作的總稱. C語(yǔ)言中的數(shù)據(jù)類型 char int float double void 字符型 整型 浮點(diǎn)型 雙精度型 無(wú)值,19,構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。 構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。 基本數(shù)據(jù)類型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過(guò)它是從編程者的角度來(lái)使用的。 數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變

5、量，才能參加運(yùn)算。,20,抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types),抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型。 特點(diǎn)是：信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離。 抽象數(shù)據(jù)類型可用（D, S, P）三元組表示，其中，D 是數(shù)據(jù)元素的集合（簡(jiǎn)稱數(shù)據(jù)對(duì)象），S 是 D上的關(guān)系集合，P 是對(duì) D 的基本操作集合。,21,抽象數(shù)據(jù)類型,22,抽象數(shù)據(jù)類型的描述,其中數(shù)據(jù)對(duì)象、數(shù)據(jù)之間的關(guān)系用偽碼描述；基本操作定義格式為,ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名,基本操作名（參數(shù)表）

6、前置條件：先決條件描述 后置條件：操作結(jié)果描述,23,基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以 False, True Boolean, +、-、=、= 等都是可用的服務(wù)。 Zero( ) : NaturalNumber /前置條件：無(wú) /后置條件：返回自然數(shù)0,25,IsZero(x) : Boolean /前置條件：x為NaturalNumber /后置條件：if (x = 0) then 返回True else 返回False Add (x, y) : NaturalNumber /前置條件：x, y為NaturalNumber且x+yMaxInt /后置條件：返回 x

7、+y Subtract (x, y) : NaturalNumber /前置條件： x, y為NaturalNumber且xy /后置條件：返回 x- y,26,Equal (x, y) : Boolean /前置條件： x, y為NaturalNumber /后置條件： if (x = y) 返回True else 返回 False Successor (x) : NaturalNumber /前置條件： x為NaturalNumber /后置條件： if (x = MaxInt) 返回 x else 返回 x+1 end NaturalNumber,27,面向?qū)ο蟮母拍?面向?qū)ο?= 對(duì)象

8、類繼承通信 對(duì)象 在應(yīng)用問(wèn)題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說(shuō)明等。 由一組屬性值和在這組值上的一組服務(wù)（或稱操作）構(gòu)成。 與C中構(gòu)造數(shù)據(jù)類型不同在于：C中的構(gòu)造數(shù)據(jù)類型的變量?jī)H涉及屬性值，與操作分離，而C+中的對(duì)象則不然。,28,類 (class)，實(shí)例 (instance) 具有相同屬性和服務(wù)的對(duì)象歸于同一類，形成類。 類中的對(duì)象為該類的實(shí)例。 同一類的實(shí)例 共享類的屬性和類的操作； 通過(guò)繼承共享其父類的公共的和保護(hù)性的屬性和操作； 同一類的不同實(shí)例有不同的屬性值。,29,四邊形類及其對(duì)象,30,繼承 派生類（子類）：四邊形，三角形， 基類（父類）：多邊形,31,通信 消息傳遞 C+中消息傳遞

9、的方式： 定義：Point p; void move(int x, inty); 使用：p.move(x, y); C中則不同，需使用函數(shù)調(diào)用方式： 定義：Point p; void move(Point q, int x, inty); 使用：move(p, x, y);,32,Draw( ) move(x, y) contains(aPoint),Polygon,referencePoint Vertices,Polygon 類,referencePoint Vertices,Draw( ) move(x, y) contains(aPoint),Polygon的子類 Quadrilate

10、ral類,Quadrilateral,33,算法定義,定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列 特性： 輸入 有0個(gè)或多個(gè)輸入 輸出 有一個(gè)或多個(gè)輸出(處理結(jié)果) 確定性 每步定義都是確切無(wú)歧義的 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束 有效性 每一條運(yùn)算應(yīng)足夠基本,34,事例學(xué)習(xí)：選擇排序問(wèn)題 明確問(wèn)題：遞增排序 解決方案：逐個(gè)選擇最小數(shù)據(jù) 算法框架： for (int i = 0; i n-1; i+) /n-1趟 從ai檢查到an-1; 若最小整數(shù)在ak, 交換ai與ak; 細(xì)化程序：程序 SelectSort,算法設(shè)計(jì) 自頂向下，逐步求精,35,void sele

11、ctSort ( int a , const int n ) /對(duì)n個(gè)整數(shù)a0,a1,an-1按遞增順序排序 for (int i = 0; i n-1; i+) int k = i; /從ai查到an-1, 找最小整數(shù), 在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; ,36,模板 (template),定義 適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過(guò)簡(jiǎn)單地代換，變成針對(duì)具體某種數(shù)據(jù)類型的類定義或算法。,37,用模板定義用于排序的數(shù)據(jù)表類 #ifndef DATALI

12、ST_H #define DATALIST_H #include /K是表項(xiàng)關(guān)鍵碼類型 template / /E是表項(xiàng)類型 class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);,38,public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend o

13、stream #endif,39,類中所有操作作為模板函數(shù)的實(shí)現(xiàn) template void dataList : swap (int m1, int m2) /交換由m1, m2為下標(biāo)的數(shù)組元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;,40,template int dataList:minKey (int low, int high) /查找數(shù)組Elementlow到Elementhigh中具 /有最小關(guān)鍵碼值的表項(xiàng)，函數(shù)返回其位置 int min = low; for (int i = lo

14、w+1, i = high, i+) if ( elementi elementmin ) min = i; return min; ;,定義的重載操作,41,template ostream ,42,template istream ,43,template void dataList : sort ( ) /按非遞減順序?qū)istSize個(gè)關(guān)鍵碼element0到 /elementArraySize-1排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i);

15、 #endif,44,使用模板的選擇排序算法的主函數(shù) #include #include “dataList.h” const int SZ = 10; int main ( ) struct sick /患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ;,45,dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; re

16、turn 0; ,定義對(duì)象時(shí)，代入實(shí)際數(shù)據(jù)類型,重載友元操作,標(biāo)準(zhǔn)IO操作,消息通信,46,算法簡(jiǎn)單性能分析與度量,算法的性能標(biāo)準(zhǔn) 算法的后期測(cè)試 算法的事前估計(jì),47,算法的性能標(biāo)準(zhǔn),正確性 (Correctness ) 算法應(yīng)滿足具體問(wèn)題的需求。 可讀性(Readability) 算法應(yīng)該容易閱讀。以有利于閱讀者對(duì)程序的理解。 效率 效率指的是算法執(zhí)行的時(shí)間和空間利用率。通常這兩者與問(wèn)題的規(guī)模有關(guān)。 健壯性 (Robustness) 算法應(yīng)具有容錯(cuò)處理的功能。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。,48,算法的后期測(cè)試,對(duì)一個(gè)算法要作出全面的分析可分成兩個(gè)階段

17、進(jìn)行，即事前分析和事后測(cè)試 事前分析要求事前求出該算法的一個(gè)時(shí)間界限函數(shù)。 事后測(cè)試則要求在算法執(zhí)行后通過(guò)算法執(zhí)行的時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料來(lái)分析。 事后分析要求在算法中的某些部位插裝時(shí)間函數(shù) time ( )，測(cè)定算法完成某一功能所花費(fèi)時(shí)間。,49,例如，給出順序搜索 (Sequenial Search)算法 int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索與給定值 x 相等的元 /素，函數(shù)返回其位置，失敗返回-1。 int i = 0; while ( i n ,50,插裝 time( ) 的計(jì)時(shí)程序 double start, s

18、top; time( 事實(shí)上，算法運(yùn)行時(shí)間要受輸入規(guī)模、利用編譯程序生成的目標(biāo)代碼的質(zhì)量、計(jì)算機(jī)程序指令系統(tǒng)的品質(zhì)和速度等制約。,51,算法的事前估計(jì),算法的事前估計(jì)主要包括時(shí)間復(fù)雜性和空間復(fù)雜性的分析： 問(wèn)題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)點(diǎn)個(gè)數(shù)、被分類序列的正整數(shù)個(gè)數(shù)等。 時(shí)間復(fù)雜性：算法所需時(shí)間和問(wèn)題規(guī)模的函數(shù)，記為 T(n)。當(dāng) n 時(shí)的時(shí)間復(fù)雜性，稱為漸進(jìn)時(shí)間復(fù)雜性。 空間復(fù)雜性：算法所需空間和問(wèn)題規(guī)模的函數(shù)。記為 S(n)。當(dāng) n 時(shí)的時(shí)間復(fù)雜性，稱為漸進(jìn)空間復(fù)雜性。,52,空間復(fù)雜度度量,存儲(chǔ)空間的固定部分程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長(zhǎng)成分(如數(shù)組元素、結(jié)構(gòu)成分、對(duì)象的數(shù)據(jù)成員等)變量所占空間 可變部分尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過(guò)new和dele