數(shù)據(jù)結(jié)構(gòu)清華大學PPT課件

1、1第一章第一章 數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)概念第1頁/共72頁2 學學 號號 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 1 98131 劉激揚劉激揚 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 島島 1979.07 3 98165 盧聲凱盧聲凱 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 廣廣 州州 1980.10 5 98224 洪洪 偉偉 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕 女女 蘇蘇 州州 1980.03 7 98297 宮宮 力力 男男 北北 京京 1981.01 8 98310 蔡曉莉蔡曉莉 女

2、女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.12第2頁/共72頁3 課程編號課程編號 課課 程程 名名 學時學時 024002 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ) 64 024010 匯編語言匯編語言 48 024016 計算機原理計算機原理 64 024020 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 64 024021 微機技術(shù)微機技術(shù) 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 48第3頁/共72頁4學生學生( (學號學號, ,姓名姓名, ,性別性別, ,籍貫籍貫) )課程課程( (課程號課程號, ,課程名課程名, ,學分學分) )選課選課(

3、 (學號學號, ,課程號課程號, ,成績成績) )第4頁/共72頁5UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第5頁/共72頁6數(shù)據(jù)（數(shù)據(jù)（datadata）數(shù)據(jù)是數(shù)據(jù)是信息信息的載體，是描述客觀事物的數(shù)、的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。算機程序識別和處理的符號的集合。數(shù)據(jù)的分類：數(shù)據(jù)的分類：u 數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù)u 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)第6頁/共72頁7姓

4、名姓名 所在院系所在院系 性別性別 出生日期出生日期 年年 月月職務(wù)職務(wù) 業(yè)績業(yè)績數(shù)據(jù)元素數(shù)據(jù)元素 (data element)(data element)n數(shù)據(jù)的基本單位。在計算機程序中常作為數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。一個整體進行考慮和處理。n有時一個數(shù)據(jù)元素可以由若干有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項數(shù)據(jù)項 (Data Item)組成。數(shù)據(jù)項是具有獨立含義組成。數(shù)據(jù)項是具有獨立含義的最小的最小標識單位。標識單位。n數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。第7頁/共72頁8什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)定義定義: 由某一數(shù)據(jù)元素的集合以及

5、該集合中所有由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成。記為：數(shù)據(jù)元素之間的關(guān)系組成。記為： Data_Structure = D, R 其中，其中，D 是某一數(shù)據(jù)元素的集合，是某一數(shù)據(jù)元素的集合，R 是該是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合第8頁/共72頁9例：例：N N 個網(wǎng)點之間的連通關(guān)系個網(wǎng)點之間的連通關(guān)系 156152436243第9頁/共72頁10數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式n包括三個方面：包括三個方面：u數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯邏輯結(jié)構(gòu)結(jié)構(gòu)；u數(shù)據(jù)元素及其關(guān)系在

6、計算機存儲內(nèi)的表數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的表示，即數(shù)據(jù)的示，即數(shù)據(jù)的存儲表示存儲表示；u數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作操作。第10頁/共72頁11數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)；與數(shù)據(jù)的存儲無關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；象出來的數(shù)據(jù)模型；n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；內(nèi)容無關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲

7、位置無關(guān)。置無關(guān)。第11頁/共72頁12數(shù)據(jù)的邏輯結(jié)構(gòu)分類數(shù)據(jù)的邏輯結(jié)構(gòu)分類n線性結(jié)構(gòu)線性結(jié)構(gòu)u 線性表線性表n非線性結(jié)構(gòu)非線性結(jié)構(gòu)u 樹樹u 圖（或網(wǎng)絡(luò)）圖（或網(wǎng)絡(luò)）第12頁/共72頁13線性結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)樹樹 二叉樹二叉樹 二叉搜索樹二叉搜索樹bindevetclibuser14131211234567891031587101199874566231311第13頁/共72頁14堆結(jié)構(gòu)堆結(jié)構(gòu)123548711102916410121151236987第14頁/共72頁15圖結(jié)構(gòu)圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)12543611331814665161921125634第15頁/共72頁1

