高中算法程序框圖特點總結

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

問題一一個程序框圖包括哪幾部分？具有什么特點？

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

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

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

③框內必要的文字說明．(2)特點：

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

(2)只有一個出口．請注意一個判斷框有兩個出口,而一個條件結構只有一個出口，不要將判斷框的出口和條件結構出口混為一談；

(3)結構內的每一部分都有機會被執(zhí)行到，也就是說每一個框都應該有從入口到出口的路徑通過它；

(4)結構內的循環(huán)都不存在死循環(huán)，即無終止的循環(huán)，下圖就是一個死循環(huán)．

上述三種結構的共同特點，也是檢查一個程序框圖或算法是否正確、合理的基本方法．問題三怎樣畫程序框圖？

畫程序框圖,首先應該有正確的自然語言描述的算法，然后根據(jù)算法的流程方向，使用順序結構框圖，條件結構框圖、循環(huán)結構框圖將算法的內容準確地表達出來,再按照算法的順序將它們用流程線連接起來，最后加上終端框，就構成一個完整程序框圖．在畫程序框圖時，圖形框的選擇要準確，選擇主要的程序表達式或自然算法語言編入框圖內，框圖布局要恰當，方框之間連線要適當縮短.

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

第一步，用自然語言表述算法步驟．

第二步，確定每一個算法步驟所包含的邏輯結構,并用相應的程序框圖表示，得到該步驟的程序框圖.

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

問題四怎樣使用條件結構？

條件結構是程序結構中極為重要的一個邏輯結構,只有它，才具有判斷、分類的功能．它的程序框圖是唯一的一個有一個進入點、兩個退出點的程序框圖．

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

行的程序流向，

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

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

累乘變量如同累加變量的設置目的一樣,只不過分工不同，前者是用來計算很多項的和，后者是用來處理很多項的積．累加變量的初值一般賦值0，累乘變量的初值一般賦值1．

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

問題六循環(huán)結構的三要素是什么？它們各自的作用是什么？

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

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

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

學數(shù)學用專頁第2頁共2頁版權所有少智報數(shù)學專頁

擴展閱讀：程序算法總結沒有密碼版本

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

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

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

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

AlgorithmsandDataStructures

1明確數(shù)據(jù)結構，單一進行操作1-1單一數(shù)據(jù)結構

1-1-1鏈表

在單數(shù)據(jù)結構（即在題目中明確提到了某種數(shù)據(jù)結構，沒有摻雜，也沒有背景，只是進行某些特定操作）的題型中，鏈表是一大類，而單鏈表因為其特定的存儲結構和讀取方法又成為考查的重點。

列舉題目如下

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

1-1-1-1單鏈表的反轉

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

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

對題目進行簡單分析后不難得出，因為鏈表的特殊存儲結構，使得其在存儲結構上如果交叉則一定為“Y”型或者為“V”型，不可能為“X”型。所以相交只需求出第一個交點。

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

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

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

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

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

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

思路即為，因為知道這個節(jié)點，不遍歷，能找到的只有他下一個節(jié)點以及他本身，這樣的話將他下一個節(jié)點的數(shù)據(jù)和next屬性付給當前節(jié)點，并將下一節(jié)點刪除即可，偷梁換柱，達到效果。

代碼可以如下：

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

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

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

