Data Structure

Словарь (map) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данные. Все данные хранятся в виде пар ключ-значение. Доступ к элементам данных осуществляется по ключу. Ключ всегда должен быть уникальным в пределах одного словаря, данные могут дублироваться при необходимости. У данной структуры есть и другие часто встречающиеся названия: ассоциативный массив или Dictionary. Принцип работы словаря схож с камерой хранения: есть ячейка, в которой может храниться что угодно, но доступ к этой ячейке осуществляется по уникальному номеру, благодаря чему ее всегда легко найти. Давайте рассмотрим пример реализации словаря на языке C#.

На рисунке ниже представлена схематичная структура словаря.

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

1. Add — добавление нового элемента с уникальным ключом.

2. Remove — удаление элемента по ключу.

3. Update — изменить хранимое значение по ключу.

4. Get — получить хранимое значение по ключу.

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

Теперь рассмотрим программный код.

Элемент словаря

Объявим класс словаря, его свойства и реализуем основные операции

Теперь проверим работу словаря обратившись к нему

Ну и наконец запустим приложение и посмотрим результат работы на консоли

Заключение

На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется Dictionary. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.

Источник: https://shwan.ru/map/

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

На рисунке ниже схематически представлены два множества A и B, а также основные операции: объединение, пересечение, разность.

Давайте подробнее рассмотрим все наиболее часто встречающиеся операции над множествами:

1. Add — добавление элемента. Если такой элемент уже присутствует, то он не будет добавлен.

Remove — удаление элемента из множества.

2. Union — объединение множеств. Создается новое множество, включающее в себя все элементы из множества А и множества В. Если элемент содержится в обоих множествах, он будет добавлен однократно.

3. Difference — разность множеств. Создается новое множество, включающее в себя все элементы множества А, которые не входят в множество В.

4. Intersection — пересечение множеств. Создается новое множество, включающее в себя все элементы входящие одновременно и в множество А, и в множество В.

5.Subset — проверка на подмножество. Чтобы быть подмножеством, все элементы множества А должны содержаться в множестве В. Тогда множество А является подмножеством множества В.

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

Реализация класса Set.cs

Для начала объявим класс и его свойства

Теперь реализуем операции добавления и удаления элементов множества

Теперь реализуем операцию объединения множеств

Реализуем операцию пересечения множеств

Реализуем операцию разности множеств

Ну и наконец сделаем проверку на подмножество и реализуем интерфейс IEnumerable

Теперь проверим работу нашего класса

В результате получаем следующий вывод на экран

Заключение

На платформе .NET все операции над множествами уже оптимально реализованы в рамках LINQ запросов, поэтому реализовывать самостоятельно нет необходимости. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.

Источник https://shwan.ru/set/

Связный список (Linked List) представляет собой коллекцию связанных элементов, которые содержат в себе хранимые данные, а также ссылку на связанные с ним элементы (один или несколько). Основным преимуществом данной структуры данных перед обычным массивом является ее динамичность — возможность легко менять количество элементов. Давайте рассмотрим пример реализации на языке C# элементарного односвязного списка.

Для начала необходимо упомянуть, что существует несколько видов связных списков. Вот наиболее часто используемые из них:

1. Односвязный список

2. Двусвязный список

3. Кольцевой список

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

Элемент списка

Рассмотрим класс элемента связного списка. Для того, чтобы сделать его более универсальным мы используем Универсальный параметр T. Это позволит динамически указывать тип данных при использовании списка.

Список элементов

Теперь рассмотрим сам класс связного списка. Для него мы также используем Универсальный (generic) тип T, а также реализуем интерфейс IEnumerable, чтобы в дальнейшем было удобно перебирать элементы списка с помощью цикла foreach. Выделим основные необходимые свойства класса:

Теперь реализуем метод добавления данных в коллекцию

Удаление данных из коллекции

Ну и наконец вспомогательные методы для полной очистки связного списка и перебора элементов в цикле

Использование

Теперь нам остается проверить работу нашего списка. Для этого создадим несколько элементов и проверим работу списка.

В итоге получаем следующий вывод на консоль

Заключение

Здесь представлена элементарная реализация данной динамической структуры данных. На практике она уже реализована намного лучше внутри платформы .NET в виде списка List<T>, но для того, чтобы понять внутреннюю структуру лучше рассматривать более простые примеры. Источник https://shwan.ru/linked-list/