Двунаправленный список

Этот проект выполнен в рамках учебного курса "Основы программирования".

Содержание

Типы

Название	Описание
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_.