Двунаправленный список
Этот проект выполнен в рамках учебного курса "Основы программирования".
Содержание
Типы
Название | Описание |
---|---|
list_t | Непрозрачный тип представления списка. Все функции данной библиотеки принимают либо возвращают указатели на переменные этого типа. Программист не должен самостоятельно изменять содержимое памяти, по этим адресам. |
lst_iter_t | Непрозрачный тип представления двунаправленных итераторов списка. Функции с префиксом lst_iter_ принимают значения этого типа. |
lst_elem_t | Тип элементов, хранящихся в списке. Работоспособность этой библиотеки проверена исходя, что этот тип является целочисленным. TODO: организовать работу библиотки при общем типе. |
Интерфейс
Библиотека предоставляет интерфейс для работы со списком. Реализации этих функций находится в файле list.c
Название | Описание | Сложность | Ответсвенный | Готовность |
---|---|---|---|---|
lst_new | Создаёт новый список | const | Гурьев | Протестирована |
lst_free | Освобождает память, занимаемую списком | O(n) | Гурьев | Протестирована |
lst_append | Добавляет элемент в конец | const | Макаровская | Протестирована |
lst_insert_before | Добавляет элемент перед тем, на который указывает итератор | const | Табалин | Не реализована |
lst_insert_range | Копирует в список элементы массива | O(n) | — | Запланирована |
lst_insert_list | Копирует в список элементы из другого списка | O(n) | — | Запланирована |
lst_delete | Удаляет элемент, на который указывает итератор | const | Копцева | Не проходит тесты |
lst_clear | Удаляет все элементы в списке | O(n) | Копцева | Протестирована |
lst_empty | Проверяет, не является ли список пустым | const | — | Запланирована |
lst_size | Вычисляет размер списка | O(n) | Руденко | Протестирована |
lst_index | Возвращает элемент с заданным номером | O(n) | Табалин | Протестирована |
lst_repack | Переупаковывает список | O(n) | Гурьев | Нет тестов |
Следующие функции предназначены для работы с итераторами. Их определения можно найти в файле list.c. Примечание: алгоритмическая сложность этих функций постоянна. |
Название | Описание | Ответсвенный | Готовность |
---|---|---|---|
lst_iter_next | Возвращает итератор на следующий элемент списка | Табалин | Протестирована |
lst_iter_prev | Возвращает итератор на предыдущий элемент списка | Табалин | Нет тестов |
lst_iter_is_null | Проверяет, является ли итератор нулевым | Табалин | Протестирована |
lst_iter_deref | Возвращает значение элемента, на который указывает итератор | Табалин | Протестирована |
lst_iter_by_index | Возвращает итератор, на элемент с заданным номером | Табалин | Протестирована |
Алгоритмы
Нижеследующие функции реализуют стандартные алгоритмы для нашего списка. Их реализации хранятся в файле algorithm.c.
Название | Описание | Сложность | Ответсвенный | Готовность |
---|---|---|---|---|
lst_binsearch | Выполняет биарный поиск | O(log n) | Гурьев | Отказались |
lst_count | Возвращает количество вхождений заданного значения | O(n) | Чжун | Протестирована |
lst_copy | Возвращает копию списка | O(n) | Макаровская | Протестирована |
lst_compare | Сравнивает два списка | O(n) | Гурьев | Не реализована |
lst_find | Возвращает итератор на первое вхождение значения | O(n) | Табалин | Протестирована |
lst_for_each | Замещает каждый элемент в списке результатом вызова функции | O(n) | Гурьев | Протестирована |
lst_max | Возвращает наибольшее значение из списка | O(n) | Копцева | Протестирована |
lst_min | Возвращает наименьшее значение из списка | O(n) | Копцева | Протестирована |
lst_random_shuffle | Переставляет элементы в случайном порядке | O(n) | Руденко | Отказались |
lst_replace | Заменяет все вхождения одного значения на другое | O(n) | Чжун | Протестирована |
lst_remove | Удаляет из списка все вхождения заданного значения | O(n) | Чжун | Не реализована |
lst_sort | Сортирует список | O(n log n) | Руденко | Не реализована |
lst_swap | Обменивает два списка | const | Макаровская | Не реализована |
Тесты
В этом разделе содержатся описания работы всех функций из этой библиотеке. Ко многим из них преведены примеры их использования. Эти примеры одновременно являются и тестами. Чтобы запутить их, выполните команду make
в каталоге с репозиторием. По этой команде запустится скрипт ./doctest.py
, который на основе данного файла сформирует код на Си, и скомпилирует его. Если все тесты будут пройдены,выводится соответствуещее сообщение, иначе будут показаны различия между выводом программы и приведёнными здесь результатами.
Далее содержатся директивы doctest.py. Каждая директива занимает ровно одну строчку и представляет собой HTML комментарий вида <!-- doctest: команда -->
. Кроме директивы в строчке ничего не должно быть. Получив команду, doctest.py ищет на следующей строчке первый, самый левый, блок кода и обрабатывает его согласно директиве. Подобнее см. doctest.py.
lst_new
list_t* lst_new(int)
Создаёт и инициализирует список и возвращает на него указатель. В случае нехватки памяти возвращается нулевой указатель. Параметр игнорируется.
Пример:
list_t* L;
if (!(L = lst_new(0))) {
/* ошибка при создании списка */
abort();
}
/* работаем со списком */
lst_free(L);
lst_free
void lst_free(list_t* lst)
Уничтожает список lst и освобождает память. Обязательно вызывайте эту функцию перед выходом из программы.
lst_append
int lst_append(list_t* lst, lst_elem_t el)
Вставляет элемент el в конец списка lst. В случае успеха возвращает ненулевое значение, иначе 0. Если произошли ошибки — список остаётся в корректном состоянии. Все итераторы списка остаются в валидном состоянии.
Список до: 96 78 84 61 57 30 43 50 71
Пример:
lst_append(L, 42);
lst_append(L, 13);
Результат: 96 78 84 61 57 30 43 50 71 42 13
lst_insert_before
int lst_insert_before(lst_iter_t it, lst_elem_t el)
Вставляет элемент el перед тем, на который указывает it. В случае успеха возвращает ненулевое значение, иначе 0. Итераторы, указывающие на элементы после it остаются валиднымы (включая it). Итераторы до it могут быть испорчены, но не далее некоторого количества.
Не реализована
Список до: 28 13 74 2 52 58 68 95 65
Пример:
lst_iter_t p = lst_find(L, 68);
lst_insert_before(p, 42);
p = lst_iter_by_index(L, 3);
lst_insert_before(p, 13);
Результат: 28 13 74 13 2 52 58 42 68 95 65
lst_delete
void lst_delete(lst_iter_t it)
Удаляет элемент, на который указывает it. it и некоторое количество итераторов после становятся недействительными. До it остаются валидными.
Список до: 64 54 89 76 52 71 4 23 24 52 94 69 29 22
Пример:
lst_delete(lst_find(L, 52));
lst_delete(lst_iter_by_index(L, 2));
lst_delete(lst_iter_by_index(L, 11));
Результат: 64 54 76 71 4 23 24 52 94 69 29
lst_clear
void lst_clear(list_t* lst)
Очищает список lst. После этой операции размер списка становится равным нулю, список можно заново использовать (как после lst_new. Обратите внимание, не освобождается вся память, занимаемая списком, чтобы уничтожить список используйте lst_free.
Тест пропускается из-за итераторов
Список до: 65 15 44 42 51 4 74 40 75
Пример:
lst_clear(L);
Результат:
lst_iter_by_index
lst_index
Список: 19 0 69 79 46 23 93 11 31 42 65 90 26 7 89
lst_index(L, 6) == 93;
lst_index(L, 11) == 90;
lst_count
Список: 37 13 78 78 13 29 78 6 13 51 90 32 13 95
lst_count(L, 13) == 4;
lst_count(L, 78) == 3;
lst_repack
Список: 20 88 70 63 5 21 19 89 47 94 87 9 55 79 62 93 97 34 16 61 72 12 38 31 15
lst_repack(L);
Результат: 20 88 70 63 5 21 19 89 47 94 87 9 55 79 62 93 97 34 16 61 72 12 38 31 15
lst_copy
lst_compare
lst_find
Список: 37 52 41 45 67 26
lst_iter_is_null(lst_find(L, 13)) == 1;
lst_iter_is_null(lst_find(L, 45)) == 0;
lst_for_each
Список: 56 15 69 24 16
lst_elem_t func(lst_elem_t l) {
return l + 1;
}
...
lst_for_each(L, func);
Результат: 57 16 70 25 17
lst_max
Список: 39 53 48 27 17 83 75 15 28
lst_max(L) == 83;
lst_min
Список: 39 53 48 27 17 83 75 15 28
lst_min(L) == 15;
lst_replace
Список: 35 60 69 4 69 82 42 69 90 32 87 69 76
lst_replace(L, 69, 42);
Результат: 35 60 42 4 42 82 42 42 90 32 87 42 76
lst_remove
Ещё не готова
Список: 66 42 56 42 29 1 73 42 97 34 42 63
lst_remove(L, 42);
Результат: 66 56 29 1 73 97 34 63
lst_sort
Ещё не готова
Список: 61 78 91 19 40 11 63 62 42 55 15 35
lst_sort(L);
Результат: 11 15 19 35 40 42 55 61 62 63 78 91
lst_size
Список: 72 64 62 75 20 15 68 64 74 57 16 24 84 97 43 54 92 26 27
lst_size(L) == 19;
Рекомендации по оформлению кода
- Разделяйте пробелом управляющие конструкции (такие как if/while/for) и скобку. Пробелы между круглыми скобками и их содержимым не ставьте. Открывающая фигурная скобка должна быть в конце строки после закрывающей круглой скобки и пробела. Всегда, когда это возможно, пишите составную инструкцию. Так будет проще модифицировать код, например, добавлять ещё какие-то действия.
if (условие) {
операторы
} else if (условие) {
операторы
} else {
операторы
}
- Однако после имени функции или макроса с параметрами пробел не ставится.
printf("Hello, world!");
- Длина строки в файле с кодом не более 80 символов.
- В качестве отступов — табуляция, впрочем, вы можете использовать и пробелы, для си это не важно.
- Имена типов, функций, переменных и пр. пишутся в нижнем регистре, имена макросов-констант — заглавными буквами. Слова разделяются нижним подчёркиванием. Имена, которые попадают в глобальную область видимости, предварять префиксом
lst_
.