《數(shù)據(jù)結(jié)構(gòu)C語言 PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言 PPT課件（51頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、學(xué)習(xí)提要 掌握本課程所涉及到的基本名詞、術(shù)語和概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系及性質(zhì)。 了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。 理解算法設(shè)計(jì)的五個(gè)要素和基本要求；掌握算法效率的度量方法，著重學(xué)習(xí)算法的時(shí)間復(fù)雜度分析。第1頁/共51頁教學(xué)重點(diǎn)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)；邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別；數(shù)據(jù)結(jié)構(gòu)及其三個(gè)組成部分；抽象數(shù)據(jù)類型和數(shù)據(jù)抽象；評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)及方法。第2頁/共51頁1.1什么是數(shù)據(jù)結(jié)構(gòu)一、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？1、電子計(jì)算機(jī)的主要用途：早期： 主要用于數(shù)值計(jì)算。后來： 處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）。第3頁/共

2、51頁用計(jì)算機(jī)解決問題的過程建立模型構(gòu)造求解算法選擇存儲(chǔ)結(jié)構(gòu)編寫程序測試描述問題的共性描述問題的求解方法將問題涉及的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中分析問題的過程數(shù)據(jù)結(jié)構(gòu)的作用進(jìn)行更為復(fù)雜的算法設(shè)計(jì)選擇合理的存儲(chǔ)結(jié)構(gòu)提高編程技術(shù)第4頁/共51頁引引 例例書目自動(dòng)檢索系統(tǒng)的數(shù)學(xué)模型書目自動(dòng)檢索系統(tǒng)的數(shù)學(xué)模型登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號(hào)高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L00

3、2,S001,003,索引表線性表第5頁/共51頁人機(jī)對(duì)奕問題的數(shù)學(xué)模型人機(jī)對(duì)奕問題的數(shù)學(xué)模型樹樹.第6頁/共51頁CEDABABACADBABCBDDADBDCEAEBECED圖十字路口的交通燈管理問題的數(shù)學(xué)模型第7頁/共51頁求解非數(shù)值計(jì)算的問題： 主要考慮的是設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。 即：首先要考慮對(duì)相關(guān)的各種信息如何表示、組織和存儲(chǔ)？ 因此，簡單說來，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。第8頁/共51頁問題：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？答：計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠數(shù)學(xué)方程，而非數(shù)值運(yùn)算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。 同樣的

4、數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算效率可能有明顯的差異。 程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法。而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。 算法+數(shù)據(jù)結(jié)構(gòu)=程序 提高復(fù)雜程序設(shè)計(jì)的能力 培養(yǎng)算法設(shè)計(jì)能力 為后繼課程（如操作系統(tǒng)、編譯原理等）打基礎(chǔ)。第9頁/共51頁數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展 形成階段 60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。 1968年，美唐歐克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，計(jì)算機(jī)程序設(shè)計(jì)技巧第一卷基本算法 ，“數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學(xué)計(jì)算機(jī)科學(xué)系的教學(xué)計(jì)劃。 發(fā)展階段： 數(shù)據(jù)結(jié)構(gòu)的概念

5、不斷擴(kuò)充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。 70年代后期，80年代初，我國高校陸續(xù)開設(shè)該課程。第10頁/共51頁數(shù)據(jù)結(jié)構(gòu)課程所處的地位：介于數(shù)學(xué)、計(jì)算介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)機(jī)硬件和計(jì)算機(jī)軟件三者之間的軟件三者之間的一門核心課程。一門核心課程。第11頁/共51頁基本概念和術(shù)語1.2.1基本概念1.數(shù)據(jù)（data）： 數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合, 是計(jì)算機(jī)程序加工的”原料”。 分類： 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù)第12頁/共51頁2、數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序

6、中常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(Data Item)(Data Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。學(xué)號(hào)學(xué)號(hào) 姓名姓名成成績績001LiLy89002Yang98003Zhao78第13頁/共51頁3、數(shù)據(jù)對(duì)象（data object）l數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。u整數(shù)數(shù)據(jù)對(duì)象 N = 0, 1, 2, u字母字符數(shù)據(jù)對(duì)象 C=A，B，Zu學(xué)生成績數(shù)據(jù)對(duì)象Cj=（101，jane，80）， （ 102，jack，90 ）， （ 103，jerry，75 ）學(xué)號(hào)學(xué)號(hào)姓名姓名成績成績001LiLy890

7、02Yang98003Zhao78第14頁/共51頁4、數(shù)據(jù)結(jié)構(gòu)(data structure) 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 在任何問題中，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)(Structure)。 數(shù)據(jù)結(jié)構(gòu)是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間的關(guān)系的總和。第15頁/共51頁 按數(shù)據(jù)元素之間關(guān)系的不同特性，通常有4類基本結(jié)構(gòu)（1）集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，別無其它關(guān)系。（2）線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。（3）樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。（4）圖狀結(jié)構(gòu)

