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

抽象數(shù)據(jù)類(lèi)型、算法學(xué)習(xí)目的：*了解抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn);駕馭算法的特征和算法分析的方法。重點(diǎn)難點(diǎn)：算法的時(shí)間困難度和空間困難度的概念與分析。1.3抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)1.4算法和算法分析教學(xué)內(nèi)容1.3抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)(P9)抽象數(shù)據(jù)類(lèi)型須要通過(guò)固有數(shù)據(jù)類(lèi)型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型)來(lái)實(shí)現(xiàn)。本書(shū)接受類(lèi)C語(yǔ)言，是C語(yǔ)言的一個(gè)核心子集。1.預(yù)定義常量和類(lèi)型

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

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

4.賦值語(yǔ)句a=1;a=b=c=1;a=b>10?c:d;5.選擇語(yǔ)句if（表達(dá)式）語(yǔ)句；

if（表達(dá)式）語(yǔ)句；else語(yǔ)句;switch(表達(dá)式){case值1：語(yǔ)句序列1；break;……case值n：語(yǔ)句序列n；break;default:語(yǔ)句序列n+1;

}

6.循環(huán)語(yǔ)句for,while,do-while7.結(jié)束語(yǔ)句函數(shù)結(jié)束：return表達(dá)式；return；case結(jié)束：break；異樣結(jié)束：exit(異樣代碼)；

8.輸入輸出語(yǔ)句scanf([格式串],變量）;printf(([格式串],表達(dá)式);9.注釋//,/*……*/10.基本函數(shù)

max,min,abs,eof,eoln

11.邏輯運(yùn)算約定

&&：A&&BA為0時(shí)，不再對(duì)B求值||：A||BA為非0時(shí)，不再對(duì)B求值12.結(jié)構(gòu)體struct結(jié)構(gòu)體類(lèi)型名{

成員說(shuō)明列表}；structstudent{intnum;charname[20];intage;};structstudentstu1;13.指針

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

floatrealpart；

floatimagpart；}complex；//存儲(chǔ)結(jié)構(gòu)的定義//基本操作的函數(shù)原型說(shuō)明void

Assign(complex&Z,

floatrealval,floatimagval)；//構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)realval

和imagval

的值例

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

GetReal(cpmplexZ)；

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

Getimag(cpmplexZ)；

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

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

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

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

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

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

2)確定性3)可行性4)輸入5)輸出1、算法1)有窮性對(duì)于隨意一組合法輸入值，在執(zhí)行有窮步驟之后確定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。2)確定性算法中每條指令必需有精確的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性，并且在任何條件下，算法都只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出。3)可行性算法中的全部操作都必需足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。4)輸入0個(gè)或多個(gè)輸入。作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量須要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒(méi)有輸入，事實(shí)上已被嵌入算法之中。

5)輸出一個(gè)或多個(gè)輸出。它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。2、算法設(shè)計(jì)的要求設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1)正確性2)可讀性3)健壯性4)高效率與低存儲(chǔ)量需求1)正確性首先，算法應(yīng)當(dāng)滿(mǎn)足以特定的“規(guī)格說(shuō)明”方式給出的需求。其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．程序中不含語(yǔ)法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿(mǎn)足要求的結(jié)果；c．程序?qū)τ诩?xì)心選擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿(mǎn)足要求的結(jié)果；d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿(mǎn)足要求的結(jié)果。一般狀況下，通常以第c層意義的正確性作為衡量一個(gè)程序是否合格的標(biāo)準(zhǔn)。2)可讀性算法主要是為了人的閱讀與溝通，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)當(dāng)易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。3)健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇異的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4)效率與低存儲(chǔ)量需求效率指算法執(zhí)行的時(shí)間，對(duì)于同一個(gè)問(wèn)題假如有多個(gè)算法可以解決，執(zhí)行時(shí)間短的算法效率高。存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所須要的最大存儲(chǔ)空間。這兩者都與問(wèn)題的規(guī)模有關(guān)。3、算法效率的度量通常有兩種衡量算法效率的方法:事后統(tǒng)計(jì)法缺點(diǎn)：1．必需執(zhí)行程序；2．所得時(shí)間的統(tǒng)計(jì)量依靠于計(jì)算機(jī)的軟硬件環(huán)境，會(huì)掩蓋算法本質(zhì)。事前分析估算法：有誤差，不精確，但是帶來(lái)的效率高于它的誤差。和算法執(zhí)行時(shí)間相關(guān)的因素有：1）算法所用“策略”；2）算法所解問(wèn)題的“規(guī)?！?；3）編程所用“語(yǔ)言”；4）“編譯”的質(zhì)量；5）執(zhí)行算法的計(jì)算機(jī)的“速度”。明顯，同一個(gè)算法用不同的語(yǔ)言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同計(jì)算機(jī)上運(yùn)行，效率不同，這表明運(yùn)用確定的時(shí)間單位衡量算法的效率是不合適的，撇開(kāi)這些與計(jì)算機(jī)軟硬件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依靠于問(wèn)題的規(guī)模-它是問(wèn)題規(guī)模的函數(shù)。算法=限制結(jié)構(gòu)+原操作（簡(jiǎn)潔操作//固有數(shù)據(jù)類(lèi)型的操作）為了便于比較同一問(wèn)題的不同算法，通常從算法中選取一種對(duì)于所探討的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法的時(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];

}

