高中算法程序框圖特點(diǎn)總結(jié)

彰顯數(shù)學(xué)魅力！演繹網(wǎng)站傳奇！程序框圖疑難導(dǎo)悟

問(wèn)題一一個(gè)程序框圖包括哪幾部分？具有什么特點(diǎn)？

(1)一個(gè)程序框圖包括：

①表示相應(yīng)操作的程序框，起、止框是任何程序框圖不可少的，表示框圖開(kāi)始或結(jié)束，輸入框和輸出框可用在算法中任何需要輸入、輸出的位置，算法中間要處理數(shù)據(jù)或計(jì)算，可分別寫(xiě)在不同的處理框內(nèi)，當(dāng)算法要求你對(duì)兩個(gè)不同的結(jié)果進(jìn)行判斷時(shí)，判斷條件要寫(xiě)在判斷框內(nèi)．

②帶箭頭的流程線．一個(gè)程序框到另一個(gè)程序框用流程線連接．流程線不要忘記畫(huà)箭頭，圖中它是反映流程的執(zhí)行先后次序的，若不畫(huà)出箭頭就難以判定各框的執(zhí)行順序．

③框內(nèi)必要的文字說(shuō)明．(2)特點(diǎn)：

用框圖能夠清楚地展現(xiàn)算法的邏輯結(jié)構(gòu)，具有直觀、形象、容易理解的特點(diǎn).問(wèn)題二三種基本邏輯結(jié)構(gòu)的程序框圖有哪些共同特點(diǎn)？(1)只有一個(gè)入口；

(2)只有一個(gè)出口．請(qǐng)注意一個(gè)判斷框有兩個(gè)出口,而一個(gè)條件結(jié)構(gòu)只有一個(gè)出口，不要將判斷框的出口和條件結(jié)構(gòu)出口混為一談；

(3)結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到，也就是說(shuō)每一個(gè)框都應(yīng)該有從入口到出口的路徑通過(guò)它；

(4)結(jié)構(gòu)內(nèi)的循環(huán)都不存在死循環(huán)，即無(wú)終止的循環(huán)，下圖就是一個(gè)死循環(huán)．

上述三種結(jié)構(gòu)的共同特點(diǎn)，也是檢查一個(gè)程序框圖或算法是否正確、合理的基本方法．問(wèn)題三怎樣畫(huà)程序框圖？

畫(huà)程序框圖,首先應(yīng)該有正確的自然語(yǔ)言描述的算法，然后根據(jù)算法的流程方向，使用順序結(jié)構(gòu)框圖，條件結(jié)構(gòu)框圖、循環(huán)結(jié)構(gòu)框圖將算法的內(nèi)容準(zhǔn)確地表達(dá)出來(lái),再按照算法的順序?qū)⑺鼈冇昧鞒叹�連接起來(lái)，最后加上終端框，就構(gòu)成一個(gè)完整程序框圖．在畫(huà)程序框圖時(shí)，圖形框的選擇要準(zhǔn)確，選擇主要的程序表達(dá)式或自然算法語(yǔ)言編入框圖內(nèi)，框圖布局要恰當(dāng)，方框之間連線要適當(dāng)縮短.

在設(shè)計(jì)框圖時(shí)，對(duì)各個(gè)程序結(jié)構(gòu)一定要分清楚，如果只是執(zhí)行輸入、輸出、計(jì)算等功能的，則使用順序結(jié)構(gòu)；如果要根據(jù)條件進(jìn)行判斷或者是根據(jù)情況進(jìn)行討論，那么就應(yīng)該使用條件結(jié)構(gòu)；如果重復(fù)地進(jìn)行某一操作程序，那么就要使用循環(huán)結(jié)構(gòu)．判斷好各個(gè)算法語(yǔ)句使用的語(yǔ)言結(jié)構(gòu)后，用相應(yīng)的框圖語(yǔ)言將對(duì)應(yīng)的算法語(yǔ)言表達(dá)出來(lái)，主要包括以下步驟：

第一步，用自然語(yǔ)言表述算法步驟．

第二步，確定每一個(gè)算法步驟所包含的邏輯結(jié)構(gòu),并用相應(yīng)的程序框圖表示，得到該步驟的程序框圖.

第三步，將所有步驟的程序框圖用流程線連接起來(lái)．并加上終端框，得到表示整個(gè)算法的程序框圖.

問(wèn)題四怎樣使用條件結(jié)構(gòu)？

條件結(jié)構(gòu)是程序結(jié)構(gòu)中極為重要的一個(gè)邏輯結(jié)構(gòu),只有它，才具有判斷、分類的功能．它的程序框圖是唯一的一個(gè)有一個(gè)進(jìn)入點(diǎn)、兩個(gè)退出點(diǎn)的程序框圖．

學(xué)數(shù)學(xué)用專頁(yè)第1頁(yè)共2頁(yè)版權(quán)所有少智報(bào)數(shù)學(xué)專頁(yè)彰顯數(shù)學(xué)魅力！演繹網(wǎng)站傳奇！條件結(jié)構(gòu)的第一大功能是進(jìn)行判斷，在設(shè)計(jì)條件結(jié)構(gòu)時(shí)，應(yīng)該根據(jù)判斷條件而確定所執(zhí)

行的程序流向，

條件結(jié)構(gòu)的第二大功能是對(duì)所遇到的情況進(jìn)行分類（或分情況執(zhí)行程序），要求：(1)在分類時(shí)，對(duì)所分的類別種類要清楚．不能夠出現(xiàn)類別不清，而且一個(gè)條件結(jié)構(gòu)只將情況分為兩類，若有三類以以上則須用條件結(jié)構(gòu)進(jìn)行嵌套．

(2)在分類時(shí)必須類別明確全面，不能出現(xiàn)重分、漏分和亂分．問(wèn)題五循環(huán)結(jié)構(gòu)的計(jì)數(shù)變量與累加、累乘變量在有關(guān)累加、累乘問(wèn)題的循環(huán)結(jié)構(gòu)中一般都有一個(gè)計(jì)數(shù)變量和累加或累乘變量．計(jì)數(shù)變量用于記錄循環(huán)次數(shù)．累加變量或累乘變量用于輸出結(jié)果．計(jì)數(shù)變量和累加變量一般是同步執(zhí)行的，累加或累乘一次，同時(shí)又計(jì)數(shù)一次．

累乘變量如同累加變量的設(shè)置目的一樣,只不過(guò)分工不同，前者是用來(lái)計(jì)算很多項(xiàng)的和，后者是用來(lái)處理很多項(xiàng)的積．累加變量的初值一般賦值0，累乘變量的初值一般賦值1．

累加、累乘變量是為最終輸出的結(jié)果服務(wù)的，通常累加變量用來(lái)處理有通項(xiàng)公式或遞推公式的數(shù)列的前n項(xiàng)和,累乘變量用來(lái)處理像階乘一樣有通項(xiàng)公式或遞推公式的數(shù)列的前n項(xiàng)的積.

