MINISTERUL EDUCAŢIEI REPUBLICII MOLDOVA

UNIVERSITATEA TEHNICĂ A MOLDOVEI

Facultatea Calculatoare, Informatică si Microelectronică

Automatică si Informatică

RAPORT Lucrare de laborator nr. 1

La Matematica Discretă

Pe tema: Păstrarea grafurilor in memoria calculatorului.

A efectuat: st. gr. AI-101

A verificat: lector superior

Chisinău 2012

1. Scopul lucrării:

1. Studierea metodelor de definire a unui graf : matricea de incidență, matricea de

adiacență, liste.

2. Elaborarea unor proceduri de introducere , extragere si transformare a diferitelor

forme de reprezentare internă a grafurilor cu scoaterea rezultatelor la display si

imprimantă.

2. Sarcina de bază:

1. Elaborați procedura de introducere a unui graf în memoria calculatorului în formă

de matrice de incidență, de matrice de adiacență și listă de adiacență cu posibilități de

analiză a certitudinii.

2. Elaborați proceduri de transformare dintr-o formă de reprezentare in alta.

3. Folosind procedurile enumerate , elaborați programul care vă permite:

* introducerea grafului reprezentat sub oricare forma din cele trei forme cu

posibilități de corecție a datelor.

* păstrarea grafului în memoria externă în formă de lista de adiacență.

* extragerea informației într-una dintre cele trei forme la imprimantă și display.

3. Listing-ul programului in C:

#include"stdlib.h"#include"iostream.h"#include"conio.h"#include"math.h"#include"fstream.h"main(){system("cls");ofstream out("textzz.txt");float A[20][20];int AA[20];int BB[20];int z,t,i,j,n,p=0,b,o,k,r,s,k1,r1,nm,w,po,pp,d,ee=0;cout<<"\n\n\t\t Lucrare de laborator nr.1 la Matematica discreta";cout<<"\n Dam numarul de varfuri: n= "; out<<"\n Dam numarul de varfuri: n= ";cin>>n;

