1、第一章 數(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)概念 學(xué)學(xué) 號(hào)號(hào) 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 1 98131 劉激揚(yáng)劉激揚(yáng) 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 島島 1979.07 3 98165 盧聲凱盧聲凱 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 廣廣 州州 1980.10 5 98224 洪洪 偉偉 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕 女女 蘇蘇 州州 1980.03 7 98297 宮宮 力力 男男 北北

2、 京京 1981.01 8 98310 蔡曉莉蔡曉莉 女女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.12 課程編號(hào)課程編號(hào) 課課 程程 名名 學(xué)時(shí)學(xué)時(shí) 024002 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 64 024010 匯編語(yǔ)言匯編語(yǔ)言 48 024016 計(jì)算機(jī)原理計(jì)算機(jī)原理 64 024020 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 64 024021 微機(jī)技術(shù)微機(jī)技術(shù) 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫(kù)原理數(shù)據(jù)庫(kù)原理 48學(xué)生學(xué)生( (學(xué)號(hào)學(xué)號(hào), ,姓名姓名, ,性別性別, ,籍貫籍貫) )課程課程( (課程號(hào)課程號(hào), ,課程名課程名, ,學(xué)分

3、學(xué)分) )選課選課( (學(xué)號(hào)學(xué)號(hào), ,課程號(hào)課程號(hào), ,成果成果) )UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp數(shù)據(jù)數(shù)據(jù)datadata）n數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。機(jī)程序識(shí)別和處理的符號(hào)的集合。n數(shù)據(jù)的分類：數(shù)據(jù)的分類：n 數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù)n 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)姓名姓名 所在院系所在院系 性別性別

4、 出生日期出生日期 年年 月月職務(wù)職務(wù) 業(yè)績(jī)業(yè)績(jī)數(shù)據(jù)元素?cái)?shù)據(jù)元素 (data element)(data element)n數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)整體進(jìn)行考慮和處理。n有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng) (Data Item)(Data Item)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。的最小標(biāo)識(shí)單位。n數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)定義定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有由某一數(shù)據(jù)元素的集

5、合以及該集合中所有數(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)系的有限集合。例：例：N N 個(gè)網(wǎng)點(diǎn)之間的連通關(guān)系個(gè)網(wǎng)點(diǎn)之間的連通關(guān)系 156152436243數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式n包括三個(gè)方面：包括三個(gè)方面：n數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；構(gòu)；n數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)內(nèi)的表示，數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)內(nèi)的表示，即數(shù)

6、據(jù)的存儲(chǔ)表示；即數(shù)據(jù)的存儲(chǔ)表示；n數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作。數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作。數(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ù)的存儲(chǔ)無關(guān)；與數(shù)據(jù)的存儲(chǔ)無關(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ù)元素的相對(duì)存儲(chǔ)位數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置無關(guān)。置無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類數(shù)據(jù)的邏輯結(jié)構(gòu)分類n線性結(jié)構(gòu)線性結(jié)構(gòu)n 線性

7、表線性表n非線性結(jié)構(gòu)非線性結(jié)構(gòu)n 樹樹n 圖或網(wǎng)絡(luò)）圖或網(wǎng)絡(luò)）線性結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)樹樹 二叉樹二叉樹 二叉搜索樹二叉搜索樹bindevetclibuser14131211234567891031587101199874566231311堆結(jié)構(gòu)堆結(jié)構(gòu)123548711102916410121151236987圖結(jié)構(gòu)圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)12543611331814665161921125634數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)；的實(shí)現(xiàn)；n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語(yǔ)言。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語(yǔ)言。n 順序

8、存儲(chǔ)表示順序存儲(chǔ)表示n 鏈接存儲(chǔ)表示鏈接存儲(chǔ)表示n 索引存儲(chǔ)表示索引存儲(chǔ)表示n 散列存儲(chǔ)表示散列存儲(chǔ)表示主要用于內(nèi)存的主要用于內(nèi)存的存儲(chǔ)表示存儲(chǔ)表示主要用于外存主要用于外存 (文文件件) 的存儲(chǔ)表示的存儲(chǔ)表示抽象數(shù)據(jù)類型及面向?qū)ο蟾拍畛橄髷?shù)據(jù)類型及面向?qū)ο蟾拍頽數(shù)據(jù)類型數(shù)據(jù)類型 定義：一組性質(zhì)相同的值的集合定義：一組性質(zhì)相同的值的集合, 以及定以及定義于這個(gè)值集合上的一組操作的總稱義于這個(gè)值集合上的一組操作的總稱.nC語(yǔ)言中的數(shù)據(jù)類型語(yǔ)言中的數(shù)據(jù)類型n char int float double voidn 字符型字符型 整型整型 浮點(diǎn)型浮點(diǎn)型 雙精度型雙精度型 無無值值 n構(gòu)造數(shù)據(jù)類型由基本

