程序員面試寶典1

28十二月20231程序員面試寶典1參考書(shū)程序員面試寶典(第三版)歐立奇等編著電子工業(yè)出版社程序員求職成功路周揚(yáng)榮編著機(jī)械工業(yè)出版社高質(zhì)量程序設(shè)計(jì)指南林銳等編著電子工業(yè)出版社1、結(jié)構(gòu)化程序設(shè)計(jì)思想2、編譯器3、C語(yǔ)言4、編程規(guī)范5、操作系統(tǒng)6、內(nèi)存管理7、優(yōu)化8、測(cè)試9、求職之路2010年7月編程語(yǔ)言排行榜語(yǔ)言所占比例1Java18.72C18.53C++10.54PHP8.65C#5.76VisualBasic5.57Python4.28Perl3.19Objective-C2.510JavaScript2.4一、結(jié)構(gòu)化程序設(shè)計(jì)思想EdsgerWybeDijkstra1930-2002

1965年，Dijkstra指出：“可以從高級(jí)語(yǔ)言中取消GOTO語(yǔ)句”

著名計(jì)算機(jī)科學(xué)家沃思(NikiklausWirth)提出一個(gè)公式

數(shù)據(jù)結(jié)構(gòu)＋算法＝程序程序＝算法＋數(shù)據(jù)結(jié)構(gòu)＋程序設(shè)計(jì)方法＋語(yǔ)言工具和環(huán)境

算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對(duì)象，語(yǔ)言是工具，編程需要采用合適的方法。算法是解決“做什么”和“怎么做”的問(wèn)題。程序中的操作語(yǔ)句，實(shí)際上就是算法的體現(xiàn)。1966年Bohm等證明了，只用順序、選擇、循環(huán)三種基本的控制結(jié)構(gòu)就能實(shí)現(xiàn)任何單入口單出口的沒(méi)有“死循環(huán)”的程序。1968年Dijkstra再次建議從一切高級(jí)語(yǔ)言中取消GOTO語(yǔ)句，只使用三種基本控制結(jié)構(gòu)編寫(xiě)程序。

