Program - algoritm de explorare in largime
functie, declarare matrice, citire arce, construire matrice, apelare functie de exploorare in largime
void largime(int a[][100],int n,int s)
{
int viz[n],coada[n],i,k=0,j,ct;
coada[0]=s;
for (i=1;i<=n;i++)
viz[i]=0;
viz[k]=1;
k++;
while (k<n)
{
ct=0;
for (i=ct;i<k;i++)
{
for (j=1;j<=n;j++)
if (a[coada[i]][j] && viz[j]==0)
{
viz[j]=1;
coada[k]=j;
k++;
}
ct++;
}
}
for (i=0;i<n;i++)
printf("%d ",coada[i]);
printf("\n");
}
Conspect ALGORITMI PENTRU PRELUCRAREA GRAFURILOR
si primul algoritm (Algoritmul lui Dijkstra)
void dijkstra (int n,int a[][100])Main
{
int tata[n],cost[n][n],dist[n],s[n],i,j,pas,k,q,minim;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i==j)
cost[i][j]=0;
else
if (a[i][j])
cost[i][j]=a[i][j];
else
cost[i][j]=100000;
for (i=1;i<=n;i++)
{
s[i]=0;
dist[i]=cost[1][i];
if (dist[i]<100000)
tata[i]=1;
else
tata[i]=0;
}
s[1]=1;
tata[1]=0;
for (i=1;i<n;i++)
{
minim=100000;
for (q=1;q<=n;q++)
if (dist[q]<minim && dist[q])
{
minim=dist[q];
k=q;
}
if (k==100000)
return;
s[k]=1;
for (j=1;j<=n;j++)
if (s[j]==0 && dist[k]+cost[k][j]<dist[j])
{
dist[j]=dist[k]+cost[k][j];
tata[j]=k;
}
}
for (i=2;i<=n;i++)
printf("%d - %d\n",dist[i],tata[i]);
}
int main()
{
int a[100][100],n,m,i,x,y,c,j;
FILE *f;
f=fopen("in.txt","r");
fscanf(f,"%d %d\n",&n,&m);
for (i=0;i<m;i++)
{
fscanf(f,"%d %d %d\n",&x,&y,&c);
a[x][y]=c;
}
largime(a,n,1);
dijkstra(n,a);
return 0;
}
Lab 8 - prob. 3.2
Să se implementeze algoritmii prezentaţi aferenţi unei tabele de dispersie. Înregistrarea va conţine datele aferente unui student. Cheia va fi numele şi prenumele studentului. Scrieţi în plusfaţă de cele prezentate o funcţie de ştergere a unei înregistrări de cheie dată.
// nu chiar toti studentii sunt gasiti
#include <stdio.h>Pro's
#include <stdlib.h>
#include<string.h>
#define M 27
typedef struct Nod{
char nume[50];
char facult[50];
int an;
struct nod *st,*dr;
} nod;
int ff(char cuv[])
{
return cuv[0]-'A';
}
// antete functii tabela
void adaug(nod *ht[],char nume[],char facult[],int an);
void afis(nod *ht[]);
nod* caut(nod *ht[],char nume[]);
void stergere(nod *ht[],char nume[]);
// antete functii arbore
nod* adaug_arbore(nod *r, char nume[],char facult[],int an);
void afisIN(nod *r);
nod* caut_arbore(nod *r,char nume[]);
nod* stergere_arbore(nod *r,char nume[]); // functia lunga din laborator
// functii tabela
void adaug(nod *ht[],char nume[], char facult[],int an)
{
int i=ff(nume);
ht[i]=adaug_arbore(ht[i],nume,facult,an);
}
void afis(nod *ht[])
{
int i=0;
for(i=0; i<M; i++)
{
nod *rad=ht[i];
afisIN(rad);
}
}
//functii arbore
nod* caut_arbore(nod *r,char nume[])
{
nod *p=NULL;
if(r!=0)
{
if(strcmp(nume,r->nume)==0)
p=r;
else if(strcmp(nume,r->nume)<0)
p=caut_arbore(r->st,nume);
else caut_arbore(r->dr,nume);
}
return p;
}
nod* adaug_arbore(nod *p, char nume[50],char facult[50],int an)
{
if(p==NULL)
{
p=(nod *)malloc(sizeof(nod));
p->st=p->dr=NULL;
strcpy(p->nume,nume);
strcpy(p->facult,facult);
p->an=an;
}
else if(strcmp(p->nume,nume)>0)
p->st=adaug_arbore(p->st,nume,facult,an);
else if(strcmp(p->nume,nume)<0)
p->dr=adaug_arbore(p->dr,nume,facult,an);
else if(strcmp(p->nume,nume)==0)
return p;
}
void afisIN(nod *r)
{
if(r)
{
afisIN(r->st);
printf("%s %s %d \n",r->nume,r->facult,r->an);
afisIN(r->dr);
}
}
int main()
{
FILE *f;
nod *rad=0;
nod* ht[M];
int i=0,an;
char nume[50],facult[50];
for(i=0; i<M; i++)
ht[i]=0;
f=fopen("date.txt","r");
if(f==NULL)
{
printf("error");
return -1;
}
while(!feof(f))
{
fscanf(f,"%s %s %d",nume,facult,&an);
rad=adaug_arbore(rad,nume,facult,an);
//adaug(ht[ff(nume)],nume,facult,an);
}
afisIN(rad);
//printf("\n\n");
//afis(ht[i]);
char nume_cautare[40];
printf("\nCautare student (nume): ");
scanf("%s",nume_cautare);
nod *p=caut_arbore(rad,nume_cautare);
if(p!=NULL)
{
printf("%s %s %d\n",p->nume,p->facult,p->an);
}
else printf("Nu exista studentul cu numele introdus\n\n");
printf("Apasati o tasta pentru terminare");
getch();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
typedef struct nodtype
{
char nume[20];
struct nod *dr,*st;
}nod;
void inserare(char nume[20],nod **rad)
{
nod *p,*q;
p=(nod *)malloc(sizeof(nod));
p->st=NULL;
p->dr=NULL;
strcpy(p->nume,nume);
q=*rad;
if (*rad)
{
for (;;)
{
if (strcmp(nume,q->nume)<0)
{
if (q->st==0)
{
q->st=p;
return;
}
else
q=q->st;
}
else
if (strcmp(nume,q->nume)>0)
{
if (q->dr==0)
{
q->dr=p;
return;
}
else
q=q->dr;
}
else
{
return;
}
}
}
else
(*rad)=p;
}
void afisare(nod *rad)
{
if (rad)
{
afisare(rad->st);
printf("%s\n",rad->nume);
afisare(rad->dr);
}
}
nod *cautare(nod *rad,char nume[])
{
nod *p=NULL;
if (rad)
{
if (!strcmp(rad->nume,nume))
p=rad;
else
if (strcmp(rad->nume,nume)<0)
p=cautare(rad->st,nume);
else
p=cautare(rad->dr,nume);
}
return p;
}
void stergere(nod **rad,char nume[20])
{
nod *p,*q,*tp,*tq;
int directie=0;
p=(*rad);
tp=0;
while (p && strcmp(p->nume,nume))
if (strcmp(p->nume,nume)>0)
{
tp=p;
p=p->st;
directie=1;
}
else
if (strcmp(p->nume,nume)<0)
{
tp=p;
p=p->dr;
directie=2;
}
if (p==0)
return 0;
if (p->st==0)
q=p->dr;
else
{
if (p->dr==0)
{
q=p->st;
}
else
{
tq=p;
q=p->dr;
while (q)
{
tq=q;
q=q->st;
}
q->st=p->st;
if (tq!=p)
{
tq->st=q->dr;
q->dr=p->dr;
}
}
}
if (p==(*rad))
(*rad)=q;
free(p);
if (tp)
{
if (directie==1)
tp->st=q;
else
tp->dr=q;
}
}
int dispersie(char nume[20])
{
return (nume[0]-'A');
}
int main()
{
FILE *f;
int n,k,i;
char nume[20];
f=fopen("in.txt","r");
fscanf(f,"%d\n",&n);
nod *ht[27];
for (i=0;i<27;i++)
ht[i]=NULL;
for (i=0;i<n;i++)
{
fgets(nume,20,f);
strcpy(nume+strlen(nume)-2,nume+strlen(nume));
k=dispersie(nume);
inserare(nume,&ht[k]);
}
for (i=0;i<27;i++)
{
afisare(ht[i]);
}
/*char caut[20];
scanf("%s",caut);
nod *p;
p=cautare(ht[caut[0]-'A'],caut);
printf("%s\n",p->nume);
*/
char sterg[20];
scanf("%s",sterg);
stergere(&ht[sterg[0]-'A'],sterg);
afisare(ht[sterg[0]-'A']);
return 0;
}
