Блок задач

1. Разгон

Сложность 2

Задача «Двусвязный список»

Реализовать на языке C модуль для работы с двусвязным списком элементов.

Примерный интерфейс:

#include <stdbool.h> // bool
#include <stddef.h>  // size_t

void * dlist_create(size_t itemSize);
void dlist_destroy(void * dlist, void(*destroy)( void * ));

void * dlist_init(void * dlist, size_t itemSize);
void dlist_clear(void * dlist, void(*destroy)( void * ));

size_t dlist_count(const void * dlist);
void * dlist_item(void * dlist, size_t i);
void * dlist_append(void * dlist);
void * dlist_prepend(void * dlist);
void dlist_removeFirst(void * dlist, void(*destroy)( void * ));
void dlist_removeLast(void * dlist, void(*destroy)( void * ));

size_t dlist_first(const void * dlist);
size_t dlist_last(const void * dlist);
size_t dlist_next(const void * dlist, size_t item_id);
size_t dlist_prev(const void * dlist, size_t item_id);
size_t dlist_stop(const void * dlist);
void * dlist_current(const void * dlist, size_t item_id);
void * dlist_insertAfter(void * dlist, size_t item_id);
void * dlist_insertBefore(void * dlist, size_t item_id);
void dlist_erase(void * dlist, size_t item_id, void(*destroy)( void * ));
  • dlist_create -- Создать новый пустой двусвязный список. Размер элемента -- itemSize байт.
  • dlist_destroy -- Удалить существующий двусвязный список. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
  • dlist_init -- Инициализировать двусвязный список. Размер элемента -- itemSize байт.
  • dlist_clear -- Удалить все элементы из двусвязного списка. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
  • dlist_count -- Количество элементов в списке.
  • dlist_item -- Получить элемент по индексу в списке.
  • dlist_append -- Добавить элемент в хвост двусвязного списка. В случае успеха, функция возвращает указатель на добавленный элемент, иначе -- NULL.
  • dlist_prepend -- Добавить элемент в голову двусвязного списка. В случае успеха, функция возвращает указатель на добавленный элемент, иначе -- NULL.
  • dlist_removeFirst -- Удалить элемент из головы двусвязного списка. Если указана функция destroy, то вызвать её для удаляемого элемента.
  • dlist_removeLast -- Удалить элемент из хвоста двусвязного списка. Если указана функция destroy, то вызвать её для удаляемого элемента.
  • dlist_first -- Идентификатор для первого элемента из двусвязного списка. Идентификатор может стать невалидным при модификации списка.
  • dlist_last -- Идентификатор для последнего элемента из двусвязного списка. Идентификатор может стать невалидным при модификации списка.
  • dlist_next -- По идентификатору текущего элемента получить идентификатор следующего элемента списка.
  • dlist_prev -- По идентификатору текущего элемента получить идентификатор предыдущего элемента списка.
  • dlist_stop -- Идентификатор, получаемый при попытке обратиться к элементу за пределами списка.
  • dlist_current -- Получить указатель на элемент списка по его идентификатору.
  • dlist_insertAfter -- Вставка нового элемента списка после указанного по идентификатору. В случае успеха, функция возвращает указатель на вставленный элемент, иначе -- NULL.
  • dlist_insertBefore -- Вставка нового элемента списка перед указанным по идентификатору. В случае успеха, функция возвращает указатель на вставленный элемент, иначе -- NULL.
  • dlist_erase -- Удаление элемента по его идентификатору. Если указана функция destroy, то вызвать её для удаляемого элемента. После удаления элемента из списка, идентификаторы любых элементов из этого массива могут стать невалидным.