8、6數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)n數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)；的實現(xiàn)；n數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。u 順序存儲表示順序存儲表示u 鏈接存儲表示鏈接存儲表示u 索引存儲表示索引存儲表示u 散列存儲表示散列存儲表示主要用于內(nèi)存的主要用于內(nèi)存的存儲表示存儲表示主要用于外存主要用于外存 (文文件件) 的存儲表示的存儲表示第16頁/共72頁17抽象數(shù)據(jù)類型及面向?qū)ο蟾拍畛橄髷?shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)類型數(shù)據(jù)類型 定義：定義：一組性質(zhì)相同的值的集合一組性質(zhì)相同的值的集合, 以及定義于這個值集合上的一組操作的總以及定義于

9、這個值集合上的一組操作的總稱稱.C語言中的數(shù)據(jù)類型語言中的數(shù)據(jù)類型字符型字符型 整型整型 浮點型浮點型 雙精度型雙精度型 無值無值 第17頁/共72頁18n構(gòu)造數(shù)據(jù)類型由構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型基本數(shù)據(jù)類型或或構(gòu)造數(shù)據(jù)構(gòu)造數(shù)據(jù)類型類型組成。組成。n構(gòu)造數(shù)據(jù)類型由構(gòu)造數(shù)據(jù)類型由不同成分類型不同成分類型構(gòu)成。構(gòu)成。n基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。n數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。者的角度來使用的。n數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型

10、的變量，才能參加運算。類型的變量，才能參加運算。 第18頁/共72頁19抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types)(ADTs: Abstract Data Types)抽象數(shù)據(jù)類型是由用戶定義，用以表示抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。應(yīng)用問題的數(shù)據(jù)模型。特點是：特點是：信息隱蔽信息隱蔽和和數(shù)據(jù)封裝數(shù)據(jù)封裝，使用與使用與實現(xiàn)相分離實現(xiàn)相分離。抽象數(shù)據(jù)類型可用抽象數(shù)據(jù)類型可用（D, S, P）三元組表三元組表示，其中，示，其中，D 是數(shù)據(jù)元素的集合（簡稱是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對象），數(shù)據(jù)對象），S 是是 D上的關(guān)系集合，上的關(guān)系集合，

11、P 是是對對 D 的基本操作集合。的基本操作集合。 第19頁/共72頁20抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找查找 登錄登錄 刪除刪除 修改修改 符符 號號 表表第20頁/共72頁21抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型的描述其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系用偽碼其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系用偽碼描述；基本操作定義格式為描述；基本操作定義格式為ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(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ù)類型名基本操作名（參數(shù)表）基本操作名（參數(shù)表）前置條件

12、：前置條件：先決條件描述先決條件描述后置條件：后置條件：操作結(jié)果描述操作結(jié)果描述第21頁/共72頁22基本操作有兩種參數(shù)：基本操作有兩種參數(shù)：賦值參數(shù)賦值參數(shù)只為操作只為操作提供輸入值；提供輸入值；引用參數(shù)引用參數(shù)以以&打頭，除可提打頭，除可提供輸入值外，還將返回操作結(jié)果。供輸入值外，還將返回操作結(jié)果。 “前置條件前置條件”描述了操作執(zhí)行之前數(shù)據(jù)描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，結(jié)構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。則操作失敗，并返回相應(yīng)出錯信息。 “后置條件后置條件”說明了操作正常完成之后，說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變

13、化狀況和應(yīng)返回的結(jié)果。若數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置條件為空，則省略之。前置條件為空，則省略之。第22頁/共72頁23自然數(shù)的抽象數(shù)據(jù)類型定義自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber isobjects: 一個整數(shù)的有序子集合一個整數(shù)的有序子集合,它開始于它開始于0, 結(jié)束于機器能表示的最大整數(shù)結(jié)束于機器能表示的最大整數(shù)(MaxInt)。Function: 對于所有的對于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等等都是可用的服務(wù)。都是可用的服務(wù)。 Zero( ) : NaturalNumber /前

