Задание №1. Реализация универсальных контейнеров на языке С
Цель задания
Данное задание является вводным и обязательным для исполнения для всех студентов (данное задание является переработкой задания http://ccfit. nsu. ru/~deviv/courses/oop/tasks/task1-1.doc).
Задание преследует несколько целей:
- Продемонстрировать модульное программирование Продемонстрировать разделение реализации и интерфейса Закрепление алгоритмов построения стандартных контейнеров
Одним из особенностей данной задачи является то, что она должна быть реализованна средствами структурного программирования на языке C++. Это означает, что вы не должны пользоваться средствами объектного и объектно-ориентированного программирования C++.
Постановка задачи
Необходимо реализовать три контейнера:
- Линейный двусвязанный список Динамический массив Ассоциативный массив
Первые два контейнера должны иметь единый интерфейс (другими словами, открытый заголовочный файл для них будет один и тот же). Структрно, каждый из этих модулей должен выглядеть таким образом:
Эти модуля контейнера должны иметь следующий интерфейс (container. h):
typedef void(*cont_handle)(void* data);
void* cont_allocate(); // Создает пустой контейнер
void cont_release(void* cont); // Удаляет контейнер
void cont_add(void* cont, void* data); // Добавляет элемент в конец контейнера
void cont_insert(void* cont, int pos, void* data); // Вставляет злемент в позицию pos
int cont_size(void* cont); // Возвращает размер контейнера
void* cont_get(void* cont, int pos); // Возвращает данные в позиции pos
void* cont_replace(void* cont, int pos, void* data); // Заменяет данные в позиции pos. Возвращает старые данные.
void* cont_remove(void* cont, int pos); // Удаляет данные из позиции pos. Возвращает удаленные данные.
void cont_foreach(void* cont, cont_handle proc); // Перебирает все элементы контейнера по порядку.
void cont_foreach_reverse(void* cont, cont_handle proc); // Перебирает все элементы контейнера в обратном порядке.
Третий контейнер – ассоциативный массив, является надстройкой над одним из первых двух. Его реализация должна использовать интерфейс (только интерфейс!!!) основного контейнера для реализации хранения данных.
Модуль ассоциативного массива должен иметь следующий интерфейс (map. h):
typedef void(*assoc_handle)(void* key, void* data);
void* assoc_allocate(); // Создает пустой контейнер
void assoc_release(void* cont); // Удаляет контейнер
void* assoc_put(void* cont, void* key, void* data); // Добавляет элемент в конец контейнера. Возвращает старые данные, связанные с этим ключем.
int assoc_size(void* cont); // Возвращает размер контейнера
void* assoc_get(void* cont, void* key); // Возвращает ключ из позиции pos
void* assoc_get_key(void* cont, int pos); // Возвращает ключ из позиции pos
void* assoc_get_value(void* cont, int pos); // Возвращает значение из позиции pos
void* assoc_remove(void* cont, void* key); // Удаляет данные по ключу.
void assoc_foreach(void* cont, assoc_handle proc); // Перебирает все элементы контейнера по порядку.
void assoc_foreach_reverse(void* cont, assoc_handle proc); // Перебирает все элементы контейнера в обратном порядке.
Тестовый код должен проверять все методы контейнера и ассоциативного массива через прописанные интерфейсы. Желательно добавить стресс-тестирование контейнеров на большом объеме данных (миллионы объектов).
Дополнительно
Задавать функцию сравнения ключей при создании ассоциативного массива и хранить ассоциативный массив, используя хэш-таблицу или отсортированный массив (для эффективного поиска).
