NR 4-5
.docxMinisterul Educatiei al Republicii Moldova
Universitatea Tehnică a Moldovei
Catedra “Informatica Aplicată”
RAPORT
Lucrarea de laborator Nr:4-5
Structuri de date si algoritmi
A efectuat:
st. gr. C-103 Radu Nani
A verificat:
dr. conf. univ Mihail Kulev
Chisinau 2011
Lucrare de laborator Nr.4-5
Tema: Arbori binari .
Scopul lucrării: Procesarea arborilor binari ,utilizind metoda iterativa si recursiva.
Formularea problemei: Avind data structura „ruta” cu cimpurile:
-Nr
-dest
-data
-ora
-pret
De efectuat un program, care va alcatui un arbore binar si va contine cimpurile mentionate mai sus, ce le va putea procesa dupa diversi parametri.
Listingul programului:
Lab45.h:
typedef struct ruta
{
char nr[10];
char dest [20];
char data[15];
char ora[10];
float pret;
int nrn;
struct ruta*left;
struct ruta*right;
}ruta;
ruta*root=NULL;
int i=1,l=1;
//definim coada
typedef struct elq
{
ruta*adr;
struct elq*next;
}elq;
elq*first=NULL,*last=NULL;
//functii
int meniulnr1();
void Menu2();
void Menu1();
inq(ruta*c);
int outll(void);
ruta*searchll(char cautat);
ruta*delq(void);
void citirenod(ruta*m);
void outinfo(ruta*m);
int outll(void);
ruta*searchll(void);
void outRSD(ruta*m);
void outRDS(ruta*m);
void outSRD(ruta*m);
void outSDR(ruta*m);
void outDRS(ruta*m);
void outDSR(ruta*m);
ruta*createRSD(void);
int createll(void);
int height(void);
int destnod(void);
void elibmem();
LAB45sda.cpp:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include"lab45.h"
//introducerea adresei nodului din coada
inq(ruta*c)
{elq*t;
t=(elq*)malloc(sizeof(*t));
if (!t)return 0;
t->adr=c;
t->next=NULL;
if (first==NULL){first=t;last=t;return 1;}
last->next=t;
last=t;
return 1;}
//stergerea adresei nodului din coada
ruta*delq(void)
{ruta*c;
elq*t;
if(first==NULL)return NULL;t=first;
first=first->next;
c=t->adr; if(first==NULL) last=NULL;
free(t);
return c;
}
//functia citire
void citirenod(ruta*m)
{clrscr(); puts("Introduceti datele despre noduri:\n");
printf("nr:");
fflush(stdin);
gets(m->nr);
printf("Destarul de rutaurisme:");
scanf("%d",&m->dest);
printf("Data:");
fflush(stdin);
gets(m->data);
printf("Ora:");
fflush(stdin);
gets(m->ora);
printf("Pret:");
scanf("%f",&m->pret);
printf("Introduceti destarul nodului: "); scanf("%d",&m->nrn);
puts("\n");
}
//afisare informatiei
void outinfo(ruta*m)
{
printf("\t Nrn:%d",m->nrn);printf("\n");
printf(" \tNr:%s",m->nr);printf("\n");
printf(" \tDestarul de rutaurisme:%d",m->dest);printf("\n");
printf(" \tData:%s",m->data);printf("\n");
printf(" \tOra:%s",m->ora);printf("\n");
printf(" \tPret:%.2f",m->pret);printf("\n");
printf(" \tStinga:%p",m->left);printf("\n");
printf("\tDreapta:%p",m->right);printf("\n");
}
//afisarea arborelui pe niveluri
int outll(void)
{int f; ruta*p,*s;
first=last=NULL;
if(!root)
{clrscr();
puts(" Eroare \n");
puts("\n Nu ati introdus nici un arbore");
return 0;}
p=root;l=1;
f=inq(p);if(!f)return 0;
while (first){
p=delq();
if (!(l==1))
outinfo(p);l++;
s=p->left;
if(s){f=inq(s);if(!f)return 0;}
s=p->right;
if(s){f=inq(s);if(!f)return 0;}
}return 1;}
//cautare elementului/a unei tari dupa deste
ruta*searchll(void)
{ruta*p,*s;int f;char cautat[20];
first=last=NULL;
puts("Dati nra rutaurismului pe care doriti sal cautati:"); fflush(stdin); gets(cautat);
if(!root)return NULL;
p=root;
f=inq(p);if(!f)return NULL;
while(first){
p=delq();
if(strcmp(p->nr, cautat)==0){return(p); }
s=p->left;
if(s){f=inq(s);if(!f)return 0;}
s=p->right;
if(s){f=inq(s);if(!f)return 0;}
}return NULL;}
//afisarea RSD
void outRSD(ruta*m)
{ruta*s;
if(!m)puts("Arbore vid");
if (!(l==1))
outinfo(m);l++;
s=m->left; if(s)outRSD(s);
s=m->right;if(s)outRSD(s);
}
//afisarea RDS
void outRDS(ruta*m)
{ruta*s;
if(!m)puts("Arbore vid");
if (!(l==1))
outinfo(m);l++;
s=m->right;if(s)outRDS(s);
s=m->left; if(s)outRDS(s);
}
//afisarea SRD
void outSRD(ruta*m)
{ruta*s;
if(!m)puts("Arbore vid");
s=m->left;if(s)outSRD(s);
if (!(l==1))
outinfo(m);l++;
s=m->right; if(s)outSRD(s);
}
//afisarea SDR
void outSDR(ruta*m)
{ruta*s;
if(!m)puts("Arbore vid");
s=m->left;if(s)outSDR(s);
s=m->right; if(s)outSDR(s);
if (!(l==1))
outinfo(m);l++;
}
//afisarea DRS
void outDRS(ruta*m)
{ruta*s;
if(!m)puts("Arbore vid");
s=m->right;if(s)outDRS(s);
if (!(l==1))
outinfo(m);l++;
s=m->left; if(s)outDRS(s);
}
//afisarea DSR
void outDSR(ruta*m)
{ruta*s;
if(!m)puts("Arbore vid");
s=m->right;if(s)outDSR(s);
s=m->left; if(s)outDSR(s);
if (!(l==1))
outinfo(m);l++;
}
//Crearea arborelui in preordine
ruta*createRSD(void)
{ruta*c;int f;
c=(ruta*)malloc(sizeof(*c));
if(c==NULL)exit(1);
citirenod(c); c->nrn=i;i++;
printf("Creati copilul de la stinga a nodului <%s> ?(1/0): ",c->nr);
scanf("%d",&f);
if(f==1){c->left=createRSD();}
else c->left=NULL;
printf("Creati copilul de la dreapta a nodului <%s> ?(1/0): ",c->nr);
scanf("%d",&f);
if(f==1){c->right=createRSD();}
else c->right=NULL;
return c;}
//functia pentru a crea un arbore binaar cu parcurgere pe niveluri(iterativ)
int createll(void)
{ruta*p,*s,*nr;
int f=0;
first=last=NULL;
root=NULL;
printf("Tastati 1 pentru a face o radacina (1/0): "); scanf("%d",&f);
if(f==1){p=(ruta*)malloc(sizeof(*p));
if(!p)return 0;
root=p;
citirenod(p);
f=inq(p);}
else return 0;
while(first){
p=delq();
printf("Creati copilul de la stinga a nodului %d ? (1/0): ",p->nrn);
scanf("%d",&f);
if(f==1){s=(ruta*)malloc(sizeof(*s));
if(!s)return 0;
p->left=s;
citirenod(s);
f=inq(s);
if(!f)return 0;}
else p->left=NULL;
printf("Creati copilul de la dreapta a nodului %d ? (1/0): ",p->nrn);
scanf("%d",&f);
if(f==1){s=(ruta*)malloc(sizeof(*s));
if(!s)return 0;
p->right=s;
citirenod(s);
f=inq(s);
if(!f)return 0;}
else p->right=NULL;}
return 1;
}
//determinarea inaltimii arborelui
int height(void)
{ruta*p,*s;
int hl=0,hr=0,h;
p=root;
inq(p);
while(first){
p=delq();
s=p->left;
if(s){hl++;inq(s);}
s=p->right;
if(s){hr++;inq(s);}}
if(hl>hr){h=hl;}else{h=hr;}return h;
}
//Determinarea nr-ului de noduri
int destnod(void)
{ruta*p,*s;
int n=1;
p=root;inq(p);
while(first){
p=delq();
s=p->left;if(s){n++;inq(s);}
s=p->right;if(s){n++;inq(s);}}
return n;}
//Eliberarea memoriei
void elibmem()
{ruta*p,*s;
p=root;inq(p);
while(first){
p=delq();
s=p->left;if(s){inq(s);}
s=p->right;if(s){inq(s);}
free(p);}
root=NULL;}
Main.cpp:
#include"lab45sda.cpp"
void dm(float *x)
{ dm(x);}
int main() {
ruta*p; int h,n,nm,nm2;
inceput : while (1) { clrscr();
printf("\n\t\t\t Meniul:\n\n");
printf("\t\t_______________________________\n");
printf("\t\t 1.Crearea arborelui pe nivele\n");
printf("\t\t 2.Crearea arborelui cu [RSD]\n");
printf("\t\t 3.Cautarea dupa deste\n");
printf("\t\t 4.Afisarea arborelui\n");
printf("\t\t 5.Eliberarea memoriei\n");
printf("\t\t_______________________________\n");
printf("\t\t\t ESC.Iesire\n\n");
switch (getch())
{ case 49:{createll();getch();break;}
case 50:{root=createRSD();getch();break;}
case 51:{p=searchll(); if(p){outinfo(p);} else puts("Gresit, asa nod nu exista!!!");getch();break;}
case 52:{clrscr();while (1) {
printf("\n\t\t\tMeniu de afisare:\n");
printf("\t\t_______________________________\n");
printf("\t\t1. Afisarea inaltimei arborelui\n");
printf("\t\t2. Afisarea destarului de noduri\n");
printf("\t\t3. Afisarea in forma de nivel\n");
printf("\t\t4. Afisarea arborelui [RSD].\n");
printf("\t\t5. Afisarea arborelui [RDS].\n");
printf("\t\t6. Afisarea arborelui [SRD].\n");
printf("\t\t7. Afisarea arborelui [DRS].\n");
printf("\t\t8. Afisarea arborelui [SRD].\n");
printf("\t\t9. Afisarea arborelui [DSR].\n");
printf("\t\t_______________________________\n");
printf("\t\t\t BS.Revenire\n");
switch (getch())
{ case 49:{h=height();printf("Inaltimea arborelui =:%i",h); getch();break;}
case 50:{ n=destnod();printf("Acest arbore are %i noduri",n);getch();break;}
case 51:{clrscr();outll();getch();break;}
case 52:{clrscr();l=1;outRSD(root);getch();break;}
case 53:{clrscr();l=1;outRDS(root);getch();break;}
case 54:{clrscr();l=1;outSRD(root);getch();break;}
case 55:{clrscr();l=1;outDRS(root);getch();break;}
case 56:{clrscr();l=1;outSDR(root);getch();break;}
case 57:{clrscr();l=1;outDSR(root);getch();break;}
case 8:{goto inceput;}
default :;
}
clrscr();
}}
case 53:{ elibmem();clrscr();puts("Memoria a fost eliberata cu succes!!!");getch();break;}
case 27:{return 0;}
default :;
}
clrscr();
}
}
MENIUL
Crearea arborelui pe nivele:
Afisarea inaltimii arborelui:
Afisarea destarului de noduri a arborelui:
Afisarea in forma de nivel a arborelui:
Concluzia:
In final pot concluziona ca lucrul cu acest program aplicativ mi-a imbunatatit deprinderele de lucru in limbajul de programare c++. In cadrul acestei lucrari de laborator am utilizat operatiunile arborelui binar prin diverse medtode studiate in mod teoretic pe parcursul cursurilor cu tematica respectiva.
Bibliografie:
Conspectul prelegerilor dr. conf. univ M. Kulev pentru studentii anului I, grupa C-103, specialitatea Calculatoare, disciplina Programarea Calculatoarelor, semestrul I, anul de învătămînt 2010-2011, UTM, Chisinău.
Cartea: “Bazele Programarii in C”
Autor Istrati.