Главная arrow Учебники arrow Информатика и ИКТ 10-11 класс Семакин 2012 arrow §14 Структуры данных: деревья, сети, графы, таблицы

§14 Структуры данных: деревья, сети, графы, таблицы

Информатика и ИКТ 10-11 класс Семакин, Информатика 10-11 класс Семакин, Структуры данных, Деревья, Сети, Графы, Таблицы, Иерархические структуры

Данные, используемые в любой информационной модели, всегда определенным образом упорядочены, структурированы. Иначе можно сказать так: данные, на которых базируется информационная модель, представляют собой систему со всеми характерными признаками — элементным составом, структурой, назначением. Такие структурированные системы данных часто называют структурами данных. Исследуя некоторую реальную систему (объект моделирования), системный аналитик строит ее теоретическую модель (см. рис. 3.1).
Этапы разработки компьютерной информационной модели
При этом в первую очередь он должен описать структуру данных. Мы рассмотрим несколько часто используемых видов описания структур данных: графы, иерархические структуры (деревья) и таблицы.
Графы
Информация о некотором реальном объекте может быть представлена по-разному. В разговорной речи мы используем словесное (вербальное) представление информации. Вот, например, словесное описание некоторой местности: «Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию довольно трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понятнее становится из схемы на рис. 3.2 (на ней поселки обозначены первыми буквами своих названий).
Неориентированный <a href='/slovar-spravochnik-po-terminam/osnovyi-informatsionnoy-tehnologii/graf-graph-ot-grech.-grapho-pishu-izobrazhayu.html
' target='_self'>граф</a> (сеть)
Это не карта местности. Здесь не выдержаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом.
Граф отображает элементный состав системы и структуру связей.
Составными частями графа являются вершины и ребра. Здесь вершины изображены кружками, обозначающими элементы системы, а ребра изображены линиями, показывающими связи (отношения) между элементами. Глядя на этот граф, легко понять структуру дорожной системы в данной местности.
Построенный граф позволяет, например, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Видно, что есть два возможных пути; обозначим их так:
1) Р — К — Б — М;
2) Р — К — Д — Б — М.
Очевидно, первый путь более выгодный, потому что он короче. Однако если по какой-то причине дорога между К и Б окажется непроезжей (начнутся ремонтные работы или дорогу занесет снегом), то единственным остается второй путь. Граф на рис. 3.2 еще называют сетью.
Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин.
Для сетей также характерно наличие замкнутых путей, которые называются циклами. На рис. 3.2 имеется цикл: К - Д - Б - К. Кстати, термин «дорожная сеть» используется и в разговорной речи. И чем такая сеть гуще, тем лучше для сообщения, поскольку появляется множество различных вариантов проезда.
Граф, изображенный на рис.3.2, является неориентированным графом. На нем каждое ребро обозначает наличие дорожной связи между двумя пунктами. Но дорожная связь действует одинаково в обе стороны: если по дороге можно проехать от Б к М, то по ней же можно проехать и от М к Б. Такую связь еще называют симметричной.
А теперь рассмотрим другой пример графа — на рис. 3.3.
Ориентированный <a href='/slovar-spravochnik-po-terminam/osnovyi-informatsionnoy-tehnologii/graf-graph-ot-grech.-grapho-pishu-izobrazhayu.html
' target='_self'>граф</a>
Этот пример относится к медицине. Известно, что существуют четыре группы крови человека. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы. Граф на рис. 3.3 показывает возможные варианты переливания крови. Группы крови обозначены вершинами графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови. Например, из этого графа видно, что кровь I группы можно переливать любому человеку, а человек с I группой крови воспринимает только кровь своей группы. Видно также, что человеку с IV группой крови можно переливать любую кровь, но его собственную кровь можно переливать только человеку с той же группой.
Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Такие линии принято называть дугами (в отличие от ребер неориентированных графов). Граф с такими свойствами называется ориентированным. Линия, выходящая и входящая в одну и ту же вершину, называется петлей. На рис. 3.3 присутствуют четыре такие петли.
Нетрудно понять преимущества изображения системы переливания крови в виде графа по сравнению с вербальным (словесным) описанием тех же самых правил. Граф на рис. 3.3 легко воспринимается и запоминается.
Иерархические структуры (деревья)
При построении информационных моделей многих систем приходится иметь дело с иерархической структурой. Как правило, иерархическую структуру имеют системы административного управления, между элементами которых установлены отношения подчиненности. Например: директор завода — начальники цехов — начальники участков — бригадиры — рабочие. Иерархическую структуру имеют также системы, между элементами которых существуют отношения вхождения одних в другие.
На рис. 3.4 изображен граф, отражающий иерархическую административную структуру нашего государства: Российская Федерация делится на семь административных округов; округа делятся на регионы (области и национальные республики), в состав которых входят города и другие населенные пункты. Такой граф называется деревом. Основным свойством дерева является то, что между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель.
Граф иерархической системы
Обычно у дерева, отображающего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Эта вершина изображается вверху; от нее идут ветви дерева. От корня начинается отсчет уровней дерева. Вершины, непосредственно связанные с корнем, образуют первый уровень. От них идут связи к вершинам второго уровня и т. д. Каждая вершина дерева (кроме корня) имеет одну исходную вершину на предыдущем уровне и может иметь множество порожденных вершин на следующем уровне. Такой принцип связи называется «один ко многим», в отличие от сети — там связь «многие ко многим». Вершины, которые не имеют порожденных вершин, называются листьями. На рис. 3.4 вершины, обозначающие города, являются листьями.
Иерархическими являются различные системы классификации в науке. Например, в биологии весь животный мир Земли рассматривается как система, которая делится на типы животных, типы делятся на классы, классы состоят из отрядов, отряды — из семейств, семейства делятся на роды, роды — на виды. Следовательно, система животных имеет шестиуровневую иерархическую структуру.
При изучении информатики вам не однажды приходилось встречаться с иерархическими системами. Например, система хранения файлов на магнитных дисках организована по иерархическому принципу. Операционная система позволяет получить на экране компьютера изображение файловой структуры в виде дерева (рис. 3.5). Корнем этого дерева является корневой каталог диска, вершинами — подкаталоги разных уровней.
Иерархическая <a href='/slovar-spravochnik-po-terminam/avtomatizatsiya-informatsionnyih-protsessov/sistema-system.html
' target='_self'>система</a> хранения файлов
Как известно, путь к файлу — это путь от корневого каталога до каталога, непосредственно содержащего данный файл. И для каждого файла такой путь единственный. Например, путь к файлам, содержащимся в каталоге Images на рис.3.5, описывается так:
\Inform\hyperbase\6.11\Images
При поиске информации в дереве перемещение по нему может происходить только вверх или вниз (на уровень выше или на уровень ниже). Нельзя осуществить прямой переход между вершинами одного уровня.
Еще одним примером иерархической структуры является система доменных адресов в Интернете. Фрагмент этой системы представлен на рис. 3.6 в виде дерева.
Иерархическая <a href='/slovar-spravochnik-po-terminam/osnovyi-informatsionnoy-tehnologii/struktura-structure.html
' target='_self'>структура</a> доменных адресов в Интернете
В этом дереве от корня отходят домены первого уровня, затем — второго и т. д. Овалами изображены компьютеры. Адрес компьютера включает в себя последовательность доменов и имя компьютера (сначала записывается имя компьютера, затем домен нижнего уровня и т. д., до домена самого верхнего уровня). Для трех указанных на рис. 3.6 компьютеров доменные адреса записываются так:
www.pstu.ас.ru        hidra.psu.ru        mail.psu.ru
Каждую вершину дерева, не являющуюся листом, можно рассматривать как корень поддерева, исходящего из этой вершины. Например, на рис. 3.6 поддерево с корнем в вершине г и представляет структуру доменных имен российского сектора Интернета.
Таблицы
Представление информации в табличной форме широко распространено. Только в школьной практике вам приходится встречаться с массой таблиц: расписанием занятий, журналом успеваемости, графиком дежурств, таблицей Менделеева, таблицами физических свойств веществ (плотности, теплоемкости, электрического сопротивления и пр.), таблицами исторических дат и многими другими.
Чаще всего мы пользуемся прямоугольными таблицами (бывают и более «хитрые» формы таблиц, но о них мы говорить не будем). Простейшая таблица состоит из строк и граф (столбцов). В верхней строке таблицы обычно располагаются заголовки столбцов. Пересечение строки и столбца образует ячейку. Таблица 3.1 — пример прямоугольной таблицы, содержащей сведения о погоде в течение нескольких дней.
Таблица 3.1. Погода

