Разработка и реализация класса линейного списка (Лабораторная работа № 1)

Разработка и реализация класса линейного списка №1

Разработать класс двунаправленного списка в соответствии со следующими требованиями.

Характеристика закрытого раздела списка.

ü  Тип узла определить как list_node.

ü  Поле данных узла списка называется key. Тип поля key определить, как value_type в открытом разделе класса.

ü  Узел также содержит два указателя: на следующий элемент списка next и на предыдущий элемент списка prev.

ü  Указатели на начало и конец списка (хвост tail и голову head). Узел хвоста является фиктивным, т.е. не содержит данных и применяется для проверки конца списка. Поэтому последним действительным элементом не пустого списка является узел, расположенный перед хвостом.

ü  Счетчик количества элементов N  списка. Тип поля N  определить, как index  в открытом разделе класса.

ü  Указатель на текущий элемент списка curt и его индекс cur_ind. Текущий указатель и его индекс в списке изменяются при обходе узлов списка с помощью функций открытого раздела fovard() и back().

Интерфейс класса списка.

ü  Тип элемента данных узла списка value_type при помощи директивы typedef.

ü  index тип представляющий индекс элемента (узла) линейного списка

ü  Конструктор по умолчанию: List().

ü  Функция передвижения по списку: index  fovard(). Возвращает индекс следующего элемента списка и изменяет индекс current.

ü  Функция возвращает индекс предыдущего элемента списка index  back(). Возвращает индекс предыдущего  элемента списка и изменяет индекс current.

ü  Функция установки нового значения поля данных линейного списка:
bool  setKey(index  i, const value_type item), где item соответствующее значение.

ü  Функция проверки наличия значения в списке index   find( const value_type& item) const, где item значение. Функция возвращает индекс элемента списка, если значение элемента списка и значения item совпадают. Если ключ item не найден функция возвращает фиктивный индекс хвоста списка.

ü  Функция index  size() const  возвращает число элементов списка.

ü  Функция bool   ins_prev(index  i, const value_type& item) вставляет узел, содержащий значение item, перед узлом с индексом i. Если индекс выходит за пределы списка возвращает false.

ü  Функция bool   del_prev(index  i) удаляет узел перед узлом с индексом i. Если индекс выходит за пределы списка возвращает false. Функция устанавливает текущий указатель и его индекс на хвост списка.

ü  value_type get_item(index  i) const метод получения данных узла с индексом i.

ü  value_type get_cur() const метод получения данных текущего узла.

ü  index  get_cur_index() метод получения индекса текущего узла.

Перечень и описание внешних функций (утилит).

ü  Функция вывода списка на экран void PrintList (const List& l).

ü  Функция сортировки списка на основании функции сравнения void SortList (List& l, bool (compare*)( const List:: value_type& val1, const List:: value_type& val21 ), где
bool (*compare)( const List:: value_type& val1, const List:: value_type& val2 ) указатель на метод сравнения данных.узлов списка.

Примечание: Интерфейсную функцию ввода данных списка реализовывать не следует. Список заполнять инициализированными объектами, объявленными в программе. 

Варианты заданий

Вариант задания определяет объект, хранящийся в узле списка. Список должен содержать не менее 7 элементов. Класс объекта должен иметь полный набор методов установки и получения данных (set и get). Функции сравнения объектов класса (greater), меньше (less) и (==) реализуются, как внешние. Логика сравнения остается на Ваше усмотрение.

Реализация функции сортировки списка.

Отчет о выполнении работы представляется в печатной форме и должен содержать:

1. Титульный лист (оформление стандартное);
2. Условие варианта;
3. Комментарии к работе, если необходимо;
4. Код программы;
5. Результаты.

Результаты должны содержать примеры использования всех метод класса списка и его утилит. Список следует отсортировать в порядке возрастания и убывания.

1.  Вариант 

·  номер аптеки;

·  адрес;

·  количество лекарств;

·  массив 5 записей с полями:

      - название лекарства;

      - цена.