Выполнено студентом группы ИУ8-23 Тихомировым Никитой
Задача: найти на GitHub репозитории с кодом, соответствующим таким структурам данных как
- Дерево
- Очередь
- Список
- Множество
Для каждого из них найти основные действия (перечислены на лекциях).
Решение: Были найдены три проекта, удовлетворяющие условию задания, первый реализует первые три структуры, а ещё два - последнюю. Два репозитория представлены для языка C++, один - для языка Go. Приведены ссылки на проекты, заголовочные файлы и файлы реализации. Стоит отметить, что все проекты реализуют "структуры ради структур" - то есть являются скорее библиотеками, чем решениями каких-то прикладных задач. Причина такого выбора примеров - более качественная реализация (структура реализуется программистом лучше, если её реализация и является основной задачей), простота нахождения мной на GitHub, лаконичность проектов, а также гарантия того, что структура будет реализована - то есть не будет взята какая-нибудь другая библиотека или вообще класс из встроенной библиотеки.
Функционал дерева ограничивается добавлением элементов и проверкой значения на существование поэтому некоторые основные методы дерева носят статус доступа private. Но, тем не менее, это всё ещё дерево.
https://github.com/mandliya/algorithms_and_data_structures
https://github.com/mandliya/algorithms_and_data_structures/blob/master/include/binarySearchTree.h
(метод получения значения для сыновей и значения узла в данном примере не используется, есть только сами поля)
Нормальная человеческая очередь, первый пришёл - первый ушёл. Только вот разделения на файлы нет, всё в одном делается. Также, внезапно, обнуления не добавили.
(Тот же самый)
https://github.com/mandliya/algorithms_and_data_structures/blob/master/include/queue.h
Нормальная человеческая очередь, первый пришёл - первый ушёл. Только вот разделения на файлы нет, всё в одном делается. Также, внезапно, обнуления не добавили.
(Тот же самый)
https://github.com/mandliya/algorithms_and_data_structures/blob/master/include/queue.h
Двусвязный список, который умеет выталкивать и добавлять элементы и с головы, и с хвоста. Можно делать стэк, можно делать очередь. Снова всё в одном файле.
(Тот же самый)
https://github.com/mandliya/algorithms_and_data_structures/blob/master/include/list.h
Нормального множества(со всеми перечисленными операциями) я не нашёл, но нашёл два наполовину нормальных. Первое - множество с перегруженными математическими операциями, всё реализовано в одном файле. Второе - множество со всеми остальными операциями (на языке Go) (математические также реализованы, но мне не понравилось)
https://github.com/karatach1998
https://github.com/karatach1998/SetLib/blob/master/SetLib/SetOrderedArray.h
Строки 93-96 - Математические операции пересечения, объединения, разности и симметрической разности.
Объявление:https://github.com/fatih/set/blob/master/set.go
Реализация: https://github.com/fatih/set/blob/master/set_nots.go