2-抽象數(shù)據(jù)類型的表示與實現(xiàn)、算法課件

抽象數(shù)據(jù)類型、算法學習目的：*了解抽象數(shù)據(jù)類型的表示與實現(xiàn);把握算法的特征和算法分析的方法。重點難點：算法的時間簡潔度和空間簡潔度的概念與分析。1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)1.4算法和算法分析教學內(nèi)容1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)(P9)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。本書承受類C語言，是C語言的一個核心子集。1.預定義常量和類型

//函數(shù)結(jié)果狀態(tài)代碼

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;類C介紹2.數(shù)據(jù)構(gòu)造的表示〔存儲構(gòu)造〕用類型定義typedef描述。數(shù)據(jù)元素類型商定為ElemType，由用戶在使用該數(shù)據(jù)類型時自行定義。typedefintStatus;3.根本操作的算法使用函數(shù)描述函數(shù)類型函數(shù)名〔參數(shù)表〕{//算法說明語句序列}//函數(shù)名

4.賦值語句a=1;a=b=c=1;a=b>10?c:d;5.選擇語句if〔表達式〕語句；if〔表達式〕語句；else語句;switch(表達式){case值1：語句序列1；break;……case值n：語句序列n；break;default:語句序列n+1;}

6.循環(huán)語句for,while,do-while7.完畢語句函數(shù)完畢：return表達式；return；case完畢：break；特殊完畢：exit(特殊代碼)；

8.輸入輸出語句scanf([格式串],變量〕;printf(([格式串],表達式);9.注釋//,/*……*/10.根本函數(shù)max,min,abs,eof,eoln

11.規(guī)律運算商定&&：A&&BA為0時，不再對B求值||：A||BA為非0時，不再對B求值12.構(gòu)造體struct構(gòu)造體類型名{成員說明列表}；structstudent{intnum;charname[20];intage;};structstudentstu1;13.指針

int*p;//定義了一個指向整型變量的指針變量p*p//表示p指向的對象structstudent{intnum;charname[20];intage;}stu1,stu2;stu1.num=1111;typedefstruct{

floatrealpart；

floatimagpart；}complex；//存儲構(gòu)造的定義//根本操作的函數(shù)原型說明voidAssign(complex&Z,floatrealval,floatimagval)；//構(gòu)造復數(shù)Z,其實部和虛局部別被賦以參數(shù)realval和imagval的值例

復數(shù)的實現(xiàn)float

GetReal(cpmplexZ)；

//返回復數(shù)Z的實部值float

Getimag(cpmplexZ)；

//返回復數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個復數(shù)z1,z2的和

//-----根本操作的實現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//以sum返回兩個復數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略}1.4算法和算法分析(P13)1、算法2、算法設計的要求3、算法效率的度量4、算法的存儲空間需求算法是對特定問題求解步驟的一種描述，是指令的有限序列，其中每條指令表示一個或多個操作。算法的描述：本書中使用類C語言。一個算法必需滿足以下五個重要特性：1)有窮性

2)確定性3)可行性4)輸入5)輸出1、算法1)有窮性對于任意一組合法輸入值，在執(zhí)行有窮步驟之后確定能完畢，即：算法中的每個步驟都能在有限時間內(nèi)完成。2)確定性算法中每條指令必需有準確的含義，讀者理解時不會產(chǎn)生二義性，并且在任何條件下，算法都只有唯一的一條執(zhí)行路徑，即對于一樣的輸入只能得出一樣的輸出。3)可行性算法中的全部操作都必需足夠根本，都可以通過已經(jīng)實現(xiàn)的根本操作運算有限次實現(xiàn)之。4)輸入0個或多個輸入。作為算法加工對象的量值，通常表達為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法外表上可以沒有輸入，實際上已被嵌入算法之中。5)輸出一個或多個輸出。它是一組與“輸入”有確定關系的量值，是算法進展信息加工后得到的結(jié)果，這種確定關系即為算法的功能。2、算法設計的要求設計算法時，通常應考慮到達以下目標：1)正確性2)可讀性3)強健性4)高效率與低存儲量需求1)正確性首先，算法應當滿足以特定的“規(guī)格說明”方式給出的需求。其次，對算法是否“正確”的理解可以有以下四個層次：a．程序中不含語法錯誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；c．程序?qū)τ诩毿倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果。一般狀況下，通常以第c層意義的正確性作為衡量一個程序是否合格的標準。2)可讀性算法主要是為了人的閱讀與溝通，其次才是為計算機執(zhí)行，因此算法應當易于人的理解；另一方面，晦澀難讀的程序易于隱蔽較多錯誤而難以調(diào)試。3)強健性當輸入的數(shù)據(jù)非法時，算法應當恰當?shù)刈鞒龇错懟蜻M展相應處理，而不是產(chǎn)生莫名奇異的輸出結(jié)果。并且，處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進展處理。4)效率與低存儲量需求效率指算法執(zhí)行的時間，對于同一個問題假設有多個算法可以解決，執(zhí)行時間短的算法效率高。存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。這兩者都與問題的規(guī)模有關。3、算法效率的度量通常有兩種衡量算法效率的方法:事后統(tǒng)計法缺點：1．必需執(zhí)行程序；2．所得時間的統(tǒng)計量依靠于計算機的軟硬件環(huán)境，會掩蓋算法本質(zhì)。事前分析估算法：有誤差，不準確，但是帶來的效率高于它的誤差。和算法執(zhí)行時間相關的因素有：1〕算法所用“策略”；2〕算法所解問題的“規(guī)模”；3〕編程所用“語言”；4〕“編譯”的質(zhì)量；5〕執(zhí)行算法的計算機的“速度”。明顯，同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進展編譯，或者在不同計算機上運行，效率不同，這說明使用確定的時間單位衡量算法的效率是不適宜的，撇開這些與計算機軟硬件有關的因素，可以認為一個特定算法“運行工作量”的大小，只依靠于問題的規(guī)模-它是問題規(guī)模的函數(shù)。算法=把握構(gòu)造+原操作〔簡潔操作//固有數(shù)據(jù)類型的操作〕為了便于比較同一問題的不同算法，通常從算法中選取一種對于所爭論的問題來說是根本操作的原操作，以該根本操作在算法中重復執(zhí)行的次數(shù)作為算法的時間量度。如：for(i=1;i<=n;++i)