out<<n;n=n+1;cout<<"\n Introducem legaturile \n"; out<<"\n Introducem legaturile \n";for(i=1;i<n;i++){for(j=1;j<n;j++) {cout<<"x"<<i<<"x"<<j<<" "; /*indicator optic*/ out<<"x"<<i<<"x"<<j<<" ";cin>>A[i][j];out<<A[i][j]; }}eticheta:n=n+ee;ee=0; cout<<"\n meniu"; out<<"\n meniu"; cout<<"\n 1: Matriciea de incidenta"; out<<"\n 1: Matriciea de incidenta"; out<<"\n 2: Matriciea de adiacenta"; cout<<"\n 2: Matriciea de adiacenta"; out<<"\n 3: Lista de adiacenta"; cout<<"\n 3: Lista de adiacenta"; out<<"\n 4: Modificarea legaturilor intre virfuri"; cout<<"\n 4: Modificarea legaturilor intre virfuri"; out<<"\n 5: Adaugarea unui varf si a tuturor laturilor comun cu el"; cout<<"\n 5: Adaugarea unui varf si a tuturor laturilor comun cu el"; out<<"\n 6: Evitarea unui varf"; cout<<"\n 6: Evitarea unui varf"; cout<<"\n 7: Iesire"; out<<"\n 7: Iesire"; out<<"\n Alegeti optiunea convenabila si tastati enter:"; cout<<"\n Alegeti optiunea convenabila si tastati enter:\n"; cin>>nm; out<<nm; switch(nm) {case 1 : { cout<<"\n\n Afisarea matricei de incidenta:\n";

out<<"\n\n Afisarea matricei de incidenta\n"; cout<<" º"; /* element pentru regularea matriciei

desenate*/ out<<" º"; for(r=1;r<n;r++){

cout<<"x"<<r<<" º"; /*pu. a ne arata cu care varf este legatura*/

out<<"x"<<r<<" º";} for(i=1;i<n;i++){ cout<<"\n"; out<<"\n"; cout<<"ÍÍÎÍ"; /*a indrepta desenu*/ out<<"ÍÍÎÍ"; for(k=1;k<n;k++){ cout<<"ÍÍÎÍ"; /*pentru a desena kletka*/ out<<"ÍÍÎÍ";} cout<<"\nx"<<i<<"º"; /*elementu de la kare

porneste*/ out<<"\nx"<<i<<"º"; for(j=1;j<n;j++){ cout<<A[i][j]<<" º" ; out<<A[i][j]<<" º" ;}} cout<<"\ndaca doriti sa schimbati varianta alesa tastati

tasta 0"; out<<"\ndaca doriti sa schimbati varianta alesa tastati

tasta 0 "; cin>>w; out<<w; if(w==1){ return 0;} if(w!=1){system("cls"); goto eticheta;}}

case 3 : {cout<<"\n\n\nlist!"; out<<"\n\n\nlist!";for(i=1;i<n;i++){ out<<"\nx"<<i<<" º"; /*trasarea liniea ce desparte varful

principal de sec.*/cout<<"\nx"<<i<<" º";for(j=1;j<n;j++){if(A[i][j]!=0){ out<<j<<" " ;cout<<j<<" " ;}} out<<"0";cout<<"0";}

out<<"\ndaca doriti sa schimbati varianta alesa tastati tasta 0";cout<<"\ndaca doriti sa schimbati varianta alesa tastati tasta 0";cin>>w;out<<w;if(w==1){return 0;}if(w!=1){system("cls");goto eticheta;}}

case 2 :{ cout<<"\n\Afisam matricea de adiacenta:\n"; out<<"\n\Afisam matricea de adiacenta:\n";k=0;p=0;for(i=1;i<n;i++){for(j=1;j<n;j++){if(A[i][j]!=0){k++;AA[k]=i;BB[k]=j;p++;}} }cout<<" "<<"º"; out<<" "<<"º";k=0;for(o=1;o<n;o++){cout<<" x"<<o<<"º"; out<<" x"<<o<<"º";}for(s=1;s<p+1;s++){k++;cout<<"\n";out<<"\n";for(o=1;o<n+1;o++){cout<<"ÍÍÎÍ"; out<<"ÍÍÎÍ";}cout<<"\nu"<<s<<"º "; out<<"\nu"<<s<<"º ";b=0;k1=AA[k];r1=BB[k];for(o=1;o<n;o++){if(k1==r1){if(k1==o){b=2;}if(k1!=o){b=0;}}

if(k1!=r1){if(k1==o){b=-1;}if(k1!=o){b=0;}if(r1==o){b=1;}}if(b<0) {cout<< b<<"º "; out<< b<<"º ";}if(b>=0){cout<<" "<<b<<"º "; out<<" "<<b<<"º ";}}}cout<<"\ndaca doriti sa schimbati varianta alesa tastati tasta 0"; out<<"\ndaca doriti sa schimbati varianta alesa tastati tasta 0";cin>>w;out<<w;if(w==1){return 0;}if(w!=1){system("cls");goto eticheta;}}

case 4: {cout<<"\n alegeti virfurile intre care doriti sa faceti modifikari\n";

cin>>po;cin>>pp;i=po;j=pp;cout<<"dam noua valoare legaturii ";cout<<"x"<<i<<"x"<<j;cin>>A[i][j];system("cls");goto eticheta;}

case 5: {for(i=n;i<n+1;i++){ for(j=1;j<n+1;j++) { cout<<"x"<<i<<"x"<<j<<" "; /*indikator optik*/ cin>>A[i][j];}} for(i=1;i<n;i++){ for(j=n;j<n+1;j++) { cout<<"x"<<i<<"x"<<j<<" "; /*indikator optik*/ cin>>A[i][j];}} ee=1; goto eticheta; }

case 7: {cout<<"Sunteti sigur ca doriti sa iesiti? Daca da, tastati 1.";cin>>w;if(w==1){

return 0;}if(w!=0){system("cls");goto eticheta;} }

case 6: { cout<<" Pe care varf doriti sa-l evitati?"; cin>>d; i=d; for(j=1;j<n;j++) { A[i][j]=NULL;} j=d; for(i=1;i<n;i++);

{ A[i][j]=NULL;} goto eticheta; }

default: {system("cls");cout<<"Alegeti optiunea corecta";goto eticheta; } }

out.close();

return 0;}

4. Afisare la ecran:

5. Concluzie:Prin intermediul acestei lucrari de laborator, am reusit sa elaborez un program in compilatorul C++, prin care am introdus un graf in memoria calculatorului in forma de matrice de incidenta si de adiacenta,lista de adiacenta. Acest program contine si functii de transformare dintr-o forma de reprezentare a grafului in alta si de afisare la display a tuturor functiilor sale prin intermediul unui meniu de navigare.