По курсу “ Теория алгоритмов и вычислительных

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

Им. К.Э. ЦИОЛКОВКОГО

      КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе на тему: “Разработка алгоритмов и

программ выполнения операций над последовательными

и связанными представлениями структур данных ”

По курсу “ Теория алгоритмов и вычислительных

методы ”

Руководитель: Авдошин С.М.

Дата сдачи: _____________

Подпись:   _____________

Студент: Лицентов Д.Б.

Группа: 3ИТ- 2-26

Москва

1998

1. Постановка задачи.

 

 

Дано:

  Два орграфа X и Y с N вершинами ( X в последовательном представлении, Y в связанном представлении) без кратностей. Дуги орграфов образуют                 неупорядоченные списки. Орграфы задаются неупорядоченными списками смежных вершин - номеров вершин, в которые ведут ребра из каждой вершины графа.

Требуется:

Выполнить над ребрами орграфов операцию разности (X/Y). В результате выполнения этой операции новый орграф Z определяется в связанном представлении, а старый орграф X исправляется в последовательном представлении.

Особенности представления данных:

Последовательное представление данных: одномерный массив Array, содержащую два целочисленных поля I (содержит номер вершины, из которой исходит дуга) и J (содержит номер вершины, в которую входит дуга).

      

Array[_]			I		J
Array[ 1 ]			From		To
Array[ 2 ]			From		To
…			From		To
Array[ N ]			From		To

      N – количество дуг в орграфе X.

Связанное представление данных: одномерный массив Spisok указателей на структуру index, представляющую собой элемент списка и содержащий поле: целочисленное i ndex (содержит номер вершины, в которую входит дуга) и Next - указатель на структуру Spisok, указывающее на следующий элемент списка

Spisok[ _ ]	NEXT		index	next		index	next		Index	Next
Spisok[ 1 ]			To			…			To	NULL
…			To			…			To	NULL
Spisok[ N ]			To			…			To	NULL

 

N - количество вершин в графе Y,Z.

 

 

2. Внешнее описание программы.

 

Ввод информации об неориентированных графах происходит из файла, формат которого должен быть нижеследующим:

N

  X11 X12... X1k1 0

  X21 X22... X2k2 0

 ...

  XN1 XN2... XNkN 0

  Y11 Y12... Y1k1 0

  Y21 Y22... Y2k2 0

 ...

YN1 YN2... YNkN 0

где N - число вершин в графах

Xij - номер очередной вершины смежной i в графе X (i = 1..N, j=1..ki)

 Yij - номер очередной вершины смежной i в графе Y (i = 1..N, j=1..ki)

Если из какой-то вершины не выходит ни одного ребра, то для нее в исходных данных задаем только ноль (например ‘0’ - вершина 2 изолирована). Таким образом, для каждого графа должно вводится в общей сложности N нолей.

Формат печати результатов работы программы представлен в следующем формате:

Даны неориентированные графы X и Y без кратностей.

Для каждого графа задаем номера вершины смежности с данной.

Граф X (в ЭВМ в последовательном представлении):

1: X11 X12... X1k1

2: X21 X22... X2k2

 ...

N: XN1 XN2... XNkN

Граф Y (в ЭВМ в связанном представлении):

1: Y11 Y12... Y1k1

2: Y21 Y22... Y2k2

 ...

N: YN1 YN2... YNkN

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

с получением нового графа Z (в связанном представлении):

1: Z11 1,Z12... Z1k1

2: Z21 Z22... Z2k2

 ...

N: ZN1 ZN2... ZNkN

И исправлением старого графа X (в последовательном представлении):

1: X11 X12... X1k1

2: X21 X22... X2k2

 ...

N: XN1 XN2... XNkN

Кол-во вершин, кол-во дуг графа X, кол-во дуг графа Y

и кол-во времени, затраченного на вычисление разности X и Y:

N MX MY T

где T - кол-во времени, затраченного на вычисление разности X и Y

Zij - номер очередной вершины смежной i в графе Z (i = 1..N, j=1..ki)

MX - кол-во дуг в графе X

MY - кол-во дуг в графе Y

Метод решения:

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

Аномалии исходных данных и реакция программы на них:

1. нехватка памяти при распределение: вывод сообщения на экран и завершение работы программы;

