Математическая модель африканской электрификации, страница 3

  list *next;

};

typedef struct Uzel

{

  SubInt X;

  SubInt Y;

  int Pay;

  Ref Left;

  Ref Right;

};

typedef struct zveno *svqz;

typedef struct zveno

{

  unsigned int Element[256];

  svqz Sled;

  zveno();

};

zveno::zveno()

{

 for(int k=0;k<256;k++)Element[k]=0;

}

void Init_spisok(L **l)

{

 *l=NULL;

}

void insert(L **l,SubInt t1,SubInt t2)

{

 L *rabochii;

 rabochii = new L;

 rabochii->t1=t1;

 rabochii->t2=t2;

 rabochii->next=NULL;

 if(*l==NULL) *l=rabochii;

 else

  {

   L *beg_k;

   for(beg_k=*l;beg_k->next!=NULL;beg_k=beg_k->next);

   beg_k->next=rabochii;

  }

}

void Search (int A, int B, int C, Ref *p)

{

 if ( (*p) == NULL )

  {

   (*p) = new (Uzel); (**p).X = A; (**p).Y = B; (**p).Pay = C;

   (**p).Left = (**p).Right = NULL;

  }

 else

 if ( C<=(**p).Pay ) Search (A,B,C,&((**p).Left));

 else

 if ( C>(**p).Pay ) Search (A,B,C,&((**p).Right));

}

void Postroenie (svqz *UkStr)

{

  svqz UkZv;

  int el;

  FILE *fp;

  fp=fopen("vershiny.txt","r");

  (*UkStr) = new (zveno);

  UkZv = (*UkStr); UkZv->Sled = NULL;

  while (fscanf(fp,"%d",&el)!=EOF)

  {

   UkZv->Sled = new (zveno); UkZv = UkZv->Sled;

   UkZv->Element[el] = 1; UkZv->Sled = NULL;

  }

}

void Postr()

{

  int A,B,C;

  FILE *fp;

  fp=fopen("rebra.txt","r");

  while ( fscanf(fp,"%d %d %d",&A,&B,&C)!=EOF)

  {

   Search (A,B,C,&Root);

  }

  fclose(fp);

}

void Poisk (svqz st, SubInt MENT, svqz *Res)

{

  svqz q;

  (*Res) = NULL; q = st->Sled;

  while  ( q != NULL  &&  (*Res) == NULL )

  {

   if ( q->Element[MENT]==1 ) (*Res) = q;

   else  q = q->Sled;

  }

}

void Udalenie (svqz *zv, svqz UkStr)

{

 svqz Z;

 svqz UkZv1;

 if ( (*zv)->Sled != NULL ) (**zv) = *((**zv).Sled);

 else

  {  Z = UkStr; UkZv1 = UkStr->Sled;

     while  (UkZv1 != (*zv))

     { Z = UkZv1; UkZv1 = UkZv1->Sled; }

       Z->Sled = NULL; delete UkZv1;

     }

}

void Reshenie(list **p)

{

  svqz UkStr;

  Ref UkUzel;

  Ref UkUzel1;

  SubInt T1,T2;

  svqz Res1,Res2;

  Postroenie (&UkStr);

  printf("rebra ostovnogo dereva min cost:\n");

  while ( UkStr->Sled->Sled != NULL )

  {

    UkUzel1 = Root;

    UkUzel  = Root->Left;

    if ( UkUzel== NULL )

             {

               T1 = Root->X; T2 = Root->Y;

               Root = Root->Right; delete UkUzel1;

             }

    else

             {

              while ( UkUzel->Left != NULL )

                        {

                          UkUzel1 = UkUzel1->Left;

                          UkUzel  = UkUzel->Left;

                        }

                        T1 = UkUzel->X; T2 = UkUzel->Y;

                        UkUzel1->Left = UkUzel->Right;

                        delete UkUzel;

             }

             Res1 = Res2 = NULL;

             Poisk (UkStr,T1,&Res1);

             Poisk (UkStr,T2,&Res2);

             if ( Res1!=Res2 )

             {

               for (int k=0;k<256;k++)

                 if ( Res1->Element[k]==1 || Res2->Element[k]==1 )

                          Res1->Element[k]=1;

                 Udalenie (&Res2,UkStr);

                 insert(p,T1,T2);

             }

  }

}

void out(L*p)

{

 L *r;

 for(r=p;r!=NULL;r=r->next)

  printf("%d %d\n",r->t1,r->t2);

}

void main()

{

    clrscr();

    L * spisok;

    Postr();

    Init_spisok(&spisok);

    Reshenie(&spisok);

    out(spisok);

    getch();

}

7.  Набор тестов

№	Входные данные	Результат	Назначение
1.		(1, 2)	Граф с минимальным количеством ребер
2.		(1, 2) (1, 4) (2, 5) (2, 3)
3.		(2, 3) (3, 4) (4, 1)	Граф с несколькими одинаковыми остовными деревьями с минимальным весом

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

Программа выдала желаемый результат на всех тестах.

9.  Список используемой литературы

1.  Хиценко В.П., «Структуры данных и алгоритмы», Новосибирск 2008.

2.  Томас Кормен, «Алгоритмы. Построение и анализ», Москва 2005.