14、置條件前置條件：無：無 /后置條件后置條件：返回自然數(shù)返回自然數(shù)0第23頁/共72頁24IsZero(x) : Boolean /前置條件前置條件：x為為NaturalNumber /后置條件后置條件：if (x = 0) then 返回返回True else 返回返回False Add (x, y) : NaturalNumber /前置條件前置條件：x, y為為NaturalNumber且且x+yMaxInt /后置條件后置條件：返回返回 x+y Subtract (x, y) : NaturalNumber /前置條件前置條件： x, y為為NaturalNumber且且xy /后置條件

15、后置條件：返回返回 x- - y第24頁/共72頁25Equal (x, y) : Boolean /前置條件前置條件： x, y為為NaturalNumber /后置條件后置條件： if (x = y) 返回返回True else 返回返回 False Successor (x) : NaturalNumber /前置條件前置條件： x為為NaturalNumber /后置條件后置條件： if (x = MaxInt) 返回返回 x else 返回返回 x+1end NaturalNumber第25頁/共72頁26面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍頽面向?qū)ο竺嫦驅(qū)ο?= = 對象類繼承通信對象類繼

16、承通信n對象對象u在應(yīng)用問題中出現(xiàn)的各種在應(yīng)用問題中出現(xiàn)的各種實體實體、事件事件、規(guī)格說明規(guī)格說明等。等。u由一組由一組屬性值屬性值和在這組值上的一組和在這組值上的一組服務(wù)服務(wù)（或稱操作）構(gòu)成。（或稱操作）構(gòu)成。u與與C中構(gòu)造數(shù)據(jù)類型不同在于：中構(gòu)造數(shù)據(jù)類型不同在于：C中的中的構(gòu)造數(shù)據(jù)類型的變量僅涉及屬性值，與構(gòu)造數(shù)據(jù)類型的變量僅涉及屬性值，與操作分離，而操作分離，而C+中的對象則不然。中的對象則不然。第26頁/共72頁27n類類 (class)，實例，實例 (instance)u具有相同屬性和服務(wù)的對象歸于同一類，具有相同屬性和服務(wù)的對象歸于同一類，形成類。形成類。u類中的對象為該類的實例。

