軟件體系結(jié)構(gòu)

———

編程回顧林榮恒北京郵電大學(xué)北京郵電大學(xué)主要內(nèi)容編程概述程序風(fēng)格算法與數(shù)據(jù)結(jié)構(gòu)小結(jié)設(shè)計(jì)、調(diào)試和測(cè)試這里不再介紹北京郵電大學(xué)編程概述程序編程Programming編程語言北京郵電大學(xué)程序計(jì)算機(jī)的工作是由程序來控制的程序：程序是為解決某一問題而編寫的語句序列。通俗的說，將解決一個(gè)實(shí)際問題的具體操作步驟用某種計(jì)算機(jī)語言描述出來，就形成了程序。語句序列：指令計(jì)算機(jī)可以識(shí)別的命令實(shí)際問題的具體操作步驟：算法求解問題的方法，是在有限的步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則，是計(jì)算機(jī)處理問題所需要的過程北京郵電大學(xué)高質(zhì)量的程序所具備的條件建立正確的數(shù)學(xué)模型和確定有效的計(jì)算方法運(yùn)行結(jié)果必須正確，且在精度和其它各方面均滿足要求程序本身具有良好的結(jié)構(gòu)，邏輯清晰，易讀易懂程序運(yùn)行時(shí)間盡可能短，同時(shí)盡可能合理地使用內(nèi)存便于檢查、修正、移植和維護(hù)北京郵電大學(xué)編程編程(Programming)：就是編寫程序，它是在對(duì)算法進(jìn)行正確描述的基礎(chǔ)上進(jìn)行的，是用計(jì)算機(jī)語言（程序設(shè)計(jì)語言）實(shí)現(xiàn)算法的過程。算法轉(zhuǎn)變程序的過程北京郵電大學(xué)編程的一般過程對(duì)于簡(jiǎn)單問題，前三步可看作一步，即分析問題、設(shè)計(jì)算法。維護(hù)？？？北京郵電大學(xué)程序語言機(jī)器語言由計(jì)算機(jī)硬件系統(tǒng)可以識(shí)別的二進(jìn)制指令組成匯編語言將機(jī)器指令映射為一些可以被人讀懂的助記符，如ADD、SUB等高級(jí)語言屏蔽了機(jī)器的細(xì)節(jié)，提高了語言的抽象層次程序中可以采用具有一定含義的數(shù)據(jù)命名和容易理解的執(zhí)行語句在書寫程序時(shí)可以聯(lián)系到程序所描述的具體事物面向過程面向?qū)ο蟊本┼]電大學(xué)選擇計(jì)算機(jī)語言的原則根據(jù)自己所處理事務(wù)的特點(diǎn)來選擇計(jì)算機(jī)語言符合現(xiàn)代程序設(shè)計(jì)的要求適合使用者的硬件和軟件環(huán)境考慮軟件執(zhí)行效率考慮使用者的工作性質(zhì)北京郵電大學(xué)高級(jí)程序語言學(xué)習(xí)要點(diǎn)數(shù)據(jù)結(jié)構(gòu)基本、復(fù)合變量類型聲明方法操作符語句賦值、計(jì)算結(jié)構(gòu)控制語句：條件、分支、循環(huán)過程調(diào)用語句功能塊/操作函數(shù)、過程類中的方法或成員變量北京郵電大學(xué)高級(jí)程序語言學(xué)習(xí)要點(diǎn)(2)模塊.c文件類類庫或者庫函數(shù)：該語言或者第三方提供的，不用自己編寫的系統(tǒng)調(diào)用輸入輸出：文件、鍵盤、網(wǎng)絡(luò)隨機(jī)數(shù)、String線程……作用域Public、static、private、protected、friendly、extern異常處理北京郵電大學(xué)高級(jí)程序語言學(xué)習(xí)要點(diǎn)(3)可執(zhí)行程序的構(gòu)成和組織主程序、Main函數(shù)、Main類模塊文件、類文件目錄結(jié)構(gòu)程序編輯、編譯、鏈接和執(zhí)行方法依賴于環(huán)境該語言有特色的地方可視化程序設(shè)計(jì)實(shí)質(zhì)是去使用開發(fā)環(huán)境提供的可視化庫函數(shù)或者類庫北京郵電大學(xué)主要內(nèi)容編程概述程序風(fēng)格算法與數(shù)據(jù)結(jié)構(gòu)小結(jié)北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)看看這個(gè)代碼typedefstruct{doublex,y,z}vec;vecU,black,amb={.02,.02,.02};structsphere{veccen,color;doublerad,kd,ks,kt,kl,ir}*s,*best,sph[]={0.,6.,.5,1.,1.,1.,.9,.05,.2,.85,0.,1.7,-1.,8.,-.5,1.,.5,.2,1.,.7,.3,0.,.05,1.2,1.,8.,-.5,.1,.8,.8,1.,.3,.7,0.,0.,1.2,3.,-6.,15.,1.,.8,1.,7.,0.,0.,0.,.6,1.5,-3.,-3.,12.,.8,1.,1.,5.,0.,0.,0.,.5,1.5,};yx;doubleu,b,tmin,sqrt(),tan();doublevdot(A,B)vecA,B;{returnA.x*B.x+A.y*B.y+A.z*B.z;}vecvcomb(a,A,B)doublea;vecA,B;{B.x+=a*A.x;B.y+=a*A.y;B.z+=a*A.z;returnB;}vecvunit(A)vecA;{returnvcomb(1./sqrt(vdot(A,A)),A,black);}structsphere*intersect(P,D)vecP,D;{best=0;tmin=1e30;s=sph+5;while(s--sph)b=vdot(D,U=vcomb(-1.,P,s-cen)),u=b*b-vdot(U,U)+s-rad*s-rad,u=u0?sqrt(u):1e31,u=b-u1e-7?b-u:b+u,tmin=u=1e-7&&u<tmin?best=s,u:tmin;returnbest;}vectrace(level,P,D)vecP,D;{doubled,eta,e;vecN,color;structsphere*s,*l;if(!level--)returnblack;if(s=intersect(P,D));elsereturnamb;color=amb;eta=s-ir;d=-vdot(D,N=vunit(vcomb(-1.,P=vcomb(tmin,D,P),s-cen)));if(d<0)N=vcomb(-1.,N,black),eta=1/eta,d=-d;l=sph+5;while(l--sph)if((e=l-kl*vdot(N,U=vunit(vcomb(-1.,P,l-cen))))0&&intersect(P,U)==l)color=vcomb(e,l-color,color);U=s-color;color.x*=U.x;color.y*=U.y;color.z*=U.z;e=1-eta*eta*(1-d*d);returnvcomb(s-kt,e0?trace(level,P,vcomb(eta,D,vcomb(eta*d-sqrt(e),N,black))):black,vcomb(s-ks,trace(level,P,vcomb(2*d,N,D)),vcomb(s-kd,color,vcomb(s-kl,U,black))));}main(){printf("%d%d\n",32,32);while(yx<32*32)U.x=yx%32-32/2,U.z=32/2-yx++/32,U.y=32/2/tan(25/114.5915590261),U=vcomb(255.,trace(3,black,vunit(U)),black),printf("%.0f%.0f%.0f\n",U);}你寫的比它好多少？北京郵電大學(xué)想寫出高質(zhì)量的代碼嗎？高質(zhì)量代碼的四個(gè)基本特性：正確性簡(jiǎn)單性可讀性可測(cè)試性可讀性（清晰性）是“易于維護(hù)、易于重構(gòu)的程序”最有價(jià)值的特性采用好的程序設(shè)計(jì)風(fēng)格進(jìn)行編碼是實(shí)現(xiàn)可讀性的必要保障北京郵電大學(xué)為什么要有可讀性？編程首先是與人交流，其次才是與計(jì)算機(jī)交流，采用好的風(fēng)格編寫出可讀性好的代碼，可以降低與人交流的復(fù)雜度：編程閱讀代碼的次數(shù)要比編寫代碼多得多，即使在開發(fā)的初期也是如此維護(hù)代碼的維護(hù)者會(huì)感激你使代碼容易理解將來的維護(hù)者很可能就是你自己，到時(shí)候你得嘗試記起自己六個(gè)月以前在想什么軟件的首要技術(shù)使命是管理復(fù)雜度，許多編程實(shí)踐背后的動(dòng)機(jī)正是為了降低程序的復(fù)雜度北京郵電大學(xué)怎樣提高可讀性？名字，最常見的有類名、子程序名、變量名；長(zhǎng)度，比如類的長(zhǎng)度、數(shù)據(jù)成員的數(shù)目、子程序的長(zhǎng)度、子程序的參數(shù)數(shù)目、語句的嵌套層數(shù)；復(fù)雜度，包括表達(dá)式的復(fù)雜度、語句邏輯的復(fù)雜度等；格式，包括縮進(jìn)、空格、注釋等；耦合度，包括由于共享數(shù)據(jù)（含全局?jǐn)?shù)據(jù)）導(dǎo)致的耦合、類之間耦合（繼承、組合、友元）、子程序之間的耦合等；北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)名字：名不正，則言不順！！！類名、子程序名、變量名等，用于標(biāo)識(shí)相應(yīng)的對(duì)象可以使用切合實(shí)際的命名約定，但一旦使用了，就一定要始終如一地堅(jiān)持你的命名約定frontsize,frontSize,front_size北京郵電大學(xué)一些基本的命名規(guī)則全局變量使用具有說明性的名字，作用范圍越大，所攜帶的信息應(yīng)該越多好名字：currentDate、todaysDate壞名字：X,y,d,cd,td,x,y,date局部變量可以使用短名字例如，如果循環(huán)只有寥寥數(shù)行，而且只是單層循環(huán)，那么可以用i、j等如果循環(huán)行數(shù)較多，或者有嵌套，則需要更長(zhǎng)而且有意義的名字試比較：score[teamIndex][eventIndex]