AB順序BAexpTFIF_THEN_ELSEAexpTFDO_WHILE擴(kuò)展的結(jié)構(gòu)程序設(shè)計(jì)為了實(shí)際使用方便起見(jiàn)，常常還允許使用DO_UNTIL和DO＿CASE兩種控制結(jié)構(gòu)DO_CASECASE1DOCASEICASE2CASEn…DO_UNTILAexpTF修正的結(jié)構(gòu)程序設(shè)計(jì)如果需在循環(huán)體中或選擇語(yǔ)句的內(nèi)部有出口時(shí)，可以使用LEAVE（BREAK）結(jié)構(gòu)。WhileSdoBegin…LEAVE/BREAK…End;受限制的GOTO語(yǔ)句70年代初采用結(jié)構(gòu)化程序設(shè)計(jì)取得成功的例子：1971，IBM，紐約時(shí)報(bào)信息庫(kù)管理系統(tǒng)，8.3萬(wàn)行美國(guó)宇航局空間實(shí)驗(yàn)室飛行模擬系統(tǒng)，40萬(wàn)行1972年Mills提出“程序應(yīng)該只有一個(gè)入口和一個(gè)出口”，從而補(bǔ)充了結(jié)構(gòu)程序設(shè)計(jì)的規(guī)則。SP經(jīng)典定義如果一個(gè)程序的代碼塊僅僅通過(guò)順序、選擇和循環(huán)這三種控制結(jié)構(gòu)進(jìn)行連接，并且每個(gè)代碼塊只有一個(gè)入口和一個(gè)出口，則稱這個(gè)程序是結(jié)構(gòu)化的。結(jié)構(gòu)程序設(shè)計(jì)是一種盡可能少用GOTO語(yǔ)句的程序設(shè)計(jì)技術(shù)，它采用自頂向下、逐步細(xì)化的設(shè)計(jì)方法和單入口單出口的控制技術(shù)。結(jié)構(gòu)化程序設(shè)計(jì)方法自頂向下逐步細(xì)化模塊化設(shè)計(jì)結(jié)構(gòu)化編碼自頂向下逐步求精的程序設(shè)計(jì)技術(shù)自頂向下、逐步求精 若想讓計(jì)算機(jī)解題必須用清晰而無(wú)兩義性的方式給它提供算法。要求：找出一個(gè)算法，它能提供所解問(wèn)題的從輸入到輸出所需的映象。選擇一種程序語(yǔ)言寫(xiě)出程序，用計(jì)算機(jī)能接受的方式表述算法。 關(guān)鍵是如何找出算法。因?yàn)閷?xiě)出程序，只是表述算法，應(yīng)該沒(méi)有困難。編程過(guò)程問(wèn)題解決一個(gè)復(fù)雜的過(guò)程.算法解決問(wèn)題所使用的一系列合乎邏輯的、簡(jiǎn)潔的步驟.解決問(wèn)題包含的步驟:分析問(wèn)題，找出解決問(wèn)題的模型。根據(jù)模型設(shè)計(jì)出適合計(jì)算機(jī)特點(diǎn)的處理方法即算法．選擇適合的計(jì)算機(jī)語(yǔ)言進(jìn)行編程，以實(shí)現(xiàn)算法。上機(jī)編輯、調(diào)試、運(yùn)行所編制的程序．得到結(jié)果．對(duì)結(jié)果進(jìn)行分析，整理出文字材料即文檔。求解一個(gè)問(wèn)題粗略的解決方案細(xì)化第一步子問(wèn)題第二步子問(wèn)題第n步子問(wèn)題...前處理結(jié)束條件后處理進(jìn)展一步前處理后處理?xiàng)l件處理1處理2處理n......條件條件條件前處理后處理遞歸條件遞歸順序連接循環(huán)分支選擇遞歸算法的特點(diǎn)有窮性：一個(gè)算法應(yīng)包含有限個(gè)操作步驟。確定性：每個(gè)步驟應(yīng)該是確定的。有0個(gè)或多個(gè)輸入有1個(gè)或多個(gè)輸出有效性：每個(gè)步驟都能有效執(zhí)行。例1(I)例1：由鍵盤(pán)輸入三個(gè)整數(shù)，輸出其中最大的數(shù)；S1.輸入a,b,c三個(gè)整數(shù)S2.求出三個(gè)數(shù)中的最大數(shù)S3.輸出最大數(shù)如何求出最大數(shù)？現(xiàn)在還沒(méi)有討論例1(II)S2.求出三個(gè)數(shù)中的最大數(shù)算法一：S2.1如果a>b,執(zhí)行2.2，否則執(zhí)行2.3S2.2如果a>c，最大數(shù)為a，否則最大數(shù)為cS2.3如果b>c，最大數(shù)為b，否則最大數(shù)為c例1(III)S2.求出三個(gè)數(shù)中的最大數(shù)算法二：（引入temp變量）S2.1如果a>b,temp=a，否則temp=bS2.2如果temp>c，max=temp，max=c例2：判斷一個(gè)整數(shù)m是否為素?cái)?shù)算法如下：S1：輸入m的值。S2：判斷m是否為素?cái)?shù)。S3：輸出m是否為素?cái)?shù)。S4：算法結(jié)束。第2步分析：判斷整數(shù)m（m>2）是否為素?cái)?shù)的方法是：如果m不能被i整除（i為2到m-1的所有整數(shù)），則m是素?cái)?shù)。算法如下：S2.1：i賦初值為2：標(biāo)記m是素?cái)?shù)S2.2：判斷m能否被i整除。若能，標(biāo)記m不為素?cái)?shù)，結(jié)束循環(huán)。S2.3：若m不為被i整除，給i的值加1。若i<m,則轉(zhuǎn)到S3。例3(I)例3：編程找出1000以內(nèi)的所有“完數(shù)”，并按照下面格式輸出因子：6Itsfactorsare1,2,3S1:a=2S2:如果a<1000,執(zhí)行S3，否則轉(zhuǎn)S7S3:求出a的所有因子S4:如果是完數(shù)，按照格式輸出S5：a=a+1S6：轉(zhuǎn)S2S7：算法結(jié)束例3(II)S3分析：判斷整數(shù)a是否為完數(shù)的算法是：從1到a-1找出因子，看這些因子的和是否等于aS3.1:i=1,n=0(n記錄找到的第幾個(gè)因子)S3.2:判斷i<a，如果成立轉(zhuǎn)3.3，否則結(jié)束a的分解，轉(zhuǎn)到S4S3.3：如果i是a的因子,保存因子到k[n],n=n+1(因子個(gè)數(shù)加1)S3.4:i=i+1，轉(zhuǎn)3.2例3(III)S4分析：判斷是否為完數(shù)，將數(shù)a減去所有的因子，得數(shù)為0的既是完數(shù)S4.1i=0,s=aS4.2如果i<=n，s=s-k[n];否則轉(zhuǎn)S4.4S4.3i=i+1；轉(zhuǎn)到S4.2S4.4如果s=0，按照格式輸出a和所有的因子例3(IV)(S3-S4整合)S3.1:i=1,n=0(n記錄找到的第幾個(gè)因子)，s=aS3.2:判斷i<a，如果成立轉(zhuǎn)3.3，否則結(jié)束a的分解，轉(zhuǎn)到S4S3.3：如果i是a的因子,保存因子到k[n],n=n+1(因子個(gè)數(shù)加1),s=s-k[n]S3.4:i=i+1，轉(zhuǎn)3.2例4：測(cè)定字母偶的出現(xiàn)頻率測(cè)定小寫(xiě)字符串中相鄰字母偶出現(xiàn)頻率。