2. неверный формат файла: вывод сообщения на экран и завершение работы программы;

Входные данные

Входными данными для моей работы является начальное число вершин графа, которое по мере работы программы увеличиться на 30 верши. Это число не может превосходить значения 80 вершин, так как в процессе работы программы число увеличивается на 30 и становиться 110 – это «критическое» число получается из расчета 110» 2¹⁶/3. Это происходит потому, что стандартный тип int не может вместить в себя более чем 2¹⁶. Мне же требуется для нормально работы программы, чтобы тип вмещал в себя утроенное количество вершин неориентированного графа. Конечно, это всего лишь приближение, но с учётом того, что графы генерируются случайно возможность набора 33000 невелико и, следовательно, допустимо.

Входной файл генерируется каждый раз новый.

Графы для расчета мультипликативных констант генерируются случайным образом, используя датчик случайных чисел, это-то и накладывает ограничения на количество вершин. Дело в том, что при работе с генератором случайных чисел предпостительно иоспользовать целый тип данных – так говорил товарищ Подбельский В.В.

Оценка временной сложности.

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

# include<iostream.h>

# include<time.h>

# include<stdlib.h>

# include<fstream.h>

# include<conio.h>

# include <math.h>

 

///////////////////////////////////////////////////////////////////////////////////////////////////////

struct Spisok  //Связанное представление графа

{ int index;   //Содержвтельная "ячейка"

  Spisok *next; //Следуюцая "дуга"

};

///////////////////////////////////////////////////////////////////////////////////////////////////////

struct Array //Последовательное представление графа

{ int I;       //из какой вершины

int J;       //в какую вершину

};

///////////////////////////////////////////////////////////////////////////////////////////////////////

 

inline double fun1(double N_X,double N_Y,double N_Z){ return N_X*(N_Y+N_Z);}

 

inline double fun2(double N_X,double N_Y,double N_Z){ return N_X+N_Y;}

 

inline double fun3(double N_X,double N_Y,double N_Z){ return N_X;}

 

inline double fun4(double N_X,double N_Y,double N_Z){ return N_Y;}

 

inline double fun5(double N_X,double N_Y,double N_Z){ return N_Z;}

 

inline double fun6(double N_X,double N_Y,double N_Z){ return 1;}

///////////////////////////////////////////////////////////////////////////////////////////////////////

const int N = 6, M = N+1;

 

double A[N][M];

double B[N][M];

 

 typedef double(*MENU1)(double,double,double);

 

MENU1 MyMenu[6] = { fun1,fun2,fun3,fun4, fun5,fun6 };

////////////////////////////////////////////////////////////////////////////////

int gordanA(int n, int m)

{ int i, j, k, ir;

double s, c;

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

  for (s = 0, i = 0; i < (n - j); i++)if (fabs(A[i][j]) > fabs(s)) s = A[ir = i][j];

  if(s==0)return -1;

  for (k = j + 1; k < m; k++){

        c = A[ir][k]/s;

        for (i = 0; i < ir; i++)A[i][k] -= c * A[i][j];

        for (i = ir + 1; i < n; i++)A[i - 1][k] = A[i][k] - c * A[i][j];

        A[n - 1][k] = c;

  }

}

return 0;

}

///////////////////////////////////////////////////////////////////////////////

long double Stp(int a, int n)