17、類中的對象為該類的實例。u同一類的實例同一類的實例 共享類的屬性和類的操作；共享類的屬性和類的操作； 通過繼承共享其父類的公共的和保護通過繼承共享其父類的公共的和保護性的屬性和操作；性的屬性和操作； 同一類的不同實例有不同的屬性值。同一類的不同實例有不同的屬性值。第27頁/共72頁28四邊形類及其對象四邊形類及其對象屬性aPoint1 aPoint2aPoint3 aPoint4服務(wù)服務(wù)Draw( )move(x, y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(45,

18、 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)contains(aPoint)服務(wù)服務(wù)服務(wù)服務(wù)quadrilateral第28頁/共72頁29n繼承繼承u派生類（子類）：派生類（子類）：四邊形，三角四邊形，三角形，形，u基類（父類）：基類（父類）：多邊形多邊形派生類派生類繼承的特性繼承的特性+特有的特性特有的特性基類基類多邊形多邊形四邊形四邊形三角形三角形六邊形六邊形第29頁/共72頁30n通信通信u消息傳遞消息傳遞uC+中消息傳遞的方式：中消息傳遞的方式： 定義：定義：Point

19、 p; void move(int x, inty); 使用：使用：p.move(x, y);uC中則不同，需使用函數(shù)調(diào)用方式：中則不同，需使用函數(shù)調(diào)用方式： 定義：定義：Point p; void move(Point q, int x, inty); 使用：使用：move(p, x, y);第30頁/共72頁31Draw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 類類referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子類的子類Q

20、uadrilateral類類Quadrilateral第31頁/共72頁32算法定義算法定義定義：定義：一個有窮的指令集一個有窮的指令集，這些指令為，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列解決某一特定任務(wù)規(guī)定了一個運算序列特性：特性：u輸入輸入 有有0個或多個輸入個或多個輸入u輸出輸出 有一個或多個輸出有一個或多個輸出(處理結(jié)果處理結(jié)果)u確定性確定性 每步定義都是確切無歧義的每步定義都是確切無歧義的u有窮性有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束算法應(yīng)在執(zhí)行有窮步后結(jié)束u有效性有效性 每一條運算應(yīng)足夠基本每一條運算應(yīng)足夠基本第32頁/共72頁33事例學習：事例學習：選擇排序問題選擇排序問題明確

21、問題：明確問題：遞增排序遞增排序解決方案：解決方案：逐個選擇最小數(shù)據(jù)逐個選擇最小數(shù)據(jù)算法框架：算法框架： for (int i = 0; i n-1; i+) /n-1趟趟 從從ai檢查到檢查到an-1; 若最小整數(shù)在若最小整數(shù)在ak, 交換交換ai與與ak; 細化程序：細化程序：程序程序 SelectSort 算法設(shè)計算法設(shè)計 自頂向下，逐步求精自頂向下，逐步求精 第33頁/共72頁34 void selectSort ( int a , const int n ) /對n個整數(shù)a0,a1,an-1按遞增順序排序 for (int i = 0; i n-1; i+) int k = i; /

22、從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; 第34頁/共72頁35模板模板 (template)(template)定義定義 適合適合多種數(shù)據(jù)類型多種數(shù)據(jù)類型的的類定義類定義或或算法算法，在特，在特定環(huán)境下通過簡單地代換，變成定環(huán)境下通過簡單地代換，變成針對具體某針對具體某種數(shù)據(jù)類型種數(shù)據(jù)類型的的類定義類定義或或算法。算法。第35頁/共72頁36用模板定義用于排序的數(shù)據(jù)表類用模板定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H

23、#define DATALIST_H#include /K是表項關(guān)鍵碼類型template / /E是表項類型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);第36頁/共72頁37 public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend o

24、stream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& inList); ; #endif 第37頁/共72頁38類中所有操作作為模板函數(shù)的實現(xiàn)類中所有操作作為模板函數(shù)的實現(xiàn)template void dataList : swap (int m1, int m2) /交換由m1, m2為下標的數(shù)組元素的值 E temp = element m1; element m1 = el

25、ement m2; element m2 = temp; ;第38頁/共72頁39template int dataList:minKey (int low, int high) /查找數(shù)組Elementlow到Elementhigh中具/有最小關(guān)鍵碼值的表項，函數(shù)返回其位置 int min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定義的重載操作定義的重載操作第39頁/共72頁40template ostream& operator (ostream&

26、amp; outStream, dataList outList) outStream “輸出數(shù)組內(nèi)容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream endl; ouStream “輸出數(shù)組當前大小 : ” outList.listSize endl; return outStream; 第40頁/共72頁41 template istream& operator (istream& inStream, dataList inList) cout inLis

27、t.listSize; cout “輸入數(shù)組元素值 : n”; for (int i = 0; i inList.listSize; i+) cout “元素” i inList.elementi; return inStream; 第41頁/共72頁42template void dataList : sort ( ) /按非遞減順序?qū)Π捶沁f減順序?qū)istSize個關(guān)鍵碼個關(guān)鍵碼element0到到/elementArraySize-1排序排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j

28、 != i) swap (j, i); #endif 第42頁/共72頁43使用模板的選擇排序算法的主函數(shù)使用模板的選擇排序算法的主函數(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; ; 第43頁/共72頁44 dataList TestList (SZ); cin TestList; cout TestL