9、數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。類型組成。n構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。n基本數(shù)據(jù)類型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)基本數(shù)據(jù)類型可以看作是計(jì)算機(jī)中已實(shí)現(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ù)類型的變量，才能參加運(yùn)算。類型的變量，才能參加運(yùn)算。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types)(ADTs: Abstract Data T

10、ypes)n抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。用問題的數(shù)據(jù)模型。n特點(diǎn)是：信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)特點(diǎn)是：信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離。現(xiàn)相分離。n抽象數(shù)據(jù)類型可用抽象數(shù)據(jù)類型可用D, S, P三元組表示，三元組表示，其中，其中，D 是數(shù)據(jù)元素的集合簡(jiǎn)稱數(shù)據(jù)對(duì)是數(shù)據(jù)元素的集合簡(jiǎn)稱數(shù)據(jù)對(duì)象），象），S 是是 D上的關(guān)系集合，上的關(guān)系集合，P 是對(duì)是對(duì) D 的的基本操作集合。基本操作集合。 n抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找查找 登錄登錄 刪除刪除 修改修改 符符 號(hào)號(hào) 表表抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型的描述n其中數(shù)據(jù)對(duì)象、數(shù)據(jù)之間

11、的關(guān)系用偽碼描其中數(shù)據(jù)對(duì)象、數(shù)據(jù)之間的關(guān)系用偽碼描述；基本操作定義格式為述；基本操作定義格式為ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名基本操作名參數(shù)表）基本操作名參數(shù)表）前置條件：先決條件描述前置條件：先決條件描述后置條件：操作結(jié)果描述后置條件：操作結(jié)果描述n基本操作有兩種參數(shù)：賦值參數(shù)只為操作提基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以供輸入值；引用參數(shù)以&打頭，除可提供輸打頭，除可提供

12、輸入值外，還將返回操作結(jié)果。入值外，還將返回操作結(jié)果。n “前置條件前置條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，則構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作失敗，并返回相應(yīng)出錯(cuò)信息。n “后置條件后置條件說明了操作正常完成之后，說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置條件為空，則省略之。置條件為空，則省略之。自然數(shù)的抽象數(shù)據(jù)類型定義自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber isobjects: 一個(gè)整數(shù)的有序子集合一個(gè)整數(shù)的有序子集合,它

13、開始于它開始于0, 結(jié)束于機(jī)器能表示的最大整數(shù)結(jié)束于機(jī)器能表示的最大整數(shù)(MaxInt)。Function: 對(duì)于所有的對(duì)于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是等都是可用的服務(wù)。可用的服務(wù)。 Zero( ) : NaturalNumber /前置條件：無前置條件：無 /后置條件：返回自然數(shù)后置條件：返回自然數(shù)0 面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍頽面向?qū)ο竺嫦驅(qū)ο?= = 對(duì)象類繼承通信對(duì)象類繼承通信n對(duì)象對(duì)象n在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等。格說明等。n由一組屬性值和在這組

14、值上的一組服務(wù)由一組屬性值和在這組值上的一組服務(wù)或稱操作構(gòu)成。或稱操作構(gòu)成。n與與C C中構(gòu)造數(shù)據(jù)類型不同在于：中構(gòu)造數(shù)據(jù)類型不同在于：C C中的構(gòu)造中的構(gòu)造數(shù)據(jù)類型的變量?jī)H涉及屬性值，與操作分?jǐn)?shù)據(jù)類型的變量?jī)H涉及屬性值，與操作分離，而離，而C+C+中的對(duì)象則不然。中的對(duì)象則不然。n類類 (class)，實(shí)例，實(shí)例 (instance)n具有相同屬性和服務(wù)的對(duì)象歸于同一類，具有相同屬性和服務(wù)的對(duì)象歸于同一類，形成類。形成類。n類中的對(duì)象為該類的實(shí)例。類中的對(duì)象為該類的實(shí)例。n同一類的實(shí)例同一類的實(shí)例n共享類的屬性和類的操作；共享類的屬性和類的操作；n通過繼承共享其父類的公共的和保護(hù)性的通過繼承

