Ministerul Educaiei al Republicii Moldova

Universitatea Tehnic a Moldovei

Faculatea Calulatore, Informatic i Microelectronic

Tema: ALGORITMUL DE CUTARE N ADNCIME

I ALGORITMUL DE CUTARE N LRGIME A efectuat:

A verificat: Lisnic Inga

Chiinu 2015LUCRAREA DE LABORATOR Nr. 2

1. SCOPUL LUCRRII:

Studierea algoritmilor de cutare n graf i a diferitor forme de pstrare i prelucrare a datelor.

Elaborarea procedurii de cutare n adncime.

2. NOTE DE CURS

Structuri de date: listeFiecare tip de list definete o mulime de iruri finite de elemente de tipul declarat. Numrul de elemente care se numete lungimea listei poate varia pentru diferite liste de acelai tip. Lista care nu conine nici un element se va numi vid. Pentru list sunt definite noiunile nceputul, sfritul listei i respectiv primul i ultimul element, de asemenea elementul curent ca i predecesorul i succesorul elementului curent. Element curent se numete acel unic element care este accesibil la momentul dat.

Structuri de date : fire de ateptareFirele de ateptare (FA, rnd, coad, ir de ateptare) se vor folosi pentru a realiza algoritmul de prelucrare a elementelor listei n conformitate cu care elementele vor fi eliminate din list n ordinea n care au fost incluse n ea (primul sosit - primul servit).

Operaiile de baz cu firele de ateptare:

Formarea unui FA vid;

Verificare dac FA nu este vid;

Alegerea primului element cu eliminarea lui din FA;

Introducerea unei valori noi n calitate de ultim element al FA.

Structuri de date - arboriSe va defini o mulime de structuri fiecare din care va consta dintr-un obiect de baz numit vrf sau rdcina arborelui dat i o list de elemente din mulimea definit, care (elementele) se vor numi subarbori ai arborelui dat. Arborele pentru care lista subarborilor este vid se va numi arbore trivial, iar rdcina lui - frunz.

Rdcina arborelui se va numi tatl vrfurilor care servesc drept rdcini pentru subarbori; aceste vrfuri se vor mai numi copiii rdcinii arborelui: rdcina primului subarbore se va numi fiul cel mai mare, iar rdcina fiecrui subarbore urmtor n list se va numi frate.

Operaiile de baz pentru arbori vor fi:

Formarea unui arbore trivial;

Alegerea sau nlocuirea rdcinii arborelui;

Alegerea sau nlocuirea listei rdcinilor subarborilor;

Operaiile de baz care sunt valabile pentru liste.

Cutare n adncime

La cutarea n adncime (parcurgerea unui graf n sens direct, n preordine) vrfurile grafului vor fi vizitate n conformitate cu urmtoarea procedur recursiv: mai nti va fi vizitat rdcina arborelui q, apoi, dac rdcina arborelui nu este frunz - pentru fiecare fiu p al rdcinii q ne vom adresa recursiv procedurii de parcurgere n adncime pentru a vizita vrfurile tuturor subarborilor cu rdcina p ordonate ca fii ai lui q.

3. SARCINA DE BAZ

1. Elaborai procedura cutrii n adncime ntr-un graf arbitrar;

2. Elaborai un program cu urmtoarele posibiliti:

introducerea grafului n calculator,

parcurgerea grafului n adncime,

vizualizarea rezultatelor la display i imprimant.

LUCRAREA DE LABORATOR Nr. 3

TEMA: ALGORITMUL DE CUTARE N LRGIME

1. SCOPUL LUCRRII:

Studierea algoritmului de cutare n lrgime;

Elaborarea programului de cutare n lrgime.

2. NOTE DE CURS

Algoritmul de cutare n lrgime

