Другой путь генерации множественных решений — метод удаления узла (node removal) — просто удаляет последний узел из текущего решения и пытается снова найти решение. Для этого в функцию main () внесены изменения, позволяющие удалить последний рейс текущего решения из базы данных, очищать все поля skip и получать новый пустой стек, использующийся для хранения следующего решения. Новая версия функции main о приведена в листинге 7.5.
Листинг 7.5. Функция main() для получения множественных решений с помощью удаления узла
// Версия для удаления узлов, int main () {
char to[40], from[40];
Search ob;
Flightlnfo f;
// Добавляет рейсы в базу данных, ob.addflight("New York", "Chicago", 900); ob.addflight("Chicago", "Denver", 1000); ob.addflight("New York", "Toronto", 500); ob.addflight("New York", "Denver", 1800); ob.addflight("Toronto", "Calgary", 1700); ob.addflight("Toronto". "Los Angeles", 2500); ob.addflight("Toronto", "Chicago", 500); ob.addf1ight("Denver", "Urbana", 1000); ob.addflight("Denver", "Houston", 1000); ob.addf1ight("Houston", "Los Angeles",1500); ob.addflight("Denver", "Los Angeles", 1000);
// Получает пункты отправления и назначения, cout « "From? ";
cin.getline(from, 40); cout « "To? ";
cin.getline(to, 40);
// Находит множественные решения. for(;;) {
// Проверяет, есть ли рейс.
ob.findroute(from, to);
// Если не найден ни один новый маршрут, завершается, if(!ob.routefound()) break;
// Сохраняет рейс на вершине стека (on top-of-stack). f = ob.getTOSO ;
ob.route(); // отображает текущий маршрут
ob.resetAllSkipO ; // переустанавливает поля skip
// Удаляет из базы данных последний рейс //из предыдущего решения, ob.remove(f);
}
return 0;
)
Для удаления последнего рейса, включенного в предыдущее решение, Функция main о получает его с помощью вызова функции gecTOSO, кото-Рая объявлена как встроенная функция в классе Search. II Возвращает рейс из вершины стека. PlightInfo getTOSO { return btStack.top();
}
Функция getTOso возвращает информацию о последнем рейсе маршрут хранящемся на вершине стека возврата.
Для действительного удаления этого рейса функция main о вызывает функцию remove (), приведенную далее. // Удаляет рейс.
void Search::remove(Flightlnfo f) (
for(unsigned i=0; i< flights.size(); i++) if(flights[i].from == f.from && flights[i].to == f.to) flights[i].from = "";
}
Удаление рейса заключается в присваивании пустой строки переменной from, содержащей название пункта отправления.
Для очистки полей skip функция main о вызывает функцию resetAilskip (), приведенную далее. // Переустанавливает все поля skip, void Search::resetAllSkip() {
for(unsigned i=0; i< flights.sizeO; i++) flights[i].skip - false;
}
Функция resetAilskip о просто присваивает всем полям skip значение
false (не забудьте Добавить ПРОТОТИПЫ ДЛЯ функций resetAilskip () и remove () В раздел объявления класса Search).
Поскольку внесено достаточно много изменений, для большей наглядности программа с применением метода удаления узла приведена полностью в листинге 7.6. Обратите внимание на то, что она тоже использует первоначальную программу поиска в глубину из листинга 7.1.
|