例如，針對(duì) thecat對(duì) th、he、ca、at計(jì)數(shù)。設(shè)有說(shuō)明： intconmat[26][26];字母偶he的出現(xiàn)次數(shù)存入下標(biāo)變量 conmat[‘h'-‘a(chǎn)’]['e'-’a’]首先把該問(wèn)題分解成如下幾步：S1初始化計(jì)數(shù)器數(shù)組conmat；S2統(tǒng)計(jì)每個(gè)字母偶的出現(xiàn)頻率；S3輸出統(tǒng)計(jì)結(jié)果。initial初始化statistical統(tǒng)計(jì)out輸出求精上述PAD中的每一個(gè)步驟：S1:初始化數(shù)組conmat,顯然應(yīng)該一行一行的初始化；對(duì)于每行又應(yīng)該一個(gè)元素一個(gè)元素的初始化。初始化第i行initial初始化for(i=0;i<26;i++)結(jié)束deffor(j=0;j<26;j++)conmat[i][j]=0S2:考慮統(tǒng)計(jì)部分：假設(shè)被統(tǒng)計(jì)的字符串是從終端輸入的，則顯然我們應(yīng)該把該字符串全部讀入，并在讀入的過(guò)程中邊讀邊統(tǒng)計(jì)。用下圖表示。讀(prevchar)statisticalwhile(!EOF)統(tǒng)計(jì)一次結(jié)束def讀(thischar)再考慮S2具體統(tǒng)計(jì)算法，為統(tǒng)計(jì)字母偶的出現(xiàn)頻率，顯然在讀入字符串的過(guò)程中應(yīng)該始終保存兩個(gè)字符prevchar、thischar，并且當(dāng)該兩個(gè)字符都是字母時(shí)，相應(yīng)計(jì)數(shù)單元加1；最后在讀入下一個(gè)字符之前還應(yīng)該把保存的兩個(gè)字符向前串。統(tǒng)計(jì)一次conmat[prevchar][thischar]++結(jié)束thischar,prevchar都是字母prevchar=thischar最后考慮輸出部分,我們把結(jié)果輸出成兩個(gè)26×13的表，每個(gè)表元素是相應(yīng)字母偶的出現(xiàn)次數(shù)：*abcde...mab...z*nopqr...zab...z

outone('a','m')輸出a..m部分outone('n','z')輸出n..z部分out輸出結(jié)束def打印一個(gè)表（第一個(gè)表），顯然應(yīng)該先打印表頭再打印下邊各行打印表頭打印表體outone結(jié)束beginch,endch打印表頭可以求精成先輸出一個(gè)“*”；再順次輸出各個(gè)字符。順次輸出各個(gè)字符是一個(gè)循環(huán)。打印表頭打印表體outone結(jié)束beginch,endch輸出('*')輸出("\n")順次輸出各個(gè)字符for(c1=beginch;

c1<=endch;

c1++)輸出(c1)打印表體應(yīng)該一行一行的打印，每行應(yīng)該先打印行頭，再打印本行各個(gè)元素；打印本行各個(gè)元素，應(yīng)該一個(gè)元素一個(gè)元素的打印，是一個(gè)循環(huán)打印表體outone結(jié)束beginch,endch輸出('*')輸出("\n")for(c1=beginch;

c1<=endch;

c1++)輸出(c1)for(c1=‘a(chǎn)’;c1<=‘z’;

c1++)輸出一行輸出(c1)輸出("\n")輸出本行各個(gè)元素for(c2=beginch;c2<=endch;c2++)輸出conmat[c1][c2]例5：三個(gè)齒輪嚙合問(wèn)題 設(shè)有三個(gè)齒輪互相銜接，求當(dāng)三個(gè)齒輪的某兩對(duì)齒互相銜接后到下一次這兩對(duì)齒再互相銜接，每個(gè)齒輪最少各轉(zhuǎn)多少圈。 解:這是求最小公倍數(shù)的問(wèn)題。每個(gè)齒輪需轉(zhuǎn)圈數(shù)是三個(gè)齒輪齒數(shù)的最小公倍數(shù)除以自己的齒數(shù)。設(shè)三個(gè)齒輪的齒數(shù)分別為:na、nb、nc；嚙合最小圈數(shù)分別為:ma、mb、mc；三齒輪齒數(shù)的最小公倍數(shù)為k3。計(jì)算步驟表示為：開(kāi)始讀入三齒輪齒數(shù)求三齒數(shù)的最小公倍數(shù)k3分別計(jì)算嚙合的最小圈數(shù)輸出結(jié)果結(jié)束讀入三齒輪齒數(shù)和輸出結(jié)果，分別只是一次調(diào)用讀或?qū)懞瘮?shù)，不必求精。求精計(jì)算三齒數(shù)的最小公倍數(shù)k3?？梢园言搯?wèn)題分解成先求兩個(gè)齒數(shù)na與nb的最小公倍數(shù)k2，然后再求k2與第三個(gè)齒數(shù)nc的最小公倍數(shù)k3，k3即為na、nb、nc三個(gè)齒輪齒數(shù)的最小公倍數(shù)。設(shè)已經(jīng)有求兩個(gè)數(shù)的最小公倍數(shù)的函數(shù)intlowestcm(intx,inty)則該求精過(guò)程可表示成。求三齒數(shù)的最小公倍數(shù)k3=lowestcm(lowestcm(na,nb),nc )結(jié)束求精求兩個(gè)數(shù)的最小公倍數(shù)的函lowestcm。x、y的最小公倍數(shù)是x、y的積除以x、y的最大公約數(shù)。設(shè)已經(jīng)有求兩個(gè)數(shù)的最大公約數(shù)的函數(shù) intgcd(intx,inty)則該求精過(guò)程可表示成：

