數(shù)據(jù)結構課件第1章

1、 第一章第一章 緒緒 論論 上課前需要說明的幾個問題：上課前需要說明的幾個問題： 任課教師：王歲花任課教師：王歲花 聯(lián)系電話：聯(lián)系電話：13663901273136639012732.2.交流信箱：交流信箱：3.3.公共信箱：公共信箱： 公共信箱：公共信箱： 密碼：密碼： dsggxx2008dsggxx20084.4.關于數(shù)據(jù)結構課程：關于數(shù)據(jù)結構課程： 教材、重要性、時間按排（教材、重要性、時間按排（54+3654+36） 考試成績考試成績= =期末考試期末考試* *70%+70%+平時成績平時成績* *30%30%5.5.平時成績主要是實驗作業(yè)完成情況，實驗每次平時成績主要是實驗作業(yè)完成

2、情況，實驗每次點名，隨機抽查驗收，查看程序運行。點名，隨機抽查驗收，查看程序運行。 第一章第一章 緒緒 論論 1.1 1.1 什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構1.2 1.2 基本概念和術語基本概念和術語1.4 1.4 算法和算法分析算法和算法分析1.3 1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型本章小結、本章小結、教材、參考文獻教材、參考文獻作作 業(yè)業(yè) 第一章第一章 緒緒 論論 1.1 1.1 什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構1) 1) 數(shù)據(jù)結構討論的范疇數(shù)據(jù)結構討論的范疇Niklaus WirthNiklaus Wirth 程序程序= =數(shù)據(jù)結構數(shù)據(jù)結構+ +算法算法 用計算機解決一個具體問題時，大致需要經(jīng)過

3、下列用計算機解決一個具體問題時，大致需要經(jīng)過下列幾個步驟幾個步驟:（1）抽象出一個適當?shù)臄?shù)學模型）抽象出一個適當?shù)臄?shù)學模型（2）設計一個解此數(shù)學模型的算法）設計一個解此數(shù)學模型的算法（3）編出程序進行測試、修改直至得到最終結果。）編出程序進行測試、修改直至得到最終結果。 第一章第一章 緒緒 論論 例例1. 1. 田徑賽的時間安排問題田徑賽的時間安排問題 設有六個比賽項目，規(guī)定每個選手至多可參加三個設有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示），設計比項目，有五人報名參加比賽（如下表所示），設計比賽日程表，使得用盡可能少的時間段完成比賽。賽日程表，使得用盡可能

4、少的時間段完成比賽。姓姓 名名項項 目目1項項 目目2項項 目目3丁丁 一一馬馬 二二張張 三三李李 四四王王 五五跳跳 高高標標 槍槍標標 槍槍鉛鉛 球球跳跳 遠遠跳跳 遠遠100米米鉛鉛 球球100米米200米米200米米跳跳 高高200米米用無向圖的用無向圖的著色問題解著色問題解決！決！ 第一章第一章 緒緒 論論 （1 1）設用如下六個不同的代號代表不同的項目：）設用如下六個不同的代號代表不同的項目： 跳高跳高 跳遠跳遠 標槍標槍 鉛球鉛球 100100米米 200200米米 A A B B C D E C D E F F （2 2）用頂點代表比賽項目）用頂點代表比賽項目 （3 3）用邊

5、連接不能同時進行比賽的項目）用邊連接不能同時進行比賽的項目 如下圖所示：如下圖所示：姓姓 名名項目項目1項目項目2項目項目3丁丁 一一馬馬 二二張張 三三李李 四四王王 五五ACCDBBEDEFFAF 第一章第一章 緒緒 論論 韋爾奇韋爾奇. .鮑威爾（鮑威爾（Welch Powell)Welch Powell)方法：方法： 1.1.將圖將圖G G中的結點按中的結點按度度遞減的順序排列。遞減的順序排列。 2.2.用沒有用過的顏色對第一個點著色，并且按排列用沒有用過的顏色對第一個點著色，并且按排列次序，對與前面著色點不相鄰的點著相同顏色。次序，對與前面著色點不相鄰的點著相同顏色。 3.3.從序列

