版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、1第一章第一章 數(shù)據(jù)結構數(shù)據(jù)結構(sh j (sh j ji u)ji u)概念概念第1頁/共72頁第一頁,共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 宮宮 力力 男男
2、 北北 京京 1981.01 8 98310 蔡曉莉蔡曉莉 女女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.12第2頁/共72頁第二頁,共72頁。3 課程編號課程編號 課課 程程 名名 學時學時 024002 程序設計基礎程序設計基礎 64 024010 匯編語言匯編語言 48 024016 計算機原理計算機原理 64 024020 數(shù)據(jù)結構數(shù)據(jù)結構 64 024021 微機技術微機技術 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 48第3頁/共72頁第三頁,共72頁。4學生學生( (學號學號, ,姓名姓名(xngm
3、ng),(xngmng),性別性別, ,籍籍貫貫) )課程課程(kchng)(kchng)( (課程課程(kchng)(kchng)號號, ,課課程程(kchng)(kchng)名名, ,學分學分) )選課選課( (學號學號, ,課程課程(kchng)(kchng)號號, ,成績成績) )第4頁/共72頁第四頁,共72頁。5UNIX文件系統(tǒng)文件系統(tǒng)(xtng)的系統(tǒng)的系統(tǒng)(xtng)結構圖結構圖/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第5頁/共72頁第五頁,共72頁。6數(shù)據(jù)數(shù)據(jù)(shj)(shj)(data
4、data)數(shù)據(jù)是信息的載體,是描述客觀事物數(shù)據(jù)是信息的載體,是描述客觀事物(k un sh w)的數(shù)、字符、以及所有能輸入到計算的數(shù)、字符、以及所有能輸入到計算機中,被計算機程序識別和處理的符號的集合。機中,被計算機程序識別和處理的符號的集合。數(shù)據(jù)的分類:數(shù)據(jù)的分類: 數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)第6頁/共72頁第六頁,共72頁。7姓名姓名 所在院系所在院系 性別性別 出生日期出生日期 年年 月月職務職務 業(yè)績業(yè)績數(shù)據(jù)數(shù)據(jù)(shj)(shj)元素元素 (data element) (data element)n數(shù)據(jù)的基本單位。在計算機程序中常作為一個數(shù)據(jù)的基本單位。在計算機程
5、序中常作為一個整體進行考慮和處理。整體進行考慮和處理。n有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項 (Data (Data Item)Item)組成。數(shù)據(jù)項是具有獨立含義組成。數(shù)據(jù)項是具有獨立含義(hny)(hny)的最小標識單位。的最小標識單位。n數(shù)據(jù)元素又稱為元素、結點、記錄。數(shù)據(jù)元素又稱為元素、結點、記錄。第7頁/共72頁第七頁,共72頁。8什么什么(shn me)是數(shù)據(jù)結構是數(shù)據(jù)結構定義定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有由某一數(shù)據(jù)元素的集合以及該集合中所有(suyu)數(shù)據(jù)元素之間的關系組成。記為:數(shù)據(jù)元素之間的關系組成。記為: Data_Structur
6、e = D, R 其中,其中,D 是某一數(shù)據(jù)元素的集合,是某一數(shù)據(jù)元素的集合,R 是該集是該集合中所有合中所有(suyu)數(shù)據(jù)元素之間的關系的有限集數(shù)據(jù)元素之間的關系的有限集合。合。第8頁/共72頁第八頁,共72頁。9例:例:N N 個網(wǎng)點之間的連通個網(wǎng)點之間的連通(lintng)(lintng)關系關系 156152436243第9頁/共72頁第九頁,共72頁。10數(shù)據(jù)數(shù)據(jù)(shj)結構是數(shù)據(jù)結構是數(shù)據(jù)(shj)的組織形式的組織形式n包括三個方面:包括三個方面:n數(shù)據(jù)元素間的邏輯關系,即數(shù)據(jù)的邏輯結構;數(shù)據(jù)元素間的邏輯關系,即數(shù)據(jù)的邏輯結構;n數(shù)據(jù)元素及其關系在計算機存儲數(shù)據(jù)元素及其關系在計
7、算機存儲(cn ch)內的內的表示,即數(shù)據(jù)的存儲表示,即數(shù)據(jù)的存儲(cn ch)表示;表示;n數(shù)據(jù)的運算,即對數(shù)據(jù)元素施加的操作。數(shù)據(jù)的運算,即對數(shù)據(jù)元素施加的操作。第10頁/共72頁第十頁,共72頁。11數(shù)據(jù)的邏輯數(shù)據(jù)的邏輯(lu j)結構結構n數(shù)據(jù)的邏輯結構從邏輯關系上描述數(shù)據(jù),與數(shù)數(shù)據(jù)的邏輯結構從邏輯關系上描述數(shù)據(jù),與數(shù)據(jù)的存儲無關;據(jù)的存儲無關;n數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)據(jù)模型;來的數(shù)據(jù)模型;n數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素(yun s)本身的本身的形式、內容無關;形式、內容無關;n數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素
8、數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素(yun s)的相對的相對存儲位置無關。存儲位置無關。第11頁/共72頁第十一頁,共72頁。12數(shù)據(jù)數(shù)據(jù)(shj)的邏輯結的邏輯結構分類構分類n線性結構線性結構(jigu)n 線性表線性表n非線性結構非線性結構(jigu)n 樹樹n 圖(或網(wǎng)絡)圖(或網(wǎng)絡)第12頁/共72頁第十二頁,共72頁。13線性結構線性結構(jigu)樹形結構樹形結構(jigu)樹樹 二叉樹二叉樹 二叉搜索二叉搜索(su (su su)su)樹樹bindevetclibuser14131211234567891031587101199874566231311第13頁/共72頁第十三頁,共72頁。
9、14堆結構堆結構(jigu)123548711102916410121151236987第14頁/共72頁第十四頁,共72頁。15圖結構圖結構(jigu) (jigu) 網(wǎng)絡結構網(wǎng)絡結構(jigu)(jigu)12543611331814665161921125634第15頁/共72頁第十五頁,共72頁。16數(shù)據(jù)的存儲數(shù)據(jù)的存儲(cn ch)結構結構n數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實現(xiàn);現(xiàn);n數(shù)據(jù)的存儲結構依賴于計算機語言。數(shù)據(jù)的存儲結構依賴于計算機語言。n 順序存儲表示順序存儲表示n 鏈接鏈接(lin ji)存儲表示存儲表示n 索引存儲表示索引
10、存儲表示n 散列存儲表示散列存儲表示主要主要(zhyo)用于用于內存的存儲表示內存的存儲表示主要用于外存主要用于外存 (文文件件) 的存儲表示的存儲表示第16頁/共72頁第十六頁,共72頁。17抽象數(shù)據(jù)類型及面向對象概念抽象數(shù)據(jù)類型及面向對象概念(ginin)數(shù)據(jù)類型數(shù)據(jù)類型 定義:一組性質相同的值的集合定義:一組性質相同的值的集合(jh), 以及定義于這個值集合以及定義于這個值集合(jh)上的一上的一組操作的總稱組操作的總稱.C語言中的數(shù)據(jù)類型語言中的數(shù)據(jù)類型 char int float double void 字符型字符型 整型整型 浮點型浮點型 雙精度型雙精度型 無值無值 第17頁/共
11、72頁第十七頁,共72頁。18n構造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構造數(shù)據(jù)類構造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構造數(shù)據(jù)類型組成。型組成。n構造數(shù)據(jù)類型由不同成分類型構成。構造數(shù)據(jù)類型由不同成分類型構成。n基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結構。數(shù)據(jù)結構。n數(shù)據(jù)類型就是數(shù)據(jù)結構,不過它是從編程者數(shù)據(jù)類型就是數(shù)據(jù)結構,不過它是從編程者的角度來使用的。的角度來使用的。n數(shù)據(jù)類型是模板,必須定義屬于某種數(shù)據(jù)類數(shù)據(jù)類型是模板,必須定義屬于某種數(shù)據(jù)類型的變量型的變量(binling),才能參加運算。,才能參加運算。 第18頁/共72頁第十八頁,共72頁。19抽象數(shù)據(jù)類型抽
12、象數(shù)據(jù)類型 (ADTs: Abstract Data Types)(ADTs: Abstract Data Types)抽象數(shù)據(jù)類型是由用戶定義,用以表示應抽象數(shù)據(jù)類型是由用戶定義,用以表示應用問題的數(shù)據(jù)模型。用問題的數(shù)據(jù)模型。特點是:信息隱蔽和數(shù)據(jù)封裝,使用與實特點是:信息隱蔽和數(shù)據(jù)封裝,使用與實現(xiàn)相分離。現(xiàn)相分離。抽象數(shù)據(jù)類型可用(抽象數(shù)據(jù)類型可用(D, S, P)三元組表示,)三元組表示,其中,其中,D 是數(shù)據(jù)元素是數(shù)據(jù)元素(yun s)的集合(簡的集合(簡稱數(shù)據(jù)對象),稱數(shù)據(jù)對象),S 是是 D上的關系集合,上的關系集合,P 是對是對 D 的基本操作集合。的基本操作集合。 第19頁/共
13、72頁第十九頁,共72頁。20抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找查找 登錄登錄 刪除刪除 修改修改 符符 號號 表表第20頁/共72頁第二十頁,共72頁。21抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型的描述(mio sh)其中數(shù)據(jù)對象、數(shù)據(jù)之間的關系其中數(shù)據(jù)對象、數(shù)據(jù)之間的關系(gun x)用偽碼描述;基本操作定義格式為用偽碼描述;基本操作定義格式為ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象數(shù)據(jù)對象(duxing):數(shù)據(jù)對象:數(shù)據(jù)對象(duxing)的定義的定義 數(shù)據(jù)關系:數(shù)據(jù)關系的定義數(shù)據(jù)關系:數(shù)據(jù)關系的定義 基本操作:基本操作的定義基本操作:基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名基本操作名
14、(參數(shù)表)基本操作名(參數(shù)表)前置條件:前置條件:先決條件描述先決條件描述后置條件:后置條件:操作結果描述操作結果描述第21頁/共72頁第二十一頁,共72頁。22基本操作有兩種參數(shù):賦值參數(shù)只為操作提基本操作有兩種參數(shù):賦值參數(shù)只為操作提供輸入值;引用參數(shù)以供輸入值;引用參數(shù)以&打頭,除可提供輸打頭,除可提供輸入值外,還將返回操作結果。入值外,還將返回操作結果。 “前置條件前置條件”描述了操作執(zhí)行之前數(shù)據(jù)結構描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的先決條件,若不滿足,則操和參數(shù)應滿足的先決條件,若不滿足,則操作失敗,并返回相應出錯作失敗,并返回相應出錯(ch cu)信息。信息。 “后置條件后置
15、條件”說明了操作正常完成之后,數(shù)說明了操作正常完成之后,數(shù)據(jù)結構的變化狀況和應返回的結果。若前置據(jù)結構的變化狀況和應返回的結果。若前置條件為空,則省略之。條件為空,則省略之。第22頁/共72頁第二十二頁,共72頁。23自然數(shù)的抽象數(shù)據(jù)類型定義自然數(shù)的抽象數(shù)據(jù)類型定義(dngy)ADT NaturalNumber isobjects: 一個整數(shù)的有序子集合一個整數(shù)的有序子集合,它開始于它開始于0, 結束結束(jish)于機器能表示的最大整數(shù)于機器能表示的最大整數(shù)(MaxInt)。Function: 對于所有的對于所有的 x, y NaturalNumber; False, True Boolea
16、n, +、-、=、= 等都是等都是可用的服務??捎玫姆?。 Zero( ) : NaturalNumber /前置條件:無前置條件:無 /后置條件:返回自然數(shù)后置條件:返回自然數(shù)0 第23頁/共72頁第二十三頁,共72頁。24 Subtract (x, y) : NaturalNumber /前置條件前置條件(tiojin): x, y為為NaturalNumber且且xy /后置條件后置條件(tiojin):返回:返回 x- y第24頁/共72頁第二十四頁,共72頁。25第25頁/共72頁第二十五頁,共72頁。26面向對象的概念面向對象的概念(ginin)n面向對象面向對象 = = 對象類繼
17、承通信對象類繼承通信n對象對象n在應用問題中出現(xiàn)的各種實體、事件、規(guī)格說在應用問題中出現(xiàn)的各種實體、事件、規(guī)格說明等。明等。n由一組屬性值和在這組值上的一組服務(或稱由一組屬性值和在這組值上的一組服務(或稱操作)構成。操作)構成。n與與C C中構造數(shù)據(jù)類型不同在于:中構造數(shù)據(jù)類型不同在于:C C中的構造數(shù)據(jù)中的構造數(shù)據(jù)類型的變量僅涉及類型的變量僅涉及(shj)(shj)屬性值,與操作屬性值,與操作分離,而分離,而C+C+中的對象則不然。中的對象則不然。第26頁/共72頁第二十六頁,共72頁。27n類類 (class),實例,實例(shl) (instance)n具有相同屬性和服務的對象歸于同一
18、類,具有相同屬性和服務的對象歸于同一類,形成類。形成類。n類中的對象為該類的實例類中的對象為該類的實例(shl)。n同一類的實例同一類的實例(shl)n共享類的屬性和類的操作;共享類的屬性和類的操作;n通過繼承共享其父類的公共的和保護性的通過繼承共享其父類的公共的和保護性的屬性和操作;屬性和操作;n同一類的不同實例同一類的不同實例(shl)有不同的屬性值。有不同的屬性值。第27頁/共72頁第二十七頁,共72頁。28四邊形類及其對象四邊形類及其對象(duxing)屬性aPoint1 aPoint2aPoint3 aPoint4服務服務Draw( )move(x, y)contains(aPoin
19、t)屬性值屬性值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)contains(aPoint)服務服務服務服務quadrilateral第28頁/共72頁第二十八頁,共72頁。29n繼承繼承(jchng)n派生類(子類):四邊形,三角形,派生類(子類):四邊形,三角形,n基類(父類):多邊形基類(父類):多邊形派生類派生類繼承的特性繼承的特性+特有的特
20、性特有的特性基類基類多邊形多邊形四邊形四邊形三角形三角形六邊形六邊形第29頁/共72頁第二十九頁,共72頁。30n通信通信n消息傳遞消息傳遞nC+中消息傳遞的方式:中消息傳遞的方式:n定義:定義:Point p; void move(int x, inty);n使用使用(shyng):p.move(x, y);nC中則不同,需使用中則不同,需使用(shyng)函數(shù)調用方式:函數(shù)調用方式:n定義:定義:Point p; void move(Point q, int x, inty);n使用使用(shyng):move(p, x, y); 第30頁/共72頁第三十頁,共72頁。31Draw( )m
21、ove(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 類類referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子類的子類Quadrilateral類類Quadrilateral第31頁/共72頁第三十一頁,共72頁。32算法算法(sun f)定定義義定義:一個有窮的指令集,這些定義:一個有窮的指令集,這些(zhxi)指令為解決某一特定任務規(guī)定了一個運算指令為解決某一特定任務規(guī)定了一個運算序列序列特性:特性:輸入輸入 有有0個或多個輸入個或多個輸入輸出輸
22、出 有一個或多個輸出有一個或多個輸出(處理結果處理結果)確定性確定性 每步定義都是確切無歧義的每步定義都是確切無歧義的有窮性有窮性 算法應在執(zhí)行有窮步后結束算法應在執(zhí)行有窮步后結束有效性有效性 每一條運算應足夠基本每一條運算應足夠基本第32頁/共72頁第三十二頁,共72頁。33事例學習:選擇排序問題事例學習:選擇排序問題明確問題:遞增排序明確問題:遞增排序解決方案:逐個選擇最小數(shù)據(jù)解決方案:逐個選擇最小數(shù)據(jù)算法框架:算法框架: for (int i = 0; i n-1; i+) /n-1趟趟 從從ai檢查檢查(jinch)到到an-1; 若最小整數(shù)在若最小整數(shù)在ak, 交換交換ai與與ak;
23、 細化程序:程序細化程序:程序 SelectSort 算法算法(sun f)(sun f)設計設計 自頂向下,逐步求精自頂向下,逐步求精 第33頁/共72頁第三十三頁,共72頁。34 void selectSort ( int a , const int n ) /對對n個整數(shù)個整數(shù)a0,a1,an-1按遞增按遞增(dzng)順序排順序排序序 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 = a
24、i; ai = ak; ak = temp; 第34頁/共72頁第三十四頁,共72頁。35模板模板(mbn) (mbn) (template)(template)定義定義 適合多種數(shù)據(jù)類型的類定義或算法,在特適合多種數(shù)據(jù)類型的類定義或算法,在特定環(huán)境下通過簡單定環(huán)境下通過簡單(jindn)(jindn)地代換,變地代換,變成針對具體某種數(shù)據(jù)類型的類定義或算法。成針對具體某種數(shù)據(jù)類型的類定義或算法。第35頁/共72頁第三十五頁,共72頁。36用模板定義用模板定義(dngy)用于排序的數(shù)據(jù)表用于排序的數(shù)據(jù)表類類#ifndef DATALIST_H#define DATALIST_H#include
25、 /K是表項關鍵是表項關鍵碼類型碼類型template / /E是是表項類型表項類型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);第36頁/共72頁第三十六頁,共72頁。37 public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ost
26、ream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& inList); ; #endif 第37頁/共72頁第三十七頁,共72頁。38類中所有類中所有(suyu)操作作為模板函數(shù)的實現(xiàn)操作作為模板函數(shù)的實現(xiàn)template void dataList : swap (int m1, int m2) /交換由交換由m1, m2為下標的數(shù)組元素的值為下標的數(shù)組元素的值 E temp = element m1; element m1
27、= element m2; element m2 = temp; ;第38頁/共72頁第三十八頁,共72頁。39template int dataList:minKey (int low, int high) /查找數(shù)組查找數(shù)組Elementlow到到Elementhigh中具中具/有最小關鍵碼值的表項,函數(shù)返回有最小關鍵碼值的表項,函數(shù)返回(fnhu)其位其位置置 int min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定義的重載定義的重載(zhn zi)操
28、作操作第39頁/共72頁第三十九頁,共72頁。40template ostream& operator (ostream& outStream, dataList outList) outStream “輸出輸出(shch)數(shù)組內容數(shù)組內容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream endl; ouStream “輸出輸出(shch)數(shù)組當前大小數(shù)組當前大小 : ” outList.listSize endl; return outStream; 第40頁/共72頁第四
29、十頁,共72頁。41 template istream& operator (istream& inStream, dataList inList) /輸入輸入(shr)對象為對象為inList,輸入,輸入(shr)流對象流對象為為inStream cout inList.listSize; cout “輸入輸入(shr)數(shù)組元素值數(shù)組元素值 : n”; for (int i = 0; i inList.listSize; i+) cout “元素元素” i inList.elementi; return inStream; 第41頁/共72頁第四十一頁,共72頁。42template voi
30、d dataList : sort ( ) /按非遞減順序按非遞減順序(shnx)對對listSize個關鍵碼個關鍵碼element0到到/elementArraySize-1排序排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i); #endif 第42頁/共72頁第四十二頁,共72頁。43使用模板使用模板(mbn)的選擇排序算法的主函數(shù)的選擇排序算法的主函數(shù) #include #include “dataList.h” const int SZ = 10;
31、 int main ( ) struct sick /患者患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ; 第43頁/共72頁第四十三頁,共72頁。44 dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; 定義定義(dngy)對象對象時,代入實際數(shù)時,代入實際數(shù)據(jù)類型據(jù)類型重載重載(zhn zi)
32、友元操作友元操作標準標準(biozhn)IO操作操作消息通信消息通信第44頁/共72頁第四十四頁,共72頁。45算法算法(sun f)簡單性能分簡單性能分析與度量析與度量第45頁/共72頁第四十五頁,共72頁。46算法算法(sun f)的的性能標準性能標準應對其作出反應,而不應產(chǎn)生莫名其妙的應對其作出反應,而不應產(chǎn)生莫名其妙的輸出結果。輸出結果。第46頁/共72頁第四十六頁,共72頁。47算法算法(sun f)的后的后期測試期測試對一個算法要作出全面的分析可分成兩個對一個算法要作出全面的分析可分成兩個階段進行,即事前分析和事后測試階段進行,即事前分析和事后測試事前分析要求事前求出該算法的一個時
33、間事前分析要求事前求出該算法的一個時間界限函數(shù)。界限函數(shù)。事后測試則要求在算法執(zhí)行后通過算法執(zhí)事后測試則要求在算法執(zhí)行后通過算法執(zhí)行的時間和實際占用空間的統(tǒng)計資料來分行的時間和實際占用空間的統(tǒng)計資料來分析。析。事后分析要求在算法中的某些部位事后分析要求在算法中的某些部位(bwi)(bwi)插裝時間函數(shù)插裝時間函數(shù) time ( ) time ( ),測定,測定算法完成某一功能所花費時間。算法完成某一功能所花費時間。第47頁/共72頁第四十七頁,共72頁。48例如,給出順序搜索例如,給出順序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int
34、n, int x ) /在在a0,an-1中搜索與給定值中搜索與給定值 x 相等的元相等的元/素,函數(shù)素,函數(shù)(hnsh)返回其位置,失敗返回返回其位置,失敗返回-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i;第48頁/共72頁第四十八頁,共72頁。49 插裝 time( ) 的計時程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&stop); double runTime = stop - sta
35、rt; cout n runTime endl;事實上,算法運行時間要受輸入規(guī)模、利用編譯程序生成(shn chn)的目標代碼的質量、計算機程序指令系統(tǒng)的品質和速度等制約。第49頁/共72頁第四十九頁,共72頁。50算法的事前算法的事前(shqin)估計估計算法的事前估計主要包括時間算法的事前估計主要包括時間(shjin)(shjin)復雜性和空間復雜性的分析:復雜性和空間復雜性的分析:問題的規(guī)模:如:矩陣的階數(shù)、圖的結點個問題的規(guī)模:如:矩陣的階數(shù)、圖的結點個數(shù)、被分類序列的正整數(shù)個數(shù)等。數(shù)、被分類序列的正整數(shù)個數(shù)等。時間時間(shjin)(shjin)復雜性:算法所需時間復雜性:算法所需時
36、間(shjin)(shjin)和問題規(guī)模的函數(shù),記為和問題規(guī)模的函數(shù),記為 T(n) T(n)。當當 n n 時的時間時的時間(shjin)(shjin)復雜性,復雜性,稱為漸進時間稱為漸進時間(shjin)(shjin)復雜性。復雜性??臻g復雜性:算法所需空間和問題規(guī)模的函空間復雜性:算法所需空間和問題規(guī)模的函數(shù)。記為數(shù)。記為 S(n) S(n)。當。當 n n 時的時間時的時間(shjin)(shjin)復雜性,稱為漸進空間復雜性。復雜性,稱為漸進空間復雜性。第50頁/共72頁第五十頁,共72頁。51空間空間(kngjin)復雜度度量復雜度度量第51頁/共72頁第五十一頁,共72頁。52時
37、間時間(shjin)復雜度度復雜度度量量第52頁/共72頁第五十二頁,共72頁。53n程序步確定程序步確定(qudng)方法方法n插入計數(shù)全局變量插入計數(shù)全局變量countn建表,列出個語句的程序步建表,列出個語句的程序步例例 以迭代以迭代(di di)(di di)方式求累加和的方式求累加和的函數(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;
38、s = s + ai; return s; return s; 第53頁/共72頁第五十三頁,共72頁。54在求累加和程序中加入在求累加和程序中加入(jir) count 語句語句 float sum (float a , int n) float s = 0.0; count+; /count 統(tǒng)計執(zhí)行語統(tǒng)計執(zhí)行語句條數(shù)句條數(shù) for (int i = 0; i n; i+) count += 2; /針對針對 for 語句語句s += ai;count+; /針對賦值語句針對賦值語句 count += 2; /針對針對 for 的最后一的最后一次次 count+; /針對針對 return
39、 語句語句 return s; 執(zhí)行結束得執(zhí)行結束得 程序步數(shù)程序步數(shù) count = 3*n+4第54頁/共72頁第五十四頁,共72頁。55第55頁/共72頁第五十五頁,共72頁。56注意:注意: 一個語句本身的程序一個語句本身的程序(chngx)步數(shù)可能不等步數(shù)可能不等于該語句一次執(zhí)行所具有的程序于該語句一次執(zhí)行所具有的程序(chngx)步數(shù)。步數(shù)。 例如:例如:賦值語句賦值語句x = sum (R, n) 本身程序本身程序(chngx)步數(shù)為步數(shù)為 1;一次執(zhí)行對函數(shù)一次執(zhí)行對函數(shù) sum (R, n) 的調用需要的程序的調用需要的程序(chngx)步數(shù)為步數(shù)為 3*n+4;一次執(zhí)行的程
40、序一次執(zhí)行的程序(chngx)步數(shù)為步數(shù)為 1+3*n+4 = 3*n+5第56頁/共72頁第五十六頁,共72頁。57計算累加和程序計算累加和程序(chngx)程序程序(chngx)步數(shù)計算工作步數(shù)計算工作表格表格第57頁/共72頁第五十七頁,共72頁。58時間時間(shjin)復雜度的漸進復雜度的漸進表示法表示法例例 求兩個求兩個(lin )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+
41、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頁第五十八頁,共72頁。59時間時間(shjin)復雜度的漸進表復雜度的漸進表示法示法算法中所有算法中所有(suyu)語句的頻度之和是矩陣階語句的頻度之和是矩陣階數(shù)數(shù)n的函數(shù)的函數(shù) T(n) = 3n3 + 5n2 + 4n +2一般地,稱一般地,稱 n 是問題的規(guī)模。則時間復雜度是問題的規(guī)模。則時間復雜度 T(n) 是問題規(guī)模是問題規(guī)模 n 的函數(shù)。的函數(shù)。當當n趨于無窮大時,把時間復雜度的數(shù)量
42、級趨于無窮大時,把時間復雜度的數(shù)量級(階)稱為算法的漸進時間復雜度(階)稱為算法的漸進時間復雜度 T(n) = O(n3) 大大O表示法表示法第59頁/共72頁第五十九頁,共72頁。60加法規(guī)則加法規(guī)則 針對并列針對并列(bngli)程序段程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)各種函數(shù)的增長趨勢各種函數(shù)的增長趨勢 c log2n n nlog2n n2 n3 2n 3n n!第60頁/共72頁第六十頁,共72頁。61T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for
43、 ( 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頁第六十一頁,共72頁。62乘法規(guī)則乘法規(guī)則 針對嵌套程序段針對嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)漸進漸進(jinjn)的空間復雜度的空間復雜度 S (n) = O(f (n)兩個并列循環(huán)的例子兩個并列循環(huán)的例子第62頁/共72頁第六十二頁,共7
44、2頁。63 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; 漸進漸進(jinjn)時間復雜度為時間復雜度為 O(max (m*n, m)第63頁/共72頁第六十三頁,共72頁。64起泡排序起泡排序 void bubbleSort (int a , int n ) /對表對表 a 逐趟比較逐趟比較, n 是表當前是表當
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 廣東廣東省通信管理局局屬事業(yè)單位招聘筆試歷年典型考點(頻考版試卷)附帶答案詳解版
- 廣東2024年南方醫(yī)科大學南方醫(yī)院招聘專業(yè)技術人員筆試歷年典型考點(頻考版試卷)附帶答案詳解
- 2024年03月重慶市西南證券股份有限公司招考筆試歷年參考題庫附帶答案詳解
- 2024年中國補虛膠囊市場調查研究報告
- 2024年特聘金融顧問服務協(xié)議書3篇
- 唐山2025年河北唐山市路北區(qū)赴高校選聘55名教師筆試歷年典型考點(頻考版試卷)附帶答案詳解
- 2025年度淋浴房產(chǎn)品國際市場推廣合作協(xié)議3篇
- 2024年生物質鍋爐購銷協(xié)議
- 2025版勞動合同主體變更及員工帶薪休假協(xié)議3篇
- 2025版電影劇本創(chuàng)作人員全權聘用合同范本3篇
- 2025蛇年春節(jié)春聯(lián)對聯(lián)帶橫批(276副)
- 2024年時事政治試題【有答案】
- 全套教學課件《工程倫理學》
- 人音版六年級上冊全冊音樂教案(新教材)
- 2024年認證行業(yè)法律法規(guī)及認證基礎知識
- 機械原理課程設計鎖梁自動成型機床切削機構
- MT 285-1992縫管錨桿
- CRAC無線電技術觀摩交流大會業(yè)余無線電應急通信演練基本規(guī)則
- 消防安全重點單位檔案(參考)
- 35KV降壓變電所一次系統(tǒng)電氣設計(可編輯)
- TL494組成的200W逆變器電路圖
評論
0/150
提交評論