Лабораторная
работа 3.
Списки, деревья.
Несколько замечаний перед тем, как приступить к выполнению задания...
1) Изучите теорию по теме "Графы"... смотри здесь
2) Задача1. Составить программу, которая содержит процедуру создания заданного способа представления графа в памяти ЭВМ. Информацию о графах сохраните в текстовых файлах в своем разделе.
Предполагается, что вершины графа пронумерованы от 1 до N, а ребра – от 1 до M. Каждому ребру и каждой вершине может быть сопоставлен вес – целое положительное число.
Реализуйте в виде методов следующие операции:
проверка смежности вершин
v и w;
перечисление всех вершин смежных с
v;
определение веса ребра (v, w);
определение веса вершины v;
перечисление всех ребер (v, w);
перечисление ребер, инцидентных вершине v;
перечисление вершин, инцидентных ребру s.
Варианты задания.
Варианты отличаются способом представления графа в памяти ЭВМ. Для
конкретного студента вариант определяется преподавателем.
1)Матрица
смежности.
2)Матрица
инцидентности.
3)Списки
смежных вершин.
4)Перечень
ребер.
Вариант | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
Номер способа представления | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 |
Протестируйте свою задачу на конкретных графах:
Граф 1. Неориентированный граф.
Граф 2. Ориентированный граф.
3) Задача 2. Задано бинарное дерево поиска (реализация на основе динамических списков). Необходимо реализовать процедуру добавления и удаления узла дерева, поиск заданного значения, а также реализовать прямой, обратный и концевой обходы дерева. Реализовать в программе проверку всех подпрограмм: добавление узлов (8-10 значений), все виды обхода получившегося дерева, поиск заданного значения, удаление заданного значения, все виды обхода получившегося дерева.
4) Задача 3. Для заданной
последовательности чисел, записанных в строку через пробел во входной
текстовый файл, создать бинарное дерево поиска (реализация на основе
массива). Запросить число с клавиатуры
и воспользовавшись свойствами бинарного дерева поиска ответить на вопрос:
есть ли заданное число в последовательности. В случае положительного ответа
- удалить этот элемент из дерева. Провести прямой, обратный и внутренний
обход дерева.
Указание: массив содержит n элементов, корень
- 0-ой элемент, у каждой i-ой вершины есть два
потомка: (2i+1)-ая и (2i+2)-ая
вершины.