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

Алгоритмы и структуры данных на C#: на практике

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

1. Динамические массивы и работа с List<T>

В C# базовым динамическим массивом является класс List<T>. В отличие от классического массива, он автоматически расширяется при добавлении элементов. Рассмотрим его ключевые операции и одну из важнейших — бинарный поиск.

Бинарный поиск (Binary Search) работает только на отсортированных данных. Его сложность — O(log n). Алгоритм делит диапазон поиска пополам на каждом шаге.

using System;
using System.Collections.Generic;

public class BinarySearchExample
{
    public static int BinarySearch(List<int> sortedList, int target)
    {
        int left = 0;
        int right = sortedList.Count - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (sortedList[mid] == target)
                return mid; // Элемент найден, возвращаем индекс
            else if (sortedList[mid] < target)
                left = mid + 1; // Ищем в правой половине
            else
                right = mid - 1; // Ищем в левой половине
        }
        return -1; // Элемент не найден
    }

    public static void Main()
    {
        var numbers = new List<int> { 2, 5, 8, 12, 16, 23, 38, 45, 56, 67 };
        int target = 23;
        int result = BinarySearch(numbers, target);
        Console.WriteLine(result != -1 ? $"Элемент {target} найден на индексе {result}" : "Элемент не найден");
    }
}

Почему это важно? List<T> используется в 90% проектов. Умение быстро искать в нем данные — ключ к производительности.

2. Стек и Очередь: LIFO и FIFO на практике

Стек (Stack) и очередь (Queue) — это коллекции с четко определенным порядком доступа. Они незаменимы при обработке вызовов, синтаксическом анализе и работе с задачами.

Стек (LIFO — Last In, First Out)

Используется, например, для проверки правильности скобок в коде.

using System;
using System.Collections.Generic;

public class StackExample
{
    public static bool IsValidBrackets(string input)
    {
        Stack<char> stack = new Stack<char>();
        foreach (char ch in input)
        {
            if (ch == '(' || ch == '{' || ch == '[')
            {
                stack.Push(ch);
            }
            else if (ch == ')' || ch == '}' || ch == ']')
            {
                if (stack.Count == 0) return false;

                char top = stack.Pop();
                if ((ch == ')' && top != '(') ||
                    (ch == '}' && top != '{') ||
                    (ch == ']' && top != '['))
                {
                    return false;
                }
            }
        }
        return stack.Count == 0;
    }

    public static void Main()
    {
        string test1 = "({[]})";
        string test2 = "({[})";
        Console.WriteLine($"'{test1}' — корректные скобки: {IsValidBrackets(test1)}");
        Console.WriteLine($"'{test2}' — корректные скобки: {IsValidBrackets(test2)}");
    }
}

Очередь (FIFO — First In, First Out)

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

using System;
using System.Collections.Generic;

public class QueueExample
{
    public static void Main()
    {
        Queue<string> printQueue = new Queue<string>();
        printQueue.Enqueue("Документ1.pdf");
        printQueue.Enqueue("Документ2.pdf");
        printQueue.Enqueue("Документ3.pdf");

        Console.WriteLine("Очередь печати:");
        while (printQueue.Count > 0)
        {
            string document = printQueue.Dequeue();
            Console.WriteLine($"Печатается: {document}");
        }
    }
}

3. Связный список: собственная реализация

Хотя в .NET есть встроенный LinkedList<T>, понимание его внутреннего устройства развивает алгоритмическое мышление. Реализуем односвязный список.

using System;

public class Node
{
    public int Data { get; set; }
    public Node Next { get; set; }

    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

public class SinglyLinkedList
{
    private Node head;

    public void AddFirst(int data)
    {
        Node newNode = new Node(data);
        newNode.Next = head;
        head = newNode;
    }

    public void AddLast(int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }

    public void PrintList()
    {
        Node current = head;
        while (current != null)
        {
            Console.Write(current.Data + " -> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }

    public static void Main()
    {
        SinglyLinkedList list = new SinglyLinkedList();
        list.AddLast(10);
        list.AddLast(20);
        list.AddFirst(5);
        list.PrintList(); // Вывод: 5 -> 10 -> 20 -> null
    }
}

Преимущество связного списка: вставка и удаление в начале списка выполняются за O(1), в отличие от массива, где это требует сдвига элементов.

4. Сортировка пузырьком и быстрая сортировка (QuickSort)

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

Сортировка пузырьком (Bubble Sort) — O(n²)

Подходит для обучения, но не для продакшна.

using System;

public class BubbleSortExample
{
    public static void BubbleSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    // Обмен значений
                    (arr[j], arr[j +