Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Одесский национальный университет им. И.И. Мечникова

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

NR 4-5

.docx

Скачиваний:

Добавлен:

07.07.2019

Размер:

95.17 Кб

Скачать

☆

Ministerul 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.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
17.08.201924.29 Кб22Native and borrowed words.docx
#
25.11.2019864.77 Кб16NAVChAL_NA_PRAKTIKA.doc
#
20.05.2015313.23 Кб35Never Let Me Go.docx
#
20.05.2015137.22 Кб21nmon_1453_716_997_21102013.doc
#
22.12.20182.29 Mб93nmp_rimske_pravo.doc
#
07.07.201995.17 Кб4NR 4-5.docx
#
22.08.2019266.75 Кб7obrazes diploma 1011 .doc
#
20.05.2015124.54 Кб44Obshaya_psikhologia.docx
#
20.05.2015255.49 Кб67Obuchen.doc
#
20.05.2015152.58 Кб14obzhd.doc
#
19.03.201614.41 Mб385Odessa-_moy_gorod_rodnoy-8_klass.pdf