VPF::Код программы - Форум программистов

TMC

Дата 17.12.2007, 22:55 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 2.11.2007

Репутация: нет
Всего: нет

Здравствуйте , Уважаемые программисты!

Прошу прощения за неловкую тему , но очень нужно просто .
У меня такой вопрос - на каком языке написан код программы (код дан ниже) и чем можно открыть , чтобы отредактировать данный код (Если можно , ссылку на программную среду)

Заранее большое спасибо.

Код


#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define M 10 //Максимальное количество вершин в графе.
typedef int Boolean;
typedef struct L *Lref; // Тип: указатель на заголовочный узел.
typedef struct T *Tref; // Тип: указатель на дуговой узел.

//Описание типа заголовочного узла.
typedef struct L 
{ 
  int Key; //Имя заголовочного узла.
  int Count; //Количество предшественников.
  Tref Trail; //Указатель на список смежности.
  Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
};

//Описание типа дугового узла.
typedef struct T 
{ 
  Lref Id; 
  Tref Next; 
};

class Spisok
{
  private:
    Lref Head; //Указатель на голову списка заголовочных узлов.
    Lref Tail; //Указатель на фиктивный элемент 
               // в конце списка заголовочных узлов.
    int Fun[M+1]; //Массив вершин графа.
    int NewFun[M+1]; //Массив перестановок элементов массива Fun.
    void SearchGraph (int, Lref *);
    Lref Search(int);
    Boolean Find_Arc (int, int);
    Boolean Isomorph (Spisok, int);
  public:
    Spisok() {//Инициализация списка заголовочных узлов.
              Head = Tail =  new (L); }
    Lref GetHead() { return Head; }
    Lref GetTail() { return Tail; }
    void MakeGraph ();
    void PrintGraph ();
    void Sorting ();
    friend void Reshenie(Spisok,Spisok);
};

void main ()
{
  Spisok A,B;

  //Построение графов и вывод их структур смежности.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  B.MakeGraph ();
  B.PrintGraph (); cout<<endl;
  A.Sorting ();
  A.PrintGraph (); cout<<endl;
  B.Sorting ();
  B.PrintGraph (); cout<<endl;
  //Решение.
  Reshenie(A,B);
}

void Reshenie(Spisok A, Spisok B)
//Решение задачи.
{
   Lref Ukaz;      //Рабочий указатель для перемещения 
                   // по списку заголовочных звеньев.
   int P[M+1];     //Массив для перестановок.
   int Ves[M+1];   //Массив "весов" элементов массива P
                   //(в нем хранятся степени вершин).
   int Ves1[M+1];  //Вначале - копия массива Ves,     
                   //затем - рабочий массив.
   Boolean Fl;     //Флаг совпадения массивов Ves и Ves1.
   Boolean PR[M+1];
   int C[M+1];
   int x,k,t;

  //Определение количества вершин и функций.
  int N=0;
  Ukaz = A.GetHead();
  while (Ukaz!=A.GetTail())
    { N++; 
      A.Fun[N] = A.NewFun[N] = Ukaz->Key; Ves[N] = Ukaz->Count;
      Ves1[N] = Ves[N]; Ukaz = Ukaz->Next;
    }
  N=0;
  Ukaz = B.GetHead();
  while (Ukaz!=B.GetTail())
    { N++; 
      B.Fun[N] = Ukaz->Key; Ukaz = Ukaz->Next;
    }
  for (int i=1;i<=N;i++) cout << Ves[i] << " "; cout << endl;
  for (i=1;i<=N;i++) cout << A.Fun[i] << " "; cout << endl;
  for (i=1;i<=N;i++) cout << B.Fun[i] << " "; cout << endl;
  //Инициализация.
  for (i=1;i<=N;i++)
    { P[i] = i; C[i] = 1; PR[i] = TRUE; }
  //Нахождение перестановок.
  C[N] = 0;
  cout << "Отображение вершин, определяющее изоморфизм: \n";
  if ( A.Isomorph (B,N) )
  {
    for(int j=1;j<=N;j++) A.NewFun[j] = A.Fun[P[j]];
    for(j=1;j<=N;j++) cout << A.NewFun[j] << " ";
    cout << endl;
    for(j=1;j<=N;j++) cout << B.Fun[j] << " ";
    cout << endl;
  }
  cout << " --------------------------- \n";
  i = 1;
  while ( i<N )
  {
    i = 1; x = 0;
    while ( C[i]==N-i+1 )
    {
       PR[i] = (!PR[i]); C[i] = 1;
       if ( PR[i]) x++;
       i++;
    }
    if ( i<N )
    //Выполнение транспозиции.
    {
       if ( PR[i] )  k = C[i] + x;
       else  k = N - i + 1 - C[i] + x;
       t = P[k]; P[k] = P[k+1]; P[k+1] = t;
       t = Ves1[k]; Ves1[k] = Ves1[k+1];
       Ves1[k+1] = t; C[i] += 1;
       //Отбор нужной перестановки.
       Fl = TRUE;
       for (int j=1;j<=N;j++) Fl = (Fl && (Ves[j]==Ves1[j]));
       if ( Fl )
       {
          for (j=1;j<=N;j++) A.NewFun[j] = A.Fun[P[j]];
          if (A.Isomorph (B,N))
          {
             for (j=1;j<=N;j++) cout << A.NewFun[j] << " ";
             cout << endl;
             for (j=1;j<=N;j++) cout << B.Fun[j] << " ";
             cout << endl;
             cout << " --------------------------- \n";
           }
       }
    }
  }
}

