Laborator nr45 SDA 1 Implementarea tipului de date abstract “Arbore binar geniralizat” in limbajul C. Algoritmi iterativi si algoritmi recursivi. PDF

Preview

Summary

Ministerul Educației al Republicii MoldovaUniversitatea Tehnică a MoldoveiCatedra Informatica AplicatăRAPORTLucrarea de laborator nr&La Structuri de date si algoritmiA efectuat:st. gr. TI-15X Student NameA verificat: M. Kulevdr., conf.,Chișinău 2016Lucrarea de laborator nr&Tema: Implementare...

Description

Ministerul Educației al Republicii Moldova Universitatea Tehnică a Moldovei

Catedra Informatica Aplicată

RAPORT Lucrarea de laborator nr.4&5 La Structuri de date si algoritmi

A efectuat: st. gr. TI-15X A verificat: dr., conf.univ.,

Student Name M. Kulev

Chișinău 2016 Lucrarea de laborator nr.4&5 Tema: Implementarea tipului de date abstract “Arbore binar geniralizat” in limbajul C. Algoritmi iterativi si algoritmi recursivi.

Scopul lucrarii: Obținerea deprinderilor de implementare practice in limbajul C a tipului de date abstract (TDA) “Arbore binar geniralizat”, utilizînd algoritmi iterativi si recursivi.

