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 вершины), далее вывожу на экран разность этих графов. Как легко убедиться, в том что это правильная разность, можно предположить, что это будет справедливо и для графов большей размерности.