分类目录

链接

2013年二月
« 1月   3月 »
 123
45678910
11121314151617
18192021222324
25262728  

近期文章

热门标签

博主推荐

现在位置:    首页 > .NET > 正文
用栈实现递归算法(第一版)
.NET 暂无评论 阅读(1,135)

 

学习使用,先用二叉树后序遍历写了个 斐波那契数的例子,后台陆续更新更好的算法,最新在学《算法导论》,开始有点困难,不过不急,慢慢来。。。一天,一周,一个月一个算法,弄明白了,比什么都强!!

 

这段代码没有解释,不久会更新,先看着代码哈

 

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace TEST
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             Console.Write(GetFoo(10));
  13.  
  14.             Console.Read();
  15.         }
  16.         //
  17.         static long GetFoo(int n)
  18.         {
  19.             if (IsLeaf(n))
  20.             {
  21.                 return GetLeafvalue(n);
  22.             }
  23.             //结果保存栈
  24.             Stack<long[]> resultStack = new Stack<long[]>();
  25.  
  26.             //临时结果数组
  27.             long[] tempResultArry = InitTempResultArry();
  28.  
  29.             //压入临时结果数组
  30.             resultStack.Push(tempResultArry);
  31.  
  32.             //临时节点栈
  33.             Stack<int> tempNodeStack = new Stack<int>();
  34.  
  35.             //压入根节点
  36.             tempNodeStack.Push(n);
  37.  
  38.             //遍历临时节点
  39.             while (tempNodeStack.Count > 0)
  40.             {
  41.                 tempResultArry = resultStack.Last();
  42.                 int branchIndex = GetNodeBranchIndex(tempResultArry);
  43.  
  44.                 //当前节点遍历完成
  45.                 if (branchIndex == -1)
  46.                 {
  47.                     if (resultStack.Count == 1)
  48.                     {
  49.                         break;
  50.                     }
  51.                     else
  52.                     {
  53.                         tempNodeStack.Pop();
  54.                         resultStack.Pop();
  55.                         
  56.                         //把结果赋值给上层
  57.                         //tempResultArry = resultStack.Last();
  58.  
  59.                         long tempResult = CalculateResult(tempResultArry);
  60.                         tempResultArry[1] = tempResultArry[0];
  61.                         tempResultArry[0] = tempResult;
  62.                     }
  63.                 }
  64.                 else
  65.                 {
  66.                     //没完成,得到要遍历的下一个节点
  67.                     int currentNode = tempNodeStack.First();
  68.                     int nextNode = GetSubNode(currentNode, branchIndex);
  69.  
  70.                     if (IsLeaf(nextNode))
  71.                     {
  72.                         tempResultArry[branchIndex] = GetLeafvalue(nextNode);
  73.                     }
  74.                     else
  75.                     {
  76.                         tempNodeStack.Push(nextNode);
  77.                         resultStack.Push(InitTempResultArry());
  78.                     }
  79.  
  80.                 }
  81.  
  82.  
  83.             }
  84.             return CalculateResult(resultStack.First());
  85.         }
  86.  
  87.         //
  88.         static bool IsLeaf(int n)
  89.         {
  90.             return n < 3;
  91.         }
  92.         //
  93.         static int GetNodeBranchIndex(long[] tempNodeResultArry)
  94.         {
  95.             for (int i = 0; i < tempNodeResultArry.Length; i++)
  96.             {
  97.                 if (tempNodeResultArry[i] == -1)
  98.                 {
  99.                     return i;
  100.                 }
  101.             }
  102.             return -1;//表示没有遍历完成
  103.         }
  104.  
  105.         //
  106.         static int GetSubNode(int node, int branchIndex)
  107.         {
  108.             return node - branchIndex - 1;
  109.         }
  110.         //
  111.         static long GetLeafvalue(int n)
  112.         {
  113.             return 1;
  114.         }
  115.         //
  116.         static long[] InitTempResultArry()
  117.         {
  118.             long[] tempResultArry = new long[2];
  119.             for (int i = 0; i < 2; i++)
  120.             {
  121.                 tempResultArry[i] = -1;
  122.             }
  123.             return tempResultArry;
  124.         }
  125.  
  126.         static long CalculateResult(long[] tmpResults)
  127.         {
  128.             long retValue = 0;
  129.             for (int i = 0; i < 2; i++)
  130.             {
  131.                 retValue += tmpResults[i];
  132.             }
  133.             return retValue;
  134.         }
  135.  
  136.     }
  137. }

用栈实现递归算法(第一版) - 龙歌网络 - 博客园.

本文版权归数据库之家所有,转载引用请完整注明以下信息:
本文作者:Bruce
本文地址:用栈实现递归算法(第一版) | 数据库之家