15、共享其父類的公共的和保護(hù)性的屬性和操作；屬性和操作；n同一類的不同實(shí)例有不同的屬性值。同一類的不同實(shí)例有不同的屬性值。四邊形類及其對(duì)象四邊形類及其對(duì)象屬性aPoint1 aPoint2aPoint3 aPoint4效勞效勞Draw( )move(x, y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)cont

16、ains(aPoint)效勞效勞效勞效勞quadrilateraln繼承繼承n派生類子類）：四邊形，三角形，派生類子類）：四邊形，三角形，n基類父類）：多邊形基類父類）：多邊形派生類派生類繼承的特性繼承的特性+特有的特性特有的特性基類基類多邊形多邊形四邊形四邊形三角形三角形六邊形六邊形n通信通信n消息傳遞消息傳遞nC+中消息傳遞的方式：中消息傳遞的方式：n定義：定義：Point p; void move(int x, inty);n使用：使用：p.move(x, y);nC中則不同，需使用函數(shù)調(diào)用方式：中則不同，需使用函數(shù)調(diào)用方式：n定義：定義：Point p; void move(Point

17、 q, int x, inty);n使用：使用：move(p, x, y); Draw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 類類referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子類的子類Quadrilateral類類Quadrilateral算法定義算法定義n定義：一個(gè)有窮的指令集，這些指令為解定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列n特性：特性：n輸入輸入 有有0

18、個(gè)或多個(gè)輸入個(gè)或多個(gè)輸入n輸出輸出 有一個(gè)或多個(gè)輸出有一個(gè)或多個(gè)輸出(處理結(jié)果處理結(jié)果)n確定性確定性 每步定義都是確切無歧義的每步定義都是確切無歧義的n有窮性有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束算法應(yīng)在執(zhí)行有窮步后結(jié)束n有效性有效性 每一條運(yùn)算應(yīng)足夠基本每一條運(yùn)算應(yīng)足夠基本n事例學(xué)習(xí)：選擇排序問題事例學(xué)習(xí)：選擇排序問題n明確問題：遞增排序明確問題：遞增排序n解決方案：逐個(gè)選擇最小數(shù)據(jù)解決方案：逐個(gè)選擇最小數(shù)據(jù)n算法框架：算法框架： for (int i = 0; i n-1; i+) /n-1趟趟 從從ai檢查到檢查到an-1; 若最小整數(shù)在若最小整數(shù)在ak, 交換交換ai與與ak;n n細(xì)化程

19、序：程序細(xì)化程序：程序 SelectSort 算法設(shè)計(jì)算法設(shè)計(jì) 自頂向下，逐步求精自頂向下，逐步求精 void selectSort ( int a , const int n ) /對(duì)對(duì)n個(gè)整數(shù)個(gè)整數(shù)a0,a1,an-1按遞增順序排序按遞增順序排序 for (int i = 0; i n-1; i+) int k = i; /從從ai查到查到an-1, 找最小整數(shù)找最小整數(shù), 在在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; 模板模板 (template)(template

20、)定義定義 適合多種數(shù)據(jù)類型的類定義或算法，在特適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過簡(jiǎn)單地代換，變成針對(duì)具體某定環(huán)境下通過簡(jiǎn)單地代換，變成針對(duì)具體某種數(shù)據(jù)類型的類定義或算法。種數(shù)據(jù)類型的類定義或算法。用模板定義用于排序的數(shù)據(jù)表類用模板定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H#define DATALIST_H#include /K是表項(xiàng)關(guān)鍵是表項(xiàng)關(guān)鍵碼類型碼類型template / /E是是表項(xiàng)類型表項(xiàng)類型class dataList private: E *element; int listSize; void swap (int m1, int m2); in

21、t minKey (int low, int high); public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& inList);

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

23、，函數(shù)返回其位置 int min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定義的重載操作定義的重載操作template ostream& operator (ostream& outStream, dataList outList) outStream “輸出數(shù)組內(nèi)容輸出數(shù)組內(nèi)容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream

24、 endl; ouStream “輸出數(shù)組當(dāng)前大小輸出數(shù)組當(dāng)前大小 : ” outList.listSize endl; return outStream; template istream& operator (istream& inStream, dataList inList) /輸入對(duì)象為輸入對(duì)象為inList，輸入流對(duì)象為，輸入流對(duì)象為inStream cout inList.listSize; cout “輸入數(shù)組元素值輸入數(shù)組元素值 : n”; for (int i = 0; i inList.listSize; i+) cout “元素元素” i inList.

25、elementi; return inStream; template void dataList : sort ( ) /按非遞減順序?qū)Π捶沁f減順序?qū)istSize個(gè)關(guān)鍵碼個(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); #endif 使用模板的選擇排序算法的主函數(shù)使用模板的選擇排序算法的主函數(shù) #include #include “dataList.h” const int SZ