6、中刪除第從序列中刪除第2 2步著過色的點。步著過色的點。 4.4.重復第重復第2 2、3 3步，直到序列為空。步，直到序列為空。 第一章第一章 緒緒 論論 例例: :對上例，執(zhí)行算法第對上例，執(zhí)行算法第1 1步結果為：步結果為： F ,A , E ,B , C ,D F ,A , E ,B , C ,D 重復執(zhí)行第重復執(zhí)行第2,32,3步序列變化為：步序列變化為： A,E,B,C,D E,B,D B A,E,B,C,D E,B,D B 圖的變化為：圖的變化為： 第一章第一章 緒緒 論論 數(shù)據(jù)結構數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計是一門研究非數(shù)值計算的程序設計問題中計算機操作對象以及它們之間

7、關系和操問題中計算機操作對象以及它們之間關系和操作等的學科。作等的學科。2) 數(shù)據(jù)結構數(shù)據(jù)結構 對研究對研究對象對象及其之間及其之間關系關系的描述。的描述。結構結構數(shù)據(jù)結構的形式定義為數(shù)據(jù)結構的形式定義為: : 數(shù)據(jù)結構是一個二元組數(shù)據(jù)結構是一個二元組 Data_Structures = (D, S)Data_Structures = (D, S)其中其中:D :D ：是數(shù)據(jù)元素的有限集：是數(shù)據(jù)元素的有限集 S S ：是：是 D D上關系的有限集上關系的有限集。（邏輯結構）（邏輯結構） 第一章第一章 緒緒 論論 1.2 1.2 基本概念和術語基本概念和術語 數(shù)據(jù)數(shù)據(jù)(Data):(Data):

