Алгоритм обхода дерева каталогов в C# без рекурсии

Наиболее часто, при решении типовой задачи обхода дерева каталогов в C# используется алгоритм с использованием рекурсии. Однако, это не единственный из возможных вариантов решения. Сегодня мы рассмотрим алгоритм обхода дерева папок без использования рекурсии. Для работы нам понадобится знание работы стека.

Задача

Организовать обход дерева каталогов на любую глубину без использования рекурсии.

Краткие сведения о стеке в C#

Стек — это упорядоченная структура данных, в которой действует принцип LIFO (англ. Last In — First Out) — «последний зашел — первый вышел». В C# для создания стека может использоваться универсальный класс Stack<T> у которого определены следующие основные методы:

• Push— вставляет элемент в начало Stack .
• Pop  — удаляет элемент из верхней части Stack<T> .
• Peek  — возвращает элемент, расположенный в верхней части Stack<T>, но не удаляет его.

Принцип по которому действует стек можно продемонстрировать в следующем примере:

Stack<string> numbers = new Stack<string>();
numbers.Push("one");
numbers.Push("two");
numbers.Push("three");
numbers.Push("four");
numbers.Push("five");

// A stack can be enumerated without disturbing its contents.
foreach (string number in numbers)
{
    Console.WriteLine(number);
}

В этой части программы создается стек на пять элементов, которые последовательно добавляются в стек и, затем, используя цикл foreach выводятся пользователю в консоль. В результате в консоли мы увидим следующий результат:

То есть все элементы выводятся в итоге в обратном по сравнению с добавлением порядке — от последнего добавленного элемента до первого.

Алгоритм обхода дерева каталогов в C# без рекурсии

Без использования рекурсии обход дерева каталогов можно представить в виде следующего алгоритма:

1. Создаем стек и добавляем в него директорию, которую указал пользователь для обхода
2. Создаем цикл while, который выполняем до тех пор, пока в стеке есть хотя бы один элемент
   1. в цикле while:
      1. извлекаем очередной (последний добавленный) элемент из стека — путь к директори
      2. используя методы работы с каталогами в C#, получаем список всех подкаталогов в текущем каталоге
      3. добавляем полученные директории в стек
      4. используя методы работы с каталогами в C#, получаем список всех файлов в текущем каталоге и выводим их пользователю.
   2. завершаем работу цикла, если стек оказывается пустым

Реализация алгоритма обхода дерева каталогов в C# без рекурсии

Ниже представлен метод, реализующий алгоритм обхода дерева каталогов в C# без использования рекурсии:

public static void Walk(string root)
{
    Stack<string> dirs = new Stack<string>(20);
    if (!Directory.Exists(root))
    {
        throw new ArgumentException();
    }
    
    dirs.Push(root);

    while (dirs.Count > 0)
    {
        string currentDir = dirs.Pop();
        string[] subDirs;
        try
        {
            subDirs = Directory.GetDirectories(currentDir);
        }
        catch (UnauthorizedAccessException e)
        {
            Console.WriteLine(e.Message);
            continue;
        }
        catch (DirectoryNotFoundException e)
        {
            Console.WriteLine(e.Message);
            continue;
        }

        string[] files = null;
        try
        {
            files = Directory.GetFiles(currentDir);
        }

        catch (UnauthorizedAccessException e)
        {

            Console.WriteLine(e.Message);
            continue;
        }

        catch (DirectoryNotFoundException e)
        {
            Console.WriteLine(e.Message);
            continue;
        }
        foreach (string file in files)
        {
            try
            {
                FileInfo fi = new FileInfo(file);
                Console.WriteLine("{0}: {1}, {2}", fi.Name, fi.Length, fi.CreationTime);
            }
            catch (FileNotFoundException e)
            {
                Console.WriteLine(e.Message);
                continue;
            }
        }

        foreach (string str in subDirs)
            dirs.Push(str);
    }
}

В представленном методе в блоках try...catch обрабатываются следующие исключительные ситуации:

• UnauthorizedAccessException — исключение возникает, когда у текущего пользователя недостаточно прав для просмотра каталога
• DirectoryNotFoundException — исключение возникает, когда программа пробует получить доступ к каталогу в момент, когда этот каталог был удален или же доступ осуществляется к несуществующему каталогу
• FileNotFoundException — исключение возникает, когда программа пробует получить доступ к файлу в момент, когда этот файл был удален или же доступ осуществляется к несуществующему файлу.

Для каждого найденного файла в консоль будет выведена строка, содержащая имя файла, его размер в байтах и дату создания. Для более подробной информации о форматировании строк см. эту статью, а для получения информации по файлам — эту.

Исходный код программы обхода дерева каталогов в C# без использования рекурсии

Ниже представлен весь исходный код программы, реализующей обход дерева каталогов без использования рекурсии:

using System;
using System.IO;
using System.Collections.Generic;

namespace FileSystem
{
    class Program
    {
        static void Main(string[] args)
        {
            Walk(@"c:\CSharp Output\");//подставляем в качестве параметра путь к папке
        }

        public static void Walk(string root)
        {
            Stack<string> dirs = new Stack<string>(20);

            if (!Directory.Exists(root))
            {
                throw new ArgumentException();
            }
            
            dirs.Push(root); //добавили элемент в стек

            while (dirs.Count > 0)
            {
                string currentDir = dirs.Pop(); //извлекаем очередной элемент из стека
                string[] subDirs;
                try
                {
                    subDirs = Directory.GetDirectories(currentDir);//получаем список каталогов
                }
                catch (UnauthorizedAccessException e)
                {
                    Console.WriteLine(e.Message);
                    continue;
                }
                catch (DirectoryNotFoundException e)
                {
                    Console.WriteLine(e.Message);
                    continue;
                }

                string[] files;
                try
                {
                    files = Directory.GetFiles(currentDir);//получаем список файлов
                }

                catch (UnauthorizedAccessException e)
                {

                    Console.WriteLine(e.Message);
                    continue;
                }

                catch (DirectoryNotFoundException e)
                {
                    Console.WriteLine(e.Message);
                    continue;
                }
                
                foreach (string file in files) //выводим информацию о файлах в консоль
                {
                    try
                    {
                        FileInfo fi = new FileInfo(file);
                        Console.WriteLine("{0}: {1}, {2}", fi.Name, fi.Length, fi.CreationTime);
                    }
                    catch (FileNotFoundException e)
                    {
                        Console.WriteLine(e.Message);
                        continue;
                    }
                }

                foreach (string str in subDirs)
                    dirs.Push(str); //добавляем все подкаталоги в стек
            }
        }

    }
}

Итого

Сегодня мы реализовали в C# алгоритм обхода дерева папок без использования рекурсивных методов и, попутно, познакомились с такой структурой данных как стек. Без использования рекурсии код становится больше и, иногда, сложнее в осмыслении, однако и более безопасным. О том, как организовать рекурсивный обход дерева каталогов — смотрите эту статью.