Освоение структур данных в .NET: создание оптимизированного программного продукта

От массивов к набору хэшей: усовершенствуйте свой код, самостоятельно создавая структуры данных, повышая уровень разработки C# в .NET.

Готовы ли вы погрузиться в увлекательный мир структур данных в .NET? Если вы разработчик, стремящийся улучшить свои навыки кодирования и создавать более эффективные приложения, вы попали по адресу! В этом мы отправимся в авантюрное путешествие по структурам данных, сосредоточившись на их реализации в неизменно популярной среде dotnet. Приготовьтесь к некоторым умопомрачительным концепциям, аналогиям с полными реализациями.

Скромный массив: строительные блоки данных

(Встроенный тип данных в .NET)

Начнем со скромного массива — строительного блока многих структур данных. Массивы похожи на команду супергероев, где каждому члену присвоен уникальный индекс. Как и в «Мстителях», где Железный человек знает, что его индекс равен 0, Капитан Америка — его индексу 1 и т. д., массивы позволяют нам хранить коллекцию элементов, к которым мы можем получить доступ, используя их соответствующие индексы. Но будьте осторожны, доступ к элементу за пределами массива подобен Тору, взмахивающему молотом в воздухе — это приводит к проблемам!

// Creating an array of integers
int[] myArray = new int[5];

// Accessing elements in the array
myArray[0] = 10;
myArray[1] = 20;
myArray[2] = 30;
myArray[3] = 40;
myArray[4] = 50;

Чтобы использовать возможности массивов в dotnet, ознакомьтесь с официальной документацией.

Связанные списки: динамический дуэт

(Встроенный тип данных в .NET)

Представьте, что вы участвуете в гонке, и вы можете держаться за руки только с человеком впереди вас. Это концепция связанного списка! Каждый элемент или «узел» содержит значение и ссылку на следующий узел, образуя цепочку взаимосвязанных героев. Связанные списки превосходны в сценариях, где важно динамическое изменение размера, поскольку их можно легко адаптировать, добавляя или удаляя узлы. Это похоже на Фантастическую четверку, растягивание и сжатие по мере необходимости!

// Creating a linked list of strings
LinkedList<string> myLinkedList = new LinkedList<string>();

// Adding elements to the linked list
myLinkedList.AddLast("Apple");
myLinkedList.AddLast("Banana");
myLinkedList.AddLast("Orange");
myLinkedList.AddLast("Grapes");

// Removing an element from the linked list
myLinkedList.Remove("Banana");

Чтобы исследовать увлекательный мир связанных списков в dotnet, ознакомьтесь с Документацией Dotnet LinkedList.

Стеки и очереди: парадокс очереди ожидания

(Давайте создадим свой собственный, несмотря на то, что встроенный тип данных уже существует в .NET)

Давайте отдохнем от супергероев и окунемся в мир очередей и штабелей. Стопки похожи на стопку блинов, куда можно добавлять или убирать только сверху. Он следует принципу «последним пришел — первым ушел» (LIFO), точно так же, как однажды вы решили съесть десерт перед ужином. С другой стороны, очереди напоминают очередь в тематический парк — первый в очереди получает удовольствие от поездки первым, а опоздавшие должны терпеливо ждать. Очереди работают по принципу «первым пришел – первым обслужен» (FIFO), что обеспечивает справедливость для всех.

Стеки: последний пришел, первый ушел

Давайте создадим нашу собственную реализацию стека в ядре dotnet, используя C#:

// Define the Stack class
public class Stack<T>
{
    private List<T> items; // A list to store the elements

    public Stack()
    {
        items = new List<T>(); // Initialize the list
    }

    public void Push(T item)
    {
        items.Add(item); // Add the item to the top of the stack
    }

    public T Pop()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("Stack is empty.");
        }

        int lastIndex = items.Count - 1;
        T lastItem = items[lastIndex]; // Retrieve the last item
        items.RemoveAt(lastIndex); // Remove the last item from the list
        return lastItem;
    }

    public T Peek()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("Stack is empty.");
        }

        return items[items.Count - 1]; // Retrieve the last item without removing it
    }

    public bool IsEmpty()
    {
        return items.Count == 0; // Check if the stack is empty
    }
}

С этой пользовательской реализацией Stack теперь мы можем выполнять магические операции:

// Creating a stack of integers
Stack<int> numberStack = new Stack<int>();

// Pushing elements onto the stack
numberStack.Push(10);
numberStack.Push(20);
numberStack.Push(30);

// Checking the top element
int topElement = numberStack.Peek(); // Retrieves the top element (30)

// Popping elements from the stack
int poppedElement = numberStack.Pop(); // Removes and returns the top element (30)

Откройте для себя очаровательные истории о стеках и очередях в Документации по стекам и очередям Dotnet.

Очереди: первый пришел, первый вышел

Давайте создадим собственную реализацию очереди в ядре dotnet с помощью C#:

// Define the Queue class
public class Queue<T>
{
    private List<T> items; // A list to store the elements

    public Queue()
    {
        items = new List<T>(); // Initialize the list
    }

