1、主講：戴小鵬 教授 Mobile QQ:357295461 OFFice:6-208 湖南農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院,數(shù)據(jù)結(jié)構(gòu),每天早晨，叫起你的不是鬧鐘，而是夢想,遠見的思維決定了未來的格局,寫在前面的話,如何和我聯(lián)系？ 辦公室：6-208 辦公電話：84618000 MobileEmail： QQ:357295461 作業(yè)題E-Mail: (密碼12345678）出于仁義與道德，不要改 本課程的網(wǎng)站： 00/wlkt/C808/Asp/Root/Index.asp?Mode=1 Data Relation

2、ships: R = |C1,C2 實數(shù) Operations: InitComplex( 初始條件：復(fù)數(shù)T已知 操作結(jié)果： E1,E2分別減C1,C2 ADT Complex,抽象數(shù)據(jù)類型Complex的規(guī)格說明：,2、抽象數(shù)據(jù)類型(ADT),抽象數(shù)據(jù)類型Complex具體的表示和實現(xiàn)依賴于所采用的計算機語言。用戶可以用某種高級語言的固有數(shù)據(jù)類型和自定義數(shù)據(jù)類型，并借助于過程和函數(shù)來表示和實現(xiàn)抽象數(shù)據(jù)類型Complex。C語言表示如下：,抽象數(shù)據(jù)類型Complex的表示：,2、抽象數(shù)據(jù)類型(ADT),struct Complex real RealPart; real ImagPart; ；

3、,Operation 在Complex上可定義下列操作 1）函數(shù)InitComplex生成一個復(fù)數(shù)Z，Z=x+iy Complex InitComplex( real x, real y ); 2）函數(shù)Add求兩個復(fù)數(shù)Z1與Z2之和。 Complex Add( Complex Z1, Complex Z2 ); 或Complex Add( Complex Z, real R1, real R2 ); 3）函數(shù)Sub，求兩個復(fù)數(shù)Z1與Z2之差 Complex Sub( Complex Z1, Complex Z2 ); 或Complex Sub(Complex Z, real R1, real

4、R2 );,2、抽象數(shù)據(jù)類型(ADT),繼下頁,Operation 4）函數(shù)Multiply求兩個復(fù)數(shù)之積 Complex Multiply( Complex Z1, Complex Z2 ); Complex Multiply( Complex Z, real R1, real R2); 5）函數(shù)GetRealPart 取復(fù)數(shù)Z的實部 real GetRealPart( Complex Z ); 6）函數(shù)GetImagPart取函數(shù)Z的虛部 real GetImagPart( Complex Z );,2、抽象數(shù)據(jù)類型(ADT),續(xù)上頁,以上關(guān)于ADT的定義（規(guī)格說明、表示）沒有涉及到實現(xiàn)。

5、正象ADT的名字所暗示的那樣，它是作為實現(xiàn)的公共特征的抽象。但是，從ADT的角度研究數(shù)據(jù)結(jié)構(gòu)的最終目的仍在于應(yīng)用，因此必須仔細(xì)考慮表示方法、算法、實現(xiàn)的技術(shù)及細(xì)節(jié)。而當(dāng)ADT被實現(xiàn)時，ADT中的元素成了數(shù)據(jù)結(jié)構(gòu)的一個實例,而那些操作就成了算法。 由于在ADT的規(guī)格說明中，只指明了其功能而未指定要采用何種方法，因此，實現(xiàn)的獨立性是顯而易見的。,抽象數(shù)據(jù)類型Complex的實現(xiàn)：,2、抽象數(shù)據(jù)類型(ADT),Complex Create( real x, real y ) Complex Z; Z.RealPart = x; Z.ImagPart = y; return Z; Complex Ad

6、d( Complex Z1, Complex Z2 ) Complex Sum; Sum.RealPart = Z1.RealPart + Z2.RealPart; Sum.ImagPart = Z1.ImagPart + Z2.ImagPart; return Sum; (以下略) ,抽象數(shù)據(jù)類型Complex的C語言實現(xiàn)：,2、抽象數(shù)據(jù)類型(ADT),實現(xiàn)ADT,2、抽象數(shù)據(jù)類型(ADT),由于C語言是面向過程的語言，它能支持ADT的實現(xiàn)，但是不能很好的反映ADT的數(shù)據(jù)隱蔽原則。在Pascal語言中，庫單元(Unit)是ADT的較好表示和實現(xiàn)。 隨著面向?qū)ο蠹夹g(shù)的成熟，用面向?qū)ο笾械膶ο?

