mdlab3
DESCRIPTION
Matematica discreta lab3TRANSCRIPT
Universitatea Tehnic a Moldovei
Universitatea Tehnic a Moldovei
Catedra Automatica si Tehnologii InformationaleRAPORT
lucrarea de laborator 3La Matematica DiscretaTEMA: ALGORITMUL DE CUTARE N ADNCIME A elaborat: st.gr.TI-143 Fiodor Alexandru
A verificat: Ceban CheorgheChiinu 2015SCOPUL LUCRRII:
Studierea algoritmilor de cutare n graf i a diferitor forme de pstrare i prelucrare a datelor. Elaborarea procedurii de cutare n adncime .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 imprimant1. Folosind procedurile din lucrrile precedente, elaborai programul care va permite:
introducerea grafului n calculator;
parcurgerea grafului n adincime;
extragerea datelor la display i printer.
CONSIDERAII TEORETICE: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: stiveStiva se utilizeaz pentru a realiza algoritmul de prelucrare a elementelor dup principiul "ultimul sosit - primul prelucrat" (LIFO).
Operaiile de baz cu stivele sunt urmtoarele:
Formarea unei stive vide;
Verificare la vid;
Alegerea elementului din topul stivei cu sau fr eliminare;
Introducerea unui element nou n topul stivei.
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.
n cazul utilizrii unei stive pentru pstrarea drumului curent pe arbore, drum care ncepe din rdcina arborelui i se termin cu vrful vizitat n momentul dat, poate fi realizat un algoritm nerecursiv de forma:
Viziteaz rdcina arborelui i introdu-o n stiva vid S;
WHILE stiva S nu este vid DO
BEGIN
fie p - vrful din topul stivei S;
IF fiii vrfului p nc nu au fost vizitai
THEN viziteaz fiul mai mare al lui p i introduce-l n SELSE BEGIN
elimin vrful p din stiva SIF p are frai THEN viziteaz pe fratele lui p i introduce-l n stiva SEND
END
Acest algoritm poate fi modificat pentru a putea fi utilizat la parcurgerea tuturor vrfurilor unui graf arbitrar. n algoritmul de mai jos se va presupune c este stabilit o relaie de ordine pe mulimea tuturor vrfurilor grafului, iar mulimea vrfurilor adiacente cu un vrf arbitrar al grafului este de asemenea ordonat:
WHILE va exista cel puin un vrf care nu a fost vizitat DO
BEGIN
fie p - primul din vrfurile nevizitate;
viziteaz vrful p i introduce-l n stiva vid S;
WHILE stiva S nu este vid DO
BEGIN
fie p - vrful din topul stivei S;
IF m vrfuri ale lui p sunt vrfuri adiacente nevizitate
THEN BEGIN
fie z primul vrf nevizitat din vrfurile adiacente cu p;
parcurge muchia (p,z), viziteaz vrful z i introduce-l n stiva S;
END
ELSE elimin vrful p din stiva SEND
END
n cazul n care se va lucra cu un graf conex arbitrar cu relaia de ordine lips, nu va mai avea importan ordinea de parcurgere a vrfurilor. Propunem un algoritm care utilizeaz mai larg posibilitile stivei, cea ce face programul mai efectiv n sensul diminurii timpului de calcul necesar. De exemplu, acest algoritm n varianta recursiv este pe larg utilizat n programele de selectare global n subdirectori (cazul programelor antivirus).
Introdu n stiv vrful iniial i marcheaz-l;
WHILE stiva nu este vid DO
BEGIN
extrage un vrf din stiv;
IF exist vrfuri nemarcate adiacente cu vrful extras
THEN marcheaz-le i introduce-le n stiv;
END
Listingul Programului:#include
#include
#include
typedef struct list
{
int info;
struct list *adr;
}list;
list* pushList(list *prev_el, list *&head_el, int inf);
list** saveList(int n, list **adi_list);
void viewList(int n, list **adi_list);
list* popList(list *curr_el);
int* parLatime(int n, int v_st, list **adi_list, int *vect_res, int &k);
void cleanMem(int n, list **adi_list);
void saveFileList(int n, list **adi_list, FILE *fp);
int main()
{
list **adi_list, *tmp_list;
int n, *vect_res, v_st, i, k, opt;
FILE *fp;
printf("Introduceti numarul de virfuri: ");
scanf("%d", &n);
adi_list = saveList(n, adi_list);
system("cls");
do
{
system("cls");
printf("=========================================\n");
printf("= Parcurgerea grafului in LARGIME =\n");
printf("=========================================\n");
printf(" \n");
printf(" Afisarea listei de adiacenta \n");
printf(" Pracurgerea in largime \n");
printf(" Iesire \n");
printf("#### ");
opt = getche();
switch(opt)
{
case '1':
printf("\nLista de adiacenta: \n");
viewList(n, adi_list);
printf("\n\nApasati orice tasta pentru revenire...");
fp = fopen("md_saveL3.txt", "w");
saveFileList(n, adi_list, fp);
fclose(fp);
getch();
system("cls");
break;
case '2':
printf("\n");
viewList(n, adi_list);
printf("Introduceti virful de pornire: ");
scanf("%d", &v_st);
vect_res =(int *)malloc(n * sizeof(int));
vect_res = parLatime(n, v_st, adi_list, vect_res, k);
printf("Parcurgerea in largime incepind cu virful %d: ", vect_res[0]);
for(i = 0; i < k; i++)
printf("%d ", vect_res[i]);
printf("\n\nApasati orice tasta pentru revenire...");
fp = fopen("md_saveL3.txt", "a");
fprintf(fp, "\nParcurgerea in largime incepind cu virful %d: \n", vect_res[0]);
for(i = 0; i < k; i++)
fprintf(fp, "%d ", vect_res[i]);
fprintf(fp, "\n");
fclose(fp);
free(vect_res);
getch();
break;
default:
cleanMem(n, adi_list);
}
}while(opt != '0');
return 0;
}
//Functia pentru adaugarea unui element intr-o lista
list* pushList(list *prev_el, list *&head_el, int inf)
{
list *tmp = (list *)malloc(sizeof(list));
tmp->info = inf;
tmp->adr = 0;
if(prev_el == 0)
head_el = tmp;
else
prev_el->adr = tmp;
prev_el = tmp;
return prev_el;
}
//Functia pentru introducerea listei de adiacenta
list** saveList(int n, list **adi_list)
{
int i, inf;
list *prev_el, *head_el;
adi_list = (list **)malloc(n * sizeof(list *));
for(i = 0; i < n; i++)
{
prev_el = head_el = 0;
printf("%d |", i + 1);
do
{
scanf("%d", &inf);
prev_el = pushList(prev_el, head_el, inf);
}while(inf != 0);
adi_list[i] = head_el;
}
return adi_list;
}
//Functia pentru afisarea listei de adiacenta
void viewList(int n, list **adi_list)
{
int i;
list *curr_el;
for(i = 0; i < n; i++)
{
curr_el = adi_list[i];
printf("%d |", i + 1);
while(curr_el != 0)
{
printf("%d ", curr_el->info);
curr_el = curr_el->adr;
}
printf("\n");
}
}
//Functia pentru parcurgerea in latime
int* parLatime(int n, int v_st, list **adi_list, int *vect_res, int &k)
{
int i, j, v_con, n_line;
list *next_el, *head_el, *stack_el;
next_el = head_el = stack_el = 0;
if(v_st == 0)
return 0;
k = 0;
j = 0;
do
{
next_el = adi_list[v_st - 1];
while(v_st != 0)
{
v_con = 0;
i = 0;
while(i < k)
{
if(v_st == vect_res[i])
{
v_con = 1;
break;
}
i++;
}
if(v_con == 0)
{
stack_el = pushList(stack_el, head_el, v_st);
vect_res[k] = v_st;
v_st = next_el->info;
k++;
}else{
v_st = next_el->info;
}
if(next_el->adr != 0)
next_el = next_el->adr;
else
break;
}
if(head_el->adr != 0)
{
head_el = popList(head_el);
if(head_el != 0)
v_st = head_el->info;
else
v_st = 0;
}
if(v_st == 0)
{
for(i = 0; i < n; i++)
{
v_con = 0;
j = 0;
do
{
if(vect_res[j] == i + 1)
{
v_con = 1;
break;
}
j++;
}while(j < k);
if(v_con == 0)
{
v_st = i + 1;
break;
}
}
}
}while(k != n);
return vect_res;
}
//Functia pentru stergerea unui element din lista
list* popList(list *head_el)
{
list *tmp;
tmp = head_el;
if(head_el->adr == 0)
head_el = 0;
else
head_el = head_el->adr;
free(tmp);
return head_el;
}
//Functia pentru salvarea listei de adiacenta intr-un document text
void saveFileList(int n, list **adi_list, FILE *fp)
{
int i;
list *curr_el;
for(i = 0; i < n; i++)
{
curr_el = adi_list[i];
fprintf(fp ,"%d |", i + 1);
while(curr_el != 0)
{
fprintf(fp, "%d ", curr_el->info);
curr_el = curr_el->adr;
}
fprintf(fp, "\n");
}
}
//Eliberarea memoriei dinamice ocupate de toate elementele programului
void cleanMem(int n, list **adi_list)
{
int i;
list *curr_el, *prev_el;
for(i = 0; i < n; i++)
{
curr_el = adi_list[i];
while(curr_el != 0)
{
//prev_el = curr_el;
prev_el = curr_el->adr;
free(curr_el);
curr_el = prev_el;
}
}
free(adi_list);
}Rezultat:
Concluzie: Efecuand aceasta lucrare de laborator, am invatat sa efectuam metodele de reprezentare ale grafului in adincime, precum si metodele lui de stocare in memoria calculatorului.
Ca si la prima lucrare, pentru introducerea datelor am folosit lista de adiacenta, ea fiind cea mai simpla metoda de introducere a grafului de la tastatura, care si piermite utilizatorului sa aleaga cu usurinta virfurile necesare,de asemenea aceasta metoda utilizeaza si cel mai putin din memoria calculatorului.PAGE