КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пример. Список дуг
Для этого способа хранения структуры составляется таблица, каждая строка в которой фиксирует дугу графа следования, причем в первом элементе строки записывается обозначение начальной вершины дуги, а во втором элементе - обозначение конечной вершины дуги. Если таблица будет представлена в памяти ЭВМ как массив размерностью 2 x k, где k - количество дуг, то массив будет занимать объем V=2k слов. Рассмотрим пример структуры сборочного технологического процесса.
Список дуг для этой структуры:
| Оi | Oj | |
| O1 | O2 | |
| O3 | O2 | |
| O2 | O5 | |
| O4 | O5 | |
Для этого примера V=8 слов. Этот способ всегда лучше, чем первые два способа в случае, когда структура представляет собой либо линейный граф, либо граф типа "дерево". Для структуры типа "сеть" хранение в виде списка дуг выгоднее, если k < 1.5n. Ниже приведена структура операции типа "сеть".
При хранении этой структуры списком дуг - V=20 слов.
Список дуг
| pi | pj |
| p1 | p2 |
| p2 | p3 |
| p2 | p4 |
| p2 | p5 |
| p2 | p6 |
| p3 | p7 |
| p4 | p7 |
| p5 | p7 |
| p6 | p7 |
| p7 | p8 |
Изменение списка дуг производится путем добавления или вычеркивания строк.
Дата добавления: 2015-04-15; просмотров: 110; Мы поможем в написании вашей работы!; Нарушение авторских прав |