7、類來描述和實現(xiàn)ADT是非常好的方法。這種方法在面向?qū)ο蟪绦蛟O(shè)計方面已經(jīng)成熟，已經(jīng)廣泛應(yīng)用于不同程序設(shè)計語言及開發(fā)環(huán)境當(dāng)中（如：C+，Object Pascal, VB, Java, PowerBuilder等等）。,下面是Complex采用C+的定義： class Complex private: real RealPart; real ImagPart; public: Complex( real x, real y );/構(gòu)造函數(shù) Complex( Complex /取虛部 C+實現(xiàn)略,C+實現(xiàn)ADT,2、抽象數(shù)據(jù)類型(ADT),3、類C語言語法規(guī)則,類C語言是介于偽碼語言和高級語言之間的

8、一種算法描述語言。 使用類C語言描述算法的好處： 1. 保持C結(jié)構(gòu)清晰、明確直觀等特色； 2. 但又略去一些次要環(huán)節(jié)，抓住主干精華。,2、類C語言語法規(guī)則,函數(shù)類型 過程名(參數(shù)表) /算法說明 語句組; return 結(jié)果； /過程名 當(dāng)返回狀態(tài)結(jié)果時，函數(shù)定義為Status類型。,1）算法以過程或函數(shù)的形式表示,3、類C語言語法規(guī)則,2）賦值語句,簡單賦值 變量名 = 表達式；,串聯(lián)賦值 變量1 = 變量2 = = 表達式；,成組賦值 (變量名1,變量名k)=(表達式1,表達式k);,結(jié)構(gòu)名 = 結(jié)構(gòu)名;,結(jié)構(gòu)名 = (值1, ,值k)；,3、類C語言語法規(guī)則,2）賦值語句,變換賦值 變量

9、1 變量2；,if( 條件 ) 語句1; if( 條件 ) 語句1; else 語句2； /可以嵌套,3）IF語句,3、類C語言語法規(guī)則,switch( 表達式 ) case 條件1：語句1；break; case 條件n：語句n; break; default: 語句 n+1 ,4） Switch語句,switch case 條件1：語句1；break; case 條件n：語句n; break; default: 語句 n+1 ,3、類C語言語法規(guī)則,For語句： for( 處置表達式序列; 條件; 修改表達式系列 ) 語句； While語句： while( 條件 ) 語句； Do-Whil

10、e語句： do 語句; while ( 條件 );,5） 循環(huán)語句,3、類C語言語法規(guī)則,6）基本函數(shù),7）布爾運算符,8）標(biāo)識符,9）常量和類型,第二問題數(shù)據(jù)結(jié)構(gòu)研究什么,？,運算,邏輯結(jié)構(gòu),存儲結(jié)構(gòu),第三問題重新理解算法Algorithm, 算法的概念 算法的描述 算法設(shè)計的要求 算法效率的度量 算法的存儲空間需求,4、算法的描述和算法分析,算法,=,程序,？,算法是為了描述解決某一問題的方法，而不涉及具體的實現(xiàn)細(xì)節(jié)。,算法存在的辨證關(guān)系數(shù)據(jù)結(jié)構(gòu)與算法的辨證關(guān)系,給定了數(shù)據(jù)的邏輯結(jié)構(gòu)后，對同一邏輯結(jié)構(gòu)而言，由于存儲結(jié)構(gòu)的不同，定義的運算也是不同的。 如線性表是一種邏輯結(jié)構(gòu)，若采用順序存儲方

11、法表示，則稱為順序表；若采用鏈?zhǔn)酱鎯Ψ椒ū硎荆瑒t稱為鏈表。 相同的運算在順序表和鏈表上的實現(xiàn)方法是不同的。, 算法的概念,4、算法的描述和算法分析,算法(Algorithm)是對特定問題求解步驟的一種描述，是能在計算機上經(jīng)過有限時間完成的、毫不含糊的指令的有限序列。其中每一條指令表示一個或多個操作。,問題（Problem）是一個函數(shù)，或是輸入和輸出的一種聯(lián)系。程序（Program）是用計算機程序設(shè)計語言實現(xiàn)的完成一定功能的代碼。 算法的實現(xiàn)一定是程序，但程序不一定是算法的實現(xiàn)。,4、算法的描述和算法分析,算法的五個重要特性,1）有窮性：執(zhí)行有限步，每步均在有窮時間內(nèi)完成。,2）確定性：對相同的

