Scrieti programul C care permite efectuarea tuturor operatiilor asupra unui graf implementat prin matricea de adiacenta(varianta II)cu vizualizarea naturala a grafului dupa fiecare operatie efectuata.
Descrierea algoritmului.
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 tabloul 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 conectat 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 nodurilor grafului 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 */
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;
Programul C:
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
#include <math.h>
#include <process.h>
#include <ctype.h>
#define PI (2*asin(1))
#define r 100
#define PATH 'C:BORLANDCBGI'
#define maxN 20
typedef int TipCheie;
typedef int TipInfo;
typedef TipCheie 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;
void initializare_mod_grafic(void)
} /* initializare */
int CautNod(Graf g, TipCheie cheie)
/* CautNod */
void InserNod(Graf *g, TipEl e)
g->Arce[g->Contor-1][g->Contor-1]=1;
} /* InserNod */
void InserArc(Graf *g, TipArc IndiceArc)
/* InserArc */
void SuprimaNod(Graf *g, int IndiceNod)
g->Arce[IndiceNod][IndiceNod] = 1;
g->Contor--;
} /* SuprimaNod */
void SuprimArc(Graf *g, TipArc IndiceArc)
/* SuprimArc */
void afisareNoduri(Graf g)
;
int i,xi,yi;
x0 = (getmaxx()/2)+80;
y0 = getmaxy()/2;
for (i=0; i<g.Contor; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
void Creare(Graf *g)
if (g->Contor!=0)
printf('Introduceti arc?(D/N):');
fflush(stdin);scanf('%c',&c); c = toupper(c);
}
}
closegraph();
}/* Creare */
void asteptare(void)
/* asteptare */
void main(void)
else
afisareGraf(g);
break;
case 'C':
clrscr();
Creare(&g);
break;
case 'I':
clrscr();
if(g.Contor==0)
printf('Introduceti cheia nodului: ');
fflush(stdin); scanf('%c',&e); e = toupper(e);
InserNod(&g,e);
afisareGraf(g);
break;
case 'N':
clrscr();
if(g.Contor==0)
printf('Introduceti nodul de pornire: ');
fflush(stdin);
scanf('%c',&ch); ch = toupper(ch);
if((IndiceArc.lin = CautNod(g,ch)) == -1)
printf('Introduceti nodul de sosire: ');
fflush(stdin);
scanf('%c',&ch); ch = toupper(ch);
if((IndiceArc.col = CautNod(g, ch)) == -1)
InserArc(&g, IndiceArc);
afisareGraf(g);
break;
case 'S':
clrscr();
if (g.Contor>0)
else
}
else
break;
case 'T':
clrscr();
if (g.Contor>0)
else
}
else
break;
default: printf('Ati tastat optiune gresita!n');
break;
}/* switch */
}
while (optiune!='X');
}/* main */
Tema 2
Acelasi enunt ca si la tema 1,cu mentiunea ca, cheile contin in structura lor pe langa cheie si informatie de tip char[10].
Programul C:
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
#include <math.h>
#include <process.h>
#include <ctype.h>
#define PI (2*asin(1))
#define r 100
#define PATH 'C:BORLANDCBGI'
#define maxN 20
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;
void initializare_mod_grafic(void)
} /* initializare */
int CautNod(Graf g, TipCheie cheie)
/* CautNod */
void InserNod(Graf *g, TipEl e)
g->Arce[g->Contor-1][g->Contor-1] = 1;
} /* InserNod */
void InserArc(Graf *g, TipArc IndiceArc)
/* InserArc */
void SuprimaNod(Graf *g, int IndiceNod)
g->Arce[IndiceNod][IndiceNod] = 1;
g->Contor--;
} /* SuprimaNod */
void SuprimArc(Graf *g, TipArc IndiceArc)
/* SuprimArc */
void afisareNoduri(Graf g)
;
int i, xi, yi;
x0 = (getmaxx()/2)+80;
y0 = getmaxy()/2;
for (i=0; i<g.Contor; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
void Creare(Graf *g)
if (g->Contor!=0)
printf('Introduceti arc?(D/N):');
fflush(stdin);scanf('%c',&c); c = toupper(c);
}
}
closegraph();
}/* Creare */
void asteptare(void)
/* asteptare */
void main(void)
else
afisareGraf(g);
break;
case 'C':
clrscr();
Creare(&g);
break;
case 'I':
clrscr();
if(g.Contor==0)
printf('Introduceti cheia nodului: ');
fflush(stdin); scanf('%c', &e.cheie);
e.cheie = toupper(e.cheie);
printf('Introduceti informatia din nod: ');
fflush(stdin); scanf('%s', &e.info);
InserNod(&g, e);
afisareGraf(g);
break;
case 'N':
clrscr();
if(g.Contor==0)
printf('Introduceti nodul de pornire: ');
fflush(stdin);
scanf('%c',&ch); ch = toupper(ch);
if((IndiceArc.lin = CautNod(g, ch)) == -1)
printf('Introduceti nodul de sosire: ');
fflush(stdin);
scanf('%c',&ch); ch = toupper(ch);
if((IndiceArc.col = CautNod(g, ch)) == -1)
InserArc(&g, IndiceArc);
afisareGraf(g);
break;
case 'S':
clrscr();
if (g.Contor>0)
else
}
else
break;
case 'T':
clrscr();
if (g.Contor>0)
else
}
else
break;
default: printf('Ati tastat optiune gresita!n');
break;
}/* switch */
}
while (optiune!='X');
}/* main */
|