問(wèn)題六循環(huán)結(jié)構(gòu)的三要素是什么？它們各自的作用是什么？

循環(huán)變量、循環(huán)體、循環(huán)終止條件是循環(huán)結(jié)構(gòu)的三要素，循環(huán)結(jié)構(gòu)的三要素在分析所有循環(huán)結(jié)構(gòu)的算法，畫(huà)出算法的框圖之前就應(yīng)該分析清楚，耳有準(zhǔn)確地把握了這三個(gè)要素，才能清楚地畫(huà)出循環(huán)結(jié)構(gòu)的算法框圖．

(1)循環(huán)變量：應(yīng)明確它時(shí)初始值、步長(zhǎng)（指循環(huán)變量每次增加的值）、終值.(2)循環(huán)體：也稱循環(huán)表達(dá)式,它是算法中反復(fù)執(zhí)行的部分．

(3)循環(huán)的終止條件：算法框圖中用一個(gè)判斷框來(lái)表示，用它判斷是否繼續(xù)執(zhí)行循環(huán)體．

學(xué)數(shù)學(xué)用專頁(yè)第2頁(yè)共2頁(yè)版權(quán)所有少智報(bào)數(shù)學(xué)專頁(yè)

擴(kuò)展閱讀：程序算法總結(jié)沒(méi)有密碼版本

注：所有程序以及算法均為本人從網(wǎng)絡(luò)，書(shū)籍中收集，程序均為手寫(xiě)調(diào)試完成，供RD001內(nèi)部使用，參考，謝絕其他一切形式的擴(kuò)散，共享。

應(yīng)聘的環(huán)節(jié)主要包括面試和筆試，其中不免會(huì)涉及到很多算法和數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，在這里將其先分為兩大類，筆試的時(shí)候算法題為非即時(shí)算法考察，面試的時(shí)候算法題為即時(shí)算法考察。

筆試時(shí)寫(xiě)的算法允許有較長(zhǎng)的思考時(shí)間，可以專注功能的實(shí)現(xiàn)，而暫時(shí)不管空間以及時(shí)間復(fù)雜度，面試的時(shí)候不一樣，當(dāng)你寫(xiě)出一個(gè)半吊子算法，往往面試官會(huì)讓你寫(xiě)出一個(gè)更好的，一般也會(huì)有一些提示。面試的時(shí)候算法的提問(wèn)一般不會(huì)給你很長(zhǎng)時(shí)間，短則2分鐘最長(zhǎng)也5分鐘你連思路也沒(méi)有的話基本就pass了。

這里不管是不是即時(shí)考察題型，暫且歸納為一起。

AlgorithmsandDataStructures

1明確數(shù)據(jù)結(jié)構(gòu)，單一進(jìn)行操作1-1單一數(shù)據(jù)結(jié)構(gòu)

1-1-1鏈表

在單數(shù)據(jù)結(jié)構(gòu)（即在題目中明確提到了某種數(shù)據(jù)結(jié)構(gòu)，沒(méi)有摻雜，也沒(méi)有背景，只是進(jìn)行某些特定操作）的題型中，鏈表是一大類，而單鏈表因?yàn)槠涮囟ǖ拇鎯?chǔ)結(jié)構(gòu)和讀取方法又成為考查的重點(diǎn)。

列舉題目如下

(注：以下題目的給定Node節(jié)點(diǎn)全部為如下定義方式)publicclassNode{publicNodenext;publicobjectdata;}

1-1-1-1單鏈表的反轉(zhuǎn)

給定單鏈表的頭節(jié)點(diǎn)Nodehead.給出將此鏈表反轉(zhuǎn)的方法。publicvoidReverseLinkedList(Nodehead){//首先，反轉(zhuǎn)后必然head為尾部節(jié)點(diǎn)，將head的一份拷貝賦值給一個(gè)新的node節(jié)點(diǎn)，用于托管舊的鏈表。NodenDele=head;//等你將舊鏈表需要摘取的項(xiàng)加到新鏈表頭部時(shí)，需要用另一個(gè)node暫時(shí)托管舊鏈表。NodenNext=null;//此時(shí)就將head置為了新鏈表的末尾了。head=null;while(nDele!=null){//這幾部依次為：先存下當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)用于備份，之后將dele節(jié)點(diǎn)指向新鏈表的頭部并且將新鏈表的頭位置前移，同時(shí)控制每次循環(huán)都能指向后一個(gè)節(jié)點(diǎn)向前進(jìn)行。nNext=nDele.next;nDele.next=head;head=nDele;nDele=nNext;}//至此算法完結(jié)。在這個(gè)while循環(huán)結(jié)束時(shí)候，就將原來(lái)的鏈表重新接在了新鏈表上，完成了逆轉(zhuǎn)操作。}1-1-1-2鏈表相交

給定兩個(gè)單鏈表，表頭分別為head1和head2.判斷兩個(gè)鏈表是否相交，如果不相交返回null，如果相交，則給出相交的第一個(gè)交點(diǎn)。

對(duì)題目進(jìn)行簡(jiǎn)單分析后不難得出，因?yàn)殒湵淼奶厥獯鎯?chǔ)結(jié)構(gòu)，使得其在存儲(chǔ)結(jié)構(gòu)上如果交叉則一定為“Y”型或者為“V”型，不可能為“X”型。所以相交只需求出第一個(gè)交點(diǎn)。

算法具體實(shí)現(xiàn)可以如下

publicNodeFindSameNode(Nodehead1,Nodehead2){if(head1==null||head2==null){returnnull;}//兩個(gè)Node用于托管兩個(gè)Linkedlist，這樣在操作時(shí)候不會(huì)破壞原有Node地址。NodetNode1=head1;NodetNode2=head2;//用于記錄兩個(gè)鏈表的長(zhǎng)度。intlHead1=0,lHead2=0;//用于求出連個(gè)鏈表的長(zhǎng)度，while(tNode1!=null){tNode1=tNode1.next;lHead1++;}while(tNode2!=null){tNode2=tNode2.next;lHead2++;}//到最后都沒(méi)有相交，必然沒(méi)有相交。if(tNode1!=tNode2){returnnull;}//相交了，這時(shí)還可以繼續(xù)從參數(shù)提取倆鏈表首地址。else{tNode1=head1;tNode2=head2;//沒(méi)有這兩個(gè)賦值，他們的next都為null了。//先假設(shè)兩個(gè)鏈表長(zhǎng)度不一樣，求出他們的長(zhǎng)度差。intf=System.Math.Abs(lHead1-lHead2);//先判斷后循環(huán)，小優(yōu)化。if(lHead1>lHead2){//使長(zhǎng)的鏈表將長(zhǎng)的一部分走完，之后就能一起走到交點(diǎn)。當(dāng)循環(huán)結(jié)束，兩個(gè)鏈表指針到末尾的長(zhǎng)度一樣了。for(intk=0;k

給定一個(gè)單鏈表，頭節(jié)點(diǎn)為nodehead.找出其倒數(shù)第N個(gè)節(jié)點(diǎn)。

算法思路即為給定兩個(gè)Node,起初在Head節(jié)點(diǎn)向后走的時(shí)候，使另外一個(gè)節(jié)點(diǎn)node1托管這個(gè)鏈表的頭，在Head向后走了N個(gè)節(jié)點(diǎn)后，node1向后遍歷，在Head為Null時(shí)，node1即指向了倒數(shù)第N個(gè)節(jié)點(diǎn)。算法可以如下：

publicNodeFindCountdownNode(Nodehead,intN){if(head==null){returnnull;}//兩個(gè)托管指針。NodenTmpNode=head;NodenCountDownNode=head;//循環(huán)結(jié)束后，兩個(gè)指針相差距離為Nfor(inti=0;i

刪除單鏈表中的某節(jié)點(diǎn)，或者不知道頭節(jié)點(diǎn)，這時(shí)需要保證此節(jié)點(diǎn)不是最后一個(gè)節(jié)點(diǎn)，或者即使讓你知道頭節(jié)點(diǎn)，但是不允許循環(huán)遍歷。

思路即為，因?yàn)橹�道這個(gè)節(jié)點(diǎn)，不遍歷，能找到的只有他下一個(gè)節(jié)點(diǎn)以及他本身，這樣的話將他下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)和next屬性付給當(dāng)前節(jié)點(diǎn)，并將下一節(jié)點(diǎn)刪除即可，偷梁換柱，達(dá)到效果。