for(j=1;j<=n;++j){

c[i,j]=0;

for(k=1;k<=n;++k)

c[i,j]+=a[i,k]*b[k,j];

}

乘法運算是矩陣相乘問題的根本操作，整個算法的執(zhí)行時間與該根本操作〔乘法〕重復執(zhí)行的次數(shù)n3成正比。一般狀況下，算法中根本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作：T〔n〕=O〔f(n)〕它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率一樣，稱作算法的漸近時間簡潔度，簡稱時間簡潔度。算法的時間簡潔度計算語句頻度：語句重復執(zhí)行的次數(shù)例1：{++x;s=0;}例2：for(i=1;i<=n;++i){++x;s+=x;}例3：for(j=1;j<=n;++j)for(k=1;k<=n;+=k){++x;s+=x;}含根本操作“x增1”的語句的頻度分別為1,n,n2則這3個程序段的時間簡潔度分別為O(1),O(n),O(n2),分別稱為常量階、線性階、平方階。我們總是考慮在最壞狀況下的時間簡潔度，以保證算法的運行時間不會比它更長〔最壞狀況下估算算法執(zhí)行時間的一個上界〕一個特定算法的“運行工作量”的大小，只依靠于問題的規(guī)?！餐ǔＳ谜麛?shù)量n表示〕，或者說，它是問題規(guī)模的函數(shù)。與待處理數(shù)據(jù)的初態(tài)無關。例4for(i=1;i<n;i++){y=y+1;for(j=0;j<=2n;j++)x++;}頻度n-1(n-1)(2n+1)T(n)=n-1+(n-1)(2n+1)=O(n2)例5i=1;while(i<=n)i=i*2;頻度1?設為x，則有：2x<=n,即x<=log2n,所以i=i*2的頻度為log2nT(n)=O(log2n)例6兩個n×n的矩陣相乘。voidMult_matrix(intc[][],inta[][],intb[][]，intn)

{

//a、b和c均為n階方陣，且c是a和b的乘積

for(i=1;i<=n;++i)

for(j=1;j<=n;++j) {

c[i,j]=0;

for(k=1;k<=n;++k)

c[i,j]+=a[i,k]*b[k,j];

}

}//Mult_matrix

算法的時間簡潔度為T(n)=O(n3)

一個算法的時間簡潔度還可以具體分為最好、最差〔最壞〕、平均三種狀況爭論。最好狀況下最簡潔求出，但沒有多大實際意義最差狀況下也簡潔求出，而且這是估量該算法執(zhí)行時間的一個上界平均狀況下最難計算：在很多狀況下地輸入數(shù)據(jù)集消逝的概率難以確定。一般，算法的時間簡潔度如無特殊說明，則指最壞狀況下的時間簡潔度。4、算法的存儲空間需求算法的空間簡潔度定義為:S(n)=O(f(n))表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與f(n)的增長率一樣。算法的存儲量包括:1)輸入數(shù)據(jù)所占空間2)程序本身所占空間3)幫助變量所占空間

假設輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關，則只需要分析除輸入和程序之外的幫助變量所占額外空間。假設所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。假設所需存儲量依靠于特定的輸入，則通常按最壞狀況考慮。

課堂總結(jié)

主要內(nèi)容：了解抽象數(shù)據(jù)類型的表示與實現(xiàn);把握算法的特征和算法分析的方法。重點難點：算法的時間簡潔度和空間簡潔度的概念與分析。作業(yè)：指出