8、或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。bindevetclibuseretcuserdevlibbindevetcuser14131211234567891031587101199874566231311152436第16頁/共51頁數(shù)據(jù)結(jié)構(gòu)的形式定義用一個(gè)二元組表示，記為： Data_Structure = （D, S） 其中，D 是數(shù)據(jù)元素的有限集（即一個(gè)數(shù)據(jù) 對(duì)象），S 是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。在計(jì)算機(jī)科學(xué)中，對(duì)復(fù)數(shù)的定義：復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)Complex=(C,R)其中：C是包含兩個(gè)實(shí)數(shù)的集合 C1, C2 ,R=P,P是定義在C上的一種關(guān)系 。第17頁

9、/共51頁例、用數(shù)據(jù)結(jié)構(gòu)如何描述2行3列矩陣： 它是一個(gè)含6個(gè)數(shù)據(jù)元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行關(guān)系”和“列關(guān)系”兩個(gè)次序關(guān)系，其中 行關(guān)系為 ， 列關(guān)系為 ，。 意為 x 和 y 之間存在 x領(lǐng)先于y 的次序關(guān)系。654321aaaaaa思考： 如何描述一個(gè)一行六列的矩陣？第18頁/共51頁例1-5 假設(shè)我們需要編制一個(gè)事務(wù)管理的程序，管理學(xué)校科學(xué)研究課題小組的各項(xiàng)事務(wù)，則首先要為程序的操作對(duì)象課題小組設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)。假設(shè)每個(gè)小組由一位教師、一至三名研究生及一至六名本科生組成，小組成員之間的關(guān)系是：教師指導(dǎo)研究生，而由每位研究生指導(dǎo)一至兩名本科生。 則可以

10、如下定義數(shù)據(jù)結(jié)構(gòu)： Group = (P，R) 其中: P = T，G1，Gn，S11Snm 1=n=3，1=m=2， R = R1, R2 R1 = | 1=i=n, 1=n=3 R2 = | 1=i=n, 1=j=m, 1=n=3, 1=m=2 第19頁/共51頁5、數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，可以看作是從具體問題抽象出來的數(shù)據(jù)模型，與數(shù)據(jù)的存儲(chǔ)無關(guān)，也與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置無關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)分類： 線性結(jié)構(gòu) 線性表、棧、隊(duì)列 、串 非線性結(jié)構(gòu) 樹 、圖（或網(wǎng)絡(luò)）第20頁/共51頁6、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(或稱映象）稱為數(shù)據(jù)的存

11、儲(chǔ)結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。（1）數(shù)據(jù)元素的表示：位、字長、元素、結(jié)點(diǎn)、數(shù)據(jù)域（2）關(guān)系的表示兩種基本的存儲(chǔ)方法：順序映像（順序存儲(chǔ)結(jié)構(gòu)）非順序映像（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)） 第21頁/共51頁u順序存儲(chǔ)結(jié)構(gòu): 借助數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)仍然相鄰。u鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針，借助該指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 所有元素存放在可以不連續(xù)的存貯單元中，但元素之間的關(guān)系可以通過地址（指針）確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰

12、的。第22頁/共51頁存儲(chǔ)結(jié)構(gòu)的描述 存儲(chǔ)結(jié)構(gòu)的描述方法隨編程環(huán)境的不同而不同，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述之。 例如，用一維數(shù)組類型描述順序存儲(chǔ)結(jié)構(gòu)，用指針描述鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 例如，定義日期為：typedef struct int y; / 年號(hào) Yearint m; / 月號(hào) Monthint d; / 日號(hào) Day DateType; / 日期類型同樣，此時(shí)對(duì)數(shù)據(jù)元素也要借用高級(jí)編程語言中的數(shù)據(jù)類型描述之。第23頁/共51頁7、數(shù)據(jù)類型（data type） 數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。 數(shù)據(jù)類型可分兩類：原子類型和結(jié)構(gòu)類型。 例如：在C語言中

