數(shù)據(jù)結(jié)構(gòu)選講DATASTRUCTURE課件.ppt

1、數(shù)據(jù)結(jié)構(gòu)選講DATA STRUCTURE,主講教師： 羅 熊 Instructor: LUO Xiong E-mail: ,課程內(nèi)容： 計(jì)算機(jī)軟件的基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu) 課時(shí)安排： 數(shù)據(jù)結(jié)構(gòu)32學(xué)時(shí) 教 材： 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu). 北京：清華大學(xué)出版社，1997. 參考書(shū)： 數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語(yǔ)言篇） 李春葆 數(shù)據(jù)結(jié)構(gòu)題集 嚴(yán)蔚敏，吳偉民 數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用C+語(yǔ)言描述 （英文版） Sartaj Sahni McGraw-Hill long; unsigned float float; double; long double,2、指針類型 3、數(shù)組類型 4、字符串 5、結(jié)構(gòu)體類型 6、

2、共用體類型 7、枚舉類型 8、自定義類型,1.4 用C語(yǔ)言編寫(xiě)算法的注意事項(xiàng),1、避免使用出現(xiàn)二義性的表達(dá)式,i+; i = + i; i = 1; j = i + + + i -,2、避免使用轉(zhuǎn)向語(yǔ)句 3、避免使用預(yù)處理 4、避免函數(shù)返回值隱含說(shuō)明,1.5 算法設(shè)計(jì)目標(biāo)和算法效率度量,定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列 特性： 輸入 有0個(gè)或多個(gè)輸入 輸出 有一個(gè)或多個(gè)輸出(處理結(jié)果) 確定性 每步定義都是確切、無(wú)歧義的 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束 有效性 每一條運(yùn)算應(yīng)足夠基本 算法的描述:c+,c,PASCAL等語(yǔ)言,2021/3/12,28,算法有

3、這樣一些特點(diǎn)： 1、有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個(gè)指令序列的執(zhí)行在有限的時(shí)間內(nèi)結(jié)束。 2、確定性：算法中的每一個(gè)步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。 3、有零個(gè)或多個(gè)輸入 4、有一個(gè)或多個(gè)輸出 5、有效性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。例如：被零除的計(jì)算動(dòng)作是不能被有效執(zhí)行的,設(shè)計(jì)算法的基本方法:把一個(gè)具體問(wèn)題轉(zhuǎn)變成一個(gè)算法 事例學(xué)習(xí)：選擇排序問(wèn)題 明確問(wèn)題：非遞減排序 解決方案：逐個(gè)選擇最小數(shù)據(jù) 算法框架： for ( int i=0; in-2; i+ ) /n-1趟 從ai檢查到an-1;若最小的整數(shù)在ak, 交

4、換ai與ak; 細(xì)化程序：程序 SelectSort,算法設(shè)計(jì) 自頂向下，逐步求精,性能分析與度量,算法的性能標(biāo)準(zhǔn) 算法的后期測(cè)試 算法的事前估計(jì),2021/3/12,31,分析評(píng)價(jià)算法時(shí)應(yīng)考慮的因素： 1、正確性 在給定有效的輸入數(shù)據(jù)后，算法經(jīng)過(guò)有窮時(shí)間的計(jì)算能給出正確的答案。 2、復(fù)雜度 時(shí)間復(fù)雜度 3、簡(jiǎn)單性 4、最優(yōu)性 算法A是最優(yōu)的是指：在給定問(wèn)題的所有算法中，A執(zhí)行的進(jìn)步運(yùn)算次數(shù)最少 5、可讀性 要求算法易于理解，便于分析 6、可修改可擴(kuò)展性 如果問(wèn)題P 的一個(gè)算法是A，為了解答一個(gè)與P類似的問(wèn)題，希望對(duì)A稍做改動(dòng)就可正確運(yùn)行，如算法A滿足這一點(diǎn)，則說(shuō)A的可修改性好,2021/3/

5、12,32,與算法效率有關(guān)的因素,程序設(shè)計(jì)語(yǔ)言 編譯的代碼質(zhì)量 機(jī)器執(zhí)行指令的速度 問(wèn)題的規(guī)模,2021/3/12,33,求解同樣一個(gè)問(wèn)題可能會(huì)有許多不同的算法，如何評(píng)價(jià)這些算法的好壞呢？ 首先算法必須是正確的。此外還需考慮： 1、算法易于理解，易于編程（在計(jì)算機(jī)上實(shí)現(xiàn)） ，易于調(diào)試。 2、要求算法高效，節(jié)省時(shí)間與空間。 一個(gè)算法運(yùn)行所需時(shí)間的長(zhǎng)短、空間的大小具有非常重要的意義。 時(shí)間和空間相互之間有一種制約關(guān)系，何者為重需視具體情況而定,2021/3/12,34,算法高效與算法易理解、易編程之間也有一種制約關(guān)系 這兩個(gè)要求有時(shí)互相矛盾。因此，對(duì)反復(fù)運(yùn)行的算法，首先考慮的是高效性，對(duì)偶爾運(yùn)行的