Дата

Осадки

Температура, °С

Давление, мм рт. ст.

Влажность, %

15.03.2007

снег

-3,5

746

67

16.03.2007

без осадков

0

750

62

17.03.2007

туман

1,0

740

100

18.03.2007

дождь

3,4

745

96

19.03.2007

без осадков

5,2

760

87

Обратите внимание на правила оформления таблиц. Над таблицей обычно указывается ее номер и заголовок. Заголовки столбцов пишутся с прописной буквы; там, где это необходимо, указываются размерности величин.
Таблица 3.1 является примером таблицы типа «объект—свойство». Каждая строка такой таблицы относится к конкретному объекту. В нашем примере объект — это определенный день. Первый столбец обычно идентифицирует этот объект (дата идентифицирует день). Последующие графы отражают свойства объекта. В таблице 3.1 это метеорологические данные. Обратите внимание на то, что строки таблицы расположены по возрастанию даты, т. е. информация в таблице упорядочена (по дате). Упорядоченность позволяет быстро найти нужные данные.
Другой тип таблиц называется «объект—объект». Такие таблицы отражают взаимосвязь между различными объектами. Примером является таблица успеваемости учеников по разным предметам (табл. 3.2).
Таблица 3.2. Успеваемость

Ученик

Предмет

Русский

Алгебра

Химия

Физика

История

Музыка

Аликин Петр

4

5

5

4

4

5

Ботов Иван

3

3

3

3

3

4

Волков Илья

