Scrieti programul C care permite efectuarea tuturor operatiilor asupra unui graf implementat cu matricea de adiacenta (varianta II).
Descrierea algoritmului.
In cazul in care numarul de noduri ale grafului este fix, ceea ce presupune ca vom putea adauga noi arce sau suprima in structura de date de tip graf, dar nu si noduri, atunci tipurile de date folosite si variabilele utilizate in prelucrarea structurii de tip graf cu 646j95g varianta II vor fi urmatoarele:
#define NrNoduri 5
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
Functiile care vor descrie operatiile efectuate asupra structurii de tip graf astfel implementata vor presupune si testul daca exista arc intre 2 noduri x si y. Functia care realizeaza acest lucru este:
int Adiacent(TipEl x, TipEl y, Graf g)
/* Adiacent */
Functia index realizeaza corespondenta nume nod – indice de acces in matricea de adiacenta.
Grafurile orientate sunt simple restrictii ale grafurilor orientate, in sensul ca daca exista arc de la x la y, <x, y> se materializeaza punand pe linia corespunzatoare lui x si coloana corespunzatoare lui y in matricea Arce valoarea 1, dar nu si pe linia corespunzatoare lui y si coloana corespunzatoare lui x.
In cazul grafurilor valorice stim ca fiecare arc are asociat un numar numit valoarea(costul) arcului, prin urmare in implementarea grafurilor valorice va trebui sa reprezentam si valoarea asociata fiecarui arc.
Tipurile de structuri de date si variabile folosite in implementarea unui graf valoric cu varianta II vor fi urmatoare:
#define NrNoduri 5
typedef char TipCheie;
typedef int TipInfo;
typedef struct
TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipVal;
typedef struct
TipArc;
typedef TipArc TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
TipVal v;
Functii folosite in implementarea grafurilor valorice:
void InitGraf(Graf *g); - realizeaza initializarea grafului
void AdaugaV(TipEl x, TipEl y, TipVal v, Graf *g); - adauga un arc de la x la y de valoare v;
void Sterge(TipEl x, TipEl y, TipVal *v,Graf *g); - sterge arcul de la x la y(daca exista) si seteaza pe v la valoarea asociata grafului;
Programul C:
#include <stdio.h>
#include <conio.h>
#include <ctype.h> /* pt. functia toupper() */
#include <graphics.h>
#include <stdlib.h>
#include <math.h>
#define CALE 'C:BORLANDCBGI'
#define PI (2*asin(1))
#define r 100
#define NrNoduri 5
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
int Adiacent(TipEl x, TipEl y, Graf g)
/* Adiacent */
void InitGraf(Graf *g)
}/* InitGraf */
void Adauga(TipEl x, TipEl y, Graf *g)
else
}/* Adauga */
void Sterge(TipEl x, TipEl y, Graf *g)
else
}/* Sterge */
int index(char c)
/* index */
void asteptare(void)
/* asteptare */
void initializare_mod_grafic(void)
} /* initializare */
void afisareNoduri(Graf g)
;
int i, xi, yi, x0, y0;
x0 = (getmaxx()/2) + 80;
y0 = getmaxy()/2;
for(i=0; i<NrNoduri; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
void main(void)
}
while(op == 'N');
afisareGraf(g);
break;
case 'I':
printf('nIntroduceti nodul de pornire: ');
x = toupper(getche());
printf('nIntroduceti nodul de sosire: ');
y = toupper(getche());
Adauga(x, y, &g);
afisareGraf(g);
break;
case 'S':
printf('nIntroduceti nodul de pornire: ');
x = toupper(getche());
printf('nIntroduceti nodul de sosire: ');
y = toupper(getche());
Sterge(x, y, &g);
afisareGraf(g);
break;
}
}
while(optiune != 'X');
}/*main*/
Tema 2
Scrieti programul C care permite efectuarea tuturor operatiilor asupra unui graf valoric implementat cu matricea de adiacenta (varianta II). Vizualizarea grafului e sub forma naturala.
Programul C:
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <graphics.h>
#include <ctype.h>
#include <string.h>
#define PI 2*asin(1)
#define r 100
#define CALE 'C:BORLANDCBGI'
#define NrNoduri 4
typedef char TipCheie;
typedef int TipInfo;
typedef struct
TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipVal;
typedef struct
TipArc;
typedef TipArc TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
TipVal v;
int CautNod(Graf g,TipCheie cheie)
/* CautNod */
int index(char c)
/* index */
void InitGraf(Graf *g)
}/* InitGraf */
void creare()
if(ok)
i--;
else
}
printf('Trasati un arc?(d/n)');fflush(stdin);
scanf('%c',&c);c=toupper(c);
while(c=='D')
}
printf('Trasati un arc?(d/n)'); fflush(stdin);
scanf('%c', &c); c = toupper(c);
}
}/* creare */
int Adiacent(TipEl x, TipEl y, Graf g)
/* Adiacent */
void AdaugaV(TipEl x, TipEl y, TipVal v, Graf *g)
else
}/* Adauga */
void Sterge(TipEl x, TipEl y, TipVal *v, Graf *g)
else
}/* Sterge */
void initializare_mod_grafic(void)
} /* initializare */
void afisareNoduri(Graf g)
;
int i, xi, yi, x0, y0;
x0 = getmaxx()/2;
y0 = getmaxy()/2;
for(i=0; i<NrNoduri; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
void main()
}
afisareGraf(g);
break;
case 'D':
printf('Introduceti primul nod: ');
fflush(stdin); scanf('%c',&x); x = toupper(x);
if(CautNod(g,x)<0)
printf('Nodul nu exista!n');
else
}
afisareGraf(g);
break;
case 'E':break;
default:printf('Optiune gresita!n');
}
}while(c != 'E');
}/* main */
|
