1、數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE 用面向?qū)ο蠓椒ㄅcC+描述n 課程特點n 介紹如何組織各種數(shù)據(jù)在計算機中的傳遞和轉(zhuǎn)換；、n 課程采用面向?qū)ο蟮挠^點討論數(shù)據(jù)結(jié)構(gòu)技術(shù)；n 兼有面向過程和面向?qū)ο箅p重特色的C+語言作為算法的描述工具；n 強化數(shù)據(jù)結(jié)構(gòu)基本知識和面向?qū)ο蟪绦蛟O(shè)計基本能力的雙基訓(xùn)練。2n 課程要求n “聽課”“自學(xué)”“實踐”并舉n 掌握重要數(shù)據(jù)結(jié)構(gòu)的概念、使用方法及實現(xiàn)技術(shù)；n 學(xué)會做簡單的算法分析，包括算法的時間代價和空間代價。3參考資料n 數(shù)據(jù)結(jié)構(gòu)（C語言版）n 嚴(yán)蔚敏、吳偉民nn 數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+語言描述）n 殷人昆nn 數(shù)據(jù)結(jié)構(gòu) C+與面向?qū)ο蟮耐緩絥 張乃孝、裘

2、忠燕n 高等教育n 新編實用算法分析與程序設(shè)計n 王建德、吳永輝郵電nn 數(shù)據(jù)結(jié)構(gòu)-Java版n （美）D.S.Malik, P.S.Nair 著，楊浩譯nn 數(shù)據(jù)結(jié)構(gòu)與算法C+版（美）Adam Drozdek編著，鄭巖，戰(zhàn)曉蘇 翻譯nn4n 如何評價成績？（擬訂待調(diào)整，三個班級統(tǒng)一 ）n 期末閉卷筆試（約60%左右）n 期中閉卷筆試（約15%左右）n 項目實踐（約35%左右）n 上機實踐n 作業(yè)及出勤情況成績?yōu)閮?yōu)者不超過30%5前四周上機實踐課程內(nèi)容簡介n 第一周：C+程序設(shè)計語言n 基礎(chǔ)知識n 語法、數(shù)據(jù)類型、指針、函數(shù)、傳遞參數(shù)和地址n C+開發(fā)環(huán)境n VC的使用技巧n 上機操作實例（如

3、何創(chuàng)建工程，如何加入頭文件、cpp文件等；怎樣編譯；怎樣調(diào)試）n 用具體實例來說明上述概念和使用技巧6n 第二周：面向?qū)ο蟮某绦蛟O(shè)計OOPn 類和對象n 構(gòu)造/析構(gòu)函數(shù)n 類的繼承n 派生類n 虛函數(shù)與多態(tài)n 重載類型referencenn 友元7n 第三周：template介紹n template及其優(yōu)勢n 模板的多態(tài)性n template使用方法n 函數(shù)模板/類模板n 以一些具體實例來介紹template的應(yīng)用8n 第四周：程序設(shè)計風(fēng)格及設(shè)計實踐n 編程規(guī)范n 好程序的定義n 命名規(guī)則n 表達(dá)式和語句n 函數(shù)n 如何寫Documentn 注釋n 什么樣的編碼是好的編程風(fēng)格9n 數(shù)據(jù)結(jié)構(gòu)的概

4、念n 數(shù)據(jù)結(jié)構(gòu)的抽象形式n 作為ADT的C+類n 算法定義n 算法性能分析與度量n 本章小結(jié)1.1 數(shù)據(jù)結(jié)構(gòu)的概念n 宇宙三要素：物質(zhì)、能量和信息n 信息是客觀世界在人腦中的反映。n 數(shù)據(jù)是信息的載體。n 數(shù)據(jù)是怎樣在計算機中n 舉例說明和組織的？11“學(xué)生”表格12345678912學(xué) 號姓 名籍 貫出生年月98131劉激揚男北 京1979.1298164衣春生男青 島1979.0798165盧聲凱男天 津1981.0298182袁秋慧女廣 州1980.1098224洪 偉男太 原1981.0198236熊南燕女蘇 州1980.0398297宮 力男北 京1981.0198310蔡曉莉女昆