29、ist endl; TestList.Sort ( ); cout TestList endl; return 0; 定義對象時，代定義對象時，代入實際數(shù)據(jù)類型入實際數(shù)據(jù)類型重載友元操作重載友元操作標準標準IO操作操作消息通信消息通信第44頁/共72頁45算法簡單性能分析與度量算法簡單性能分析與度量第45頁/共72頁46算法的性能標準算法的性能標準(Correctness ) 算法應(yīng)滿足具體算法應(yīng)滿足具體問題的需求。問題的需求。(Readability) 算法應(yīng)該容易閱讀。算法應(yīng)該容易閱讀。以有利于閱讀者對程序的理解。以有利于閱讀者對程序的理解。效率指的是算法執(zhí)行的時間和空間效率指的是算法執(zhí)行

30、的時間和空間利用率。通常這兩者與問題的規(guī)模有關(guān)。利用率。通常這兩者與問題的規(guī)模有關(guān)。(Robustness) 算法應(yīng)具有容錯算法應(yīng)具有容錯處理的功能。當輸入非法數(shù)據(jù)時，算法應(yīng)處理的功能。當輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸對其作出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。出結(jié)果。第46頁/共72頁47算法的后期測試算法的后期測試對一個算法要作出全面的分析可分成兩個對一個算法要作出全面的分析可分成兩個階段進行，即階段進行，即事前分析事前分析和和事后測試事后測試事前分析事前分析要求事前求出該算法的一個時間要求事前求出該算法的一個時間界限函數(shù)。界限函數(shù)。事后測試事后測試則要求在算法

31、執(zhí)行后通過算法執(zhí)則要求在算法執(zhí)行后通過算法執(zhí)行的時間和實際占用空間的統(tǒng)計資料來分行的時間和實際占用空間的統(tǒng)計資料來分析。析。事后分析要求在算法中的某些部位插裝時事后分析要求在算法中的某些部位插裝時間函數(shù)間函數(shù) time ( )，第47頁/共72頁48例如，給出順序搜索例如，給出順序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索與給定值 x 相等的元/素，函數(shù)返回其位置，失敗返回-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n

32、 ) return -1; return i;第48頁/共72頁49 插裝插裝 time( ) 的計時程序的計時程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&stop); double runTime = stop - start; cout n runTime endl;事實上，算法運行時間要受事實上，算法運行時間要受輸入規(guī)模、利用輸入規(guī)模、利用編譯程序生成的目標代碼的質(zhì)量、計算機編譯程序生成的目標代碼的質(zhì)量、計算機程序指令系統(tǒng)的品質(zhì)和速度等制約。程序指令系統(tǒng)的品質(zhì)和速度等制約。

33、第49頁/共72頁50算法的事前估計算法的事前估計算法的事前估計主要包括時間復雜性和算法的事前估計主要包括時間復雜性和空間復雜性的分析：空間復雜性的分析：u問題的規(guī)模：問題的規(guī)模：如：矩陣的階數(shù)、圖的如：矩陣的階數(shù)、圖的結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)等。等。u時間復雜性時間復雜性：算法所需時間和問題規(guī)：算法所需時間和問題規(guī)模的函數(shù)，記為模的函數(shù)，記為 T(n)。當當 n 時的時的時間復雜性，稱為時間復雜性，稱為漸進時間復雜性漸進時間復雜性。u空間復雜性空間復雜性：算法所需空間和問題規(guī)：算法所需空間和問題規(guī)模的函數(shù)。記為模的函數(shù)。記為 S(n)。當當 n 時的時