Sarcina de lucru: De scris trei fișiere în limbajul C pentru implementarea (2 fisiere) si utilizarea (1 fișier – program cu funcția main) a TDA “Arbore binar geniralizat ” 1. Fișierul antet cu extensia (h) care descrie structura nodului al arborelui binar (conform variantei din lucrarea de laborator 1) și prototipurile funcțiilor care asigură operațiunile de prelucrare a arborelui binar. Pentru lucrare de laborator 4 în acest fișier trebuie de adaugat descrierea structurilor elementelor cozei și a stivei unde vor fi stocate adresele nodurilor ale arborelui binar precum și prototipurile funcțiilor de inserare și eliminare a elimentului pentru coada și stiva respectiv. 2. Fisier cu extensia (cpp sau c) care conține codurile (implementările) tuturor funcțiilor declarate în fișierul antet. 3. Fișierul utilizatorului - programul cu funcția main () pentru prelucrarea arborelui binar cu afișarea meniului de optiuni pe ecran, si anume: crearea arborelui binar geniralizat împreuna cu introducerea informației nodurilor arborelui de la tastatură în rejim interactiv, afișarea informatiei despre nodurile arborelui pe ecran și a adreselor nodului current, copilului sting și copilului drept al acestora, căutarea nodului după un cîmp informațional al nodului, determinarea numărului de noduri în arbore, determinarea înalțimei a arborelui, eliberarea memoriei dinamice alocate pentru arbore, ieșire din program. În lucrare de laborator 4 funcțiile de prelucrare ale arborelui binar trebuie impementate folosind algoritm iterativ în 2 versiuni: a) utilizînd coada - pentru parcurgerea arborelui în largime (parcurgerea arborelui pe niveluri) și b) utilizînd stiva – pentru parcurgerea arborelui în adîncime (parcurgerea inordine: rădăcină -> subarbore stîng(drept) -> subarbore drept(stîng). O excepție face funcția de eliberare a memoriei dinamice alocate pentru arbore ( trebuie folosită parcurgerea postordine: subarbore stîng(drept) -> subarbore drept(stîng) -> rădăcină). În lucrare de laborator 5 funcțiile de prelucrare ale arborelui binar, trebuie implementate folosind algoritm recursiv pentru parcurgerea arborelui în adîncime: rădăcină -> subarbore stîng(drept) -> subarbore drept(stîng). Și aici o excepție face funcția de eliberare a memoriei dinamice alocate pentru arbore (trebuie folosită parcurgerea postordine: subarbore stîng(drept) -> subarbore drept(stîng) -> rădăcină).

1

În lucrare de laborator 5 funcția de afișare a informaței despre nodurile arborelui pe ecran, precum și a adreselor nodului current, copilului sting și copilului drept al acestora trebuie impementată pentru toate parcurgerile recursive posibile ale arborelui binar. Varianta 10: Stat

Noţiuni teoretice În informatica, un arbore binar este un arbore în care fiecare nod are cel mult doi succesori (fii). De obicei, succesorii se numesc „nodul stânga” și „nodul dreapta”. Arborii binari sunt folosiți mai ales drept arbori binari de căutare sau și la structurile de date de tip heap. o fiecare nod are 0,1 sau 2 succesori; o fiecare nod are un singur predecesor, cu exceptia radacinii care nu are niciunul; o succesorii fiecarui nod sunt ordonati(fiul sting, fiul drept, daca este unul singur trebuie de mentionat care; Prin parcurgerea unui arbore se intelege examinarea in mod sistematic a nodurilor sale astfel incat fiecare nod sa fie atins o singura data.Aceasta actiune este numita si "vizitare" a varfurilor arborelui,scopul ei fiind de a stationa in fiecare varf pentru a efectua o prelucrare a informatiei asociata varfului respectiv.Arborele este o structura neliniara de organizare a datelor,iar rolul traversarii sale este tocmai conceperea unei aranjari liniare a nodurilor in vederea trecerii de la unul la altul,fructificand avantajul acestei organizari Parcurgerea arborilor Preordine Se parcurge rădăcina Se parcurge subarborele stâng Se parcurge subarborele drept

Inordine Se parcurge subarborele stâng Se parcurge rădăcina Se parcurge subarborele drept

Postordine Se parcurge subarborele stâng Se parcurge subarborele drept Se parcurge rădăcina

Implementare: typedef struct arbore{ int info; 2

struct nod *left, *right; }arbore;

Analiza datelor: Functia main a) date intermediare: optiune – variabilă simplă de tip întreg, opțiunea aleasă de utilizator; t - variabilă locala de tip pointer la nod care reprezinta adresa elementului cautat; fname - variabila de tip pointer la char,denumirea fisierului pentru introducere int inq(nod* x); Functia pentru inserarea unui element in coada. Parametri x – pointer de tip nod, adresa nodului care se introduce în coadă; date returnabile: functia returnaza 1 daca s-a alocat memorie -1 invers; Variabile locale c – pointer de tip coadă, memoria elementului adăugat; nod* delq(void); Functia pentru eliminarea unui element din coada astfel obtinindui adresa lui. Parametri nu sunt; Date returnabile x – pointer de tip nod (arbore), elementul șters; Variabile locale c – pointer de tip coadă, adresa în care se stochează elementul ce urmează să fie șters; int push(nod* x); Functia pentru inserarea unui element in stiva. Parametri x – pointer de tip nod, adresa nodului care se introduce în stiva; Date returnabile functia returnaza 1 daca s-a locat memorie -1 invers; Variabile locale c – pointer de tip stivă, memoria elementului adăugat;

nod *pop(void); Functia pentru eliminarea unui element din stiva astfel obtinindui adresa lui. Parametri nu sunt; Date returnabile x– pointer de tip nod, elementul șters; Variabile locale c – pointer de tip stivă, adresa în care se stochează elementul ce urmează să fie șters;

int show_q(void); Functia pentru afisarea liste de elemente cu ajutorul cozii in latime Parametri nu sunt; Date returnabile functia returneaza 1 daca elementele au fost gasite,0 daca lista este vida Variabile locale 3

p,c – pointer de tip nod, variabile pentru prelucrarea listei;

int show_s(void); Functia pentru afisarea liste de elemente cu ajutorul stivei in adincime Parametri nu sunt; Date returnabile functia returneaza 1 daca elementele au fost gasite,0 daca lista este vida Variabile locale p,c – pointer de tip nod, variabile pentru prelucrarea listei; int size_q(void); Functia pentru afisarea la ecran la marimii arborelui cu ajutorul cozii Parametri nu sunt; Date returnabile n – variabilă simplă de tip întreg, mărimea arborelui; Variabile locale c,p – pointeri de tip nod, variabile pentru prelucrarea listei; int show_rsd(nod *c); Functia pentru afisarea RSD Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile nu sunt Variabile locale nu sunt int show_rds(nod *c); Functia pentru afisarea RDS Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile nu sunt Variabile locale nu sunt int show_srd(nod *c); Functia pentru afisarea SRD Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile nu sunt Variabile locale nu sunt int show_drs(nod *c); Functia pentru afisarea DRS Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile nu sunt Variabile locale nu sunt int show_sdr(nod *c); Functia pentru afisarea SDR Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile nu sunt Variabile locale nu sunt int show_dsr(nod *c); Functia pentru afisarea DSR 4

Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile nu sunt Variabile locale nu sunt int size_s(void); Functia pentru afisarea la ecran la marimii arborelui cu ajutorul stivei Parametri nu sunt; Date returnabile s – variabilă simplă de tip întreg, mărimea arborelui; Variabile locale c,p – pointeri de tip nod, variabile pentru prelucrarea listei; int creat_q(void); Functia pentru crearea arborelui cu ajutorul cozii. Parametri nu sunt; Date returnabile returneaza 1 daca elementul a fost creat cu succes,0 invers; Variabile locale f – variabilă simplă de tip întreg, răspunsul utilizatorului. c,p – pointeri de tip carte(arbore), variabile pentru prelucrarea listei; int creat_s(void); Functia pentru crearea arborelui cu ajutorul stivei. Parametri nu sunt; Date returnabile returneaza 1 daca elementul a fost creat cu succes,0 invers; Variabile locale f – variabilă simplă de tip întreg, răspunsul utilizatorului. c,p – pointeri de tip carte(arbore), variabile pentru prelucrarea listei; nod* search_q(char* fname); Functia pentru cautarea unui element dupa un cimp al structurii cu ajutorul cozii. Parametri fname - variabila de tip ponter la char,denumirea elementrului pentru cautare; Date returnabile p - pointer de tip nod,adresa elementului găsit; Variabile locale p,c– pointer de tip nod, variabile pentru prelucrarea listei;

nod* search_s(char* fname); Functia pentru cautarea unui element dupa un cimp al structurii cu ajutorul stivei. Parametri fname- variabila de tip ponter la char,denumirea elementrului pentru cautare; Date returnabile p - pointer de tip nod,adresa elementului găsit; Variabile locale p,c– pointer de tip nod, variabile pentru prelucrarea listei;

int freemem_s(void); Functia pentru eliberarea memoriei Parametri nu sunt; Date returnabile returneaza 1 daca elementul a fost creat cu succes,0 invers 5

Variabile locale c,p – pointeri de tip carte(arbore), variabile pentru prelucrarea listei

int freemem_q(void); Functia pentru eliberarea memoriei Parametri nu sunt; Date returnabile returneaza 1 daca elementul a fost creat cu succes,0 invers Variabile locale c,p – pointeri de tip carte(arbore), variabile pentru prelucrarea listei;

nod* creat_rsd(nod *parent); Functia pentru crearea arborelui recursiv RSD. Parametri nu sunt; Date returnabile parent - pointer de tip nod Variabile locale f– variabilă simplă de tip întreg, răspunsul utilizatorului; c - pointer de tip nod,adresa rădăcinii; nod* search_rsd(nod *c, char *fname); Functia pentru cautarea unui elementru cu ajutorul recursiei. Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile c-pointer de tip carte, adresa elementului găsit; Variabile locale nu sunt; int size_rsd(nod *c); Functia pentru afisarea la ecran a marimii arborelui cu ajutorul recuriei. Parametri c-pointer de tip nod, adresa rădăcinii; Date returnabile: mărimea arborelui; Variabile locale n - variabila simpla de tip întreg,marimea arborelui

int height_rsd(nod *c) ; Functia pentru afisarea la ecran a inaltimii arborelui cu ajutorul recursiei. Parametri c-pointer de tip nodmadresa rădăcinii; Date returnabile r,l – variabile simple de tip întreg, înălțimea arborelui; Variabile locale l,r - variabile simple de tip întreg,

void freemem_rsd(nod *c); Functia pentru eliberarea memoriei

6

Parametri c-pointer de tip carte(arbore), adresa rădăcinii; Date returnabile nu sunt; Variabile locale nu sunt;

Codul programului in limbajul C Fișierul stat.h: #include #include #include typedef struct nod{ char nume[100]; char capitala[100]; char presedinte[100]; int populatia; int suprafata; struct nod *left,*right; }nod; nod *root=NULL; // coada typedef struct elq{ nod *adrnod; struct elq *next; }elq; elq *first=NULL; elq *last=NULL; // stiva typedef struct els{ nod *adrnod; struct els* prev; }els; els *top=NULL; int inq(nod *inf); nod* delq(); int push(nod *inf); nod* pop(); int creat_q(); int creat_s(); nod* creat_rsd(nod *parent); int show_q(); int show_s(); void show_rsd(nod *c); void show_rds(nod *c); void show_srd(nod *c); void show_drs(nod *c); void show_sdr(nod *c); void show_dsr(nod *c); nod* search_q(char *fname); nod* search_s(char *fname); nod* search_rsd(nod* c, char *fname); int size_q(); int size_s(); 7

int size_rsd(nod *c); void freemem_rsd(nod *c); int freemem_q(); int freemem_s(); int height_rsd(nod *c);

Fișierul functions.h: #include "stat.h" #include #include #include int inq(nod *x){ elq *c; c=(elq*)malloc(sizeof(elq)); if(!c) return 0; if(!first){ first = c; } else { last->next=c; } last=c; c->next=NULL; c->adrnod=x; return 1; } nod* delq(){ elq *c=first; nod *x; if(c == last){ first=last=NULL; } else { first=c->next; } x=c->adrnod; free(c); return x; } int push(nod *x){ els *c; c=(els*)malloc(sizeof(els)); if(!c) return 0; c->prev=top; c->adrnod=x; top=c; return 1; } nod* pop(){ els *c=top; nod *x; top=c->prev; 8

x=c->adrnod; free(c); return x; } int creat_q(){ int f; nod *c,*p; first=last=NULL; printf(" Doriti sa creati radacina arborelui (1/0)?: "); scanf("%d",&f); if(f){ c=(nod*)malloc(sizeof(nod)); if(!c) return -1; printf(" Introduceti datele radacinei:\n"); printf(" Nume: "); scanf("%s",&c->nume); printf(" Capitala: "); scanf("%s",&c->capitala); printf(" Presedinte: "); scanf("%s",&c->presedinte); printf(" Populatia: "); scanf("%d",&c->populatia); printf(" Suprafata: "); scanf("%d",&c->suprafata); if(!inq(c)) return -2; root = c; }else { root = NULL; } while(first){ p = delq(); printf(" Doriti sa creati copilul sting al nodului %s (1/0)?: ",p->nume); scanf("%d",&f); if(f){ c=(nod*)malloc(sizeof(nod)); if(!c) return -3; printf(" Introduceti datele copilului sting\n"); printf(" Nume: "); scanf("%s",&c->nume); printf(" Capitala: "); scanf("%s",&c->capitala); printf(" Presedinte: "); scanf("%s",&c->presedinte); printf(" Populatia: "); scanf("%d",&c->populatia); printf(" Suprafata: "); scanf("%d",&c->suprafata); p->left=c; if(!inq(c)) return -2; } else { p->left=NULL; 9

} printf(" Doriti sa creati copilul drept al nodului %s (1/0)?: ",p->nume); scanf("%d",&f); if(f){ c=(nod*)malloc(sizeof(nod)); if(!c) return -3; printf(" Introduceti datele copilului drept\n"); printf(" Nume: "); scanf("%s",&c->nume); printf(" Capitala: "); scanf("%s",&c->capitala); printf(" Presedinte: "); scanf("%s",&c->presedinte); printf(" Populatia: "); scanf("%d",&c->populatia); printf(" Suprafata: "); scanf("%d",&c->suprafata); p->right = c; if(!inq(c)) return -2; } else { p->right = NULL; } } return 1; } int show_q(){ nod *p,*c; first=last=NULL; if(!root) return 0; p=root; if(!inq(p)) return -2; printf(" Lista nodurilor\n\n"); while(first){ p=delq(); printf(" ---Nodul %s---\n",p->nume); printf(" Nume: %s\n",p->nume); printf(" Capitala: %s\n",p->capitala); printf(" Presedinte: %s\n",p->presedinte); printf(" Populatia: %d\n",p->populatia); printf(" Suprafata: %d\n\n",p->suprafata); c=p->left; if(c){ if(!inq(c)) return -2; } c=p->right; if(c){ if(!inq(c)) return -2; } } return 1; } 10