6、算法，則需突出算法易理解和易編程（以排序?yàn)槔?冒泡排序和快速排序,2021/3/12,35,我們重點(diǎn)考慮時(shí)間因素。 一個(gè)算法所耗費(fèi)的時(shí)間，應(yīng)該是該算法中每條語(yǔ)句的執(zhí)行時(shí)間之和，而每條語(yǔ)句的執(zhí)行時(shí)間又是該語(yǔ)句的執(zhí)行次數(shù)（頻度）與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。 我們假定，每條語(yǔ)句一次執(zhí)行的時(shí)間都是相同的，為單位時(shí)間。這樣我們對(duì)時(shí)間的分析就可以獨(dú)立于軟硬件系統(tǒng),2021/3/12,36,我們將算法求解問(wèn)題的輸入量稱為問(wèn)題的規(guī)模，用一個(gè)整數(shù)來(lái)表示，一個(gè)算法的時(shí)間復(fù)雜度是該算法的時(shí)間耗費(fèi)，一般地說(shuō)，時(shí)間復(fù)雜度是問(wèn)題規(guī)模的函數(shù) T( n )。 當(dāng)問(wèn)題的規(guī)模n 趨于無(wú)窮大時(shí)，把時(shí)間復(fù)雜度T( n )的數(shù)量級(jí)

7、（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度（有時(shí)簡(jiǎn)稱為時(shí)間復(fù)雜度）。 嚴(yán)格的數(shù)學(xué)定義為：若T( n ) 和 f( n ) 是定義在正整數(shù)集合上的兩個(gè)函數(shù)，當(dāng)存在兩個(gè)正的乘數(shù)C和n0時(shí)，使得對(duì)所有的,成立，則,都有,這時(shí)稱T( n )的時(shí)間復(fù)雜度為f( n )數(shù)量級(jí),2021/3/12,37,算法運(yùn)行所需要的時(shí)間與兩個(gè)因素有關(guān)： 1、問(wèn)題實(shí)例的大小 （如1000個(gè)數(shù)的排序）； 2、實(shí)例的具體情況 （如1000個(gè)數(shù)的排列情況,2021/3/12,38,算法分析 1、假定每條語(yǔ)句的執(zhí)行時(shí)間為單位時(shí)間。算法的時(shí)間復(fù)雜度是該算法中所有語(yǔ)句的執(zhí)行頻度之和,2021/3/12,39,例：求兩個(gè)方陣的乘積 CA*B de

8、fine 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+) / Cij=Aik*Bkj /,2021/3/12,40,2、一般情況下，對(duì)步進(jìn)循環(huán)語(yǔ)句只考慮循環(huán)體語(yǔ)句的執(zhí)行次數(shù)，而忽略該語(yǔ)句中部長(zhǎng)加一、終值判別、循環(huán)轉(zhuǎn)移等成份。因此，當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度所決定的,2021/3/12,41,例： x=0;y=0; for (k=1;k=n;k+) x+;

9、for (i=1;i=n;i+) for (j=1;j=n;j+) /n*n y,一般情況下，對(duì)步進(jìn)循環(huán)語(yǔ)句只需考慮循環(huán)體中語(yǔ)句的執(zhí)行次數(shù)，而忽略循環(huán)體中步長(zhǎng)加1、終值判斷、控制轉(zhuǎn)移等成分,2021/3/12,42,例： x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x,2021/3/12,43,3、選擇執(zhí)行的成分，如 if 語(yǔ)句的執(zhí)行時(shí)間，決定于then 子句、else 子句耗時(shí)較多的部分 4、如果算法的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)，則算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1,例： temp = i; i = j; j = temp,2021/3/12,44,5、很多算法的時(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模有關(guān)，而且還與它所處理的數(shù)據(jù)集的狀態(tài)有關(guān)。通常是根據(jù)數(shù)據(jù)集中可能出現(xiàn)的最壞情況估計(jì)出算法的最壞時(shí)間復(fù)雜度,2021/3/12,45,例： i=n-1; while (i=0,此問(wèn)題不僅與規(guī)模 n 有關(guān)，而且與數(shù)組A中各元素的取值有關(guān),例： fact(n) if (n = 1) return 1; else return