Блок задач

1. Разгон

Сложность 2

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

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

Строго заданный интерфейс:

#include <stddef.h>  // size_t

static const size_t INVALID = ~((size_t)0);

void * slist_create(size_t itemSize);
void slist_destroy(void * slist, void(*destroy)( void * ));

void * slist_init(void * slist, size_t itemSize, void(*destroy)(void*));
void slist_clear(void * slist, void(*destroy)( void * ));

size_t slist_count(const void * slist);
void * slist_item(void * slist, size_t i);
void * slist_prepend(void * slist);
void slist_remove(void * slist, void(*destroy)( void * ));

size_t slist_first(const void * slist);
size_t slist_next(const void * slist, size_t item_id);
size_t slist_stop(const void * slist);
void * slist_current(const void * slist, size_t item_id);
void * slist_insert(void * slist, size_t item_id);
void slist_erase(void * slist, size_t item_id, void(*destroy)( void * ));
  • INVALID -- код ошибки для невалидных ситуаций.
  • slist_create -- Создать новый пустой односвязный список. Размер элемента -- itemSize байт.
  • slist_destroy -- Удалить существующий односвязный список. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
  • slist_init -- Инициализировать односвязный список новыми параметрами. Если slist содержит элементы, то сначала удалить все элементы, потом инициализировать односвязный список с учетом новых параметров. Размер элемента -- itemSize байт. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
  • slist_clear -- Удалить все элементы из односвязного списка. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
  • slist_count -- Количество элементов в списке. В случае, если slist равен NULL, возвращает INVALID константу.
  • slist_item -- Получить элемент по индексу в списке.
  • slist_prepend -- Добавить элемент в голову односвязного списка. В случае успеха, функция возвращает указатель на добавленный элемент, иначе -- NULL.
  • slist_remove -- Удалить элемент из головы односвязного списка. Если указана функция destroy, то вызвать её для удаляемого элемента.
  • slist_first -- Идентификатор для первого элемента из односвязного списка. Идентификатор может стать невалидным при модификации списка.
  • slist_next -- По идентификатору текущего элемента получить идентификатор следующего элемента списка.
  • slist_stop -- Идентификатор, получаемый при попытке обратиться к элементу за пределами списка.
  • slist_current -- Получить указатель на элемент списка по его идентификатору.
  • slist_insert -- Вставка нового элемента списка после указанного по идентификатору. Когда список пустой, для успешной вставки элемента в качестве item_id должен указываться идентификатор, возвращаемый функцией slist_stop. В остальных случаях, item_id должен однозначно соответствовать элементу списка. В случае успеха, функция возвращает указатель на вставленный элемент, иначе -- NULL.
  • slist_erase -- Удаление элемента по его идентификатору. Если указана функция destroy, то вызвать её для удаляемого элемента. После удаления элемента из списка, идентификаторы любых элементов из этого массива могут стать невалидным.
//Пример использования
#include <string.h>
#include <assert.h>
#include <math.h>

#include "slist.h"

typedef struct {
    int array[8];
    float d_variable;
} Value;

int main(int argc, char* argv[])
{
    //Создаем односвязный список с элементами типа Value;
    void* slist = slist_create(sizeof(Value));

    assert(0 == slist_count(slist));
    assert(slist_stop(slist) == slist_first(slist));

    //Создаем объект для односвязного списка
    Value value = { {1, 2, 3, 4, 5, 6, 7, 8}, 0.f };

    //Добавляем новый элемент в односвязный список
    Value* insertedValue = (Value*)slist_prepend(slist);

    //Инициализируем добавленный элемент
    *insertedValue = value;

    Value* item = (Value*)slist_item(slist, 0);

    for (size_t i = 0; 8 > i; ++i) {
        assert(item->array[i] == value.array[i]);
    }

    assert(fabsf(item->d_variable - value.d_variable) < 1e-10f);
    assert(NULL == slist_item(slist, 1));

    assert(slist_next(slist, slist_first(slist)) == slist_stop(slist));

    slist_destroy(slist, NULL);

    return 0;
}