Lref Spisok::Search (int w)
//Функция возвращает указатель на заголовочный узел 
//ключом w. Если узел отсутствует, то функция возвращает NULL .
{
  Lref h = Head;
  (*Tail).Key = w; //Поиск "с барьером".
  while ((*h).Key!=w) h = (*h).Next;
  if (h==Tail) //В списке заголовочных узлов нет узла с ключом w.
    h = NULL;
  return h;
} 

void Spisok::SearchGraph (int w, Lref *h)
//Функция возвращает указатель на заголовочный узел 
//с ключом w в графе, заданном структурой Вирта с указателем Head. 
{
  *h = Head; (*Tail).Key = w;
  while ((**h).Key!=w) *h = (**h).Next;
  if (*h==Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
  { Tail = new (L); (**h).Count = 0; 
    (**h).Trail = NULL; (**h).Next = Tail; }
}

void Spisok::MakeGraph ()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
  int x,y;
  Lref p,q; //Рабочие указатели.
  Tref t,r; //Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.
  cout<<"Вводите начальную вершину дуги: ";
  cin>>x;
  while (x!=0)
  {
     cout<<"Вводите конечную вершину дуги: "; cin>>y;
     //Определим, существует ли в графе дуга (x,y)?
     SearchGraph (x, &p); SearchGraph (y,&q);
     r = (*p).Trail; Res = FALSE; 
     while ((r!=NULL)&&(!Res)) 
       if ((*r).Id==q) Res = TRUE; 
       else r = (*r).Next; 
     if (!Res) //Если дуга отсутствует, то поместим её в граф.
      { t = new (T); (*t).Id = q; 
        (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; } 
     cout<<"Вводите начальную вершину дуги: "; cin>>x;
  }
}

void Spisok::PrintGraph ()
//Вывод структуры Вирта, заданной указателем 
//Head и соответствующей ориентированному графу.
{
  Lref p; //Рабочий указатель.
  Tref q; //Рабочий указатель.

  p = Head;
  while (p!=Tail)
  {
     cout<< "(" << (*p).Count << ")" << (*p).Key << "("; q = (*p).Trail; 
     while (q!=NULL) 
      { cout<<(*(*q).Id).Key; q = (*q).Next; } 
     cout<<")"; p = (*p).Next; cout<<" ";
  }
}

Boolean Spisok::Find_Arc (int x, int y)
//Функция возвращает TRUE, если в графе, представленном
//структурой Вирта (Head,Tail), существует дуга (x,y).
{

  Lref p,q;    //Рабочие указатели.
  Tref r;      //Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.

  //Определим, существует ли в графе дуга (x,y)? 
  p = Search (x);
  q = Search (y);
  r = p->Trail; Res = FALSE;
  while  ( r != NULL && !Res ) 
    if  (r->Id==q) Res = TRUE;
    else  r = r->Next;
  return Res;
}

void Spisok::Sorting ()
//Сортировка узлов в заголовочном списке
//по полю Count в порядке убывания.
{
  Lref UkZv_1,UkZv_2;
  Lref UkZv_3;
  Tref UkZv_4;
  int  A, B;
  Tref D;

  UkZv_1 = Head;
  while ( UkZv_1 != Tail )
  {
    UkZv_2 = UkZv_1->Next;
    while  ( UkZv_2!=Tail )
    {
      if ( UkZv_1->Count < UkZv_2->Count )
      {
        A              = UkZv_1->Key;
        B              = UkZv_1->Count;
        D              = UkZv_1->Trail;
        UkZv_1->Key    = UkZv_2->Key;
        UkZv_1->Count  = UkZv_2->Count;
        UkZv_1->Trail  = UkZv_2->Trail;
        UkZv_2->Key    = A;
        UkZv_2->Count  = B;
        UkZv_2->Trail  = D;
        UkZv_3 = Head;
        while ( UkZv_3!=Tail )
        {
          UkZv_4 = UkZv_3->Trail;
          while ( UkZv_4 != NULL )
          {
            if ( UkZv_4->Id==UkZv_1 ) UkZv_4->Id = UkZv_2;
            else  
               if ( UkZv_4->Id==UkZv_2 ) UkZv_4->Id=UkZv_1;
            UkZv_4 = UkZv_4->Next;
          }
          UkZv_3 = UkZv_3->Next;
        }
      }
      UkZv_2 = UkZv_2->Next;
    }
    UkZv_1 = UkZv_1->Next;
  }
}

Boolean Spisok::Isomorph (Spisok B, int N)
//Функция, возвращающая TRUE, если  графы, представленные 
//структурами Вирта (A.Head,A.Tail) и (B.Head,B.Tail), изоморфны.
//Отображение  вершин  при  изоморфизме  задано  векторами
//NewFun и Fun.
{

  Boolean Flag = TRUE;
  int k1,k2;

  for (int i=1;i<=N;i++)
  {
    k1 = 1;
    while ( i != this->NewFun[k1] ) k1++;
    for (int j=1;j<=N;j++)
    {
      k2 = 1;
      while ( j != this->NewFun[k2] )  k2++;
       if  ( i>j && this->Find_Arc(i,j) )
          Flag = (Flag && B.Find_Arc (B.Fun[k1],B.Fun[k2]));
    }
  }
  return Flag;
}

mr.Anderson

Дата 17.12.2007, 23:07 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128

Это С++. Поищи по гуглу среду для редактирования и компиляции С++ - файлов. Можно C++ Builder (но он очень большой), можно GC++, можно MS VC++ (тоже огромная)... в общем, порой гугл.

--------------------

TMC

Дата 17.12.2007, 23:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 2.11.2007

Репутация: нет
Всего: нет

Спасибо .
Но я так и не нашёл :(
Искал в гугл по запросу , который ты сказал , но чё-то всё не то.
Может перекинешь по аське , если анлим ? Мне просто буквально посмотреть как работает прога и всё.

qwerty789

Дата 18.12.2007, 02:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 7.12.2007

Репутация: 1
Всего: 1

CodeBlocks можешь скачать http://www.codeblocks.org/ или Dev-Cpp http://www.bloodshed.net/

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »