DataStructure

資料結(jié)構(gòu)與算法目錄認(rèn)識(shí)資料與信息算法(Algorithm)程序(program)與程序設(shè)計(jì)(programming)算法的效能分析1.認(rèn)識(shí)資料與信息

資料(Data)，指的就是一種未經(jīng)處理的原始文字(Word)、數(shù)字(Number)、符號(hào)(Symbol)或圖形(Graph)等，它所表達(dá)出來的只是一種沒有評(píng)估價(jià)值的基本原素或項(xiàng)目。例如姓名或我們?？吹降恼n表、通訊錄等等都可泛稱是一種「資料」。

資料處理

「資料處理」就是用人力或機(jī)器設(shè)備，對(duì)資料進(jìn)行有系統(tǒng)的整理如記錄、排序、合并、整合、計(jì)算、統(tǒng)計(jì)等，以使原始的「資料」符合需求，而成為有用的「信息」(Information)

資料結(jié)構(gòu)資料結(jié)構(gòu)是在資料處理過程中，一種分析、組織資料的方法(algorithm)與邏輯(logic)。它考慮到了資料間的特性與相互關(guān)系(relationship)。程序設(shè)計(jì)師必須選擇一種資料結(jié)構(gòu)來進(jìn)行資料的新增、修改、刪除、儲(chǔ)存等動(dòng)作，如果在選擇資料結(jié)構(gòu)時(shí)作了錯(cuò)誤的決定，那程序執(zhí)行起來的速度將可能變得非常沒有效率。資料和信息的角色是否一成不變不一定。同一份文件可能在某種況下為資料，而在另一種狀況下則為信息。例如美伊戰(zhàn)爭(zhēng)的戰(zhàn)役死傷人數(shù)報(bào)告，對(duì)你我這些平民百姓而言，當(dāng)然只是一份不痛不癢的「資料」(Data)；不過對(duì)于英美聯(lián)軍指揮官而言，這份報(bào)份可就是彌足珍貴的「信息」(Information)。2.算法(Algorithm)

資料結(jié)構(gòu)加上算法等于可執(zhí)行程序?！杆惴ā乖陧f氏辭典定義為：「在有限步驟內(nèi)解決數(shù)學(xué)問題的程序?！乖谟?jì)算機(jī)領(lǐng)域可以把算法定義成：「為了解決某一個(gè)工作或問題，所需要有限數(shù)目的機(jī)械性或重覆性指令與計(jì)算步驟。」

