Структуры и алгоритмы обработки данных

Министерство образования и науки РФ

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

 «Комсомольский-на-Амуре Государственный Технический Университет»

Факультет компьютерных технологий

Кафедра МОП ЭВМ

ЛАБОРАТОРНАЯ РАБОТА 2

по курсу «Структуры и алгоритмы обработки данных»

Выполнил:                                                                                                         Казаков М.Ю

Проверил:                                                                                                          Хусаинов А.А.

Вариант:                                                                                                            6

Комсомольск-на-Амуре

2006

Задание:     

Заданы n городов, между которыми определены рейсы самолетов. Матрица n ´ n состоит из чисел a_ij = 1, если существует рейс самолета из i в j, и 0 – в противном случае. Найти маршрут из p в q и вывести посещаемые города в обратном направлении.

Алгоритм работы программы:

Определяем матрицу len[n], элементом которой len[i] будет расстояние от города p до города i. s – текущий город.

1)  Начальное значение всех элементов len[i] равно (n + 1), а для p-ого элемента – 0;

2)  s = p;

3)  Для каждого города i, в который существует прямой путь из города s, определяем новое расстояние (len[s] + 1).

4)  Если это расстояние меньше len[i], то len[i] = len[s] + 1. Переходим на шаг 3) при s = i.

5)  len[q] содержит кратчайшее расстояние от p до q.

Текст программы:

#include <iostream.h>

int **A, *len, n;

void calc(int t);

void main()

{

  int i, j, t, p, q, id = 1;

  cout << "Количество городов: ";

  cin >> n;

  A = new int*[n];

  len = new int[n];

  for (i = 0; i < n; ++i)

  {

    A[i] = new int[n];

    len = new int[n];

  }

  cout << "Рейсы: " << endl << endl;

  for (i = 0; i < n; ++i)

  {

    for (j = 0; j < n; ++j)

      cin >> A[i][j];

    len[i] = n + 1;

  }

  cout << "Отправная точка: ";

  cin >> p;

  cout << "Пункт назначения: ";

  cin >> q;

  len[p] = 0;

  calc(p);

  t = q;

  while (t != p && id)

  {

    id = 0;

    cout << t << " ";

    for (i = 0; i < n; ++i)

      if (A[i][t] && len[i] == len[t] - 1)

      {

        t = i;

        i = n;

        ++id;

      }

  }

  if (id)

    cout << t;

  else

    cout << "\r" << "Нет пути из города " << p << " в " << q;

  for (i = 0; i < n; ++i)

    delete A[i];

}

void calc(int t)

{

  for (int i = 0; i < n; ++i)

    {

      if (A[t][i] && (len[i] > len[t] + 1))

      {

        len[i] = len[t] + 1;

        calc(i);

      }

    }

}

Результат работы программы:

Список использованных источников:

1.  Хусаинов А.А., Михайлова Н.Н. Структуры и алгоритмы обработки данных: Учеб. пособие. – Комсомольск-на-Амуре: Комсомольский-на-Амуре гос. техн. ун-т, 2002. – 89 с.