8、是對信息的一種符號表示。在計算機科是對信息的一種符號表示。在計算機科學中是指所有能被輸入到計算機中并被計算機程序處學中是指所有能被輸入到計算機中并被計算機程序處理的符號的總稱。理的符號的總稱。數(shù)據(jù)元素數(shù)據(jù)元素(Data Element(Data Element):):是數(shù)據(jù)的基本單位，在計是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)項數(shù)據(jù)項(Data Item(Data Item）: :一個數(shù)據(jù)元素可由若干個數(shù)據(jù)一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象

9、數(shù)據(jù)對象(Data Object)(Data Object)：是性質相同的數(shù)據(jù)元素的：是性質相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。集合。是數(shù)據(jù)的一個子集。 第一章第一章 緒緒 論論 數(shù)據(jù)結構數(shù)據(jù)結構: :是相互之間存在一種或多種特定關系的數(shù)是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。據(jù)元素的集合。根據(jù)數(shù)據(jù)元素間關系的不同，數(shù)據(jù)結構或分為根據(jù)數(shù)據(jù)元素間關系的不同，數(shù)據(jù)結構或分為四種：四種：線性結構：線性結構：結構中的數(shù)據(jù)元素之間結構中的數(shù)據(jù)元素之間 存在一對一的關系。存在一對一的關系。樹型結構（層次結構）：樹型結構（層次結構）：結構中的數(shù)結構中的數(shù)據(jù)元素之間存在一對多的關系。據(jù)元素之間存

10、在一對多的關系。圖狀結構圖狀結構（網(wǎng)狀結構）：結構中的（網(wǎng)狀結構）：結構中的數(shù)據(jù)元素之間存在多對多的關系。數(shù)據(jù)元素之間存在多對多的關系。集集 合：合：結構中的數(shù)據(jù)元素除了結構中的數(shù)據(jù)元素除了 同屬于一個集合外，別無其它關系。同屬于一個集合外，別無其它關系。Data_Structures = (D, S)Data_Structures = (D, S)（邏輯結構）（邏輯結構） 第一章第一章 緒緒 論論 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構 邏輯結構在存儲器中的映象邏輯結構在存儲器中的映象“數(shù)據(jù)元素數(shù)據(jù)元素”的映象的映象 ？“關系關系”的映象的映象 ？數(shù)據(jù)元素的映象方法：數(shù)據(jù)元素的映象方法：用二進制位用二

11、進制位(bit)(bit)的位串表示數(shù)據(jù)元素的位串表示數(shù)據(jù)元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2 第一章第一章 緒緒 論論 1 1. .順序映象順序映象 ：借助于元素在計算機存儲器中的存借助于元素在計算機存儲器中的存儲位置來描述元素之間的邏輯關系。儲位置來描述元素之間的邏輯關系。 例：關系的映象方法（表示例：關系的映象方法（表示 的方法）的方法） xyz2.2.鏈式映象鏈式映象 借助于指示元素存儲地址的指針表示借助于指示元素存儲地址的指針表示元素之間的邏輯關系元素之間的邏輯關系 。 xyz 第一章第一章 緒緒 論論

12、 在不同的編程環(huán)境中，在不同的編程環(huán)境中，存儲結構可有不同的描述方法。存儲結構可有不同的描述方法。 當用高級程序設計語言進行編程時，通?？捎酶呒壆斢酶呒壋绦蛟O計語言進行編程時，通?？捎酶呒壘幊陶Z言中提供的數(shù)據(jù)類型描述之。編程語言中提供的數(shù)據(jù)類型描述之。 第一章第一章 緒緒 論論 數(shù)據(jù)類型：數(shù)據(jù)類型：數(shù)據(jù)類型是一個值的集合和定義在這組值數(shù)據(jù)類型是一個值的集合和定義在這組值 集上的一組操作的總稱。集上的一組操作的總稱。例如：例如：C-語言中的語言中的int , float , char等等抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type 簡稱簡稱ADT) ：是指一個是指一個數(shù)學模型以

13、及定義在此數(shù)學模型上的一組操作。數(shù)學模型以及定義在此數(shù)學模型上的一組操作。 第一章第一章 緒緒 論論 抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的描述方法: : 抽象數(shù)據(jù)類型可用（抽象數(shù)據(jù)類型可用（D D，S S，P P）三元組表示）三元組表示, ,其其中，中，D D是數(shù)據(jù)對象，是數(shù)據(jù)對象，S S是是D D上的關系集，上的關系集，P P是對是對D D的基本的基本操作集。操作集。 本門課采用下面格式表示抽象數(shù)據(jù)類型：本門課采用下面格式表示抽象數(shù)據(jù)類型：ADT ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義數(shù)據(jù)關系：數(shù)據(jù)關系：數(shù)據(jù)關系的定義數(shù)據(jù)關系的定義基本操作：基

14、本操作：基本操作的定義基本操作的定義 ADT ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 第一章第一章 緒緒 論論 其中，數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼描述，基本其中，數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼描述，基本操作的定義格式為：操作的定義格式為：基本操作名（參數(shù)表）基本操作名（參數(shù)表）初始條件：初始條件：初始條件描述初始條件描述操作結果：操作結果：操作結果描述操作結果描述基本操作有兩種參數(shù)基本操作有兩種參數(shù)：賦值參數(shù)：賦值參數(shù)只為操作提供輸入值；只為操作提供輸入值；引用參數(shù)引用參數(shù)以以& &打頭，打頭， 除可提供輸入值外，還將帶回操作除可提供輸入值外，還將帶回操作結果。結果。引用變量和

15、引用參數(shù)引用變量和引用參數(shù) 第一章第一章 緒緒 論論 “ “初始條件初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結構和參描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息?；叵鄳鲥e信息。若初始條件為空，則省略之。若初始條件為空，則省略之。 “操作結果操作結果”說明了操作正常完成之后，數(shù)據(jù)說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。結構的變化狀況和應返回的結果。 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程高級編程語言中已實現(xiàn)的數(shù)據(jù)類型語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。來實現(xiàn)。例如：抽象

16、數(shù)據(jù)類型三元組的定義：例如：抽象數(shù)據(jù)類型三元組的定義：P9 第一章第一章 緒緒 論論 #includestdio.hvoid main( ) int x=3, y=4, &z=x; printf(x=%d, y=%d, z=%dn,x,y,z); z=x+y; printf(x=%d, y=%d, z=%dn,x,y,z); 運行結果運行結果:x=3, y=4, z=3x=7, y=4, z=7 第一章第一章 緒緒 論論 void sum1(int a,int b,int c) c=a+b; return;void sum2(int a,int b,int &c) c=a+b;

17、 return;void main( )void main( ) int x=3,y=4,z=5; int x=3,y=4,z=5; printf(x=%d,y=%d,z=%dn,x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); sum1(x,y,z); sum1(x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); sum2(x,y,z); sum2(x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); printf(x=%d,y=%d,z=%dn,x,y

18、,z); 運行結果運行結果x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=7x=3,y=4,z=7 第一章第一章 緒緒 論論 - / - 采用動態(tài)分配的順序存儲結構采用動態(tài)分配的順序存儲結構- typedef ElemType typedef ElemType * *Triplet;Triplet;/ / 由由InitTripletInitTriplet分配三個元素存儲空間分配三個元素存儲空間/ Triplet/ Triplet類型是類型是ElemTypeElemType類型的指針類型的指針/存放存放ElemTypeElemType類

19、型的地址類型的地址例如：抽象數(shù)據(jù)類型三元組的定義：例如：抽象數(shù)據(jù)類型三元組的定義：P9 第一章第一章 緒緒 論論 bo1_1.cpp / bo1_1.cpp 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型TripletTriplet和和ElemTypeElemType/(/(由由c1_1.hc1_1.h定義定義) )的基本操作的基本操作(8(8個個) )Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3) /操作結果操作結果: :構造三元組構造三元組T,T,依次置依次置T T的三個元素的初的三個元素的初 /值為值為v1,v2v1

20、,v2和和v3v3 if(!(T=(ElemType *)malloc(3*sizeof(ElemType) exit(OVERFLOW); T0=v1,T1=v2,T2=v3; return OK; 第一章第一章 緒緒 論論 Status Get(Triplet T,int i, ElemType &e) /初始條件：三元組初始條件：三元組T T已存在，已存在，1i31i3。 /操作結果：用操作結果：用e e返回返回T T的第的第i i元的值元的值 if(i3) return ERROR; e=Ti-1; return OK; Status Put(Triplet T,int i,E

21、lemType e) /初始條件：三元組初始條件：三元組T T已存在，已存在，1i31i3。 /操作結果：改變操作結果：改變T T的第的第i i元的值為元的值為e e if(i3) return ERROR; Ti-1=e; return OK; 第一章第一章 緒緒 論論 Status IsAscending(Triplet T) / / 初始條件：三元組初始條件：三元組T T已存在。操作結果：如果已存在。操作結果：如果 /T/T的三個元素按升序排列，返回的三個元素按升序排列，返回1 1，否則返回，否則返回0 0 return(T0=T1&T1=T1&T1=T2); 第一章第一

22、章 緒緒 論論 Status Max(Triplet T,ElemType &e)Status Max(Triplet T,ElemType &e) / / 初始條件：三元組初始條件：三元組T T已存在。已存在。 / / 操作結果：用操作結果：用e e返回返回T T的三個元素中的最大值的三個元素中的最大值 e=(T0=T1)?(T0=T2)?T0:T2):e=(T0=T1)?(T0=T2)?T0:T2): (T1 =T2)?T1:T2);T1 =T2)?T1:T2); return OK; return OK; Status Min(Triplet T,ElemType &am

23、p;e)Status Min(Triplet T,ElemType &e) / / 初始條件：三元組初始條件：三元組T T已存在。已存在。 /操作結果：用操作結果：用e e返回返回T T的三個元素中的最小值的三個元素中的最小值 e=(T0=T1)?(T0=T2)?T0:T2)e=(T0=T1)?(T0=T2)?T0:T2): : ( (T1=T2)?T1:T2);T1=0)n=0)個初始數(shù)據(jù)的輸入。個初始數(shù)據(jù)的輸入。 （5 5）輸出：）輸出：一個算法有一個或多個與輸入有某種關系一個算法有一個或多個與輸入有某種關系的有效信息的輸出。的有效信息的輸出。 第一章第一章 緒緒 論論 3 3）算

24、法設計的要求）算法設計的要求 正確性、可讀性、健壯性和效率與存儲量要求。正確性、可讀性、健壯性和效率與存儲量要求。 第一章第一章 緒緒 論論 程序正確性的五個層面：程序正確性的五個層面： （1 1）不含語法錯誤）不含語法錯誤 （2 2）程序對于）程序對于n n組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結果。求的結果。 （3 3）程序對于精心選擇的典型、邊界性的）程序對于精心選擇的典型、邊界性的n n組輸入數(shù)組輸入數(shù)據(jù)能得出滿足規(guī)格說明要求的結果。據(jù)能得出滿足規(guī)格說明要求的結果。 （4 4）程序對于一切合適的輸入數(shù)據(jù)都能得出滿足規(guī)）程序對于一切合適的輸入數(shù)據(jù)都能得出滿足

25、規(guī)格說明要求的結果（窮舉）。格說明要求的結果（窮舉）。 （5 5）用數(shù)學方法證明程序的正確性用數(shù)學方法證明程序的正確性 第一章第一章 緒緒 論論 嫦娥一號：嫦娥一號：98.8萬行源代碼，萬行源代碼， 421萬份文件，萬份文件， 打印打印出來有出來有23000頁。用了頁。用了160多萬行程序證明它的正確多萬行程序證明它的正確 性。性。可讀性、健壯性和效率與存儲量要求?？勺x性、健壯性和效率與存儲量要求。 第一章第一章 緒緒 論論 4 4）高效率與低存儲量需求）高效率與低存儲量需求通常，效率指的是通常，效率指的是算法執(zhí)行時間算法執(zhí)行時間；存儲量指的是；存儲量指的是算法執(zhí)行過程中算法執(zhí)行過程中所需的最

26、大存儲空間所需的最大存儲空間，兩者都與問題的，兩者都與問題的規(guī)模有關。規(guī)模有關。算法效率的衡量方法和準則算法效率的衡量方法和準則衡量算法效率的方法衡量算法效率的方法: :缺點：缺點：1 1必須執(zhí)行程序必須執(zhí)行程序 2 2其它因素掩蓋算法本質其它因素掩蓋算法本質事后統(tǒng)計法：事后統(tǒng)計法：事前分析估算法事前分析估算法 第一章第一章 緒緒 論論 和算法執(zhí)行時間有關的因素：和算法執(zhí)行時間有關的因素：1 1算法選用的策略算法選用的策略2 2問題的規(guī)模問題的規(guī)模3 3編寫程序的語言編寫程序的語言4 4編譯程序產(chǎn)生的機器代碼的質量編譯程序產(chǎn)生的機器代碼的質量5 5計算機執(zhí)行指令的速度計算機執(zhí)行指令的速度 一個

27、特定一個特定算法的算法的“運行工作量運行工作量” 的大小，只的大小，只依賴于依賴于問題的規(guī)模問題的規(guī)模（通常用整數(shù)量（通常用整數(shù)量n表示），或表示），或者說，者說，它是問題規(guī)模的函數(shù)它是問題規(guī)模的函數(shù)f(n) f(n) 。 第一章第一章 緒緒 論論 算法算法 = = 控制結構控制結構 + + 原操作原操作 /基本操作基本操作 （固有數(shù)據(jù)類型的操作）（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間算法的執(zhí)行時間 = =原操作原操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時間的執(zhí)行時間 算法的執(zhí)行時間算法的執(zhí)行時間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和 成正比成正比 從算法中選取一

