Этот проект выполнен в рамках учебного курса "Основы программирования".
| Название | Описание |
|---|---|
| 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.
list_t* lst_new(int)
Создаёт и инициализирует список и возвращает на него указатель. В случае нехватки памяти возвращается нулевой указатель. Параметр игнорируется.
Пример:
list_t* L;
if (!(L = lst_new(0))) {
/* ошибка при создании списка */
abort();
}
/* работаем со списком */
lst_free(L);void lst_free(list_t* lst)
Уничтожает список lst и освобождает память. Обязательно вызывайте эту функцию перед выходом из программы.
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
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
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
void lst_clear(list_t* lst)
Очищает список lst. После этой операции размер списка становится равным нулю, список можно заново использовать (как после lst_new. Обратите внимание, не освобождается вся память, занимаемая списком, чтобы уничтожить список используйте lst_free.
Тест пропускается из-за итераторов
Список до: 65 15 44 42 51 4 74 40 75
Пример:
lst_clear(L);Результат:
Список: 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;Список: 37 13 78 78 13 29 78 6 13 51 90 32 13 95
lst_count(L, 13) == 4;
lst_count(L, 78) == 3;Список: 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
Список: 37 52 41 45 67 26
lst_iter_is_null(lst_find(L, 13)) == 1;
lst_iter_is_null(lst_find(L, 45)) == 0;Список: 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
Список: 39 53 48 27 17 83 75 15 28
lst_max(L) == 83;Список: 39 53 48 27 17 83 75 15 28
lst_min(L) == 15;Список: 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
Ещё не готова
Список: 66 42 56 42 29 1 73 42 97 34 42 63
lst_remove(L, 42);Результат: 66 56 29 1 73 97 34 63
Ещё не готова
Список: 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
Список: 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_.