乘法運(yùn)算是矩陣相乘問(wèn)題的基本操作，整個(gè)算法的執(zhí)行時(shí)間與該基本操作（乘法）重復(fù)執(zhí)行的次數(shù)n3成正比。一般狀況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間量度記作：T（n）=O（f(n)）它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱(chēng)作算法的漸近時(shí)間困難度，簡(jiǎn)稱(chēng)時(shí)間困難度。算法的時(shí)間困難度計(jì)算語(yǔ)句頻度：語(yǔ)句重復(fù)執(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”的語(yǔ)句的頻度分別為1,n,n2則這3個(gè)程序段的時(shí)間困難度分別為O(1),O(n),O(n2),分別稱(chēng)為常量階、線性階、平方階。我們總是考慮在最壞狀況下的時(shí)間困難度，以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)（最壞狀況下估算算法執(zhí)行時(shí)間的一個(gè)上界）一個(gè)特定算法的“運(yùn)行工作量”的大小，只依靠于問(wèn)題的規(guī)模（通常用整數(shù)量n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。與待處理數(shù)據(jù)的初態(tài)無(wú)關(guān)。例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?設(shè)為x，則有：2x<=n,即x<=log2n,所以i=i*2的頻度為log2nT(n)=O(log2n)例6兩個(gè)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

算法的時(shí)間困難度為T(mén)(n)=O(n3)

一個(gè)算法的時(shí)間困難度還可以具體分為最好、最差（最壞）、平均三種狀況探討。最好狀況下最簡(jiǎn)潔求出，但沒(méi)有多大實(shí)際意義最差狀況下也簡(jiǎn)潔求出，而且這是估計(jì)該算法執(zhí)行時(shí)間的一個(gè)上界平均狀況下最難計(jì)算：在很多狀況下地輸入數(shù)據(jù)集出現(xiàn)的概率難以確定。一般，算法的時(shí)間困難度如無(wú)特殊說(shuō)明，則指最壞狀況下的時(shí)間困難度。4、算法的存儲(chǔ)空間需求算法的空間困難度定義為:S(n)=O(f(n))表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與f(n)的增長(zhǎng)率相同。算法的存儲(chǔ)量包括:1)輸入數(shù)據(jù)所占空間2)程序本身所占空間3)幫助變量所占空間

若輸入數(shù)據(jù)所占空間只取決于問(wèn)題本身，和算法無(wú)關(guān)，則只須要分析除輸入和程序之外的幫助變量所占額外空間。若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱(chēng)此算法為原地工作。若所需存儲(chǔ)量依靠于特定的輸入，則通常按最壞狀況考慮。

課堂總結(jié)

主要內(nèi)容：了解抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn);駕馭算法的特征和算法分析的方法。重點(diǎn)難點(diǎn)：算法的時(shí)間困難度和空間困難度的概念與分析