nod* search_q(char *fname){ nod *p,*c; first=last=NULL; if(!root) return NULL; p=root; if(!inq(p)) return NULL; while(first){ p=delq(); if(!strcmp(p->nume,fname)) return p; c=p->left; if(c){ if(!inq(c)) return NULL; } c=p->right; if(c){ if(!inq(c)) return NULL; } } return NULL; } int size_q(){ int s=0; nod *p,*c; first=last=NULL; if(!root) return 0; p=root; if(!inq(p)) return -2; while(first){ p=delq(); s++; c=p->left; if(c){ if(!inq(c)) return -2; } c=p->right; if(c){ if(!inq(c)) return -2; } } return s; } int freemem_q(){ nod *p,*c; first=last=NULL; if(!root) return 0; p=root; if(!inq(p)) return -2; while(first){ p=delq(); 11

c=p->left; if(c){ if(!inq(c)) return -2; } c=p->right; if(c){ if(!inq(c)) return -2; } free(p); } return 1; } int height_q(nod *c){ int l=0,r=0; if(!c) return -1; l=1+height_q(c->left); r=1+height_q(c->right); if(l>r) return l; else return r; } int creat_s(){ nod *p, *c; int f; root=NULL; top=NULL; printf(" Doriti sa creati radacina arborelui (1/0)? : "); fflush(stdin); scanf("%d",&f); if(f){ c=(nod*)malloc(sizeof(nod)); if(!c) return -1; printf(" Introduceti datele \n"); printf(" Nume: "); scanf("%s",&c->nume); printf(" Capitala: "); scanf("%s",&c->capitala); printf(" Presedinte: "); scanf("%s",&c->presedinte); printf(" Populatia: "); scanf("%d",&c->populatia); printf(" Suprafata: "); scanf("%d",&c->suprafata); if(!push(c)) return -5; root=c; while(top){ p=pop(); printf(" Doriti sa creati copilul drept al nodului %s (1/0)?: ",p->nume); fflush(stdin); scanf("%d",&f); if(f){ c=(nod*)malloc(sizeof(nod)); 12

if(!c) return -3; printf(" Introduceti datele\n"); printf(" Nume: "); scanf("%s",&c->nume); printf(" Capitala: "); scanf("%s",&c->capitala); printf(" Presedinte: "); scanf("%s",&c->presedinte); printf(" Populatia: "); scanf("%d",&c->populatia); printf(" Suprafata: "); scanf("%d",&c->suprafata); p->right = c; if(!push(c)) return -5; } else { p->right = NULL; } printf(" Doriti sa creati copilul sting al nodului %s (1/0)?: ",p->nume); fflush(stdin); scanf("%d",&f); if(f){ c=(nod*)malloc(sizeof(nod)); if(!c) return -3; printf(" Introduceti datele\n"); printf(" Nume: "); scanf("%s",&c->nume); printf(" Capitala: "); scanf("%s",&c->capitala); printf(" Presedinte: "); scanf("%s",&c->presedinte); printf(" Populatia: "); scanf("%d",&c->populatia); printf(" Suprafata: "); scanf("%d",&c->suprafata); p->left=c; if(!push(c)) return -5; } else { p->left=NULL; } } } return 1; } int show_s(){ nod *p,*c; top=NULL; if(!root) return 0; p=root; if(!push(p)) return -5; printf("Lista nodurilor\n\n"); while(top){ 13

p=pop(); printf(" ---Nodul %s---\n",p->nume); printf(" Nume: %s\n",p->nume); printf(" Capitala: %s\n",p->capitala); printf(" Presedinte: %s\n",p->presedinte); printf(" Populatia: %d\n",p->populatia); printf(" Suprafata: %d\n\n",p->suprafata); c=p->right; if(c!=NULL){ if(!push(c)) return -5; } c=p->left; if(c!=NULL){ if(!push(c)) return -5; } } printf("\n"); return 1; } int size_s(){ nod *p,*c; int s=0; top=NULL; if(!root) return 0; p=root; if(!push(p)) return -5; while(top){ p=pop(); s++; c=p->right; if(c!=NULL){ if(!push(c)) return -5; } c=p->left; if(c!=NULL){ if(!push(c)) return -5; } } return s; } nod* search_s(char *fname){ nod *p,*c; top=NULL; if(!root) return NULL; p=root; if(!push(p)) return NULL; while(top){ p=pop(); if(!strcmp(fname,p->nume)) return p; c=p->right; if(c!=NULL){ 14

if(!push(c)) return NULL; } c=p->left; if(c!=NULL){ if(!push(c)) return NULL; } } return NULL; } int freemem_s(){ nod *p,*c; top=NULL; if(!root) return 0; p=root; if(!push(p)) return -5; while(top){ p=pop(); c=p->right; if(c!=NULL){ if(!push(c)) return -5; } c=p->left; if(c!=NULL){ if(!push(c)) return -5; } free(p); } return 1; } int height_s(nod *c){ int l=0,r=0; if(!c) return -1; l=1+height_s(c->left); r=1+height_s(c->right); if(l>r) return l; else return r; } nod* creat_rsd(nod* parent){ nod *c; int f; c=(nod*)malloc( sizeof(*c) ); if(!c) return NULL; printf(" Introduceti datele\n"); printf(" Nume: "); fflush(stdin); scanf("%s",&c->nume); printf(" Capitala: "); scanf("%s",&c->capitala); 15

printf(" Presedinte: "); scanf("%s",&c->presedinte); printf(" Populatia: "); scanf("%d",&c->populatia); printf(" Suprafata: "); scanf("%d",&c->suprafata); printf(" Doriti sa creati copilul sting al nodului %s (1/0)?: ",c->nume); fflush(stdin); scanf("%d",&f); if(f){ c->left=creat_rsd2(c); } else { c->left=NULL; } printf(" Doriti sa creati copilul drept al nodului %s (1/0)?: ",c->nume); fflush(stdin); scanf("%d",&f); if(f){ c->right=creat_rsd(c); } else { c->right=NULL; } return c; } void show_rsd(nod *c){ if(!c){ return; } printf(" ---Nodul %s---\n",c->nume); printf(" Nume: %s\n",c->nume); printf(" Capitala: %s\n",c->capitala); printf(" Presedinte: %s\n",c->presedinte); printf(" Populatia: %d\n",c->populatia); printf(" Suprafata: %d\n\n",c->suprafata); show_rsd(c->left); show_rsd(c->right); } void show_rds(nod *c){ if(!c){ return; } printf(" ---Nodul %s---\n",c->nume); printf(" Nume: %s\n",c->nume); printf(" Capitala: %s\n",c->capitala); printf(" Presedinte: %s\n",c->presedinte); printf(" Populatia: %d\n",c->populatia); printf(" Suprafata: %d\n\n",c->suprafata); show_rds(c->right); show_rds(c->left); } void show...