Между данными, используемыми в той или иной информационной модели, всегда существуют некоторые связи, определяющие ту или иную структуру данных.
Вспомните, как мы определяли структуру данных при рассмотрении алгоритмов и программ. О каких информационных моделях тогда шла речь? С какими структурами данных вы сталкивались в программировании?
Различают линейные и нелинейные структуры данных.
В курсе информатики основной школы вы познакомились с линейным односвязным списком — последовательностью линейно связанных элементов, для которых разрешены операции добавления элемента в произвольное место списка и удаление любого элемента. Связь элементов списка осуществляется за счёт того, что каждый элемент списка содержит кроме данных адрес элемента, следующего за ним в списке. В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент.
Частным случаем линейного односвязного списка является стек — последовательность, в которой включение и исключение элементов осуществляются с одной и той же стороны этой последовательности .
Ещё одним частным случаем линейного односвязного списка является очередь — последовательность, у которой включение элементов производится с одной стороны последовательности, а исключение — с другой. Сторона, где происходит включение элементов, называется хвостом; сторона, где происходит исключение, — головой. Понятие очереди как структуры данных очень близко к бытовому понятию «очередь» (рис. 3.2).
Рис. 3.2. Иллюстрация понятия «очередь»
Подумайте, какая связь между стеком и следующими объектами:
Почему стек является структурой типа LIFO (от англ. Last In, Firts Out — последним пришёл, первым ушёл)?
Почему очередь является структурой типа FIFO (от англ. First In, First Out — первым пришёл, первым ушёл)?
Примеры нелинейных структур данных вам также хорошо известны — это графы и деревья (рис. 3.3).
Граф — это множество элементов (вершин графа) вместе с набором отношений между ними.
Рис. 3.3. Примеры графовых структур
Граф является многосвязной структурой, обладающей следующими свойствами:
1) на каждый элемент может быть произвольное количество ссылок;
2) каждый элемент может иметь связь с любым количеством других элементов;
3) каждая связка может иметь направление и вес.
Ненаправленная (без стрелки) линия, соединяющая вершины графа, называется ребром. Линия направленная (со стрелкой) называется дугой. При этом вершина, из которой дуга исходит, называется начальной, а вершина, куда дуга входит, — конечной. Граф называется неориентированным, если его вершины соединены рёбрами. Вершины ориентированного графа соединены дугами. Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер.
Графы являются основным средством для описания структур сложных объектов. С их помощью можно описать вычислительную сеть, транспортную систему, схему авиалиний и другие объекты.
Одной из разновидностей графа является дерево.
Дерево — это совокупность элементов (вершин), в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья). Каждое поддерево является деревом, а его корень является потомком корня дерева, т. е. все элементы связаны между собой отношением «предок — потомок». В результате образуется иерархическая структура вершин.
Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков.
Деревья используются для представления родственных связей (генеалогическое дерево), для определения выигрышной стратегии в играх и т. д.
Ещё одной знакомой вам структурой данных являются таблицы, состоящие из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей.
Оформляют таблицы в соответствии с рисунком 3.4.
Рис. 3.4. Оформление таблицы
Название таблицы, при его наличии, должно отражать её содержание, быть точным, кратким. Название следует помещать над таблицей.
Заголовки граф и строк таблицы следует писать с прописной буквы, а подзаголовки граф — со строчной буквы, если они составляют одно предложение с заголовком, или с прописной буквы, если они имеют самостоятельное значение. В конце заголовков и подзаголовков таблицы точки не ставят. Заголовки и подзаголовки граф указывают в единственном числе.
Если все показатели, приведённые в графах таблицы, выражены в одной и той же единице физической величины, то её обозначение необходимо помещать над таблицей справа. Если в графе таблицы помещены значения одной и той же физической величины, то обозначение единицы физической величины указывают в заголовке (подзаголовке) этой графы.
Эти и другие требования к оформлению таблиц содержатся в ГОСТ 2.105-95 «ЕСКД. Общие требования к оформлению текстовых документов».
В курсе информатики основной школы вы познакомились с таблицами типа:
• «объект — свойство», содержащими информацию о свойствах отдельных объектов, принадлежащих одному классу;
• «объект — объект», содержащими информацию о некотором одном свойстве пар объектов, принадлежащих одному или разным классам.
Таблицы, в которых отражено наличие или отсутствие связей между отдельными элементами некоторой системы, называются двоичными матрицами.
Вспомните и приведите примеры таблиц типа «объект — свойство», «объект — объект», отражающих не только количественные, но и качественные характеристики свойств (двоичные матрицы).
Табличный способ представления данных является универсальным — любую структуру данных, в том числе и представленную в форме графа, можно свести к табличной форме. Это тем более важно в связи с тем, что для компьютерной обработки табличное представление данных является предпочтительным.
Пример 1. Построим таблицу, соответствующую неориентированному графу (рис. 3.5), отражающему схему дорог между некоторыми населёнными пунктами.
Рис. 3.5. Граф схемы дорог
Строки и столбцы таблицы будут соответствовать вершинам графа. Если две вершины являются смежными (соединены ребром), то в ячейку на пересечении соответствующих столбца и строки будем записывать вес этого ребра. В противном случае (вершины не являются смежными) в ячейку будем записывать 0. Получится таблица типа «объект — объект».
Такую таблицу называют матрицей смежности. Часто в матрицах смежности вместо нуля ставят знак минус, что обеспечивает большую наглядность.
Матрица смежности неориентированного графа симметрична относительно главной диагонали, идущей от левого верхнего угла к правому нижнему углу. У матрицы смежности неориентированного графа такая симметрия отсутствует.
Пример 2. Обед в школьной столовой состоит из двух блюд и напитка. На первое можно выбрать щи или окрошку, на второе — плов или пельмени, на третье — сок или компот. Все возможные варианты представлены с помощью дерева на рисунке 3.6.
Рис. 3.6. Дерево вариантов обеда
Для того чтобы представить эту же информацию в таблице, будем двигаться по дереву от листьев к корню, описывая все возможные варианты обеда.
Получилась таблица типа «объект-свойства»: объектами в ней являются варианты обеда, а свойствами — составляющие его блюда. При этом число граф в полученной таблице соответствует числу уровней в дереве.
При решении класса задач, связанного с нахождением кратчайшего пути в ориентированном графе, можно:
1) от исходного графа перейти к матрице смежности;
2) по матрице смежности построить дерево решений;
3) по дереву решений выбрать подходящий вариант.
Пример 3. Найдём кратчайший путь от вершины А до вершины F в графе, приведённом на рисунке 3.7.
Рис. 3.7. Ориентированный граф
Составим матрицу смежности, соответствующую данному ориентированному графу:
По матрице смежности построим полное дерево перебора решений — рисунок 3.8.
Рис. 3.8. Полное дерево перебора решений
На рисунке 3.8 видно, что кратчайший путь из вершины А в вершину F равен 17 и имеет вид A-B-E-F.
Пример 4. На рисунке 3.9 представлена схема дорог, связывающих города А, Б, С, D, Е, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько разных путей существует из города А в город G?
Рис. 3.9. Схема дорог.
Существует несколько способов решения этой задачи. Рассмотрим их.
Вариант 1. По графу можно построить матрицу смежности, а на её основе построить дерево, корнем которого будет служить вершина А. Число листьев построенного дерева будет равно числу дорог из города А в город G.
Постройте дерево и подсчитайте число дорог из города А в город G самостоятельно.
Вариант 2. Пусть Кх — число путей из города А в город X.
Начнем считать число путей с конца маршрута. Так как в город G есть дороги из городов С, E, F, то KG = КC + КЕ + KF.
В свою очередь КC = 1 + KD = 1 + 1 = 2, КЕ = КB + KC =1 + 2 = 3, КF = KC = 2.
Таким образом, KG = 2 + 3 + 2 = 7.
Вариант 3. Можно считать число путей с начала маршрута. При этом процесс подсчёта удобно изображать на самом графе — рисунок 3.10.
Рис. 3.10. Схема дорог с подсчётом числа путей
Пример 5. На рисунке 3.11 представлена схема дорог, связывающих населённые пункты А, В, С, D, Е, F, G. В таблице содержатся сведения о длинах этих дорог (в километрах). Схему и таблицу создавали независимо друг от друга, поэтому в них используются разные обозначения. Необходимо выяснить длину пути в километрах из пункта D в пункт F.
Рис. 3.11. Схема дорог и таблица их длин
Рассмотрим имеющийся граф и выясним степень каждой вершины — число рёбер, соединяющих некоторую вершину с другими вершинами. Получим:
На основании имеющейся таблицы мы также можем сделать выводы о том, сколькими дорогами соединён тот или иной населённый пункт с другими населёнными пунктами:
Сопоставив полученную информацию, можем сказать, что через Г1 в таблице обозначен населённый пункт F, а через Г7 — D. Согласно таблице, расстояние между этими пунктами равно 25 км.