5、明1981.0298318陳 健男杭 州1979.12“課程”表格13課程編號課 程 名學(xué)時024002程序設(shè)計基礎(chǔ)64024010匯編語言48024016計算機原理64024020數(shù)據(jù)結(jié)構(gòu)64024021微機技術(shù)64024024操作系統(tǒng)48024026數(shù)據(jù)庫原理48“選課單”包含如下信息學(xué)生選課系統(tǒng)中實體的網(wǎng)狀關(guān)系14選課(學(xué)號,課程號,成績)課程(課程號,課程名,學(xué)分)學(xué)生(學(xué)號,姓名,籍貫)學(xué)號課程編號成績時間UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖binetcswyintaoxie15Tree.cppStack.cppQueue.cppdsmathuserlib/ (root)基本概念：數(shù)據(jù) (D

6、ata)n 數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。u 數(shù)值性數(shù)據(jù)(int)u 非數(shù)值性數(shù)據(jù) (char)16基本概念：數(shù)據(jù)元素 (Data Element)n 數(shù)據(jù)的基本，在計算機程序中常作為一個整體進(jìn)行考慮和處理。n 有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是具有含義的最小標(biāo)識。n 數(shù)據(jù)元素又稱為元素、結(jié)點、。17基本概念:數(shù)據(jù)對象 (Data Object)n 數(shù)據(jù)的子集，具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。N=0, ±1, ±2, u 整數(shù)數(shù)據(jù)對象u 學(xué)生數(shù)據(jù)對象n 數(shù)據(jù)

7、對象中所有成員之間存在某種關(guān)系，如學(xué)生按學(xué)號的排序；按的分類等。n 數(shù)據(jù)成員及其之間關(guān)系，是數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容。18什么是數(shù)據(jù)結(jié)構(gòu)定義:由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：Data_Structure=D, R其中，D是某一數(shù)據(jù)對象，R是該對象中所 有數(shù)據(jù)成員之間關(guān)系的有限集合。19N個之間的連通關(guān)系3網(wǎng)狀關(guān)系樹形關(guān)系20數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式n 數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；n 數(shù)據(jù)元素及其關(guān)系在計算機內(nèi)的表示，即數(shù)據(jù)的表示；n 數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作。例如：座位/學(xué)生（按班級）21DS第一部分：數(shù)據(jù)的邏輯結(jié)構(gòu)n 數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描

8、述數(shù)據(jù)，與數(shù)據(jù)的無關(guān)；n 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；n 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)。22數(shù)據(jù)的邏輯結(jié)構(gòu)分類n 線性結(jié)構(gòu)u 線性表n 非線性結(jié)構(gòu)u 樹u 圖（或網(wǎng)絡(luò)）23線性結(jié)構(gòu)：useretcdevbinlib樹形結(jié)構(gòu)：樹1二叉樹1二叉搜索樹6313269453109111224堆結(jié)構(gòu)（樹的特例）：1211971066373548289“最小”堆“最大”堆25121221663113335454網(wǎng)絡(luò)結(jié)構(gòu)圖結(jié)構(gòu)26DS第二個重要部分：數(shù)據(jù)的n 數(shù)據(jù)的結(jié)構(gòu)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)；n 數(shù)據(jù)的u 順序結(jié)構(gòu)依賴于計算機語言。表示表示表示表示主要用于內(nèi)存的

9、表示uu 索引u 散列主要用于外存（文件）的表示27數(shù)據(jù)結(jié)構(gòu)的抽象層次28n 線性類u 直接存取類u 順序存取類u 廣義索引類數(shù)組、文件表、棧、隊列、優(yōu)先隊列線性索引、搜索樹n 非線性u 層次u 群類類樹、二叉樹、堆類集合、圖29數(shù)據(jù)結(jié)構(gòu)的課程內(nèi)容體系方面層次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運算實現(xiàn)結(jié)構(gòu)算法評價不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析1.2 數(shù)據(jù)結(jié)構(gòu)的抽象形式1.2.1 數(shù)據(jù)類型定義：一組性質(zhì)相同的值的集合，以及定義于這個值集合上的一組操作的總稱。n C語言中的數(shù)據(jù)類型char字符型int整型floatdoublevoid無值浮點型 雙精度型int取值范圍-32768, 32767；每個數(shù)

