第2章面向?qū)ο蟪绦蛟O(shè)計和算法性能分析課件

第2章面向?qū)ο蟪绦蛟O(shè)計和算法性能分析2.1抽象數(shù)據(jù)類型

2.2面向?qū)ο蟪绦蛟O(shè)計和類2.3對象2.4算法、算法設(shè)計目標和算法性能分析第2章面向?qū)ο蟪绦蛟O(shè)計和算法性能分析2.1抽象數(shù)據(jù)2.1抽象數(shù)據(jù)類型

2.1.1數(shù)據(jù)結(jié)構(gòu)計算機是對各種各樣的數(shù)據(jù)進行處理的機器。在計算機中如何組織數(shù)據(jù)，如何處理數(shù)據(jù)，從而如何更好地利用數(shù)據(jù)是計算機學(xué)科的基本研究內(nèi)容。

數(shù)據(jù)（Data）這個術(shù)語在計算機數(shù)據(jù)處理中含義非常廣泛，可以認為它是描述客觀事物的數(shù)字、字符、圖形、圖像、聲音等所有能輸入到計算機中并能為計算機接受的電子信號的集合。2.1抽象數(shù)據(jù)類型

2.1.1數(shù)據(jù)結(jié)構(gòu)它們依靠多媒體(多種傳輸信息媒體)的支持，能為計算機所存儲、處理和傳輸。在本書中所說的數(shù)據(jù)僅指常規(guī)媒體所支持的數(shù)字、字符等信號，不包括其他媒體所支持的聲音、圖形、圖像等信號。

數(shù)據(jù)元素（DataElement）是計算機中描述數(shù)據(jù)的基本單位。在大多數(shù)情況下，一個數(shù)據(jù)元素由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。如對學(xué)生登記問題中，每個數(shù)據(jù)元素就可包括學(xué)號、姓名、班級等，學(xué)號、姓名、班級等就稱作該數(shù)據(jù)元素的數(shù)據(jù)項。學(xué)生登記問題的數(shù)據(jù)結(jié)構(gòu)是最簡單的線性表結(jié)構(gòu)。它們依靠多媒體(多種傳輸信息媒體)的

邏輯結(jié)構(gòu)（LogicalStructure）是數(shù)據(jù)元素的邏輯表示方式。如圖2―1就是一組數(shù)據(jù)元素的邏輯結(jié)構(gòu)。圖2―1學(xué)生登記數(shù)據(jù)元素邏輯結(jié)構(gòu)（LogicalStruc

存儲結(jié)構(gòu)（StoreStructure）是數(shù)據(jù)元素在計算機中的存儲方式。數(shù)據(jù)元素可以有多種存儲形式，如圖2―1所示的學(xué)生登記中的數(shù)據(jù)元素既可用一個足夠大的數(shù)組存儲，也可用一個如圖2―2所示的單鏈表存儲。圖2―2單鏈表存儲存儲結(jié)構(gòu)（StoreStruct操作集合不同的問題要求實現(xiàn)的操作集合將不同，一個數(shù)據(jù)元素集合上允許（或要求）的所有操作構(gòu)成了該數(shù)據(jù)元素的操作集合。如上述學(xué)生登記問題就可能要求實現(xiàn)插入、刪除、打印等操作。

數(shù)據(jù)結(jié)構(gòu)（DataStructure）表示數(shù)據(jù)元素間的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)以及這個數(shù)據(jù)元素集合上的操作集合的總稱。如上述學(xué)生登記問題中數(shù)據(jù)元素集合和數(shù)據(jù)元素集合上的操作集合就構(gòu)成一種稱為線性表的數(shù)據(jù)結(jié)構(gòu)。操作集合不同的問題要求實現(xiàn)的操作集合數(shù)據(jù)結(jié)構(gòu)課程研究程序設(shè)計中常用的各種數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素間的邏輯關(guān)系和這些數(shù)據(jù)元素集合上的操作集合，它們的不同的存儲結(jié)構(gòu)（或稱存儲方法），以及不同存儲結(jié)構(gòu)下各種操作的實現(xiàn)方法。依據(jù)數(shù)據(jù)元素之間的關(guān)系，數(shù)據(jù)結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)中各個數(shù)據(jù)元素依次排列在一個線性序列中。線性結(jié)構(gòu)有線性表、堆棧、隊列、字符串、數(shù)組等；非線性結(jié)構(gòu)中各個數(shù)據(jù)元素可能與多個其他數(shù)據(jù)元素發(fā)生聯(lián)系，非線性結(jié)構(gòu)有二叉樹、樹、堆、集合、圖等。數(shù)據(jù)結(jié)構(gòu)課程研究程序設(shè)計中常用的各種2.1.2數(shù)據(jù)類型

