Программная инженерия Нижний Новгород 017 Лабораторный

AB 
CA 
BC 

---

 
83 
2.2. Алгоритмы 
В качестве основных алгоритмов обработки плексов в рамках лабораторной работы 
должны быть рассмотрены операции обхода плексов, необходимых, например, при отрисовке 
чертежа. 
Реализация алгоритмов обхода плексов может быть выполнена поэтапно: на первом этапе 
можно реализовать частный алгоритм обхода плексов без подплексов (как, например, на рис. 
3), и только затем приступить к разработке общего алгоритма обхода. 
2.2.1. Обход плекса без подплексов 
Плексы без подплексов соответствуют представлению чертежей, которые можно 
нарисовать без отрыва карандаша от бумаги. Пример такого объекта - треугольник 
представлен на рис. 1. Соответствующий плекс без подплексов приведен на рис. 3. 
Для того чтобы нарисовать линию, необходимо знать ее начальную и конечную точку. Так 
как в плексе допускается вместо указателя точки хранить указатель линии, то необходимо 
найти первую линию, у которой указатель начала – точка. В приведенном примере на рис. 3 
это линия BC. Тогда конечная точка этой линии будет начальной точкой предыдущей линии 
(в примере – CA). То есть, на первом этапе необходимо отыскать линию, у которой указатель 
начала – точка, при этом указатели на все пройденные линии необходимо запомнить в стеке. 
На втором этапе из стека извлекаются линии, для которых в качестве начальной точки 
выступает конечная точка обработанной линии. Процесс заканчивается, когда в стеке больше 
не содержится указателей на линию. 
 
2.2.2. Обход плекса с подплексами 
Плекс с подплексами служит для представления чертежей, которые нельзя нарисовать без 
отрыва карандаша от бумаги. Пример такого чертежа представлен на рис. 9, возможная 
структура плекса для которого показана на рис. 10. 
Пример чертежа, для представления которого требуется плекс
с подплексами (верхняя горизонтальная линия состоит из двух отзков DB и BF). 
A