13、原子類型：整型、實(shí)型、字符型等 結(jié)構(gòu)類型：數(shù)組、結(jié)構(gòu)體、聯(lián)合等第24頁/共51頁9、抽象抽象數(shù)據(jù)類型 (Abstract Data Type簡稱ADT) l由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型l指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。 l例如：計(jì)算機(jī)擁有的整數(shù)類型。l它與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，但其特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽（獨(dú)立于計(jì)算機(jī)）。第25頁/共51頁抽象數(shù)據(jù)類型的描述方法 抽象數(shù)據(jù)類型可用（D，S，P）三元組表示，其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作

14、：基本操作的定義 ADT 抽象數(shù)據(jù)類型名數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼（不真正執(zhí)行的符號(hào)）描述。基本操作的定義格式為： 基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述第26頁/共51頁 基本操作有兩種參數(shù)： 賦值參數(shù)只為操作提供輸入值； 引用參數(shù)以&打頭， 除了可以提供輸入值外，還將返回操作結(jié)果。 “初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。若初始條件為空，則省略之。 “操作結(jié)果” 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。第27頁/共51頁舉例抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADT Complex 數(shù)據(jù)對(duì)象

15、：De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：R1變量1變量n; 輸出語句 printf( 格式串，表達(dá)式1， ，表達(dá)式n);或 cout表達(dá)式1表達(dá)式n;(9)注釋 行注釋 /文字序列(10)基本函數(shù)有 求最大值 max (表達(dá)式l，表達(dá)式n) 求最小值 min (表達(dá)式1，表達(dá)式n) 求絕對(duì)值 abs (表達(dá)式) 求不足整數(shù)值 floor(表達(dá)式)向下取整 求進(jìn)位整數(shù)值 ceil(表達(dá)式)向上取整 判定文件結(jié)束 eof(文件變量)或eof 判定行結(jié)束 eoln(文件變量)或eoln 第35頁/共51頁抽象數(shù)據(jù)類型實(shí)現(xiàn)示例例如利用C語言實(shí)現(xiàn)的“復(fù)數(shù)”類型如下描述：/ 存儲(chǔ)結(jié)構(gòu)的定義typ

16、edef struct float realpart;float imagpart; complex;/ 基本操作的函數(shù)原型說明void Assign( complex &Z, float realval, float imagval );/ 構(gòu)造復(fù)數(shù) Z，其實(shí)部和虛部分別被賦以參數(shù) realval 和 imagval 的值void DestroyComplex( complex &Z) / 銷毀復(fù)數(shù) Zfloat GetReal( cpmplex Z ); / 返回復(fù)數(shù) Z 的實(shí)部值float Getimag( cpmplex Z ); / 返回復(fù)數(shù) Z 的虛部值void add( comp

17、lex z1, complex z2, complex &sum );/ 以 sum 返回兩個(gè)復(fù)數(shù) z1，z2 的和基本操作的實(shí)現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個(gè)復(fù)數(shù) z1，z2 的和sum.realpart = z1.realpart + z2.realpart;sum.imagpart = z1.imagpart + z2.imagpart; 第36頁/共51頁1.4算法和算法分析 算法的定義：是對(duì)特定問題求解步驟的一種描述,是一個(gè)有窮的指令集，這些指令表示一個(gè)或多個(gè)操作。 算法的特性(要素)： 有窮

18、性 算法應(yīng)在執(zhí)行有窮步后結(jié)束,且每一步都在有窮時(shí)間內(nèi)完成 確定性 每步定義都是確切、無歧義的 可行性 算法中描述的操作應(yīng)能通過執(zhí)行有限次已經(jīng)實(shí)現(xiàn)的基本運(yùn)算而實(shí)現(xiàn) 輸入 有0個(gè)或多個(gè)輸入 輸出 有一個(gè)或多個(gè)輸出(處理結(jié)果)。第37頁/共51頁算法設(shè)計(jì)的要求 正確性：不含有語法錯(cuò)誤；對(duì)于各種合法的輸入數(shù)據(jù)能夠得到滿足規(guī)格說明要求的結(jié)果。 可讀性：要求程序有較好的人機(jī)交互性,有助于人們對(duì)算法的理解。 健壯性：對(duì)輸入的非法數(shù)據(jù)能作出適當(dāng)?shù)捻憫?yīng)或處理。 效率與低存儲(chǔ)需求：主要指算法的執(zhí)行時(shí)間和所需的最大存儲(chǔ)空間，這兩方面主要和問題的規(guī)模有關(guān)。第38頁/共51頁算法效率的度量 算法的后期測試 在算法中的某

19、些部位插裝時(shí)間函數(shù) time ( )測定算法完成 某一功能所花費(fèi)時(shí)間。 算法的事前估計(jì)： 空間復(fù)雜度 時(shí)間復(fù)雜度第39頁/共51頁程序運(yùn)行所需要的時(shí)間取決于下列因素： 依據(jù)的算法選用何種策略。 問題的規(guī)模。 書寫程序的語言。 編譯程序所生成目標(biāo)代碼的質(zhì)量。 硬件的速度。 可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”大小，只依賴于問題的規(guī)模（通常用整數(shù)n表示），或者說，它是問題規(guī)模的函數(shù)。第40頁/共51頁 一個(gè)算法所耗費(fèi)的時(shí)間，應(yīng)該是該算法中每條語句的執(zhí)行時(shí)間之和，而每條語句的執(zhí)行時(shí)間又是該語句的執(zhí)行次數(shù)（頻度）與該語句執(zhí)行一次所需時(shí)間的乘積。 語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。 我們假定，每條語句

20、一次執(zhí)行的時(shí)間都是相同的，為單位時(shí)間。這樣我們對(duì)時(shí)間的分析就可以獨(dú)立于軟硬件系統(tǒng)。 時(shí)間復(fù)雜度是問題規(guī)模的函數(shù)T( n )。第41頁/共51頁語句頻度舉例 （a） +x; s=0； +x 的頻度為1 （b） for (i=1; i=n; +i) +x; s+=x; +x的頻度為n （c） for (j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x; +x的頻度為n2第42頁/共51頁時(shí)間復(fù)雜度 設(shè)解決一個(gè)問題的規(guī)模為n ，基本操作被重復(fù)執(zhí)行的次數(shù)是n的一個(gè)函數(shù) f（n），假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，則可記作： T (n) =

21、 O(f(n) 其中T（n）叫算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度， O是Order（數(shù)量級(jí)）的首字母，意思是T（n）與f（n）只差一個(gè)常數(shù)倍。 比較同一問題的不同算法，通常的做法是，從算法中選取一種對(duì)于所研究的問題是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度?；静僮鞯脑僮?數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同。第43頁/共51頁漸進(jìn)時(shí)間復(fù)雜度的計(jì)算 加法規(guī)則 針對(duì)并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) 乘法規(guī)則針對(duì)嵌套程序段 T (n, m) = T1 (n)

22、 * T2 (m) = O(f (n)*g (m) 注：c log2n n nlog2n n2 n3 2n 3n n!第44頁/共51頁x = 0; y = 0;for ( int k = 0; k n; k + ) x +;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)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)第45頁/共51頁例對(duì) n 個(gè)整數(shù)的序列進(jìn)行選擇排序。其中序列的“長度”

23、n 為問題的規(guī)模。void selectSort ( int a , int n ) /對(duì)n個(gè)整數(shù)a0,a1,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 = 0 & Ai != k ) i-; return i;算法的語句 i- 的頻度不僅與 n 有關(guān)，還與 A i 中各元素的取值，以及 k 的取值有關(guān)。第47頁/共51頁算法的空間復(fù)雜度 空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的度量，記作： S(n)

24、 = O(g(n) 表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與g(n)的增長率相同。 算法的存儲(chǔ)量包括： 輸入數(shù)據(jù)所占空間; 程序本身所占空間； 輔助變量所占空間。 第48頁/共51頁說明 算法的所有性能之間都存在著或多或少的相互影響，因此，當(dāng)設(shè)計(jì)一個(gè)算法，特別是大型算法時(shí)，要綜合考慮算法的各項(xiàng)性能、算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語言的特性及算法運(yùn)行的機(jī)器系統(tǒng)環(huán)境等各方面因素，才能設(shè)計(jì)出比較好的算法。 第49頁/共51頁本章小結(jié) 與數(shù)據(jù)結(jié)構(gòu)相關(guān)的幾個(gè)名詞概念 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)） 在數(shù)據(jù)結(jié)構(gòu)上的操作 抽象數(shù)據(jù)類型 算法分析：時(shí)間復(fù)雜度、空間復(fù)雜度第50頁/共51頁感謝您的觀看。第51頁/共51頁