類型是一組值的集合。

數(shù)據(jù)類型（DataType）是指一個類型和定義在該類型上的操作集合。

2.1.2數(shù)據(jù)類型2.1.3抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（AbstractDataType，ADT）是用戶在數(shù)據(jù)類型基礎(chǔ)上自己定義和實現(xiàn)的數(shù)據(jù)類型。類似于在計算機機器語言的位、字節(jié)和字的基礎(chǔ)上引入整數(shù)、浮點數(shù)、雙精度數(shù)、字符等數(shù)據(jù)類型的思想方法，高級程序設(shè)計語言使用者可以在高級程序設(shè)計語言整數(shù)、浮點數(shù)、雙精度數(shù)、字符等數(shù)據(jù)類型的基礎(chǔ)上引入各種新的數(shù)據(jù)類型提供給自己或他人使用，從而使自己或他人的程序編制達到更高一級的數(shù)據(jù)抽象。這種由用戶自己定義和實現(xiàn)的新的數(shù)據(jù)類型稱為抽象數(shù)據(jù)類型。2.1.3抽象數(shù)據(jù)類型因此我們說，抽象數(shù)據(jù)類型是用戶在數(shù)據(jù)類型基礎(chǔ)上自己定義和實現(xiàn)的數(shù)據(jù)類型。一種抽象數(shù)據(jù)類型定義了一種新的數(shù)據(jù)元素集合和數(shù)據(jù)元素集合上所允許的操作集合。抽象數(shù)據(jù)類型是用戶通過更高一級抽象得到的新的數(shù)據(jù)類型。抽象數(shù)據(jù)類型在更高一級的抽象程度上實現(xiàn)了信息的隱藏和封裝。因此我們說，抽象數(shù)據(jù)類型是用戶在數(shù)據(jù)ClassSeqList{private:Datatypedata［MaxListSize］;intsize;//數(shù)據(jù)元素個數(shù)public:SeqList(void);//構(gòu)造函數(shù)~SeqList(void);//析構(gòu)函數(shù)intListSize(void)const;//返回元素的個數(shù)sizeintListEmpty(void)const;//表空返回1；否則返回0intFind(Datatype&item)const;//返回元素item在表中的位置DatatypeGetData(intpos)const;//返回位置pos的元素voidInsert(constDatatype&item,intpos);//在位置pos插入元素itemDatatypeDelete(constintpos);//刪除位置pos的元素并返回voidClearList(void);//把表清空};ClassSeqList2.1.5模塊化軟件設(shè)計的特點抽象數(shù)據(jù)類型是軟件設(shè)計中的模塊化方法，而模塊化的軟件設(shè)計方法有以下特點：1代碼可重用所設(shè)計的抽象數(shù)據(jù)類型能像整數(shù)、浮點數(shù)、雙精度數(shù)、字符等高級程序設(shè)計語言中的數(shù)據(jù)類型一樣重復(fù)使用。2.1.5模塊化軟件設(shè)計的特點2信息隱藏抽象數(shù)據(jù)類型封裝了數(shù)據(jù)元素的具體存儲方法和各種操作的具體實現(xiàn)方法，抽象數(shù)據(jù)類型的使用者只需根據(jù)調(diào)用界面調(diào)用它們，無需了解抽象數(shù)據(jù)類型數(shù)據(jù)元素存儲方法和各種操作實現(xiàn)方法的具體細節(jié)，從而像程序設(shè)計語言中的數(shù)據(jù)類型一樣實現(xiàn)了信息隱藏。2信息隱藏3可靠性提高基于模塊的軟件開發(fā)可以大大降低軟件的復(fù)雜度，所以可以提高軟件的可靠性。4便于軟件調(diào)試和維護由于抽象數(shù)據(jù)類型具有信息隱藏的優(yōu)點，軟件設(shè)計只需考慮高一級的程序結(jié)構(gòu)，無需考慮封裝在抽象數(shù)據(jù)類型中的實現(xiàn)細節(jié)，所以基于抽象數(shù)據(jù)類型的軟件設(shè)計便于調(diào)試和維護。3可靠性提高2.2面向?qū)ο蟪绦蛟O(shè)計和類

面向?qū)ο蟪绦蛟O(shè)計（OrientedObjectProgramming）是以類設(shè)計為核心的一種新的程序設(shè)計方法，它是基于抽象數(shù)據(jù)類型程序設(shè)計方法的進一步發(fā)展。2.2面向?qū)ο蟪绦蛟O(shè)計和類面類（Class）是面向?qū)ο蟪绦蛟O(shè)計中相同對象的抽象描述。類包括數(shù)據(jù)成員和方法兩部分。數(shù)據(jù)成員是類封裝起來、只允許類方法操作的數(shù)據(jù)元素。方法是類所提供的操作，把類提供的操作稱作方法，是因為類中數(shù)據(jù)成員的存取只能由類提供的“方法”進行。類（Class）是面向?qū)ο蟪绦蛟O(shè)計中類的構(gòu)成：1直接定義按照類的定義構(gòu)成。2派生派生類是指該類是由一個或一個以上（通常是一個）的已有類派生構(gòu)造而成。類的構(gòu)成：classparent{protected: charversion;public: parent(){version='A';}};classderive1:publicparent{private: intinfo;public: derive1(intnumber){ info=number; } voidprint(){ cout<<version<<info; }};派生類的類構(gòu)造方法使類具有了繼承機制。派生類對象既獨自具有該類特有的數(shù)據(jù)成員和方法，又同時具有基類中共同的數(shù)據(jù)成員和方法。classparent{派生類的類構(gòu)造方法使類具有了繼承機3合成合成類是指該類是由一個或一個以上的已有類合成構(gòu)造而成。例如，下例中的線是由兩個點構(gòu)成的，因此線類可由點類合成。classPoint{private:floatx,y;//點的坐標public:Point(floath,floatv);//構(gòu)造函數(shù)floatGetX(void)const;//取x坐標3合成FloatGetY(void)const;//取y坐標voidDraw(void)const;//在{x,y}處劃點}；ClassLine{private:Pointp1,p2;//線的兩個點位置public:Line(Pointa,Pointb);//構(gòu)造函數(shù)voidDraw(void)const;//劃線連接點p1和p2}；FloatGetY(void)const;2.3對象對象（Object）是類的實例化。2.3對象對象（O＃include"graph.h"Voidmain(void){Inti=0,j=i;Pointpoint1(0,0),point2(3,4);Lineline1(point1,point2);......}＃include"graph.h"2.4算法、算法設(shè)計目標和算法性能分析2.4.1算法

算法（Algorithms）是對特定問題求解步驟描述的計算機指令的有限序列。算法滿足以下性質(zhì)：2.4算法、算法設(shè)計目標和算法性能分析2.4.1算（1）輸入性：具有零個或若干個輸入量。（2）輸出性：至少產(chǎn)生一個輸出或執(zhí)行一個有意義操作。（3）有限性：計算機的指令執(zhí)行序列是有限的。（4）確定性：每一條指令的含義明確，無二義性。（5）可執(zhí)行性：每一條指令都應(yīng)在有限的時間內(nèi)完成。（1）輸入性：具有零個或若干個輸入量。2.4.2算法設(shè)計目標算法設(shè)計應(yīng)滿足以下五個目標：（1）正確性：

（2）可讀性：（3）健壯性：（4）高時間效率：（5）低內(nèi)存要求2.4.2算法設(shè)計目標（3）健壯性：算法的高時間效率和低內(nèi)存要求通常是矛盾的。例如，有些問題若采用較多的內(nèi)存空間可使時間效率提高，若采用較少的內(nèi)存空間則使時間效率降低。在目前計算機硬件價格快速下降的趨勢下，算法的時間效率應(yīng)首先予以考慮。算法的高時間效率和低內(nèi)存要求通常是矛2.4.3算法的時間效率算法的時間效率是通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量的。程序在計算機上運行所消耗的時間與下列因素有關(guān)：（1）書寫算法的程序設(shè)計語言；（2）編譯產(chǎn)生的機器語言代碼質(zhì)量；（3）機器執(zhí)行指令的速度；（4）問題的規(guī)模，即算法的時間效率與算法處理的數(shù)據(jù)個數(shù)n的關(guān)系。2.4.3算法的時間效率僅考慮算法本身的因素，則算法的時間效率只與問題的規(guī)模n有關(guān)。因此算法的時間效率是問題規(guī)模的函數(shù)，算法的時間效率也稱作算法的時間復(fù)雜度T(n)。算法的時間效率分析通常采用O(f(n))表示法。僅考慮算法本身的因素，則算法的時間定義：T(n)=O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤cf(n)。換句話說，O(f(n))給出了函數(shù)f(n)的上界。事實上分析一個算法中基本語句的執(zhí)行次數(shù)就可求出該算法的時間復(fù)雜度。

（1）x=x+1；時間復(fù)雜度為O(1)，稱為常量階；（3）for(i=1;i<=n;i++) for(j=1;j<=n;j++)x=x+1;時間復(fù)雜度為O(n2),稱為平方階。（2）for(i=1;i<=n;i++)x=x+1;時間復(fù)雜度為O(n)，稱為線性階；定義：T(n)=O(f(n))當(dāng)且僅例2―1設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個n階矩陣相乘運算程序段的時間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<n;j++){c［i］［j］=0;for(k=0;k<n;k++)c［i］［j］=c［i］［j］+a［i］［k］*b［k］

}例2―1設(shè)數(shù)組a和b在前邊部分解設(shè)基本語句的執(zhí)行次數(shù)為f(n)，有f(n)=n2+n3因程序段的時間復(fù)雜度T(n)=f(n)=n2+n3≤c*n3=O(n3)，其中c為常數(shù)，所以該程序段的時間復(fù)雜度為O(n3)。解例2―2設(shè)n為如下程序段處理的數(shù)據(jù)個數(shù)，求如下程序段的時間復(fù)雜度。for(i=1;i<=n;i=2*i)printf(“i=%d／n”,i);／*基本語句*／解設(shè)基本語句的執(zhí)行次數(shù)為f(n)，有2f(n)-1≤n,即有f(n)≤lbn+1因程序段的時間復(fù)雜度T(n)=f(n)≤lbn+1≤c*lbn=O(lbn)，其中c為常數(shù)，所以該程序段的時間復(fù)雜度為O(lbn)。例2―2設(shè)n為如下程序段處理的數(shù)據(jù)例2―3下邊的算法是用冒泡排序法對數(shù)組a中的n個整數(shù)類型的數(shù)據(jù)元素（a［0］--a［n-1］）從小到大排序的算法，求該算法的時間復(fù)雜度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){例2―3下邊的算法是用冒泡排序法對if(a［j］>a［j+1］){flag=1;temp=a［j］;a［j］=a［j+1］;a［j+1］=temp;}}}}if(a［j］>a［j+1］)解這個算法的時間復(fù)雜度隨待排序數(shù)據(jù)的不同而不同。當(dāng)某次排序過程中沒有任何兩個數(shù)組元素交換位置，則表明數(shù)組元素已排序完畢，此時算法將因標記flag=0不滿足循環(huán)條件而結(jié)束。但是，在最壞情況下，每次排序過程中都至少有兩個數(shù)組元素交換位置，因此，應(yīng)按最壞情況計算該算法的時間復(fù)雜度。設(shè)基本語句的執(zhí)行次數(shù)為f(n)，最壞情況下有f(n)=n+4*n2/2因算法的時間復(fù)雜度T(n)=f(n)=n+4*n2≤c*n2=O(n2)，其中c為常數(shù)，所以該算法的時間復(fù)雜度為O(n2)。解這個算法的時間復(fù)雜度隨待排序數(shù)例2―4下邊算法是在一個有n個數(shù)據(jù)元素的數(shù)組a中刪除第i個位置的數(shù)組元素，要求當(dāng)刪除成功時數(shù)組元素個數(shù)減1，求該算法的時間復(fù)雜度。其中，數(shù)組下標從0至n-1。IntDelete(inta［］,int*n,inti){intj;if(i<0||i>*n)return0;/*刪除位置錯誤，失敗返回*/

for(j=i+1;j<*n;j++)a［j-1］=a［j］;/*順次移位填補*/例2―4下邊算法是在一個有n個數(shù)(*n)--;/*數(shù)組元素個數(shù)減1*/return1;/*刪除成功返回*/}解這個算法的時間復(fù)雜度隨刪除數(shù)據(jù)的位置不同而不同。當(dāng)刪除最后一個位置的數(shù)組元素時有i=n-1,j=i+1=n，此時因不需移位填補而循環(huán)次數(shù)為0；當(dāng)刪除倒數(shù)最后一個位置的數(shù)組元素時有i=n-2,j=i+1=n-1，此時因只需移位填補一次而循環(huán)次數(shù)為1;依此類推,當(dāng)刪除第一個位置的數(shù)組元素時有i=0,j=i+1=1，此時因需移位填補n-1次而循環(huán)次數(shù)為n-1。此時算法的時間復(fù)雜度應(yīng)是刪除數(shù)據(jù)的位置等概率取值情況下的平均時間復(fù)雜度。(*n)--;假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概率的（一般情況下均可作等概率假設(shè)），設(shè)Pi為刪除第i個位置上數(shù)據(jù)元素的概率，則有Pi=1/n，設(shè)E為刪除數(shù)組元素的平均次數(shù)，則有假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概因該算法的時間復(fù)雜度T(n)=E≤(n+1)／2≤c*n=O(n)，其中c為常數(shù)，所以該算法的時間復(fù)雜度為O(n)。算法的時間復(fù)雜度是衡量一個算法好壞的重要指標。一般來說，具有多項式時間復(fù)雜度的算法是可接受、可實際使用的算法；具有指數(shù)時間復(fù)雜度的算法是只有當(dāng)n足夠小時才可使用的算法。表2―1給出了多項式增長和指數(shù)增長的比較。從表2―1可以看出，當(dāng)n=50時，多項式函數(shù)n3=125000，而指數(shù)函數(shù)2n=1.0×1015，n!=3.0×1064，nn=8.9×1084。因該算法的時間復(fù)雜度T(n)=E表2-1多項式增長和指數(shù)增長的比較表2-1多項式增長和指數(shù)增長的比較2.4.4算法的符號命名、書寫格式和注釋格式本書算法的符號命名和書寫格式采用規(guī)范的軟件工程方法。學(xué)生在算法設(shè)計和上機實習(xí)過程中應(yīng)學(xué)習(xí)這種書寫規(guī)則。算法中的各種符號命名方法規(guī)定為：（1）變量名和數(shù)據(jù)成員名字母均小寫；若單詞多于一個時，第二個單詞首字母大寫。有些教科書中變量名和數(shù)據(jù)成員名首字母均大寫。但頻繁地轉(zhuǎn)換字母的大小寫對于鍵盤輸入十分不便，所以一個單詞時首字母不大寫。當(dāng)變量名的單詞多于一個時，如果第二個單詞首字母不大寫，則變量名的含義很難理解。例如，后面章節(jié)中的變量名list,myList，數(shù)據(jù)成員名data，next,leftChild,rightChild的書寫是規(guī)范的。2.4.4算法的符號命名、書寫格式和注