10、據(jù)類型對應(yīng)一組操作int(6/4)=1(float)(6.0/4.0)=1.531n 數(shù)據(jù)類型由n 基本數(shù)據(jù)類型 或n 構(gòu)造數(shù)據(jù)類型組成n 構(gòu)造數(shù)據(jù)類型由不同成分類型。n 基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。n 數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過是從編程者的角度來使用。321.2.2 數(shù)據(jù)抽象與抽象數(shù)據(jù)類型(ADTs: AbstractData Types)§ 由用戶定義， 用以表示應(yīng)用問題的數(shù)據(jù)模型。§ 抽象的本質(zhì)：抽取反映問題本質(zhì)的東西， 忽略非本質(zhì)的細(xì)節(jié)。§ ADT：由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)的服務(wù)（或稱操作）。§ 信息隱蔽和數(shù)據(jù)封裝

11、，使用與實現(xiàn)相分離。33使用者抽象數(shù)據(jù)類型查找登錄刪除修改符號表34自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber isobjects: 一個整數(shù)的有序子集合,它開始于0，能表示的最大整數(shù)(MaxInt)。結(jié)束于Function: 對于所有的 x, yÎNaturalNumber；False, TrueÎBoolean, +、-、<、=、=等都是可用的服務(wù)。Zero( ): NaturalNumber返回自然數(shù)035IsZero(x):Boolean Add (x, y):if (x=0)返回Trueelse返回Falseif (x+y<=MaxIn

12、t)返回 x+yNaturalNumber else返回MaxIntSubtract(x, y):if (x<y)返回0NaturalNumber else返回 x-yEqual(x, y) :Boolean Successor(x):if (x=y)返回Trueelse返回Falseif (x=MaxInt)返回xNaturalNumber elseend NaturalNumber返回x+11.3 作為ADT的C+類n 面向?qū)ο蟮母拍頽 Codd and Yourdonn Rational Rose, IBMn 面向?qū)ο?對象類繼承通信n 實現(xiàn)信息隱藏和封裝37n 對象u 實體、規(guī)格

13、說明等。u 由一組屬性值和在這組值上的一組服務(wù)（或稱操作）。n 類(Class)，實例(Instance)u 具有相同屬性和服務(wù)的對象歸于同一類， 形成類。u 類中的對象為該類的實例。38quadrilateral1 屬性值(35, 10) (50, 10)quadrilateral2 屬性值(45, 65) (50, 45)quadrilateral 屬性aPoint1 aPoint2aPoint3aPoint4(35, 25)(50, 25)(65, 66)(60, 70)服務(wù) 服務(wù) Draw( ) move(Dx, Dy)contains(aPoint) 服務(wù) Draw( ) move(

14、Dx, Dy)contains(aPoint)Draw( ) move(Dx, Dy) contains(aPoint)四邊形類及其對象39n 繼承u 派生類：四邊形，三角形，子類特化類（特殊化類）u 基類：多邊形父類泛化類（一般化類）n 通信u 消息傳遞40PolygonQuadrilateralreferencePoint VerticesreferencePoint VerticesDraw( ) move(Dx, Dy) contains(aPoint)Draw( ) move(Dx, Dy) contains(aPoint)Polygon 類Polygon的子類Quadrilater

15、al類41用C+描述面向?qū)ο蟪绦騨 C+的函數(shù)特征n C+的數(shù)據(jù)n C+的作用域n C+的類n C+的對象n C+的輸入/輸出n C+的函數(shù)n C+的參數(shù)傳遞C+的函數(shù)名重載和操作符重載nC+的動態(tài)分配n友元(friend)函數(shù)內(nèi)聯(lián)(inline)函數(shù)結(jié)構(gòu)(struct)與類(union)與類nnnn42詳細(xì)介紹上機實踐課模板(template)目的：實現(xiàn)軟件重用定義適合多種數(shù)據(jù)類型的類定義或算法， 在特定環(huán)境下通過簡單地代換，變成具體某種數(shù)據(jù)類型的類定義或算法。43用模板定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H #define DATALIST_H #include <