代碼可以如下：

publicvoidDeleOndeNode(NoderandomNode){//沒(méi)有判斷NodemyNext=randomNode.next;if(myNext!=null){randomNode.data=myNext.data;randomNode.next=myNext.next;myNext=null;}else{/*只有當(dāng)給定head時(shí)候才可以處理末尾節(jié)點(diǎn)，代碼為Nodecurr_node=head;while(curr_node.next!=ramdomNode){curr_node=curr_node.next;}curr_node=NULL;*/}}

1-1-1-5鏈表是否有環(huán)

如何判斷一個(gè)鏈表是否有環(huán)存在。

思路為定義兩個(gè)指針，即好像在操場(chǎng)上跑步，只要兩個(gè)人速度不一樣，速度快的肯定會(huì)有套速度慢的一圈的時(shí)刻。難點(diǎn)的還可以加上找到環(huán)的入口點(diǎn)，這里暫且不說(shuō)。代碼可以如下publicboolIsExistLoop(NodeHead){if(Head==null||Head.next==null){returnfalse;}if(Head.next==Head){returntrue;}NodeslowH=Head;NodefastH=Head.next;//兩個(gè)指針開(kāi)始追逐while(slowH!=fastH&&fastH!=null&&fastH.next!=null){slowH=slowH.next;fastH=fastH.next.next;}//退出循環(huán)的條件未知，判斷一下是否有環(huán)if(slowH==fastH){returntrue;}returnfalse;}1-1-1-6兩個(gè)遞增鏈表合并為遞減鏈表

給定兩個(gè)遞增的鏈表，頭節(jié)點(diǎn)分別為head1,head2,如何操作使之合并為一個(gè)遞減的鏈表。

思路為經(jīng)典的二路歸并排序算法，建立一個(gè)新鏈表，開(kāi)始遍歷兩個(gè)鏈表，將數(shù)值小的插入到新鏈表的末尾，并且將該節(jié)點(diǎn)原來(lái)指針向前移動(dòng)一次，繼續(xù)比較，大多數(shù)情況在遍歷玩一個(gè)鏈表后，另外一個(gè)會(huì)有剩余節(jié)點(diǎn)，需要處理。代碼可以如下publicvoidMergeSortList(Nodehead1,Nodehead2){//為了不破壞原有鏈表，依然設(shè)立托管指針。NodeDele1=head1;NodeDele2=head2;NodetmpNode=null;NodetmpNode2=null;Nodehead=null;//判斷鏈表的節(jié)點(diǎn)，誰(shuí)的data值為小的，則將其對(duì)接在新鏈表的末尾，并將新鏈表前移一位。//若兩個(gè)鏈表值相等，則同時(shí)對(duì)接在末尾，并使dele1在前。while(Dele1!=null&&Dele2!=null){if(Dele1.dataDele2.data){tmpNode=Dele2.next;Dele12.next=head;head=Dele2;Dele2=tmpNode;}else{tmpNode=Dele1.next;tmpNode2=Dele2.next;Dele12.next=head;Dele1.next=Dele2;head=Dele1;Dele1=tmpNode;Dele2=tmpNode2;}}//在此循環(huán)之前，其中一個(gè)鏈表已經(jīng)循環(huán)完畢了，下面就是看哪個(gè)鏈表還有剩余.//同逆轉(zhuǎn)的思想，對(duì)接到新鏈表。while(Dele1.next!=null){tmpNode=Dele1.next;Dele1.next=head;head=Dele1;Dele1=tmpNode;}while(Dele2.next!=null){tmpNode=Dele2.next;Dele2.next=head;head=Dele2;Dele2=tmpNode;}//此時(shí)head即為新鏈表的頭節(jié)點(diǎn)，完成了降序排列，嚴(yán)格來(lái)說(shuō)。//此算法不是2路歸并排序，二路歸并排序具體效果是使兩個(gè)升序鏈表生成新的升序鏈表。//而在操作完了之后還需要一次逆轉(zhuǎn)，我認(rèn)為這樣的效率不如直接逆轉(zhuǎn)。//如果采用傳統(tǒng)的二路歸并，核心代碼應(yīng)該如下，切記在完成之后需一次Reverse操作。/**判斷誰(shuí)小，假設(shè)dele1,*head.next=dele1*head=dele1*dele1=dele1.next*等到循環(huán)完畢只需要用if不需要用while判斷，對(duì)接到剩余的鏈表即可，*if(dele1!=null)head.next=dele1;*if(dele2!=null)head.next=dele2;*/}1-1-2二叉樹(shù)

在如下算法中所默認(rèn)的二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)均如下所示：publicclassBinTreeNode{publicobjectdata;publicBinTreeNodeLeftChildTree;publicBinTreeNodeRightChildTree;}在對(duì)二叉樹(shù)的操作中，頻繁的會(huì)用到遞歸，分治的思想。同時(shí)由于二叉樹(shù)的深度優(yōu)先，廣度優(yōu)先遍歷，以及先序，中序，后序的非遞歸方式涉及到堆棧以及隊(duì)列，故列到后面，屬于復(fù)合數(shù)據(jù)結(jié)構(gòu)的部分。

1-1-2-1先序，中序，后序遍歷

二叉樹(shù)有3種遍歷方式，先序，中序，后序。三種遍歷方式寫(xiě)法類似，都用到了遞歸：遍歷結(jié)果都知道，程序如下：

publicvoidPreOrder(BinTreeNodehead){if(head!=null){Console.WriteLine(head.data.ToString());PreOrder(head.LeftChildTree);PreOrder(head.RightChildTree);}}publicvoidMidOrder(BinTreeNodehead){if(head!=null){MidOrder(head.LeftChildTree);Console.WriteLine(head.data.ToString());MidOrder(head.RightChildTree);}}publicvoidPostOrder(BinTreeNodehead){if(head!=null){MidOrder(head.LeftChildTree);MidOrder(head.RightChildTree);Console.WriteLine(head.data.ToString());}}1-1-2-2求二叉樹(shù)的深度

同樣用遞歸，算法如下

publicintGetDepth(BinTreeNodehead){if(head==null)return0;intleftDepth,rightDepth,totalDepth;leftDepth=GetDepth(head.LeftChildTree);rightDepth=GetDepth(head.RightChildTree);totalDepth=leftDepth>rightDepth?leftDepth+1:rightDepth+1;returntotalDepth;}

1-1-2-3求二叉（排序）樹(shù)的最近公共祖先

算法思想，對(duì)于二叉排序樹(shù)（binarysearchtree）有一個(gè)特點(diǎn)，就是對(duì)于一個(gè)root左節(jié)點(diǎn)都是小于他的value的node節(jié)點(diǎn)，而root的右節(jié)點(diǎn)都大于root的value值，這樣的話可以歸納出如下思考方法：當(dāng)待尋找的兩個(gè)節(jié)點(diǎn)node1和node2，滿足node1.datahead.data){returnSearchCommonFather(node1,node2,head.RightChildTree);}elseif(node1.data

1-1-2-4二叉排序樹(shù)轉(zhuǎn)換為循環(huán)雙向鏈表

思路仍然為遞歸，先將左子樹(shù)變?yōu)長(zhǎng)inkedList(LL),再將右子樹(shù)變?yōu)長(zhǎng)L,之后將左子樹(shù)，Root，右子樹(shù)變?yōu)橐粋�(gè)整體的LL.代碼可以如下#regionBST-To-DoubleSortedLinkedList//此函數(shù)用于將兩個(gè)LinkedList首尾對(duì)接。publicBinTreeNodeAppendLL(BinTreeNodenode1,BinTreeNodenode2){if(node1==null)returnnode2;if(node2==null)returnnode1;//找到尾巴節(jié)點(diǎn)BinTreeNodetail1=node1.LeftChildTree;BinTreeNodetail2=node2.RightChildTree;//完成首尾對(duì)接，兩個(gè)首尾都需要對(duì)接tail1.RightChildTree=node2;node2.LeftChildTree=tail1;tail2.RightChildTree=node1;node1.LeftChildTree=tail2;returnnode1;}publicBinTreeNodeConvertBstToLinkedList(BinTreeNodehead){if(head==null)returnnull;//求出左右子樹(shù)的鏈表。BinTreeNodeleftLL=ConvertBstToLinkedList(head.LeftChildTree);BinTreeNoderightLL=ConvertBstToLinkedList(head.RightChildTree);//首先讓head獨(dú)立，不然亂了，具體原因可以查看Append函數(shù)。head.RightChildTree=head;head.LeftChildTree=head;//嫁接leftLL=AppendLL(leftLL,head);leftLL=AppendLL(leftLL,rightLL);returnleftLL;}#endregion1-1-2-5計(jì)算一個(gè)二叉樹(shù)的葉子數(shù)目