12、輸入，必產(chǎn)生相同的輸出，即無二義性。,3）可行性：計算機可使用已實現(xiàn)的基本運算執(zhí)行有限次來完成。,4）輸入：零個或多個輸入。,5）輸出：一個或多個輸出。,4、算法的描述和算法分析,關(guān)于算法性質(zhì)的另一種描述 1、正確性(Correctness) 它必須完成所期望的功能，把每一次輸入轉(zhuǎn)化為正確的輸出。 2、具體步驟(Concrete Steps) 一個算法應(yīng)該由一系列具體步驟組成。 3、確定性(No Ambiguity) 下一步（通常是指算法描述中的下一步）應(yīng)執(zhí)行的步驟必須明確。 4、有限性(Finite) 一個算法必須由有限步組成。 5、可終止性(Terminable) 算法必須可以終止，即不能

13、進入死循環(huán)。,算法的描述,4、算法的描述和算法分析,一個算法可以用各種不同的方法來進行描述。比如可使用某種高級語言、匯編語言甚至機器語言來描述某個算法，亦可使用偽碼語言或框圖等其它形式來描述它。,算法的描述,4、算法的描述和算法分析,描述算法的語言形式,1.文字形式:用中文或英文這樣的文字來描述算法。,2.偽碼形式:用一種仿程序設(shè)計語言的語言來描述算法。,3.程序設(shè)計語言形式:用某種程序設(shè)計語言描述算法。其優(yōu)點是算法不用修改，直接作為程序語句鍵入計算機，計算機能調(diào)用和運行。這里我們采用上講介紹的類C語言來描述算法,4、算法的描述和算法分析,例:設(shè)計一個把存儲在數(shù)組中的有n個抽象數(shù)據(jù)元素a0,

14、a1,an-1逆置的算法，即要求逆置后的數(shù)組中數(shù)據(jù)元素序列為an-1 , , a1 , a0 ,并要求原數(shù)組中的數(shù)據(jù)元素值不能被改變。,void Reverse(int n, DataType a, DataType b) int i; for(i=0;in;i+) bi=an-1-i; /把數(shù)組a的元素逆置后賦給數(shù)組b ,4、算法的描述和算法分析,例1-2:設(shè)計一個把存儲在數(shù)組中的有n個抽象數(shù)據(jù)元素a0, a1,an-1逆置的算法，即要求逆置后的數(shù)組中數(shù)據(jù)元素序列為an-1 , , a1 , a0 ,并要求原數(shù)組中的數(shù)據(jù)元素值被改變。,void Reverse(int n, DataType

15、 a) int i,m=n/2; DataType temp; for(i=0;im;i+) /進行m次調(diào)換 temp=ai; ai=an-1-i; an-1-i=temp; ,在程序設(shè)計中，對算法進行分析是十分重要的。對于一個具體的應(yīng)用實例，通常可能有若干個算法可供選用，應(yīng)判斷哪一個算法在現(xiàn)有的計算機環(huán)境中對解決某個問題是最優(yōu)的。,例5：寫一函數(shù)，用以計算1+2+n的值，其中n為已知。 long SumWork( int n ) int sum = 0; for( int i = 1; i+; i = n ) sum += i; return sum ; ,算法設(shè)計的要求,4、算法的描述和算

16、法分析,long BetterSum( int n ) return (n+1)*n/2; ,算法設(shè)計的要求,4、算法的描述和算法分析,在計算機科學(xué)中，通常使用算法的計算（執(zhí)行）時間和所需的存儲空間來評價算法或程序的優(yōu)劣。 在選擇算法時，除了要考慮算法的運算時間和所需內(nèi)存外，往往還要考慮其它一些重要的因素，即所謂設(shè)計一個“好”的算法應(yīng)考慮達到的下列目標(biāo)。,1）正確性 2）可讀性 3）健壯性 4）效率與低存儲量需求,算法設(shè)計的要求,4、算法的描述和算法分析,1）正確性(Correctness) 能滿足具體問題的需求。正確性對于選擇算法來說，是首要的問題。 正確性的四個層次： a. 程序不含語法錯

17、誤； b. 程序?qū)τ谳斎霐?shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果 (要算對)； c. 程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的輸入 數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果； d. 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明 要求的結(jié)果。,算法設(shè)計的要求,4、算法的描述和算法分析,2）可讀性(Readability) 希望一個算法易于理解、易于編碼，也易于調(diào)試。 3）健壯性(Robustness) 對于異常的處理能力。能作出判斷，并給出適當(dāng)?shù)奶崾净蚓嫘畔?，以等待操作員的干預(yù)或能自動進行適當(dāng)處理。 4）效率(Efficiency)與低存儲需求 效率指算法執(zhí)行時間。同一問題，算法執(zhí)行時間越短，效率越高

18、。存儲量需求指算法執(zhí)行過程中所需的最大存儲空間。此所謂時（執(zhí)行時間）、空（運行空間）效應(yīng)。,算法效率的度量,4、算法的描述和算法分析,算法執(zhí)行時間的度量時間復(fù)雜度 執(zhí)行時間取決于下列因素： a. 選用哪種算法 b. 問題的規(guī)模（輸入的大小/復(fù)雜程度）； c. 所選用的語言； d. 編譯程序所產(chǎn)生可執(zhí)行代碼的質(zhì)量； e. 機器執(zhí)行指令的速度。 1）事后統(tǒng)計 對算法程序的執(zhí)行進行計時。（有缺陷） 2）事前估計 事先估算的主要因素問題的規(guī)模。,算法效率的度量,4、算法的描述和算法分析,一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，算法時間取決于兩者的綜合效果。但是，

19、為便于比較同一問題的不同算法，通常的做法是：從算法中選取一種對于所研究的問題（或算法類型）來說是基本運算的原操作，以該基本運算重復(fù)執(zhí)行的次數(shù)作為算法的時間量度的依據(jù)。,2）事前估計,算法效率的度量,4、算法的描述和算法分析,例6： 兩個nn矩陣相乘，令乘法運算作為基本運算 for( i = 1; i = n; i+ ) for( j = 1; j = n; j+ ) Cij = 0; for( k = 1; k = n; k+ ) Cij += Aik * Bkj; ; 整個算法執(zhí)行時間與乘法操作重復(fù)執(zhí)行的次數(shù)n3成正比，記作 T(n)=O(n3). 兩個nn矩陣相乘的時間復(fù)雜度為O(n3).