intlowestcm(intx,inty)returnx*y/gcd(x,y)結(jié)束def采用展轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)，函數(shù) intgcd(intx,inty)定義如下函數(shù)gcd是一個(gè)遞歸函數(shù)，先采用分支求精過(guò)程、再采用遞歸求精過(guò)程，可以求精成下圖intgcd(intx,inty)結(jié)束y≠0returngcd(y,x%y)returnx最后，分別計(jì)算嚙合的最小圈數(shù)可以被求精成下圖。開(kāi)始ma=k3/namb=k3/nbmc=k3/nc結(jié)束例6：驗(yàn)證三角形外心定理三角形三條邊的垂直平分線交于一點(diǎn)，該點(diǎn)是三角形外接圓的圓心。 解：不失一般性，假設(shè)三角形的任意一條邊都不平行于任意一個(gè)坐標(biāo)軸。依據(jù)平面幾何知識(shí)，該問(wèn)題的驗(yàn)證步驟應(yīng)該是：讀入三點(diǎn)a,b,c的坐標(biāo)(x1,y1)、(x2,y2)、(x3,y3)；檢驗(yàn)三點(diǎn)是否構(gòu)成一個(gè)三角形；若三點(diǎn)構(gòu)成三角形，則驗(yàn)證外心定理。開(kāi)始驗(yàn)證外心定理結(jié)束是三角形讀入三點(diǎn)a,b,c坐標(biāo)讀入三點(diǎn)坐標(biāo)只是一個(gè)讀語(yǔ)句，不必求精，下邊求精檢驗(yàn)是否三角形和驗(yàn)證外心定理。檢驗(yàn)三點(diǎn)是否構(gòu)成三角形使用一個(gè)bool型函數(shù)isTriange，可以求精成： 求兩點(diǎn)p1,p2確定的直線方程L12； 判斷若p3在L12上， 則isTriange為false， 否則isTriange為true。