算法五個(gè)條件輸入(Input)：0個(gè)或多個(gè)輸入資料，這些輸入必需有清楚的描述或定義。輸出(Output)：至少會(huì)有一個(gè)輸出結(jié)果，不可以沒有輸出結(jié)果。明確性(Definiteness)：每一個(gè)指令或步驟必需是簡(jiǎn)潔明確而不含糊的。有限性(Finiteness)：在有限的步驟后一定會(huì)結(jié)束，不會(huì)產(chǎn)生無窮回路。有效性(Effectiveness)：步驟清楚且可行，能讓使用者用紙筆計(jì)算而求出答案。算法常用的表現(xiàn)方法一般文字：中文、英文、數(shù)字等。虛擬語(yǔ)言：接近高階程序語(yǔ)言的寫法，經(jīng)常使用的有SPARKS、PASCA-LIKE等語(yǔ)言。表格或圖形：如陣列、樹形圖、矩陣圖等。流程圖：資料流程圖)及控制流程圖可以算是一種通用的表示法，也有固定的圖型符號(hào)。程序語(yǔ)言：目前資料結(jié)構(gòu)的算法經(jīng)常是以可讀性高的高階語(yǔ)言來表示，例如C語(yǔ)言、C++語(yǔ)言、Java語(yǔ)言、VisualBasic語(yǔ)言等，在本書中將以C語(yǔ)言來表達(dá)算法算法、程序、與流程圖的異同算法和程序是有所區(qū)別，因?yàn)槌绦虿灰欢ㄒ獫M足有限性的要求，如作業(yè)系統(tǒng)或機(jī)器上的運(yùn)作程序；除非當(dāng)機(jī)，否則永遠(yuǎn)在等待回路(waitingloop)或記錄機(jī)器運(yùn)作狀況，這也違反了算法五大原則之一的「有限性」。只要是算法都能夠利用程序流程圖表現(xiàn)，但因?yàn)槌绦蛄鞒虉D可包含無窮回路，所以無法利用算法來表達(dá)。3.程序(program)與程序設(shè)計(jì)(programming)程序產(chǎn)生的五個(gè)階段:需求認(rèn)識(shí)：了解程序所要解決的問題是什么，有那些輸入及輸出等。設(shè)計(jì)規(guī)劃：根據(jù)需求，選擇適合的資料結(jié)構(gòu)，并以任何的表示方式來寫一個(gè)算法以解決問題。分析討論：思考其他可能的算法及資料結(jié)構(gòu)，最后再做出最適當(dāng)?shù)倪x擇。編寫程序：把分析的結(jié)論，寫成初步的程序碼。測(cè)試檢驗(yàn)：最后必需確認(rèn)程序的輸出是否符合需求，這個(gè)步驟得細(xì)步的執(zhí)行程序并進(jìn)行許多的相關(guān)測(cè)試。它又分為三種基本結(jié)構(gòu)(BasicStructure)：基本結(jié)構(gòu)名稱概念圖[循序結(jié)構(gòu)]逐步的撰寫敘述[選擇結(jié)構(gòu)]依某些條件做邏輯斷[重復(fù)結(jié)構(gòu)]依某些條件決定是否重復(fù)執(zhí)行某些敘述。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：「由上而下法」讓程序可讀性更高，對(duì)于日后修改維護(hù)幫助很大。再加上「模塊化」的設(shè)計(jì)能讓設(shè)計(jì)者分工合作，降低開發(fā)成本。缺點(diǎn)：由于維持可讀性高的要求，必須有較多的指令，容易占用存儲(chǔ)器空間，與非結(jié)構(gòu)程序設(shè)計(jì)相比，執(zhí)行速度也會(huì)較慢?；举Y料型態(tài)(atomicdatatype)或稱為實(shí)質(zhì)資料型態(tài)(physicaldatatype)結(jié)構(gòu)型資料型態(tài)(structuredatatype)或稱為虛擬資料型態(tài)(virtualdatatype)抽象資料型態(tài)(AbstractDataType：ADT)資料儲(chǔ)存層次的分類基本資料型態(tài)一個(gè)基本的資料實(shí)體，例如一般程序語(yǔ)言中的整數(shù)、實(shí)數(shù)、字符等等。基本上，每種語(yǔ)言都擁有略微不同的基本資料型態(tài)。像C語(yǔ)言的基本資料型態(tài)為整數(shù)(int)、字符(char)、單精度浮點(diǎn)數(shù)(float)與倍精度浮點(diǎn)數(shù)(double)。結(jié)構(gòu)型資料型態(tài)比實(shí)質(zhì)資料型態(tài)更高一層，是指一個(gè)資料實(shí)體包含其他的資料型態(tài)，例如字符串(string)、集合(set)、陣列(array)。抽象資料型態(tài)比結(jié)構(gòu)型資料型態(tài)更高一層，ADT是指定義一些結(jié)構(gòu)型資料型態(tài)所具備的數(shù)學(xué)運(yùn)算關(guān)系。也就是說，使用者毋需考慮到ADT的制作細(xì)節(jié)，只要知道如何使用即可。例如堆棧(stack)或隊(duì)列(queue)就是一種很典型的ADT模式。4.算法的效能分析Givenaproblem,theremaybeseveralpossibleimplementations.Efficiencyisthemostimportantconsiderationincludingtimeandspace.ComplexityTheory–toestimatethetimeandspaceneededforaprogram.It’smachineindependent.SpaceComplexityofaprogram–theamountofmemoryspaceneededtocompleteaprogram.TimeComplexityofaprogram–theamountofcomputation(computer)timeneededtocompleteaprogram.SpaceComplexityS(p)

S(p)=Sc+Sp(I)Sc(Fixspacerequirement)includinginstructionspace,constants,simplevariables,andfix-sizestructures.TheScisindependentofthenumberandsizeofinputsandoutputs.e.g.inti,sum=0,A[100];

Sp(I)(Variablespacerequirement)dependsonaparticularinstanceIofaproblem.InstanceImaybeafunctionofnumber,size,orvaluesofinputsandoutputs.e.g.int*n;//scorelistofacourseTimeComplexityT(p)

T(p)=Tc+Tp(I)Tc(Fixtimerequirement)compiletime,Tcisindependentofanyinstanceoftheproblem.Tp(I)(Variabletimerequirement)executiontime,dependsonaparticularinstanceIofaproblem.e.g.matrixmultiplicationC[][]=A[][]*B[][]

(0,0)0,10,20,30,n 0,0 1,02,0 n,0 (n*)+(n+)=>2n2n*n*n+an2+bn+c=>2n3

+an2+bn+cAsymptoticNotations

