Data Structures and Algorithms in C
1.0.0
Здесь вы найдете некоторые структуры данных и алгоритмы, реализованные в C. Эти алгоритмы в основном основаны на книге «Введение в алгоритмы Томаса Х. Кормена» .
Каждый модуль состоит из хотя бы одного файла заголовка (.h) и одного исходного файла, который содержит Code Corpus (.c). Чтобы использовать один из этих модулей, я предлагаю вам выполнить эти шаги:
/modules/modules/List ), который содержит исходный код .c File (например, List.c )/include/ folder, найдите файл заголовка (.h), который вам нужен (например, List.h ) и загрузите его.#include "foo.h" ). Большинство модулей включают, например, HashFunctions или Comparators или даже другие структуры данных. Найдите то, что нужно, и загрузите все файлы.#include "foo.h" если вы измените текущую структуру папки.Если вы клонируете всю папку, вы можете запустить:
make : это дополняет каждый модульmake run-tests : который компилирует каждый модуль и выполняет все тестыmake valgind-tests : который компилирует каждый модуль и выполняет все тесты, используя Valgrind | Структура данных | Определение |
|---|---|
| Bloom Filter | Bloom Filter-это космическая вероятностная структура данных, задуманная Бертоном Ховардом Блумом в 1970 году, которая используется для проверки того, является ли элемент элементом набора. Неверные позитивные совпадения возможны, но ложные негативы не являются - другими словами, запрос возвращает либо «возможно в наборе», либо «определенно не в комплекте». Элементы могут быть добавлены к набору, но не удалены (хотя это можно решить с помощью варианта фильтра с подсчетом Bloom); Чем больше элементов добавлены, тем больше вероятность ложных срабатываний. |
| Красное черное дерево | Красное дерево-это своего рода бинарное бинарное дерево бинарного поиска. Каждый узел хранит дополнительный бит, представляющий «цвет» («красный» или «черный»), используемый для обеспечения того, чтобы дерево оставалось сбалансированным во время вставки и удалений. Когда дерево модифицировано, новое дерево переставляется и «перекрашивается», чтобы восстановить раскраски, которые ограничивают, насколько неуравновешенным дерево может стать в худшем случае. Свойства спроектированы так, что эта перестройка и повторное разрыв можно выполнить эффективно. Перебалансирование не идеально, но гарантирует поиск во время O (logn) , где n-количество узлов дерева. Операции внедрения и удаления, наряду с перестройкой дерева и повторным резоляции, также выполняются во время O (logn) . |
| Связанный список | Связанный список - это линейная коллекция элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий. Это структура данных, состоящая из набора узлов, которые вместе представляют последовательность. |
| Очередь | Приоритетная очередь - это абстрактный тип данных, аналогичный регулярной очереди или структуре данных стека, в которой каждый элемент дополнительно имеет «приоритет», связанный с ним. В очереди приоритета элемент с высоким приоритетом обслуживается перед элементом с низким приоритетом. |
| Хэштаб с списком | Общая реализация очень простой хэштата с ключами и цепями. Реконструкция не предоставлена. |
| Хэштибл с красным черным деревом | Таким образом, мы находимся из таблицы, в которой каждый ряд имеет указатель на красное черное дерево, мы получаем вышеупомянутые лучшие сложности и в то же время избегая слишком большого количества столкновений. |
| Хэштаб с ведрами до красного черного дерева | Хэштата состояла из ведра указателей на красные черные деревья |
| Maxheap | Макс-HEAP-это полное бинарное дерево, в котором значение в каждом внутреннем узле больше или равно значениям у детей этого узла. Картирование элементов кучи в массив тривиально: если узел сохраняется индекс k, то его левый ребенок хранится при индексе 2K+1 и его правого ребенка в индексе 2K+2. |
| Disjointset | Структура данных Disecoint-SET, также называемая структурой данных Union-Find или набором Merge-Find, представляет собой структуру данных, в которой хранится набор непересекающихся наборов. Эквивалентно, он хранит раздел установленного на подмножествам. Он обеспечивает операции для добавления новых наборов, слияния наборов (замены их союзом) и поиска представителя набора. Последняя операция позволяет эффективно узнать, находятся ли какие -либо два элемента в одних и тех же или разных наборах. |
| Планировщик работы с потоками | Планировщик многопоточного задания с использованием Unix Pthreads. |
| Алгоритм | Определение |
|---|---|
| Кучи | Heapsort-это алгоритм сортировки на основе сравнения. Heapsort можно рассматривать как улучшенную сортировку выбора: как сортировка выбора, Heapsort делит свой вход на отсортированную и несортированную область, и он итеративно сокращает несортированную область, извлекая из него самый большой элемент и вставляя ее в отсортированную область. В отличие от сортировки выбора, Heapsort не тратит время при сканировании линейного времени несортированной области; Скорее, сортировка кучи поддерживает несортированную область в структуре данных кучи, чтобы быстрее найти самый большой элемент на каждом этапе. |
| Quicksort | QuickSort - это эффективный алгоритм сортировки. Разработанный британским компьютерным ученым Тони Хоаром в 1959 году и опубликованный в 1961 году, он по -прежнему обычно используется алгоритм для сортировки. При хорошем внедрении он может быть несколько быстрее, чем слияние и примерно в два или три раза быстрее, чем Heapsort. |
| Утилита | Определение |
|---|---|
| Компараторы | Функции, которые сравнивают два значения и возвращают 0,> 0, <0 |
| Хэш -функции | Строковые хэш -функции |
Для тестирования созданных модулей я использовал библиотеку acutest.h .
Больше информации о библиотеке Acutest
Создание простых программ (основные функции) в качестве примеров для всех модулей.
☑ Некоторые модули были сделаны в сотрудничестве с Myrto Iglezou . ☑
© Konstantinos nikoletos | 2021