{

long double c,bi;

int k;

c=1;

k=n;

bi=a;

while(k>0){

  if(k%2==1)c*=bi;

  bi*=bi;

  k/=2;

}

return c;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////

void CursorOff(void)

{asm{

  mov ah,1

  mov ch,0x20

  int 0x10

}

}

///////////////////////////////////////////////////////////////////////////////////////////////////////

Spisok **GenSeY(int Mas_y,int & Counter)

{ Counter=0;

Spisok **Y = new Spisok* [Mas_y];

for (int i = 0; i< Mas_y; i++){

  int m = 0;

  int *Pro = new int [Mas_y];

  Spisok *beg = NULL, *end = NULL;

  for (int j = 0; j< Mas_y; j++){

        int k = random(Mas_y);

        int flag = 0;

        for (int j = 0; j< m; j++)if (k==Pro[j]) flag = 1;

        if (k!= 0 && flag == 0){

               Pro[m] = k;

               m++;

               if ((beg==NULL) && (end==NULL)){

                      end=new(Spisok);

                      if (end == NULL) {cout << "Lack of memory";exit (1);}

                      beg=end;

               }

               else{

                      end=end->next=new (Spisok);

                      if (end==NULL) {cout <<"L a c k of m e m o r y!"; exit (1);}

               }

               end->next=NULL;

               end->index = k;

               Counter++;

        }

  }

  Y [i] = beg;

  delete [] Pro;

}

 return Y;

}

////////////////////////////////////////////////////////////////////////////////

Array *GenSeX(int Mas_y,int & Counter)

{ Counter=0;

Array *X = new Array[Mas_y*Mas_y];

if(X==NULL){cout<<"\n net u mena stolko pamaty!!!\n";exit(1);}

randomize();

for (int i = 0; i< Mas_y; i++){

  int m = 0;

  int *Pro = new int [Mas_y];

  for (int j = 0; j< Mas_y; j++){

        int k = random(Mas_y);

        int flag = 0;

        for (int j = 0; j< m; j++)if (k==Pro[j]) flag = 1;

        if (k!= 0 && flag == 0){

               X[Counter].I=i;

               X[Counter].J=k;

               Pro[m] = k;

               m++;

               Counter++;

        }

  }

   delete [] Pro;

}

 return X;

}

////////////////////////////////////////////////////////////////////////////

int Number(int & kol2,char *st)

{ int N;

  ifstream file;

  int kol1 = 0; kol2 = 0;

 

  file.open(st);

  if (!file) cerr <<"Can not open file!!!!!";

  else

        {file >> N;

         file.get();

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

               {char *string = new char[3*N];

                file.getline(string,3*N,'\n');

 

                for(int j = 0; string[j]!= '0'; j++)

                      {if (string[j] == ' ')

                             //{if((j%2!=0)||(j > N*3))

                             // {cout <<"error in file "<<st;return 0;}

                             if (i<N) kol1++;

                              else kol2 ++;

                      }

                delete [] string;

                }

        }

  file.close();

  //cout << kol1 <<"\t"<< kol2;

  return kol1;

 

}

////////////////////////////////////////////////////////////////////////////////

Array *ReadFileX(Array *X,char * st)

{

  ifstream file;

  int n;

  file.open(st);

  if (!file) cerr <<"Can not open file!!!!!";

  else

        {file >> n;

         file.get();

         int k = 0,n1=0;

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

                file >> n1;

                while (n1!= 0){

                      X[k].I = i;

                      X[k].J = n1-1;

                      k++;

                      n1=0;

                      file >> n1;

                      //cout << X[k-1].I<< "\t"<<X[k-1].J<<"\n";

               }

         }

  }

  file.close();

return X;

}

////////////////////////////////////////////////////////////////////////////////

Spisok **ReadFileY(Spisok **Y,char *st)

{

  int n;;

  ifstream file;

 

  file.open(st);

  if (!file) cerr <<"Can not open file!!!!!";

  else

        {file >> n;

         file.get();

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

               {

                      char *string = new char[580];

                      if (string == NULL) {cout << "Lack of memory";exit(1);}

                      file.getline(string,580,'\n');

                      delete [] string;

               }

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

               {

               int n1;

               file >> n1;

               Spisok *beg=NULL,*end = NULL;

               while (n1!= 0)

               { if ((beg==NULL) && (end==NULL))

                      { end=new(Spisok);

                      if (end == NULL) {cout << "Lack of memory";exit (1);}

                      beg=end;}

               else

 

                      { end=end->next=new (Spisok);

               if (end==NULL) {cout <<"L a c k of m e m o r y!"; exit (1);}}

 

               end->next=NULL;

               end->index = n1-1;

               file >> n1;

               }

                             //file >> n1;

               Y[j] = beg; }

                       }

file.close();

return Y;

}

////////////////////////////////////////////////////////////////////////////////

void print3(Array *X,int N1,int N)

{

int k = 0;

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

  cout <<'\n'<<i<<": ";

  for (k=0; k < N1; k++)if(X[k].I == i)cout << X[k].J<<' ';

}

}

////////////////////////////////////////////////////////////////////////////////