同樣的思想，總之二叉樹(shù)遞歸就對(duì)了，注意設(shè)置遞歸的出口。代碼如下

publicvoidCountTreeLeaf(BinTreeNodehead,refintcount){//用Out傳址方式返回?cái)?shù)目。count=0;if(head!=null){if(head.LeftChildTree==null&&head.RightChildTree==null)count++;//分別計(jì)算左右子樹(shù)，計(jì)算完畢后Count即為葉子數(shù)目。CountTreeLeaf(head.LeftChildTree,refcount);CountTreeLeaf(head.RightChildTree,refcount);}}//沒(méi)有帶返回值，也沒(méi)有調(diào)試，這樣不方便是需要在調(diào)用時(shí)確定Count為0，或者可以用返回int值的。左右相加即可

1-1-2-6求二叉樹(shù)葉子節(jié)點(diǎn)的最大距離

此為編程之美上的一道算法題，文章在最后著重說(shuō)了如何控制遞歸的調(diào)用和退出。所謂距離，就是指兩個(gè)節(jié)點(diǎn)之間的距離�？梢韵胂螅�距離最遠(yuǎn)兩個(gè)節(jié)點(diǎn)必然為兩個(gè)葉子節(jié)點(diǎn)，假設(shè)根節(jié)點(diǎn)為K,兩個(gè)最大距離的節(jié)點(diǎn)為U和V,那么有兩種情況：

（1）U和V分別在K節(jié)點(diǎn)的兩個(gè)子樹(shù)上，那么他們之間的路線必然經(jīng)過(guò)K.(2)U和V在K節(jié)點(diǎn)的一個(gè)子樹(shù)上，那么他們之間的路線必然不經(jīng)過(guò)K.問(wèn)題即可以轉(zhuǎn)化為在子樹(shù)上求最大距離的點(diǎn)，之后Max一下就可以了。

注：在做這個(gè)問(wèn)題的時(shí)候，需要在以前的BinTreeNode重新派生一個(gè)類，其中多出來(lái)兩個(gè)屬性用以記錄該節(jié)點(diǎn)左子樹(shù)和右子樹(shù)中的最長(zhǎng)距離，或者直接加也可，否則無(wú)法編譯通過(guò)。代碼如下，參照編程之美。

intmaxlen=0;publicvoidFindMaxLen(BinTreeNodehead){//空樹(shù)if(head==null)return;//一下兩步用于判斷左右子樹(shù)是否為空，在給屬性賦值完畢之后，用遞歸確保程序執(zhí)行，而真正算距離的還沒(méi)開(kāi)始，也是到達(dá)葉子節(jié)點(diǎn)以后的反彈階段。if(head.LeftChildTree==null){head.nMaxLeft=0;}else{FindMaxLen(head.LeftChildTree);}if(head.RightChildTree==null){head.nMaxRight=0;}else{FindMaxLen(head.RightChildTree);}//這里計(jì)算左子樹(shù)的最大距離，非葉子節(jié)點(diǎn)都要經(jīng)過(guò)這里兩個(gè)邏輯中至少一個(gè)。if(head.LeftChildTree!=null){intnTempMax=0;//判斷左右子樹(shù)哪個(gè)更深head.LeftChildTree.nMaxLeft>head.LeftChildTree.nMaxRight?nTempMax=head.LeftChildTree.nMaxLeft:nTempMax=head.LeftChildTree.nMaxRight;//將左右子樹(shù)更深的+和根節(jié)點(diǎn)的這條連線，作為這個(gè)子樹(shù)的深度。head.LeftChildTree.nMaxLeft=nTempMax+1;}//右子樹(shù)if(head.RightChildTree!=null){intnTempMax=0;//判斷左右子樹(shù)哪個(gè)更深head.RightChildTree.nMaxLeft>head.RightChildTree.nMaxRight?nTempMax=head.RightChildTree.nMaxLeft:nTempMax=head.RightChildTree.nMaxRight;//將左右子樹(shù)更深的+和根節(jié)點(diǎn)的這條連線，作為這個(gè)子樹(shù)的深度。head.RightChildTree.nMaxLeft=nTempMax+1;}//左右子樹(shù)都算完了，加起來(lái)就是這個(gè)大子樹(shù)的深度，需要更新一下maxlen。if(head.nMaxLeft+head.nMaxRight>maxlen){maxlen=head.nMaxLeft+head.nMaxRight;}}/*遞歸的分析方法：*(1)弄清遞歸的順序，遞歸實(shí)現(xiàn)中，往往要假設(shè)后面的調(diào)用已經(jīng)完成，即已經(jīng)到最后一步了，上題即是這種情況。*(2)分析遞歸的邏輯，每次要有正確的變量變化，否則遞歸就沒(méi)用了。*(3)找到遞歸的出口，邊界條件，如不為null,大于0等等，需要設(shè)置遞歸的出口。*/1-1-2-7向BST中插入一個(gè)節(jié)點(diǎn)

BST即為(BinarySearchTree)，特點(diǎn)上面已經(jīng)說(shuō)過(guò)。

思路如下，

因?yàn)橐�插入的�?jié)點(diǎn)必然要成為暫時(shí)的葉子節(jié)點(diǎn)，所以必然要等到遍歷到null的時(shí)候插入。所以可以按如下步驟

