49

9. Нелинейные структуры данных

Вид занятия – лабораторная работа Цель – исследование способов хранения нелинейных структур данных

Продолжительность – 4 часа

На данной лабораторной работе мы познакомимся с особенностями представления в памяти двух базовых нелинейных структур данных: графа и бинарного дерева.

Граф

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

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

Как многосвязная структура граф обладает следующими свойствами:

1.на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

2.каждый элемент может иметь связь с любым количеством других элементов;

3.каждая связка (ребро, дуга) может иметь направление и вес.

Обычно информацию о графах хранят двумя способами:

1.в виде матрицы примыканий (смежностей);

2.в виде списка примыканий (смежностей).

Матрица примыканий AdjMat графа G = (V, E) с числом вершин записывается в виде двумерного массива размером N х N. В каждой ячейке [i,j] этого массива записано значение 0 за исключением лишь тех случаев, когда из вершины Vi в вершину Vj ведет ребро, и тогда в ячейке записано значение 1.

	1,		если	vivj E
							(9.1).
	AdjMat[i, j]=	0,	если	v v		E
					j
				i

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

				(A)	(B)	(C)	(D)
	A	B	(A)	0	1	0	1
			(B)	1	0	1	1
	D	C	(C)	0	1	0	1
			(D)	1	1	1	0
	A	B		(A)	(B)	(C)	(D)
			(A)	0	1	0	0
			(B)	0	0	1	1
	D	C	(C)	0	0	0	1
			(D)	1	0	1	0

Рисунок 9.1. – Представление графа в виде матрицы примыканий

50

Список примыканий AdjList графа G = (V,E) с числом вершин V = N записывается в виде одномерного массива длины N, каждый элемент которого представляет собой ссылку на список

(см. рис. 9.2).

A A B B C C D E D E

B C

A C D

A B E

B E

C D

Рисунок 9.2. – Представление графа в виде списка примыканий

Бинарное дерево

Дерево – это граф, который характеризуется следующими свойствами:

1.Существует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент и который называется “корнем”.

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

3.На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Наиболее простой разновидностью деревьев являются бинарные деревья. Это такие деревья, у каждой вершины которых, имеется от 0 до 2 дочерних вершин.

В памяти ЭВМ деревья можно представлять с помощью связных списков и массивов (или последовательных списков). Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от родительской вершины к дочерней. У каждого элемента бинарного дерева имеется два указателя, поэтому удобно узел представить в виде трёхэлементной структуры (см. рис. 9.3).

Рисунок 9.3. – Структура элемента бинарного дерева

Задание

1.Разработайте программу позволяющую хранить информацию об ориентированном графе произвольного размера. Программа должна содержать процедуры:

1.Добавления вершины в граф.

51

2.Удаления вершины из графа.

3.Вывода информации о составе графа.

4.Сохранения (чтения) данных в файл.

Программа должна позволять пользователю выбирать формат хранения данных (матрица примыканий или список примыканий).

2.Разработайте программу позволяющую хранить информацию об иерархической структуре в формате бинарного дерева. Программа должна содержать процедуры:

1.Добавления вершины в произвольное место дерева.

2.Удаления вершины (и всех дочерних элементов) из дерева.

3.Вывода информации о составе дерева.

4.Сохранения (чтения) данных в файл.

Примечание: разработанная на данном занятии программа (хранящая информацию об ориентированном графе) будет востребована на лабораторной работе на тему “Алгоритмы на графах”. Поэтому при проектировании формата хранения данных о вершине графа целесообразно предусмотреть дополнительное поле логического типа. В нём мы станем содержать информацию о факте посещения вершины графа при реализации алгоритмов обхода в глубину, обхода по уровням, и т.д.

Примечание: при выполнении первого задания вам может помочь компонент TStringGrid. Указанный компонент описан в приложении к данному пособию.