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

TikTak=cloc() - TikTak;

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

После раскрытия скобок и замены T(n)= T(n)=(c,(n))= получим

Положим Аij=(ti, tj) и B=(ti,TikTak) => мы получили систему уравнений AX=B, где Х=С. Формирование в матрице столбцов А и столбцов В записывается очень легко используя любой алгоритмический язык. После заполнения матрицы её остаётся решить и вывести решения этой задачи. Решение производиться методом Жордана.

Априорная временная оценка процедур.

Процедура вывода графа на экран в последовательном представлении:

Void prin3(Array *X, int N1, int N)

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

N – количество вершин графа.

N1 – количество дуг в графе Х

O(N,N1)=N*N1

Процедура вывода графа на экран в связаном представлении:

Void print3(Spisok **X, int N)

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

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

O(N)=N

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

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

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

N1 – количество вершин в графе Х

X – грав в последовательном представлении

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

Z – грав в последовательном представлении

O(N,N1)=N1*N*k=N1*N2

N2 – количество вершин в графе Y

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

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

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

N1 – количество вершин в графе Х

X – грав в последовательном представлении

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

O(N,N1)=N1*N*(k+l)=N1*(N3+N2)

N2 – количество вершин в графе Y

N3 – количество вершин в графе Z – возвращаемом.

Процедура ввода графов в последовательном представлении:

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

St – указатель на строку с именем файла из которого будет происходить ввод

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

O(N,N1)=N+N2

N2 – количество вершин в графе Y

Процедура ввода графов в последовательном представлении:

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

St – указатель на строку с именем файла из которого будет происходить ввод

X – грав в последовательном представлении

O(N,N1)=N2

N2 – количество вершин в графе X

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

# include

# include

# include

# include

# include

# include

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

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

if (i

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

}

}

}

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

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

cout <<"\n"<

Spisok *rex = X[i];

while (rex != NULL){

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

for(j=0;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

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

//cout<<' ';

for(i=0;i

for(j=0;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Демонстрация работоспособности программы."<

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

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

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

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