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

}

//очистка таблицы

void pust (table *T)

{

 int i;

 for (i=0; i<N; i++){

     T->elem[i].numb=0;

       T->elem[i].name[0]='\0';

 }

 T->n=0;

}

//очистка матрицы весов

void pustm (int **mat, int n)

{

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

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

             mat[i][j]=0;

}

//добавление в таблицу

int addtable (table *t, city *elem)

{

 int i,k=0, g=1, max=0;

 for (i=0; i<t->n; i++){

       if (!strcmp(t->elem[i].name , elem->name))

       {

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

      g=0;

       }

       if (t->elem[i].numb>=max)

        max=t->elem[i].numb+1;

 }

    if (g) elem->numb=max;

    strcpy(t->elem[t->n].name,elem->name);

    t->elem[t->n].numb=elem->numb;

    t->n++;

   return max;

}

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

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

{

 int i, stop=1;

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

        if(t->elem[i].numb==numb)

        {

         strcpy(name, t->elem[i].name);

         stop=0;

        }

}

//ввод сети дорог

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

{

 char e;

  int i=0,j,k, g;

  city town;

   fscanf (in, "%c", &e);

   while (e!=':')

   {

    j=0;

      while (e!=' '&&e!=':')

      {

       town.name[j]=e;

       j++;

       fscanf (in, "%c", &e);

      }

    town.name[j]='\0';

      k=addtable(T,&town);

    i++;

      fscanf (in, "%c", &e);

   }

   int a=0;

   if (e==':')

         for (i=0; i<=k+1; i++)

         {

               fscanf (in, "%d", &wm1t[T->elem[a].numb][T->elem[a+1].numb]);

             a=a+2;

         }

       return k;

}

//поиск максимального по длине пути

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

{

 int *mark;

 int i,j,y,weight,k=0,a;

 long *dest, *prev;

 char name [21];

 mark = (int *)malloc(N*sizeof(int));

 dest = (long *)malloc(N*sizeof(long));

 prev = (long *)malloc (N*sizeof(long));

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

  {mark[i]=0;

   dest[i]=0;

  }

   y=start;

    mark[y]=1;

      dest[y]=0;

      a=kol-1;

       while (!mark[end])

       {

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

              if ((!mark[i])&&(dest[i]<dest[y]+matr[y][i]))

              {

               dest[i]=dest[y]+matr[y][i];

           prev[i]=y;

              }

       weight=0;

         for (i=0; i<a-1; i++)

               if (!mark[i])

                     if (weight<dest[i])

                     {

                       weight=dest[i];

                       y=i;

                     }

         mark[y]=1;

         a++;

       }

       i=end;

        while (i!=start)

        {

         findtf(t,i,name);

         fprintf (out, "%s ", name);

         i=prev[i];

        }

   findtf(t,i,name);

   fprintf (out, "%s", name);

   fprintf (out, "\nДлинна=%d", dest[end]);}

6.2. Модуль 2

#include "func.h"

void main ()

{

 setlocale(LC_ALL,"");

 FILE *in, *out;

 in=fopen("input.txt","r");

 table t;

 int **wm1t, kol, dest=-1, start=-1;

  wm1t=(int **)malloc (N*sizeof(int));

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

         wm1t[i]=(int *)malloc (N*sizeof(int));

 pustm(wm1t,N);

 pust(&t);

 kol=getweb(in,&t,wm1t);

 fclose(in);

 out=fopen("output.txt","w");

 menu(&t,&dest,&start);

 if (start==-1||dest==-1)

       printf ("Нет такого города в сети дорог!!!");

 else

 find(&t,kol,wm1t,dest,start,out);

 fclose (out);

printf ("\n");

system ("pause");

}

7. Тесты

№	Сеть дорог	Города	Длина пути
1	Ald                                   8             Nsk	Ald, Nsk	8
2	7         Kaz                  Ald                                               8  Nsk           10	Nsk, Kaz	15
3	Ald              8         5   Nsk          10                  Ny            12   Bst      7	Nsk, Ny	20
4	Ald      10              Kaz              8         5          15   Nsk          10                  Ny            12   Bst      7	Nsk, Kaz	27

8. Результат отладки и анализ программ

         Программа работает правильно, что подтверждается результатами тестов.