Scrieti programul C care va permite crearea si vizualizarea sub forma naturala a unui graf implementat prin matricea de adicenta varianta a II-a, atunci cand multimea nodurilor este neordonata.
Tema2: Scrieti programul care va permite efectuarea tuturor operatiilor de baza asupra unui graf implementat prin matrice de adiacenta varianta a II-a.
Descrierea algoritmului 515i84f
Implementarea unui TDA graf cu matricea de adicenta varianta a II-a este o varianta mai flexibila decat varianta I care presupune urmatoarea structura de date:
#define maxN 100
typedef int TipCheie;
typedef int TipInfo;
typedef struct
TipEl;
typedef TipEl TipTabEl[maxN];
typedef int TipMatAdi[maxN][maxN];
typedef int TipContor;
typedef struct
Graf;
typedef struct
TipArc;
Graf G;
TipEl e;
TipArc IndiceArc;
int IndiceNod;
int x0,y0,i,j,n;
In anumite situatii nodurile nu contin si alte informatii in afara de cheia nodului, situatie in care TipEl coincide cu TipCheie; in alte situatii nodurile s-ar putea sa nu contina nici cheia nodurilor, situatie in care ne intereseaza doar numele nodurilor(al catelea este nodul in lista nodurilor) in vederea conectarii nodurilor in aceasta reprezentare. In cele ce urmeaza pentru simplificarea descrierii operatiilor ce le vom efectua asupra unui TDA graf implementat cu matricea de adiacenta varianta II vom presupune ca TipEl coincide cu TipCheie.
Multimea nodurilor grafului poate fii ordonata sau nu. Daca multimea nodurilor este ordonata atunci determinarea indexului de acces al unui nod in tabloul Noduri presupune o cautare binara, in schimb daca multimea nodurilor este neordonata atunci determinarea indexului de acces presupune o cautare liniara.
Functia care realizeaza acest lucru este:
int CautNod(Graf g, TipCheie cheie)
/* CautNod */
Inserarea unui nod in graful g astfel implementat depinde daca multimea nodurilor este ordonata sau nu. Daca multimea nodurilor este neordonata, atunci inserarea unui nou nod in graful g va presupune:
g.Contor++;
plasarea noului nod in tablou noduri pe pozitia corespunzatoare contorului:
g.Noduri[g.Contor-1] = e; unde e este noul nod de adaugat.
Functia C care realizeaza inserarea unui nod izolat in graful g este:
void InserareNod(Graf *g, TipEl e)
/* daca exista arcul (e, e)
g->Arce[g->Contor-1][g->Contor-1]=1;
} /* InserNod */
Daca nodul de inserat e conecttat cu alte noduri ale grafului atunci in matricea Arce va trebui sa inseram pe rand arcele noi.
Functia C care realizeaza inserarea unui nou arc in graful g este:
void InserArc(Graf *g, TipArc IndiceArc)
/* InserArc */
Pentru a crea un graf g implementat prin matricea de adiacenta varianta II va trebui sa parcurgem 2 etape:
precizarea multimii nodurilorgrafului printr-un apel al functiei InserNod pentru fiecare nod al grafului;
completarea matricei de adiacenta a grafului printr-un apel pentru fiecare arc al grafului a functiei InserArc.
Observatii:
Daca multimea nodurilor este ordonata, atunci dupa ce determinam pozitia unde trebuie inserat noul nod va trebui sa realizam mutarea tuturor nodurilor de la aceasta pozitie spre dreapta pentru a elibera pozitia respectiva, urmand ca pe aceasta pozitie sa fie inserat noul nod.
In mod similar daca se doreste suprimarea unui nod cu indicele IndiceNod din graful g, daca presupunem ca multimea nodurilor este neordonata, atunci suprimarea nodului se poate face copiind pe pozitia IndiceNod din tabloul Noduri elementele care se afla in tabloul Noduri pe pozitia corspunzatoare contorului.
Functia C care descrie suprimarea unui nod din graful d este:
void SuprimaNod(Graf *g, int IndiceNod)
g->Arce[IndiceNod][IndiceNod]=1;
g->Contor--;
} /* SuprimaNod */
Observatii:
Functia SuprimaNod realizeaza suprimarea atat a nodului IndiceNod, cat si a arcelor conexe lui.
Daca se doreste suprimarea unui arc din graful g, arc precizat prin variabila IndiceArc atunci:
g.Arce[IndiceArc.lin] = 0;
g.Arce[IndiceArc.col] = 0;
Rezolvare:
Tema1:Scrieti programul C care va permite crearea si vizualizarea sub forma naturala a unui graf implementat prin matricea de adicenta varianta a II-a, atunci cand multimea nodurilor este neordonata.
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <math.h>
#define R 130
#define r 15
#define pi M_PI
#define maxN 30
typedef char TipCheie;
typedef int TipVal;
typedef TipCheie TipEl;
typedef int TipContor;
typedef TipEl TipTabEl[maxN];
typedef int TipMatAdi[maxN][maxN];
typedef int TipMat[maxN][maxN];
typedef struct
Graf;
typedef struct
TipArc;
double xi,yi,xj,yj,x1,y1,x2,y2,x3,y3,x0,y0,xk,yk,x,y;
double ALFA,ALFA1,ALFA2;
int n,k,i,j,a;
char s[2]=,c1,c2,c;
char sir[2];
Graf g;
TipArc IndiceArc;
TipEl e;
TipMatAdi Drum;
int IndiceNod;
TipVal v;
void Init_Mod_Grafic(void)
} /*Init_Mod_Grafic*/
void Desenare_Noduri(void)
}//Desenare_Noduri
void Desenare_Graf(void)
}//Desenare_Graf
void Inser_Nod(Graf *g,TipEl e)
g->Arce[g->Contor-1][g->Contor-1]=0;
}/*Inser_Nod*/
void Inser_Arc(Graf *g,TipArc IndiceArc)
int Cauta_Nod(Graf g,TipCheie Cheie)
/*Cauta_Nod*/
void Creare(void)
/*crearea multimii arcelor */
if(g.Contor==0)
printf('Nu exista noduri!n');
else
printf('Adaugi arc?(D/N)');
fflush(stdin);scanf('%c',&c);c=toupper(c);
}
}
}
} /*Creare*/
void Afisare_Matrice(TipMatAdi A)
}/*Afisare_Matrice*/
int main(void)
}
break;
case 'G': if(g.Contor!=0)
else
printf('Graful este vid!n');
break;
case 'M': Afisare_Matrice(g.Arce);
break;
case 'E': break;
default : printf('Optiune gresita!n');
break;
}
printf('Tastati Enter!n');
fflush(stdin);
getch();
}
while(op!='E');
return 0;
Rezolvare:
Tema2:Scrieti programul care va permite efectuarea tuturor operatiilor de baza asupra unui graf implementat prin matrice de adiacenta varianta a II-a.
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <math.h>
#define R 130
#define r 15
#define pi M_PI
#define maxN 30
typedef char TipCheie;
typedef int TipVal;
typedef TipCheie TipEl;
typedef int TipContor;
typedef TipEl TipTabEl[maxN];
typedef int TipMatAdi[maxN][maxN];
typedef int TipMat[maxN][maxN];
typedef struct
Graf;
typedef struct
TipArc;
double xi,yi,xj,yj,x1,y1,x2,y2,x3,y3,x0,y0,xk,yk,x,y;
double ALFA,ALFA1,ALFA2;
int n,k,i,j,a;
char s[2]=,c1,c2,c;
char sir[2];
Graf g;
TipArc IndiceArc;
TipEl e;
TipMatAdi Drum;
int IndiceNod;
TipVal v;
void Init_Mod_Grafic(void)
}/*Init_Mod_Grafic*/
void Desenare_Noduri(void)
}//Desenare_Noduri
void Desenare_Graf(void)
}//Desenare_Graf
void Inser_Nod(Graf *g,TipEl e)
g->Arce[g->Contor-1][g->Contor-1]=0;
}/*Inser_Nod*/
void Inser_Arc(Graf *g,TipArc IndiceArc)
void Suprima_Nod(Graf *g, int IndiceNod)
g->Arce[IndiceNod][IndiceNod]=1;
g->Contor--;
} /* Suprima_Nod */
void Suprima_Arc(Graf *g,TipArc IndiceArc)
/*Suprima_Arc*/
int Cauta_Nod(Graf g,TipCheie Cheie)
/*Cauta_Nod*/
void Creare(void)
/*crearea multimii arcelor */
if(g.Contor==0)
printf('Nu exista noduri!n');
else
printf('Adaugi arc?(D/N)');
fflush(stdin);scanf('%c',&c);c=toupper(c);
}
}
}
} /*Creare*/
void Afisare_Matrice(TipMatAdi A)
}/*Afisare_Matrice*/
int main(void)
}
break;
case 'S': printf('Introduceti nodul de suprimat:');
fflush(stdin);scanf('%c',&e);e=toupper(e);
IndiceNod=Cauta_Nod(g,e);
if(IndiceNod!=-1)
Suprima_Nod(&g,IndiceNod);
else printf('Nodul nu exista in graf!n');
Desenare_Graf();
break;
case 'D':if(g.Contor!=0)
}
else
printf('Graful este vid!n');
break;
case 'G': if(g.Contor!=0)
else
printf('Graful este vid!n');
break;
case 'M': Afisare_Matrice(g.Arce);
break;
case 'E': break;
default : printf('Optiune gresita!n');
break;
}
printf('Tastati Enter!n');
fflush(stdin);
getch();
while(op!='E');
return 0;
|