void print2(Spisok **X,int N)

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

  cout <<"\n"<<i<<": ";

  Spisok *rex = X[i];

  while (rex!= NULL){

        cout << rex -> index << " ";

        rex = rex->next;

  }

}

}

////////////////////////////////////////////////////////////////////////////////

void WriteFile(char *st,int Mas_y)

{

ofstream F;

F.open(st);

randomize();

if (!F) cout << "Can not open file "<< st;

F << Mas_y<<"\n";

for (int i = 0; i< 2*Mas_y; i++)

{ int m = 0;

   int *Pro = new int [Mas_y];

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

  {int k = random(Mas_y+1);

  int flag = 0;

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

  {if (k==Pro[j]) flag = 1;}

        if (k!= 0 && flag == 0)

        F<< k <<" ";

  Pro[m] = k;

  m++;

  }

   delete [] Pro;

   F<<"0\n";

}

 F.close();

 

}

 

////////////////////////////////////////////////////////////////////////////////

 

///////////////////////////////////////////////////////////////////////////////////////////////////////

int HowMuch(char *FileName)

{//читаем первую строчку файла и узнаём сколько вершин в графе.

ifstream file;

int n=0;

file.open(FileName);

if (!file) cerr <<"Can not open file!!!!!";

else file >> n;

return n;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////

Array *RaznostZ(int n,int &n1,Array *X,Spisok **Y,Array *Z)

/*обьединение в последовательном представлении

N - кол-во вершин в новом графе, N2 - кол-во дуг в Y.*/

{float i,j,newn=0;

Array *newX = new Array [n1];      //выделение памяти для графа в последоват представлении

//cout<<' ';

for(i=0;i<n1;i++){//cout<<"\b\\";  //цикл для графа в пследовательном пред.

for(j=0;j<n;j++)         //цикл для графа в связанном пред.

  if(X[i].I==j){//cout<<"\bД"; //если совпали выходищие вершины...

        Spisok *max=Y[j]; //max глядит на начало списка Y[j]

        int Flag=0;    //Просто флаговая переменная

        while(max!=NULL){ //Проверяем на совпадения "входящие" вершины

               if(X[i].J==max->index){Flag=1;break;}//если нашли повторение, то выход

               max=max->next; //передвигаемся на следующий элемент списка

        }

        if(Flag==0){   //если не было совпадений вершин, то... всё понятно:

               newX[newn].I=X[i].I;

               newX[newn].J=X[i].J;

               newn++;

        }

        //cout<<"\b|";

  }

//cout<<"\b/";

}

//cout<<"\b \b";

n1=newn;

delete [] Z;

return newX;

}

////////////////////////////////////////////////////////////////////////

void DeleteY(Spisok **Z,int n)

{int i=0;

Spisok *rex;

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

  rex=Z[i];

  while(rex!=NULL){Z[i]=rex->next;delete rex;rex=Z[i];}

  delete Z[i];

}

delete [] Z;

}

////////////////////////////////////////////////////////////////////////////////

Spisok** RaznostY(int n,int n1,Array *X, Spisok **Y)