求p1,p2兩點(diǎn)直線方程L12：y=a*x+bisTriange結(jié)束w在L12上returnfalsereturntrue求兩點(diǎn)間直線方程可以寫(xiě)一個(gè)函數(shù) line(x1,y1,x2,y2,*a,*b)并求精成下圖。

line*b=y1-a*x1結(jié)束*a=(y2-y1)/(x2-x1)x1,y1,x2,y2：兩點(diǎn)坐標(biāo)*a,*b：直線方程系數(shù)

驗(yàn)證外心定理可以如下進(jìn)行：求每條邊的垂直平分線；驗(yàn)證該三條直線是否交于一點(diǎn)；若交于一點(diǎn)，則驗(yàn)證該點(diǎn)到三角形各頂點(diǎn)距離是否相等否則錯(cuò)誤命題。驗(yàn)證外心定理求每條邊的垂直平分線方程結(jié)束三條直線交于一點(diǎn)印O.K該點(diǎn)到三角形各頂點(diǎn)距離相等印false求每條邊的垂直平分線方程可以寫(xiě)一個(gè)求一條線段的垂直平分線方程的函數(shù)，然后分別三次調(diào)用該函數(shù)。

每條邊的垂直平分線方程結(jié)束求邊L12的垂直平分線：vline(ax,ay,bx,by,&a_a,&a_b)求邊L23的垂直平分線：vline(bx,by,cx,cy,&b_a,&b_b)求邊L13的垂直平分線：vline(cx,cy,ax,ay,&c_a,&c_b)求一條邊的垂直平分線方程可以先調(diào)用前述函數(shù)line，求該邊的直線方程;再求該邊的中點(diǎn),然后求過(guò)該中點(diǎn)的與該邊垂直的直線方程，得下圖vline直線方程:line(x1,y1,x2,y2,&ta,&tb)結(jié)束中點(diǎn):x=(x1+x2)/2;y=(y1+y2)/2垂直平分線方程：*a=-1/ta;*b=y-(*ta)*xx1,y1,x2,y2：兩點(diǎn)*a,*b：垂線方程驗(yàn)證該三條直線是否交于一點(diǎn)編成一個(gè)函數(shù)isOnePoint，可以先求兩條直線的交點(diǎn)，然后再判斷第三條直線是否過(guò)該點(diǎn)。三條直線交于一點(diǎn)結(jié)束求L12與L23交點(diǎn):*x=(b1-b2)/(a1-a2);*y=a1*(*x)+b1returnfalsereturntruefabs(a3*(*x)+b3-y)<eps設(shè)有一個(gè)函數(shù) distance(x1,y1,x2,y2)可以計(jì)算兩點(diǎn)間距離，驗(yàn)證三條垂直平分線的交點(diǎn)到三角形各頂點(diǎn)距離是否相等，是一個(gè)布爾表達(dá)式。distance結(jié)束returnsqrt((x2-x1)2+(y2-y1)2)