16、;iostream.h>template <class Type> class dataListprivate:Type *Element; int ArraySize;void Swap(int m1, int m2); int MaxKey(int low, int high);44public:dataList(int size=10) : ArraySize(size), Element(new Type Size) dataList( ) delete Element; void Sort( );friend ostream & operator <&

17、lt; (ostream &outStream, datalist <Type> &outList);friend istream & operator >> (istream &inStream, datalist <Type> &inList);#endif45類中所有操作作為模板函數(shù)的實現(xiàn)#ifndef SELECTTM_H #define SELECTTM_H #include “datalist.h”template <class Type> void dataList <Type>

18、:Swap(int m1,int m2)/交換由m1, m2為下標(biāo)的數(shù)組元素的值Type temp=Elementm1;Elementm1=Elementm2; Elementm2=temp;46template <class Type> int dataList <Type> :MaxKey(int low, int high)/查找數(shù)組Elementlow到Elementhigh/中的最大值，函數(shù)返回其位置int max=low;for (int k=low+1; k<=high; k+) if (Elementmax<Elementk)max=k; r

19、eturn max;47template <class Type>ostream & operator << (ostream &OutStream,dataList <Type> OutList)OutStream<<“數(shù)組內(nèi)容：n”;for (int i=0; i<OutList.ArraySize; i+)OutStream<<OutList.Elementi<< ;OutStream<<endl;OuStream<<“數(shù)組當(dāng)前大小：”<<OutList.Ar

20、raySize<<endl;return OutStream;48template <class Type>istream & operator >> (istream &InStream,dataList <Type> InList)/輸入對象為InList，輸入流對象為InStreamcout<<“錄入數(shù)組當(dāng)前大小：”;Instream>>InList.ArraySize;cout<<“錄入數(shù)組元素值：n”;for (int i=0; i<InList.ArraySize; i+) c

21、out<<“元素”<<i<<“：”;InStream>>InList.Elementi; return InStream;49template <class Type> void dataList <Type> : Sort( )/按非遞減順序?qū)rraySize個關(guān)鍵碼/Element0到ElementArraySize-1排序for (int i=ArraySize-1; i>0; i-)int j=MaxKey(0, i);if (j!=i)swap(j, i);#endif50使用模板的選擇排序算法的主函數(shù)#

22、include “selecttm.h” const int SIZE=10; int main( ) dataList <int> TestList(SIZE); cin>>TestList; cout<<TestList<<endl; TestList.Sort( ); cout<<TestList<<endl; return 0;模板的詳細(xì)介紹上機實踐課1.4 算法定義n 定義：一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定一個運算序列。n 特性：u 輸入Input有0個或多個輸入；u 輸出Output有一個或多個

23、輸出（處理結(jié)果）；u 確定性u 有窮性u 有效性每步定義都是確切無歧義的；算法應(yīng)在執(zhí)行有窮步后結(jié)束； 每一條運算應(yīng)足夠基本。52算法Algorithm=程序Program？n 算法是有窮性結(jié)束。算法應(yīng)在執(zhí)行有窮步后n 程序可能持續(xù)運行，直到系統(tǒng)例如操作系統(tǒng)wait函數(shù)。n 算法是面向問題的。n 程序是算法的具體語言實現(xiàn)。，53算法設(shè)計自頂向下，逐步求精u 事例學(xué)習(xí)：n個整數(shù)的選擇排序問題基本思想: 在一組對象ViVn-1中選擇具有最小排序碼的對象； 若它不是這組對象中的第一個對象，則將它與這組對象中的第一個對象對調(diào)； 在這組對象中剔除這個具有最小排序碼的對象，在剩下的對象Vi+1Vn-1中重復(fù)