{/*Расчет разности графов Z=X-Y

  Z,Y - связанном представлении, X - в последовательном.

  n - кол-во вершин графа, n1 - кол-во дуг графа*/

int i,j;

Spisok **Z = new Spisok *[n];//выделение памяти для графа в связанном представлении

for (i=0;i<n;i++) {Z[i] = new Spisok;Z[i]= NULL;}//выделение памяти для графа в связанном представлении

//cout<<' ';

for(i=0;i<n1;i++){//cout<<"\b\/";  //цикл для графа в пследовательном пред.

for(j=0;j<n;j++)         //цикл для графа в связанном пред.

  if(X[i].I==j){//cout<<"\bД"; //если совпали выходищие вершины...

        Spisok *max=Y[j]; //max глядит на начало списка Y[j]

        int Flag=0;    //Просто флаговая переменная

        while(max!=NULL){ //Проверяем на совпадения "входящие" вершины

               if(X[i].J==max->index)Flag=1;//если нашли повторение, то выход

               max=max->next; //передвигаемся на следующий элемент списка

        }

        if(Flag==0){   //если небыло совпадений вершин, то... всё понятно:

                Spisok *end=Z[j], *beg=Z[j], *pred=Z[j];

                while (end!=NULL) {pred = end;end = end ->next;}

           end = pred;

                if((beg==NULL)&&(end==NULL))Z[j]=beg=end=new(Spisok);

                else end = end -> next = new (Spisok);

                end -> next = NULL;

                end -> index = X[i].J;

        }

        //cout<<"\b|";

  }

//cout<<"\b\\";

}

//cout<<"\b \b";

DeleteY(Y,n);           //Убийство связанного графа Игрыка!

return Z;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////

void Demo(void)

/* Х - в последовательном представлении

  У - в связанном представлении*/

 

{ int n=4,N2;

clrscr();        //очистка экрана

CursorOff();

cout<<"\t\tДемонстрация работоспособности программы."<<endl;

char st [] ="GrapH.txt"; //имя генерируемого файла

cout<<"\t\tИмя файла с данными задачи: "<<st<<endl;

WriteFile(st,n);    //генерация файла с н вершинами

n=HowMuch(st);        //подсчет числа вершин графов

int N1 = Number(N2,st); //подсчет числа дуг

Array *X = new Array [N1]; //выделение памяти для графа в последоват представлении

X = ReadFileX(X,st);     //чтение графа в последовательном представлении

cout << "\n X в последовательном";

print3(X,N1,n);       //вывод графа в последовательном представлении

Spisok **Y = new Spisok *[n]; //выделение памяти для графа в связанном представлении

for (int i=0;i<n;i++) Y[i] = new Spisok;//выделение памяти для графа в связанном представлении

Y = ReadFileY(Y,st);      //чтение графа в связанном представлении

cout << "\n Y в свяанном";

print2(Y,n);              //печать графа в связанном представлении

Array *Z = new Array[n]; //выделение памяти для графа в последоват представлении

int nZ=N1;

Z=RaznostZ(n,nZ,X,Y,Z); //считаем разность графов: первый параметр - число вершин, второй и третий

                      //граффы в соответствующем представлении.

 

cout<<"\n Z=X-Y в последовательном";

print3(Z,nZ,n);    //вывод графа в последовательном представлении

 

//Spisok **Z1 = new Spisok *[n];//выделение памяти для графа в связанном представлении

//for (i=0;i<n;i++) {Z1[i] = new Spisok;Z1[i]= NULL;}//выделение памяти для графа в связанном представлении

 

Y=RaznostY(n,N1,X,Y); //считаем разность графа и записываем это в граф Y

 

cout<<"\n новый Y - в связанном представлении";     //Вывод подсказки - "Что делать"

print2(Y,n);              //печать графа в связанном представлении

 

delete [] X;              //удаление из памяти графа Х

delete [] Z;

DeleteY(Y,n);      //Убийство связанного графа Игрыка!

//DeleteY(Z1,n);   //Убийство связанного графа Зюблы!

cout<<"\n\t\t\tPress Any Key to continue\b"<<flush;//Вывод подсказки - "Что делать дальше"

getch();           //Ждём нажатия любой клавиши

}

////////////////////////////////////////////////////////////////////////////////

void TimeOut(int Tik, float TikTak[], int Mas_x[], int Mas_y[],int Mas_z[])

{

clrscr();

int i=0,j=0,k=0,h=0,count=0;

cout<<'\n';

for(;i<N;i++)for(;j<M;j++) A[i][j]=0;

for (k = 0; k < Tik; k++)

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

        for (int j = 0; j < Tik; j++) A[i][j] += (*MyMenu[j])(Mas_x[k],Mas_y[k],Mas_z[k]) * (*MyMenu[i])(Mas_x[k],Mas_y[k],Mas_z[k]);

        A[i][N]+=(*MyMenu[i])(Mas_x[k],Mas_y[k],Mas_z[k])*TikTak[k];

  }

 

if(gordanA(N,M))cout<<"Матрица вырождена!!!"; //N-колво строк, M-кол-во столбцов

 

//for(i=0;i<N;i++){cout<<'\n';for(j=0;j<M;j++) cout<<A[i][j]<<'\t';}

cout<<"\t\t\t O(nX,nY,nZ)=C1*nX*(nY+nZ)"<<endl;

for(i=0;i<N-1;i++) cout<<"\n\t\t\t\tC"<<i<<'='<<A[i][M];

cout <<"\n\nКол-во дуг Х\tКол-во дуг Y\tКол-во дуг Z\tЭксперимент\tТеория";//<<"Mas_tx Mas_Tnx";

double *Mas_Tnz=new double[N];

for(i=0;i<Tik;i++) Mas_Tnz[i]=0;

 

for (int y = 0; y < Tik; y++){

  for (i = 0; i < N; i++){Mas_Tnz[y] += ((*MyMenu[i])(Mas_x[y],Mas_y[y],Mas_z[y]))*(A[i][N]);}

  cout <<"\n"<<Mas_x[y]<<"\t\t"<< Mas_y[y]<<"\t\t"<<Mas_z[y]<<"\t\t"<<TikTak[y]<<"\t"<<Mas_Tnz[y];

}

 

}