(1)把父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)，即根節(jié)點(diǎn)；(2)如果新節(jié)點(diǎn)內(nèi)的數(shù)據(jù)值小于當(dāng)前節(jié)點(diǎn)內(nèi)的數(shù)據(jù)值，那么把當(dāng)前節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)。如果新節(jié)點(diǎn)內(nèi)的數(shù)據(jù)值大于當(dāng)前節(jié)點(diǎn)內(nèi)的數(shù)據(jù)值，那么就跳到步驟4；

(3)如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)的數(shù)值為空（null），就把新節(jié)點(diǎn)插入在這里并且退出循環(huán)。否則，跳到while循環(huán)的下一次循環(huán)操作中；

(4)把當(dāng)前節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)；

(5)如果當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)的數(shù)值為空（null），就把新節(jié)點(diǎn)插入在這里并且退出循環(huán)。否則，跳到while循環(huán)的下一次循環(huán)操作中。代碼如下publicvoidInsert(BinTreeNodehead,inti){BinTreeNodebtn=newBinTreeNode();btn.data=i;//如果是空樹(shù)，不用插入了。if(head==null){head=btn;}//不是空樹(shù)else{//移動(dòng)的指針以及他的父節(jié)點(diǎn)指針，找到合適的節(jié)點(diǎn)，就可以取而代之。BinTreeNodecurrent=head;BinTreeNodeparent;//查找符合條件的位置while(true){//指針要走了，記錄下現(xiàn)在即為其父節(jié)點(diǎn)。parent=current;//應(yīng)該放在左子樹(shù)？if(i

另外就是初始化一個(gè)二叉樹(shù)，這個(gè)相對(duì)簡(jiǎn)單，只不過(guò)不斷重復(fù)插入。

刪除一個(gè)節(jié)點(diǎn)，這個(gè)比較復(fù)雜，一般會(huì)在BST結(jié)構(gòu)有這種需要，需要考慮幾種情況，（1）沒(méi)有葉子節(jié)點(diǎn)，這樣直接將其置為null即可，（2）有左無(wú)右，需要將左節(jié)點(diǎn)摘下來(lái)重新分配。（3）有右無(wú)左，同上.(4)有右有左，最復(fù)雜，不分析了。

1-2復(fù)合數(shù)據(jù)結(jié)構(gòu)

單數(shù)據(jù)結(jié)構(gòu)常用的就是上面兩種，而堆棧，隊(duì)列一般會(huì)作為組合或者與上述兩種結(jié)構(gòu)的組合進(jìn)行考察。舉例如下：

1-2-1用鏈表模擬堆棧和隊(duì)列

詳細(xì)意思就是說(shuō)，用對(duì)鏈表的操作，模擬實(shí)現(xiàn)堆棧的特色操作，后進(jìn)先出Push(i),Pop().以及隊(duì)列的特色操作先進(jìn)先出，Enqueue(i),Dequeue().代碼以及注釋如下

publicclassStackAndQueueWithLinkedList{//維護(hù)兩個(gè)指針，這兩個(gè)指針?lè)謩e已經(jīng)指向傳進(jìn)來(lái)準(zhǔn)備操作的鏈表的頭和尾。NodeListFirst=newNode();NodeListEnd=newNode();//在構(gòu)造函數(shù)中對(duì)指針初始化。publicStackAndQueueWithLinkedList(NodeHead){ListFirst=Head;ListEnd=GetTail(Head);}//得到最后一個(gè)node.privateNodeGetTail(NodeHead){if(Head==null)returnnull;Nodetemp=Head;while(temp!=null){temp=temp.next;}returntemp;}//進(jìn)隊(duì)列，加到末尾。boolEnqueue(inti){//裝箱NodecurNode=newNode();curNode.data=i;//如果是空的。if(ListEnd==null){ListFirst=curNode;ListEnd=curNode;}//不為空，加到末尾。else{ListEnd.next=curNode;//更新尾部節(jié)點(diǎn)。ListEnd=curNode;}returntrue;}//出隊(duì)列objectDequeue(){//如果為空if(ListFirst==null){throw(newException("LinkedListisnull"));}//出隊(duì)以后的數(shù)據(jù)intdata=ListFirst.data;//如果就此一個(gè)節(jié)點(diǎn)，刪除之后，F(xiàn)irst和End都應(yīng)該為nullif(ListFirst.next==null){ListEnd=null;}//更新開(kāi)始節(jié)點(diǎn)。ListFirst=ListFirst.next;returndata;}//進(jìn)堆棧,和進(jìn)隊(duì)列一樣的，都是加到末尾。boolpush(inti){//裝箱NodecurNode=newNode();curNode.data=i;//如果是空的。if(ListEnd==null){ListFirst=curNode;ListEnd=curNode;}//不為空，加到末尾。else{ListEnd.next=curNode;//更新尾部節(jié)點(diǎn)。ListEnd=curNode;}returntrue;}//出堆棧objectpop(){if(ListFirst==null)thrownewException("LinkedListisnull");//道理同上if(ListFirst.next==null){ListEnd=null;}//以下三行更新End節(jié)點(diǎn)NodepreNode=FindPreviousOfLast();intdata=preNode.data;ListEnd=preNode;returndata;}//和找倒數(shù)第N個(gè)的思路一樣。privateNodeFindPreviousOfLast(){NodetmpEndNode=newNode();NodetmpPreNode=newNode();tmpPreNode=tmpEndNode=ListFirst;tmpEndNode=tmpEndNode.next;while(tmpEndNode!=null){tmpEndNode=tmpEndNode.next;tmpPreNode=tmpPreNode.next;}returntmpPreNode;}}1-2-2樹(shù)的先序，中序，后序遍歷（非遞歸）

在單一數(shù)據(jù)結(jié)構(gòu)的操作中有很簡(jiǎn)單的用遞歸操作樹(shù)的遍歷，3句話就可以把樹(shù)的先序，后序，中序遍歷表示出來(lái)，如果不用遞歸的話，為保證可以順利回溯，則需要用臨時(shí)的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)遍歷過(guò)程中的點(diǎn)，堆棧是一個(gè)好的選擇。代碼如下：publicvoidPreOrderWithOutRecursive(BinTreeNodehead){Stackmystack=newStack();//在遍歷一個(gè)root節(jié)點(diǎn)以后，要把它壓棧，以便以后能按順序返回各自的右節(jié)點(diǎn)。while(head!=null||mystack.Count!=0){//輸出自己和左子樹(shù)。while(head!=null){Console.WriteLine(head.data.ToString());mystack.Push(head);head=head.LeftChildTree;}//將自己的右子樹(shù)返回來(lái)，繼續(xù)向下循環(huán)。if(mystack.Count!=0){BinTreeNodetmpRoot=mystack.Pop();head=tmpRoot.RightChildTree;}}}publicvoidMidOrderWithOutRecursive(BinTreeNodehead){Stackmystack=newStack();//同上，壓棧處理，不同的是，不能馬上輸出自己，只能等到pop到自己的時(shí)候再輸出while(head||mystack.Count!=0){while(head!=null){mystack.Push(head);head=head.LeftChildTree;}if(mystack.Count!=0){BinTreeNodetmpRoot=mystack.Pop();Console.WriteLine(tmpRoot.data.ToString());head=tmpRoot.RightChildTree;}}}/*后序遍歷的難點(diǎn)在于需要知道某節(jié)點(diǎn)的右子樹(shù)是否已經(jīng)遍歷過(guò)，*我自己沒(méi)寫(xiě)出來(lái)，參考網(wǎng)上的算法，主要有兩種，一種是在Node節(jié)點(diǎn)加一個(gè)屬性為tag,初始值為false,標(biāo)志該節(jié)點(diǎn)*的右子樹(shù)是否已經(jīng)被遍歷過(guò)，一種是通過(guò)判斷記上一次訪問(wèn)的節(jié)點(diǎn)是否和現(xiàn)在節(jié)點(diǎn)的右子樹(shù)節(jié)點(diǎn)相等。*///基于第一種加一個(gè)tag的方式，代碼如下publicvoidPostOrderWithOutRecursive(BinTreeNodehead){Stackmystack=newStack();while(head!=null||mystack.Count!=0){while(head!=null){mystack.Push(head);head=head.LeftChildTree;}if(mystack.Count!=0){head=mystack.Peek();if(head.tag)//可以訪問(wèn){Console.WriteLine(head.data.ToString());mystack.Pop();head=null;//第二次訪問(wèn)時(shí)候標(biāo)志其右子樹(shù)也已經(jīng)被遍歷。}//不能訪問(wèn)，那么繼續(xù)向右找，還有沒(méi)遍歷的。else{head.tag=true;head=head.RightChildTree;}}}}//結(jié)構(gòu)更清晰的一個(gè)算法，代碼如下publicvoidPostOrderWithOutRecursive2(BinTreeNodehead){Stackmystack=newStack();if(head!=null){mystack.Push(head);}while(mystack.Count!=0){BinTreeNodebtn=mystack.Pop();//左右子樹(shù)都已入棧if(btn.tag){Console.WriteLine(btn.data.ToString());}//左右子樹(shù)尚未入棧，需要一次壓入右，左，中節(jié)點(diǎn)。else{if(btn.RightChildTree!=null){btn.RightChildTree.tag=false;//控制其左右子樹(shù)都為false.mystack.Push(btn.RightChildTree);}if(btn.LeftChildTree!=null){btn.LeftChildTree.tag=false;//false.mystack.Push(btn.LeftChildTree);}btn.tag=true;mystack.Push(btn);}}}//至于不用標(biāo)志位的一個(gè)算法，更難一些。也更麻煩一些。如下publicvoidPostOrderWithOutRecursive3(BinTreeNodehead){//先把當(dāng)前的head做一個(gè)備份BinTreeNodetmp=head;Stackmystack=newStack();while(head!=null){//左子樹(shù)全部入棧，老方法。for(;head.LeftChildTree!=null;head=head.LeftChildTree)mystack.Push(head);//當(dāng)前節(jié)點(diǎn)無(wú)右子樹(shù)，或者子樹(shù)已經(jīng)輸出while(head!=null&&(head.RightChildTree!=null||head.RightChildTree==tmp)){Console.WriteLine(head.data.ToString());tmp=head;if(mystack.Count==0)return;head=mystack.Pop();}//處理右節(jié)點(diǎn)mystack.Push(head);head=head.RightChildTree;}}1-2-3樹(shù)的廣度優(yōu)先遍歷。

深度優(yōu)先和廣度優(yōu)先是對(duì)于二叉樹(shù)最基本的兩個(gè)算法，事實(shí)上，先中后序遍歷都是深度優(yōu)先遍歷的特例，設(shè)L、D、R分別代表遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)和遍歷右子樹(shù)，則有DLR(先序)、LDR(中序)、LRD(后序)、DRL、RDL、RLD六種不同的二叉樹(shù)深度遍歷方案。上面已經(jīng)寫(xiě)了那么多了，深度優(yōu)先就不寫(xiě)了，其余的就不寫(xiě)了。

而主要寫(xiě)廣度優(yōu)先，廣度優(yōu)先就是對(duì)樹(shù)分層，也叫層次遍歷這樣的話用隊(duì)列存儲(chǔ)比較好。代碼如下publicvoidLevelTravel(BinTreeNodehead){if(head==null)return;QueuemyQue=newQueue();myQue.Enqueue(head);//為實(shí)現(xiàn)廣度優(yōu)先，一般不能用遞歸，一定是一邊入隊(duì)一邊出隊(duì)，而終止條件就是隊(duì)列為空while(myQue.Count!=0){BinTreeNodetmpNode=myQue.Dequeue();Console.WriteLine(tmpNode.data.ToString());//節(jié)點(diǎn)自己出了隊(duì)列，將自己的左右孩子入到隊(duì)列末端。if(tmpNode.LeftChildTree!=null){myQue.Enqueue(tmpNode.LeftChildTree);}if(tmpNode.RightChildTree!=null){myQue.Enqueue(tmpNode.RightChildTree);}}}2數(shù)據(jù)結(jié)構(gòu)不明確，偏向考察算法2-1對(duì)于M的階乘，末尾有多少個(gè)0？

題目分析：對(duì)于乘法，只能有2和5相乘才可以產(chǎn)生0，而且2與5的倍數(shù)相乘也可以得0.在一個(gè)隨機(jī)連續(xù)的范圍內(nèi)，偶數(shù)與5的倍數(shù)的個(gè)數(shù)相比，偶數(shù)總是多于5的倍數(shù)，那么這樣的話，相乘得到0的個(gè)數(shù)的瓶頸則可以確定在于5的個(gè)數(shù).由此，問(wèn)題則歸結(jié)為，求1-M中5的出現(xiàn)個(gè)數(shù)，換句話說(shuō)，就是有多少個(gè)數(shù)一共能貢獻(xiàn)多少個(gè)5（例，5的貢獻(xiàn)度為一個(gè)5，25貢獻(xiàn)度為2個(gè)5，50也是2個(gè)5.以此類推）。可以得到解題程序如下：

publicintfindZeroCount(intm){//小于5就算了。if(mfor(inti=1;i1;i--){index=r.Next(1,i);//放入數(shù)組，倒著放的。myArr[i-2]=tmpList[index];//這句是關(guān)鍵。也可以自己實(shí)現(xiàn)。tmpList.RemoveAt(index);}returnmyArr;}2-3斐波那契數(shù)列求第N項(xiàng)。

斐波那契數(shù)列則是如下這樣的數(shù)列：{1,1,2,3,5,8……..}遞歸的教科書(shū)教材例子，不過(guò)也經(jīng)常問(wèn)到。程序如下

publicintvisitFibonacci(intn){intret=0;if(n<2)ret=1;//遞歸else{ret=visitFibonacci(n-2)+visitFibonacci(n-1);}returnret;}2-4回文判斷

輸入一個(gè)字符串，判斷是否為回文。回文就是正著看倒著看都一樣的字符串，比如“abcba”.”MoM”.先給出一個(gè)我自己寫(xiě)的publicboolisPalindrome(char[]text){boolflag=true;inti=0;intlength=text.Length;//length或者length+1或者length-1/2貌似都行for(i=0;i

數(shù)組為整型。具體就是找到相同的就把相同兩個(gè)中的前一個(gè)Cover掉。先寫(xiě)一個(gè)最容易想的，特別傻的方法。程序如下，時(shí)間復(fù)雜度為N^2.

publicvoidremoveDuplicate(int[]a){intsize=a.Length;intcount=0;inti,j;//類似冒泡了。很慢for(i=0;i2-6用一次遍歷求出兩個(gè)數(shù)組的并集

此題思路和上一個(gè)題的第二種解法類似，只不過(guò)可以不用indexof，用一個(gè)正規(guī)點(diǎn)的，HashTable.publicstaticint[]GetUnion(int[]arr1,int[]arr2){Listlist=newList();System.Collections.Hashtableht=newSystem.Collections.Hashtable();//遍歷第一個(gè)數(shù)組，有的元素都標(biāo)上記號(hào)。for(inti=0;i

思路如下：學(xué)過(guò)二進(jìn)制都知道，將一個(gè)數(shù)除以2的過(guò)程，事實(shí)上就是對(duì)其進(jìn)行右移位一次的過(guò)程，用10100010為例，第一次除以2，商為1010001，余0，所以為偶數(shù)。再除以2，商為101000，余1，所以為奇數(shù)。如此反復(fù)。于是可以有如下解法求出一個(gè)數(shù)的二進(jìn)制表示中1的個(gè)數(shù)代碼1：publicintgetOneDigCount(intm){intcount=0;while(m>0){//如果能被2整除if(m%2==1){count++;}m=m/2;}returncount;}或者可以考慮用位操作符，因?yàn)榧词鼓銓?xiě)的每次/2，在計(jì)算機(jī)中，也是如此操作的，把這個(gè)過(guò)程寫(xiě)下來(lái)，可以節(jié)省很多的執(zhí)行時(shí)間，而如何判斷最后一位是不是1則成了關(guān)鍵，可以用當(dāng)前數(shù)與0x01進(jìn)行“與”操作。如果結(jié)果為1則最后一位是1.代碼如下publicintgetOneCount(intm){intcount=0;while(m>0){//與操作count+=m&0x01;//右移一位的操作m>>=1;}returncount;}2-8按順序輸出矩陣中的數(shù)字：

思路：因?yàn)榫仃囕敵鲇蟹较虻淖兓�，故采用一個(gè)bool型變量控制輸出方向。程序應(yīng)該還有改進(jìn)空間，如下publicstaticvoidprintArrayInrule(){//矩陣為4×4的，這兩個(gè)也可作為參數(shù)接收。constintlength=16;constintwidth=4;//計(jì)數(shù)器，控制矩陣范圍內(nèi)intindex=0;//具體每一列輸出的數(shù)值intstartI=1;//多少個(gè)轉(zhuǎn)變一次方向intmyPoint=1;//true為向下，false為向上boolDirection=true;while(index=width){Console.WriteLine(startI.ToString());startI+=1;Direction=!Direction;myPoint=0;}else{//向下if(Direction){Console.WriteLine(startI.ToString());startI+=4;}//向上elseif(!Direction){Console.WriteLine(startI.ToString());startI-=4;}}myPoint++;index++;}}2-9給定一個(gè)數(shù)組為N個(gè)元素集合

int型數(shù)組，N個(gè)，求出其中和為N+1的數(shù)隊(duì)。復(fù)雜度為O（n）為（n^2）則不得分我想的是先對(duì)數(shù)組排序，快排，復(fù)雜度為（nlogn），然后再用兩個(gè)指針head,tail,標(biāo)識(shí)，如果head+tail=N+1則計(jì)數(shù)器+1，如果head+tailN+1則tail--.如此找到所有數(shù)對(duì)。

而上網(wǎng)查的是用一個(gè)HashTable來(lái)標(biāo)記，復(fù)雜度為O(N)，但是哈希表不用.NET內(nèi)置的，自己模擬一個(gè)，代碼如下：

publicstaticintgetSumCount(int[]array,intN){intcount=0;//創(chuàng)建哈希表int[]hashTable=newint[N+1];for(inti=0;i=0;index--){sb.Append(args[index]);}returnsb.ToString();}2-11數(shù)組奇偶分離

對(duì)于一個(gè)數(shù)組，如1，2，3，4，5，6，7，8，9，0.進(jìn)行奇偶分離，之后的結(jié)果應(yīng)該是如1，3，5，7，9，2，4，6，8，0。其中奇偶部分不要求排序。

第一種方法，犧牲空間，重新建個(gè)新數(shù)組，用兩個(gè)標(biāo)量控制放的位置，代碼如下。

publicArrayarraySplit(int[]a){intsize=a.Length;//兩個(gè)標(biāo)量。inthead=0;inttail=size;//新數(shù)組，用于存放好的數(shù)據(jù)，int[]b=newint[size];//一次循環(huán)分離數(shù)組for(inti=0;ihead){if(a[tail]%2!=0){//空間復(fù)雜度為1；inttmp=a[tail];a[tail]=a[head];a[head]=tmp;}elsetail--;}}head++;}returna;}

2-12int型數(shù)組找出其中最大的k個(gè)數(shù)。

此題用一般的排序方法并不難，難的是如何不對(duì)前K個(gè)數(shù)排序，就能選出前K個(gè)最大的數(shù)。用快速排序的變形，可以達(dá)到這樣的目的代碼如下publicint[]FindTopK(int[]a,intk){if(kfor(inti=0;itmp){parta.Add(b[j]);}else{partb.Add(b[j]);}}//將哨兵放到個(gè)數(shù)少的List里。if(parta.Count

一個(gè)數(shù)組，下標(biāo)從0到n，元素為從0到n的整數(shù)，判斷是否有重復(fù)元素這個(gè)問(wèn)題其實(shí)前面2-5分析過(guò)，只不過(guò)這次一個(gè)循環(huán)搞定。代碼如下，類似哈希映射的判斷

publicboolhasDuplicate(int[]a,intsize){//輔助判斷的數(shù)組int[]array=newint[size+1];for(inti=0;i

分析：采用迭代法進(jìn)行求解

當(dāng)字符串有兩個(gè)元素ab，除了本身ab，再交換最后一位和最后二位，得到ba。當(dāng)字符串有三個(gè)元素abc時(shí)得到abc,acb,bac,bca,cba,cab。算法：用head和tail標(biāo)記字符串開(kāi)頭和結(jié)尾

1，如果開(kāi)頭和結(jié)尾相等，則輸出串，迭代終止。

2，從字符串開(kāi)頭開(kāi)始遍歷每一個(gè)字符，與開(kāi)頭字符串交換。3，對(duì)新串迭代執(zhí)行本程序，開(kāi)頭標(biāo)記加1。代碼如下

publicstaticvoidPrintStrArrange(stringstr,inthead,inttail){chartmp;//遞歸出口if(head==tail)Console.WriteLine(str);else{for(inti=head;i

2-15計(jì)算字符串的相似度

定義一套方法使兩個(gè)字符串變的相同，

（1）修改一個(gè)字符（如把”a”替換為”b”）;（2）增加一個(gè)字符(如把”abdd”替換為”aebdd”)

（3）刪除一個(gè)字符（如把”Travelling”替換為”Traveling”）

這幾種方案，都是通過(guò)一次操作就可以變成一樣的字符串，將“把兩個(gè)字符串操作為相同字符串所需的距離定義為兩個(gè)字符串的距離”距離的倒數(shù)就是2字符串的相似度。給定任意兩個(gè)字符串，如何求相似度？

思路：首先，兩個(gè)字符串的距離絕對(duì)不會(huì)大于2者長(zhǎng)度之和，還是用分治的策略，看看怎樣才能把兩個(gè)字符串變成一樣的字符串，設(shè)想兩個(gè)字符串第一個(gè)char相同，那么只需要計(jì)算A字符串的A[2,,,length]和B[2..length]就可以，如果第一個(gè)字符不同，那么可以1.刪除A的第一個(gè)字符，比較A[2…length]和B[1.length].2.刪除B的第一個(gè)字符，比較A[1.L]和B[2.L];3.修改A和B一樣，比較A[2.L]和B[2.L];4.同上。

5.增加B的第一個(gè)到A之前，比較A[1.L]和B[2.L]6.同上逆轉(zhuǎn)，比較A[2.L]和B[1.L]

歸納一下，可以按照如下操作，按照前面講述的遞歸思想，假設(shè)前面已經(jīng)變化完畢，只剩最后一步，那么需要做的事情有：

（1）一步操作之后，將A[2.L]和B[1.L]變成一樣的串（2）一步操作之后，將A[1.L]和B[2.L]變成一樣的串。（3）一步操作之后，將A[2.L]和B[2.L]變成一樣的串。選取代價(jià)最小的，為二者的距離。由此分析，程序如下，依然遞歸：publicintCanculateStringDistance(stringstrA,intpABegin,intpAEnd,stringstrB,intpBBegin,intpBEnd){//遞歸的出口。計(jì)算完了以后的判斷if(pABegin>pAEnd){if(pBBegin>pBEnd)return0;elsereturnpBEnd-pBBegin+1;}if(pBBegin>pBEnd){if(pABegin>pAEnd)return0;elsereturnpAEnd-pABegin+1;}//這個(gè)字符相等，不需要耗費(fèi)任何代價(jià)。if(strA[pABegin]==strB[pBBegin]){returnCanculateStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);}else{//3條途徑，選取代價(jià)最小的intdt1=CanculateStringDistance(strA,pABegin+2,pAEnd,strB,pBBegin+1,pBEnd);intdt2=CanculateStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin+2,pBEnd);intdt3=CanculateStringDistance(strA,pABegin+2,pAEnd,strB,pBBegin+2,pBEnd);//注意上面前提是一步操作之后，一步操作的代價(jià)是必然的，需要+1；intret=Math.Min(Math.Min(dt1,dt2),dt3)+1;returnret;}}總結(jié)

1.以上所有程序以及算法均為本人從網(wǎng)絡(luò)，書(shū)籍中收集，程序均為手寫(xiě)調(diào)試完成，供RD001內(nèi)部使用，參考，謝絕其他一切形式的擴(kuò)散，共享。

2.算法還有很多，沒(méi)有列舉到的也很多，以上的例子僅旨在向各位提供一種思路和一種解決問(wèn)題的思考方式。

3.以上部分程序經(jīng)本人運(yùn)行測(cè)試正確，其余的只是刻畫(huà)一種思路，只保證編譯可以通過(guò)，看的時(shí)候可以自己寫(xiě)完之后運(yùn)行一下，如果有錯(cuò)誤歡迎告訴我。

4.后序還會(huì)陸續(xù)更新排序和查找比較等內(nèi)容，用以完善此文檔，也歡迎各位有好的建議以及算法補(bǔ)充進(jìn)來(lái)。（尤其是復(fù)合數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，有些少的可憐）

5.一些算法是摘取自《編程之美》，還有其他很多不錯(cuò)的思想和題目，有興趣的可以多看看。

RD001孫凱201*-9-

友情提示：本文中關(guān)于《高中算法程序框圖特點(diǎn)總結(jié)》給出的范例僅供您參考拓展思維使用，高中算法程序框圖特點(diǎn)總結(jié)：該篇文章建議您自主創(chuàng)作。

來(lái)源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問(wèn)題，請(qǐng)聯(lián)系我們及時(shí)刪除。

《高中算法程序框圖特點(diǎn)總結(jié)》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請(qǐng)保留原作者信息,謝謝!
鏈接地址：http://www.7334dd.com/gongwen/587745.html

• 上一篇：高一語(yǔ)文期末教學(xué)工作總結(jié)
• 下一篇：小學(xué)語(yǔ)文教師教學(xué)工作總結(jié)12