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

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

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

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

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

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

數(shù)據(jù)元素（DataElement）是計(jì)算機(jī)中描述數(shù)據(jù)的基本單位。在大多數(shù)情況下，一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。如對(duì)學(xué)生登記問題中，每個(gè)數(shù)據(jù)元素就可包括學(xué)號(hào)、姓名、班級(jí)等，學(xué)號(hào)、姓名、班級(jí)等就稱作該數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。學(xué)生登記問題的數(shù)據(jù)結(jié)構(gòu)是最簡(jiǎn)單的線性表結(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

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

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

類型是一組值的集合。

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

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

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

面向?qū)ο蟪绦蛟O(shè)計(jì)（OrientedObjectProgramming）是以類設(shè)計(jì)為核心的一種新的程序設(shè)計(jì)方法，它是基于抽象數(shù)據(jù)類型程序設(shè)計(jì)方法的進(jìn)一步發(fā)展。2.2面向?qū)ο蟪绦蛟O(shè)計(jì)和類面類（Class）是面向?qū)ο蟪绦蛟O(shè)計(jì)中相同對(duì)象的抽象描述。類包括數(shù)據(jù)成員和方法兩部分。數(shù)據(jù)成員是類封裝起來、只允許類方法操作的數(shù)據(jù)元素。方法是類所提供的操作，把類提供的操作稱作方法，是因?yàn)轭愔袛?shù)據(jù)成員的存取只能由類提供的“方法”進(jìn)行。類（Class）是面向?qū)ο蟪绦蛟O(shè)計(jì)中類的構(gòu)成：1直接定義按照類的定義構(gòu)成。2派生派生類是指該類是由一個(gè)或一個(gè)以上（通常是一個(gè)）的已有類派生構(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)造方法使類具有了繼承機(jī)制。派生類對(duì)象既獨(dú)自具有該類特有的數(shù)據(jù)成員和方法，又同時(shí)具有基類中共同的數(shù)據(jù)成員和方法。classparent{派生類的類構(gòu)造方法使類具有了繼承機(jī)3合成合成類是指該類是由一個(gè)或一個(gè)以上的已有類合成構(gòu)造而成。例如，下例中的線是由兩個(gè)點(diǎn)構(gòu)成的，因此線類可由點(diǎn)類合成。classPoint{private:floatx,y;//點(diǎn)的坐標(biāo)public:Point(floath,floatv);//構(gòu)造函數(shù)floatGetX(void)const;//取x坐標(biāo)3合成FloatGetY(void)const;//取y坐標(biāo)voidDraw(void)const;//在{x,y}處劃點(diǎn)}；ClassLine{private:Pointp1,p2;//線的兩個(gè)點(diǎn)位置public:Line(Pointa,Pointb);//構(gòu)造函數(shù)voidDraw(void)const;//劃線連接點(diǎn)p1和p2}；FloatGetY(void)const;2.3對(duì)象對(duì)象（Object）是類的實(shí)例化。2.3對(duì)象對(duì)象（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è)計(jì)目標(biāo)和算法性能分析2.4.1算法

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

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

（1）x=x+1；時(shí)間復(fù)雜度為O(1)，稱為常量階；（3）for(i=1;i<=n;i++) for(j=1;j<=n;j++)x=x+1;時(shí)間復(fù)雜度為O(n2),稱為平方階。（2）for(i=1;i<=n;i++)x=x+1;時(shí)間復(fù)雜度為O(n)，稱為線性階；定義：T(n)=O(f(n))當(dāng)且僅例2―1設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個(gè)n階矩陣相乘運(yùn)算程序段的時(shí)間復(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因程序段的時(shí)間復(fù)雜度T(n)=f(n)=n2+n3≤c*n3=O(n3)，其中c為常數(shù)，所以該程序段的時(shí)間復(fù)雜度為O(n3)。解例2―2設(shè)n為如下程序段處理的數(shù)據(jù)個(gè)數(shù)，求如下程序段的時(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因程序段的時(shí)間復(fù)雜度T(n)=f(n)≤lbn+1≤c*lbn=O(lbn)，其中c為常數(shù)，所以該程序段的時(shí)間復(fù)雜度為O(lbn)。例2―2設(shè)n為如下程序段處理的數(shù)據(jù)例2―3下邊的算法是用冒泡排序法對(duì)數(shù)組a中的n個(gè)整數(shù)類型的數(shù)據(jù)元素（a［0］--a［n-1］）從小到大排序的算法，求該算法的時(shí)間復(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下邊的算法是用冒泡排序法對(duì)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］)解這個(gè)算法的時(shí)間復(fù)雜度隨待排序數(shù)據(jù)的不同而不同。當(dāng)某次排序過程中沒有任何兩個(gè)數(shù)組元素交換位置，則表明數(shù)組元素已排序完畢，此時(shí)算法將因標(biāo)記flag=0不滿足循環(huán)條件而結(jié)束。但是，在最壞情況下，每次排序過程中都至少有兩個(gè)數(shù)組元素交換位置，因此，應(yīng)按最壞情況計(jì)算該算法的時(shí)間復(fù)雜度。設(shè)基本語句的執(zhí)行次數(shù)為f(n)，最壞情況下有f(n)=n+4*n2/2因算法的時(shí)間復(fù)雜度T(n)=f(n)=n+4*n2≤c*n2=O(n2)，其中c為常數(shù)，所以該算法的時(shí)間復(fù)雜度為O(n2)。解這個(gè)算法的時(shí)間復(fù)雜度隨待排序數(shù)例2―4下邊算法是在一個(gè)有n個(gè)數(shù)據(jù)元素的數(shù)組a中刪除第i個(gè)位置的數(shù)組元素，要求當(dāng)刪除成功時(shí)數(shù)組元素個(gè)數(shù)減1，求該算法的時(shí)間復(fù)雜度。其中，數(shù)組下標(biāo)從0至n-1。IntDelete(inta［］,int*n,inti){intj;if(i<0||i>*n)return0;/*刪除位置錯(cuò)誤，失敗返回*/

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