////////////////////////////////////////////////////////////////////////////////

void TestTime(int n)

/*                    Х - в последовательном представлении

                      У - в связанном представлении

*/

{

clrscr();          //очистка экрана

cerr<<"\t\tНемного подождите - идут эксперименты...\n";

int i,nX=0,nZ=0,nY=0;

float TikTak[19],Secundomer=0;

int Mas_x[12],Mas_y[12],Mas_z[12];

for(int Tik=0;Tik<N;Tik++){  //цикл начала экспериментов от Н до Н+45

n=n+Tik*5;         //количество генерируемых вершин

Array *X = new Array [nX]; //выделение памяти для графа в последоват представлении

X = GenSeX(n,nX);  //чтение графа в последовательном представлении

Mas_x[Tik]=nX;     //запоминаем кол-во вершин в графе ЫксА

Spisok **Y = new Spisok *[n];//выделение памяти для графа в связанном представлении

for (int i=0;i<n;i++){Y[i] = new Spisok;Y[i]=NULL;}//выделение памяти для графа в связанном представлении

Y = GenSeY(n,nY);  //чтение графа в связанном представлении

Mas_y[Tik]=nY;     //запоминаем кол-во вершин в графе ИгрикА

Array *Z = new Array[n];  //выделение памяти для графа в последоват представлении

cerr <<"\nЧисло вершин в графе = "<<n;

cout<<"\nRaznostZ...";

nZ=nX;             //так надо Сергей Михайловичь

Z=RaznostZ(n,nZ,X,Y,Z); //считаем разность графов: первый параметр - число вершин, второй и третий

                      //граффы в соответствующем представлении.

//cout<<"\nnX="<<nX<<"\tnY="<<nY<<"\tnZ="<<nZ;

Mas_z[Tik]=nZ;     //запоминаем кол-во вершин в графе зЮблА

cout<<"\t\t\tэтот комп пока ещё работает...\nRasnostY...\t\t\tПовторяю который раз?! Ответ: ";

for(int XXX=0;XXX<10;XXX++){ //цикл повторений

  cout<<"\b"<<XXX; //Вывод количества повторений

  Secundomer=clock(); //"..на старт... внимпние... марш!!!" - засекли начала эксперимента.

        Y=RaznostY(n,nX,X,Y); //считаем разность графа и записываем это в граф Y

  TikTak[Tik]=(clock()-Secundomer);//"Финиш!!!" - получили конец эксперимента

}                  //к.ц. цикла вовторений

TikTak[Tik]=TikTak[Tik]/(10 * CLK_TCK);//Вычисление тиков!!!

 

delete [] X;       //удаление из памяти графа Х

DeleteY(Y,n);      //Убийство связанного графа Игрыка!

delete [] Z;//удаление из памяти графа в последовательном представлении

n-=Tik*5;          //"предохраитель" от геометрической прогрессии...

}                     //к.ц. для экспериментов!!!

//cout <<"\nMas_x\tMas_y\tMas-z\tTikTak";

//for (int y = 0; y < Tik; y++)cout <<"\n"<<Mas_x[y]<<"\t"<< Mas_y[y]<<'\t'<<Mas_z[y]<<"\t"<<TikTak[y]<<" \t";

cout<<"\n\nесли вы видите эту надпись, значит эксперименты прошли удачно"

  <<"\n\tPress any key для вывода результатов на экран."<<flush;

getch();           //Ждём нажатия любой клавиши

TimeOut(Tik,TikTak,Mas_x,Mas_y,Mas_z);//вызываем функцию общёта всего и вся

cout<<"\n\n\t\t Press Any Key for exit to you system."<<flush;//Вывод подсказки - "Что делать дальше"

getch();           //Ждём нажатия любой клавиши

}

