Вычисление длины самого длинного простого пути от города А до города В в заданной системе односторонних дорог, страница 2

                            dist(x)=dist(y)+w_ij;

                            result = {пройденный город y}

}

}

{Новая вершина y принадлежит X}

              dist(y)=              min            dist(x);

                            ^{x принадлежит X и метка(x)=0}

метка(y)=1;

}

4.3. Алгоритм ввода системы дорог

{

e  =  первый символ;

while(e!=’:’){

    while(e!=’ ‘ и e!=’:’){

              символ название города  = e;

              e =  следующий символ;

    }

k=k+1;

{добавление города в список}

}

If (e==’:’){

e = следующий символ;

              for(I от 0 до k )

              for (j от 0 до k)

              w_ij  = e;

}

}     

}

4.4. Добавление города в список

{g=1; max=0;

              If (город в списке_названий_городов есть){

                            добавить город в список;

                            номер города=номер города который есть в списке;

                            g=0;       

              }

              если (номер города который есть в списке>max)

              max= номер города который есть в списке;

если (g==1)  номер города=max;

}

5.Структура программы

              Текст программы разбит на два модуля:

              1) Содержит функции реализации решения задачи.

              2)Содержит основную программу.

5.1. Состав модуля 1

Функция findtm:

-назначение:

Поиск в таблице по заданному имени города его номер в матрице весов. Функция возвращает номер если город найден, и -1 если не найден.

-прототип функции:

              void findtm (table *t, char *start, char *end, int *stn, int *endn);

-параметры:

              t-(входной параметр) таблица в для хранений названий городов;

              start – (входной параметр) название города начала пути;

              end – (входной параметр) название города конца пути;

              strn – (выходной параметр) номер города начала пути;

              endn – (выходной параметр) номер города конца пути.

Функция getweb:

-назначение:

Ввод системы дорог. Формирует матрицу весов и заполняет таблицу с названиями городов.

-прототип функции:

              int getweb (FILE *in, table *T, int **wm1t)

-параметры:

              in – (входной параметр) файл в котором хранятся названия городов и расстояния между ними;

              T – (выходной параметр) таблица для хранения названий городов;

              wm1t – (выходной параметр) матрица расстояний между городами.

 Функция find:

-назначение

              Поиск  наибольшего расстояния между  двумя городами;

-прототип функции

void find (table *t, int kol, int **matr, int start, int end, FILE *out);

-параметры

              t-(входной параметр) таблица в для хранений названий городов;

              kol – (входной параметр) количество городов в таблице;

              matr - (входной параметр) матрица расстояний между городами;

              start – (входной параметр) номер города начала в матрице весов;

              end – (входной параметр) номер города конца в матрице весов.

Функция addtable:

-назначение

              Добавление в таблицу названия города и подсчет количества городов в таблице;

-прототип функции

int addtable (table *t, city *elem)

-параметры

              t – (выходной параметр) таблица в для хранений названий городов;

              elem – (входной параметр) название города.

Функция findtf:

-назначение

              поиск названия города но номеру в таблице;

-прототип функции

void findtf (table *t, int numb, char *name)

-параметры

      t – (входной параметр) таблица в для хранений названий городов;

              numb – (входной параметр) номер города;

              name – (выходной нараметр) название города.

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

6.1. Модуль 1

#include "stdlib.h"

#include "stdio.h"

#include "string.h"

#define N 20

#include "locale.h"

struct city

{

 char name [21];

 int numb;

};

struct table

{

 city elem[N];

 int n;

};

//поиск номера города в таблице

void findtm (table *t, char *start, char *end, int *stn, int *endn)

{

 int i,stop=1,m=1,a=1;

  for (i=0; i<t->n&&stop==1; i++)

  {

   if (!strcmp(t->elem[i].name, start)&&m==1)

   {

       *stn=t->elem[i].numb;

     m=0;

   }

   if (!strcmp(t->elem[i].name, end)&&a==1)

   {

    *endn=t->elem[i].numb;

     a=0;

   }

   if (a==0&&m==0) stop=0;

  }

}

//вывод меню на экран

void menu (table *t, int *startnu, int *endnu)

{

 char dest[21];

 char start[21];

 printf ("ВВедите город начала пути:");

 scanf ("%s", &start);

 printf ("\n");

 printf ("ВВедите город назначения:");

 scanf ("%s", &dest);

 findtm(t,start,dest,startnu,endnu);