Обозначение записей и ячеек
Обычно мы имеем дело с различными элементами данных — записями, ячейками, файлами и списками. Однако в данном случае наибольший интерес для нас представляют записи и ячейки.
Чтобы упростить восприятие графов, воспользуемся системой обозначений, в которой записи изображены в виде окружностей, а ячейки — в виде - квадратов. Пустая ячейка показана при помощи квадрата с пересекающимися внутри двумя прямыми.
Отношения данных
Предшествование. В тех случаях, когда ячейки требуется представить как различные элементы данных, их отношения отображают тонкими линиями. Стрелки на рисунках показывают взаимное расположение ячеек. Иногда расположение определяется индексами.
Так, ячейка А2 соседствует с А3, но поскольку ее индекс меньше, ясно, что А2 предшествует А3.
Тонкой линией также отображается текущее позиционное отношение записей относительно списка, в который они входят. Так, на рис. 4.14 (3) файл содержит запись а2, которая предшествует записи а3 в списке.
Отношение «меньше чем» отображается штрихпунктирной линией.
Отношение «указывает на» точечной линией, которая направлена от указанной записи к целевой.
Пересылка. Пересылка данных по определенному адресу изображается утолщенной линией направленной от места хранения данных к адресату
Поиск. Поиск сводится к анализу списка или файла. В процессе поиска анализируются члены множества в некоторой последовательности. Последовательность, в которой производится поиск, обозначается направленной пунктирной линией. Следует отметить, что, в то время как другие отношения представляются статически, поиск является динамическим процессом. Он начинается с первого члена множества и, продвигаясь по цепочке, заканчивается на том члене множества, на который указывает последняя стрелка.
Изменения. “Раскрашивая” - стрелку в различные цвета (или используя различные типы линий), на графе можно представить выполняемые в списке или файле изменения:
• линия, образованная последовательностью знаков “х”, показывает, что представляемое ею отношение больше не существует;
• линия, образованная последовательностью знаков “о”, показывает, что представляемое ею отношение является новым, т. е. раньше оно не существовало.
Пример. Рассмотрим пример, который имеет большое значение, так как объединяет некоторые концепции теории графов. На рис.4.15 изображен список L, содержащий множество ячеек. Из этого множества на рисунке показаны только ячейки с А до J. Перекрестные линии в ячейках Н, I, J означают, что эти ячейки пустые. S является ячейкой-указателем. Она содержит указатель на ячейку Н и позволяет перейти к оставшимся пустым ячейкам в списке L. Записи в списке L упорядочены. Это можно определить с помощью линий предшествования, отображающих последовательные переходы от А к В, от В к С и т. д. Между G и Н нет стрелки, так как G является последней записью массива, содержащегося в списке L.
Слева на рис.4.15 схематически изображен поиск записи t. В данном примере показано включение этой записи в упорядоченный список L, после чего результирующий список L также оказывается упорядоченным. Включение записи в .список требует выполнения операции поиска записей, содержащихся в L. Направление поиска указано пунктирной линией, продолжающейся от А до D. При поиске обнаруживается, что запись в ячейке С меньше t, но t меньше записи в ячейке D. Следовательно, запись t должна быть помещена в список между записями, содержащимися в ячейках С и D.
Размещение записи. В данный момент у нас нет места для размещения записи t. Для его получения необходима реорганизация списка. Записи, хранящиеся в ячейкахD—G, должны быть перемещены на одну позицию вниз. Другими словами, необходимо выполнить следующие действия:
(G)->H, (F)->G, (E)->F, (D)->E, t->D. (4.3.1)
В результате записи, расположенные в ячейках D-G, сместятся вниз на одну ячейку каждая. С момента пересылки записи из D в Е я до тех пор, пока в D не попадет на последнем шаге запись t, в этих ячейках будут находиться одинаковые записи.
Отметим важность последовательного выполнения действий. Первой в пустую ячейку должна быть перемещена самая .нижняя запись в списке, затем запись в предыдущей ячейке и т. д.
Рис.4.16 иллюстрирует процесс внесения изменения .в список L. Утолщенные линии отображают перемещение записей, а цифры в кружках указывают, в какой последовательности выполнялась пересылка,
например, 1 означает, что запись из ячейки G первой переслана в Н, а 5 - что последней была переслана запись t в D. S указывает на следующую доступную свободную ячейку: раньше эта ячейка указывала на Н, теперь - на I. Таким образом, на рисунке изображают старый и новый указатели.
Упражнения
4.1. Для списка, ячейки и элемента:
а) объясните, что означает, каждое понятие;
б) укажите, какие типы символов используются для них;
в) объясните, что является их содержимым;
г) укажите, какие типы символов используются для описанияих содержимого.
4.2. Объясните предложения;
а) (адрес) = данное; б) [данное] = адрес.
4.3. Разберите предложение: “Ключ однозначно идентифицирует запись”. Объясните его. Почему “однозначно”?
4.4. На чем основывается выбор ключевого поля файла?
4.5. Что означает выражение “один ключ больше другого”? Как это определяется? Как это представляется символически? Объясните, почему это может зависеть от ЭВМ?
4.6. Как в ASCII обеспечивается кодирование пробела символов и цифр?
4.7. Для списков порядок должен устанавливать: отношение между ячейками в списке или отношение между записями в файле.
4.8. Дайте точное определение для списков:
а) порядка по возрастанию;
б) порядка по убыванию.
4.9. Что такое граф? Какие функции выполняют линии и точки при представлении графа? Как он используется?
4.10. Что вы понимаете под отношением? Какое отношение называется:
а) рефлексивным;
б) симметричным;
в) транзитивным?
4.11. Определите, являются ли приведенные ниже отношения рефлексивными, симметричными и (или) транзитивными. Подтвердите это примерами и контрпримерами:
а) отец; б) брат; в) родной брат или сестра; г) равен; д) не равен; е) больше чем; ж) между; з) меньше чем; и) предшествует; к) любит.
4.12. Что такое ориентированный граф? Что такое дуга? Что показывает стрелка? Какие типы отношений представляет граф?
4.13. Что такое маршрут? Какое он имеет значение в графе списка? в схеме организации?
4.14. Что означают определения элементарный, простой и непростой? Что такое цикл?
4.15. а) Какая разница между петлей и циклом?
б) Может ли граф иметь цикл и не иметь петли? Объясните.
в) Может ли граф иметь петлю и не иметь цикла? Объясните.
4.16, а) Что такое связный граф и связный орграф?
б) Может ли орграф быть связным, а соответствующий ему граф нет? Объясните.
4.17. Дайте простое определение дереву, направленному дереву.
4.18. Что представляют в схеме организации лист и корень7 Что можно сказать о такой схеме, если число корней больше одного? Как представить графически схему обычной организации?
4.19. Должен ли граф программы
а) иметь древовидную структуру? Объясните;
б) иметь древовидную структуру с двоичным ветвлением? Объясните;
в) быть транзитивным? Объясните.
4.20. а) Что такое раскрашенный граф?
б) Может ли орграф быть раскрашенным? Объясните.
4.21. Дан состав семьи: прародители – Петр, Евдокия.
Их дети – Евгений, Ольга, Галина.
Евгений был женат на Валентине, от их брака родились дети – Надежда и Владимир. Надежда вышла замуж за Виктора у них сын Валерий.
Ольга замужем за Георгием, у них дочь Наталья, у Натальи сын Николай
Галина замужем первым браком за Виктором, от их брак родился Александр, второй брак Галины с Владимиром, от их брака родились Светлана и Наталья.
1.Сконструировать полную схему семьи с использованием отношений:
А) «родитель», «супруг»
Б) «отец», «мать», «муж», «жена», «сестра», «брат», «дядя», «тетя», «кузен» и т.д.
В) построить раскрашенный граф, данной семьи.