思路為定義兩個指針，即好像在操場上跑步，只要兩個人速度不一樣，速度快的肯定會有套速度慢的一圈的時刻。難點的還可以加上找到環(huán)的入口點，這里暫且不說。代碼可以如下publicboolIsExistLoop(NodeHead){if(Head==null||Head.next==null){returnfalse;}if(Head.next==Head){returntrue;}NodeslowH=Head;NodefastH=Head.next;//兩個指針開始追逐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兩個遞增鏈表合并為遞減鏈表

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

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

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

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

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

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求二叉樹的深度

同樣用遞歸，算法如下

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求二叉（排序）樹的最近公共祖先

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

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

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

同樣的思想，總之二叉樹遞歸就對了，注意設置遞歸的出口。代碼如下

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

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

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

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

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

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

BST即為(BinarySearchTree)，特點上面已經(jīng)說過。

思路如下，

因為要插入的節(jié)點必然要成為暫時的葉子節(jié)點，所以必然要等到遍歷到null的時候插入。所以可以按如下步驟

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

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

(4)把當前節(jié)點設置為當前節(jié)點的右子節(jié)點；

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

另外就是初始化一個二叉樹，這個相對簡單，只不過不斷重復插入。

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

1-2復合數(shù)據(jù)結構

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

1-2-1用鏈表模擬堆棧和隊列

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

publicclassStackAndQueueWithLinkedList{//維護兩個指針，這兩個指針分別已經(jīng)指向傳進來準備操作的鏈表的頭和尾。NodeListFirst=newNode();NodeListEnd=newNode();//在構造函數(shù)中對指針初始化。publicStackAndQueueWithLinkedList(NodeHead){ListFirst=Head;ListEnd=GetTail(Head);}//得到最后一個node.privateNodeGetTail(NodeHead){if(Head==null)returnnull;Nodetemp=Head;while(temp!=null){temp=temp.next;}returntemp;}//進隊列，加到末尾。boolEnqueue(inti){//裝箱NodecurNode=newNode();curNode.data=i;//如果是空的。if(ListEnd==null){ListFirst=curNode;ListEnd=curNode;}//不為空，加到末尾。else{ListEnd.next=curNode;//更新尾部節(jié)點。ListEnd=curNode;}returntrue;}//出隊列objectDequeue(){//如果為空if(ListFirst==null){throw(newException("LinkedListisnull"));}//出隊以后的數(shù)據(jù)intdata=ListFirst.data;//如果就此一個節(jié)點，刪除之后，F(xiàn)irst和End都應該為nullif(ListFirst.next==null){ListEnd=null;}//更新開始節(jié)點。ListFirst=ListFirst.next;returndata;}//進堆棧,和進隊列一樣的，都是加到末尾。boolpush(inti){//裝箱NodecurNode=newNode();curNode.data=i;//如果是空的。if(ListEnd==null){ListFirst=curNode;ListEnd=curNode;}//不為空，加到末尾。else{ListEnd.next=curNode;//更新尾部節(jié)點。ListEnd=curNode;}returntrue;}//出堆棧objectpop(){if(ListFirst==null)thrownewException("LinkedListisnull");//道理同上if(ListFirst.next==null){ListEnd=null;}//以下三行更新End節(jié)點NodepreNode=FindPreviousOfLast();intdata=preNode.data;ListEnd=preNode;returndata;}//和找倒數(shù)第N個的思路一樣。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ù)據(jù)結構的操作中有很簡單的用遞歸操作樹的遍歷，3句話就可以把樹的先序，后序，中序遍歷表示出來，如果不用遞歸的話，為保證可以順利回溯，則需要用臨時的數(shù)據(jù)結構來存儲遍歷過程中的點，堆棧是一個好的選擇。代碼如下：publicvoidPreOrderWithOutRecursive(BinTreeNodehead){Stackmystack=newStack();//在遍歷一個root節(jié)點以后，要把它壓棧，以便以后能按順序返回各自的右節(jié)點。while(head!=null||mystack.Count!=0){//輸出自己和左子樹。while(head!=null){Console.WriteLine(head.data.ToString());mystack.Push(head);head=head.LeftChildTree;}//將自己的右子樹返回來，繼續(xù)向下循環(huán)。if(mystack.Count!=0){BinTreeNodetmpRoot=mystack.Pop();head=tmpRoot.RightChildTree;}}}publicvoidMidOrderWithOutRecursive(BinTreeNodehead){Stackmystack=newStack();//同上，壓棧處理，不同的是，不能馬上輸出自己，只能等到pop到自己的時候再輸出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;}}}/*后序遍歷的難點在于需要知道某節(jié)點的右子樹是否已經(jīng)遍歷過，*我自己沒寫出來，參考網(wǎng)上的算法，主要有兩種，一種是在Node節(jié)點加一個屬性為tag,初始值為false,標志該節(jié)點*的右子樹是否已經(jīng)被遍歷過，一種是通過判斷記上一次訪問的節(jié)點是否和現(xiàn)在節(jié)點的右子樹節(jié)點相等。*///基于第一種加一個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)//可以訪問{Console.WriteLine(head.data.ToString());mystack.Pop();head=null;//第二次訪問時候標志其右子樹也已經(jīng)被遍歷。}//不能訪問，那么繼續(xù)向右找，還有沒遍歷的。else{head.tag=true;head=head.RightChildTree;}}}}//結構更清晰的一個算法，代碼如下publicvoidPostOrderWithOutRecursive2(BinTreeNodehead){Stackmystack=newStack();if(head!=null){mystack.Push(head);}while(mystack.Count!=0){BinTreeNodebtn=mystack.Pop();//左右子樹都已入棧if(btn.tag){Console.WriteLine(btn.data.ToString());}//左右子樹尚未入棧，需要一次壓入右，左，中節(jié)點。else{if(btn.RightChildTree!=null){btn.RightChildTree.tag=false;//控制其左右子樹都為false.mystack.Push(btn.RightChildTree);}if(btn.LeftChildTree!=null){btn.LeftChildTree.tag=false;//false.mystack.Push(btn.LeftChildTree);}btn.tag=true;mystack.Push(btn);}}}//至于不用標志位的一個算法，更難一些。也更麻煩一些。如下publicvoidPostOrderWithOutRecursive3(BinTreeNodehead){//先把當前的head做一個備份BinTreeNodetmp=head;Stackmystack=newStack();while(head!=null){//左子樹全部入棧，老方法。for(;head.LeftChildTree!=null;head=head.LeftChildTree)mystack.Push(head);//當前節(jié)點無右子樹，或者子樹已經(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é)點mystack.Push(head);head=head.RightChildTree;}}1-2-3樹的廣度優(yōu)先遍歷。

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

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

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

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

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

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

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

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

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

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

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

思路：因為矩陣輸出有方向的變化，故采用一個bool型變量控制輸出方向。程序應該還有改進空間，如下publicstaticvoidprintArrayInrule(){//矩陣為4×4的，這兩個也可作為參數(shù)接收。constintlength=16;constintwidth=4;//計數(shù)器，控制矩陣范圍內intindex=0;//具體每一列輸出的數(shù)值intstartI=1;//多少個轉變一次方向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給定一個數(shù)組為N個元素集合

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

而上網(wǎng)查的是用一個HashTable來標記，復雜度為O(N)，但是哈希表不用.NET內置的，自己模擬一個，代碼如下：

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ù)組奇偶分離

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

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

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

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

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

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

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

分析：采用迭代法進行求解

當字符串有兩個元素ab，除了本身ab，再交換最后一位和最后二位，得到ba。當字符串有三個元素abc時得到abc,acb,bac,bca,cba,cab。算法：用head和tail標記字符串開頭和結尾

1，如果開頭和結尾相等，則輸出串，迭代終止。

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

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

2-15計算字符串的相似度

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

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

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

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

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

5.增加B的第一個到A之前，比較A[1.L]和B[2.L]6.同上逆轉，比較A[2.L]和B[1.L]

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

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

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

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

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

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

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

RD001孫凱201*-9-

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

來源：網(wǎng)絡整理 免責聲明：本文僅限學習分享，如產(chǎn)生版權問題，請聯(lián)系我們及時刪除。

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

• 上一篇：高一語文期末教學工作總結
• 下一篇：小學語文教師教學工作總結12