34、的時間復雜性，稱為時間復雜性，稱為漸進空間復雜性漸進空間復雜性。第50頁/共72頁51空間復雜度度量空間復雜度度量第51頁/共72頁52時間復雜度度量時間復雜度度量達式達式：程序步數(shù)為：程序步數(shù)為1第52頁/共72頁53n程序步確定方法程序步確定方法u插入計數(shù)全局變量插入計數(shù)全局變量countu建表，建表，列出個語句的程序步列出個語句的程序步例例 以迭代方式求累加和的函數(shù)以迭代方式求累加和的函數(shù) float sum (float a , int n) float s = 0.0; for (int i = 0; i n; i+) s = s + ai; return s; 第53頁/共72頁5

35、4在求累加和程序中加入在求累加和程序中加入 count 語句語句 float sum (float a , int n) float s = 0.0; count+; /count 統(tǒng)計執(zhí)行語句條數(shù) for (int i = 0; i n; i+) count += 2; /針對 for 語句s += ai;count+; /針對賦值語句 count += 2; /針對 for 的最后一次 count+; /針對 return 語句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序步數(shù) count = 3*n+4第54頁/共72頁55 void sum (float a , int n)

36、 for (int i = 0; i n; i+) count += 3; count += 4; 第55頁/共72頁56注意注意： 一個語句本身的程序步數(shù)可能不等于該語一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。句一次執(zhí)行所具有的程序步數(shù)。 例如：例如：賦值語句賦值語句x = sum (R, n) 本身程序步數(shù)為本身程序步數(shù)為 1；一次執(zhí)行對函數(shù)一次執(zhí)行對函數(shù) sum (R, n) 的調(diào)用需要的程的調(diào)用需要的程序步數(shù)為序步數(shù)為 3*n+4；一次執(zhí)行的程序步數(shù)為一次執(zhí)行的程序步數(shù)為 1+3*n+4 = 3*n+5第56頁/共72頁57計算累加和程序計算累加和程序程序步數(shù)計算

37、工作表格程序步數(shù)計算工作表格第57頁/共72頁58時間復雜度的漸進表示法時間復雜度的漸進表示法例例 求兩個求兩個n階方陣的乘積階方陣的乘積C = A Bvoid MatrixMultiply (int Ann, int Bnn, int Cnn) for (int i = 0; i n; i+) 2n+2 for (int j = 0; j n; j+) n(2n+2) Cij = 0; n2 for (int k = 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 3n3 + 5n2 + 4n +2第58頁/共72頁59時間復雜度的漸進表示法時間

38、復雜度的漸進表示法算法中所有語句的頻度之和是算法中所有語句的頻度之和是矩陣階數(shù)矩陣階數(shù)n的函數(shù)的函數(shù) T(n) = 3n3 + 5n2 + 4n +2一般地，稱一般地，稱 n 是問題的規(guī)模。則時間復雜是問題的規(guī)模。則時間復雜度度 T(n) 是問題規(guī)模是問題規(guī)模 n 的函數(shù)。的函數(shù)。當當n趨于無窮大時，把時間復雜度的數(shù)量趨于無窮大時，把時間復雜度的數(shù)量級（階）稱為算法的漸進時間復雜度級（階）稱為算法的漸進時間復雜度 T(n) = O(n3) 大大O表示法表示法第59頁/共72頁60加法規(guī)則加法規(guī)則 針對并列程序段針對并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max

39、(f (n), g (m)各種函數(shù)的增長趨勢各種函數(shù)的增長趨勢 c log2n n nlog2n n2 n3 2n 3n n!第60頁/共72頁61T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T3(n) = O(n2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;第61頁/共72頁62乘法規(guī)則乘法規(guī)則 針對嵌套程序段針對嵌

40、套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)漸進的空間復雜度漸進的空間復雜度 S (n) = O(f (n)兩個并列循環(huán)的例子兩個并列循環(huán)的例子第62頁/共72頁63 void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行 sumi = 0.0; /數(shù)據(jù)累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行數(shù)據(jù)和 cout i “ : ” sum i endl; O(max (m*n, m)第63頁/共72頁64起泡排序起泡排序 void bubbleSort (int a , int n ) /對表 a 逐趟比較,