-formeasuringspaceandtimecomplexitiesO(Big-oh)Ω(omega)θ(theta)Big-oh的介紹O(g(n))可視為某算法在計(jì)算機(jī)中所需執(zhí)行時(shí)間不會(huì)超過某一常數(shù)倍的g(n)，也就是說當(dāng)某算法的空間或時(shí)間復(fù)雜度(spaceortimecomplexity)為O(g(n))(讀成big-ohofg(n)或orderisg(n))。Definition:Thefunctionf(n)issaidtobeoforderatmostg(n)iftherearepositiveconstantscandn0suchthatf(n)<=cg(n)foralln,n>=n0.Therefore,“Bigoh”isthesmallestupperboundoff(n).常見的Big-oh有下列幾種：O(1)：稱為常數(shù)(constant)O(log2n)：稱為(logarithmic)O(log22n)：稱為(logsquared)O(n)：稱為線性(linear)O(nlog2n)：稱為nlognO(n2)：稱為平方(quadratic)O(n3)：稱為立方(cubic)O(2n)：稱為指數(shù)(exponential)Ω(omega)的介紹Ω也是一種復(fù)雜度的漸近表示法，如果說Big-oh是執(zhí)行時(shí)間量度的最壞情況，那Ω就是執(zhí)行時(shí)間量度的最好狀況。以下是Ω的定義：Definition:Thefunctionf(n)issaidtobeoforderatleastg(n)iftherearepositiveconstantscandn0suchthatf(n)>=cg(n)foralln,n>=n0.Therefore,“Bigoh”isthelargestlowerboundoff(n).θ(theta)的介紹是一種比Big-O與Ω更精確復(fù)雜度的漸近表示法。定義如下：Definition:Thefunctionf(n)isθ(g(n))iffthereexistspositiveconstantsc1,c2andn0,suchthatc1g(n)<=f(n)<=c2g(n)foralln,n>=n0.Therefore,“θ”isboththesmallestupperboundandthegreatestlowerboundoff(n).Examplesforasymptoticnotations1.3n+2=Ο(n),∵3n+2≦4n,foralln≧2,c=4.2.3n+3=Ο(n),∵3n+3≦4n,foralln≧3,c=4.3.3n+3=Ο(n2),∵3n+2≦3n2,foralln≧2,c=3.(2)iscorrect.(3)iswrong.“Bigoh“shouldbeasmallerfunctionofn.4.10n2+4n+2=Ο(n2),∵10n2+4n+2≦11n2,foralln≧5,c=11.5.6．2n+n2=Ο(2n),∵6．2n+nn≦7．2n,foralln≧4,c=7.6.3n+3=Ω(n),∵3n+3≧3n,foralln≧1,c=3.7.3n+3=Ω(1),∵3n+3≧3,foralln≧1,c=3.(6)iscorrect.(7)iswrong.“Omega”shouldbealargerfunctionofn.8.3n+2=Θ(n)∵3n≦3n+2≦4n,foralln≧2,c1=3,c2=4,andn0=2.ExampleforS(p):addupvaluesofnelementsinanarraycalledlist. main() floataddup(floatlist[],intn) { { floatlist[n],temp=0.0; floattemp=0.0; inti; inti; for(i=0;i<n;i++) for(i=0;i<n;i++) temp+=list[i]; temp+=list[i]; returntemp; returntemp; } } Smain(n)=c+n=O(n) Saddup(n)=c=O(1) Otherlanguagesmayneedtopassthewholearray,butadduppassesonlyaddressesofthe1‘stelementandthesizeofarray.ExampleforT(p):usestepcountinsteadofexecutiontime.1.on-linestepcount floatsum(floatlist[],intn)/*calculatethesumofanarray*/ { floattmp=0.0;count++; /*tmpassignment*/ inti; for(i=0;i<n;i++){

count++; /*forloop*/ tmp+=list[i];count++; *addingup*/ } count++;/*lasttimetocheckforloopandfails*/ returntmp;count++; /*forreturn*/ } =>stepcount=2*n+3=>Tsum(n)=O(n)2.Tabularmethod voidadd(inta[][],intb[][],intc[][],introw,intcol) { Stepperexec. freq. total inti,j; 0 0 0 for(i=0;i<row;I++) 1 row+1row+1 for(j=0;j<col;j++) 1 row*(col+1)row*col+row c[i][j]=a[i][j]+b[i][j]; 1 row*col row*col }Intotal,wehavestepcount=2row*col+2row+1. =>Tadd(row,col)=O(row*col)Thus,ifrow>>col,onemaywanttoexchangeiandjtoreducethestepcountandexecutiontime.3.ExecutiontimeMeasurement#include<time.h> 1.Clock 2.TimeBeforeexecution,use start=clock(); start=time(NULL);Afterexecution,use stop=clock(); stop=time(NULL);Typereturn clock_t time_tresultinsec.(stop-start)/CLK_TCK;

difftime(stop,start);Whenmeasuringtheexecutionofaprogram,wehaveCLK_TCK=18.2,beginclk