5

5

5

5

5

5

Галкина Нина

4

4

5

2

4

4

Эта таблица отражает связь между объектами двух типов: учениками и изучаемыми дисциплинами. Оценка (расположена в ячейке) является характеристикой такой связи. В такой таблице строки и столбцы могут поменяться местами: в строках — информация о предметах, в столбцах — об учениках. Удобнее работать с таблицами, в которых столбцов меньше, чем строк. Обычно учеников в классе больше, чем изучаемых предметов.
Важной разновидностью таблиц типа «объект-объект» являются двоичные матрицы. Двоичные матрицы отображают качественную связь между объектами: есть связь или нет связи. Например, если бы ученики могли выбирать изучаемые предметы по своему усмотрению, то сведения о том, кто что изучает, можно было бы представить в виде таблицы 3.3:
Таблица 3.3. Изучаемые предметы

Ученик

Предмет

Русский

Алгебра

Химия

Физика

История

Музыка

Аликин Петр

0

1

1

1

0

0

Ботов Иван

1

1

0

1

0

1

Волков Илья

1

0

0

0

1

1

Галкина Нина

0

1

1

0

1

0

Нетрудно догадаться, что единица указывает на изучаемый предмет, а неизучаемый предмет отмечен нулем.
Табличный способ представления данных является универсальным. Любую структуру данных, в том числе и представленную в форме графа, можно свести к табличной форме. Таблица 3.4 — возможное представление иерархической структуры, изображенной на рис. 3.2.
Таблица 3.4. Административная структура Российской Федерации

Город

Регион

Округ

Березники

Пермская обл.

Приволжский

Екатеринбург

Свердловская обл.

Уральский

Кунгур

Пермская обл.

Приволжский

Пермь

Пермская обл.

Приволжский

Сергиев Посад

Московская обл.

Центральный

Заполнение таблицы происходит путем движения по дереву снизу вверх (от листьев к корню). Получилась таблица типа «объект-свойство». Объекты — города, а свойствами является их принадлежность к соответствующим административно-географическим зонам. Строки в данной таблице упорядочены в алфавитной последовательности названий городов. Число граф в таблице равно числу уровней в дереве. Нет смысла заводить графу под названием «Государство», поскольку во всех строках в ней будет присутствовать одно значение «Российская Федерация». Лучше это слово вынести в заголовок таблицы.
Для табличного представления сетей используют двоичные матрицы. Таблица 3.5 представляет собой двоичную матрицу, соответствующую структуре сети на рис. 3.2.
Таблица 3.5. Дорожная сеть

Поселок

Поселок

Бабкино

Дедкино

Кошкино

Репкино

Мышкино

Бабкино

0

1

1

0

1

Дедкино

1

0

1

0

0

Кошкино

1

1

0

1

0

Репкино

0

0

1

0

0

Мышкино

1

0

0

0

0

Двоичная матрица в этой таблице называется матрицей смежности: единицы стоят на пересечении строк и столбцов с названиями смежных (соединенных дорогой) поселков. Если сеть является неориентированным графом, то матрица смежности симметрична относительно главной диагонали, идущей от верхнего левого угла в правый нижний угол матрицы (подумайте сами почему). Вследствие этого, если строки и столбцы поменять местами, то матрица не изменится.
Замечание: вопрос о том, какую цифру (ноль или единицу) ставить в диагональных клетках, носит условный характер. Можно договориться по-разному. В таблице 3.5 поставлены нули из тех соображений, что, например, дороги Бабкино-Бабкино не существует (хотя, в принципе, можно построить такую петлю).
У матрицы, отражающей ориентированный граф, такой симметричности не будет. В этом случае надо договориться о смысле строк и столбцов. Например, пусть для каждой пары смежных вершин строка обозначает начальную, а столбец — конечную вершину. Тогда структуру ориентированного графа, изображенного на рис. 3.3, можно представить следующей двоичной матрицей смежности — табл. 3.6.
Таблица 3.6. Переливание крови

Начальная вершина

Конечная вершина

I

II

III

IV

I

1

1

1

1

II

0

1

0

1

III

0

0

1

1

IV

0

0

0

1

Может возникнуть вопрос: зачем мы переводили графы в табличную форму? Ведь граф, с точки зрения человека, гораздо нагляднее и понятнее представляет структуру системы, чем таблица. Для человека это действительно так. Однако для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии работают с таблицами (базы данных, электронные таблицы); обработку таблиц удобно описывать на универсальных языках программирования. Поэтому представление системы в форме графа обычно используется в теоретических моделях, а в компьютерном моделировании чаще работают с табличным представлением.
Система основных понятий

Структуры данных

Графы

Таблицы

Разновидности графа

Элементы прямоугольной таблицы

Деревья

Сети

Строки

Столбцы

Ячейки

Тип связей в графе

Типы таблиц

Один ко многим

Многие ко многим

Элементы дерева

Элементы сети

Объект-

свойство

Объект-

объект

Двоичная

матрица

Корень Ветви Листья

Вершины Ребра

Единственность пути между вершинами

Множественность путей между вершинами