26、 = 10; int main ( ) struct sick /患者患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ; dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; 定義對(duì)象時(shí)，代定義對(duì)象時(shí)，代入實(shí)際數(shù)據(jù)類型入實(shí)際數(shù)據(jù)類型重載友元操作重載友元操作標(biāo)準(zhǔn)標(biāo)準(zhǔn)IO操作操作消息通信消息通信算法簡(jiǎn)單性

27、能分析與度量算法簡(jiǎn)單性能分析與度量算法的性能標(biāo)準(zhǔn)算法的性能標(biāo)準(zhǔn)算法的后期測(cè)試算法的后期測(cè)試n對(duì)一個(gè)算法要作出全面的分析可分成兩個(gè)階對(duì)一個(gè)算法要作出全面的分析可分成兩個(gè)階段進(jìn)行，即事前分析和事后測(cè)試段進(jìn)行，即事前分析和事后測(cè)試n事前分析要求事前求出該算法的一個(gè)時(shí)間界事前分析要求事前求出該算法的一個(gè)時(shí)間界限函數(shù)。限函數(shù)。n事后測(cè)試則要求在算法執(zhí)行后通過算法執(zhí)行事后測(cè)試則要求在算法執(zhí)行后通過算法執(zhí)行的時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料來分析。的時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料來分析。n事后分析要求在算法中的某些部位插裝時(shí)間事后分析要求在算法中的某些部位插裝時(shí)間函數(shù)函數(shù) time ( )time ( )，測(cè)定算

28、法完成某一功能所，測(cè)定算法完成某一功能所花費(fèi)時(shí)間。花費(fèi)時(shí)間。例如，給出順序搜索例如，給出順序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在在a0,an-1中搜索與給定值中搜索與給定值 x 相等的元相等的元/素，函數(shù)返回其位置，失敗返回素，函數(shù)返回其位置，失敗返回-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i; 插裝 time( ) 的計(jì)時(shí)程序 double start, stop; time(&am

29、p;start); int k = seqsearch (a, n, x); time(&stop); double runTime = stop - start; cout n runTime endl;事實(shí)上，算法運(yùn)行時(shí)間要受輸入規(guī)模、利用編譯程序生成的目標(biāo)代碼的質(zhì)量、計(jì)算機(jī)程序指令系統(tǒng)的品質(zhì)和速度等制約。算法的事前估計(jì)算法的事前估計(jì)n算法的事前估計(jì)主要包括時(shí)間復(fù)雜性和空算法的事前估計(jì)主要包括時(shí)間復(fù)雜性和空間復(fù)雜性的分析：間復(fù)雜性的分析：n問題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)點(diǎn)問題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)點(diǎn)個(gè)數(shù)、被分類序列的正整數(shù)個(gè)數(shù)等。個(gè)數(shù)、被分類序列的正整數(shù)個(gè)數(shù)等。n時(shí)間復(fù)

30、雜性：算法所需時(shí)間和問題規(guī)模的時(shí)間復(fù)雜性：算法所需時(shí)間和問題規(guī)模的函數(shù)，記為函數(shù)，記為 T(n)T(n)。當(dāng)。當(dāng) n n 時(shí)的時(shí)間復(fù)時(shí)的時(shí)間復(fù)雜性，稱為漸進(jìn)時(shí)間復(fù)雜性。雜性，稱為漸進(jìn)時(shí)間復(fù)雜性。n空間復(fù)雜性：算法所需空間和問題規(guī)模的空間復(fù)雜性：算法所需空間和問題規(guī)模的函數(shù)。記為函數(shù)。記為 S(n)S(n)。當(dāng)。當(dāng) n n 時(shí)的時(shí)間復(fù)時(shí)的時(shí)間復(fù)雜性，稱為漸進(jìn)空間復(fù)雜性。雜性，稱為漸進(jìn)空間復(fù)雜性。空間復(fù)雜度度量空間復(fù)雜度度量時(shí)間復(fù)雜度度量時(shí)間復(fù)雜度度量n程序步確定方法程序步確定方法n插入計(jì)數(shù)全局變量插入計(jì)數(shù)全局變量countn建表，列出個(gè)語(yǔ)句的程序步建表，列出個(gè)語(yǔ)句的程序步例例 以迭代方式求累加和