x1,y1,x2,y2：兩點(diǎn)坐標(biāo)算法的描述1.自然語(yǔ)言描述:用自然語(yǔ)言給出解決問(wèn)題的詳細(xì)步驟.如前面的例子。2.流程圖：用圖框表示。3.N-S圖4.PAD圖4.偽代碼：使用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字、符號(hào)來(lái)描述算法。5.計(jì)算機(jī)語(yǔ)言：采用這種方法必須嚴(yán)格遵守所使用的語(yǔ)言的語(yǔ)法規(guī)則。程序流程圖(I)傳統(tǒng)流程圖里常用的符號(hào)開(kāi)始或結(jié)束框“處理框”--運(yùn)算步驟輸入或輸出框判斷框連接符：一個(gè)程序中兩個(gè)部分之間的連接程序的流程線注釋6.3.1程序流程圖(III)程序流程圖的特點(diǎn)優(yōu)點(diǎn)直觀描繪控制流程易學(xué)缺點(diǎn)不是逐步求精的工具隨意轉(zhuǎn)移控制不易表示數(shù)據(jù)結(jié)構(gòu)盒圖(N-S圖)(I)出于要有一種不允許違背結(jié)構(gòu)程序設(shè)計(jì)精神的圖形工具的考慮，Nassi和Shneiderman提出了盒圖，又稱為N-S圖。盒圖(N-S圖)(II)嵌套的表示盒圖的特點(diǎn)控制結(jié)構(gòu)作用域明確不能任意轉(zhuǎn)移控制SP方式思考和解決問(wèn)題的習(xí)慣易表示嵌套關(guān)系、模塊的層次結(jié)構(gòu)PAD(ProblemAnalysisDiagram)圖(I)PAD圖(II)PAD示例PAD圖(II)對(duì)應(yīng)于增量型循環(huán)結(jié)構(gòu)

fori:=n1ton2stepn3do

在PAD中有相應(yīng)的循環(huán)控制結(jié)構(gòu)PAD圖(III)PAD圖的特點(diǎn)優(yōu)點(diǎn)結(jié)構(gòu)化程序結(jié)構(gòu)清晰表現(xiàn)程序邏輯，易讀、易懂、易記描繪數(shù)據(jù)結(jié)構(gòu)支持自頂向下、逐步求精方法的使用PAD圖高級(jí)程序設(shè)計(jì)語(yǔ)言缺點(diǎn)不適合于初學(xué)者，算法未考慮成熟時(shí)的設(shè)計(jì)過(guò)程設(shè)計(jì)語(yǔ)言(I)過(guò)程設(shè)計(jì)語(yǔ)言（PDL）也稱為偽碼，現(xiàn)在有許多種不同的過(guò)程設(shè)計(jì)語(yǔ)言在使用。它是用正文形式表示數(shù)據(jù)和處理過(guò)程的設(shè)計(jì)工具。PDL具有嚴(yán)格的關(guān)鍵字外部語(yǔ)法，內(nèi)部語(yǔ)法靈活PDL-----關(guān)鍵字+自然語(yǔ)言(1)數(shù)據(jù)說(shuō)明:格式:

TYPE

<變量名>

AS

<限定詞1><限定詞2>其功能是定義數(shù)據(jù)的類型和作用域

TYPEnumberASSTRING

LENGTH(12)過(guò)程設(shè)計(jì)語(yǔ)言(II)(2)程序塊:PDL的