///////////////////////////////////////////////////////////////////////////

void main (void)

{

Demo();

TestTime(85);

}

///////////////////////////////////////////////////////////////////////////

Тесты.

Для демонстрации работоспособности программы я вывожу некий, случайно сформированный граф на дисплей для маленькой размерности (в данном примере 4 вершины), далее вывожу на экран разность этих графов. Как легко убедиться, в том что это правильная разность, можно предположить, что это будет справедливо и для графов большей размерности.

      

Демонстрация работоспособности программы.            Имя файла с данными задачи: GrapH.txt  X в последовательном 0: 2 1: 1 3 0 2: 2 0 3 3: 3 0  Y в свяанном 0: 1 3 1: 1 0 2: 3 2 3: 2 3 1  Z=X-Y в последовательном 0: 2 1: 3 2: 0 3: 0  новый Y - в связанном представлении 0: 2 1: 3 2: 0 3: 0                    Press Any Key to continue

После предложения программы нажать любую клавишу вы видите перед собой экран следующего содержания:

 

Немного подождите - идут эксперименты... Число вершин в графе = 85 RaznostZ...                этот комп пока ещё работает... RasnostY...                Повторяю который раз?! Ответ:9 Число вершин в графе = 90 RaznostZ...                этот комп пока ещё работает... RasnostY...                Повторяю который раз?! Ответ:9 Число вершин в графе = 95 RaznostZ...                этот комп пока ещё работает... RasnostY...                Повторяю который раз?! Ответ:9 Число вершин в графе = 100 RaznostZ...                этот комп пока ещё работает... RasnostY...                Повторяю который раз?! Ответ:9 Число вершин в графе = 105 RaznostZ...                этот комп пока ещё работает... RasnostY...                Повторяю который раз?! Ответ:9 Число вершин в графе = 110 RaznostZ...                этот комп пока ещё работает... RasnostY...                Повторяю который раз?! Ответ:9 если вы видите эту надпись, значит эксперименты прошли удачно    Press any key для вывода результатов на экран.

 

После предложения программы нажать любую клавишу вы видите перед собой экран следующего содержания:

O(nX,nY,nZ)=C1*nX*(nY+nZ)                            C0=3.894613e-06                            C1=1.953171e-06                            C2=1.941442e-08                            C3=7.187807e-12                            C4=3.05476e05 Верш Кол-во дуг Х  Кол-во дуг Y Кол-во дуг Z Эксперимент Теория 70 3028                   3045              1120            0.06044    0.058657 75 3507                 3531               1289            0.071429   0.074507 80 4032                 3978               1471                 0.082418   0.082331 85 4488                 4577              1608             0.104396   0.103425 90 5136                 5061              1898             0.126374   0.125175 95     5692                  5638               2075             0.137363   0.138322                             Press Any Key for exit to you system.

В графе эксперимент я вывожу экспериментально время – время которое я получил при выполнение моей процедуры. В графе теория я вывожу значение времени получившееся при подстановке мультипликативных констант в исходное уравнение.

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

Им. К.Э. ЦИОЛКОВКОГО

      КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе на тему: “Разработка алгоритмов и

программ выполнения операций над последовательными

и связанными представлениями структур данных ”

по курсу “ Теория алгоритмов и вычислительных

методы ”

Руководитель: Авдошин С.М.

Дата сдачи: _____________

Подпись:   _____________

Студент: Лицентов Д.Б.

Группа: 3ИТ- 2-26

Москва

1998

1. Постановка задачи.

 

 

Дано:

  Два орграфа X и Y с N вершинами ( X в последовательном представлении, Y в связанном представлении) без кратностей. Дуги орграфов образуют                 неупорядоченные списки. Орграфы задаются неупорядоченными списками смежных вершин - номеров вершин, в которые ведут ребра из каждой вершины графа.

Требуется:

Выполнить над ребрами орграфов операцию разности (X/Y). В результате выполнения этой операции новый орграф Z определяется в связанном представлении, а старый орграф X исправляется в последовательном представлении.

Особенности представления данных:

Последовательное представление данных: одномерный массив Array, содержащую два целочисленных поля I (содержит номер вершины, из которой исходит дуга) и J (содержит номер вершины, в которую входит дуга).

      

Array[_]			I		J
Array[ 1 ]			From		To
Array[ 2 ]			From		To
…			From		To
Array[ N ]			From		To

      N – количество дуг в орграфе X.

Связанное представление данных: одномерный массив Spisok указателей на структуру index, представляющую собой элемент списка и содержащий поле: целочисленное i ndex (содержит номер вершины, в которую входит дуга) и Next - указатель на структуру Spisok, указывающее на следующий элемент списка

Spisok[ _ ]	NEXT		index	next		index	next		Index	Next
Spisok[ 1 ]			To			…			To	NULL
…			To			…			To	NULL
Spisok[ N ]			To			…			To	NULL

 

N - количество вершин в графе Y,Z.

 

 

2. Внешнее описание программы.

 

Ввод информации об неориентированных графах происходит из файла, формат которого должен быть нижеследующим:

N

  X11 X12... X1k1 0

  X21 X22... X2k2 0

 ...

  XN1 XN2... XNkN 0

  Y11 Y12... Y1k1 0

  Y21 Y22... Y2k2 0

 ...

YN1 YN2... YNkN 0

где N - число вершин в графах

Xij - номер очередной вершины смежной i в графе X (i = 1..N, j=1..ki)

 Yij - номер очередной вершины смежной i в графе Y (i = 1..N, j=1..ki)

Если из какой-то вершины не выходит ни одного ребра, то для нее в исходных данных задаем только ноль (например ‘0’ - вершина 2 изолирована). Таким образом, для каждого графа должно вводится в общей сложности N нолей.

Формат печати результатов работы программы представлен в следующем формате:

Даны неориентированные графы X и Y без кратностей.

Для каждого графа задаем номера вершины смежности с данной.

Граф X (в ЭВМ в последовательном представлении):

1: X11 X12... X1k1

2: X21 X22... X2k2

 ...

N: XN1 XN2... XNkN

Граф Y (в ЭВМ в связанном представлении):

1: Y11 Y12... Y1k1

2: Y21 Y22... Y2k2

 ...

N: YN1 YN2... YNkN

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

с получением нового графа Z (в связанном представлении):

1: Z11 1,Z12... Z1k1

2: Z21 Z22... Z2k2

 ...

N: ZN1 ZN2... ZNkN

И исправлением старого графа X (в последовательном представлении):

1: X11 X12... X1k1

2: X21 X22... X2k2

 ...

N: XN1 XN2... XNkN

Кол-во вершин, кол-во дуг графа X, кол-во дуг графа Y

и кол-во времени, затраченного на вычисление разности X и Y:

N MX MY T

где T - кол-во времени, затраченного на вычисление разности X и Y

Zij - номер очередной вершины смежной i в графе Z (i = 1..N, j=1..ki)

MX - кол-во дуг в графе X

MY - кол-во дуг в графе Y

Метод решения:

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

Аномалии исходных данных и реакция программы на них:

1. нехватка памяти при распределение: вывод сообщения на экран и завершение работы программы;

2. неверный формат файла: вывод сообщения на экран и завершение работы программы;

Входные данные

Входными данными для моей работы является начальное число вершин графа, которое по мере работы программы увеличиться на 30 верши. Это число не может превосходить значения 80 вершин, так как в процессе работы программы число увеличивается на 30 и становиться 110 – это «критическое» число получается из расчета 110» 2¹⁶/3. Это происходит потому, что стандартный тип int не может вместить в себя более чем 2¹⁶. Мне же требуется для нормально работы программы, чтобы тип вмещал в себя утроенное количество вершин неориентированного графа. Конечно, это всего лишь приближение, но с учётом того, что графы генерируются случайно возможность набора 33000 невелико и, следовательно, допустимо.

Входной файл генерируется каждый раз новый.

Графы для расчета мультипликативных констант генерируются случайным образом, используя датчик случайных чисел, это-то и накладывает ограничения на количество вершин. Дело в том, что при работе с генератором случайных чисел предпостительно иоспользовать целый тип данных – так говорил товарищ Подбельский В.В.

Оценка временной сложности.