28、種對于所研究的問題來說是從算法中選取一種對于所研究的問題來說是 基基本操作本操作 的原操作，以該基本操作的原操作，以該基本操作 在算法中重復執(zhí)在算法中重復執(zhí)行的次數(shù)行的次數(shù) 作為算法運行時間的衡量準則。作為算法運行時間的衡量準則。 第一章第一章 緒緒 論論 表示隨著問題規(guī)模的增大，算法執(zhí)行時間增長增表示隨著問題規(guī)模的增大，算法執(zhí)行時間增長增長率和長率和 f(n)f(n)相同，稱作算法的漸近時間復雜度，簡相同，稱作算法的漸近時間復雜度，簡稱為時間復雜度。稱為時間復雜度。一般情況下，算法中基本操作執(zhí)行的次數(shù)是問題一般情況下，算法中基本操作執(zhí)行的次數(shù)是問題規(guī)模規(guī)模n n的某個函數(shù)的某個函數(shù)f(n),

29、f(n),算法的時間量度記作：算法的時間量度記作：T (n) = O(f(n)T (n) = O(f(n)= MnT (n)limf(n) ( M M 是是00的常數(shù)的常數(shù)) ) 也可以用：也可以用： 第一章第一章 緒緒 論論 如何估算算法的時間復雜度？如何估算算法的時間復雜度？例：例：2n2n3 3+1000n+1000n2 2+1=O(n+1=O(n3 3) ) 1000n 1000n2 2+n+1000000= O(n+n+1000000= O(n2 2) ) 第一章第一章 緒緒 論論 例例一一兩兩個個矩矩陣陣相相乘乘void mult(int a, int b, int c )void

30、 mult(int a, int b, int c ) / / 以二維數(shù)組存儲矩陣元素，以二維數(shù)組存儲矩陣元素，c c 為為 a a 和和 b b 的乘積的乘積 for (i=1; i=n; +i)for (i=1; i=n; +i) for (j=1; j=n; +j) for (j=1; j=n; +j) cij = 0; cij = 0; for (k=1; k=n; +k) for (k=1; k=1 & change; for (i=n-1, change=TRUE; i=1 & change; -i)i) / bubble_sort / bubble_sort ch

31、ange = FALSE; change = FALSE; / change / change 為元素進行交換標志為元素進行交換標志 for (j=0; ji; +j)for (j=0; j aj+1) if (aj aj+1) aj aj aj+1; change = TRUE ; aj+1; change = TRUE ; / / 一趟冒泡一趟冒泡交換次數(shù)：交換次數(shù)：最好情況：最好情況：0 0最壞情況：最壞情況：n(n-1)/2n(n-1)/2 第一章第一章 緒緒 論論 最壞情況下的時間復雜度最壞情況下的時間復雜度平均時間復雜度平均時間復雜度若不特別說明，以后我們所說的都是最壞情若不特別說

32、明，以后我們所說的都是最壞情況下的時間復雜度況下的時間復雜度 第一章第一章 緒緒 論論 常見函數(shù)的時間復雜度常見函數(shù)的時間復雜度按數(shù)量遞增排列及增長按數(shù)量遞增排列及增長率。率。 常數(shù)階常數(shù)階O(1)O(1) 對數(shù)階對數(shù)階O(logO(log2 2n)n) 線性階線性階O(n)O(n) 線性對數(shù)階線性對數(shù)階O(nlogO(nlog2 2n)n) 平方階平方階O(nO(n2 2) ) 立方階立方階O(nO(n3 3) ) 多項式多項式階階O(nO(nk k) ) 指數(shù)階指數(shù)階O(2O(2n n） 第一章第一章 緒緒 論論 1.10 按增長率由小到大的排列順序是：按增長率由小到大的排列順序是： (2

33、/3)n , 2100, log2(log2n) , log2n , (log2n)2, ,n2/3, n/log2n , n , nlog2n , n3/2, (4/3)n , (3/2)n ,n log2n , n! , nn解題依據(jù)為：解題依據(jù)為： n 122lim0 (1)mxxxmm 2limlogxxx 第一章第一章 緒緒 論論 4) 4) 算法的存儲空間需求算法的存儲空間需求算法的空間復雜度定義為算法的空間復雜度定義為: : 表示隨著問題規(guī)模表示隨著問題規(guī)模 n n 的增大，算法運行的增大，算法運行所需存儲量的增長率與所需存儲量的增長率與 g(n) g(n) 的增長率相同。的增長

34、率相同。S(n) = O(g(n)S(n) = O(g(n)算法的存儲量包括算法的存儲量包括: :輸入數(shù)據(jù)所占空間輸入數(shù)據(jù)所占空間程序本身所占空間程序本身所占空間輔助變量所占空間輔助變量所占空間 第一章第一章 緒緒 論論 若輸入數(shù)據(jù)所占空間只取決于問題本身，和算若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關，則只需要分析法無關，則只需要分析除輸入和程序之外的輔助變除輸入和程序之外的輔助變量所占額外空間。量所占額外空間。 若需存儲量依賴于特定的輸入，則通常按最壞若需存儲量依賴于特定的輸入，則通常按最壞情況考慮。情況考慮。 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，若所需額外空間相對于輸入數(shù)據(jù)量來

35、說是常數(shù)，則稱此算法為則稱此算法為原地工作原地工作。例如在進行冒泡排序時所。例如在進行冒泡排序時所需的額外的空間就是一個常數(shù)需的額外的空間就是一個常數(shù), ,空間復雜度為空間復雜度為O(1)O(1)。 第一章第一章 緒緒 論論 本章小結本章小結1.1.基本概念和術語基本概念和術語 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結構、數(shù)據(jù)對象、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結構、數(shù)據(jù)對象、數(shù)據(jù)結構（邏輯結構、存儲結構、運算）、多形數(shù)數(shù)據(jù)結構（邏輯結構、存儲結構、運算）、多形數(shù)據(jù)類型、抽象數(shù)據(jù)類型（定義、表示和實現(xiàn)）據(jù)類型、抽象數(shù)據(jù)類型（定義、表示和實現(xiàn)）2.2.抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：描述、類：描述、類-C-C中的

36、基本語句和函數(shù)中的基本語句和函數(shù)3.3.算法：算法：算法的時間復雜度（漸近時間復雜度、最壞算法的時間復雜度（漸近時間復雜度、最壞情況下的時間復雜度和平均時間復雜度），算法的情況下的時間復雜度和平均時間復雜度），算法的空間復雜度（原地工作、額外空間）。對空間復雜度（原地工作、額外空間）。對O O的理解的理解 第一章第一章 緒緒 論論 4.4.編程常用頭文件：編程常用頭文件： #include #include #include / malloc( ),alloc( ),realloc( )等等 #include / INT_MAX等等 #include / EOF(=Z或或F6),NULL #i

37、nclude / srand( ) ,rand( ),exit(n) #include / eof( ) #include / floor(),ceil( ),abs( ) #include / exit(n) #include / cout,cin 第一章第一章 緒緒 論論 5. 5. 函數(shù)結果狀態(tài)代碼函數(shù)結果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; / Status是函數(shù)的類型是函

38、數(shù)的類型,/其值是函數(shù)結果狀態(tài)代碼，如其值是函數(shù)結果狀態(tài)代碼，如OK等等 typedef int Boolean; / Boolean是布爾類型是布爾類型,其其/值是值是TRUE或或FALSE 第一章第一章 緒緒 論論 6. 6.上機環(huán)境及注意事項上機環(huán)境及注意事項 上機環(huán)境上機環(huán)境VC+6.0 ,VC+6.0 ,但我們不用面象對象的思想；但我們不用面象對象的思想；除了使用除了使用VCVC中提供的中提供的引用參數(shù)引用參數(shù)的概念外，全用的是標的概念外，全用的是標準準C C。 所有用戶定義的類型，必須先定義后使用！所有用戶定義的類型，必須先定義后使用！例如：例如：ElemType ElemType 在使用時，應根據(jù)情況定義它的具在使用