Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 116

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 161 >> Следующая

7 0, 1,4, 6, 3,7 — —
8 0,1,4, 6, 3,7 2 —
9 0, 1,4, 6, 3, 7,2 8 00 t см
10 0, 1,4, 6, 3, 7, 2,8 5 2-8, 8-5
11 0, 1,4, 6, 3, 7,2, 8,5 — —
Итератор обходит текущую вершину (точнее, после выполнения каждого шага итератора очередная вершина становится доступной для алгоритма, запустившего итератор, с помощью метода operator *) и выбирает следующую вершину из числа тех, в которые ведут дуги из текущей вершины. После первого шага ситуация будет такой, как показано в строке 2 табл. 6.1. Пройденная на этом шаге дуга 0-М помещается в стек. Следующие три шага выполняются аналогично, а последовательное изменение ситуации показано в табл. 6.1 в строках 3—5.
В тот момент, когда текущей стала вершина 3, оказывается, что единственная дуга, ведущая из нее, ведет в уже пройденную вершину 0, поэтому следует, используя стек, вернуться на шаг назад в вершину 6 и попытаться найти следующую вершину по одной из дуг, ведущих из этой вершины. Поскольку новых дуг, ведущих из вершины 6, тоже больше нет, то делаем еще шаг назад к вершине 4. Теперь уже находится дуга, ведущая из этой вершины в еще не пройденную вершину 7, так что после прохода по соответствующей дуге образуется новая ситуация, показанная в табл. 6.1 в строке 6.
После прохождения вершины 7 оказывается, что больше нет дуг, ведущих в еще не пройденные вершины ни из вершины 7, ни из всех предыдущих вер-
332
Гпава 6
шин на пути в эту вершину. В строке 7 таблицы показана ситуация, возникшая после проверки всех этих дуг. Теперь можно снова выбрать произвольно одну из непройденных вершин, скажем, вершину 2, и далее алгоритм последовательно переберет вершины 2, 8 и 5 так, как показано в строках 8—11. Теперь все вершины графа оказываются пройденными.
В листинге 6.1 приведено описание класса, реализующего граф так, как это было сделано в разд. 7.5, и описание класса, реализующего внешний итератор вершин графа в соответствии с указанным алгоритмом. Основное содержание алгоритма включено в реализацию оператора operator ++(), который и осуществляет переход к очередной вершине графа. По сравнению с описанием, приведенным выше, в определении функции сделано небольшое изменение: вместо множества пройденных вершин во время работы алгоритма хранится множество еще не пройденных вершин. Это изменение, разумеется, ничего не меняет по существу алгоритма, но облегчает реализацию метода hasMoreElements().
Стек дуг представлен объектом arcs класса stack<iterator<int>*>. Элементами этого стека будут итераторы, задающие последовательности дуг в представлении Z-графа. Это не очень традиционное, но довольно естественное для данной задачи решение. Действительно, нас интересуют не столько сами дуги, сколько множества тех вершин, в которые эти дуги приводят. Итератор списка номеров дуг эффективно представляет не только само множество, но и обеспечивает перебор элементов этого множества. Таким образом, итератор используется так, как обычно используется указатель на очередной элемент списка, при этом, однако, не требуется никакой информации о внутреннем устройстве списка.
Множество непройденных вершин представлено объектом setNotPassed класса Set, как он был определен в разд. 1.4. Элементами этого множества являются номера вершин графа. Считаем определенными в классе Set два дополнительных метода: метод, выдающий итератор элементов множества
iterator о (на самом деле такой итератор нами используется только для выборки произвольного элемента непустого множества), и метод empty о, проверяющий, есть ли элементы в множестве (т. е. пустое множество или нет). Номер текущей вершины в процессе обхода графа содержится в переменной
current.
Листинг 6.1. Внешний итератор вершин графа в алгоритме его обхода в глубину
// Определение класса ListGraph 7/^==============
class ListGraph {
Алгоритмы обработки графов
333
// Массив списков дуг List<int> *graph;
11 Количество вершин графа int vertexNumber;
// Класс для реализации внешнего итератора вершин графа class ExtGraphlterator : public Iterator<int> {
Set setNotPassed; // множество непройденных вершин
int current; // текущая вершина
Stack<Iterator<int>*> *arcs; // стек итераторов исходящих дуг
ListGraph *graph; // граф
public :
//====================================_======„=============
// Конструктор внешнего итератора
/ /—=—— ------- -- ----- --------- -------=====
ExtGraphlterator(ListGraph *graph); //==============================
// Деструктор
//=============================
-ExtGraphlterator() { delete arcs; }
// Функция проверки, остались ли еще не пройденные вершины bool hasMoreElements() const { return !setNotPassed.empty();
}
// Функция сдвига итератора на следующую вершину //в порядке обхода вершин графа в глубину Iterator<int> & operator ++ () ;
// Функция, выдающая номер очередной вершины на пути обхода const int & operator *() const { return current; }
};
public:
// Конструктор графа создает массив пустых списков ListGraph(int n) : vertexNumber(n), graph(new List<int>[n]) {}
// Деструктор уничтожает списки дуг -ListGraph() { delete [] graph; }
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.