24、執(zhí)行第、步，直到剩余對象只有一個為止。54初始4925125*32101640852最小者 08交換21, 08i=0492525*211608最小者 16交換25, 16i=1492525*211608最小者 21交換49, 21i=24925*25211608各趟排序后的結(jié)果55最小者 25*無交換i=34925*25211610802345最小者 25無交換i=44925*25211608結(jié)果4925*25211608各趟排序后的結(jié)果56u 明確問題：遞增排序u 解決方案：逐個選擇最小數(shù)據(jù)u 算法框架：for (int i=0; i<n-1; i+)/n-1趟從ai檢查到an-1若

25、最小整數(shù)在ak，交換ai與ak;u 細(xì)化程序：程序SelectSort57void selectSort(int a , const int n)/對n個整數(shù)a0到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;1.5 算法性能分析與度量u 如何度量數(shù)據(jù)結(jié)構(gòu)和算法的性能好壞？u 算法的性能標(biāo)準(zhǔn)u 算法的后期測試u 算法的事前估計59算法的性能標(biāo)準(zhǔn)u 正確性u 可使用性用戶

26、友u 可讀性u 程序設(shè)計風(fēng)格，軟件產(chǎn)業(yè)，對大項目非常重要，CMM (Capability Maturity Mu 上機實踐課詳細(xì)介紹u 效率時間與空間代價u 確定問題規(guī)模與算法時間和空間的關(guān)系u 健壯性容錯性u 簡單性 for Software )算法的后期測試在算法中的某些部位插裝時間函數(shù)time( )測定算法完成某花費時間。能所舉例說明61順序搜索 (Sequenial Search)int seqsearch(int a , const int n, const int x)/在a0, , an-1中搜索xint i=0;while (i<n && ai!=x) i

27、+;if (i=n) return i;return -1;62插裝time( )的計時程序double start, stop; time(&start);int k=seqsearch(a, n, x); time(&stop);double runTime=stop-start;cout<<“ ”<<n<<“ ”<<runTime<<endl;缺點:1、與環(huán)境配置有關(guān)，不同的PC，不同的系統(tǒng)性能，產(chǎn)生 不同的時間差值;2、需要確定合適的計數(shù)方法，處理器自帶的計數(shù)函數(shù)是毫秒級，因此如果少于毫秒的數(shù)量級，計數(shù)。63v

28、oid TimeSearch( )int a1000, n20;for (int j=1; j<=1000; j+)aj-1=j;/a0=1, a1=2, 初始化afor (j=0; j<10; j+) nj=10*j;/n0=0, n1=10, n2=20nj+10=100*(j+1);/n10=100, n11=200, n12=300 .cout<<“n time”<<endl;64for (j=0; j<20; j+) long start, stop;/得到計算時間time(&start);/開始計時int k=seqsearch(a

29、, nj, 0);/不查找time(&stop);/停止計時long runTime=stop-start;/計算運行時間cout<<“ ”<<nj<<“ ”<<runTime<<endl;/輸出cout<<“Times are in hundredths of a second.”<<endl;65程序測試結(jié)果輸出假設(shè)時間函數(shù)time( )的測量精度為0.01秒，程序測試結(jié)果都是0，表明時間函數(shù)的測試精度不夠。66n100 200 300 400 500 600 700 800 900 1000run

30、 Time0000000000n0102030405060708090run Time0000000000改進(jìn)的計時程序void TimeSearch( ) int a1000, n20;const long r20=300000, 300000, 200000, 200000,100000, 100000, 100000, 80000, 80000, 50000, 50000,25000, 15000, 15000, 10000, 7500, 7000, 6000, 5000,5000;for (int j=1; j<=1000; j+)aj-1=j;/初始化afor (j=0; j&

31、lt;10; j+) /為n賦值nj=10*j;nj+10=100*( j+1);cout<<“n totalTime runTime”<<endl;67for (j=0; j<20; j+) /得到計算時間long start, stop; time(&start); /開始計時for (long b=1; b<=rj; b+)int k=seqsearch(a, nj, 0);/不查找，執(zhí)行rj次time(&stop); /停止計時long totalTime=stop-start;float runTime=(float)(totalT

32、ime)/(float)(rj);/總時間除以重復(fù)執(zhí)行次數(shù)cout<<“ ”<<nj<<“ ”<<totalTime<<“ ”<<runTime<<endl;68程序修改后的測試結(jié)果輸出測量數(shù)據(jù)與n基本呈線性關(guān)系69n0102030405060708090總的運行時間241533582736467565659604681472單個運行時間0.00080.00180.00290.00370.00470.00560.00660.00750.00850.0094n100200300400500600700800900