和score[i][j]下標(biāo)串化問題北京郵電大學(xué)一些基本的命名建議（續(xù)1）研究發(fā)現(xiàn)，當(dāng)變量名的平均長(zhǎng)度在10到16個(gè)字符的時(shí)候，調(diào)試程序所需花費(fèi)的氣力是最小的。平均名字長(zhǎng)度在8到20個(gè)字符的程序也幾乎同樣容易調(diào)試。太短的名字無法傳達(dá)足夠的信息太長(zhǎng)的名字很難寫，同時(shí)也會(huì)使得程序的視覺結(jié)構(gòu)變得模糊不清北京郵電大學(xué)一些基本的命名建議（續(xù)2）保持一致性壞的命名：好的命名：ClassUserQueue{intnoOfItemsInQ,frontOfQueue,queueCapacity;publicintnoOfUsersInQueue(){…}ClassUserQueue{intnUsers,front,capacity;publicintgetNoOfUsers(){…}}北京郵電大學(xué)一些基本的命名建議（續(xù)3）函數(shù)采用動(dòng)作性的名字：用動(dòng)作性的動(dòng)詞，后面跟著名詞如：比較：If(checkoctal(c))

和if(isoctal(c))要準(zhǔn)確：名字不僅是個(gè)標(biāo)記，它還攜帶著給讀程序人的信息now=date.getTime();putchar(‘\n’);北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)表達(dá)式和語句用縮行顯示程序的結(jié)構(gòu)Bad:Good:For(n=0;n<100;field[n++]=‘\0’;*i=‘\0’;return(‘\n’);For(n=0;n<100;n++)Field[n]=’\0’;*i=‘\0’;return(‘\n’);北京郵電大學(xué)表達(dá)式和語句（續(xù)1）使用表達(dá)式的自然形式BadGoodIf(!(block_id<actblks)||!(block_id>=unblocks))If((block_id>=actblks)||(block_id<unblocks))北京郵電大學(xué)表達(dá)式和語句（續(xù)2）用加括號(hào)的方式排除二義性在混合使用相互無關(guān)的運(yùn)算符時(shí)，多加幾個(gè)括號(hào)沒有壞處尤其是C語言即使不必要，加了括號(hào)也能把意圖表現(xiàn)得更明白小竅門：使用括號(hào)使得你不用去記那些操作符的優(yōu)先級(jí)北京郵電大學(xué)表達(dá)式和語句（續(xù)3）分解復(fù)雜的表達(dá)式Bad：Good*x+=(*xp=(2*k<(n-m)?c[k+1]:d[k--]));If(2*k<(n-m)*xp=c[K+1];Else*xp=d[k--];*x+=*xp;北京郵電大學(xué)表達(dá)式和語句（續(xù)4）當(dāng)心副作用Badcode：Goodcode：str[i++]=str[i++]=‘

‘;Str[i++]=‘

‘;Str[i++]=‘

‘;北京郵電大學(xué)表達(dá)式和語句（續(xù)5）使用空行將代碼分為有機(jī)的各個(gè)部分#include<termios.h>#include<unistd.h>intmain(intargc,char**argv){/*Settheinputtono-echo,character-at-time*("cbreak")mode,*andremembertheoldmodeint0*/structtermiost0,t1;tcgetattr(0,&t0);t1=t0;t1.c_lflag&=!(ECHO|ICANON);tcsetattr(0,0,&t1);run();/*Settheterminalbacktoitsoriginalmode*/tcsetattr(0,0,&t0);return0;}北京郵電大學(xué)表達(dá)式和語句（續(xù)6）子程序、函數(shù)、方法的代碼行數(shù)最好不要超過200行可讀性不好新手可以先編長(zhǎng)的，再進(jìn)行分離。每一行只寫一條語句北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)一致性和習(xí)慣用法一致性帶來更好的程序命名的一致性語句的一致性相同實(shí)現(xiàn)方法的一致性：如果相同的計(jì)算每次總是采用相同的方式，任何變化就預(yù)示著是經(jīng)過了深思熟慮，要求讀程序的人注意其他的一致性：算法數(shù)據(jù)結(jié)構(gòu)出錯(cuò)處理方式高層設(shè)計(jì)模式……北京郵電大學(xué)一致性和習(xí)慣用法（續(xù)1）使用一致的縮排和加括號(hào)的方法if(month==FEB){if(year&4==0)

if(day>29)legal=FALSE;

elseif(day>28)legal=FALSE;}if(month==FEB){

if(year&4==0){if(day>29)legal=FALSE;}

else{if(day>28)legal=FALSE;}}Wrongcode(elsematches“ifday>29”)Rightcode北京郵電大學(xué)一致性和習(xí)慣用法（續(xù)2）為了一致性，使用習(xí)慣用法just“so-so”codeGoodcodei=0;while(i<=n-1)array[i++]=1.0;for(i=0;i<n;i++)array[i]=1.0;北京郵電大學(xué)一致性和習(xí)慣用法（續(xù)3）用else-if表達(dá)多路選擇just“so-so”code:Goodcode:if(x<v[mid])high=mid–1;elseif(x>v[mid])low=mid+1;elsereturnmid;if(x<v[mid])high=mid–1;elseif(x>v[mid])low=mid+1;elsereturnmid;245781017low=0high=6mid=310xv北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)函數(shù)宏避免函數(shù)宏函數(shù)宏的缺點(diǎn)遠(yuǎn)遠(yuǎn)超過它能帶來的好處給宏的體和參數(shù)都加上括號(hào)Badcode：Goodcode:#definesquare(x)x*x#definesquare(x)((x)*(x))北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)神秘的數(shù)神秘的數(shù)包括各種常數(shù)、數(shù)組的大小、字符位置、變換因子以及程序中出現(xiàn)的其他以文字形式寫出的數(shù)值。給神秘的數(shù)起一個(gè)好名字MINROW、MINCOL、MAXROW、MAXCOL北京郵電大學(xué)神秘的數(shù)（續(xù)1）把數(shù)定義為常數(shù)，不要定義為宏ConstintMAXROW=24;StaticfinalintMAXROW=24;使用字符形式的常數(shù)，不用整數(shù)Bad：if(c>=65&&c<=90)Soso:if(c>=‘A’&&c<=‘Z’)Good:if(issupper(c))Java：if(Character.isUpperCase(c))北京郵電大學(xué)神秘的數(shù)（續(xù)2）利用語言去計(jì)算對(duì)象的大小charbuf[1024];fgets(buf,sizeof(buf),stdin);charbuf[]=newchar[1024];For(inti=0;I<buf.length;i++)…北京郵電大學(xué)程序風(fēng)格引言名字表達(dá)式和語句一致性和習(xí)慣用法函數(shù)宏神秘的數(shù)注釋北京郵電大學(xué)注釋程序中的注釋是程序員與日后的程序讀者之間通信的重要手段。注釋絕不是可有可無的。一些正規(guī)的程序文本中，注釋行的數(shù)量占到整個(gè)源程序的1／3到1／2，甚至更多。注釋分為序言性注釋和功能性注釋。北京郵電大學(xué)序言性注釋通常置于每個(gè)程序模塊的開頭部分，它應(yīng)當(dāng)給出程序的整體說明，對(duì)于理解程序本身具有引導(dǎo)作用。有些軟件開發(fā)部門對(duì)序言性注釋做了明確而嚴(yán)格的規(guī)定，要求程序編制者逐項(xiàng)列出。有關(guān)項(xiàng)目包括：程序標(biāo)題；有關(guān)本模塊功能和目的的說明；

