




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1第一章第一章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j (sh j ji u)ji u)概念概念第1頁/共72頁第一頁,共72頁。2 學(xué)學(xué) 號號 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 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 課程編號課程編號 課課 程程 名名 學(xué)時學(xué)時 024002 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ) 64 024010 匯編語言匯編語言 48 024016 計算機(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ù)庫原理數(shù)據(jù)庫原理 48第3頁/共72頁第三頁,共72頁。4學(xué)生學(xué)生( (學(xué)號學(xué)號, ,姓名姓名(xngm
3、ng),(xngmng),性別性別, ,籍籍貫貫) )課程課程(kchng)(kchng)( (課程課程(kchng)(kchng)號號, ,課課程程(kchng)(kchng)名名, ,學(xué)分學(xué)分) )選課選課( (學(xué)號學(xué)號, ,課程課程(kchng)(kchng)號號, ,成績成績) )第4頁/共72頁第四頁,共72頁。5UNIX文件系統(tǒng)文件系統(tǒng)(xtng)的系統(tǒng)的系統(tǒng)(xtng)結(jié)構(gòu)圖結(jié)構(gòu)圖/ (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ù)、字符、以及所有能輸入到計算機(jī)中,被計算機(jī)程序識別和處理的符號的集合。機(jī)中,被計算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)的分類:數(shù)據(jù)的分類: 數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)第6頁/共72頁第六頁,共72頁。7姓名姓名 所在院系所在院系 性別性別 出生日期出生日期 年年 月月職務(wù)職務(wù) 業(yè)績業(yè)績數(shù)據(jù)數(shù)據(jù)(shj)(shj)元素元素 (data element) (data element)n數(shù)據(jù)的基本單位。在計算機(jī)程序中常作為一個數(shù)據(jù)的基本單位。在計算機(jī)程
5、序中常作為一個整體進(jìn)行考慮和處理。整體進(jìn)行考慮和處理。n有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項 (Data (Data Item)Item)組成。數(shù)據(jù)項是具有獨立含義組成。數(shù)據(jù)項是具有獨立含義(hny)(hny)的最小標(biāo)識單位。的最小標(biāo)識單位。n數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。第7頁/共72頁第七頁,共72頁。8什么什么(shn me)是數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)定義定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有由某一數(shù)據(jù)元素的集合以及該集合中所有(suyu)數(shù)據(jù)元素之間的關(guān)系組成。記為:數(shù)據(jù)元素之間的關(guān)系組成。記為: Data_Structur
6、e = D, R 其中,其中,D 是某一數(shù)據(jù)元素的集合,是某一數(shù)據(jù)元素的集合,R 是該集是該集合中所有合中所有(suyu)數(shù)據(jù)元素之間的關(guān)系的有限集數(shù)據(jù)元素之間的關(guān)系的有限集合。合。第8頁/共72頁第八頁,共72頁。9例:例:N N 個網(wǎng)點之間的連通個網(wǎng)點之間的連通(lintng)(lintng)關(guān)系關(guān)系 156152436243第9頁/共72頁第九頁,共72頁。10數(shù)據(jù)數(shù)據(jù)(shj)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)(shj)的組織形式的組織形式n包括三個方面:包括三個方面:n數(shù)據(jù)元素間的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu);數(shù)據(jù)元素間的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu);n數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲數(shù)據(jù)元素及其關(guān)系在計
7、算機(jī)存儲(cn ch)內(nèi)的內(nèi)的表示,即數(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)結(jié)構(gòu)結(jié)構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù),與數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù),與數(shù)據(jù)的存儲無關(guān);據(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ù)元素(yun s)本身的本身的形式、內(nèi)容無關(guān);形式、內(nèi)容無關(guān);n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素
8、數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素(yun s)的相對的相對存儲位置無關(guān)。存儲位置無關(guān)。第11頁/共72頁第十一頁,共72頁。12數(shù)據(jù)數(shù)據(jù)(shj)的邏輯結(jié)的邏輯結(jié)構(gòu)分類構(gòu)分類n線性結(jié)構(gòu)線性結(jié)構(gòu)(jigu)n 線性表線性表n非線性結(jié)構(gòu)非線性結(jié)構(gòu)(jigu)n 樹樹n 圖(或網(wǎng)絡(luò))圖(或網(wǎng)絡(luò))第12頁/共72頁第十二頁,共72頁。13線性結(jié)構(gòu)線性結(jié)構(gòu)(jigu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)(jigu)樹樹 二叉樹二叉樹 二叉搜索二叉搜索(su (su su)su)樹樹bindevetclibuser14131211234567891031587101199874566231311第13頁/共72頁第十三頁,共72頁。
9、14堆結(jié)構(gòu)堆結(jié)構(gòu)(jigu)123548711102916410121151236987第14頁/共72頁第十四頁,共72頁。15圖結(jié)構(gòu)圖結(jié)構(gòu)(jigu) (jigu) 網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)(jigu)(jigu)12543611331814665161921125634第15頁/共72頁第十五頁,共72頁。16數(shù)據(jù)的存儲數(shù)據(jù)的存儲(cn ch)結(jié)構(gòu)結(jié)構(gòu)n數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的實數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn);現(xiàn);n數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機(jī)語言。數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機(jī)語言。n 順序存儲表示順序存儲表示n 鏈接鏈接(lin ji)存儲表示存儲表示n 索引存儲表示索引
10、存儲表示n 散列存儲表示散列存儲表示主要主要(zhyo)用于用于內(nèi)存的存儲表示內(nèi)存的存儲表示主要用于外存主要用于外存 (文文件件) 的存儲表示的存儲表示第16頁/共72頁第十六頁,共72頁。17抽象數(shù)據(jù)類型及面向?qū)ο蟾拍畛橄髷?shù)據(jù)類型及面向?qū)ο蟾拍?ginin)數(shù)據(jù)類型數(shù)據(jù)類型 定義:一組性質(zhì)相同的值的集合定義:一組性質(zhì)相同的值的集合(jh), 以及定義于這個值集合以及定義于這個值集合(jh)上的一上的一組操作的總稱組操作的總稱.C語言中的數(shù)據(jù)類型語言中的數(shù)據(jù)類型 char int float double void 字符型字符型 整型整型 浮點型浮點型 雙精度型雙精度型 無值無值 第17頁/共
11、72頁第十七頁,共72頁。18n構(gòu)造數(shù)據(jù)類型由基本數(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ī)中已實現(xiàn)的基本數(shù)據(jù)類型可以看作是計算機(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ù)類型的變量型的變量(binling),才能參加運算。,才能參加運算。 第18頁/共72頁第十八頁,共72頁。19抽象數(shù)據(jù)類型抽
12、象數(shù)據(jù)類型 (ADTs: Abstract Data Types)(ADTs: Abstract Data Types)抽象數(shù)據(jù)類型是由用戶定義,用以表示應(yīng)抽象數(shù)據(jù)類型是由用戶定義,用以表示應(yīng)用問題的數(shù)據(jù)模型。用問題的數(shù)據(jù)模型。特點是:信息隱蔽和數(shù)據(jù)封裝,使用與實特點是:信息隱蔽和數(shù)據(jù)封裝,使用與實現(xiàn)相分離?,F(xiàn)相分離。抽象數(shù)據(jù)類型可用(抽象數(shù)據(jù)類型可用(D, S, P)三元組表示,)三元組表示,其中,其中,D 是數(shù)據(jù)元素是數(shù)據(jù)元素(yun s)的集合(簡的集合(簡稱數(shù)據(jù)對象),稱數(shù)據(jù)對象),S 是是 D上的關(guān)系集合,上的關(guān)系集合,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ù)之間的關(guān)系其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系(gun x)用偽碼描述;基本操作定義格式為用偽碼描述;基本操作定義格式為ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象數(shù)據(jù)對象(duxing):數(shù)據(jù)對象:數(shù)據(jù)對象(duxing)的定義的定義 數(shù)據(jù)關(guān)系:數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系:數(shù)據(jù)關(guān)系的定義 基本操作:基本操作的定義基本操作:基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名基本操作名
14、(參數(shù)表)基本操作名(參數(shù)表)前置條件:前置條件:先決條件描述先決條件描述后置條件:后置條件:操作結(jié)果描述操作結(jié)果描述第21頁/共72頁第二十一頁,共72頁。22基本操作有兩種參數(shù):賦值參數(shù)只為操作提基本操作有兩種參數(shù):賦值參數(shù)只為操作提供輸入值;引用參數(shù)以供輸入值;引用參數(shù)以&打頭,除可提供輸打頭,除可提供輸入值外,還將返回操作結(jié)果。入值外,還將返回操作結(jié)果。 “前置條件前置條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的先決條件,若不滿足,則操和參數(shù)應(yīng)滿足的先決條件,若不滿足,則操作失敗,并返回相應(yīng)出錯作失敗,并返回相應(yīng)出錯(ch cu)信息。信息。 “后置條件后置
15、條件”說明了操作正常完成之后,數(shù)說明了操作正常完成之后,數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置條件為空,則省略之。條件為空,則省略之。第22頁/共72頁第二十二頁,共72頁。23自然數(shù)的抽象數(shù)據(jù)類型定義自然數(shù)的抽象數(shù)據(jù)類型定義(dngy)ADT NaturalNumber isobjects: 一個整數(shù)的有序子集合一個整數(shù)的有序子集合,它開始于它開始于0, 結(jié)束結(jié)束(jish)于機(jī)器能表示的最大整數(shù)于機(jī)器能表示的最大整數(shù)(MaxInt)。Function: 對于所有的對于所有的 x, y NaturalNumber; False, True Boolea
16、n, +、-、=、= 等都是等都是可用的服務(wù)??捎玫姆?wù)。 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面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍?ginin)n面向?qū)ο竺嫦驅(qū)ο?= = 對象類繼
17、承通信對象類繼承通信n對象對象n在應(yīng)用問題中出現(xiàn)的各種實體、事件、規(guī)格說在應(yīng)用問題中出現(xiàn)的各種實體、事件、規(guī)格說明等。明等。n由一組屬性值和在這組值上的一組服務(wù)(或稱由一組屬性值和在這組值上的一組服務(wù)(或稱操作)構(gòu)成。操作)構(gòu)成。n與與C C中構(gòu)造數(shù)據(jù)類型不同在于:中構(gòu)造數(shù)據(jù)類型不同在于:C C中的構(gòu)造數(shù)據(jù)中的構(gòu)造數(shù)據(jù)類型的變量僅涉及類型的變量僅涉及(shj)(shj)屬性值,與操作屬性值,與操作分離,而分離,而C+C+中的對象則不然。中的對象則不然。第26頁/共72頁第二十六頁,共72頁。27n類類 (class),實例,實例(shl) (instance)n具有相同屬性和服務(wù)的對象歸于同一
18、類,具有相同屬性和服務(wù)的對象歸于同一類,形成類。形成類。n類中的對象為該類的實例類中的對象為該類的實例(shl)。n同一類的實例同一類的實例(shl)n共享類的屬性和類的操作;共享類的屬性和類的操作;n通過繼承共享其父類的公共的和保護(hù)性的通過繼承共享其父類的公共的和保護(hù)性的屬性和操作;屬性和操作;n同一類的不同實例同一類的不同實例(shl)有不同的屬性值。有不同的屬性值。第27頁/共72頁第二十七頁,共72頁。28四邊形類及其對象四邊形類及其對象(duxing)屬性aPoint1 aPoint2aPoint3 aPoint4服務(wù)服務(wù)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)服務(wù)服務(wù)服務(wù)服務(wù)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ù)調(diào)用方式:函數(shù)調(diào)用方式: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)指令為解決某一特定任務(wù)規(guī)定了一個運算指令為解決某一特定任務(wù)規(guī)定了一個運算序列序列特性:特性:輸入輸入 有有0個或多個輸入個或多個輸入輸出輸
22、出 有一個或多個輸出有一個或多個輸出(處理結(jié)果處理結(jié)果)確定性確定性 每步定義都是確切無歧義的每步定義都是確切無歧義的有窮性有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性有效性 每一條運算應(yīng)足夠基本每一條運算應(yīng)足夠基本第32頁/共72頁第三十二頁,共72頁。33事例學(xué)習(xí):選擇排序問題事例學(xué)習(xí):選擇排序問題明確問題:遞增排序明確問題:遞增排序解決方案:逐個選擇最小數(shù)據(jù)解決方案:逐個選擇最小數(shù)據(jù)算法框架:算法框架: for (int i = 0; i n-1; i+) /n-1趟趟 從從ai檢查檢查(jinch)到到an-1; 若最小整數(shù)在若最小整數(shù)在ak, 交換交換ai與與ak;
23、 細(xì)化程序:程序細(xì)化程序:程序 SelectSort 算法算法(sun f)(sun f)設(shè)計設(shè)計 自頂向下,逐步求精自頂向下,逐步求精 第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是表項關(guān)鍵是表項關(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頁第三十六頁,共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為下標(biāo)的數(shù)組元素的值為下標(biāo)的數(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中具中具/有最小關(guān)鍵碼值的表項,函數(shù)返回有最小關(guān)鍵碼值的表項,函數(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ù)組內(nèi)容數(shù)組內(nèi)容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream endl; ouStream “輸出輸出(shch)數(shù)組當(dāng)前大小數(shù)組當(dāng)前大小 : ” 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個關(guān)鍵碼個關(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 第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、友元操作友元操作標(biāo)準(zhǔn)標(biāo)準(zhǔn)(biozhn)IO操作操作消息通信消息通信第44頁/共72頁第四十四頁,共72頁。45算法算法(sun f)簡單性能分簡單性能分析與度量析與度量第45頁/共72頁第四十五頁,共72頁。46算法算法(sun f)的的性能標(biāo)準(zhǔn)性能標(biāo)準(zhǔn)應(yīng)對其作出反應(yīng),而不應(yīng)產(chǎn)生莫名其妙的應(yīng)對其作出反應(yīng),而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。輸出結(jié)果。第46頁/共72頁第四十六頁,共72頁。47算法算法(sun f)的后的后期測試期測試對一個算法要作出全面的分析可分成兩個對一個算法要作出全面的分析可分成兩個階段進(jìn)行,即事前分析和事后測試階段進(jìn)行,即事前分析和事后測試事前分析要求事前求出該算法的一個時
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)的目標(biāo)代碼的質(zhì)量、計算機(jī)程序指令系統(tǒng)的品質(zhì)和速度等制約。第49頁/共72頁第四十九頁,共72頁。50算法的事前算法的事前(shqin)估計估計算法的事前估計主要包括時間算法的事前估計主要包括時間(shjin)(shjin)復(fù)雜性和空間復(fù)雜性的分析:復(fù)雜性和空間復(fù)雜性的分析:問題的規(guī)模:如:矩陣的階數(shù)、圖的結(jié)點個問題的規(guī)模:如:矩陣的階數(shù)、圖的結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)等。數(shù)、被分類序列的正整數(shù)個數(shù)等。時間時間(shjin)(shjin)復(fù)雜性:算法所需時間復(fù)雜性:算法所需時
36、間(shjin)(shjin)和問題規(guī)模的函數(shù),記為和問題規(guī)模的函數(shù),記為 T(n) T(n)。當(dāng)當(dāng) n n 時的時間時的時間(shjin)(shjin)復(fù)雜性,復(fù)雜性,稱為漸進(jìn)時間稱為漸進(jìn)時間(shjin)(shjin)復(fù)雜性。復(fù)雜性。空間復(fù)雜性:算法所需空間和問題規(guī)模的函空間復(fù)雜性:算法所需空間和問題規(guī)模的函數(shù)。記為數(shù)。記為 S(n) S(n)。當(dāng)。當(dāng) n n 時的時間時的時間(shjin)(shjin)復(fù)雜性,稱為漸進(jìn)空間復(fù)雜性。復(fù)雜性,稱為漸進(jìn)空間復(fù)雜性。第50頁/共72頁第五十頁,共72頁。51空間空間(kngjin)復(fù)雜度度量復(fù)雜度度量第51頁/共72頁第五十一頁,共72頁。52時
37、間時間(shjin)復(fù)雜度度復(fù)雜度度量量第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í)行結(jié)束得執(zhí)行結(jié)束得 程序步數(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) 的調(diào)用需要的程序的調(diào)用需要的程序(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)復(fù)雜度的漸進(jìn)復(fù)雜度的漸進(jìn)表示法表示法例例 求兩個求兩個(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)復(fù)雜度的漸進(jìn)表復(fù)雜度的漸進(jìn)表示法示法算法中所有算法中所有(suyu)語句的頻度之和是矩陣階語句的頻度之和是矩陣階數(shù)數(shù)n的函數(shù)的函數(shù) T(n) = 3n3 + 5n2 + 4n +2一般地,稱一般地,稱 n 是問題的規(guī)模。則時間復(fù)雜度是問題的規(guī)模。則時間復(fù)雜度 T(n) 是問題規(guī)模是問題規(guī)模 n 的函數(shù)。的函數(shù)。當(dāng)當(dāng)n趨于無窮大時,把時間復(fù)雜度的數(shù)量
42、級趨于無窮大時,把時間復(fù)雜度的數(shù)量級(階)稱為算法的漸進(jìn)時間復(fù)雜度(階)稱為算法的漸進(jìn)時間復(fù)雜度 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)漸進(jìn)漸進(jìn)(jinjn)的空間復(fù)雜度的空間復(fù)雜度 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; 漸進(jìn)漸進(jìn)(jinjn)時間復(fù)雜度為時間復(fù)雜度為 O(max (m*n, m)第63頁/共72頁第六十三頁,共72頁。64起泡排序起泡排序 void bubbleSort (int a , int n ) /對表對表 a 逐趟比較逐趟比較, n 是表當(dāng)前是表當(dāng)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 20 曹劌論戰(zhàn) (教學(xué)設(shè)計)九年級語文下冊同步備課系列(統(tǒng)編版)
- 茂名市高三第二次綜合測試文綜歷史試題
- 學(xué)校安全法律知識
- 2025年山東省棗莊市臺兒莊區(qū)中考一模語文試題(原卷版+解析版)
- 2025年會工作總結(jié)匯報
- 采購文員年終工作總結(jié)
- 教師專業(yè)技術(shù)履職總結(jié)
- 監(jiān)控、校園廣播、網(wǎng)絡(luò)采購合同范本
- 水電線管安裝合同
- 2025年佳木斯貨運從業(yè)資格證考些什么內(nèi)容
- 2025年食安食品考試題及答案
- 2025年租賃料場協(xié)議
- 新式茶飲創(chuàng)業(yè)趨勢
- 中國大唐集團(tuán)有限公司陸上風(fēng)電工程標(biāo)桿造價指標(biāo)(2023年)
- 2025年江蘇經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院單招職業(yè)技能考試題庫帶答案
- 醫(yī)院保安服務(wù)方案投標(biāo)文件(技術(shù)方案)
- 2025-2030年中國鑄造生鐵市場發(fā)展現(xiàn)狀及前景趨勢分析報告
- 輸液連接裝置安全管理專家共識2023
- 課件-2025年春季學(xué)期 形勢與政策 第一講-加快建設(shè)社會主義文化強(qiáng)國9
- 拆除臨時用電施工方案
- 小學(xué)數(shù)學(xué)教學(xué)中小組合作學(xué)習(xí)課件
評論
0/150
提交評論