33、1000總的運行時間527505451593494439484467434484單個運行時間0.01050.02020.03010.03950.04940.05850.06910.07780.08680.0968/矩陣相乘：將aNN和bNN兩個N*N矩陣相乘/最終的結(jié)果放在cNN中返回給用戶void matrix_multi(int aNN, int bMN, int cNN)int i=j=k=0; int tmp;for (i=0; i<N; i+) for (j=0; j<N; j+)ci, j=0;for (i=0; i<N; i+) for (j=0; j<N

34、; j+)for (k=0; k<N; k+)ci, j=ai, k*bk, j+ci, j;return 0;70/增加了time( )函數(shù)后的矩陣相乘程序void multi( )int aNN, int bNN, int cNN; int i, j, k=0;for (i=0; i<N; i+) for (j=0; i<N; i+)ai, j=k+; for (i=0; i<N; i+)for (j=0; i<N; i+) bi, j=k+;long start, stop; time(&start);matrix-multi(a, b, c); t

35、ime(&stop);long runtime=stop-start; cout<<“time is ”<<runtime<< endl;71n 算法的運行時間依賴于所使用的計算機系統(tǒng)、 編譯器、可用空間大小等。n 同樣的算法在速度不同的計算機上，執(zhí)行速度 相差非常大。n 算法用不同的編譯器編譯出的目標(biāo)代碼不一樣 長，完成同樣功能所需時間不同。n 如果可用空間不夠，算法需要的運行時間很多；如果空間足夠大，則時間明顯減少。n 算法運行時間的測量用于評估算法的正確性和可用性，并不能算法的優(yōu)劣。n 通過比較算法的復(fù)雜性來評價。n 算法復(fù)雜性與具體運行環(huán)境和

36、編譯器無關(guān)。算法的事前估計u 空間復(fù)雜度(Space Complexity)u 時間復(fù)雜度(Time Complexity)u 用來確定問題規(guī)模n（比如學(xué)生人數(shù)）與算法空間f(n)，程序步數(shù)或者時實現(xiàn)時需要的間開銷g(n)的關(guān)系。u 在目前的研究領(lǐng)域，對算法進(jìn)行分析時，時空復(fù)雜性是最重要的基本功，最理想的算法評價標(biāo)準(zhǔn)。73空間復(fù)雜度度量空間的固定部分程序指令代碼的空間，常數(shù)、簡單變量、定n長成分（如數(shù)組元素、結(jié) 據(jù)成員等）變量所占空間。n 可變部分分、對象的數(shù)與實例特性有關(guān)的成分變量所占空間、變量所占空間、遞歸棧所用空間、通過new和delete命令動態(tài)使用空間。74例1：計算表達(dá)式float

37、 abc(float a, folat b, float c) return a+b+b*c+(a+b-c)/(a+b)+4.0;例2：以迭代方式求累加和的函數(shù)float sum(float a , int n) float s=0.0;for (int i=0; i<n; i+) s+=ai;return s;例3：以遞歸方式求累加和的函數(shù)float rsum(float a , int n) if (n<=0)return 0;else returnrsum(a, n-1)+an-1;75時間復(fù)雜度度量n 編譯時間n 與編譯程序有關(guān)，與實例性質(zhì)無關(guān)。n 運行時間u 程序步F 語

38、法上或語義上有意義的一段指令序列。F 執(zhí)行時間與實例特性無關(guān)。語句程序步數(shù)為0，表達(dá)式程序F 例如，步數(shù)為1。76程序步確定方法w計數(shù)全局變量count；w 建表，列出各語句的程序步。77例1：以迭代方式求累加和的函數(shù)float sum(float a , int n)float s=0.0;for (int i=0; i<n; i+) s+=ai;return s;78在求累加和程序中加入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+;