主要算法；

接口說明：包括調(diào)用形式，參數(shù)描述，子程序清單；有關(guān)數(shù)據(jù)描述：重要的變量及其用途，約束或限制條件，以及其它有關(guān)信息；

模塊位置：在哪一個(gè)源文件中，或隸屬于哪一個(gè)軟件包；

開發(fā)簡(jiǎn)歷：模塊設(shè)計(jì)者，復(fù)審者，復(fù)審日期，修改日期及有關(guān)說明等。北京郵電大學(xué)功能型注釋功能性注釋嵌在源程序體中，用以描述其后的語句或程序段是在做什么工作，或是執(zhí)行了下面的語句會(huì)怎么樣。而不要解釋下面怎么做BadGood/*AddAmounttoTotal*Total=amount+total/*AddMonthly-SalestoAnnual-Totol*Total=amount+total北京郵電大學(xué)基本建議給類、方法、函數(shù)、全局?jǐn)?shù)據(jù)加注釋描述一段程序，而不是每一個(gè)語句Purposeofcode,noteverydetailTricksusedReasonsforunusualcoding

用縮進(jìn)和空行，使程序與注釋容易區(qū)別注釋要正確，不要與代碼矛盾不要注釋差的代碼，重寫它北京郵電大學(xué)基本建議（續(xù)1）不要大談明顯的東西Zerocount++;/*Incrementzeroentrycounter*/While((c=getchar())!=EOF&&isspace(c));/*skipwhitespace北京郵電大學(xué)基本建議（續(xù)2）澄清情況，不要添亂Ifittakeslongertoreadthecommentthantoreadthecode,don’taddacomment!Bad：Good:/*stringcomparisonroutinereturns-1ifs1isaboves2*/Inanascendingorderlist,0ifequal,1ifs1belows2*//*strcmp:return<0ifs1<s2,>0ifs1>s2,0ifequal*/北京郵電大學(xué)小結(jié)程序必須是寫給人看的，僅僅偶爾才在機(jī)器上執(zhí)行。好習(xí)慣很重要，因?yàn)槌绦騿T做的大部分事情都是無意識(shí)完成的初涉編程時(shí)，就應(yīng)端正態(tài)度來學(xué)，盡快培養(yǎng)良好的習(xí)慣甚至你在工作壓力下寫出的代碼也會(huì)更好富于技巧(tricky)、聰明(clever)可算是代碼的惡劣品質(zhì)，編程不是為了炫耀自己的聰明程度，這樣寫程序簡(jiǎn)直是歪門邪道通過你自己的程序你想體現(xiàn)什么？北京郵電大學(xué)最后請(qǐng)把修改你代碼的人記在心上與人方便，與己方便北京郵電大學(xué)主要內(nèi)容編程概述程序風(fēng)格算法與數(shù)據(jù)結(jié)構(gòu)小結(jié)北京郵電大學(xué)算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概述算法概述實(shí)例小結(jié)北京郵電大學(xué)算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概述算法概述實(shí)例小結(jié)北京郵電大學(xué)基本概念數(shù)據(jù)：在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)是信息的載體數(shù)據(jù)是計(jì)算機(jī)程序加工的原料數(shù)據(jù)的含義極為廣泛，且不斷豐富數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。比如電話號(hào)碼表中的每一行信息便是一個(gè)數(shù)據(jù)元素（它包含三個(gè)數(shù)據(jù)項(xiàng)）。此概念是相對(duì)的北京郵電大學(xué)基本概念（2）數(shù)據(jù)結(jié)構(gòu)：組成數(shù)據(jù)的元素之間的結(jié)構(gòu)關(guān)系。線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖結(jié)構(gòu)是《數(shù)據(jù)結(jié)構(gòu)》中的幾類常見的數(shù)據(jù)結(jié)構(gòu)形式。如果數(shù)據(jù)中的元素之間沒有關(guān)系，則構(gòu)成集合，這也是一種結(jié)構(gòu)。北京郵電大學(xué)基本概念（3）數(shù)據(jù)結(jié)構(gòu)的內(nèi)容：邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系線性結(jié)構(gòu)：線性表、數(shù)組、棧、隊(duì)列、串等非線性結(jié)構(gòu)：樹、圖等物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：即對(duì)數(shù)據(jù)所施加的操作檢索、插入、刪除、更新、排序等北京郵電大學(xué)舉例：分析如下電話號(hào)碼表數(shù)據(jù)結(jié)構(gòu)編號(hào)姓名電話號(hào)碼1張三35501232李四35401233李七80987894張彬78967545丁丁12345676黃七98087547張發(fā)99878778丁一90909609黃三56448891、邏輯結(jié)構(gòu)2、存儲(chǔ)結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算分析：開始結(jié)點(diǎn)終端結(jié)點(diǎn)排在其前(后)面且與其相鄰的結(jié)點(diǎn)稱為該結(jié)點(diǎn)的直接前趨(后繼)結(jié)點(diǎn)有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼，這就是該數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)北京郵電大學(xué)算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概述算法概述實(shí)例小結(jié)北京郵電大學(xué)定義算法：是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。描述算法設(shè)給定兩個(gè)正整數(shù)m=112和n=64，利用輾轉(zhuǎn)相除法，求它們的最大公約數(shù)。（1）112除以64，余數(shù)為48；（2）64除以48，余數(shù)為16；（3）48除以16，余數(shù)為0；答:112和64的最大公約數(shù)為16。北京郵電大學(xué)算法的特征輸入：一個(gè)算法有零個(gè)或多個(gè)輸入；確定性：算法的每一個(gè)步驟必須要確切地定義；有窮性：一個(gè)算法在執(zhí)行有窮步之后必須結(jié)束；輸出：算法有一個(gè)或多個(gè)輸出；能行性：算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的（運(yùn)算和操作能精確地執(zhí)行）北京郵電大學(xué)算法的描述問題描述自然語言流程圖偽代碼設(shè)計(jì)一個(gè)算法，求出100以內(nèi)能被3整除的所有正整數(shù)。①令I(lǐng)=1；②如果I能被3整除，則輸出I；③I=I+1；④如果I≤100，則返回第②步；⑤結(jié)束。I=1DOIFIMOD3=0THENPRINTII=I+1LOOPWHILEI≤100開始I=1I能被3整除I=I+1I≤100結(jié)束輸出I是否否是北京郵電大學(xué)算法設(shè)計(jì)的要求1、正確性：算法應(yīng)當(dāng)滿足具體問題的需求。“正確”一詞的含義在通常的用法中有很大差別，大體可分為四個(gè)層次：程序不含語法錯(cuò)誤。程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。北京郵電大學(xué)算法設(shè)計(jì)的要求（2）2、可讀性：可讀性好有助于人對(duì)算法的理解。3、健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)做出反應(yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。4、效率與低存儲(chǔ)量需求：效率指算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。北京郵電大學(xué)算法的評(píng)價(jià)評(píng)價(jià)算法的標(biāo)準(zhǔn)：評(píng)價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來判斷一個(gè)算法的優(yōu)劣。時(shí)間復(fù)雜度空間復(fù)雜度在算法時(shí)間與空間效率的兩方面，著重分析時(shí)間效率，即算法的時(shí)間復(fù)雜度，因?yàn)槲覀兛偸窍Ｍ绦蛟谳^短的時(shí)間內(nèi)給出我們所希望的輸出。北京郵電大學(xué)典型算法遞歸與分治動(dòng)態(tài)規(guī)劃貪心算法回朔法分支限界法概率算法北京郵電大學(xué)算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概述算法概述實(shí)例小結(jié)北京郵電大學(xué)實(shí)例問題描述算法和數(shù)據(jù)結(jié)構(gòu)分析C語言實(shí)現(xiàn)北京郵電大學(xué)實(shí)例問題描述算法和數(shù)據(jù)結(jié)構(gòu)分析C語言實(shí)現(xiàn)北京郵電大學(xué)問題描述隨機(jī)產(chǎn)生出一些可以讀的英文文本隨機(jī)字母?Xpdtqwtasfasgkfuwnh字母在英語里出現(xiàn)的權(quán)重？Idtefoaetcstrder從字典里隨機(jī)選擇詞的方法？Polydactylcircumscribe北京郵電大學(xué)可能的解決思路用任何一個(gè)現(xiàn)成的某種語言的文本，可以構(gòu)造出由本文本中的語言使用情況而形成的統(tǒng)計(jì)模型。通過該模型生成的隨機(jī)文本將具有與原文本類似的統(tǒng)計(jì)性質(zhì)詞word之間的關(guān)系的統(tǒng)計(jì)模型北京郵電大學(xué)馬爾可夫鏈算法1、設(shè)置w1和w2為文本的前兩個(gè)詞2、輸出W1和W23、循環(huán)：3.1.隨機(jī)地選擇出W3，它是文本中W1W2的后綴中的一個(gè)3.2.打印w33.3.把w1和w2分別換成w2和w33.4.重復(fù)循環(huán)北京郵電大學(xué)算法解釋原文本ShowyourflowchartsandconcealyourtablesandIwillbemystified.Showyourtablesandyourflowchartswillbeobvious.(end)輸入前綴跟隨的后綴詞showyourflowchartstablesyourflowchartsandwillflowchartsandconcealflowchartswillbeyourtablesandandwillbemystified.Obvious.bemystified.showbeobvious.(end）北京郵電大學(xué)實(shí)例問題描述算法和數(shù)據(jù)結(jié)構(gòu)分析C語言實(shí)現(xiàn)北京郵電大學(xué)程序要做的事情讀入一段英文文本，利用馬爾可夫鏈算法，基于文本中固定長(zhǎng)度的短語的出現(xiàn)頻率，產(chǎn)生一段新文本。前綴中詞的個(gè)數(shù)是個(gè)參數(shù)如果選1？如果選3？英文適合選2本程序?qū)υ~word的定義：任何實(shí)際位于空格之間的內(nèi)容將標(biāo)點(diǎn)符號(hào)界定在了詞上北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)的選擇問題規(guī)模分析輸入規(guī)模N=100000性能秒級(jí)北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)的選擇（2）算法分析是否需要存儲(chǔ)整個(gè)輸入數(shù)據(jù)？需要是否需要存儲(chǔ)整個(gè)輸出數(shù)據(jù)？不需要前綴的所有后綴是否需要生成并進(jìn)行存儲(chǔ)？需要是否需要維護(hù)前綴和后綴之間的關(guān)系？需要輸入的順序關(guān)系是否需要存儲(chǔ)？不需要前綴的所有后綴的最佳生成時(shí)間是什么？輸入的時(shí)候？輸入和輸出之間？輸出的時(shí)候？北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)的選擇（3）對(duì)數(shù)據(jù)結(jié)構(gòu)的要求能夠較好表達(dá)前綴與后綴之間的關(guān)聯(lián)指針？后綴是在讀輸入的過程中一個(gè)一個(gè)讀入的，事先不知道個(gè)數(shù)鏈表？動(dòng)態(tài)數(shù)組？能夠很方便地找到某個(gè)前綴對(duì)應(yīng)的后綴散列關(guān)鍵詞：？？？把一個(gè)前綴和它所有可能的后綴的集合放在一起，稱為一個(gè)狀態(tài)北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)的選擇（4）初步確定數(shù)據(jù)結(jié)構(gòu)每個(gè)狀態(tài)由一個(gè)前綴和一個(gè)后綴鏈表組成所有這些信息存放在一個(gè)散列表中，以前綴作為關(guān)鍵碼每個(gè)前綴是一個(gè)固定大小的詞集合如果一個(gè)后綴在給定前綴下出現(xiàn)多于一次，則每個(gè)出現(xiàn)都單獨(dú)包含在有關(guān)鏈表里北京郵電大學(xué)最終的主數(shù)據(jù)結(jié)構(gòu)北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)C語言定義enum{ NPREF =2, /*numberofprefixwords*/ NHASH =4093, /*sizeofstatehashtablearray*/ MAXGEN=10000 /*maximumwordsgenerated*/};typedefstructStateState;typedefstructSuffixSuffix;structState{ /*prefix+suffixlist*/ char *pref[NPREF]; /*prefixwords*/ Suffix *suf; /*listofsuffixes*/ State *next; /*nextinhashtable*/};structSuffix{ /*listofsuffixes*/ char *word; /*suffix*/ Suffix *next; /*nextinlistofsuffixes*/};State *statetab[NHASH]; /*hashtableofstates*/北京郵電大學(xué)程序的劃分基于算法，程序可分為兩個(gè)部分輸入構(gòu)造表示所有短語（前綴和其所有可能后綴）的數(shù)據(jù)結(jié)構(gòu)輸出基于上述數(shù)據(jù)結(jié)構(gòu)，生成隨機(jī)的輸出北京郵電大學(xué)主程序1、輸入讀入輸入文檔，創(chuàng)建表達(dá)了所有前綴及其相應(yīng)后綴關(guān)系的主數(shù)據(jù)結(jié)構(gòu)2、輸出基于上述數(shù)據(jù)結(jié)構(gòu)和馬爾可夫算法，生成輸出并打印。北京郵電大學(xué)輸入模塊輸入?yún)?shù)：輸入的文本？？？輸出：主數(shù)據(jù)結(jié)構(gòu)以全局變量的形式輸出，而不是以返回值的方式輸出基本算法：依次讀入文本的詞，將其作為其NPREF個(gè)詞組成的前綴的后綴加入主數(shù)據(jù)結(jié)構(gòu)如果其前綴不包含在主數(shù)據(jù)結(jié)構(gòu)中，其前綴需要加入。考慮：1、初始前綴應(yīng)該是什么？隨便找?guī)讉€(gè)詞？是由輸入文本的前NPREF個(gè)詞來組成嗎？其它的？2、本模塊怎么結(jié)束？北京郵電大學(xué)輸出模塊輸入：主數(shù)據(jù)結(jié)構(gòu)（不是通過參數(shù)輸入的）？？？輸出：基于馬爾可夫算法隨機(jī)生成的可讀的文本打印到標(biāo)準(zhǔn)輸出，而不是通過返回參數(shù)輸出基本算法馬爾可夫算法考慮：1、初始前綴應(yīng)該是什么？隨機(jī)選取NPREF個(gè)詞？輸入的前NPREF個(gè)詞？其它？2、本模塊怎么結(jié)束？北京郵電大學(xué)實(shí)例問題描述算法和數(shù)據(jù)結(jié)構(gòu)分析C語言實(shí)現(xiàn)一個(gè)大體流程解釋北京郵電大學(xué)北京郵電大學(xué)主程序：Main函數(shù)charNONWORD[]="\n";/*cannotappearasrealword*//*markovmain:markov-chainrandomtextgeneration*/intmain(void){ inti,nwords=MAXGEN; char*prefix[NPREF]; /*currentinputprefix*/ FILE*stream; charfilename[60]; /*setupinitialprefix*/ for(i=0;i<NPREF;i++) prefix[i]=NONWORD; printf("Pleaseinputfilename\n"); scanf("%s",filename);

