高中算法程序框图特点总结
彰显数学魅力！演绎网站传奇！程序框图疑难导悟
问题一一个程序框图包括哪几部分？具有什么特点？
(1)一个程序框图包括：
①表示相应操作的程序框，起、止框是任何程序框图不可少的，表示框图开始或结束，输入框和输出框可用在算法中任何需要输入、输出的位置，算法中间要处理数据或计算，可分别写在不同的处理框内，当算法要求你对两个不同的结果进行判断时，判断条件要写在判断框内．
②带箭头的流程线．一个程序框到另一个程序框用流程线连接．流程线不要忘记画箭头，图中它是反映流程的执行先后次序的，若不画出箭头就难以判定各框的执行顺序．
③框内必要的文字说明．(2)特点：
用框图能够清楚地展现算法的逻辑结构，具有直观、形象、容易理解的特点.问题二三种基本逻辑结构的程序框图有哪些共同特点？(1)只有一个入口；
(2)只有一个出口．请注意一个判断框有两个出口,而一个条件结构只有一个出口，不要将判断框的出口和条件结构出口混为一谈；
(3)结构内的每一部分都有机会被执行到，也就是说每一个框都应该有从入口到出口的路径通过它；
(4)结构内的循环都不存在死循环，即无终止的循环，下图就是一个死循环．
上述三种结构的共同特点，也是检查一个程序框图或算法是否正确、合理的基本方法．问题三怎样画程序框图？
画程序框图,首先应该有正确的自然语言描述的算法，然后根据算法的流程方向，使用顺序结构框图，条件结构框图、循环结构框图将算法的内容准确地表达出来,再按照算法的顺序将它们用流程线连接起来，最后加上终端框，就构成一个完整程序框图．在画程序框图时，图形框的选择要准确，选择主要的程序表达式或自然算法语言编入框图内，框图布局要恰当，方框之间连线要适当缩短.
在设计框图时，对各个程序结构一定要分清楚，如果只是执行输入、输出、计算等功能的，则使用顺序结构；如果要根据条件进行判断或者是根据情况进行讨论，那么就应该使用条件结构；如果重复地进行某一操作程序，那么就要使用循环结构．判断好各个算法语句使用的语言结构后，用相应的框图语言将对应的算法语言表达出来，主要包括以下步骤：
第一步，用自然语言表述算法步骤．
第二步，确定每一个算法步骤所包含的逻辑结构,并用相应的程序框图表示，得到该步骤的程序框图.
第三步，将所有步骤的程序框图用流程线连接起来．并加上终端框，得到表示整个算法的程序框图.
问题四怎样使用条件结构？
条件结构是程序结构中极为重要的一个逻辑结构,只有它，才具有判断、分类的功能．它的程序框图是唯一的一个有一个进入点、两个退出点的程序框图．
学数学用专页第1页共2页版权所有少智报数学专页彰显数学魅力！演绎网站传奇！条件结构的第一大功能是进行判断，在设计条件结构时，应该根据判断条件而确定所执
行的程序流向，
条件结构的第二大功能是对所遇到的情况进行分类（或分情况执行程序），要求：(1)在分类时，对所分的类别种类要清楚．不能够出现类别不清，而且一个条件结构只将情况分为两类，若有三类以以上则须用条件结构进行嵌套．
(2)在分类时必须类别明确全面，不能出现重分、漏分和乱分．问题五循环结构的计数变量与累加、累乘变量在有关累加、累乘问题的循环结构中一般都有一个计数变量和累加或累乘变量．计数变量用于记录循环次数．累加变量或累乘变量用于输出结果．计数变量和累加变量一般是同步执行的，累加或累乘一次，同时又计数一次．
累乘变量如同累加变量的设置目的一样,只不过分工不同，前者是用来计算很多项的和，后者是用来处理很多项的积．累加变量的初值一般赋值0，累乘变量的初值一般赋值1．
累加、累乘变量是为最终输出的结果服务的，通常累加变量用来处理有通项公式或递推公式的数列的前n项和,累乘变量用来处理像阶乘一样有通项公式或递推公式的数列的前n项的积.
问题六循环结构的三要素是什么？它们各自的作用是什么？
循环变量、循环体、循环终止条件是循环结构的三要素，循环结构的三要素在分析所有循环结构的算法，画出算法的框图之前就应该分析清楚，耳有准确地把握了这三个要素，才能清楚地画出循环结构的算法框图．
(1)循环变量：应明确它时初始值、步长（指循环变量每次增加的值）、终值.(2)循环体：也称循环表达式,它是算法中反复执行的部分．
(3)循环的终止条件：算法框图中用一个判断框来表示，用它判断是否继续执行循环体．
学数学用专页第2页共2页版权所有少智报数学专页
扩展阅读：程序算法总结没有密码版本
注：所有程序以及算法均为本人从网络，书籍中收集，程序均为手写调试完成，供RD001内部使用，参考，谢绝其他一切形式的扩散，共享。
应聘的环节主要包括面试和笔试，其中不免会涉及到很多算法和数据结构的问题，在这里将其先分为两大类，笔试的时候算法题为非即时算法考察，面试的时候算法题为即时算法考察。
笔试时写的算法允许有较长的思考时间，可以专注功能的实现，而暂时不管空间以及时间复杂度，面试的时候不一样，当你写出一个半吊子算法，往往面试官会让你写出一个更好的，一般也会有一些提示。面试的时候算法的提问一般不会给你很长时间，短则2分钟最长也5分钟你连思路也没有的话基本就pass了。
这里不管是不是即时考察题型，暂且归纳为一起。
AlgorithmsandDataStructures
1明确数据结构，单一进行操作1-1单一数据结构
1-1-1链表
在单数据结构（即在题目中明确提到了某种数据结构，没有掺杂，也没有背景，只是进行某些特定操作）的题型中，链表是一大类，而单链表因为其特定的存储结构和读取方法又成为考查的重点。
列举题目如下
(注：以下题目的给定Node节点全部为如下定义方式)publicclassNode{publicNodenext;publicobjectdata;}
1-1-1-1单链表的反转
给定单链表的头节点Nodehead.给出将此链表反转的方法。publicvoidReverseLinkedList(Nodehead){//首先，反转后必然head为尾部节点，将head的一份拷贝赋值给一个新的node节点，用于托管旧的链表。NodenDele=head;//等你将旧链表需要摘取的项加到新链表头部时，需要用另一个node暂时托管旧链表。NodenNext=null;//此时就将head置为了新链表的末尾了。head=null;while(nDele!=null){//这几部依次为：先存下当前节点的下一节点用于备份，之后将dele节点指向新链表的头部并且将新链表的头位置前移，同时控制每次循环都能指向后一个节点向前进行。nNext=nDele.next;nDele.next=head;head=nDele;nDele=nNext;}//至此算法完结。在这个while循环结束时候，就将原来的链表重新接在了新链表上，完成了逆转操作。}1-1-1-2链表相交
给定两个单链表，表头分别为head1和head2.判断两个链表是否相交，如果不相交返回null，如果相交，则给出相交的第一个交点。
对题目进行简单分析后不难得出，因为链表的特殊存储结构，使得其在存储结构上如果交叉则一定为“Y”型或者为“V”型，不可能为“X”型。所以相交只需求出第一个交点。
算法具体实现可以如下
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;}//相交了，这时还可以继续从参数提取俩链表首地址。else{tNode1=head1;tNode2=head2;//没有这两个赋值，他们的next都为null了。//先假设两个链表长度不一样，求出他们的长度差。intf=System.Math.Abs(lHead1-lHead2);//先判断后循环，小优化。if(lHead1>lHead2){//使长的链表将长的一部分走完，之后就能一起走到交点。当循环结束，两个链表指针到末尾的长度一样了。for(intk=0;k 给定一个单链表，头节点为nodehead.找出其倒数第N个节点。 算法思路即为给定两个Node,起初在Head节点向后走的时候，使另外一个节点node1托管这个链表的头，在Head向后走了N个节点后，node1向后遍历，在Head为Null时，node1即指向了倒数第N个节点。算法可以如下： publicNodeFindCountdownNode(Nodehead,intN){if(head==null){returnnull;}//两个托管指针。NodenTmpNode=head;NodenCountDownNode=head;//循环结束后，两个指针相差距离为Nfor(inti=0;i 删除单链表中的某节点，或者不知道头节点，这时需要保证此节点不是最后一个节点，或者即使让你知道头节点，但是不允许循环遍历。 思路即为，因为知道这个节点，不遍历，能找到的只有他下一个节点以及他本身，这样的话将他下一个节点的数据和next属性付给当前节点，并将下一节点删除即可，偷梁换柱，达到效果。 代码可以如下： publicvoidDeleOndeNode(NoderandomNode){//没有判断NodemyNext=randomNode.next;if(myNext!=null){randomNode.data=myNext.data;randomNode.next=myNext.next;myNext=null;}else{/*只有当给定head时候才可以处理末尾节点，代码为Nodecurr_node=head;while(curr_node.next!=ramdomNode){curr_node=curr_node.next;}curr_node=NULL;*/}} 1-1-1-5链表是否有环 如何判断一个链表是否有环存在。 思路为定义两个指针，即好像在操场上跑步，只要两个人速度不一样，速度快的肯定会有套速度慢的一圈的时刻。难点的还可以加上找到环的入口点，这里暂且不说。代码可以如下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;}//退出循环的条件未知，判断一下是否有环if(slowH==fastH){returntrue;}returnfalse;}1-1-1-6两个递增链表合并为递减链表 给定两个递增的链表，头节点分别为head1,head2,如何操作使之合并为一个递减的链表。 思路为经典的二路归并排序算法，建立一个新链表，开始遍历两个链表，将数值小的插入到新链表的末尾，并且将该节点原来指针向前移动一次，继续比较，大多数情况在遍历玩一个链表后，另外一个会有剩余节点，需要处理。代码可以如下publicvoidMergeSortList(Nodehead1,Nodehead2){//为了不破坏原有链表，依然设立托管指针。NodeDele1=head1;NodeDele2=head2;NodetmpNode=null;NodetmpNode2=null;Nodehead=null;//判断链表的节点，谁的data值为小的，则将其对接在新链表的末尾，并将新链表前移一位。//若两个链表值相等，则同时对接在末尾，并使dele1在前。while(Dele1!=null&&Dele2!=null){if(Dele1.data 在如下算法中所默认的二叉树节点结构均如下所示：publicclassBinTreeNode{publicobjectdata;publicBinTreeNodeLeftChildTree;publicBinTreeNodeRightChildTree;}在对二叉树的操作中，频繁的会用到递归，分治的思想。同时由于二叉树的深度优先，广度优先遍历，以及先序，中序，后序的非递归方式涉及到堆栈以及队列，故列到后面，属于复合数据结构的部分。 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左节点都是小于他的value的node节点，而root的右节点都大于root的value值，这样的话可以归纳出如下思考方法：当待寻找的两个节点node1和node2，满足node1.datahead.data){returnSearchCommonFather(node1,node2,head.RightChildTree);}elseif(node1.data 1-1-2-4二叉排序树转换为循环双向链表 思路仍然为递归，先将左子树变为LinkedList(LL),再将右子树变为LL,之后将左子树，Root，右子树变为一个整体的LL.代码可以如下#regionBST-To-DoubleSortedLinkedList//此函数用于将两个LinkedList首尾对接。publicBinTreeNodeAppendLL(BinTreeNodenode1,BinTreeNodenode2){if(node1==null)returnnode2;if(node2==null)returnnode1;//找到尾巴节点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函数。head.RightChildTree=head;head.LeftChildTree=head;//嫁接leftLL=AppendLL(leftLL,head);leftLL=AppendLL(leftLL,rightLL);returnleftLL;}#endregion1-1-2-5计算一个二叉树的叶子数目 同样的思想，总之二叉树递归就对了，注意设置递归的出口。代码如下 publicvoidCountTreeLeaf(BinTreeNodehead,refintcount){//用Out传址方式返回数目。count=0;if(head!=null){if(head.LeftChildTree==null&&head.RightChildTree==null)count++;//分别计算左右子树，计算完毕后Count即为叶子数目。CountTreeLeaf(head.LeftChildTree,refcount);CountTreeLeaf(head.RightChildTree,refcount);}}//没有带返回值，也没有调试，这样不方便是需要在调用时确定Count为0，或者可以用返回int值的。左右相加即可 1-1-2-6求二叉树叶子节点的最大距离 此为编程之美上的一道算法题，文章在最后着重说了如何控制递归的调用和退出。所谓距离，就是指两个节点之间的距离。可以想象，距离最远两个节点必然为两个叶子节点，假设根节点为K,两个最大距离的节点为U和V,那么有两种情况： （1）U和V分别在K节点的两个子树上，那么他们之间的路线必然经过K.(2)U和V在K节点的一个子树上，那么他们之间的路线必然不经过K.问题即可以转化为在子树上求最大距离的点，之后Max一下就可以了。 注：在做这个问题的时候，需要在以前的BinTreeNode重新派生一个类，其中多出来两个属性用以记录该节点左子树和右子树中的最长距离，或者直接加也可，否则无法编译通过。代码如下，参照编程之美。 intmaxlen=0;publicvoidFindMaxLen(BinTreeNodehead){//空树if(head==null)return;//一下两步用于判断左右子树是否为空，在给属性赋值完毕之后，用递归确保程序执行，而真正算距离的还没开始，也是到达叶子节点以后的反弹阶段。if(head.LeftChildTree==null){head.nMaxLeft=0;}else{FindMaxLen(head.LeftChildTree);}if(head.RightChildTree==null){head.nMaxRight=0;}else{FindMaxLen(head.RightChildTree);}//这里计算左子树的最大距离，非叶子节点都要经过这里两个逻辑中至少一个。if(head.LeftChildTree!=null){intnTempMax=0;//判断左右子树哪个更深head.LeftChildTree.nMaxLeft>head.LeftChildTree.nMaxRight?nTempMax=head.LeftChildTree.nMaxLeft:nTempMax=head.LeftChildTree.nMaxRight;//将左右子树更深的+和根节点的这条连线，作为这个子树的深度。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;//将左右子树更深的+和根节点的这条连线，作为这个子树的深度。head.RightChildTree.nMaxLeft=nTempMax+1;}//左右子树都算完了，加起来就是这个大子树的深度，需要更新一下maxlen。if(head.nMaxLeft+head.nMaxRight>maxlen){maxlen=head.nMaxLeft+head.nMaxRight;}}/*递归的分析方法：*(1)弄清递归的顺序，递归实现中，往往要假设后面的调用已经完成，即已经到最后一步了，上题即是这种情况。*(2)分析递归的逻辑，每次要有正确的变量变化，否则递归就没用了。*(3)找到递归的出口，边界条件，如不为null,大于0等等，需要设置递归的出口。*/1-1-2-7向BST中插入一个节点 BST即为(BinarySearchTree)，特点上面已经说过。 思路如下， 因为要插入的节点必然要成为暂时的叶子节点，所以必然要等到遍历到null的时候插入。所以可以按如下步骤 (1)把父节点设置为当前节点，即根节点；(2)如果新节点内的数据值小于当前节点内的数据值，那么把当前节点设置为当前节点的左子节点。如果新节点内的数据值大于当前节点内的数据值，那么就跳到步骤4； (3)如果当前节点的左子节点的数值为空（null），就把新节点插入在这里并且退出循环。否则，跳到while循环的下一次循环操作中； (4)把当前节点设置为当前节点的右子节点； (5)如果当前节点的右子节点的数值为空（null），就把新节点插入在这里并且退出循环。否则，跳到while循环的下一次循环操作中。代码如下publicvoidInsert(BinTreeNodehead,inti){BinTreeNodebtn=newBinTreeNode();btn.data=i;//如果是空树，不用插入了。if(head==null){head=btn;}//不是空树else{//移动的指针以及他的父节点指针，找到合适的节点，就可以取而代之。BinTreeNodecurrent=head;BinTreeNodeparent;//查找符合条件的位置while(true){//指针要走了，记录下现在即为其父节点。parent=current;//应该放在左子树？if(i 另外就是初始化一个二叉树，这个相对简单，只不过不断重复插入。 删除一个节点，这个比较复杂，一般会在BST结构有这种需要，需要考虑几种情况，（1）没有叶子节点，这样直接将其置为null即可，（2）有左无右，需要将左节点摘下来重新分配。（3）有右无左，同上.(4)有右有左，最复杂，不分析了。 1-2复合数据结构 单数据结构常用的就是上面两种，而堆栈，队列一般会作为组合或者与上述两种结构的组合进行考察。举例如下： 1-2-1用链表模拟堆栈和队列 详细意思就是说，用对链表的操作，模拟实现堆栈的特色操作，后进先出Push(i),Pop().以及队列的特色操作先进先出，Enqueue(i),Dequeue().代码以及注释如下 publicclassStackAndQueueWithLinkedList{//维护两个指针，这两个指针分别已经指向传进来准备操作的链表的头和尾。NodeListFirst=newNode();NodeListEnd=newNode();//在构造函数中对指针初始化。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;//更新尾部节点。ListEnd=curNode;}returntrue;}//出队列objectDequeue(){//如果为空if(ListFirst==null){throw(newException("LinkedListisnull"));}//出队以后的数据intdata=ListFirst.data;//如果就此一个节点，删除之后，First和End都应该为nullif(ListFirst.next==null){ListEnd=null;}//更新开始节点。ListFirst=ListFirst.next;returndata;}//进堆栈,和进队列一样的，都是加到末尾。boolpush(inti){//装箱NodecurNode=newNode();curNode.data=i;//如果是空的。if(ListEnd==null){ListFirst=curNode;ListEnd=curNode;}//不为空，加到末尾。else{ListEnd.next=curNode;//更新尾部节点。ListEnd=curNode;}returntrue;}//出堆栈objectpop(){if(ListFirst==null)thrownewException("LinkedListisnull");//道理同上if(ListFirst.next==null){ListEnd=null;}//以下三行更新End节点NodepreNode=FindPreviousOfLast();intdata=preNode.data;ListEnd=preNode;returndata;}//和找倒数第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树的先序，中序，后序遍历（非递归） 在单一数据结构的操作中有很简单的用递归操作树的遍历，3句话就可以把树的先序，后序，中序遍历表示出来，如果不用递归的话，为保证可以顺利回溯，则需要用临时的数据结构来存储遍历过程中的点，堆栈是一个好的选择。代码如下：publicvoidPreOrderWithOutRecursive(BinTreeNodehead){Stackmystack=newStack();//在遍历一个root节点以后，要把它压栈，以便以后能按顺序返回各自的右节点。while(head!=null||mystack.Count!=0){//输出自己和左子树。while(head!=null){Console.WriteLine(head.data.ToString());mystack.Push(head);head=head.LeftChildTree;}//将自己的右子树返回来，继续向下循环。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;}}}/*后序遍历的难点在于需要知道某节点的右子树是否已经遍历过，*我自己没写出来，参考网上的算法，主要有两种，一种是在Node节点加一个属性为tag,初始值为false,标志该节点*的右子树是否已经被遍历过，一种是通过判断记上一次访问的节点是否和现在节点的右子树节点相等。*///基于第一种加一个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;//第二次访问时候标志其右子树也已经被遍历。}//不能访问，那么继续向右找，还有没遍历的。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());}//左右子树尚未入栈，需要一次压入右，左，中节点。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);//当前节点无右子树，或者子树已经输出while(head!=null&&(head.RightChildTree!=null||head.RightChildTree==tmp)){Console.WriteLine(head.data.ToString());tmp=head;if(mystack.Count==0)return;head=mystack.Pop();}//处理右节点mystack.Push(head);head=head.RightChildTree;}}1-2-3树的广度优先遍历。 深度优先和广度优先是对于二叉树最基本的两个算法，事实上，先中后序遍历都是深度优先遍历的特例，设L、D、R分别代表遍历左子树、访问根结点和遍历右子树，则有DLR(先序)、LDR(中序)、LRD(后序)、DRL、RDL、RLD六种不同的二叉树深度遍历方案。上面已经写了那么多了，深度优先就不写了，其余的就不写了。 而主要写广度优先，广度优先就是对树分层，也叫层次遍历这样的话用队列存储比较好。代码如下publicvoidLevelTravel(BinTreeNodehead){if(head==null)return;QueuemyQue=newQueue();myQue.Enqueue(head);//为实现广度优先，一般不能用递归，一定是一边入队一边出队，而终止条件就是队列为空while(myQue.Count!=0){BinTreeNodetmpNode=myQue.Dequeue();Console.WriteLine(tmpNode.data.ToString());//节点自己出了队列，将自己的左右孩子入到队列末端。if(tmpNode.LeftChildTree!=null){myQue.Enqueue(tmpNode.LeftChildTree);}if(tmpNode.RightChildTree!=null){myQue.Enqueue(tmpNode.RightChildTree);}}}2数据结构不明确，偏向考察算法2-1对于M的阶乘，末尾有多少个0？ 题目分析：对于乘法，只能有2和5相乘才可以产生0，而且2与5的倍数相乘也可以得0.在一个随机连续的范围内，偶数与5的倍数的个数相比，偶数总是多于5的倍数，那么这样的话，相乘得到0的个数的瓶颈则可以确定在于5的个数.由此，问题则归结为，求1-M中5的出现个数，换句话说，就是有多少个数一共能贡献多少个5（例，5的贡献度为一个5，25贡献度为2个5，50也是2个5.以此类推）。可以得到解题程序如下： publicintfindZeroCount(intm){//小于5就算了。if(mfor(inti=1;i1;i--){index=r.Next(1,i);//放入数组，倒着放的。myArr[i-2]=tmpList[index];//这句是关键。也可以自己实现。tmpList.RemoveAt(index);}returnmyArr;}2-3斐波那契数列求第N项。 斐波那契数列则是如下这样的数列：{1,1,2,3,5,8……..}递归的教科书教材例子，不过也经常问到。程序如下 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 数组为整型。具体就是找到相同的就把相同两个中的前一个Cover掉。先写一个最容易想的，特别傻的方法。程序如下，时间复杂度为N^2. publicvoidremoveDuplicate(int[]a){intsize=a.Length;intcount=0;inti,j;//类似冒泡了。很慢for(i=0;i 此题思路和上一个题的第二种解法类似，只不过可以不用indexof，用一个正规点的，HashTable.publicstaticint[]GetUnion(int[]arr1,int[]arr2){Listlist=newList();System.Collections.Hashtableht=newSystem.Collections.Hashtable();//遍历第一个数组，有的元素都标上记号。for(inti=0;i 思路如下：学过二进制都知道，将一个数除以2的过程，事实上就是对其进行右移位一次的过程，用10100010为例，第一次除以2，商为1010001，余0，所以为偶数。再除以2，商为101000，余1，所以为奇数。如此反复。于是可以有如下解法求出一个数的二进制表示中1的个数代码1：publicintgetOneDigCount(intm){intcount=0;while(m>0){//如果能被2整除if(m%2==1){count++;}m=m/2;}returncount;}或者可以考虑用位操作符，因为即使你写的每次/2，在计算机中，也是如此操作的，把这个过程写下来，可以节省很多的执行时间，而如何判断最后一位是不是1则成了关键，可以用当前数与0x01进行“与”操作。如果结果为1则最后一位是1.代码如下publicintgetOneCount(intm){intcount=0;while(m>0){//与操作count+=m&0x01;//右移一位的操作m>>=1;}returncount;}2-8按顺序输出矩阵中的数字： 思路：因为矩阵输出有方向的变化，故采用一个bool型变量控制输出方向。程序应该还有改进空间，如下publicstaticvoidprintArrayInrule(){//矩阵为4×4的，这两个也可作为参数接收。constintlength=16;constintwidth=4;//计数器，控制矩阵范围内intindex=0;//具体每一列输出的数值intstartI=1;//多少个转变一次方向intmyPoint=1;//true为向下，false为向上boolDirection=true;while(index int型数组，N个，求出其中和为N+1的数队。复杂度为O（n）为（n^2）则不得分我想的是先对数组排序，快排，复杂度为（nlogn），然后再用两个指针head,tail,标识，如果head+tail=N+1则计数器+1，如果head+tailN+1则tail--.如此找到所有数对。 而上网查的是用一个HashTable来标记，复杂度为O(N)，但是哈希表不用.NET内置的，自己模拟一个，代码如下： publicstaticintgetSumCount(int[]array,intN){intcount=0;//创建哈希表int[]hashTable=newint[N+1];for(inti=0;i=0;index--){sb.Append(args[index]);}returnsb.ToString();}2-11数组奇偶分离 对于一个数组，如1，2，3，4，5，6，7，8，9，0.进行奇偶分离，之后的结果应该是如1，3，5，7，9，2，4，6，8，0。其中奇偶部分不要求排序。 第一种方法，牺牲空间，重新建个新数组，用两个标量控制放的位置，代码如下。 publicArrayarraySplit(int[]a){intsize=a.Length;//两个标量。inthead=0;inttail=size;//新数组，用于存放好的数据，int[]b=newint[size];//一次循环分离数组for(inti=0;i 2-12int型数组找出其中最大的k个数。 此题用一般的排序方法并不难，难的是如何不对前K个数排序，就能选出前K个最大的数。用快速排序的变形，可以达到这样的目的代码如下publicint[]FindTopK(int[]a,intk){if(kfor(inti=0;i 一个数组，下标从0到n，元素为从0到n的整数，判断是否有重复元素这个问题其实前面2-5分析过，只不过这次一个循环搞定。代码如下，类似哈希映射的判断 publicboolhasDuplicate(int[]a,intsize){//辅助判断的数组int[]array=newint[size+1];for(inti=0;i 分析：采用迭代法进行求解 当字符串有两个元素ab，除了本身ab，再交换最后一位和最后二位，得到ba。当字符串有三个元素abc时得到abc,acb,bac,bca,cba,cab。算法：用head和tail标记字符串开头和结尾 1，如果开头和结尾相等，则输出串，迭代终止。 2，从字符串开头开始遍历每一个字符，与开头字符串交换。3，对新串迭代执行本程序，开头标记加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”） 这几种方案，都是通过一次操作就可以变成一样的字符串，将“把两个字符串操作为相同字符串所需的距离定义为两个字符串的距离”距离的倒数就是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] 归纳一下，可以按照如下操作，按照前面讲述的递归思想，假设前面已经变化完毕，只剩最后一步，那么需要做的事情有： （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.以上所有程序以及算法均为本人从网络，书籍中收集，程序均为手写调试完成，供RD001内部使用，参考，谢绝其他一切形式的扩散，共享。 2.算法还有很多，没有列举到的也很多，以上的例子仅旨在向各位提供一种思路和一种解决问题的思考方式。 3.以上部分程序经本人运行测试正确，其余的只是刻画一种思路，只保证编译可以通过，看的时候可以自己写完之后运行一下，如果有错误欢迎告诉我。 4.后序还会陆续更新排序和查找比较等内容，用以完善此文档，也欢迎各位有好的建议以及算法补充进来。（尤其是复合数据结构的内容，有些少的可怜） 5.一些算法是摘取自《编程之美》，还有其他很多不错的思想和题目，有兴趣的可以多看看。 RD001孙凯201*-9- 友情提示：本文中关于《高中算法程序框图特点总结》给出的范例仅供您参考拓展思维使用，高中算法程序框图特点总结：该篇文章建议您自主创作。 来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
《高中算法程序框图特点总结》由互联网用户整理提供,转载分享请保留原作者信息,谢谢!
链接地址：http://www.bsmz.net/gongwen/587745.html
公文素材库友情提示：本网站所有内容为共享上传提供，不涉及任何商业利益，本站对此不承担任何保证责任！
Copyright © www.bsmz.net Corporation, All Rights Reserved 共享时代 共享你我他 版权所有