39、/ s+=ai; count+;for語句/賦值語句count+; count+; return s;/for的最后一次return語句執(zhí)行結(jié)束得程序步數(shù)？ count=2*n+379程序的簡化形式void sum(float a , int n)for (int i=0; i<n; i+) count+=2;count+=3;80注意：一個語句本身的程序步數(shù)，可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。例如：賦值語句x=sum(R, n)本身的程序步數(shù)為 1；一次執(zhí)行對函數(shù)sum(R, n)的調(diào)用需要的程序步數(shù)為 2*n+3；一次執(zhí)行的程序步數(shù)為1+2*n+3=2*n+481第二種方法:

40、計算累加和程序程序步數(shù)計算工作表格82程 序 語 句一次執(zhí)行所需程序步數(shù)執(zhí)行頻度程序步數(shù)010float s=0.0;111for (int i=0; i<n; i+)1n+1n+1s+=ai;1nnreturn s;111010總程序步數(shù)2n+3例2：以遞歸方式求累加和的函數(shù)float rsum(float a , int n)if (n<=0)return 0;else return rsum(a, n-1)+an-1;83在求累加和程序中加入count語句float rsum(float a , int n)count+;/if語句if (n<=0) count+; r

41、eturn 0;else /return語句count+=2;/else與return語句return rsum(a, n-1)+an-1;84設(shè)count初始值為0，Trsum(n)是程序執(zhí)行后的count值。n=0，Trsum(0)=2; n>0，Trsum(n)=Trsum(n-1)+3;Trsum(n)=3+Trsum(n-1)=3+3+Trsum(n-2)=3*2+Trsum(n-2)=3+3+3+Trsum(n-3)=3*3+Trsum(n-3)=3*n+Trsum(0)=3n+285計算累加和程序程序步數(shù)計算工作表格86程 序 語 句一次執(zhí)行所需程序步數(shù)執(zhí)行頻度程序步數(shù)n=

42、0n>0n=0n>001100if (n<=0)11111return 0;11010else return2+Trsum(n-1)0102+Trsum (n-1)rsum(a, n-1)+an-1;101100總程序步數(shù)23+Trsum (n-1)87程序執(zhí)行代價執(zhí)行次數(shù)int i=j=k=0; int tmp;for (i=0; i<N; i+) for (j=0; j<N; j+)ci, j=0;for (i=0; i<N; i+) for (j=0; j<N; j+)for (k=0; k<N; K+)ci, j=ai, k*bk, j+

