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); //считаем разность графов: первый параметр - число вершин, второй и третий