Parcurgerea grafului n lrgime, ca i parcurgerea n adncime, va garanta vizitarea fiecrui vrf al grafului exact o singur dat, ns principiul va fi altul. Dup vizitarea vrfului iniial, de la care va ncepe cutarea n lrgime, vor fi vizitate toate vrfurile adiacente cu vrful dat, apoi toate vrfurile adiacente cu aceste ultime vrfuri .a.m.d. pn vor fi vizitate toate vrfurile grafului. Evident, este necesar ca graful s fie conex. Aceast modalitate de parcurgere a grafului (n lrgime sau postordine), care mai este adesea numit parcurgere n ordine orizontal, realizeaz parcurgerea vrfurilor de la stnga la dreapta, nivel dup nivel.

Vom nota c procedura parcurgerii grafului n lrgime permite s realizm arborele de cutare i n acelai timp s construim acest arbore. Cu alte cuvinte, se va rezolva problema determinrii unei rezolvri sub forma vectorului (a1, a2,...) de lungime necunoscut, dac este cunoscut c exist o rezolvare finit a problemei.

Algoritmul pentru cazul general este analogic cu cel pentru un graf n form de arbore cu o mic modificare care const n aceea c fiecare vrf vizitat va fi marcat pentru a exclude ciclarea algoritmului.

3. SARCINA DE BAZ

1. Elaborai procedura care va realiza algoritmul de parcurgere a grafului n lrgime;

2. Folosind procedurile din lucrrile precedente, elaborai programul care va permite:

introducerea grafului n calculator;

parcurgerea grafului n lrgime;

extragerea datelor la display i printer.

Listingul programului:#include

#include

#include

struct lista

{

int inf;

lista *next;

} *ls;

typedef struct list

{

int info;

struct list *next;

} *stack;

stack push(stack s,int info);

stack pop(stack s, int *pinfo);

void pop_end(stack &s, int *pinfo);

int este(int v, int n, int t[]);

int getst(stack s);

lista *inss(lista *cap, int k);

void afisl(lista *cap);

int mdfcontine(lista *cap,int n,int t[]);

void InitDrum();

void InitTL();

void IntrTL();

void AfisTL();

void P_Adincime();

void P_Latime();

void AfisDrum();

int menu();

int tab[25],n,i,j=0;

struct lista *tl[25];

stack s=NULL,s2=NULL;

void main(void)

{

for (;;)

switch(menu())

{

case 1 : clrscr();InitTL();IntrTL();break;

case 2 : clrscr();AfisTL();getch();break;

case 3 : clrscr();InitDrum();s=NULL;j=0;

P_Latime();AfisDrum();getch();break;

case 4 : clrscr();InitDrum();s=NULL;j=0;

P_Adincime();AfisDrum();getch();break;

case 5 : ;

case 27 : exit(1) ;break;

}

}

lista *inss(lista *cap, int k)

{

//Insereaza la sfirsitul listei

lista *t=(lista *)malloc(sizeof(lista)),*temp;

t->inf=k;t->next=NULL;

if (!cap) return t;

temp=cap;

while (temp->next) temp=temp->next;

temp->next=t;

return cap;

}

void afisl(lista *cap)

//afiseaza lista

{

if (cap) {printf("%5d",cap->inf);afisl(cap->next);} else return;

}

stack push(stack s,int info)

{

//Pune virful in topul stivei

stack t;

t=(stack)malloc(sizeof(list));

t->info=info;

t->next=s;

return t;

}

stack pop(stack s, int *pinfo)

{

//Extrage virful din topul stivei

stack t;

if (!s) return NULL;

else

{

*pinfo=s->info;t=s->next;

free(s); return(t);

}

}

int este(int v, int n, int t[])

{

//Verific daca virful se afla in tabloul ce contine drumul

int val=0,i;

for (i=0;iinfo);

}

int mdfcontine(lista *cap,int n,int t[])

{

while (cap)

if (este(cap->inf,n,t)) cap=cap->next;

else return(cap->inf);

return (-1);

}

void InitDrum()

{

int i;

for (i=0;inext;}

}

else

{

stack temp=s;

s=s2;s2=temp;

}

}

}

void pop_end(stack &s, int *pinfo)

{

if (!s) return ;

if (s->next) pop_end(s->next,pinfo);

else {*pinfo=s->info;s=NULL;} }