20、,算法效率的度量,4、算法的描述和算法分析,定義：某算法執(zhí)行時間T(n)是O(f(n)，意指存在正的常數(shù)M和n0，使對于一切n n0，T(n) Mf(n)都成立。如果一個程序的時間復(fù)雜度是O(f(n)，就說該程序的運行時間增加率的一個上界為f(n)，或說T(n)是f(n)的大O函數(shù)。,例7：設(shè)T(n)=n2+4n，則有f(n)=n2，即有： n2 + 4n = O(n2). 因為存在M=2，n0=4，使對于一切nn0，恒有 n2 +4n2 n2,4、算法的描述和算法分析,大O運算規(guī)則 規(guī)則一 對于任何的常數(shù)k和任何的函數(shù)f，恒有kf(n)=O(f(n)，即大O忽略常數(shù)因子。 規(guī)則二 若f(n)

21、=O(g(n)且g(n)=O(h(n)，則f(n)=O(h(n)，即大O的概念是傳遞的。 規(guī)則三 若定義maxf(n)，g(n)為f(n)與g(n)兩者中增長率較快的函數(shù)，則有f(n)+g(n)=O(maxf(n),g(n). 規(guī)則四 若f1(n)=O(g1(n)且f2(n)=O(g2(n)，則f1(n)f2(n)=O(g1(n) g2(n)，即大O符合乘法規(guī)則。 有關(guān)數(shù)學(xué)問題：/型不定式極限 有關(guān)數(shù)學(xué)定理：羅比塔法則,例8 求時間函數(shù)8nlog(n)+4n3/2的大O. (1) log(n)=O(n1/2) 定義 (2) nlog(n)=O(nn1/2)= O(n3/2) 規(guī)則四 (3) 8

22、nlog(n)=8O(n3/2)= O(n3/2) 規(guī)則一 (4) 4n3/2=O(n3/2) 規(guī)則一 (5) 8nlog(n)+ 4n3/2 =O(max8nlog(n)， 4n3/2） 規(guī)則三 max8nlog(n)， 4n3/2 = maxO(n3/2) ， O(n3/2) = O(n3/2) 8nlog(n)+ 4n3/2= O(O(n3/2) 所以有 = O(n3/2) 規(guī)則二 8nlog(n)+ 4n3/2= O(n3/2).,4、算法的描述和算法分析,例9: 設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個n階矩陣相乘運算算法的時間復(fù)雜度。,for(i=0;in;i+) for(j=0;

23、jn;j+) cij=0; /基本語句1 for(k=0;kn;k+) cij=cij+aik*bkj; /基本語句2 ,解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),有f(n)=c1n2+ c2n3,因 T(n)= f(n)=c1n2+ c2n3c n3, 其中c1 , c2 , c均為常數(shù)，所以該算法的時間復(fù)雜度為 T(n)=O(n3),例：求兩個方陣的乘積 CA*B define n 自然數(shù) MATRIXMLT(float Ann,float Bnn,float Cnn) int i, j, k; for(i=0;in;i+) for(j=0;jn;j+) Cij=0; for( k=0;kn;k

24、+) Cij=Aik*Bkj ,/ n+1,/ n(n+1),/ n*n,/ n*n*(n+1),/ n*n*n,例10: 設(shè)n為如下算法處理的數(shù)據(jù)個數(shù)，求如下算法的時間復(fù)雜度。 for(i=1;i=n;i=2*i) couti=i;,解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),有2f(n) n,即有f(n) log2n。 因T(n)= f(n) log2n c log2 n,所以該算法的時間復(fù)雜度為 T(n)=O(log2n)。,例11:下邊的算法是用冒泡排序法對數(shù)字a中的n個整數(shù)類型的數(shù)據(jù)元素(a0an-1)，從小到大進行排序，求該算法的時間復(fù)雜度。,void BubbleSort(int a,i

25、nt n) int i,j,flag=1; int temp; for(i=1;iaj+1) flag=1; temp=aj; aj=aj+1; aj+1=temp; ,解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),最壞情況下有 f(n)n+4*n2/2 因T(n)=f(n) n+2* n2 c* n2, 其中c為常數(shù)，所以該算法的時間復(fù)雜度為 T(n)=O(n2)。,算法的時間復(fù)雜度是衡量一個算法好壞的重要指標(biāo)。一般來說，具有多項式時間復(fù)雜度的算法，是可接受、可實際使用的算法;具有指數(shù)時間復(fù)雜度的算法，是只有當(dāng)n足夠小時才可使用的算法。,例12 下面的算法是在一個有n個數(shù)據(jù)元素的數(shù)組a中刪除第I個位置

26、的數(shù)組元素，要求當(dāng)刪除成功時數(shù)組元素個數(shù)減1，求該算法的時間復(fù)雜度。其中數(shù)組下標(biāo)從0至n-1。,int Delete(int a, int /刪除成功返回 ,解:假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概率的,設(shè)Pi為刪除第i個位置上數(shù)據(jù)元素的概率，則有Pi=1/n，設(shè)E為刪除數(shù)組元素的平均次數(shù)，則有,因T(n)=E(n+1)/2 c*n,其中c為常數(shù)，所以該算法的等概率平均時間復(fù)雜度為 T(n)= O(n)。,例13: 對比在數(shù)據(jù)元素個數(shù)為30000時，冒泡排序算法和快速排序算法的實際耗時。 根據(jù)問題的要求，設(shè)計測試程序，并在計算機上實際運行。 程序運行結(jié)果：冒泡排序: 6.00 秒；快速排序:

27、0.00 秒 程序運行結(jié)果說明：系統(tǒng)中的difftime (end,start)函數(shù)以秒為單位計時，快速排序的實際耗時少于0.5 秒，所以輸出顯示為0.00 秒。程序運行結(jié)果說明，當(dāng)數(shù)據(jù)元素個數(shù)足夠大時，理論分析的快速排序算法優(yōu)于冒泡排序算法的結(jié)果，和程序的實際測試結(jié)果吻合。,算法耗時的實際測試,算法的時間復(fù)雜度是衡量一個算法好壞的重要指標(biāo)。一般來說，具有多項式時間復(fù)雜度（如O(n)、O(n2)、O(n6)、O(n8)等）的算法，是可接受、可實際使用的算法；而具有指數(shù)時間復(fù)雜度（如O(2n)、O(nn)、O(n！)等）的算法，是理論上可以計算，但實際上不可計算的問題，通常稱作難解的問題。 對于

28、具有多項式時間復(fù)雜度的算法，無論數(shù)據(jù)元素個數(shù)多大（只要是有限的數(shù)值），算法都可以在有限的時間內(nèi)運行完成；而對于難解的問題，當(dāng)n足夠小時，算法可以在有限的時間內(nèi)運行完成，當(dāng)n比較大時，其運行時間將是一個天文數(shù)字！,數(shù)據(jù)元素個數(shù)和時間復(fù)雜度,常數(shù)階 對數(shù)階 線性階 線性對數(shù)階 平方階 立方階 K次方階 指數(shù)階,常見的時間復(fù)雜度，按數(shù)量級遞增排序：,存儲空間需求,4、算法的描述和算法分析,算法所需存儲空間的度量空間復(fù)雜度（性） 算法的空間復(fù)雜度S(n)就是一個算法或程序所需要的存儲單元數(shù)。 一個非遞歸程序，并且不含有動態(tài)數(shù)據(jù)結(jié)構(gòu)，在它還未開始執(zhí)行前，所需存儲單元總數(shù)即已確定。為簡化計算，在算法的空間復(fù)雜度分析中，將忽略程序中所有的簡單變量和程序的執(zhí)行代碼本身所占的內(nèi)存空間，而只統(tǒng)計與問題大小有關(guān)的數(shù)組等結(jié)構(gòu)變量所需的內(nèi)存量，有時當(dāng)一些數(shù)據(jù)、結(jié)構(gòu)變量要占用相當(dāng)可觀的常數(shù)量單元時，也可進行統(tǒng)