    public void Enqueue(T item)
    {
        items.Add(item); // Add the item to the end of the queue
    }

    public T Dequeue()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        T firstItem = items[0]; // Retrieve the first item
        items.RemoveAt(0); // Remove the first item from the list
        return firstItem;
    }

    public T Peek()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        return items[0]; // Retrieve the first item without removing it
    }
    public bool IsEmpty()
    {
        return items.Count == 0; // Check if the queue is empty
    }
}

С нашей пользовательской реализацией `Queue` мы теперь можем испытать магию очередей:

// Creating a queue of strings
Queue<string> messageQueue = new Queue<string>();

// Enqueueing messages into the queue
messageQueue.Enqueue("Hello");
messageQueue.Enqueue("World");
messageQueue.Enqueue("!");

// Checking the front message
string frontMessage = messageQueue.Peek(); // Retrieves the front message ("Hello")

// Dequeueing messages from the queue
string dequeuedMessage = messageQueue.Dequeue(); // Removes and returns the front message ("Hello")

Деревья: иерархическая организация природы

(Давайте построим собственное дерево)

Представьте себе лес, полный деревьев, каждое из которых разветвляется по-своему. В этом прелесть древовидных структур данных. Деревья иерархичны, с корневым узлом в качестве основы и дочерними узлами, отходящими от него. Как и в генеалогическом дереве, каждый узел может иметь несколько дочерних элементов, создавая богатую сеть отношений. Но будьте осторожны, чтобы не создать «круглое дерево» — это похоже на бесконечную семейную встречу!

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

// Define the TreeNode class
public class TreeNode<T>
{
    public T Value { get; set; }
    public TreeNode<T> Left { get; set; }
    public TreeNode<T> Right { get; set; }

    public TreeNode(T value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

// Define the BinaryTree class
public class BinaryTree<T>
{
    public TreeNode<T> Root { get; set; }

    public BinaryTree()
    {
        Root = null;
    }

    public void Insert(T value)
    {
        TreeNode<T> newNode = new TreeNode<T>(value);

        if (Root == null)
        {
            Root = newNode;
        }
        else
        {
            InsertNode(Root, newNode);
        }
    }

    private void InsertNode(TreeNode<T> currentNode, TreeNode<T> newNode)
    {
        // Determine whether to place the new node in the left or right subtree
        if (Comparer<T>.Default.Compare(newNode.Value, currentNode.Value) < 0)
        {
            if (currentNode.Left == null)
            {
                currentNode.Left = newNode;
            }
            else
            {
                InsertNode(currentNode.Left, newNode);
            }
        }
        else
        {
            if (currentNode.Right == null)
            {
                currentNode.Right = newNode;
            }
            else
            {
                InsertNode(currentNode.Right, newNode);
            }
        }
    }
}

С нашей пользовательской реализацией BinaryTree теперь мы можем посеять семена иерархии:

// Creating a binary tree of integers
BinaryTree<int> tree = new BinaryTree<int>();

// Inserting elements into the tree
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);
tree.Insert(3);

Чтобы исследовать лес деревьев в dotnet, побродите по документации Dotnet Tree.

Графики: сеть связей

(Давайте построим собственный график)

Вы когда-нибудь задумывались, насколько взаимосвязан наш мир? Графики обеспечивают способ представления и навигации по сложным сетям соединений. Представьте себе социальную сеть, в которой каждый человек является узлом, а их дружба — ребрами, которые их соединяют. Графики позволяют нам моделировать и анализировать отношения, что делает их важными для таких задач, как планирование маршрута или анализ социальных сетей. Но остерегайтесь печально известных «графических циклов» — они похожи на бесконечный цикл запросов на добавление в друзья!
Также мы можем рассмотреть пример перемещения между городами внутри страны, что также объясняет, как работает график?

В ядре dotnet мы можем создать собственную структуру данных графа, используя C#:

// Define the Graph class
public class Graph<T>
{
    private Dictionary<T, List<T>> adjacencyList; // A dictionary to store the adjacency list

    public Graph()
    {
        adjacencyList = new Dictionary<T, List<T>>(); // Initialize the adjacency list
    }

    public void AddVertex(T vertex)
    {
        if (!adjacencyList.ContainsKey(vertex))
        {
            adjacencyList[vertex] = new List<T>(); // Add a new vertex to the graph
        }
    }

    public void AddEdge(T source, T destination)
    {
        if (adjacencyList.ContainsKey(source) && adjacencyList.ContainsKey(destination))
        {
            adjacencyList[source].Add(destination); // Add an edge between two vertices
            adjacencyList[destination].Add(source); // For an undirected graph, add the reverse edge as well
        }
    }

