Din fisier se citesc cuvinte (siruri de caractere, cu fscanf). Să se scrie un program care creează un arbore de căutare, care conţine în noduri cuvintele şi frecvenţa lor de apariţie. Să se afişeze apoi cuvintele în ordine lexicografică crescătoare şi frecvenţa lor de apariţie (parcurgere in inordine, S < R < D).
3.1 De la tastatură se citesc cuvinte ( şiruri de caractere ). Să se scrie un program care creează un arbore de căutare, care conţine în noduri cuvintele şi frecvenţa lor de apariţie. Să se afişeze apoi cuvintele în ordine lexicografică crescătoare şi frecvenţa lor de apariţie.#include <stdio.h> // functia de cautare pt cresterea frecventei
#include <stdlib.h>
typedef struct tip_nod
{
int f;
char s[20];
struct tip_nod *st, *dr;
} nod;
nod *rad;
void inserare_nerecursiva(char s[])
{
nod *p,*q;
int n;
n=sizeof (nod);
p=(nod*)malloc(n);
strcpy(p->s,s);
p->st=0;
p->dr=0;
if (rad==0)
{
rad=p;
return;
}
q=rad;
for ( ; ; )
{
if (strcmp(s,q->s)<0)
{
if (q->st==0)
{
q->st=p;
return;
}
else q=q->st;
}
else if (strcmp(s,q->s)>0)
{
if (q->dr==0)
{
q->dr=p;
return;
}
else q=q->dr;
}
else
{
p->f++;
free (p);
return;
}
}
}
void inordine(nod *p, int nivel)
{
int i;
if (p!=0)
{
inordine(p->st,nivel+1);
//for(i=0; i<=nivel; i++) printf(" ");
printf("%s %d\n",p->s,p->f);
inordine(p->dr,nivel+1);
}
}
int main()
{
FILE *f;
f=fopen("date.txt","r");
char s[20];
while(!feof(f))
{
fscanf(f,"%s",s);
inserare_nerecursiva(s);
}
inordine(rad,0);
printf("\nApasati o tasta pentru terminare");
getch();
return 0;
}
Functia sterge_nod
TIP_NOD *stergere_nod(TIP_NOD *rad,int key)Tema: tabele de dispersie, probl 3.1 si 3.4
{
TIP_NOD *p,*tata_p;/* p este nodul de sters, iar tata_p este tatal lui */
TIP_NOD *nod_inlocuire,*tata_nod_inlocuire;/*nodul care il va inlocui pe p si tatal sau */
int directie; /*stg=1;dr=2*/
if(rad==0) return 0; /*arborele este vid */
p=rad;
tata_p=0; /* cautare nod cu cheia key */
while((p!=0)&&(p->cheie!=key))
{
if (key<p->cheie)
{
/*cautare in stanga */
tata_p=p;
p=p->stg;
directie=1;
}
else
{
/*cautare in dreapta */
tata_p=p;
p=p->dr;
directie=2;
}
}
if(p==0)
{
printf("\n NU EXISTA NOD CU CHEIA=%d\n",key);
return rad;
} /* s-a gasit nodul p de cheie key */
if(p->stg==0)
nod_inlocuire=p->dr; /* nodul de sters p nu are fiu sting */
else if(p->dr==0) nod_inlocuire=p->stg; /*nodul de sters p nu are fiu drept*/
else
{
/* nodul de sters p are fiu stang si fiu drept */
tata_nod_inlocuire=p;
nod_inlocuire=p->dr; /* se cauta in subarborele drept*/
while(nod_inlocuire->stg!=0)
{
tata_nod_inlocuire=nod_inlocuire;
nod_inlocuire=nod_inlocuire->stg;
}
if(tata_nod_inlocuire!=p)
{
tata_nod_inlocuire->stg=nod_inlocuire->dr;
nod_inlocuire->dr=p->dr;
}
nod_inlocuire->stg=p->stg;
}
free(p);
printf("\nNodul de cheie=%d a fost sters!\n",key);
if(tata_p==0)
return nod_inlocuire; /*s-a sters chiar radacina initiala */
else
{
if (directie==1)
tata_p->stg=nod_inlocuire;
else tata_p->dr=nod_inlocuire;
return rad;
}
}
3.4 Se consideră două liste liniare simplu înlănţuite cu câmpurile de informaţie utilă conţinând numere întregi. Să se construiască o listă care conţine reuniunea celor două liste şi în care elementele sunt ordonate crescător. Se va folosi o structură intermediară de tip arbore de căutare. Elementele comune vor apare a o singură dată.
#include <stdio.h>Fisier date.txt
#include <stdlib.h>
typedef struct nodlista
{
int x;
struct nod *urm;
} nod;
typedef struct nodarbore
{
int x;
struct nod *st,*dr;
} nodarbore;
void inserare_lista(int x,nod **prim, nod **ultim)
{
nod *p;
p=(nod *)malloc(sizeof(nod));
p->x=x;
p->urm=NULL;
if (*prim)
{
(*ultim)->urm=p;
(*ultim)=p;
}
else
{
(*prim)=p;
(*ultim)=p;
}
}
void afisare(nod *prim)
{
for (prim=prim; prim!=NULL; prim=prim->urm)
printf("%d ",prim->x);
printf("\n");
}
void creare_arbore(nodarbore **rad,int x)
{
nodarbore *p,*q;
p=(nodarbore *)malloc(sizeof(nodarbore));
p->x=x;
p->st=NULL;
p->dr=NULL;
q=(*rad);
for (;;)
{
if (*rad)
{
if (x<q->x)
{
if (q->st==NULL)
{
q->st=p;
return;
}
else
q=q->st;
}
else if (x>q->x)
{
if (q->dr==NULL)
{
q->dr=p;
return;
}
else
q=q->dr;
}
else
return;
}
else
{
(*rad)=p;
return;
}
}
}
void arbore(nod *prim1,nod *prim2,nodarbore **rad)
{
nod *p;
for (p=prim1; p!=0; p=p->urm)
creare_arbore(rad,p->x);
for (p=prim2; p!=0; p=p->urm)
creare_arbore(rad,p->x);
}
nod* lista_noua(nodarbore *a,nod **prim, nod **ultim)
{
nod *p=NULL,*q;
if (a)
{
p=(nod *)malloc(sizeof(nod));
p->x=a->x;
p->urm=NULL;
q=lista_noua(a->st,prim,ultim);
inserare_lista(a->x,prim,ultim);
q=lista_noua(a->dr,prim,ultim);
}
return p;
}
void preordine(nodarbore *p, int nivel)
{
int i;
if (p!=0)
{
for(i=0; i<=nivel; i++)
printf(" ");
printf("%2d\n",p->x);
preordine(p->st,nivel+1);
preordine(p->dr,nivel+1);
}
}
int main()
{
int n,m,i,a;
nod *prim1=0,*ultim1=0,*prim2=0,*ultim2=0,*prim=0,*ultim=0;
FILE *f;
f=fopen("date.txt","r");
fscanf(f,"%d %d",&n,&m);
for (i=1; i<=n; i++)
{
fscanf(f,"%d",&a);
inserare_lista(a,&prim1,&ultim2);
}
for (i=1; i<=m; i++)
{
fscanf(f,"%d",&a);
inserare_lista(a,&prim2,&ultim2);
}
afisare(prim1);
afisare(prim2);
printf("\nNoua lista\n");
nodarbore *rad=NULL;
arbore(prim1,prim2,&rad);
//preordine(rad,0);
lista_noua(rad,&prim,&ultim);
afisare(prim);
return 0;
}
4 5
1 5 3 7
2 6 3 9 7