43、ci, j; return 0;C1 C2 C3 C4 C5 C6 C7 C8 C9 C1011N+1 N*(N+1)N*NN+1N*N+1） N*N*(N+1)N*N*N 1n 程序步本身就不是一個準(zhǔn)確的概念，而是一個抽象的概念。n 再作一次抽象，從由多種因素的時間復(fù)雜性中抽取出其主要因素，將常數(shù)抽象為1，有利于抓住主要雜性分析。n 大O表示法，簡化復(fù)88時間復(fù)雜度的漸進(jìn)表示法例：求兩個n階方陣的乘積C=A´Bvoid MatrixMultiply(int Ann, int Bnn, int Cnn)for (int i=0; i<n; i+) for (int j=0; j

44、<n; j+) Cij=0;for (int k=0; k<n; k+) n+1 n(n+1) n2 n2(n+1)Cij=Cij+Aik*Bkj; n32n3+3n2+2n+189n 算法中所有語句的頻度之和是矩陣階數(shù)n 的函數(shù)T(n)=2n3+3n2+2n+1n 一般地，稱n是問題的規(guī)模。則時間復(fù)雜度T(n)是問題規(guī)模n的函數(shù)。n 當(dāng)n趨于無窮大時，把時間復(fù)雜度的數(shù)量級（階）稱為算法的漸進(jìn)時間復(fù)雜度。T(n)=O(n3)-大O表示法90n 大O表示法最壞情況n 當(dāng)且僅當(dāng)存在正整數(shù)c和n0，使得T(n)cf(n) 對所有的nn0成立，則稱該算法的漸進(jìn)時間復(fù)雜度為T(n)=O(f(

45、n)。n 當(dāng)實例特性n充分大時，算法的時間復(fù)雜度隨n變化，在最壞情況下若存在一個增長的上界，即cf(n)，則該算法的時間復(fù)雜度增長的數(shù)量級為f(n)，即稱該算法的漸進(jìn)時間復(fù)雜度為T(n)=O(f(n)。91n 大O表示法的使用n 需要考慮關(guān)鍵操作的程序步數(shù)。n 關(guān)鍵操作大多在循環(huán)和遞歸中；n 在多數(shù)場合中，程序步驟與執(zhí)行頻度一一對應(yīng)。n 如果給出的是漸進(jìn)值，可直接考慮關(guān)鍵操作的執(zhí)行頻度，提出其與實例特性n的函數(shù)關(guān)系g(n)。92n 漸進(jìn)時間復(fù)雜度的計算n 單個循環(huán)n 循環(huán)內(nèi)的簡單語句即為關(guān)鍵操作，該程序段的 漸進(jìn)時間復(fù)雜度應(yīng)是此關(guān)鍵操作的執(zhí)行頻度的 大O表示。n 幾個并列的循環(huán)n 分析每個循環(huán)

46、的漸進(jìn)時間復(fù)雜度，然后利用大O表示法的加n 多層的嵌套循環(huán)n 關(guān)鍵操作應(yīng)該在最內(nèi)層循環(huán)中，先自外向內(nèi)層 層分析每層循環(huán)的時間漸進(jìn)復(fù)雜度，然后利用則來計算漸進(jìn)時間復(fù)雜度。大O表示法的乘則來計算漸進(jìn)時間復(fù)雜度。93n 加則并列程序段T(n, m)=T1(n)+T2(m)=O(max(f(n), g(m)94c < log2n < n < nlog2n < n2 < n3 < 2n < 3n < n!n 取c、log2n、n、nlog2n時間效率比較高；n 取n2、n3時間效率差強人意；n 取2n、3n、n!當(dāng)n稍微大一點，算法的時間代價變?yōu)楹艽螅灾?/p>

47、于不能計算。T(n)=T1(n)+T2(n)+T3(n)=O(max(1, n, n2)= O(n2)95變量計數(shù)T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)for (int i=0; i<n; i+) for (int j=0; j<n; j+)y+;for (int k=0; k<n; k+)x+;x=0; y=0;兩個并列循環(huán)的例子void exam(float x , int m, int n)float sum ;for (inti=0; i<m; i+) /x中各行sumi=0.0;/數(shù)據(jù)累加for (int j=0; j<n; j+

48、) sumi+=xij;for (i=0; i<m; i+)/打印各行數(shù)據(jù)和cout<<i<<“: ”<<sumi<<endl;漸進(jìn)時間復(fù)雜度為 O(max(m*n, m)96n 乘則嵌套程序段T(n, m)=T1(n)*T2(m)=O(f (n)*g(m)97如果一個程序的循環(huán)中有一個包含有循環(huán)的函 數(shù)調(diào)用語句，也可在被調(diào)用函數(shù)內(nèi)部尋找關(guān)鍵操作，使用乘 則來計算漸進(jìn)時間復(fù)雜度。兩個嵌套循環(huán)的例子起泡排序（遞增）基本思想：設(shè)待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為n。最多作n-1趟，i=1, 2, ¼, n-1。在第i趟中從后向前，n-2, ¼,j=n-1,i ， 順次兩兩比較Vj-1.key和Vj.key。如果發(fā)生逆序，則交換Vj-1和Vj。984925125*32101640852i=exchang=1i=exchang=1i=08exchang=149i=42525*211608exchang=0各趟排序后的結(jié)果99template <class Type> void dataList <Type> :bubbleSort( ) /對表逐趟比較，ArraySize是表當(dāng)前長度int i=1;int exchange=1;/當(dāng)