Алгоритмы и структуры данных на C#: полное руководство для .NET разработчика

Алгоритмы и структуры данных на C#: фундамент для эффективного .NET-кода

В современной разработке на платформе .NET знание алгоритмов и структур данных является обязательным навыком для создания производительных и масштабируемых приложений. Независимо от того, пишете ли вы веб-сервисы на ASP.NET Core, десктопные приложения на WPF или мобильные решения на Xamarin, правильный выбор структуры данных напрямую влияет на скорость работы программы и потребление памяти. В этой статье мы разберем ключевые структуры данных и алгоритмы на языке C#, сопровождая каждый раздел практическими примерами кода.

1. Базовые структуры данных в C#: массивы и списки

Начнем с самого фундамента. В C# существует несколько встроенных типов для хранения коллекций, и понимание их внутреннего устройства критически важно.

Массивы (Array)

Массив — это фиксированная последовательность элементов одного типа. Он обеспечивает самый быстрый доступ по индексу (O(1)), но не позволяет изменять размер после создания.

int[] numbers = new int[5] { 10, 20, 30, 40, 50 };
// Доступ по индексу
int thirdElement = numbers[2]; // 30
// Изменение элемента
numbers[3] = 100;

Используйте массивы, когда количество элементов известно заранее и не будет меняться (например, для хранения констант или фиксированных буферов).

Список (List<T>)

List<T> — это динамический массив. Он автоматически расширяется при добавлении новых элементов. Внутри он использует обычный массив, который пересоздается при превышении емкости.

List<string> fruits = new List<string>();
fruits.Add("Яблоко");
fruits.Add("Банан");
fruits.Add("Апельсин");
Console.WriteLine(fruits.Count); // 3
fruits.RemoveAt(1); // Удаляем "Банан"

List<T> — универсальный выбор для большинства задач, где требуется последовательный доступ и частые изменения размера коллекции.

2. Стек и очередь: принципы LIFO и FIFO

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

Стек (Stack<T>)

Стек работает по принципу "последним пришел — первым вышел" (LIFO). В .NET стек реализован как универсальная коллекция.

Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);

int top = stack.Pop(); // 3
int peek = stack.Peek(); // 2 (без удаления)

Реальный пример: проверка корректности скобок в строке или реализация кнопки "Назад" в браузере.

Очередь (Queue<T>)

Очередь следует принципу "первым пришел — первым вышел" (FIFO). Это идеальный выбор для обработки задач в порядке их поступления.

Queue<string> queue = new Queue<string>();
queue.Enqueue("Задача 1");
queue.Enqueue("Задача 2");
queue.Enqueue("Задача 3");

string task = queue.Dequeue(); // "Задача 1"
string nextTask = queue.Peek(); // "Задача 2"

Очереди активно используются в паттернах Producer-Consumer, при обработке сообщений и в системах логирования.

3. Деревья и рекурсивные алгоритмы на C#

Деревья — это иерархические структуры, где каждый узел может иметь несколько дочерних узлов. Особое место занимают двоичные деревья поиска (BST), обеспечивающие быстрый поиск, вставку и удаление (O(log n) в среднем).

Реализация двоичного дерева поиска

public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}

public class BinarySearchTree
{
    public TreeNode Root;

    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }

    private TreeNode InsertRec(TreeNode root, int value)
    {
        if (root == null)
            return new TreeNode(value);

        if (value < root.Value)
            root.Left = InsertRec(root.Left, value);
        else if (value > root.Value)
            root.Right = InsertRec(root.Right, value);

        return root;
    }

    public bool Search(int value)
    {
        return SearchRec(Root, value);
    }

    private bool SearchRec(TreeNode root, int value)
    {
        if (root == null) return false;
        if (value == root.Value) return true;
        return value < root.Value 
            ? SearchRec(root.Left, value) 
            : SearchRec(root.Right, value);
    }
}

Рекурсия — естественный способ обхода деревьев. Однако помните, что глубокая рекурсия может привести к переполнению стека. В таких случаях используйте итеративные подходы с явным стеком.

4. Алгоритмы сортировки на C#: от простого к эффективному

Сортировка — одна из самых изучаемых тем в алгоритмах. Рассмотрим два популярных алгоритма.

Быстрая сортировка (QuickSort)

QuickSort — один из самых быстрых алгоритмов в среднем случае (O(n log n)). Он использует стратегию "разделяй и властвуй".

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivotIndex = Partition(arr, low, high);
        QuickSort(arr, low, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, high);
    }
}

private static int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]); // swap с кортежами
        }
    }
    (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
    return i + 1;
}

Сортировка слиянием (MergeSort)

MergeSort также работает за O(n log n), но гарантирует стабильность и предсказуемую производительность. Он использует дополнительную память.

public static void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}

private