• C# 递归算法!

    2008-01-22 02:41:00
    突然之间发现递归算法很好。 首先碰到的是这样的一首题目:计算数组{1,1,2,3,5,8.......} 第30位值,不用递归,我写出了以下这样的代码: static void Main(string[] args) ...{ int[] num=ne

              今天无所事事,于是重温了一下递归算法。突然之间发现递归算法很好用。

               首先碰到的是这样的一首题目:计算数组{1,1,2,3,5,8.......} 第30位值,不用递归,我写出了以下这样的代码:

     

            static void Main(string[] args)
            
    {


                
    int[] num=new int[30];
                num[
    0]=1;
                num[
    1]=1;
                
    int first=num[0];
                
    int second=num[1];
                
    for (int i = 2; i < num.Length; i++)
                
    {
                    num[i] 
    = first + second;
                    first 
    = second;
                    second 
    = num[i];
                }

                Console.WriteLine(num[
    29]);
                Console.ReadLine();

             

            }

     写出来,十分的累赘,于是改为归递算法来写,一目了然,十分明了。以下是代码:

     

            static void Main(string[] args)
            
    {

                Console.WriteLine(Process1(
    30));
                Console.ReadLine();        
            }

            
    public static int Process1(int i)
            
    {




                
    //计算数组{1,1,2,3,5,8.......} 第30位值
                if (i == 0return 0;
                
    if (i == 1return 1;
                
    else
                    
    return Process1(i - 1+ Process1(i - 2);
            }

    做了一些练习:

    1. 计算1+2+3+4+...+100的值

     

            static void Main(string[] args)
            
    {
                Console.WriteLine(Process2(
    100));
                Console.ReadLine();    
            }

            
    public static int Process2(int i)
            
    {
                
    //计算1+2+3+4+...+100的值
                if (i == 0return 0;
                
    return Process2(i - 1+ i;

            }

    2. 计算1 -2 +3 +-4+ 5- 6 + 7 - 8 + 9的值

     

            static void Main(string[] args)
            
    {

                Console.WriteLine(Process3(
    9- Process3(8));
                Console.ReadLine();  
            }


            
    public static int Process3(int i)
            
    {
                
    //计算1 -2 +3 +-4+ 5- 6 + 7 - 8 + 9的值
                if (i == 0return 1;
                
    if (i == 1return 2;
                
    else return Process3(i - 2+ i;
            }

    3.汉诺塔问题

     

            static void Main(string[] args)
            
    {
                Hanoi(
    5'A''B''C');
                Console.ReadLine();
            }

            
    public static void Hanoi(int n ,char A, char B, char C)
            
    {
                
    //汉诺塔问题
                
    //将n个盘子从A座借助B座,移到C座
                if (n == 1) Move(A, C);
                
    else
                
    {
                    Hanoi(n 
    - 1, A, C, B);
                    Move(A, C);
                    Hanoi(n 
    - 1, B, A, C);
                }


            }

            
    public static void Move(char startPlace, char endPlace)
            
    {
                Console.WriteLine(
    "Move {0} To {1}",startPlace,endPlace);
            }

    4.用递归法将一个整数n转换成字符串,例如,输入483,就输出字符串"483".n的位数不确定,可以是任意位数的整数。

     

            static void Main(string[] args)
            
    {
                IntToString(
    483"");
                Console.ReadLine();
            }

            
    public static void IntToString(int input,String output)
            
    {
             
    //用递归法将一个整数n转换成字符串,例如,输入483,就输出字符串"483".n的位数不确定,可以是任意位数的整数。
             
    //   String output = "";
                output = input % 10+output;
                
    if (input / 10 != 0)
                
    {
                    IntToString(input 
    / 10,output);
                }

                
    else Console.WriteLine(output);
            }

     

      add by inkstone  @2008年01月22日        

    展开全文
  • 用C#实现递归方法

    2019-05-07 00:37:51
    什么是递归函数/方法? 任何一个方法既可以调用其他方法也可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或递归方法。 通常递归有两个特点: 1. 递归方法一直会调用自己直到...以前C#中只有方法,从.NE...

    什么是递归函数/方法?

    任何一个方法既可以调用其他方法也可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或递归方法。

    通常递归有两个特点:

    1. 递归方法一直会调用自己直到某些条件被满足

    2. 递归方法会有一些参数,而它会把一些新的参数值传递给自己。

    那什么是递归函数?函数和方法没有本质区别,但函数仅在类的内部使用。以前C#中只有方法,从.NET 3.5开始才有了匿名函数。

    所以,我们最好叫递归方法,而非递归函数,本文中将统一称之为递归。

     

    在应用程序中为什么要使用递归?何时使用递归?如何用?

    “写任何一个程序可以用赋值和if-then-else语句表示出来,而while语句则可以用赋值、if-then-else和递归表示出来。”(出自Ellis Horowitz的《数据结构基础(C语言版)》 - Fundamentals of Data Structure in C)

    递归解决方案对于复杂的开发来说很方便,而且十分强大,但由于频繁使用调用栈(call stack)可能会引起性能问题(有些时候性能极差)。

    我们来看一看下面这个图:

    Proj0

    调用栈图示

    下面我打算介绍一些例子来帮助你更好的理解递归的风险和回报。

    1. 阶乘

    阶乘(!)是小于某个数的所有正整数的乘积。

    0! = 1 
    1! = 1 
    2! = 2 * 1! = 2 
    3! = 3 * 2! = 6 
    ... 
    n! = n * (n - 1)!

    下面是计算阶乘的一种实现方法(没有递归):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public long Factorial(int n)
    {
        if (n == 0)
            return 1;
        long value = 1;
        for (int i = n; i > 0; i--)
        {
            value *= i;
        }
        return value;
    }

    下面是用递归的方法实现计算阶乘,与之前的代码比起来它更简洁。

    1
    2
    3
    4
    5
    6
    public long Factorial(int n)
    {
        if (n == 0)//限制条件,对该方法调用自己做了限制
            return 1;
        return n * Factorial(n - 1);
    }

    你知道的,n的阶乘实际上是n-1的阶乘乘以n,且n>0。

    它可以表示成 Factorial(n) = Factorial(n-1) * n

    这是方法的返回值,但我们需要一个条件

    如果 n=0 返回1。

    现在这个程式的逻辑应该很清楚了,这样我们就能够轻易的理解。

    2. Fibonacci数列

    Fibonacci数列是按以下顺序排列的数字:

    0,1,1,2,3,5,8,13,21,34,55,…

    如果F0 = 0 并且 F1= 1 那么Fn = Fn-1 + Fn-2

    下面的方法就是用来计算Fn的(没有递归,性能好)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public long Fib(int n)
    {
        if (n < 2)
            return n;
        long[] f = new long[n+1];
        f[0] = 0;
        f[1] = 1;
         
        for (int i = 2; i <= n; i++)
        {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }

    如果我们使用递归方法,这个代码将更加简单,但性能很差。

    1
    2
    3
    4
    5
    6
    7
    public long Fib(int n)
    {
        if (n == 0 || n == 1) //满足条件
            return n;
        return Fib(k - 2) + Fib(k - 1);
    }
    <strong><span style="font-size: medium">3. 布尔组合</span></strong>
    1
    有时我们需要解决的问题比Fibonacci数列复杂很多,例如我们要枚举所有的布尔变量的组合。换句话说,如果n=3,那么我们必须输出如下结果:
    true, true, true
    true, true, false
    true, false, true
    true, false, false
    false, true, true
    false, true, false
    false, false, true
    false, false, false

    如果n很大,且不用递归是很难解决这个问题的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public void CompositionBooleans(string result, int counter)
    {
        if (counter == 0)
            return;
     
        bool[] booleans = new bool[2] { truefalse };
     
        for (int j = 0; j < 2; j++)
        {
            StringBuilder stringBuilder = new StringBuilder(result);
            stringBuilder.Append(string.Format("{0} ", booleans[j].ToString())).ToString();
     
            if (counter == 1)
                Console.WriteLine(stringBuilder.ToString());
     
            CompositionBooleans(stringBuilder.ToString(), counter - 1);
        }
    }

    现在让我们来调用上面这个方法:

    1
    CompositionBoolean(string.Empty, 3);

    Ian Shlasko建议我们这样使用递归:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public void BooleanCompositions(int count)
    {
      BooleanCompositions(count - 1, "true");
      BooleanCompositions(count - 1, "false");
    }
     
    private void BooleanCompositions(int counter, string partialOutput)
    {
      if (counter <= 0)
        Console.WriteLine(partialOutput);
      else
      {
        BooleanCompositions(counter - 1, partialOutput+ ", true");
        BooleanCompositions(counter - 1, partialOutput+ ", false");
      }
    }

    4. 获取内部异常

    如果你想获得innerException,那就选择递归方法吧,它很有用。

    1
    2
    3
    4
    public Exception GetInnerException(Exception ex)
    {
        return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);
    }

    为什么要获得最后一个innerException呢?!这不是本文的主题,我们的主题是如果你想获得最里面的innerException,你可以靠递归方法来完成。

    这里的代码:

    1
    return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);

    与下面的代码等价

    1
    2
    3
    if (ex.InnerException == null)//限制条件
       return ex;
    return GetInnerException(ex.InnerException);//用内部异常作为参数调用自己

    现在,一旦我们获得了一个异常,我们就能找到最里面的innerException。例如:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    try
    {
        throw new Exception("This is the exception",
            new Exception("This is the first inner exception.",
                new Exception("This is the last inner exception.")));
    }
    catch (Exception ex)
    {
        Console.WriteLine(GetInnerException(ex).Message);
    }

    我曾经想写关于匿名递归方法的文章,但是我发觉我的解释无法超越那篇文章

    5. 查找文件

    Proj1

    我在供你下载的示范项目中使用了递归,通过这个项目你可以搜索某个路径,并获得当前文件夹和其子文件夹中所有文件的路径。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    private Dictionary<stringstring> errors = new Dictionary<stringstring>();
    private List<string> result = new List<string>();
     
    private void SearchForFiles(string path)
    {
       try
       {
          foreach (string fileName in Directory.GetFiles(path))//Gets all files in the current path
          {
              result.Add(fileName);
          }
     
          foreach (string directory in Directory.GetDirectories(path))//Gets all folders in the current path
          {
             SearchForFiles(directory);//The methods calls itself with a new parameter, here!
          }
       }
       catch (System.Exception ex)
       {
          errors.Add(path, ex.Message);//Stores Error Messages in a dictionary with path in key
       }
    }

    这个方法似乎不需要满足任何条件,因为每个目录如果没有子目录,会自动遍历所有子文件。

     

    总结

    我们其实可以用递推算法来替代递归,且性能会更好些,但我们可能需要更多的时间开销和非递归函数。但关键是我们必须根据场景选择最佳实现方式。

    James MaCaffrey博士认为尽量不要使用递归,除非实在没有办法。你可以读一下他的文章

    我认为:

    A) 如果性能是非常重要的,请避免使用递归

    B)如果递推方式不是很复杂的,请避免使用递归

    C) 如果A和B都不满足,请不要犹豫,用递归吧。

    例如:

    第一节(阶乘):这里用递推并不复杂,那么就避免用递归。

    第二节(Fibonacci):像这样的递归并不被推荐。

    当然,我并不是要贬低递归的价值,我记得人工智能中的重要一章有个极小化极大算法(Minimax algorithm),全部是用递归实现的。

    但是如果你决定使用队规方法,你最好尝试用存储来优化它。










    本文转自 瞿杰 51CTO博客,原文链接:http://blog.51cto.com/tonyqus/1154618,如需转载请自行联系原作者
    展开全文
  • C#实现(递归和非递归)快速排序和简单排序 本人因为最近工作用到了一些排序算法,就把几个简单的排序算法,想冒泡排序,选择排序,插入排序,奇偶排序和快速排序等整理了出来,代码用C#代码实现,并且通过了测试...

    C#实现(递归和非递归)快速排序和简单排序

         本人因为最近工作用到了一些排序算法,就把几个简单的排序算法,想冒泡排序,选择排序,插入排序,奇偶排序和快速排序等整理了出来,代码用C#代码实现,并且通过了测试。希望能给大家提供参考。

        1.冒泡排序

           冒泡排序,是指计算机的一种排序算法,它的时间复杂度是O(n^2),虽然不及堆排序和快速排序时间复杂度为O(nlogn,底数为2),但是有两个优点:1:编程复杂度低,很容易实现;2 是具有稳定性,这里的稳定性是指源序列中相同元素的相对顺序仍然保持到排序后的顺序,而堆排序和快速排序都不具有稳定性。

         基本概念

             冒泡排序(BubbleSort)的基本概念:依次比较相邻两个数,小的在前,大的在后。在第一趟,首先比较第1个数和第2个数,小的放在前面,大的放在后面,然后比较第2个数和第3个数,小的在前,大的在后,如此继续,直到比较最后两个数,小的在前,大的在后,第一趟结束时,就把最大的数放在了最后。在第二趟,仍从第一对数开始比较(因为由于第2个数和第3个数的交换,使第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一个数已经是最大的),第二趟结束,这样在倒数第二个位置得到一个新的最大数,如此循环下去,重复以上过程,直至最终完成排序。

    比如有一个数列10, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76

    第一次排序后:10,2,4,33,6,12,34,55,66,43,23,65,1,345,61,76,31,43,76,456

    第二次排序后:2,4,10,6,12,33,34,55,43,23,65,1,66,61,76,31,43,76,345,456

    第三次排序后:2,4,6,10,12,33,34,43,23,55,1,65,61,66,31,43,76,76,345,456

    第四次排序后:2,4,6,10,12,33,34,23,43,1,55,61,65,31,43,66,76,76,345,456

    第五次排序后: 2,4,6,10,12,33,23,34,1,43,55,61,31,43,65,66,76,76,345,456

    第六次排序后: 2,4,6,10,12,23,33,1,34,43,55,31,43,61,65,66,76,76,345,456

    第七次排序后: 2,4,6,10,12,23,1,33,34,43,31,43,55,61,65,66,76,76,345,456

    第八次排序后: 2,4,6,10,12,1,23,33,34,31,43,43,55,61,65,66,76,76,345,456

    第九次排序后: 2,4,6,10,1,12,23,33,31,34,43,43,55,61,65,66,76,76,345,456

    第十次排序后: 2,4,6,1,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

    第十一次排序后:2,4,1,6,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

    第十二次排序后:2,1,4,6,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

    第十三次排序后: 1,2,4,6,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

    这样经过13趟排序后这个序列就成为一个有序的数列。

    具体实现代码为:

           private static void BubbleSort(int[] R)         {             int len = R.Length;             bool flag = false;             for (int i = 0; i < len-1; i++)             {                 flag = false;                 for (int j = 0; j < len - i-1; j++)                 {                     if (R[j] > R[j + 1])                     {                         Swap(ref R[j], ref R[j + 1]);                         flag = true;                     }                 }                 if (!flag)                 {                     break;                 }             }         }

           private static void Swap(ref int left, ref int right)         {             int temp = left;             left = right;             right = temp;         }

     

    2. 选择排序

          每一趟从待排序的元素中选择最小的(最大的)一个元素,顺序放在已排好序的数列的最后,直到待排序的元素派完,选择排序是不稳定的排序。

        基本概念

              具有n元素的数列可以进行n-1趟直接选择排序得到有序结果,初始状态有序区为空,无序区为R[1...n]

              第1趟排序在无序区R[1...n]选择关键字最小的元素R[k],将它与无序区的R[1] 进行交换,使R[1...1]和R[2...n]变为个增加为1新有序区,和无序区的元素个数减去1的新无序区。

             第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,

             使R[1..i]和R分别变  为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果 .

             对于数列    10,33,2,4,55,6,12,34,456,66,43,23,65,1,345, 61,76,31,43,76    

             第一次排序后:1,33,2,4,55,6,12,34,456,66,43,23,65,10,345,61,76,31,43,76

             第二次排序后:  1,2,33,4,55,6,12,34,456,66,43,23,65,10,345,61,76,31,43,76

             第三次排序后:1,2,4,33,55,6,12,34,456,66,43,23,65,10,345,61,76,31,43,76

             第四次排序后:1,2,4,6,55,33,12,34,456,66,43,23,65,10,345,61,76,31,43,76

             第五次排序后:1,2,4,6,10,33,12,34,456,66,43,23,65,55,345,61,76,31,43,76

             第六次排序后:  1,2,4,6,10,12,33,34,456,66,43,23,65,55,345,61,76,31,43,76

             第七次排序后:  1,2,4,6,10,12,23,34,456,66,43,33,65,55,345,61,76,31,43,76

             第八次排序后:  1,2,4,6,10,12,23,31,456,66,43,33,65,55,345,71,76,34,43,76

             第九次排序后:  1,2,4,6,10,12,23,31,33,66,43,456,65,55,345,71,76,34,43,76

             第十次排序后:  1,2,4,6,10,12,23,31,33,34,43,456,65,55,345,71,76,66,43,76

             第十一次排序后: 1,2,4,6,10,12,23,31,33,34,43,43,65,55,345,71,76,66,456,76

             第十二次排序后:  1,2,4,6,10,12,23,31,33,34,43,43,55,65,345,71,76,66,456,76

             第十三次排序后:  1,2,4,6,10,12,23,31,33,34,43,43,55,65,66,71,76,345,456,76

            第十四次排序后:   1,2,4,6,10,12,23,31,33,34,43,43,55,65,66,71,76,76,456,345

            第十五次排序后:   1,2,4,6,10,12,23,31,33,34,43,43,55,65,66,71,76,76,345,456

           最终经过15次排序后成为有序的数列。

           具体实现代码为:

            private static void SelectSort(int[] R)         {             int len = R.Length;             int min = 0;             for (int i = 0; i < len - 1; i++)             {                 min = i;                 for (int j = i + 1; j < len - 1; j++)                 {                     if (R[min] > R[j])                     {                         min = j;                     }                 }                 Swap(ref R[i], ref R[min]);             }         }

     

    3. 插入排序

            插入排序算法是一种稳定的算法,时间复杂度是O(n^2),适用于少量数据的排序。插入算法的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的,个数加1的有序数据。插入算法把要排序的数组分为两部分:第一部分包含了数组的所有元素,但将最后一个元素除外,而第二部分就只包含这一个元素,在第一部分排序后,再把最后这个元素插入到此刻已是有序的一部分中。

       基本思想

             1:每次处理都是将无序序列的第一个元素和有序序列的元素从后面逐一比较,查到合适的插入位置,将该元素插入到有序序列的合适位置。

             2:从有序R[1]和无序R[2...n]开始进行排序。

             3:处理第i个元素时(i=2,3,…,n) ,数列{R1,R2,...Ri-1}都是有序的,而数列{Ri,Ri+1,...Rn}都是无序的,用Ri 与{R1,R2,...Ri-1}逐个比较,找到合适位置,将Ri插入,

             4:重复第三部,共进行n-i次插入处理,数组全部有序

             对于数列    10,33,2,4,55,6,12,34,456,66,43,23,65,1,345, 61,76,31,43,76    

            第一次排序后:10,33,2,4,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

            第二次排序后:  2,10,33,4,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

            第三次排序后:  2,4,10,33,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

            第四次排序后:  2,4,10,33,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

            第五次排序后:  2,3,10,12,33,55,34,456,66,43,23,65,1,345,61,76,31,43,76

            第六次排序后:  2,3,10,12,33,34,55,456,66,43,23,65,1,345,61,76,31,43,76

            第七次排序后:  2,3,10,12,33,34,55,456,66,43,23,65,1,345,61,76,31,43,76

            第八次排序后:  2,3,10,12,33,34,55,66,456,43,23,65,1,345,61,76,31,43,76

            第九次排序后:  2,3,10,12,33,34,43,55,66,456,23,65,1,345,61,76,31,43,76

            第十次排序后:  2,3,10,12,23,33,34,43,55,66,456,65,1,345,61,76,31,43,76

            第十一次排序后: 2,3,10,12,23,33,34,43,55,65,66,456,1,345,61,76,31,43,76

            第十二次排序后: 1,2,3,10,12,23,33,34,43,55,65,66,456,345,61,76,31,43,76

            第十三次排序后: 1,2,3,10,12,23,33,34,43,55,65,66,345,456,61,76,31,43,76

            第十四次排序后: 1,2,3,10,12,23,33,34,43,55,61,65,66,345,456,76,31,43,76

            第十五次排序后: 1,2,3,10,12,23,33,34,43,55,61,65,66,76,345,456,31,43,76

            第十六次排序后: 1,2,3,10,12,23,31,33,34,43,55,61,65,66,76,345,456,43,76

            第十七次排序后: 1,2,3,10,12,23,31,33,34,43,43,55,61,65,66,76,345,456,76

            第十八次排序后: 1,2,3,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

           共十八次排序后,数组才是全部有序的。

          实现代码为:

             private static void InsertSort(int[] R)         {             int len = R.Length;             int j = 0;             int temp = 0;             for (int i = 1; i < len; i++)             {                 temp=R[i];                 j=i-1;                 while (j >= 0 && temp < R[j])                 {                     R[j + 1] = R[j];                     j--;                 }                 R[j + 1] = temp;             }         }

     

    4. 快速排序

               快速排序是对冒泡排序的一种改进,它的基本思想是:通过一趟排序将要排序的数列分成独立的两个部分,其中一部分的所有数据都比后一部分的所有数据都要小,然后再按此方法对这两个部分分别进行快速排序,整个排序过程可以递归进行,以次达到整个数列变为有序。快速排序不是稳定的排序。

      算法过程

             设要排序的数组为R[1...n],首先任意选取一个元素(通常选择第一个元素)作为关键元素,然后把所有比它小的都放在前面,所有比它大的都放在后面,这个过程成为一趟快速排序。

             1. 设置两个变量 low ,high,排序开始的时候low=0,high=n-1;

             2. 以第一个数组元素为关键数据key,即key = R[low];

             3. 从high开始往前搜索,即由后开始向前搜索,high=high-1,找到第一个小于key的值R[high], 并与R[low] 交换,

             4. 从low 开始向后搜索,即由前开始向后搜索,low=low+1,找到第一个大于key的值R[low],并于R[high]交换。

             5. 重复3,4.直到low=high.

                对于数列    10,33,2,4,55,6,12,34,456,66,43,23,65,1,345, 61,76,31,43,76  

               初始关键数据key=10;

               第一次交换后:1, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76

               第二次交换后:  1, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 33, 345, 61, 76, 31, 43, 76

               第三次交换后:   1, 6, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 33, 345, 61, 76, 31, 43, 76

               第四次交换后:  1, 6, 2, 4, 55, 55, 12, 34, 456, 66, 43, 23, 65, 33, 345, 61, 76, 31, 43, 76

              这样low=high=4

               再把R[low]=key

              这样第一次快速排序后数列就变为{1,6,2,4}10{55,12,34,456,66,43,23,65,33,345,61,76,31,43,76} 

              这样再分别对{1,6,2,4}和{55,12,34,456,66,43,23,65,33,345,61,76,31,43,76}  分别进行快速排序,重复这个步骤,最终使整个数组都是有序的。

             具体实现代码为:

              private static void QuickSort(int[] R, int low, int high)         {             int pivotLoc = 0;

                if(low<high)

                 {                   pivotLoc = Partition(R, low, high);                   QuickSort(R, low, pivotLoc - 1);                   QuickSort(R, pivotLoc + 1, high);

                  }         }

            private static int Partition(int[] R, int low, int high)         {             int temp = R[low];             while (low < high)             {                 while (low < high && temp <= R[high])                 {                     high--;                 }                 R[low] = R[high];                 while (low < high && temp >= R[low])                 {                     low++;                 }                 R[high] = R[low];             }             R[low] = temp;             return low;         }

        //快速非递归排序         public static void QuickSort(int[] R, int Low, int High, Stack<int> stack)         {             int low = Low;             int high = High;             int temp = R[low];             while (high > low)             {                 while (low < high && temp <= R[high])                 {                     high--;                 }                 if (high > low)                 {                     R[low] = R[high];                     R[high] = temp;                 }                 while (low < high && temp >= R[low])                 {                     low++;                 }                 if (high > low)                 {                     R[high] = R[low];                     R[low] = temp;                 }                 if (low == high)                 {                     if (Low < low - 1)                     {                         stack.Push(Low);                         stack.Push(low - 1);                     }                     if (High > low + 1)                     {                         stack.Push(low + 1);                         stack.Push(High);                     }                 }             }         }

           测试代码:

    static void Main(string[] args)

    {

            int[] arry = new int[] { 10, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76 };             Stack<int> s=new Stack<int>();             s.Push(0);             s.Push(arryk.Length - 1);             while (s.Count > 0)             {                 int low = s.Pop();                 int high = s.Pop();                 if (low > high)                 {                     temp = low;                     low = high;                     high = temp;                 }                 QuickSort(arryk, low, high, s);                          }                   Console.ReadLine();

    }

    通过对10万条随机数据进行递归和非递归排序后发现,非递归方法的速度是递归方法速度的40倍左右。

    5 . 一个无序的数组,如何通过一个函数取出最大值和最小值,要求时间复杂度最低和空间最少

      具体算法如下:

            private static int[] GetMaxMin(int[] R)         {                      int len=R.Length;             int min = R[0];             int max = R[0];             for (int i = 1; i < len;i++ )             {                 if (min > R[i])                 {                     min = R[i];                 }                 if (max < R[i])                 {                     max = R[i];                 }             }             int[] res = new int[2];             res[0] = min;             res[1] = max;             return res;

            } 6  对于已知数组,随机存储一百个数,把奇数放左边,偶数放右边,具体算法如下:

            private static void SortNumber(int[] R)         {             int high = R.Length - 1;             int low = 0;             int temp = R[low];             while (low < high)             {                 while(low<high&&R[high]%2==0)                 {                     high--;                 }                 R[low] = R[high];                 while (low < high && R[low] % 2 == 1)                 {                    low++;                 }                 R[high] = R[low];             }             R[low] = temp;         }

            7.二分查找算法

                    二分查找算法又叫折半查找,优点是比较次数少,查找速度快,平均性能好,缺点是给定的数组必须是有序的,且插入删除困难,因此二分查找使用与不经常变动而又查找频繁的有序表。 首先,假设数组是按照升序的有序表,将表中间位置的元素与给定要查找的元素比较,如果相等,则查找成功,否则利用中间位置将表分为前后两个字表,如果中间位置记录的元素大于给定的查找的数据,在前面的字表中进行查找,否则在后面的字表中进行查找。重复以上过程,直到找到或没有子表为止。

    具体实现代码如下:

           private static int BinarySearch(int[] R, int arg)         {             int low = 0;             int high = R.Length - 1;             while (low < high)             {                 int middle = (low + high) / 2;                 if (arg == R[middle])                 {                     return middle;                 }                 else if (arg < R[middle])                 {                     high = middle - 1;                 }                 else                 {                     low = middle + 1;                 }             }             return -1;         }

    转载于:https://www.cnblogs.com/lyq88/archive/2013/01/10/2853983.html

    展开全文
  • 先介绍一下简单的递归方法。 int age(int n) { int c; if(n==1) c=10; else c=age(n-1)+2; return c; } main() { printf("age(5)=%d",age(5)); } 过程是: age(5)=c=age(4)+2=18 age(4)=c=age(3)+2=16 age(3)=c=age...

    递归方法

    先介绍一下简单的递归方法再到深入点的。

    int age(int n)
    {
    int c;
    if(n==1) c=10;
    else c=age(n-1)+2;
    return c;
    }
    main()
    {
    printf("age(5)=%d",age(5));
    }
    过程是:
    age(5)=c=age(4)+2=18
    age(4)=c=age(3)+2=16
    age(3)=c=age(2)+2=14
    age(2)=c=age(1)+2=12
    age(1)=c=10
    你输入的是printf("age(5)=%d",age(5))所以系统吧之前的age(4)age(2)保存起来,等到求出了某个值也就是age(1)时,再依次求age(2)age(5)这样
    age(5)=18
    

    在这里插入图片描述
    在这里插入图片描述
    这里是递归的方法。
    原来的是5->4->3->2->1,反转后是1->2->3->4->5。

    public class Main {
    	static class ListNode{
    		int val;
    		ListNode next;
    		ListNode(int x){
    			val=x;
    		}
    	}
    	static ListNode reverseList(ListNode head) {
    		1 if(head==null||head.next==null)
    			8 return head;
    		2 System.out.print("hao");
    		3 ListNode newHead=reverseList(head.next);//这里就是用来递归的调用。
    		4 System.out.print("ren");
    		5 head.next.next=head;
    		6 head.next=null;
    		7 return newHead;
    }
    	public static void main(String[] args) {
    		ListNode head1 = new ListNode(0);
    		ListNode node1 = new ListNode(1);
    		ListNode node2 = new ListNode(2);
    		ListNode node3 = new ListNode(3);
    		head1.next=node1;
    		node1.next=node2;
    		node2.next=node3;
    		node3.next=null;
    		System.out.println(head1.next.next.next.val);
    		9 System.out.println(reverseList(head1).next.next.next.val );
    	}
    }
    

    在这里插入图片描述
    说一下它的运行过程在当我们运行在标号为9的时候跳进reverseList方法,开始进入1,2,3这个时候又进入reverseList方法,开始1,2,3又进入开始1,2,3这个时候的又进入reverseList方法为1,8,3,4,5,6,7,接下来是3,4,5,6,7,再次是3,4,5,6,7最后跳出返回结果回到9接下来结束程序。
    这个递归过程是先走出递归条件以上的代码句,在走递归条件以下的句子, 从上面的行走的过程可以看出在c和java上都一样。
    前面的1,2,3一共走了三次为的是把刚创建的newHead指向最后一位,但此时整个链表的地址next指向是没有改变的还是5.next指向4,它的走到最后一个1,2,3是reverseList(head.next);此时的head是为2它的next为1,在判断if时候在next就为1的next也就为null了也就直接返回head此时1的头节点给newhead了,走到步奏8时返回的head是此时1的地址,在后来的 5,6步骤是让2.next则就是原来的1的next指向2,这样也就让原来的,指向方向颠倒了也就有了原来的链表倒置,依次循环也会把原来第一个的next指向为null。在经过34567的时候,列如:此时的3.next还是指向2的地址的,虽然前面的是把2.next置为null,当然原来的2.next是指向1的,因为要链表倒置3.next.next=head;也就是先把3到2的地址指向给交换一下,此时2.next指向3,3.next指向null但此时的4.next是指向3的,就这样依次循环会把原来首节点的next指向null。

    非递归方法

    ListNode newHead=null;
    while(head!=null) {
    	ListNode tmp=head.next;
    	head.next=newHead;
    	newHead=head;
    	head=temp;
    }
    
    

    在这里插入图片描述
    在这里插入图片描述
    这也有点像两个数来进行的值进行交换,会找个中间值在保存。

    展开全文
  • 递归在WinForm的应用     最近做项目经常用到递归,刚开始很久没用,不太熟悉,现在研究了下,并写下了学习笔记及开发经验总结。递归热身   一个算法调用自己来完成它的部分...

    递归在WinForm 中的应用

     

     

    最近做项目经常用到递归,刚开始很久没用,不太熟悉,现在研究了下,并写下了学习笔记及开发经验总结。

    递归热身

     

    一个算法调用自己来完成它的部分工作,在解决某些问题时,一个算法需要调用自身。如果一个算法直接调用自己或间接地调用自己,就称这个算法是递归的 (Recursive) 。根据调用方式的不同,它分为直接递归 (Direct Recursion) 和间接递归 (Indirect Recursion)   比如,在收看电视节目时,如果演播室中也有一台电视机播放的是与当前相同的节目,观众就会发现屏幕里的电视套有一层层的电视画面。这种现象类似于直接递归。  

    如果把两面镜子面对面摆放,便可从任意一面镜子里看到两面镜子无数个影像,这类似于间接递归。  

    一个递归算法必须有两个部分:初始部分 (Base Case) 和递归部分 (Recursion Case) 。初始部分只处理可以直接解决而不需要再次递归调用的简单输入。递归部分包含对算法的一次或多次递归调用,每一次的调用参数都在某种程度上比原始调用参数更接近初始情况。  

    函数的递归调用可以理解为: 通过一系列的自身调用,达到某一终止条件后,再按照调用路线逐步返回。 递归是程序设计中强有力的工具,有很多数学函数是以递归来定义的。  

    如大家熟悉的阶乘函数,我们可以对 n! 作如下定义:f(n)=  

    (n=1)

    n* f(n-1)  (n>=2)

     

          一个算法具有的特性之一就是 有穷性 (Finity) :一个算法总是在执行有穷步之后结束,即算法的执行时间是有限的。递归算法当然也是算法,也满足算法的特性,因此递归不可能无限递归下去,总有一个终止条件。对该示例,递归的终止条件是n=1.  n=1 是,返回 1 ,不在调用自己本身,递归结束。

    class   Program

        {

             static   void   Main ( string []  args )

            {

                 long   result  =  function (20);

                 Console . WriteLine ( result );

                 Console . ReadLine ();

            }

     

             static   long   function ( long   n )

            {

                 if  ( n  == 1)   //算法终止条件

                {

                     return  1;

                }

     

                 return   n  *  function ( n  - 1);

            }

    }

     

    递归算法通常不是解决问题最有效的计算机程序,因为递归包含函数调用,函数调用需要时空开销。所以,递归比其他替代选择诸如 while 循环等,所花费的代价更大。但是,递归通常提供了一种能合理有效地解决某些问题的算法。 

     

    递归示例( ) :遍历二叉树

    二叉树是一种典型的树形结构,常用到递归算法来遍历。遍历按照根节点的相对顺序可分为前序遍历(DLR) 、中序遍历 (LDR) 、后序遍历 (RDL)

     

     

     

    对二叉树节点,有数据域存放数据,左孩子和右孩子为引用域存放孩子的引用:

    左孩子  LChhild

    数据域  data

    右孩子 RChild

     

     

         ///   <summary>

         ///  二叉树节点

         ///   </summary>

         ///   <typeparam name="T"></typeparam>

        public   class   Node < T >

        {

            private   T   data ; //数据域

            private   Node < T lChild ; //左孩子

            private   Node < T rChild ; //右孩子

     

            public   Node ()

           {

                data  =  default ( T );

                lChild  =  null ;

                rChild  =  null ;

           }

     

            public   Node ( T   data Node < T lChild Node < T rChild )

           {

                this . data  =  data ;

                this . lChild  =  lChild ;

                this . rChild  =  rChild ;

           }

     

            public   Node ( Node < T lChild Node < T rChild )

           {

                data  =  default ( T );

                this . lChild  =  lChild ;

                this . rChild  =  rChild ;

           }

     

            public   Node ( T   data )

               :  this ( data null null )

           {

                this . data  =  data ;

           }

     

            ///   <summary>

            ///  数据域

            ///   </summary>

            public   T   Data

           {

                get  {  return   data ; }

                set  {  this . data  =  value ; }

           }

     

            ///   <summary>

            ///  左孩子

            ///   </summary>

            public   Node < T LChild

           {

                get  {  return   lChild ; }

                set  {  lChild  =  value ; }

           }

     

            ///   <summary>

            ///  右孩子

            ///   </summary>

            public   Node < T RChild

           {

                get  {  return   rChild ; }

                set  {  rChild  =  value ; }

           }

     

    }

    先假设有以下结构的二叉树:

    先在构造函数中简单构造下对应的数据:

    public   Node < string A ;

    public   遍历二叉树 ()

            {

                 A  =  new   Node < string >( "A" );

                 Node < string B  =  new   Node < string >( "B" );

                 Node < string C  =  new   Node < string >( "C" );

                 Node < string D  =  new   Node < string >( "D" );

                 Node < string E  =  new   Node < string >( "E" );

                 Node < string F  =  new   Node < string >( "F" );

                 Node < string G  =  new   Node < string >( "G" );

                 Node < string H  =  new   Node < string >( "H" );

                 Node < string I  =  new   Node < string >( "I" );

                 Node < string J  =  new   Node < string >( "J" );

     

                 D . LChild  =  H ;

                 D . RChild  =  I ;

     

                 E . LChild  =  J ;

     

                 B . LChild  =  D ;

                 B . RChild  =  E ;

     

                 C . LChild  =  F ;

                 C . RChild  =  G ;

     

                 A . LChild  =  B ;

                 A . RChild  =  C ;

     

            }

     

    前序遍历: 先访问根结点A ,然后分别访问左子树和右子树,把 B B 的子孙看作一个结点处理, C C 的子孙看作一个结点处理,访问 B 时,把 B 当作根结点处理, B 的左子树及左子树的子孙看作一个结点处理 …… 可见,顺序依次是顶点- 左孩子 - 右孩子( DLR ),直到结点为叶子 ( 即不包含子结点的结点 ) ,即为递归的终止条件。对任意结点,只要结点确定,其左孩子和右孩子就确定,因此递归算法方法参数将结点传入即可。

    ///   <summary>

             ///  前序遍历--DLR

             ///   </summary>

             ///   <param name="root"></param>

             public   void   PreOrder ( Node < T root )

            {

                 if  ( root  ==  null )

                {

                     return ;

                }

     

                 Console . Write ( "{0} " , root . Data );

                //当节点无左孩子时,传入参数为null,下次调用即返回,终止

                 PreOrder ( root . LChild );

                 //当节点无右孩子时,传入参数为null,下次调用即返回,终止

                 PreOrder ( root . RChild );

     

            }

    同理,中序遍历和后序遍历如下:

    ///   <summary>

             ///  中序遍历 LDR

             ///   </summary>

             ///   <param name="node"></param>

             public   void   InOrder ( Node < T node )

            {

                 //if (node == null)

                 //{

                 //    return;

                 //}

                 //InOrder(node.LChild);

                 //Console.Write("{0} ",node.Data);

                 //InOrder(node.RChild);

               

                 //另外一种写法

                 if  ( node . LChild != null )  

                {

                     InOrder ( node . LChild );

                }

                 Console . Write ( "{0} " node . Data );

                 if  ( node . RChild  !=  null )

                {

                     InOrder ( node . RChild );

                }

            }

     

             ///   <summary>

             ///  后序遍历--LRD

             ///   </summary>

             ///   <param name="node"></param>

             public   void   PostOrder ( Node < T node )

            {

                 if  ( node  ==  null )

                {

                     return ;

                }

     

                 PostOrder ( node . LChild );

                 PostOrder ( node . RChild );

                 Console . Write ( "{0} " , node . Data );

            }

     

             ///   <summary>

             ///  层序遍历

             ///   </summary>

             ///   <param name="node"></param>

             public   void   LevelOrder ( Node < T node )

            {

                 if  ( node  ==  null )

                {

                     return ;

                }

                 Queue < Node < T >>  sq  =  new   Queue < Node < T >>();

                 //根结点入队

                 sq . Enqueue ( node );

     

                 while  ( sq . Count  != 0)

                {

                     Node < T tmp  =  sq . Dequeue ();  //出队

                     Console . Write ( "{0} " , tmp . Data );

     

                     if  ( tmp . LChild  !=  null )

                    {

                         sq . Enqueue ( tmp . LChild );

                    }

                     if  ( tmp . RChild  !=  null )

                    {

                         sq . Enqueue ( tmp . RChild );

                    }

                }

            }

     

    其中,另外一种写法就是在递归前判断下,满足递归条件才调用自己,这也是处理递归终止的一种方法。

        static   void   Main ( string []  args )

            {

                 遍历二叉树 < string t  =  new   遍历二叉树 < string >();

                 Console . Write ( "前序遍历:" );

                 t . PreOrder ( t . A );

                 Console . WriteLine ();

     

                 Console . Write ( "中序遍历:" );

                 t . InOrder ( t . A );

                 Console . WriteLine ();

     

                 Console . Write ( "后序遍历:" );

                 t . PostOrder ( t . A );

                 Console . WriteLine ();

     

                 Console . Write ( "层序遍历:" );

                 t . LevelOrder ( t . A );

     

                 Console . ReadLine ();

            }

    运行结果为

     

    递归示例( ) WinForm TreeView 的应用 绑定区域树

    C#中的树很多。比如, Windows Form 程序设计和 Web 程序设计中都有一种被称为 TreeView 的控件。 TreeView 控件是一个显示树形结构的控件,此树形结构与 Windows 资源管理器中的树形结构非常类似。不同的是, TreeView 可以由任意多个节点对象组成。每个节点对象都可以关联文本和图像。另外, Web 程序设计中的 TreeView 的节点还可以显示为超链接并与某个 URL 相关联。每个节点还可以包括任意多个子节点对象。包含节点及其子节点的层次结构构成了 TreeView 控件所呈现的树形结构。

    下面是很典型的一个例子,就是用TreeView 绑定数据。数据一般符合树形结构,如行政区域之间的关系、公司部门与部门员工之间关系、磁盘目录文件之间的关系等。

    父级与子级之间满足一对多的关系,因此在数据库设计中常用一字段来做本表主键的外键,代表父级区域ID 。当然,如果要方便求子孙的算法(例如列举武汉所有子区域)可以另加一字段,记录从根结点到当前结点所经历的结点 ID

    思路分析:

    1.  获取表Area 中的所有数据,存放到 DataTable 中。

    2.  获取根结点的数据并添加到根节点。根结点的处理常与子结点的递归处理不一样,例如根结点的添加是在treeView1.Nodes.Add 里面,而子结点递归是在父结点上添加,因此经常要分开处理。获取根结点数据可用 DataTable.Select( fAreaId=-1 )来获取。绑定结点时,将 Node.Text 设为区域的名字, Node.Tag 设为区域对应的数据行 DataRow 或者区域的 ID ,这样遍历子区域就知道父结点区域信息,也方便应用程序获取选中的结点对应的数据。

    3.  递归遍历子区域并添加到TreeView 控件中。递归方法参数为 Node, 由父级 Node.Tag 就能获取父级区域数据信息,进而获取其子区域,获取子区域可用    

    DataRow[] rows=DataTable.Select( fAreaId= +父级区域 ID) 。获取子区域后将其获取的信息绑定到新建的 Node 对象,方法同第二步,然后递归调用自己。当区域不包含任何子区域时,递归终止 , rows.Length==0.

    代码如下:

    public   partial   class   BindAreaForm  :  Form

        {

             private   DataTable   dt  =  null ;

     

             public   BindAreaForm ()

            {

                 InitializeComponent ();

                 InitDataTable ();

     

            }

     

             //获取Area所用数据

             private   void   InitDataTable ()

            {

                 SqlConnection   conn  =  new   SqlConnection ( "Data Source=.;Initial Catalog=Test;Integrated Security=True" );

                 SqlCommand   cmd  =  new   SqlCommand ( "SELECT * FROM Area" conn );

                 SqlDataAdapter   ada  =  new   SqlDataAdapter ( cmd );

                 dt  =  new   DataTable ();

                 ada . Fill ( dt );

            }

     

             private   void   BindAreaForm_Load ( object   sender EventArgs   e )

            {

                 BindRoot ();

            }

     

             //绑定根节点

             private   void   BindRoot ()

            {

                 DataRow []  rows  =  dt . Select ( "fAreaId=-1" ); //取根

                 foreach  ( DataRow   dRow   in   rows )

                {

                     TreeNode   rootNode  =  new   TreeNode ();

                     rootNode . Tag  =  dRow ;

                     rootNode . Text  =  dRow [ "AreaName" ]. ToString ();

                     treeView1 . Nodes . Add ( rootNode );

     

                     BindChildAreas ( rootNode );

                }

                

            }

     

             //递归绑定子区域

             private   void   BindChildAreas ( TreeNode   fNode )

            {

                 DataRow   dr  = ( DataRow ) fNode . Tag ; //父节点数据关联的数据行

                 int   fAreaId  = ( int ) dr [ "id" ];  //父节点ID

                 DataRow []  rows  =  dt . Select ( "fAreaId=" + fAreaId ); //子区域

                 if  ( rows . Length  == 0)   //递归终止,区域不包含子区域时

                {

                     return ;

                }

     

                 foreach  ( DataRow   dRow   in   rows )

                {

                     TreeNode   node  =  new   TreeNode ();

                     node . Tag  =  dRow ;

                     node . Text  =  dRow [ "AreaName" ]. ToString ();

     

                     //添加子节点

                     fNode . Nodes . Add ( node );

                     //递归

                     BindChildAreas ( node );

                }

            }

    }

    运行截图:

     

     

     

    递归示例( ) WinForm TreeView 的应用 绑定磁盘目录( )

     

    磁盘文件系统结构符合树形结构,可以把“我的电脑”或者驱动器看做是树的根( 多个驱动器看做多个根吧,做多课树处理 ) ,文件夹下面可以包含文件夹或文件,文件则是树的叶子,不能再分,显然,这也是递归的终止条件。

    思路分析:

    1.  获取要绑定的目录,此目录为treeView 控件的根。将结点的 Tag 设置成觉对路径,以便子节点获取父结点信息。

    2. 递归遍历子目录和文件,当绝对路径对应的DirectoryInfo 为文件时,递归终止。这里要提一下,网上很多判断文件时文件夹还是文件都用后缀来判断,无后缀则为文件夹,这样是不正确的,例如 host 文件就没后缀,但它是文件而不是文件夹,还有很多软件的缓存文件也没后缀的,把它们当文件夹来处理遍历访问子目录显然有异常。正确的方法是用 FileSystemInfo 类的 GetType() 方法。

      public   partial   class   MainForm  :  Form

        {

           

             public   MainForm ()

            {

                 InitializeComponent ();    

            }

             private   void   MainForm_Load ( object   sender EventArgs   e )

            {

              

                 TreeNode   root  =  new   TreeNode ();

                 root . Text  =  @"战国无双 2" ;

                 root . Tag  =  @"E:/战国无双 2" ;

                 treeView1 . Nodes . Add ( root );

                 BindChild ( root );

            }

          

             private   void   BindChild ( TreeNode   fNode )

            {

                 string   path  =  fNode . Tag . ToString ();

                

     

                 //父目录

                 DirectoryInfo   fDir  =  new   DirectoryInfo ( path );

                 FileSystemInfo []  finfos  =  fDir . GetFileSystemInfos ();

             

                 foreach  ( FileSystemInfo   f   in   finfos )

                {

                    string   type  =  f . GetType (). ToString ();

                     TreeNode   node  =  new   TreeNode ();

                     node . Text  =  f . Name ;

                     node . Tag  =  f . FullName ;

     

                     fNode . Nodes . Add ( node );

                     if  ( "System.IO.DirectoryInfo"  ==  type //是文件夹时才递归调用自己

                    {

                         BindChild ( node );

                    } 

                }

            }      

    运行截图如下:

     

    总结:

    TreeView递归绑定一般分两大步,第一步对根结点操作及输入绑定,并将结点关联数据传入递归;第二步主要是递归终止的控制,控制终止一般有两种方法:一是在递归方法开始判断是否满足递归终止条件,是则显式 return 返回,否则继续调用自己;另外一种方法是在调用自己前判断是否满足递归的条件,满足条件才调用自己。两种方法具体看程序。

    当把上面的目录改为比较大的目录例如C:/Windows 时,发现加载要很多时间。针对这个问题,请看下一篇:动态加载结点。

     

     

     

     

     

     

    递归示例( ) WinForm TreeView 的应用 绑定磁盘目录( )

     

    当具有树形结构的数据的结点很多而且树的深度比较大时,直接用递归遍历明显能发现性能很低。因此,不要一次全部加载,而是当用户点击展开时才加载此结点下的子结点。

    实现要点:

    每加载添加一个结点时,判断该结点是否为叶子( 即不含子结点 ) ,若包含子结点,先添加一个空的子节点,这样做主要是让用户在界面能看到“ + ”表示结点能展开。当用户点击“ + ”时触发 treeView_AfterExpand 事件,在该事件中处理添加子结点数据,添加之前,清理删除掉以前的结点。

       public   partial   class   MainForm2  :  Form

        {

             public   MainForm2 ()

            {

                 InitializeComponent ();

                 this . SetStyle ( ControlStyles . OptimizedDoubleBuffer true );

            }

     

             private   void   MainForm2_Load ( object   sender EventArgs   e )

            {

                 BindDrives ();

            }

     

             private   void   BindDrives ()

            {

                 DriveInfo []  drvs  =  DriveInfo . GetDrives ();

                 foreach  ( DriveInfo   drv   in   drvs )

                {

                     TreeNode   root  =  new   TreeNode ();

                     root . Text  =  drv . Name ;

                     root . Tag  =  drv . RootDirectory . ToString ();

                     // root.Nodes.Add("");

                     treeView1 . Nodes . Add ( root );

                     if  ( Directory . Exists ( drv . RootDirectory . ToString ()))

                    {

                         DirectoryInfo   dInfo  =  new   DirectoryInfo ( drv . RootDirectory . ToString ());

     

                         FileSystemInfo []  files  =  dInfo . GetFileSystemInfos ();

                         if  ( files . Length  > 0)  //有子节点,先添加一个空节点

                        {

                             root . Nodes . Add ( "emptyNode" string . Empty );

                        }

                    }

                }

            }

     

             //展开节点,移除以前的空节点,加载子节点

             private   void   treeView1_AfterExpand ( object   sender TreeViewEventArgs   e )

            {

     

                 TreeNode   parentNode  =  e . Node ;

                 // parentNode.Nodes.RemoveByKey("emptyNode");//移除空节点

                 parentNode . Nodes . Clear ();

                 string   path  =  parentNode . Tag . ToString ();

     

                 if  ( Directory . Exists ( path ))

                {

                     DirectoryInfo   dir  =  new   DirectoryInfo ( path );

     

                     FileSystemInfo []  files  =  dir . GetFileSystemInfos ();

                     foreach  ( FileSystemInfo   f   in   files )

                    {

                         TreeNode   node  =  new   TreeNode ();

                         node . Text  =  f . Name ;

                         node . Tag  =  f . FullName ;

                         parentNode . Nodes . Add ( node );   //加载子节点

     

                         if  ( Directory . Exists ( node . Tag . ToString ()))

                        {

                             DirectoryInfo   subDir  =  new   DirectoryInfo ( node . Tag . ToString ());

                             if  ( subDir . Attributes  != ( FileAttributes . System  |  FileAttributes . Hidden  |  FileAttributes . Directory ))

                            {

                                 FileSystemInfo []  subFiles  =  subDir . GetFileSystemInfos ();

                                 if  ( subFiles . Length  > 0)    //有子节点,先添加一个空节点

                                {

                                     node . Nodes . Add ( "emptyNode" string . Empty );

                                }

                            }

                        }

                    }

     

                }

    运行结果如图:

    这样,只加载用户要展开的结点,而且每次只加载当前结点的下一代,性能明显能提升,当然还能用多线程技术改善性能、用 WindowsAPI获取文件图标并关联 TreeView 结点,这里就不介绍了。

    展开全文
  • C#实现(递归和非递归)快速排序和简单排序等一系列排序算法
  • 遍历文件与文件夹的程序可以用递归实现,也可以链表List,队列Queue,堆栈Stack。 详细代码如下。 一、添加类:FileAndFolder.cs 添加如下程序代码: using System; using System.Collections.Generic; ...
  • 递归在WinForm的应用 <br /> 最近做项目经常用到递归,刚开始很久没用,不太熟悉,现在研究了下,并写下了学习笔记及开发经验总结。递归热身 <br />一个算法调用自己来完成它的部分工作,在...
  • 递归:函数自己调用自己 def func(): print("我是递归") #这里了变为死循环 func() func() # 官方最大1000,你永远跑不到1000, 我实测998 while 1: print("我不是递归") 树形结构的遍历假设存在一...
  • 一、迭代实现 思路: 通过每次遍历,修改当前结点与上一结点指向,遍历到最后一个结点,链表也就实现了反转 首先我们定义三个指针,分别指向当前节点cur、前一结点pre、下一节点next,并且pre和next为null ...
  • 逆置顺序表

    2018-01-02 15:37:54
    建立长度为n的顺序表,然后将表的数据元素逆置,即若表原来的数据元素序列为(a0,a1,a2,…,an),则逆置后的数据元素序列为(an,an-1,an-2,…,a1,a0)。(数据类型为字符型)Description第一行为顺序表...
  • 使用递归查询地区 开发工具与关键技术:Visual Studio 2015、SQL Server 2014 Management Studio、C#、JavaScript 作者: 饶芝华 撰写时间:2019年01月 18日 这是数据库的一张部分地区: 此设计借鉴麦志坚...
  • 前几天看了一个.net程序员面试题目,题目是”统计给定的文本字符出现的次数,使用循环和递归两种方法“。  下面是我对这个题目的解法:  1、使用循环: 1 /// <summary> 2 /// 使用For循环统计...
  • 顺序表应用8:最大子段和之动态规划法 Time Limit: 5MS Memory Limit: 500KB Submit Statistic Problem Description  给定n(1负数时定义子段和为0,依此定义,所的最优值为: Max{0,a[i]+a[i+1]+…+a[j]...
  • 递归打印lua

    2017-08-12 19:38:41
    递归打印lualua的print方法是不支持的打印的,这样查看一个table的内容会变得非常麻烦,在写这篇博客之前我也从网上查找了大量资料,内容很多,但是都不能满足我的要求。要不输出格式不够美观要不就是起来麻烦...
  • 一,集合1、集合的概念 集合(Set)是由一些确定的、彼此...集合成员的个数称为集合的基数(Cardinality)。 例如,集合 R 由整数 3、4、5 组成,写成 R={3,4,5}。此时 R 的成员是 3、4、5,R 的基类型是整型,R ...
  • C语言两种非递归方式实现中序遍历链表二叉树 二叉树采用二叉链表存储结构,...这与后序遍历的顺序一致,所以应付当在后序遍历的过程释放结点,可以使用后序遍历的递归算法。 若二叉树如图所示,则 示例1: 输入:...
  • 希望你也加入到人工智能的队伍来!请点击http://www.captainbed.net /* * Recursive Binary Search - by Chimomo * * [折半查找的前提]: * 1、待查找序列必须采用顺序存储结构。 * 2、待查找序列必须是按...
  • 广义是线性表的推广。定义是:一个广义是n个元素的一个有限序列。差不多就是线性表元素里面还有线性表,这个里面的元素称为原子,如果这个原子也是线性表称之为子。表示为:GL=(a1,a2,a3.....an)。和我们...
1 2 3 4 5 ... 20
收藏数 9,745
精华内容 3,898