Fisierul arbore.h
#define Max 20 /* lungimea maxima a unui identificator */
typedef struct pn
{
char *id; /* campul pemtru identificator */
int valoare; /* campul pentru valoare */
struct pn *stang, *drept; /* fiul stang si drept al nodului */
} nod; /* tipul unui nod din arborele binar ordonat */
/* functiile prin care tipul abstract arbore este prelucrat*/
void sterge(char*);
void listare(void);
nod *cauta(char*);
void introdu(char*, int);
Fisierul arbore.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include "arbore.h"
static nod *root = NULL; /* radacina arborelui */
/*---------------------------------------------------------*/
/* */
/* prezent verifica daca in arborele cu radacina indicata */
/* de t exista un nod avand campul id egal cu parametrul */
/* id */
/* */
/*---------------------------------------------------------*/
nod *prezent (nod *t, char *id)
{
if (t==NULL)
return NULL; /* nodul nu a fost gasit */
if (strcmp (t->id, id)<0)
/* incearca pentru subarborele drept */
return prezent(t->drept, id);
if (strcmp (t->id, id)>0)
/* incearca pentru subarborele stang */
return prezent (t->stang, id);
return t; /* nodul a fost gasit */
} /* prezent */
/*---------------------------------------------------------*/
/* */
/* adauga introduce in arborele indicat de t un nod nou */
/* avand campul id si valoarea v */
/* */
/*---------------------------------------------------------*/
nod *adauga(nod *t, char *id, int v)
{
if (t==NULL) /* nodul nu exista si este creat */
{
if ((t=(nod*)malloc(sizeof(nod)))==NULL ||
(t->id=(char*)malloc(strlen(id)+1))==NULL)
{
printf("Eroare: memorie insuficienta\n");
exit(1);
}
/* s-a putut crea nodul */
strcpy(t->id, id);
t->valoare=v;
t->stang=t->drept=NULL;
}
else
if (strcmp(t->id, id)<0)
/* inserarea e in subarborele drept */
t->drept=adauga(t->drept, id, v);
else
if (strcmp(t->id, id)>0)
/* inserarea e in subarborele stang */
t->stang=adauga(t->stang, id, v);
else
printf("Identificatorul %s apare in evidenta\n",id);
return t;
} /* adauga */
/*---------------------------------------------------------*/
/* */
/* supred rutina auxiliara pentru eliminarea nodurilor */
/* cu doi fii */
/* */
/*---------------------------------------------------------*/
nod *supred (nod *t, nod *p)
{
nod *q, *q_aux;
q=t;
if (q->drept!=NULL)
/* gaseste nodul cel mai mare din subarborele indicat de t */
q->drept=supred(q->drept, p);
else /* pentru nodul cel mai mare din subarborele indicat de t */
{
free(p->id);
/* muta campurile nodului indicat de q in nodul indicat de p */
p->id=q->id;
p->valoare=q->valoare;
q_aux=q;
q=q->stang; /* fiul stang este returnat */
free(q_aux); /* elibereaza memoria ocupata de nod */
}
return q;
} /* supred */
/*---------------------------------------------------------*/
/* */
/* elimina scoate nodul avand campul id egal cu parametrul */
/* id din arborele indicat de parametrul p */
/* */
/*---------------------------------------------------------*/
nod *elimina(nod *p, char *id)
{
nod *q, *q1;
char *s;
if (p==NULL)
{
printf("Eroare: %s nu apare in evidenta\n", id);
return NULL;
}
if (strcmp(p->id, id)<0) /* nodul e in subarborele drept */
{
p->drept=elimina(p->drept, id);
return p;
}
if (strcmp(p->id, id)>0) /* nodul e in subarborele stang */
{
p->stang=elimina(p->stang, id);
return p;
}
/* s-a gasit nodul ce trebuie sters */
if (p->stang==NULL) /* daca nu are fiu stang */
{
q=p->drept;
free(p->id);
free(p);
return q;
}
if (p->drept==NULL) /* nu are fiu drept */
{
q=p->stang;
free(p->id);
free(p);
return q;
}
/* are ambii fii */
p->stang=supred(p->stang, p);
return p;
} /* elimina */
/*---------------------------------------------------------*/
/* */
/* parcurge in inordine arborele cu radacina indicata de t */
/* si afiseaza nodurile */
/* */
/*---------------------------------------------------------*/
void tipareste (nod *t)
{
if (t!=NULL)
{
tipareste(t->stang); /* tipareste subarborele stang */
printf("%s : %d\n", t->id, t->valoare);
tipareste(t->drept); /* tipareste subarborele drept */
}
} /* tipareste */
/*---------------------------------------------------------*/
/* */
/* Operatorul de listare al tipului abstract */
/* */
/*---------------------------------------------------------*/
void listare(void)
{
tipareste(root);
} /* listare */
/*---------------------------------------------------------*/
/* */
/* Operatorul de cautare al tipului abstract */
/* */
/*---------------------------------------------------------*/
nod *cauta(char *s)
{
return prezent(root, s);
} /* cauta */
/*---------------------------------------------------------*/
/* */
/* Operatorul de stergere al tipului abstract */
/* */
/*---------------------------------------------------------*/
void sterge(char *s)
{
root=elimina(root, s);
} /* sterge */
/*---------------------------------------------------------*/
/* */
/* Operatorul de introducere al tipului abstract */
/* */
/*---------------------------------------------------------*/
void introdu(char *s, int v)
{
root=adauga(root, s, v);
} /* introdu */
Fisierul main.c
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <conio.h>
#include "arbore.h"
/*---------------------------------------------------------*/
/* */
/* Functia getlin citeste urmatoarea linie de la tastatura*/
/* si recunoaste identificatorul si valoarea asociata lui.*/
/* Identificatorul este returnat in parametrul s, iar */
/* valoarea in parametrul val */
/* */
/*---------------------------------------------------------*/
void getlin(char *s ,int *val)
{
int i=0, j;
char temp[Max];
gets(temp);/* citeste urmatoarea linie de la tastatura */
/* getlin 1 */
s[i]='\0'; *val=0; /* initializeaza valorile argumentelor */
while (temp[i]!='\0')
/* atata timp cat nu a fost atins sfarsitul sirului */
/* getlin 2 */
if(isalpha(temp[i]))/* daca incepe un identificator */
/* getlin 3 */
{
j=0;
while (isalnum(temp[i]))
s[j++]=temp[i++];
/*getlin 4*/
/* memoreaza identificatorul in s */
s[j]='\0'; /* memoreaza sfarsitul de sir */
/* getlin 5 */
}
else
if (isdigit(temp[i])) /* daca incepe un numar */
/* getlin 6 */
while (isdigit(temp[i])) /* getlin 7 */
{
*val=*val*10+temp[i]-'0'; /* calculeaza valoarea numarului */
/* getlin 8 */
i++;
}
else /* altfel se trece peste caracterul curent */
i++; /* getlin 9 */
} /* getlin */
/*---------------------------------------------------------*/
/* */
/*Functia comanda_a realizeaza functionalitatea comenzii a */
/* */
/*---------------------------------------------------------*/
void comanda_a(void)
{
int val;
char s[Max];
getlin(s, &val); /* citeste o linie de la tastatura */
if (strlen(s)!=0) /* daca linia e corecta */
introdu(s, val);
else
printf(" Eroare : linie incorecta \n");
} /* comanda_a */
/*---------------------------------------------------------*/
/* */
/*Functia comanda_t realizeaza functionalitatea comenzii t */
/* */
/*---------------------------------------------------------*/
void comanda_t(void)
{
char s[Max];
nod *p;
int val;
getlin(s, &val); /* citeste o linie de la tastatura */
if (strlen(s)!=0) /* daca linia e corecta */
{
if ((p=cauta(s))!=NULL) /* cauta nodul in lista */
printf("Identificator: %s Valoare: %d \n",
p->id, p->valoare);
else
printf("Eroare: Identificator nedefinit \n");
}
else
printf(" Eroare: linie incorecta \n");
} /* comanda_t */
/*---------------------------------------------------------*/
/* */
/*Functia comanda_s realizeaza functionalitatea comenzii s */
/* */
/*---------------------------------------------------------*/
void comanda_s(void)
{
char s[Max];
int val;
getlin(s, &val); /* citeste o linie de la tastatura */
if (strlen(s)!=0) /* daca linia citita e corecta */
sterge(s); /* sterge nodul din lista */
else
printf(" Eroare: linie incorecta \n");
} /* comanda_s */
/*---------------------------------------------------------*/
/* */
/* Functia comanda_oper executa operatiile legate de */
/* comenzile +, -, * si /. Se citesc cei doi operatori si */
/* se executa operatia dorita.Rezultatul este afisat */
/* */
/*---------------------------------------------------------*/
void comanda_oper(char c)
{
char s1[Max], s2[Max];
int val;
nod *p1, *p2;
getlin(s1, &val); /* se citeste primul operand */
getlin(s2, &val); /* se citeste al doilea operand */
if ((strlen(s1)!=0) && (strlen(s2)!=0))
if (((p1=cauta(s1))!=NULL) && ((p2=cauta(s2))!=NULL))
/* se verifica daca operanzii apar in lista */
{
switch(c) /* in functie de tipul comenzii */
{
case '+':
val=p1->valoare+p2->valoare;
break;
case '-':
val=p1->valoare-p2->valoare;
break;
case '*':
val=p1->valoare*p2->valoare;
break;
case '/':
if (p2->valoare!=0)
val=p1->valoare/p2->valoare;
else
printf("Eroare:Impartire la 0\n");
break;
}
printf(" Rezultatul operatiei e %d \n", val);
}
else
printf("Operand nedefinit \n");
else
printf(" Eroare: linie eronata \n");
} /* comanda_oper */
/*---------------------------------------------------------*/
/* */
/* Functia meniu afiseaza meniul programului, citeste */
/* comanda si apeleaza subrutina care implementeaza */
/* functionalitatea comenzii */
/* */
/*---------------------------------------------------------*/
void meniu(void)
{
char o;
while (1) /* meniu 1 */
{
clrscr();
/* se afiseaza meniul programului */
printf("a adauga in evidenta un id si val asociata\n");
printf("t tipareste valoarea asociata unui id \n");
printf("s sterge un id \n");
printf("l listeaza id-rii si valorile asociate lor\n");
printf("+ calculeaza suma pentru 2 id \n");
printf("- calculeaza diferenta pentru 2 id \n");
printf("* calculeaza produsul pentru 2 id \n");
printf("/ calculeaza impartirea pentru 2 id \n");
printf("f termina programul \n");
printf("\n Introduceti optiunea :");
o=getchar(); getchar(); /* meniu 2 */
switch (tolower(o)) /* meniu 3 */
{
case 'a':
comanda_a();
break;
case 't':
comanda_t();
break;
case 's':
comanda_s();
break;
case 'l':
listare();
break;
case '+': case '-': case '*': case '/':
comanda_oper(o);
break;
case 'f':
return;
default:
printf(" Eroare : Comanda inexistenta \n");
}
getchar();
}
}
/*---------------------------------------------------------*/
/* */
/* Functia main apeleaza functia meniu */
/* */
/*---------------------------------------------------------*/
void main(void)
{
meniu();
}