    public List<T> GetNeighbors(T vertex)
    {
        if (adjacencyList.ContainsKey(vertex))
        {
            return adjacencyList[vertex]; // Retrieve the neighbors of a vertex
        }

        return new List<T>();
    }
}

С нашей пользовательской реализацией Graph теперь мы можем перемещаться по сети взаимосвязей:

// Creating a graph of cities
Graph<string> cityGraph = new Graph<string>();

// Adding vertices (cities) to the graph
cityGraph.AddVertex("New York");
cityGraph.AddVertex("London");
cityGraph.AddVertex("Tokyo");

// Adding edges (connections) between cities
cityGraph.AddEdge("New York", "London");
cityGraph.AddEdge("London", "Tokyo");

// Getting neighbors (connected cities) of a vertex
List<string> neighbors = cityGraph.GetNeighbors("London"); // Retrieves the neighbors of "London" (New York, Tokyo)

Если вы готовы исследовать необъятное царство графов в dotnet, отправляйтесь в захватывающее приключение с Документацией Dotnet Graph.

Хеш-таблицы: магия пар ключ-значение

(Встроенный тип данных в .NET)

Готовы ли вы стать свидетелем магии пар ключ-значение в сфере структур данных? Приготовьтесь к завораживающему миру хеш-таблиц в dotnet. Подобно фокуснику, который без труда извлекает нужную карту из колоды, хеш-таблицы обеспечивают молниеносный доступ к данным с помощью уникальных ключей.

В этом увлекательном путешествии мы воспользуемся классом Dictionary<TKey, TValue>, чтобы овладеть мощью хеш-таблиц. Приготовьтесь быть очарованным примером, демонстрирующим их магию:

// Creating a spellbook collection using a hash table
Dictionary<string, string> spellbook = new Dictionary<string, string>();

// Adding powerful spells to the spellbook
spellbook["Fireball"] = "Unleashes a blazing fireball upon your enemies.";
spellbook["Healing Touch"] = "Restores health and vitality to the wounded.";
spellbook["Invisibility"] = "Allows the caster to vanish from sight.";

// Accessing spells using their names
string fireballSpell = spellbook["Fireball"]; // Retrieves the description of the Fireball spell

С классом Dictionary<TKey, TValue> вы можете использовать мистические силы хеш-таблиц. Эти структуры превосходны в сценариях, где необходим молниеносный поиск, что делает их идеальными для таких задач, как кэширование, индексирование или реализация ассоциативных массивов.

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

Наборы: раскрытие силы уникальных элементов

(Встроенный тип данных в .NET)

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

Dotnet предлагает класс HashSet<T>, чтобы привнести магию наборов в ваш код. Давайте погрузимся в пример, демонстрирующий их силу:

// Creating a set of magical ingredients
HashSet<string> magicalIngredients = new HashSet<string>();

// Adding unique elements to the set
magicalIngredients.Add("Dragon Scale");
magicalIngredients.Add("Unicorn Horn");
magicalIngredients.Add("Phoenix Feather");
magicalIngredients.Add("Dragon Scale"); // Ignored, as it's already in the set

// Checking if an element exists in the set
bool hasUnicornHorn = magicalIngredients.Contains("Unicorn Horn"); // True
bool hasMermaidScale = magicalIngredients.Contains("Mermaid Scale"); // False

С классом HashSet<T> вы будете использовать всю мощь наборов в своих приложениях dotnet. Наборы идеально подходят для сценариев, в которых вам необходимо обеспечить уникальность или выполнить тесты на принадлежность с исключительной скоростью.

Выбор правильной структуры данных

В огромном царстве структур данных выбор правильной структуры для ваших конкретных потребностей иногда может показаться прохождением по лабиринту возможностей. Вот несколько советов и приемов, которые помогут вам в поисках идеальной структуры данных.

Проанализируйте свои требования

Прежде чем выбрать структуру данных, тщательно проанализируйте свои требования. Учитывайте такие факторы, как ожидаемый размер набора данных, тип операций, которые вы будете выполнять (вставка, удаление, поиск), а также требуемая сложность времени и пространства. Этот анализ поможет вам сузить круг вариантов и выбрать наиболее подходящую структуру.

Знай свои сильные стороны

Каждая структура данных имеет свои сильные и слабые стороны. Например, массивы превосходны при произвольном доступе, а связанные списки — при вставках и удалениях. Поймите сильные стороны каждой структуры и сопоставьте их с вашим конкретным вариантом использования, чтобы максимизировать эффективность.

Рассмотрите компромиссы

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

Используйте встроенные классы

Воспользуйтесь преимуществами встроенных структур данных, доступных в ядре dotnet, таких как списки, словари и наборы. Эти классы были оптимизированы и протестированы, что делает их надежным выбором для распространенных сценариев.

Изучите сторонние библиотеки

Dotnet core также предлагает широкий спектр сторонних библиотек, обеспечивающих дополнительные реализации структуры данных. Изучите такие библиотеки, как C5, DataStructures.NET или priority-queue-dotnet, чтобы найти специализированные структуры, соответствующие вашим потребностям.

Вот и все! Вы дошли до конца.

Помните, что освоение структур данных похоже на приобретение сверхспособностей для вашего путешествия по программированию. Итак, продолжайте учиться, экспериментировать и исследовать волшебный мир dotnet.

Подпишитесь на меня

Пол Ар

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

Ознакомьтесь с другими моими статьями