Информатика ← ЛабораторныеЛабораторная работа №26

Абстрактные типы данных. Рекурсия. Модули

Задание

Составить и отладить модуль определения и модуль реализации по заданной схеме модуля определений для абстрактного типа данных (стека, очереди или дека в зависимости от варианта задания). Составить программынй модуль, сортирующий экземпляр указанного абстрактного типа данных заданным методом, используя только операции, импортированные из модуля определений.

Примечания

  • Стек, очередь и дек отображаются на массив.
  • В программе по возможности должна быть использована рекурсия.
  • Метод сортировки реализовать с использованием указанной вспомогательной процедуры.
  • Использование итераторов для навигации приветствуется.

Варианты АТД

  1. Стек.
  2. Очередь.
  3. Дек.

Варианты процедур и методов сортировки

  1. Поиск и удаление максимального (для дека и стека) или минимального (для очереди) элемента. Сортировка линейным выбором.
  2. Вставка элемента в стек, дек или очередь упорядоченные по возрастанию с сохранением порядка. Сотрировка простой вставкой.
  3. Конкатенация двух стеков, деков или очередей. Быстрая сортировка Хоара.
  4. Поиск в стеке, деке или очереди двух элементов, идущих подряд, первый из которых больше второго. Если такие элементы найдены, их перестановка. Сортировка методом пузырька.
  5. Слияние двух стеков, деков или очередей, упорядоченный по возрастанию с сохранением порядка. Сортировка слиянием.
  6. Поиск в стеке, очереди или деке первого от начала элемента, который меньше своего непосредственного предшественника. Если такой элемент найден, смещение его к началу до тех пор, пока он не станет первым или больше своего предшественника. Вариант метода вставки.

Пример

Модуль определения для стека:

#ifndef _lab25_udt_h_
#define _lab25_udt_h_

#include 

typedef struct {
  key_type key;
  value_type value;
} data_type;

typedef struct { ... } udt;

void udt_create(udt *);
bool udt_is_empty(const udt *);
void udt_push_front(udt *, const data_type *);
void udt_pop_front(udt *);
const data_type *udt_front(const udt *);
void udt_print(const udt *);
size_t udt_size(const udt *);

#endif

Ссылки

Оригинальный текст лабораторной