31、的函數(shù)以迭代方式求累加和的函數(shù) float sum (float a , int n) float sum (float a , int n) float s = 0.0; float s = 0.0; for (int i = 0; i n; for (int i = 0; i n; i+)i+) s = s + ai; s = s + ai; return s; return s; 在求累加和程序中加入在求累加和程序中加入 count 語(yǔ)句語(yǔ)句 float sum (float a , int n) float s = 0.0; count+; /count 統(tǒng)計(jì)執(zhí)行語(yǔ)統(tǒng)計(jì)執(zhí)行語(yǔ)句條數(shù)句條

32、數(shù) for (int i = 0; i n; i+) count += 2; /針對(duì)針對(duì) for 語(yǔ)句語(yǔ)句s += ai;count+; /針對(duì)賦值語(yǔ)句針對(duì)賦值語(yǔ)句 count += 2; /針對(duì)針對(duì) for 的最后一的最后一次次 count+; /針對(duì)針對(duì) return 語(yǔ)句語(yǔ)句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序步數(shù) count = 3*n+4注意：注意： 一個(gè)語(yǔ)句本身的程序步數(shù)可能不等于該語(yǔ)一個(gè)語(yǔ)句本身的程序步數(shù)可能不等于該語(yǔ)句一次執(zhí)行所具有的程序步數(shù)。句一次執(zhí)行所具有的程序步數(shù)。 例如：例如：賦值語(yǔ)句賦值語(yǔ)句x = sum (R, n) 本身程序步數(shù)為本身程序步數(shù)為

33、 1；一次執(zhí)行對(duì)函數(shù)一次執(zhí)行對(duì)函數(shù) sum (R, n) 的調(diào)用需要的程序的調(diào)用需要的程序步數(shù)為步數(shù)為 3*n+4；一次執(zhí)行的程序步數(shù)為一次執(zhí)行的程序步數(shù)為 1+3*n+4 = 3*n+5計(jì)算累加和程序計(jì)算累加和程序程序步數(shù)計(jì)算工作表格程序步數(shù)計(jì)算工作表格時(shí)間復(fù)雜度的漸進(jìn)表示法時(shí)間復(fù)雜度的漸進(jìn)表示法例例 求兩個(gè)求兩個(gè)n階方陣的乘積階方陣的乘積C = ABvoid 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

34、 for (int k = 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 3n3 + 5n2 + 4n +2時(shí)間復(fù)雜度的漸進(jìn)表示法時(shí)間復(fù)雜度的漸進(jìn)表示法n算法中所有語(yǔ)句的頻度之和是矩陣階數(shù)算法中所有語(yǔ)句的頻度之和是矩陣階數(shù)n的的函數(shù)函數(shù)n T(n) = 3n3 + 5n2 + 4n +2n一般地，稱一般地，稱 n 是問題的規(guī)模。則時(shí)間復(fù)雜是問題的規(guī)模。則時(shí)間復(fù)雜度度 T(n) 是問題規(guī)模是問題規(guī)模 n 的函數(shù)。的函數(shù)。n當(dāng)當(dāng)n趨于無窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級(jí)趨于無窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級(jí)階稱為算法的漸進(jìn)時(shí)間復(fù)雜度階稱為算法的漸進(jìn)時(shí)間復(fù)雜度n

35、 T(n) = O(n3) 大大O表示法表示法n加法規(guī)則加法規(guī)則 針對(duì)并列程序段針對(duì)并列程序段 n T(n, m) = T1 (n) + T2 (m)n = O(max (f (n), g (m)n各種函數(shù)的增長(zhǎng)趨勢(shì)各種函數(shù)的增長(zhǎng)趨勢(shì) n c log2n n nlog2n n2 n3 2n 3n n!T(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(n

36、2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;n乘法規(guī)則乘法規(guī)則 針對(duì)嵌套程序段針對(duì)嵌套程序段n T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)n漸進(jìn)的空間復(fù)雜度漸進(jìn)的空間復(fù)雜度n S (n) = O(f (n)n兩個(gè)并列循環(huán)的例子兩個(gè)并列循環(huán)的例子 void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行中各行 sumi = 0.0; /數(shù)據(jù)累加數(shù)據(jù)累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行數(shù)據(jù)和打印各行數(shù)據(jù)和 cout i “ : ” sum i endl; 漸進(jìn)時(shí)間復(fù)雜度為漸進(jìn)時(shí)間復(fù)雜度為 O(max (m*n, m)起泡排序起泡排序 void bubbleSort (int a , int n ) /對(duì)表對(duì)表 a 逐趟比較逐趟比較, n 是表當(dāng)前長(zhǎng)度是表當(dāng)前長(zhǎng)度 for (int i