![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 17. Свойства и типы графов. шины являются смежными с вершиной v? Программа 10.7 реализует итератор, который дает ответ клиентам
Реализации в программах 17.9 и 17.10 являются низкоуровневыми. В качестве альтернативы можно воспользоваться функцией list библиотеки STL, чтобы реализовать каждый связный список (см. упражнение 17.30). Недостаток такого подхода заключается в том, что реализации функции list библиотеки STL требуют поддержки гораздо большего числа операций, чем требуется, а это обычно влечет за собой непроизводительные затраты, которые могут неблагоприятно повлиять на все разрабатываемые нами алгоритмы (см. упражнение 17.31). В самом деле, все наши алгоритмы на графах используют интерфейс АТД Graph, следовательно, эта реализация служит подходящим местом для инкапсуляции всех низкоуровневых операций, благодаря чему достигается требуемая эффективность и не затрагиваются другие программы. Другое преимущество использования представления графа в виде связного списка заключается в том, что оно предлагает конкретную базу для оценки рабочих характеристик наших приложений. Еще одним важным фактором, который следует учесть, является тот факт, что реализация в программах 17.9 и 17.10, в основу которой положены связные списки, не полна по причине отсутствия деструктора и конструктора копирования. Для многих приложений это обстоятельство приводит к неожиданным результатам или острым проблемам, обусловленным снижением производительности. Эти функции представляют собой прямое расширение функций, используемых в реализации очереди первого класса в программе 4.22 (см. упражнение 17.29). На протяжении всей книги мы полагаем, что объекты SparceMultiGRAPH содержат их. Использование функции list из библиотеки STL вместо однонаправленных списков обладает несомненным преимуществом, которое заключается в том, что отпадает необходимость в дополнительном программном коде, поскольку теперь соответствующий деструктор и конструктор копирования определяются автоматически. Например, объекты DenseGRAPH, построенные в программе 17.7, должным образом порождаются и уничтожаются клиентскими программами, которые манипулируют ими, так как они построены на базе объектов из библиотеки STL.
|