Scrieti programul C care va permite crearea si vizualizarea sub forma naturala a unui graf implementat prin structura de adiacenta varianta multilista (metoda II).
Descriere algoritm.
Un alt mod de implementare a grafurilor, a unui TDA graf este cel cu ajutorul structurilor de adiacenta. In acest caz, fiecarui nod al grafului i se asociaza o lista cu nodurile adiacente lui.
Vom prezenta in cele ce urmeaza 2 metode de implementare a unui TDA graf cu ajutorul struct de adiacenta.
METODA 1 :Se bazeaza pe structuri liniare simplu inlantuite. Fiecarui nod al grafului I se asociaza o lista simplu inlantuita a nodurilor adiacente lui. Aceste liste sunt construite dupa principiul inserarii noului nod in fata listei si se poate utiliza un nod fictiv z pe post de fanion, a carui inlantuire indica nodul insusi.
Inceputurile listelor de a 444c26e diacenta sunt memorate intr-un tablou numit StrAdi indexat dupa nodurile grafului. Inserarea unui arc (x,y) intr-un graf astfel implementat presupune inserarea nodului x in lista de adiacente a nodului y si invers.
Fie graful neorientat :
Fig.1
METODA 2 :Se bazeaza pe utlizarea multilistelor(liste implementate dupa mai multi pointeri). Graful se va implementa printr-o structura de adiacenta in care sunt inlantuite nodurile grafului. Fiecerui nod al grafului I se asociaza lista nodurilor adiacente lui,fiecare nod al grafului va contine pe langa elementele care definesc nodul, un camp care inlantuieste nodurile grafului si un camp care marcheaza inceputul listei de adiacenta a acelui nod.
Observatii:
Metoda 1 de implementare a grafului cu ajutorul StrAdi este indicata in cazul in care se solicita pt un nod al grafului lista nodurilor adiacente lui. Este dificil de suprimat, adaugat arce in acest caz.
Ordinea in care se introduc arcele in metoda 1 este importanta, astfel incat pentru acelasi graf putem avea mai multe StrAdi. Ordinea poate influenta algoritmul de prelucrare.
Programul C :
#include <ctype.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <graphics.h>
#include <math.h>
#define NrMax 5
#define R 150
#define raza 25
typedef int TipCheie; /*primele litere ale alfabetului*/
struct adi
typedef struct adi Tadi;
typedef Tadi *PointAdi;
PointAdi StrAdi[NrMax],z,v,r;
char n1,n2;
int x,y,i,n,a;
void initgraf(void)
}
int index(char c)
/*index*/
void deseneaza_graf(void)
;
int i,j,x0,y0,xi,yi,xj,yj;
initgraf();
x0=getmaxx()/2+80;
y0=getmaxy()/2;
for(i=0;i<n;i++) /* scriem nodurile*/
setcolor(WHITE);
/*trasam arcele */
for(i=0;i<n;i++)
}
getch();
closegraph();
}/* deseneaza_graf*/]
void main (void)
/*for*/
printf('Introduceti nodul: ');fflush(stdin);
scanf('%c',&n1);n1=toupper(n1);
printf('Lista nodurilor adiacente nodului %c sunt: ',n1);
v=(PointAdi)malloc(sizeof(Tadi));
v=StrAdi[index(n1)];
while(v!=z)
printf('n');
getch();
deseneaza_graf();
getch();
printf('Tsteaza Enter!');
}/*main*/
Laborator 12
Tema 1
Scrieti programul C care va permite efectuarea tuturor operatiilor,crearea,vizualizarea,inserarea unui nod,inserarea unui arc si suprimarea unui arc pentru un graf neorientat implementat prin varianta multilista.
Descriere algoritm.
Presupunem asocierea fiecarui nod al grafului a listei de adiacenta formata din nodurile adiacente lui. Cu alte cuvinte fiecarui nod al grafului i se asociaza o lista liniara simplu inlantuita formata din nodurile adiacente lui.
Fig. 1
 |
