Пример выполнения работы
Рассмотрим 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) состоит в следующем:
Создать новый элемент, на который указывает ячейка n.
В новом элементе поле element инициализировать значением x, а поле next – значением nil.
Если число элементов очереди не равно нулю (в структуре очереди поле Lastelem не равно nil или же поле Size не равно нулю), то полю next последнего элемента очереди присвоить значение n.
В структуре очереди полю Lastelem присвоить значение n, и увеличить значение поля Size на единицу.
Данный алгоритм представлен блок-схемой на рис.Л2.2.
Алгоритм операции DEQUEUE(Q) состоит в следующем:
Если очередь пуста (в структуре очереди поле Firstelem равно nil или же поле Size равно нулю), то выдать соответствующее предупреждение и закончить операцию, иначе выполнить следующие действия:
Запомнить указатель на первый элемент очереди в переменной r.
В структуре очереди полю Firstelem присвоить значение указателя на второй элемент очереди.
Освободить память, на которую ссылается указатель r.
В структуре очереди уменьшить значение поля Size на единицу.
Данный алгоритм представлен блок-схемой на рис.Л2.3.
Контрольные вопросы к защите
Понятие типа данных.
Понятие АТД.
Понятие СД.
Механизмы агрегирования ячеек (массивы, записи, файлы).
Указатели.
АТД список.
Операторы списка.
Реализация списков с помощью массивов.
Реализация списков с помощью указателей.
АТД стек.
Операторы стека.
АТД очередь.
Операторы очереди.
Проанализируйте преимущества и недостатки различных способов реализации списков.
Способ оценки результатов
Критерии оценки результатов совпадают с критериями, определенными при описании лабораторной работы №1 в разделе «Способ оценки результатов».
Лабораторная работа №3. СД для хранения графов
Целью лабораторной работы является изучение основных структур данных, использующихся для хранения графов, и приобретение навыка разработки программ, преобразующих одни структуры в другие.
Требования к содержанию, оформлению и порядку выполнения
В содержательной части отчета по выполнению лабораторной работы требуется привести описание алгоритма, разработанного согласно своему варианту, и сделать вывод о преимуществах и недостатках использования различных СД для хранения графов. Алгоритмы рекомендуется оформлять с помощью блок-схем.
Теоретическая часть
Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.2.4.7 и 2.4.8.
Общая постановка задачи
Требуется разработать алгоритм преобразования исходной СД хранения графа в выходную СД. Варианты заданий представлены в таблице в следующем разделе.
В качестве дополнительного задания рекомендуется программно реализовать разработанный алгоритм.
Список индивидуальных данных
В таблице Л3.1 приведены варианты заданий. Каждая строка таблицы соответствует варианту. Например, в первом варианте требуется разработать алгоритм преобразования матрицы смежности графа в матрицу инцидентности, задающую тот же граф.
Таблица Л3.1 |
||||||||||||
Варианты заданий лабораторной работы №3 |
||||||||||||
№ варианта |
Исходная СД |
Выходная СД |
||||||||||
матрица смежности |
матрица инцидент-ности |
массив ребер |
массивы смежности |
список ребер |
списки смежности |
матрица смежности |
матрица инцидент-ности |
массив ребер |
массивы смежности |
список ребер |
списки смежности |
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
Ö |
|
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
Ö |
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
Ö |
|
|
|
Ö |
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
Ö |
|
|
Ö |
|
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
Ö |
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
Ö |
|
|
|
|
|
|
|
|
|
|
|
Ö |
|
|
Ö |
|
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
Ö |
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
Ö |
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
Ö |
|
|
|
|
|
|
|
Ö |
Ö |
|
|
|
|
|
|
|
|
|
|
|
|
Ö |
|
Ö |
|
|
|
|
|
|
|
|
|
|
|
Ö |
|
|
Ö |
|
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
Ö |
|
|
|
|
|
|
|
|
|
Ö |
|
|
|
|
Ö |
|