北京郵電大學(xué)主程序（2）

if((stream=fopen(filename,"r"))==NULL) { printf("Thefile%swasnotopened\n",filename); return1; }

/*InputModule*/// build(prefix,stdin); build(prefix,stream); /*Addanendflag*/ add(prefix,NONWORD); /*OutputModule*/generate(nwords); return0;}北京郵電大學(xué)輸入模塊：build函數(shù)/*build:readinput,buildprefixtable*/voidbuild(char*prefix[NPREF],FILE*f){ charbuf[100],fmt[10]; /*createaformatstring;%scouldoverflowbuf*/ sprintf(fmt,"%%%ds",sizeof(buf)-1); while(fscanf(f,fmt,buf)!=EOF) add(prefix,estrdup(buf));}北京郵電大學(xué)Add函數(shù)/*add:addwordtosuffixlist,updateprefix*/voidadd(char*prefix[NPREF],char*suffix){ State*sp; /*Searchfortheprefix,createifnotfound*/ sp=lookup(prefix,1); addsuffix(sp,suffix); /*movethewordsdowntheprefix*/ memmove(prefix,prefix+1,(NPREF-1)*sizeof(prefix[0])); prefix[NPREF-1]=suffix;}北京郵電大學(xué)lookupState*lookup(char*prefix[NPREF],intcreate){ inti,h; State*sp; h=hash(prefix); for(sp=statetab[h];sp!=NULL;sp=sp->next){ for(i=0;i<NPREF;i++) if(strcmp(prefix[i],sp->pref[i])!=0) break; if(i==NPREF) /*foundit*/ returnsp; }

北京郵電大學(xué)lookup(2) if(create){ sp=(State*)emalloc(sizeof(State)); for(i=0;i<NPREF;i++) sp->pref[i]=prefix[i]; sp->suf=NULL; sp->next=statetab[h]; statetab[h]=sp; } returnsp;}北京郵電大學(xué)Hash函數(shù)/*hash:computehashvalueforarrayofNPREFstrings*/unsignedinthash(char*s[NPREF]){ unsignedinth; unsignedchar*p; inti; h=0; for(i=0;i<NPREF;i++) for(p=(unsignedchar*)s[i];*p!='\0';p++) h=MULTIPLIER*h+*p; returnh%NHASH;}北京郵電大學(xué)Addsuffix函數(shù)/*addsuffix:addtostate.suffixmustnotchangelater*/voidaddsuffix(State*sp,char*suffix){ Suffix*suf; suf=(Suffix*)emalloc(sizeof(Suffix)); suf->word=suffix; suf->next=sp->suf; sp->suf=suf;}北京郵電大學(xué)輸出模塊：generate函數(shù)/*generate:pr