Listele de adiacenta sunt construite dupa ideea construirii listelor liniare cu un nod fictiv (fanion), inceputurile listei de adiacenta fiind memorate intr-un tablou StrAdi, iar crearea listei liniare simplu inlantuite se va face dupa tehnica de creare cu inserare in fata listei.
Tabloul StrAdi va fi indexat dupa multimea nodurilor grafului. Presupunem ca fiecare nod al grafului este desemnat print-o litera din alfabetul latin (primele n litere).
Pentru a realiza corespondenta intre numele nodului si indexul nodului respectiv in tabloul structurii de adiacenta, vom defini o functie Index. Deci, multimea nodurilor grafului nu este reprezentata explicit in memoria calculatorului, ci doar prin pozitiile lor in cadrul structurilor de adiacenta.
In implementarea grafurilor cu ajutorul structurilor de adiacenta metoda I, fiecare arc al grafului (x,y), daca graful este neorientat va fi evidentiat atat in lista de adiacenta a lui x cat si in lista de adiacenta a lui y.
Structurile de date prin care vom realiza o astfel de implementare sunt: tabloul: structura de adiacenta e un tablou de pointeri catre inceputurile listei liniare simplu inlantuite ale nodurilor adiacente corespunzatoare nodului respectiv.
Un alt tip de date este structura de date de tip lista liniara simplu inlantuita cu nod fictiv pe post de fanion creata dupa tehnica de creare cu inserare in fata listei.
Structurile de date si variabilele care implementeaza graful in aceasta varianta sunt:
#define MaxN 10;
typedef int TipCheie;
struct adi
;
typedef struct adi Tadi;
typedef Tadi * PointAdi;
PointAdi StrAdi[MaxN];
PointAdi v,z;//v-pointer auxiliar
char n1,n2,c;
int x,y,i,n;
Functia care realizeaza corespondenta intre indice si numele nodului este:
int Index(char c)
/*Index*/
Observatii:
Suprimarea unui nod dintr-o structura de graf,astfel implementat,presupune nu numai suprimarea propriu-zisa a nodului respectiv ci si suprimarea tuturor arcelor incidente acestui nod.De aceea mai intai suprimam nodul din listele de adiacente ale nodurilor cuprinse in lista lui de adiacente,eliberarea spatiului ocupat de nodurile din lista lui de adiacente si apoi suprimarea nodului din lista liniara a nodurilor grafului,inlantuita dupa campul urmNod.
Programul C:
#include<stdio.h>
#include<graphics.h>
#include<alloc.h>
#include<conio.h>
#include<ctype.h>
#include<stdlib.h>
#include<math.h>
#define R 200
#define r 15
#define maxN 20
#define PI M_PI
typedef char TipCheie;
typedef char TipInfo;
typedef struct elem
TipEl;
struct adi
;
typedef struct adi Tadi;
typedef Tadi *PointAdi;
typedef struct nod
Tnod;
typedef Tnod* PointNod;
typedef struct arc
TipArc;
typedef PointNod graf;
graf g;
TipArc IndiceArc;
PointNod IndiceNod;
TipEl e;
char c1,c2,c;
int x,y,n;
double alfa,alfa1,alfa2,x1,x2,x3,y1,y2,y3,x0,y0,xi,yi,xj,yj;
char sir[2]=;
void init_mod_grafic(void)
}/*init mod_grafic*/
void DesenareNoduri(int n)
setcolor(WHITE);
}/*DesenareNoduri*/
void TraseazaArc(int i, int j)
int index(TipCheie x)
if(b==0) return -1;
else return i;
}
void TravAdi(PointNod p, int i)
}/*TravAdi*/
int NrNoduri(graf g)
return i;
}
void DesenareGraf(void)
setcolor(WHITE);
}/*DesenareGraf*/
void InserNodG(graf *g)
else printf('nod eronat!n');
}/*InserNod*/
void InserNodA(TipCheie x, PointAdi *Ly)
/*InserNodA*/
void InserArc(TipArc IndiceArc)
/*InserArc*/
void SuprimaNodAdi(PointAdi Ax,pointAdi *Ly)
else
else
void SuprimaArc(TipArc IndiceArc)
}/*SuprimaArc*/
void creare(void)
n=NrNoduri(g);
DesenareNoduri(n);
printf('Introduci arc?(D/N) ');
fflush(stdin); scanf('%c',&c); c=toupper(c);
while(c=='D')
}
printf('Mai adaugi arc?(D/N)');
fflush(stdin); scanf('%c',&c); c=toupper(c);
}
}
void SuprimaArc(TipArc IndiceArc)
}/*SuprimaArc*/
/*(void main()
void main(void)
creare(&g);
break;
case 'V': init_mod_grafic();
deseneazaGraf();
printf('Tastati entern');
getch();
closegraph();
break;
case 'D':if(g!=NULL)
else printf('Graful este vid!n');
break;
case 'S':if(g!=NULL)
}
else printf('Graful este vid! n');
break;
case 'A':if(g!=NULL)
}
else printf('Nu ati introdus noduri! n');
break;
case 'I':printf('Introduceti cheia noului nod:');
fflush(stdin);scanf('%c',&e.cheie);
e.cheie=toupper(e.cheie);
if(('A'<=e.cheie)&&(e.cheie<='Z'))
}
else printf('Ati introdus nod eronat! n');
break;
case 'E':break;
default: printf('Ati intro. optiune gresita! n');
};/*switch*/
printf('tastati un caracter! n');getch();
}while (rasp!='E');
}/*main*/
Tema 2
Scrieti programul C care va permite efectuarea tuturor operatiilor,crearea,vizualizarea,inserarea unui nod,inserarea unui arc si suprimarea unui arc pentru un graf orientat implementat prin varianta multilista.
Programul C:
#include <graphics.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define R 200
#define r 15
#define pi M_PI
#define maxN 20
typedef char TipCheie;
typedef char TipInfo;
typedef struct elem
TipEl;
typedef struct adi
Tadi;
typedef Tadi *PointAdi;
typedef struct nod
Tnod;
typedef Tnod *PointNod;
typedef PointNod graf;
typedef struct arc
TipArc;
graf g;
TipEl e;
TipArc IndiceArc;
PointNod IndiceNod;
PointAdi StrAdi[maxN];
double x0,y0,xi,yi,xj,yj,x1,y1,x2,y2,x3,y3,alfa,alfa1,alfa2;
char c,c1, c2,s[2]=;
int i,j,x,y,n;
PointAdi v,z;
void InitModGrafic(void)
} /* InitModGrafic */
int Index(TipCheie x)
if(b==1)
return i;
else return -1;
}/* index */
PointNod CautaNod(graf g,TipCheie x)
/*CautaNod*/
PointAdi CautaAdi(int x,PointAdi Lx)
int NrNoduri(graf g)
return n;
}//NrNoduri
void DesenareNoduri(void)
setcolor(WHITE);
}/* DesenareNoduri */
void TraseazaArc(int i, int j)
/* TrasareArc */
void InserNodG(graf *g)
else printf('Nod eronat!n');
}//InserNodG
void InserNodA(TipCheie x,PointAdi *Ly)
//InserNodA
void InserArc(TipArc IndiceArc)
/* InserArc */
void InserareArc(void)
}
}/* InserArc */
void DesenareGraf(void)
q=q->UrmNod;
}
}/* DesenareGraf */
void SuprimaAdi(PointAdi Ax, PointAdi *Ly)
else
else /*nu e nici ultimul nici primul nod din lista de adiacenta*/
}/*SuprimaAdi*/
void SuprimaArc(TipArc IndiceArc)
/*SuprimaAdi*/
void Creare(void)
InitModGrafic();
n=NrNoduri(g);
DesenareNoduri();
//Introdu arce
printf('Introduci arc? (D/N) :');
fflush(stdin);scanf('%c',&c);c=toupper(c);
while (c=='D')
}
printf('Mai introduci arc? (D/N) :');
fflush(stdin);scanf('%c',&c);c=toupper(c);
}//while
}/* Creare */
void main(void)
DesenareGraf();
getch();
break;
case 'I':
DesenareGraf();
InserareArc();
getch();
break;
case 'N':
InserNodG(&g);
cleardevice();
DesenareGraf();
break;
case 'S':
printf('Introduceti arcul de suprimat:n');
printf('x='); fflush(stdin); scanf('%c',&x);x=toupper(x);
printf('y='); fflush(stdin); scanf('%c',&y);y=toupper(y);
IndiceArc.v1=CautaNod(g,x);
IndiceArc.v2=CautaNod(g,y);
if(IndiceArc.v1==NULL)
printf('Primul nod nu exista');
else
if(IndiceArc.v2==NULL)
printf('Al doilea arc nu exista');
else
break;
case 'E':
break;
default :
printf('Ai tastat optiune eronata!n');
fflush(stdin);getch();
break;
}/* switch */
printf('Tastati ENTER!n');
fflush(stdin);getch();
closegraph();
}while (op!='E');
}/* main */
|
