НАУЧНЫЕ РАБОТЫ

Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных

F.open(st);

randomize();

if (!F) cout > 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]; //выделение памяти для графа в

последоват представлении

//coutindex){Flag=1;break;}//если нашли

повторение, то выход

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

списка

}

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

всё понятно:

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

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

newn++;

}

//coutnext;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;iindex)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Демонстрация работоспособности программы."<

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

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

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

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

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

для графа в связанном представлении

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"<

"Что делать дальше"

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

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

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

for(i=0;i

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

удачно"

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

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

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

вся

cout<<"\n\n\t\t Press Any Key for exit to you system."<

подсказки - "Что делать дальше"

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 |