Целью лабораторной работы является изучение основных АТД и приобретение навыка их реализации на различных структурах данных.

Требования к содержанию, оформлению и порядку выполнения

В содержательной части отчета по выполнению лабораторной работы требуется привести описание алгоритмов, разработанных согласно своему варианту, и сделать вывод о преимуществах и недостатках использования различных СД. Алгоритмы рекомендуется оформлять с помощью блок-схем.

Теоретическая часть

Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.2.4.1-2.4.6.

Общая постановка задачи

Требуется разработать алгоритмы, реализующие операции заданного АТД, при этом использовать заданную СД. Варианты заданий представлены в таблице в следующем разделе.

В качестве дополнительных заданий рекомендуется программно реализовать разработанные алгоритмы.

Список индивидуальных данных

В таблице Л2.1 приведены варианты заданий. Каждая строка таблицы соответствует варианту. Например, в первом варианте требуется разработать алгоритмы операций TOP(S) и POP(S) АТД стек, при этом стек должен быть реализован с помощью массива.

Таблица Л2.1

Пример выполнения работы

Рассмотрим 30 вариант. В данном варианте требуется разработать алгоритмы выполнения операций ENQUEUE(x,Q) и DEQUEUE(Q) АТД «Очередь», при этом следует использовать указатели.

Как было отмечено в разд.2.4.6, очередь представляет собой специальный вид списка. Оператор ENQUEUE(x,Q) вставляет элемент x в конец очереди Q. С помощью операторов списка этот оператор может быть реализован следующим образом: INSERT(x, NEXT(LAST(Q),Q), Q). Оператор DEQUEUE(Q) удаляет первый элемент очереди Q. C помощью операторов списка данный оператор может быть реализован следующим образом: DELETE(FIRST(Q),Q).

Реализация списка на указателях проиллюстрирована на рис. 2.14. Алгоритмы операторов списка INSERT и DELETE представлены блок-схемами на рис. 2.15 и 2.16 соответственно. Данные алгоритмы могут быть использованы для реализации операторов очереди ENQUEUE и DEQUEUE. Однако, очередь представляет собой частный случай списка: вставка элемента происходит всегда в конец списка, а удаление – сначала. Поэтому эффективнее реализовать очередь в виде схемы, представленной на рис. Л2.1.

Из рисунка видно, что в структуре очереди Q хранится указатель как на первый элемент списка (поле Firstelem), так и на последний (поле Lastelem). Число элементов очереди сохраняется в поле Size. Очередь, изображенная на рис.Л2.1, состоит из трех элементов.

При такой реализации очереди алгоритм операции ENQUEUE(x,Q) состоит в следующем:

1. Создать новый элемент, на который указывает ячейка n.

2. В новом элементе поле element инициализировать значением x, а поле next – значением nil.

3. Если число элементов очереди не равно нулю (в структуре очереди поле Lastelem не равно nil или же поле Size не равно нулю), то полю next последнего элемента очереди присвоить значение n.

4. В структуре очереди полю Lastelem присвоить значение n, и увеличить значение поля Size на единицу.

Данный алгоритм представлен блок-схемой на рис.Л2.2.

Алгоритм операции DEQUEUE(Q) состоит в следующем:

Если очередь пуста (в структуре очереди поле Firstelem равно nil или же поле Size равно нулю), то выдать соответствующее предупреждение и закончить операцию, иначе выполнить следующие действия:

1. Запомнить указатель на первый элемент очереди в переменной r.

2. В структуре очереди полю Firstelem присвоить значение указателя на второй элемент очереди.

3. Освободить память, на которую ссылается указатель r.

4. В структуре очереди уменьшить значение поля Size на единицу.

Данный алгоритм представлен блок-схемой на рис.Л2.3.

Контрольные вопросы к защите

1. Понятие типа данных.

2. Понятие АТД.

3. Понятие СД.

4. Механизмы агрегирования ячеек (массивы, записи, файлы).

5. Указатели.

6. АТД список.

7. Операторы списка.

8. Реализация списков с помощью массивов.

9. Реализация списков с помощью указателей.

10. АТД стек.

11. Операторы стека.

12. АТД очередь.

13. Операторы очереди.

14. Проанализируйте преимущества и недостатки различных способов реализации списков.

Способ оценки результатов

Критерии оценки результатов совпадают с критериями, определенными при описании лабораторной работы №1 в разделе «Способ оценки результатов».