15827872 Tehnici de Programare

5/28/2018 15827872 Tehnici de Programare

1/158

Decan Sef de catedra

Prof. Univ. Dr. Rodica TRANDAFIR Conf. Univ. Dr. Rodica IOANVIZAT

FISA DISCIPLINEI

I.

UNIVERSITATEA SPIRU HARET

FACULTATEA MATEMATICA-INFORMATICA

DOMENIUL DE LICENTA INFORMATICA

SPECIALIZAREA INFORMATICA

Anul universitar 2008 - 2009

Forma de invatamant ZI

II.

DENUMIRE DISCIPLINA TEHNICI AVANSATE DE PROGRAMARE

III.

CODUL DISCIPLINEI

IV.

Statut disciplina Obligatorie Optionala Facultativa

(se marcheaza cu X) X

V. Structura disciplinei (nr. ore)

Semestrul

(numar de

la 1 la 6)

Curs

(nr. ore/sapt.

si total

nr.ore/sem.)

Seminar

(nr. ore/sapt.

si total

nr.ore/sem.)

Laborator

(nr. ore/sapt.

si total

nr.ore/sem.)

Lucrari practice

(nr. ore/sapt.

si total

nr.ore/sem.)

Proiecte

(nr. ore/sapt.

si total

nr.ore/sem.)4 2/28 - 2/28 - -

VI.(ETCS)

Numar credite 6

VII.

OBIECTIVELE DISCIPLINEI

1. Valorificarea cunostintelor acumulate in cadrul cursurilor de Programare Procedurala,Algoritmi si Structuri de date, Proiectare si Programare Orientata Obiect in vederea

programarii unor algoritmi avansati elaborati cu metode specifice.

2. Crearea deprinderilor de a gandi si programa folosind sabloane (templates)3.

Insusirea unor algoritmi avansati in domeniul prelucrarii sirurilor.4. Cresterea capabilitatii in utilizarea in programarea generica a limbajelor C++ si Java.

5. Asigurarea compatibilitatii cu invatamantul de excelenta : University of Cambridge(http://www.cl.cam.ac.uk/DeptInfo/CST05/node30.html); Imperial College London

(http://www3.imperial.ac.uk/computing/teaching/undergraduate/computing/lectures);

Princeton University (http://www.cs.princeton.edu/academics/catalog/ugrad)

VIII.

CONTINUT TEMATIC

I. Structuri de date fundamentale (Recapitulare)

II. Metode avansate de proiectarea algoritmilor:

1. Recursivitate2. Metoda Greedy3. Metoda Backtracking
http://www.cl.cam.ac.uk/DeptInfo/CST05/node30.htmlhttp://www3.imperial.ac.uk/computing/teaching/undergraduate/computing/lectureshttp://www.cs.princeton.edu/academics/catalog/ugradhttp://www.cs.princeton.edu/academics/catalog/ugradhttp://www3.imperial.ac.uk/computing/teaching/undergraduate/computing/lectureshttp://www.cl.cam.ac.uk/DeptInfo/CST05/node30.html


2/158

4. Metoda Divide et impera5. Metoda Programrii dinamice6. Metoda Branch&Bound.7. Procesarea sirurilor

IX.

TEME SEMINAR-

X.

LUCRARI DE LABORATOR

1. Metode de elaborarea algoritmilor (14 ore)2. Biblioteca Standard de Sabloane (STL) a limbajului C++ (6 ore)3. Cautare in siruri (2 ore)4. Programare generica in Java (6 ore).

XI.

LUCRARI PRACTICE

-

XII.

PROIECTE

-

XIII. Forma de evaluare (procent din nota finala)

Examen Colocviu Verificare pe

parcurs

Lucrari

practice

Laborator Proiecte

- - 70% - 30% -

XIV. BibliografieObligatorie minimala Suplimentara Facultativa

1. Albeanu G.,Algoritmi si

limbaje de programare,

Editura FRM, 2000 (pag. 207-

233)

2. Albeanu G. (coord), L.

Rapeanu, L. Radu, A.

Averian, Tehnici de

programare, Editura FRM,

2003.

3.Doina Logofatu,Algoritmi

fundamentali in Java/C++.

Aplicatii. Polirom, 2007

(integral).

4. Valeriu Iorga, Cristian

Opincaru, Corina Stratan,

Alexandru Chirita, Structuri

de date si algoritmi. Aplicatii

in C++ folosind STL,

Polirom, 2005.

1. Java, Using and

Programming Generics

in J2SE 5.0,

http://java.sun.com/devel

oper/technicalArticles/J2

SE/generics/

2. C. Galatan,

Introducere in C++

Standard Template

Library, Ed. All, 2008.

3. R. Neapolitan, K.

Naimipour ,

Foundations of

Algorithms Using C++

Pseudocode, Jones and

Bartlett Publishers, 2004.

1. N.M. Josuttis, The C++

Standard Library, Addison-

Wesley, 1999.

2. A. Drozdek,Data structures

and algorithms in C++,

Brooks/Cole, 2001.

3. Roberge J., Brandle S.,

Whittington D.,A laboratory

course in C++ data structures

(ed. 2), Jones and Bartlett

Publishers, 2003.

XV.
http://java.sun.com/developer/technicalArticles/J2SE/generics/http://java.sun.com/developer/technicalArticles/J2SE/generics/http://java.sun.com/developer/technicalArticles/J2SE/generics/http://java.sun.com/developer/technicalArticles/J2SE/generics/http://java.sun.com/developer/technicalArticles/J2SE/generics/http://java.sun.com/developer/technicalArticles/J2SE/generics/


3/158

Metode didactice (clasice/moderne)

1. Prelegerea - proiecie in amfiteatru, programe demonstrative;

2. Recomandarea, pentru studiul individual, a unor paragrafe din bibliografia indicat, n

vederea aprofundrii sau extinderii cunotinelor cptate la curs/laborator ;

3. Prezentarea unor exemple i a unor probleme aplicative n cadrul cursului pentru sporirea

interesului cursantilor.4. Evaluare folosind platforma Blackboard.

Data Titular disciplina

Titlul didactic, Numele si

prenumele

Prof. Univ. Dr. GRIGORE

ALBEANU

_____________________ Semnatura

_______________________


4/158

31

2. Structuri de date

O structurde date este o mulime de date organizate ntr-un anumitmod mpreuncu relaiile dintre acestea.n funcie de modul de alocare, structurile de date se clasificn:

structuri de date statice: tabloul, nregistrarea, mulimea, fiierul.Structurile de date statice ocupo zonde memorie constantpetoat durata de executare a blocului n care apare declaraia ielementele ocup poziii fixe. Fiierele sunt structuri de dateexterne (vezi capitolul 1).

structuri de date semistatice: stiva alocat static, coada alocat

static. Structurile de date semistatice ocupo zonde memorie dedimensiune constat, alocatpe toatdurata executrii blocului ncare apare declaraia de structur, iar elementele ocup poziiivariabile pe parcursul executrii programului.

structuri de date dinamice: lista nlnuit, structuri arborescente.Structurile de date dinamice ocup o zon de memorie dedimensiune variabil, alocatdinamic. Alocarea dinamicpermitegestionarea memoriei n timpul executrii programului. Ele suntmult mai flexibile dect cele statice i din aceast cauz sunt

extrem de avantajoase.Liste: Olisteste o colecie de elemente de informaie (noduri)

aranjate ntr-o anumit ordine. Lungimea unei liste este numrul denoduri din list. Structura corespunztoare de date trebuie s nepermit s determinm eficient care este primul/ultimul nod nstructur i care este predecesorul/succesorul (dac exist) unui noddat. Limbajele Pascal sau C(++) ofer posibiliti de implementare aacestor structuri att static ct i dinamic. Operaiile curente care sefac n liste sunt: inserarea unui nod, tergerea (extragerea) unui nod,

concatenarea unor liste, numrarea elementelor unei liste etc.Implementarea unei liste se poate face n principal n doumoduri:

Implementarea secvenial, n locaii succesive de memorie,conform ordinii nodurilor n list. Avantajele acestei tehnicisunt accesul rapid la predecesorul/succesorul unui nod igsirea rapid a primului/ultimului nod. Dezavantajele suntinserarea/tergerea relativ complicat a unui nod i faptul cnu se folosete ntreaga memorie alocatlistei.

Implementarea nlnuit. Fiecare nod conine dou pri:informaia propriu-zis i adresa nodului succesor. Alocarea


5/158

memoriei fiecrui nod se poate face n mod dinamic, n timpulrulrii programului. Accesul la un nod necesit parcurgereatuturor predecesorilor si, ceea ce poate lua ceva mai mult

timp. Inserarea/tergerea unui nod este, n schimb, foarterapid.Listele se pot clasifica dupnumrul de legturi n:

liste simple liste duble liste circulare

O list simpl are o singur legtur, legtura ultimului element esteadresa NIL/NULL. Pentru a accesa lista avem nevoie de o variabilcare s pstreze adresa primului element (cap sau pr i m). O list

dubl are dou legturi: legtura de tip urmtor i legtura de tipprecedent sau anterior. O lista circular este o lista n care, dupultimul nod, urmeaz primul, deci fiecare nod are succesor ipredecesor.

Listele se pot clasifica dup locul n care se fac operaiile deadugare/eliminare astfel:

stive cozi

2.1. Liste simplu nlnuite

ntre nodurile unei liste simplu nlnuite este definito singurrelaiede ordonare. Fiecare nod conine un pointer a crui valoare reprezintadresa nodului urmtor din list.

Limbajul Pascal

type lista = ^nod

nod=recordinf:tip ;urm: lista;

end;

Limbajul C(++)typedef struct nod {

tip inf;struct nod *urm;

}lista;

unde urmeste adresa urmtorului nod (pointer ctre urmtorul nod),iar i nfeste un cmp de informaie util.

Operaii asupra listei simplu nlnuite Crearea unei liste simplu nlnuite:1. Se iniializeaz pointerul pr i mcu Ni l / NULL, deoarece lista la

nceput este goal;

2. Se rezervzonde memorie n memoria heappentru nodul curent;32


6/158

3. Se ncarcnodul curent cu date;4. Se determin adresa ultimului nod i se realizeaz legtura cu

nodul creat;

5. Se reia cu pasul 2 dacse introduce un nod nou. Inserarea unui element x al crui cmp cheie a fost iniializat n

faa unei liste nlnuiteLISTA-INSEREAZA(p,x)1: urm(x) p2: dacpNIL atunci px

Cutarea ntr-o listnlnuitp a elementului x se realizeazprin subprogramul LISTA-CAUTA i returneazpointerul la acest

obiect.LISTA-CAUTA(p,x)1. qp2. ct timp qNIL i cheie(q)x executqurm(q)3. returneazq

Probleme rezolvate1. Fiind dato listsimplu nlnuitcu elemente numere ntregi sserealizeze un program care s execute urmtoarele operaii: crearea,

parcurgerea, adugarea unui nod la nceputul listei, adugarea unui nodla sfritul listei,tergerea unui nod de pe o poziie dat.

Observaii:

Limbajul C(++)Funcia MALLOC se folosete

pentru a rezerva octei dinmemoria heap. Trebuie inclusfiierul antet: stdlib.h saualloc.h

Limbajul Pascal:Procedura NEW(pointer)- alocareadinamica memoriei pentruvariabila dinamicpointer.Procedura DISPOSE(pointer)-eliberarea memoriei ocupate dectre variabila dinamicpointer.

Rezolvare:Parcurgerea unei liste liniare simplu nlnuite se realizeaz cu unpointer care pleacde la capul listei i va referi pe rnd fiecare nod,prelucrnd informaiile din nod apoi se trece la urmtorul nod, prelu-

crm informaiile din nod etc.33


7/158

34

tergerea unui nod de pe o poziie dat p din interiorul listei serealizeaz astfel: se parcurge lista pn la pozitia p-1, se pstreaznodul de pe poziia p, se realizeazlegtura ntre nodul p-1 i p+1 i,

apoi se elibereazmemoria ocupatde nodul p.Implementare n Pascal:

type lista=^nod;nod=recordinf:integer; urm:lista end;

var p,x:integer;cap:lista;{adresa primului nod al listei}procedureadaug(varcap:lista;x:integer); {adaugarea la sfarsitul listei}

var nou,q:lista;

beginnew(nou);nou^.inf:=x;nou^.urm:=nil;ifcap=nil thencap:=nouelse begin

q:=cap;whileq^.urm nildoq:=q^.urm;q^.urm:=nou;end;

end;

procedureadaug_inc(varcap:lista;x:integer); {adaugarea la inceput}var nou:lista;beginnew(nou);nou^.inf:=x;nou^.urm:=nil; {crearea nodului nou}ifcap=nil thencap:=nouelse begin

nou^.urm:=cap;cap:=nou;{realizarea legaturii si primul nod devine nodul creat}

end;

end;procedurelistare(cap:lista);{listarea listei}vart:lista;begin

t:=cap;whiletnil do begin

write(t^.inf,' '); {prelucrarea informatiei}t:=t^.urm; {trecerea la urmatorul nod}end;

end;proceduresterge(varcap:lista; p:integer);


8/158

35

{stergerea nodului de pe pozitia p}var q,w,t:lista;i:integer;begin

ifcap=nil thenwriteln('Lista vida !!! ')else ifp=1 then begin

{stergere la inceputul listei}q:=cap; cap:=cap^.urm; dispose(q);end

else if(cap nil) then begint:=cap; i:=1;while(t^.urm nil) and(i+1


9/158

36

lista* sterg_inc(lista *prim){lista *p;

p=prim;

prim=prim->urm;free(p);return prim;}

void adauga(lista*prim) {/*adauga un nod la o lista simplu inlantuitasi returneaza pointerul spre nodul adaugat sau zero daca nu s-a realizatadaugarea*/

lista *p,*q;

for (p=prim;p->urm!=NULL;p=p->urm)q=(lista*) malloc(sizeof(q));scanf("%d",&q->inf);q->urm=NULL;

p->urm=q;}

void main(){lista *prim;

prim=creare(); parcurgere(prim); prim=sterg_inc(prim);

printf("\n");parcurgere(prim); adauga(prim); parcurgere(prim);}lista *creare(){

int n,i,inf; lista *prim,*p,*q;printf("nr. de elemente");scanf("%d",&n);printf("informatia primului nod"); scanf("%d",&inf);prim=(lista*)malloc(sizeof(prim)); prim->inf=inf;prim->urm=NULL;for(q=prim,i=2;iinf=inf;p->urm=NULL; q->urm=p; q=p;}

return(prim);}void parcurgere(lista *p){

lista *q;for (q=p;q;q=q->urm) printf("%d ",q->inf);

}


10/158

2. Inversarea legturilor ntr-o listsimplu nlnuit.

Rezolvare:

Se parcurge lista iniial folosind trei variabile dinamice p1, p2, p3care vor face referire la elementele consecutive din list. p1 va ficapul listei modificate.

Implementare Pascal:programinvers;type lista=^nod;

nod=record inf:integer; urm:lista end;var i,n,x:integer; p:lista;

procedurecreare(varp:lista; x:integer);varq:lista;beginifp=nil then beginnew(p); p^.inf:=x; p^.urm:=nil endelse begin

q:=p; whileq^.urmnil doq:=q^.urm;new(q^.urm); q^.urm^.inf:=x; q^.urm^.urm:=nil;end;

end;

procedurelistare(p:lista);varq:lista;beginq:=p; whileqnil do beginwrite(q^.inf,' '); q:=q^.urm end;end;

Subprogramul de inversare n C:l i s ta* i nver s( l i s ta*p) {

l i st a *p1, *p2, *p3;p1=p;p2=p- >ur m;

p- >ur m=NULL;whi l e ( p2) {

p3=p2- >ur m;p2- >ur m=p1;p1=p2;p2=p3;}

r et ur n p1;}

functioninversare(p:lista):lista;varp1,p2,p3:lista;beginp1:=p;

p2:=p^.urm;p^.urm:=nil;whilep2nil do begin

p3:=p2^.urm;p2^.urm:=p1;p1:=p2;p2:=p3;end;

inversare:=p1;

end;37


11/158

38

beginread(n);fori:=1 ton do beginread(x); creare(p,x) end;

listare(p);writeln;p:=inversare(p);listare(p)

end.

3. S se efectueze suma a dou polinoame rare (polinom cu foartemuli coeficieni egali cu zero) folosind liste simplu nlnuite.

Rezolvare:

Lista are ca informaie gradul i coeficientul fiecrui termen decoeficient nenul. Pentru a calcula suma este necesar s parcurgemlistele celor doupolinoame i sadugm corespunztor n cea de-atreia list.

Implementare Pascal:typelista=^nod;

nod=recordgrad:1..5000; coef:integer; urm:lista end;var a,b,p,q,r:lista;

i,n,m:integer;procedurecreare(varp:lista);beginwrite('cati coeficienti nenuli are polinomul');readln(n);

new(p);readln(p^.coef,p^.grad);p^.urm:=nil;b:=p; {b este adresa ultimului nod}

fori:=2 ton do beginnew(a);write('coef ',i,':');readln(a^.coef); write('grad ',i,':');readln(a^.grad);

b^.urm:=a; b:=a; b^.urm:=nilendend;procedurelistare(p:lista);vara:lista;begina:=p;whileanil do beginwrite(a^.coef,'x^', a^.grad,' +'); a:=a^.urm end;writeln(#8,' ');

end;


12/158

39

procedureaduna(p,q:lista;var r:lista);vara,b,c,d:lista;begin

a:=p;b:=q; {c este adresa ultimului nod pentru lista suma}while(anil) and (bnil) doifa^.grad=b^.grad then begin

ifr=nil then beginnew(c);c^.grad:=a^.grad;c^.coef:=a^.coef +b^.coef;r:=c; r^.urm:=nil;end

else begin

new(d); d^.grad:=a^.grad;d^.coef:=a^.coef+b^.coef;c^.urm:=d;c:=d;c^.urm:=nilend;

a:=a^.urm;b:=b^.urm;end

else ifa^.grad


13/158

40

ifanil then c^.urm:=a;ifbnil thenc^.urm:=b;

end;

begincreare(p);creare(q);listare(p);listare(q);r:=nil;aduna(p,q,r);listare(r);readln;

end.Exerciii:1. Sse implementeze n C aplicaia de mai sus.

2. S se scrie un subprogram pentru calcularea produsului a doupolinoame rare.3. Sse calculeze valoarea unui polinom ntr-un punct dat.

Indicaie:Calcularea produsului se va face prin parcurgerea tuturor perechilor determeni astfel:-fiecare pereche genereazun nod n polinomul produs-gradul noului nod va fi suma gradelor nodurilor din pereche

-coeficientul noului nod va fi produsul coeficienilor termenilor dinpereche-se eliminnodurile din lista de termeni prin pstrarea fiecrui grad osingur dat astfel: dac exist dou noduri cu acelai grad unul dinele va fi eliminat, iar coeficientul celuilalt va avea valoarea sumeicoeficienilor celor doi termeni.

Valoarea unui polinom se va calcula prin parcurgerea listei iadugnd la valoare produsul dintre coeficient i valoarea dat laputerea gradului din nod.

4.Dndu-se dou liste simplu nlnuite cu elemente numere intregidistincte, sse afiseze diferena celor douliste i elementele comunecelor douliste.Rezolvare:

Diferena celor dou liste conine elementele primeia care nusunt n cea de-a doua. Se parcurge prima listi pentru fiecare nod severific dac este n cea de-a doua list, dac nu se afl atunci seadaug listei trei. Intersecia celor douliste se determinparcurgnd


14/158

41

prima listi pentru fiecare nod se verificdacelementul se afli ncea de-a doua list, dacda atunci se adaugn cea de-a treia list.

Implementare Pascal:type lista=^nod;

nod = recordinf:integer; urm:lista end;var q,cap1,cap2,cap3:lista;

gasit:boolean;procedurecreare(var cap:lista);var n,i:integer;

nou,q:lista;begin

write('nr elem'); read(n); new(cap); read(cap^.inf);cap^.urm:=nil;fori:=2 to n do begin

new(nou); read(nou^.inf); nou^.urm:=nil; q:=cap;whileq^.urmnil doq:=q^.urm;q^.urm:=nouend

end;procedurediferenta(cap1,cap2:lista);

var x:integer;q2:lista;begin

q:=cap1;whileqnil do begin

x:=q^.inf; gasit:=false; q2:=cap2;whileq2nil do begin

ifq2^.inf=x thengasit:=true; q2:=q2^.urmend;

if notgasit thenwrite(x, ' '); q:=q^.urmendend;procedureafisare(cap:lista);var q:lista;begin

q:=cap;whileqnil do beginwrite(q^.inf,' '); q:=q^.urm end;writeln;

end;


15/158

42

procedureintersectie(cap1,cap2:lista; varcap3:lista);var q,q2,nou,q3:lista;

x:integer;

beginq:=cap1;whileqnil do begin

x:=q^.inf; gasit:=false; q2:=cap2;whileq2nil do begin

if q2^.inf=x thengasit:=true;q2:=q2^.urm;end;

ifgasit then ifcap3=nil then

beginnew(cap3); cap3^.inf:=x; cap3^.urm:=nil endelse beginnew(nou); nou^.inf:=x ; nou^.urm:=nil; q3:=cap3;whileq3^.urm nil doq3:=q3^.urm;q3^.urm:=nouend;

q:=q^.urmend

end;

begincreare(cap1); creare(cap2); afisare(cap1); afisare(cap2);diferenta(cap1,cap2);writeln; diferenta(cap2, cap1);writeln('intersectie'); intersectie(cap1,cap2,cap3); afisare(cap3);end.

Exerciiu: Sse implementeze aplicaia de mai sus in C.

5. Sse creeze o listsimplu nlnuit, cu informaie numericastfelnct la orice moment al inserrii lista sfie ordonatcresctor dupinformaie.

Rezolvare:Paii: -crearea unui nod nou

-dac informaia care se adaugeste mai micdect informaiadin capul listei atunci se insereazn faa primului nod

-altfel se parcurge lista pnla primul nod a crei informaie este

mai mare dect informaia noului nod i se insereaz.


16/158

43

Implementare C:

#include

#include #include typedefstruct nod { int inf; struct nod*urm;} lista;lista *prim;lista *creare(void);void parcurgere(lista *p);

voidmain(){lista *prim;prim=creare();

parcurgere(prim);}lista *creare(){int n,inf; lista *prim,*p,*q,*nou;printf("nr. de elemente");scanf("%d",&n);prim=NULL;for(int i=1;iinf=inf;if(prim==NULL){prim=nou;prim->urm=NULL;}

else if(prim->inf>inf){nou->urm=prim;prim=nou;}

else{p=q=prim;

while(p&&p->infurm;}if (p) {q->urm=nou; nou->urm=p;}else{q->urm=nou; nou->urm=NULL;}}

}returnprim;}voidparcurgere(lista *p){ lista *q;for(q=p;q;q=q->urm) printf("%d ",q->inf);

}


17/158

44

Exerciiu: Sse implementeze aplicaia de mai sus n Pascal.

6. Sse scrie un program pentru interclasarea a douliste ordonate

simplu nlnuite.

Rezolvare:Se va parcurge simultan cele dou liste urmnd ca introducerea unuinod n lista final s fie fcutdin lista care are valoarea informaieidin nod mai mic.

Implementare C:#include

#include #include typedefstruct nod {int inf; struct nod*urm;}lista;lista *inter(lista *prim1, lista*prim2){lista *prim,*ultim;if(prim1->inf>prim2->inf){

prim=prim2;prim2=prim2->urm;}

else {

prim=prim1;prim1=prim1->urm;}

ultim=prim;while(prim1&&prim2)

if(prim1->inf>prim2->inf){ultim->urm=prim2;ultim=prim2;prim2=prim2->urm;

}else{ultim->urm=prim1;ultim=prim1;prim1=prim1->urm;}

if(prim1) ultim->urm=prim1; elseultim->urm=prim2;returnprim;}lista *creare(void);

void parcurgere(lista *p);


18/158

45

voidmain(){lista *prim1,*prim2,*prim;prim1=creare();

prim2=creare();/* parcurgere(prim1) */;prim=inter(prim1,prim2);parcurgere(prim1);

}lista *creare(){

int n,inf; lista *prim,*p,*q,*nou;printf("nr. de elemente");scanf("%d",&n);prim=NULL;

for(int i=1;iinf=inf;if(prim==NULL){

prim=nou;prim->urm=NULL;}

else if(prim->inf>inf){

nou->urm=prim;prim=nou;}else {

p=q=prim;while(p&&p->infurm;}

if(p) {q->urm=nou;nou->urm=p;}else {

q->urm=nou;nou->urm=NULL;}

}}returnprim;}voidparcurgere(lista *p){ lista *q;for (q=p;q;q=q->urm) printf("%d ",q->inf);}

Exerciiu: Sse implementeze aplicaia de mai sus n limbajul Pascal.


19/158

2.2. Liste dublu nlnuite

Pentru liste duble create dinamic modul de definire a unui nod este:

Limbajul Pascaltype lista=^nod;

nod=recordinf:tip;urm, ant:lista;

end;

typedef struct nod{inf tip;struct nod *urm;struct nod *ant;

}lista;

Operaiile care se pot defini asupra listelor dublu nlnuite suntaceleai ca i n cazul listelor simplu nlnuite:- crearea unei liste dublu nlnuite;- accesul la un element al unei liste dublu nlnuite;- inserarea unui nod ntr-o listdublu nlnuit;- tergerea unui nod dintr-o listdublu nlnuit;- tergerea unei liste dublu nlnuite.

Probleme rezolvate

1. Sse scrie un program care va conine un meniu cu principaleoperaii asupra listei dublu nlnuite.

Implementarea Pascal a soluiei:typelista=^nod;

nod=recordinf:integer; urm,ant:lista end;var cap:lista;

x:integer;

procedurecreare(varcap:lista);beginnew(cap); write('inf=');readln(cap^.inf); cap^.urm:=nil;cap^.ant:=nil;

end;procedureadaugare(varcap:lista);varq,nou:lista;beginnew(nou);readln(nou^.inf);nou^.urm:=nil;q:=cap; whileq^.urm nil doq:=q^.urm; q^.urm:=nou;nou^.ant:=q;

end;46


20/158

47

procedureinserare(var cap:lista);var nou,q:lista;

k,i:integer;

beginwriteln('unde inserezi? ');read(k);new(nou);write('ce? ');readln(nou^.inf);ifk=1 then begin

cap^.ant:=nou; nou^.urm:=cap; nou^.ant:=nil; cap:=nou;end

else beginq:=cap;

i:=1;while(q^.urmnil) and(i


21/158

48

ifi=k then beginq:=p; p^.ant^.urm:=p^.urm;p^.urm^.ant:=p^.ant; dispose(q);

endelse beginwrite('nu exista'); readln end

endend;procedureparcurgere(varcap:lista);varq:lista;beginq:=cap;whileqnil do beginwrite(q^.inf, ' '); q:=q^.urm end;

readlnend;procedureparcurgere_inv(varcap:lista);varq:lista;beginq:=cap;whileq^.urmnil doq:=q^.urm;whileqnil dobeginwrite(q^.inf, ' '); q:=q^.ant end;readln;

end;beginwhilex 7 do begin

writeln('1.creare'); writeln('2.adaugare');writeln('3.inserare'); writeln('4.stergere');writeln('5.parcurgere'); writeln('6.parcurgere_inv');writeln('7.iesire');readln(x);casex of

1:creare(cap);2:adaugare(cap);3:inserare(cap);4:stergere(cap);5:parcurgere(cap);6:parcurgere_inv(cap);end

endend.


22/158

49

2. Crearea i parcurgerea listei dublu nlnuite n limbajul C:

#include

#includetypedefstructnod{int inf; struct nod*urm,*ant; } lista;lista*prim ,*ultim;voidcreare(int n);voidparcurg(lista*prim);voidparcurg1(lista*ultim);voidmain(){

int n;printf("numarul de elemente:");scanf("%d",&n);

creare(n);puts("\n Parcurgere directa");parcurg(prim);puts("\n Parcurgere indirecta");parcurg1(ultim);}

voidcreare(int n){int i;lista *p;prim=(lista*)malloc(sizeof(lista));printf("informatia primului nod"); scanf("%d",&prim->inf);

prim->urm=prim->ant=NULL;ultim=prim;for(i=2;iinf);p->ant=ultim;ultim->urm=p;p->urm=NULL;ultim=p;}

}voidparcurg(lista*p){if(p){

printf("%d ",p->inf); parcurg(p->urm);}

}voidparcurg1(lista *p){lista *q;for(q=p;q;q=q->ant) printf("%d ",q->inf);

}


23/158

50

2.3. Liste circulare

Dupnumrul de legturi, listele circulare se mpart n: liste simple iliste duble. Listele circulare simple sunt liste simple care au n pluspropietatea cvaloarea cmpului urmtor a ultimului nod este adresacapului listei. Listele circulare duble sunt liste duble care aupropietatea c legtura urmtor a celui de-al doilea cap este primulcap i legtura anteriora primului cap este al doilea cap.

Crearea i parcurgerea listei circulare simplu nlnuite n limbajulC:

#include#include#includetypedef structnod{ int inf; structnod *urm;}lista;voidmain(){

lista *prim,*p,*q;int i,n;/*crearea listei circulare*/printf("inf primului nod");

prim=(lista*)malloc(sizeof(lista));scanf("%d",&prim->inf);prim->urm=NULL;p=prim;printf("nr de elemente");scanf("%d",&n);for(i=2;iinf);p->urm=q;p=q;}

p->urm=prim;/*parcurgerea listei*/printf("%d ",prim->inf);for(q=prim->urm;q!=prim;q=q->urm)printf("%d ",q->inf);

}

Problem rezolvat: Se d un grup de n copii aezai n cerc, caresunt numrai din m n m. Copilul care a fost numrat cu valoarea meste eliminat. Dndu-se pasul de eliminare m se cere s se precizezeordinea ieirii din cerc.


24/158

51

Rezolvare: Simularea eliminrii copiilor se realizeaz cu o listcircular la care se realizeaz eliminarea nodului care are cainformaie numrul copilului scos din joc. Numrarea se va face

parcurgnd m elemente de la poziia de unde s-a efectuat ultimatergere.

Implementarea Pascal (Lista circulareste simpl.)typelista=^nod;

nod=recordinf:integer; urm:lista end;var i,n,m,j:integer;

prim,q,p:lista;procedurecreare(varprim:lista;x:integer);

begin new(prim); prim^.inf:=x; prim^.urm:=prim end;procedureadaugare(var prim:lista;x:integer);varq,p:lista;begin

new(q);q:=prim;whileq^.urmprim doq:=q^.urm;new(p); p^.inf:=x;q^.urm:=p;p^.urm:=prim;

end;procedurelistare(prim:lista);varq:lista;beginnew(q);q:=prim;write(q^.inf,' ');whileq^.urmprim do beginq:=q^.urm; write(q^.inf,' ') end;end;begin {program principal}

read(n); creare(prim,1);fori:=2 ton doadaugare(prim,i); listare(prim);read(m); p:=prim;fori:=1 ton-1 do begin

ifi=1 then forj:=1 tom-2 dop:=p^.urmelse forj:=1 tom-1 dop:=p^.urm;

q:=p^.urm; write(q^.inf,' '); p^.urm:=q^.urm; dispose(q);end;

writeln('castigator=',p^.inf);

end.


25/158

52

Implementarea C (Lista circulareste dubl).#include #include

typedef structnod{int inf; structnod *urm,*ant; }lista;lista *prim,*p,*q;voidcreare(void);voidparcurgere(void);int n,m,i,k;

voidmain(){creare();printf("pasul de numarare");scanf("%d",&m);parcurgere();

while(p!=p->ant){for( i=1;iurm;printf("%d ",p->inf);p->ant->urm=p->urm;p->urm->ant=p->ant;q=p;p=p->urm;free(q);}

printf("%d",p->inf);}

voidparcurgere(){for(p=prim,i=1;iurm) printf("%d",p->inf);/* p=p->urm;*/}voidcreare(){printf("nr. de copii");scanf("%d",&n);prim=(lista*)malloc(sizeof(lista));prim->inf=1;prim->urm=prim->ant=NULL; p=prim;for(i=2; iinf=i;p->urm=q;q->ant=p;p=q;}

q->urm=prim;prim->ant=q;}


26/158

2.4. Stive

O stiv (stack) este o list liniar cu proprietatea c operaiile de

inserare/extragere a nodurilor se fac n/din vrful listei. Ultimul nodinserat va fi i primul ters, stivele se mai numesc i listeLIFO(eng.Last In First Out) sau listepushdown.

53

Cel mai natural mod de reprezentare pentru o stiveste implementareasecvenial ntr-un tablou S[1 .. n], unde n este numrul maxim denoduri. Primul nod va fi memorat n S[1], al doilea n S[2], iar ultimuln S[top], unde top este o variabil care conine adresa (indicele)

ultimului nod inserat. Algoritmii de inserare i de tergere (extragere)a unui nod:

pop

push

functionpush(x, S[1 .. n])

{adauga nodul x in stiva}iftop=nthen returnstiva plinatoptop+1S[top]x

returnsucces

functionpop(S[1 .. n]){sterge ultimul nod inserat din stiva si il returneaza}iftop=0 then returnstiva vida

xS[top]toptop-1

returnx

Cei doi algoritmi necesit timp constant, deci nu depind de mrimea

stivei.


27/158

54

Problem rezolvat: Realizai un meniu n limbajul Pascal care sconinoperaii asupra stivei.

Rezolvare:Implementarea Pascal:typestiva=^nod;

nod=recordinf:integer; urm:stiva end;varcap:stiva;

x:integer;procedureadauga(varcap:stiva);var nou:stiva;begin

new(nou);writeln('Ce sa adaug? ');readln(nou^.inf);nou^.urm:=nil;ifcap=nil thencap:=nou

else beginnou^.urm:=cap;cap:=nou;end;

end;proceduresterge(varcap:stiva);var q:stiva;beginifcap=nil thenwriteln('Stiva vida')

else beginq:=cap;cap:=cap^.urm;dispose(q)

end;end;procedureparcurgere(cap:stiva);var q:stiva;begin

q:=cap;whileq nil do begin

writeln('|',q^.inf,'|'); q:=q^.urm end;writeln('___')

end;


28/158

55

beginwhilex 4 do begin

writeln('1.Adaugare');

writeln('2.Stergere');writeln('3.Listare');writeln('4.Iesire');writeln('Dati optiunea');readln(x);casex of

1:adauga(cap);2:sterge(cap);3:parcurgere(cap)

endendend.

Exerciiu: Sse implementeze n limbajul C aplicaia de mai sus.

Probleme propuse

1. Sse scrie un program care citind numere ntregi din fiierul in.txtcreeazo stivi o afieaz. Sse transforme un numr din baza

10 n baza b folosind o stiv.2. Pe o linie de cale ferat se gsesc, ntr-o ordine oarecare, n

vagoane numerotate de al 1 la n. Linia continucu alte k linii demanevr. Cunoscnd ordinea iniiala vagoanelor, sse obinlaieire vagoanele n ordine: 1,2 ,n; liniile de manevr sunt destulde lungi nct sncappe o singurlinie toate cele n vagoane.

Indicaie:Se dorete partiionarea vagoanelor n k submulimi care auvagoanele ordonate cresctor

2.5. CoziO coad(eng. queue) este o list liniar n care inserrile se fac doarn capul listei, iar extragerile doar din coada listei. Cozile se numesc ilisteFIFO(eng. First In First Out). O reprezentare secvenialpentruo coad se obine prin utilizarea unui tablou C[0 .. n-1], pe care ltratm ca i cum ar fi circular: dup locaia C[n-1] urmeaz locaiaC[0]. Fie p variabila care conine indicele locaiei predecesoare primeilocaii ocupate i fie uvariabila care conine indicele locaiei ocupateultima oar. Variabilele p i u au aceeai valoare atunci i numai


29/158

56

atunci cnd coada este vid. Iniial, avem p= u= 0. Inserarea itergerea (extragerea) unui nod necesittimp constant.

Operaii asupra cozii:functioninsert-queue(x, C[0 .. n-1]){adauga nodul x in capul cozii}

p(p+1) modnifp=u then returncoada plinaC[p] x

returnsuccesfunctiondelete-queue(C[0 .. n-1])

{sterge nodul din coada listei si il returneaza}

if p=u then returncoada vidau(u+1) modnxC[u]

returnx

Testul de coad vid este acelai cu testul de coad plin. Dac s-arfolosi toate cele n locaii, atunci nu am putea distinge situaia decoadplina i cea de coadvid, deoarece n ambele situaii amavea p = u. Se folosesc efectiv numai n-1 locaii din cele n aletabloului C, deci se pot implementa astfel cozi cu cel mult n-1 noduri.

Problem rezolvat: Relizarea unui meniu pentru implementareastatica cozii.

Rezolvare: Cea mai simpl implementare a cozii static este folosireaunui tablou. Pentru gestionarea cozii este nevoie de douelemente: ppoziia primului element i u poziia de dup ultimul element dincoad. Se va face o utilizare circular a spaiului alocat astfel:urmtoarea poziie este p mod n +1.

Implementarea Pascal:TYPEcoada=array[1..50] of integer;varc:coada; p,n,u,o,x:integer;procedureadaugare(varc:coada; varp,u:integer;x:integer);begin

ifp(u mod n)+1 thenbeginc[u]:=x; u:=u mod n +1 end

elsewriteln('coada plina');

end;


30/158

57

procedurestergere(varc:coada; varp,u,x:integer);beginifpu then beginx:=c[p]; p:=p mod n+1 end

elsewriteln('coada goala');end;procedurelistare(c:coada;p,u:integer);vari:integer;beginifp=u thenwriteln('coada goala')

else begini:=p;whileiu do beginwrite(c[i],' '); i:=i mod n+1 end;

end;end;begin

writeln('nr max de elem');read(n);n:=n+1;p:=1;u:=1;repeat

writeln('1..adaugare');writeln('2..stergere');

writeln('3..listare');write('citeste optiunea');readln(o);caseo of

1: beginwrite('introduceti numarul adaugat');readln(x);adaugare(c,p,u,x);end;

2: beginstergere(c,p,u,x);

ifpu thenwriteln(x);end;3: listare(c,p,u);

end;writeln;

untilo=4;end.

Exerciiu: Sse implementeze aplicaia de mai sus n limbajul C++.


31/158

58

Problem rezolvat: S se creeze un program care s conin unmeniu cu operaii asupra unei cozi alocate dinamic.

Rezolvare:Implementarea n limbajul C++:#include #include#include // intrri-ieiri n C++typedef structnod {int inf; structnod *urm; }lista;voidadaug(lista* &prim, int x){

lista *nou, *p;nou=newlista; // crearea unui nod n C++

nou->inf=x;nou->urm=NULL;if (prim==NULL) prim=nou;else {

nou->urm=prim; prim=nou;}

}lista * creare(){

int n,x;lista*prim;

prim=NULL;clrscr();coutn;for(int i=0;i


32/158

59

voidsterg(lista *&prim){lista *p;if(prim==NULL) couturm!=NULL){p=p->urm;}delete p->urm; p->urm=NULL;}

}void main(){

lista *prim=NULL;int opt,x;

do{ clrscr();cout


33/158

60

Exerciiu: S se realizeze programul n Pascal corespunztoraplicaiei de mai sus.

Probleme propuse:1. Fiind dato listsimplu nlnuitavnd informaii numere ntregisse elimine numerele negative.

2. S se realizeze interclasarea a n liste simplu nlnuite ordonatecresctor.

3. Fiind date dou liste simple cu informaii de tip ntreg, s serealizeze subprograme pentru urmtoarele operaii: intersecia,reuniunea, diferena i diferena simetric a elementelor celordouliste.

4. S se scrie un program care citete cuvintele dintr-un fiier textin.txt, cuvintele sunt separate prin spaii i afieaz numrul deapariii al fiecrui cuvnt din fiier. Se vor folosi liste simplunlnuite.

5. Sse elimine dintr-o listsimplu nlnuittoate nodurile care auo informaie dat.

6. Sse realizeze operaii cu matrici rare folosind alocarea dinamica.7. Fiind dato listdubl, sse separe n douliste elementele de pe

poziii pare de elementele de pe poziii impare.

8. Fiind dato listdublcu informaii de tip ir de caractere, ssefacordonarea elementelor listei.9. Fiind dat o list dubl cu informaii de tip ntreg s se

construiasco listdublnumai cu elemente prime.10. Pe o tij sunt n bile colorate cu cel mult k culori, fiecare bil

avnd o etichetcu un numr de la 1 la n. Sse mute bilele pe altek tije, pe fiecare punnd numai bile din aceeai culoare. S seafieze bilele de pe fiecare din cele k tije, folosind structuridinamice.

Indicaie:Tija iniialreprezinto stiv, informaia dintr-un nod va ficompusdin numrul bilei i numrul culorii. Se va parcurge stiva ise adaug n stiva corespunztoare culorii, apoi se terge din stivainiial. Se va lucra cu un vector de stive pentru cele k tije.

11. Sse implementeze subprograme pentru operaiile de bazcu listecirculare duble.

12. Fie un traseu circular ce cuprinde n orae. O main trebuie sparcurg toate oraele i s se ntoarc de unde a plecat.

Parcurgerea se poate face n ambele sensuri. Se cere s se


34/158

61

determine un traseu posibil de parcurgere astfel nct snu rmnn pan tiind c n fiecare ora exist o staie de benzin cu ocantitate de benzin suficient, iar maina consuma c litri la 100

de kilometri.13. Fiind dat o list circular dubl, s se fac un subprogram deinserare a unui element pe o poziie dat.

14. S se realizeze un subprogram care terge elementele egale cuzero dintr-o listcircular.

15. Sse creeze o listde liste, sse parcurgi sse tearg.16. S se scrie un program care citete cuvintele dintr-un text i

afieaznumrul de apariii al fiecrui cuvnt din textul respectiv.17. Sse scrie un program care citete cuvintele dintr-un text i scrie

numrul de apariie al fiecrui cuvnt, n ordinea alfabetic acuvintelor respective.18. ntr-o gar se consider un tren de marf ale crui vagoane sunt

inventariate ntr-o list. Lista conine, pentru fiecare vagon,urmtoarele date: codul vagonului, codul coninutului vagonului,adresa expeditorului, adresa destinatarului. Deoarece n gar seinverseaz poziia vagoanelor, se cere listarea datelor desprevagoanele respective n noua lor ordine.

Indicaie:se creeazo stivn care se pstreazdatele fiecrui vagon.

Datele corespunztoare unui vagon constituie un element al stivei,adicun nod al listei simplu nlnuite. Dupce datele au fost puse nstiv, ele se scot de acolo i se listeaz.

19. La o agenie CEC existun singur ghieu care se deschide la ora 8i se nchide la ora 16, dar publicul aflat la coadeste deservit ncontinuare. Deoarece la ora nchiderii coada este destul de mare seridic problema oportunitii deschiderii a nc unui ghieu laagenia respectiv. Se cunosc operaiile efectuate la agenie i

timpul lor de execuie. n acest scop se realizeaz o simulare pecalculator a situaiei existente care sstabileasco medie a orelorsuplimentare efectuate zilnic pe o perioadde un an.

Indicaie: Programul de simulare a problemei indicate construiete ocoadde ateptare cu persoanele care sosesc la agenie n intervalul detimp indicat. Se va folosi funcia randompentru a determina operaiasolicitat i apoi pentru a determina intervalul de timp ntre doupersoane care vin la agenie.


35/158

62

20. S se realizeze un program care implementeaz subprogramepentru crearea i exploatarea unei cozi duble.

21. Se do matrice rarmemoratntr-o list. Se cere:

a) sse afieze toate elementele diferite de zero de pe diagonalaprincipal, secundar;b) sse afieze pe ecran matricea sub forma obinuit, frreconstituirea ei n memorie.

2.6. Grafuri

Noiuni introductive

Ungrafeste o pereche G= , unde Veste o mulime de vrfuri,

iar M= VxV este o mulime de muchii. O muchie de la vrful a lavrful b este notat cu perechea ordonat (a, b), dac graful esteorientat, i cu mulimea {a, b}, dac graful este neorientat. Douvrfuri unite printr-o muchie se numesc adiacente. Un drum este osuccesiune de muchii de forma (a1, a2), (a2, a3), ..., (an-1, an) sau deforma {a1, a2}, {a2, a3}, ..., {an-1, an} dupcum graful este orientat sauneorientat.Lungimeadrumului este egalcu numrul muchiilor care lconstituie. Un drumsimplu este un drum n care nici un vrf nu serepet. Un ciclueste un drum care este simplu, cu excepia primului i

ultimului vrf, care coincid. Un grafaciclic este un graf fr cicluri.Un subgraf al luiG este un graf , unde V'V, iar M' esteformatdin muchiile dinMcare unesc vrfuri din V'. Ungraf parialeste un graf


36/158

uneori valori, iar muchiilor li se pot ataa informaii numite uneorilungimisau costuri.

Metode de reprezentare a grafurilora) Matricea de adiacen

Cea mai cunoscutmetodde memorare a grafurilor neorientate estematricea de adiacen, definitn felul urmtor: 1, dacexistmuchie(arc) de la vrful i la vrful j i 0, n caz contrar. n cazul grafurilorneorientate, aceastmatrice este simetric, folosindu-se efectiv numaijumtate din spaiul matricei. n unele probleme este eficient cacealalt jumtate a matricei s fie folosit pentru reinerea altor

informaii. Matricea de adiaceneste folositn general pentru grafuricu un numr mic de noduri, deoarece dimensiunea ei este limitatdedimensiunea stivei.

Exemplu de graf orientat:

0 0 1 0 0 1 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 1 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 1

0 0 0 0 0 0 0 0

0 1 2 3 4 5 6 7

0

1

2

3

4

7

5

6

0

0

0

0

0

1

0

0

8

0 0 0 0 0 0 0 08 0

1

4

5

6

3

2

8

7

0

b) Listele de muchii

Aceast metod de memorare presupune reinerea unei matrice cu 2linii i m coloane, pe fiecare coloanfiind reinute douextremiti aleunei muchii. Aceasta reprezentare este eficientatunci cnd avem de

examinat toate muchiile grafului.63


37/158

64

Listele de muchii sunt folosite n cazul algoritmilor care prelucreazsecvenial muchiile, cum ar fi de exemplu algoritmul Kruskalde aflarea arborelui parial de cost minim n cazul grafurilor rare (cu numr

mic de muchii).

c) Listele de vecini.

Prin liste de vecini (adiacen) se realizeazataarea la fiecare vrf i alistei de vrfuri adiacente lui (pentru grafuri orientate, este necesar camuchia s plece din i). ntr-un graf cu m muchii, suma lungimilorlistelor de adiaceneste 2m, dacgraful este neorientat, respectiv m,dac graful este orientat. Dac numrul muchiilor n graf este mic,

aceast reprezentare este preferabildin punct de vedere al memorieinecesare. Este posibil sexaminm toi vecinii unui vrf dat, n medie,n mai puin de n operaii. Pe de alt parte, pentru a determina dacdouvrfuri i i j sunt adiacente, trebuie sanalizm lista de adiacena lui i (i, posibil, lista de adiacen a lui j), ceea ce este mai puineficient dect consultarea unei valori logice n matricea de adiacen.

Listele de vecini sunt cele mai recomandate n tratarea algoritmilor dinteoria grafurilor din doumotive principale:1. spatiul folosit este gestionat dinamic, putndu-se memora astfel

grafuri de dimensiuni mari;2. complexitatea optim pentru majoritatea algoritmilor fundamen-tali din teoria grafurilor (parcurgeri, conexitate, muchii i punctecritice, algoritmi de drum minim etc.) este obinutnumai folosindliste de vecini.

Existdoumodaliti de implementare a listelor de vecini.a) Prima dintre ele folosete o matriceT cu 2 linii i 2m coloane i

un vector C cu n elemente care reine pentru fiecare nod indicelecoloanei din T pe care este memorat primul element al listeinodului respectiv (sau 0 dacvrful respectiv nu are vecini). Apoi,pentru o anumitcoloani din T, T(i,1) reine un element din listacurent, iar T(i,2) reine coloana pe care se gsete urmtorulelement din lista respectivsau 0 daclista s-a terminat.

b) Cea de-a doua implementare folosete pentru fiecare nod o listsimplu nlnuit memorat n heap. Pentru fiecare list estesuficient s pstrm o singur santinel (cea de nceput a listei),introducerea vrfurilor fcndu-se mereu la nceputul listei(deoarece ordinea vrfurilor n listnu conteaz).


38/158

Exemplu:

65

1

4

5

6

3

2

8

7

0

0

1

2

3

4

7

5

6

8

2 5

6

6

4

5

3 7

2 8

Parcurgerea grafurilor

Parcurgerea unui graf presupune examinarea n vederea prelucrrii

tuturor vrfurilor acelui graf ntr-o anumit ordine, ordine care spermitprelucrarea optima informaiilor ataate grafului.

a) Parcurgerea DF (parcurgerea n adncime)

Parcurgerea DF (Depth First) presupune ca dintr-un anumit nod v,parcurgerea s fie continuat cu primul vecin al nodului v nevizitatnc. Parcurgerea n adncime a fost formulatcu mult timp n urmca o tehnicde explorare a unui labirint. O persoancare cautcevantr-un labirint i aplicaceasttehnicare avantajul ca urmtorul locn care caut este mereu foarte aproape.

Parcurgerea vrfurilor n adncime seface n ordinea: 1 3 4 5 2 61

4

56

3

2

Cel mai cunoscut mod de imple-mentare a parcurgerii DF se realizeazcu ajutorul unei funcii recursive, darexisti cazuri n care este recomandato implementare nerecursiv.

Implementarea acestei metode se

face folosind o stiv. Aceasta este iniia-


39/158

66

lizatcu un nod oarecare al grafului. La fiecare pas, se ia primul vecinnevizitat al nodului din vrful stivei i se adaugn stivdacnu maiexistse coboarn stiv.

Algoritmul recursiv:procedureDF(G)

forfiecare vVdomarca[v] nevizitatfor fiecare vVdo

if marca[v] = nevizitat then ad(v)

proceduread(v){varful v nu a fost vizitat}

marca[v] vizitatforfiecare virf w adiacent lui v doifmarca[w] = nevizitat then ad(w)

Algoritmul iterativ:

procedure iterad(v)Sstiva vidamarca[v] vizitat

push(v, S)while Snu este vida do

whileexista un varf w adiacent luiftop(S)astfel incat marca[w] = nevizitat do

marca[w] vizitatpush(w, S)

pop(S)

unde funciaftopreturneazultimul vrf inserat n stiv.Parcurgerea n adncime a unui graf nu este unic; ea depinde

att de alegerea vrfului iniial, ct i de ordinea de vizitare avrfurilor adiacente.

Problem: Ct timp este necesar pentru a parcurge un graf cu nvrfuri i m muchii?

Rezolvare:Deoarece fiecare vrf este vizitat exact o dat, avem n apeluri aleprocedurii ad. n procedura ad, cnd vizitm un vrf, testm marcajulfiecrui vecin al su. Dac reprezentm graful prin liste de adiacen,adic prin ataarea la fiecare vrf a listei de vrfuri adiacente lui,

atunci numrul total al acestor testri este m, dacgraful este orientat,


40/158

67

i 2m, dac graful este neorientat. Algoritmul necesit un timp O(n)pentru apelurile procedurii ad i un timp O(m) pentru inspectareamrcilor. Timpul de executare este O(max(m, n)) =O(m+n).

Dacreprezentm graful printr-o matrice de adiacen, se obineun timp de executare de O(n2).

b) Parcurgerea BF (parcurgerea n lime)

Parcurgerea BF (Breath First) presupune faptul cdupvizitarea unuianumit nod v, sunt parcuri toi vecinii nevizitai ai acestuia, apoi toivecinii nevizitai ai acestora din urm, pn la vizitarea tuturor nodu-rilor grafului.

Parcurgerea n lime este folosit de obicei atunci cnd se

exploreazparial anumite grafuri infinite, sau cnd se caut cel maiscurt drum dintre douvrfuri.

Implementarea acestei metode se face folosind o coad. Aceastaeste iniializat cu un nod oarecare al grafului. La fiecare pas, seviziteaznodul aflat n vrful cozii i se adaug n coad toi veciniinevizitai ai nodului respectiv.

Parcurgere_BF(nod start)Coada start

Vizitat(start) adevratct timp coada nu este vid

ic nodul de la nceputul coziiadaugtoti vecinii nevizitati ai luiic n coadVizitat(i) adevrat, unde i este un vecin nevizitat al

nodului ic

Pentru a efectua o parcurgere n laime a unui graf (orientat sauneorientat), aplicm urmtorul principiu: atunci cnd ajungem ntr-un

vrf oarecare v nevizitat, l marcm i vizitm apoi toate vrfurilenevizitate adiacente lui v, apoi toate vrfurile nevizitate adiacentevrfurilor adiacente lui v etc. Spre deosebire de parcurgerea nadncime, parcurgerea n lime nu este n mod natural recursiv.

procedure lat(v)Ccoada vidamarca[v] vizitatinsert-queue(v, C)


41/158

68

while Cnu este vida dou delete-queue(C)for fiecare virf w adiacent lui u do

if marca[w] = nevizitat then marca[w] vizitatinsert-queue(w, C)Pentru compararea celor doumetode apelm procedurile iterad i latdin procedura parcurgere(G)

procedureparcurge(G)for fiecare v Vdo marca[v] nevizitatfor fiecare v Vdo

if marca[v] = nevizitat then {iterad sau lat} (v)

Aplicaia 2.6.1:Algoritmul lui Dijkstra

Fie G = (X,U) un graf orientat, unde X este mulimea vrfurilor i Ueste mulimea muchiilor. Fiecare muchie are o lungime nenegativ.Unul din vrfuri este desemnat ca vrf surs. Problema este sdeterminm lungimea celui mai scurt drum de la surs ctre fiecarevrf din graf. Vom folosi un algoritmgreedy, datorat lui E.W. Dijkstra(1959). Notm cu C mulimea vrfurilor disponibile (candidaii) i cuS mulimea vrfurilor deja selectate. n fiecare moment, S conineacele vrfuri a cror distanminimde la surseste deja cunoscut,n timp ce mulimea C conine toate celelalte vrfuri. La nceput, Sconine doar vrful surs, iar n final S conine toate vrfurile grafului.La fiecare pas, adugam n S acel vrf din C a crui distan de lasurseste cea mai mic.

La fiecare pas al algoritmului, un tablou D conine lungimeacelui mai scurt drum special ctre fiecare vrf al grafului. Dup ceadugm un nou vrf v la S, cel mai scurt drum special ctre v va fi,de asemenea, cel mai scurt dintre toate drumurile ctre v. Cnd

algoritmul se termin, toate vrfurile din graf sunt n S, deci toatedrumurile de la sursctre celelalte vrfuri sunt speciale i valorile dinD reprezintsoluia problemei.

Matricea M dlungimea fiecarei muchii, cu M[i, j] =+, dacmuchia (i, j) nu exist. Soluia se va construi n tabloul D[2 .. n].

Algoritmul este:

S = {0}

for i = 1 to n D[i] = M[1][i]


42/158

69

for i = 1 to n-2caut cel mai mic D[v] pentru fiecare v SS = S {v}

fortoate vrfurile u Sif(D[u] > D[v] + M[v][u]) thenD[u] = D[v] + M[v][u]

Implementare n C:

#include#include#defineFALSE 0#defineTRUE 1

#define MAXN 20intsetupDijkstra(int *nod_p, inta[MAXN][MAXN], int *startnod_p);

voiddoDijkstra(intnod, inta[MAXN][MAXN], intstartnod);

voidtraceinfo(intS[MAXN], intD[MAXN], intnod);

intmain(){intnod, startnod;

inta[MAXN][MAXN];printf("Algoritmul lui Dijkstra\n");if(setupDijkstra(&nod, a, &startnod)) return1;doDijkstra(nod, a, startnod);return0;

}intsetupDijkstra

(int *nod_p, inta[MAXN][MAXN], int *startnod_p){inti, j;

do{printf("Introduceti 0 pentru a specifica graful,sau 1 pentru exemple ");scanf("%d", &i);}while((i < 0) || (i > 1));

if(i == 1){*nod_p = 5;for(i=0; i


43/158

70

printf("A Matrix: a b c d e\n");for (i=0; i


44/158

71

if(urmnod >= nod) return;// printf(" D[%c]=%2d, ", 'a'+urmnod, mic);printf("adauga nodul %c to S\n", 'a'+urmnod);

S[urmnod] = TRUE;for(j=0; j D[urmnod] + a[urmnod][j]){

D[j] = D[urmnod] + a[urmnod][j];

/*printf("D[%c] schimba %2d\n", 'a'+j, D[j]); */}else

/* printf("nu schimba\n"); */}

}traceinfo(S, D, nod);}

}

voidtraceinfo(intS[MAXN], intD[MAXN], intnod){inti;printf(" S = {");for(i=0; i


45/158

72

vom folosi vectorulD care reine distana minimgsitla un momentdat de la s la celelalte noduri. Algoritmul foloseste o coad Q, careeste iniializatcu nodul s. La fiecare pas, algoritmul scoate un nod v

din coad i gsete toate nodurile w a cror distan de la surs laacestea poate fi optimizatprin folosirea nodului v. Dacnodul wnuse afl deja n coad, el este adugat acesteia. Aceti pai se repetpncnd coada devine vid.

Algoritmul utilizeaz tehnica de relaxare, procednd ladescreterea estimrii d[v] a drumului minim de la sursa s la fiecarevrf v V pncnd este obinut costul adevrat (u,v) corespunztorunui drum minim. Algoritmul returneazadevarat daci numai dacnu conine cicluri de cost negativ accesibile din surs.

Algoritmul este:BELLMAN-FORD(G,c,s)1.INIT(G,s)2. pentru i1,|X[G]|-1 executa

3. pentru fiecare muchie (u,v) U4. RELAXEAZA(u,v,c)5. pentru fiecare muchie (u,v) U executa6. daca d[v]>d[u]+c(u,v)7. returneaza FALS

8. returneaza ADEVARATImplementare n C:

#include#include#defineFALSE 0#defineTRUE 1#define MAXN 26#defineINFINIT 999intsetupBellman(int*nod_p, inta[MAXN][MAXN], int *start_p);intdoBellman(intnod, inta[MAXN][MAXN], intstart);voidtraceinfo(intD[MAXN], intnod);intmain(){

intnod, start; inta[MAXN][MAXN];printf("Algoritmul lui Bellman-Ford\n");if(setupBellman(&nod, a, &start)) return1;if(doBellman(nod, a, start)){

printf(" Ciclu negativ\n"); return2;}

return0;}


46/158

73

intsetupBellman(int *nod_p, inta[MAXN][MAXN], int *start_p){

inti, j;

do{printf("Introduceti 0 pentru graf, or 1 pentru exemple ");scanf("%d", &i);

}while((i < 0) || (i > 1));if(i == 1){

*nod_p = 5;for(i=0; i


47/158

74

for(i=0; i


48/158

75

Probleme rezolvate

R2.6.1. Sse afieze componentele conexe folosind parcurgerea DF a

grafului. Graful este reprezentat prin matricea de adiacencititdinfiier TEXT.

Rezolvare: Implementarea Pascal folosind parcurgerea DF recursiv:var a:array[1..100,1..100] of integer;

viz:array[1..100] of integer;f:text;n,i,j:integer;

proceduredf(X:integer);vari:byte;

beginwrite(x, ' ');viz[x]:=1;fori:=1 ton doif(a[x,i]=1) and(viz[i]=0) thendf(i);end;

procedurecitire;begin

assign(f,'matrice.txt');reset(f);

readln(f,n);fori:=1 to n do beginforj:=1 ton doread(f,a[i,j]);readln(f);end;

end;begin

citire;fori:=1 ton doviz[i]:=0;

fori:=1 ton do ifviz[i]=0 then begindf(i);writeln end;end.

Exerciiu:Implementai n lumbajul C aplicaia de mai sus folosind funcia Df(iterativ) de mai jos.

voiddf(int x){inti,k,y,s[10],gasit;

k=1;


49/158

76

s[1]=x;viz[x]=1;printf("%d ",x);while(k>=1) /*cat timp stiva este nevida */ {

y=s[k];gasit=0;

for(i=1;i


50/158

77

whilep


51/158

78

write('componenta tare conexa ',k,':',i,' ');forj:=1 ton do

if(ji) and(a[i,j]0)and(a[j,i]0) then

beginwrite(j,' ');m[j]:=true;end;

inc(k);writeln;end;

end.

Implementare n limbajul C:

#includeintn, a[10][10],viz[10];voidcitire(){

intm,i,j,x,y;printf("n=");scanf("%d",&n); printf("m=");scanf("%d",&m);for(i=1;i


52/158

79

R2.6.4. Dndu-se dou grafuri reprezentate prin matricea de adia-cen sse precizeze daccel de-al doilea graf este graf parial sau

subgraf al primului graf.

Rezolvare:Implementarea Pascal este:usescrt;typemat=array[1..100,1..100] ofinteger;var a,b:mat;

n,m,n1,m1,i,j:integer;procedurecreare;varx,y,i,j:integer;

beginwriteln(' MARTICEA 1');write('Dati numarul de varfuri');readln(n);write('Dati numarul de muchii');readln(m);fori:=1 ton doforj:=1 ton doa[i,j]:=0;fori:=1 tom do begin

write('Dati primul capat al muchiei ',i,' : ');

readln(x);write('Dati al doilea capat al muchiei ',i,' : ');readln(y);a[x,y]:=1; a[y,x]:=1end

end;procedurecreare1;varx,y,i,j:integer;begin

WRITELN(' MATRICEA 2');write('Dati numarul de varfuri');readln(n1);write('Dati numarul de muchii');readln(m1);fori:=1 ton1 doforj:=1 ton1 dob[i,j]:=0;fori:=1 tom1 do begin

write('Dati primul capat al muchiei ',i,' : '); readln(x);write('Dati al doilea capat al muchiei ',i,' : '); readln(y);b[x,y]:=1;b[y,x]:=1;end;

end;


53/158

80

proceduresubgraf;vars:boolean;begin

s:=true;if n1>n thens:=false;fori:=1 ton1 do forj:=1 ton1 doif(a[i,j]=1) and(b[i,j]=0) thens:=false;

ifs=false thenwriteln(' B nu e subgraf al lui A.')elsewriteln(' B e subgraf al lui A.');

end;proceduregraf_p;varg:boolean;begin

g:=true;ifn n1 theng:=false;fori:=1 ton doforj:=1 ton doif(a[i,j]=0) and(b[i,j]=1) theng:=false;

ifg=false thenwriteln(' B nu e graf partial al lui A.')elsewriteln(' B e graf partial al lui A.');

end;begin

clrscr;creare;creare1;

graf_p;subgraf;end.Exerciiu: Sse implementeze aplicaia de mai sus n limbajul C.

R2.6.5.Determinarea drumurilor minime ntre oricare dounoduri.

Rezolvare: Se folosete algoritmul lui ROY-FLOYD. Se pornete dela matricea costurilor C.

pentruk=1,n execut

pentrui=1,n executpentruj=1,n executc[i,j]=min(c[i,j],c[i,k]+c[k,j])

Simultan cu determinarea lungimilor minime ale drumurilor pot fireinute drumurile folosind un tablou d, unde d[i,j] reprezint muli-mea predesesorilor lui j pentru drumul minim de la i la j.

Implementare Pascal:Var c:array[1..100,1..100] of longint; v:array[1..100]of integer;

d:array[1..100,1..100] of set of 1..10;

n,m,i,j,k,nr:integer; x,y:integer;


54/158

81

procedurecitire;varcost,x,y:integer;begin

write('nr. de noduri');readln(n);write('nr. de muchii');readln(m);for i:=1 ton do

forj:=1 ton do ifij thenc[i,j]:=maxint elsec[i,j]:=0;fori:=1 to m do begin

write('Dati capetele arcului si costul ');readln(x,y,cost); c[x,y]:=cost;end;

end;

procedureinitializare;{determina multimea predecesorilor, initializeaza multimea D}beginfori:=1 to n do

forj:=1 ton doif(ij) and(c[i,j]c[i,k]+c[k,j] thenbeginc[i,j]:=c[i,k]+c[k,j]; d[i,j]:=d[k,j] end

else ifc[i,j]=c[i,k]+c[k,j] thend[i,j]:=d[i,j]+d[k,j];


55/158

82

fori:= 1 ton do beginforj:=1 ton dowrite(c[i,j]:4);writeln

end;write('Dati doua noduri'); readln(x,y);writeln('costul minim= ', c[x,y], ' drumurile minime=' );forx:=1 ton do fory:=1 ton do

beginwriteln('drum de la ',x,'la ',y);ifc[x,y]=maxint thenwrite('nu exista')

else beginnr:=1;v[1]:=y;

drum(x,y)endend

end.

Exerciiu: Sse implementeze algoritmul Roy-Floyd n limbajul C.

R2.6.6. Sse verifice dacun graf reprezentat dinamic este conex saucomplet.

Rezolvare:Se folosete un tablou de liste unde bl[i]reprezintlista vecinilor lui i.

Implementare Pascal:

typelista=^nod;nod= recordinf:integer; urm:lista end;

var bl:array[1..100] oflista;f:text;i,n,x:integer;complet:boolean;

procedureadaugare (varp:lista;x:integer);var t,q:lista;begin

new(q);q^.inf:=x;q^.urm:=nil;ifp=nil thenp:=q

else begint:=p;whilet^.urmnil dot:=t^.urm;t^.urm:=q;end;

end;


56/158

83

procedurelistare(p:lista);vart:lista;begin

t:=p;whilet nil do beginwrite(t^.inf,' ');t:=t^.urmend;

writeln;end;proceduredf(i:integer);var q,t,st:lista;

viz:array[1..100] ofinteger;conex,gasit:boolean;j:integer;

beginforj:=1 ton doviz[j]:=0;viz[i]:=1;write(i,' ');new(q);q^.inf:=i;q^.urm:=nil;st:=q;whilestnil dobegin

x:=st^.inf; t:=bl[x]; gasit:=false;whilet nil do begin

ifviz[t^.inf]=0 then beginnew(q); q^.inf:=t^.inf; q^.urm:=nil; viz[t^.inf]:=1;write(t^.inf,' '); q^.urm:=st; gasit:=true; st:=q; break;end;

t:=t^.urm;end;

ifnotgasit then begint:=st; st:=st^.urm; dispose(t) end;end;

conex:=true;

forj:=1 ton do ifviz[j]=0 thenconex:=false;ifconex thenwrite('conex') elsewrite('nu este conex');end;functionnumarare( p:lista):integer;var nr:integer; t:lista;begin

nr:=0;t:=p;whiletnil do beginnr:=nr+1; t:=t^.urm end;numarare:=nr

end;


57/158

84

beginassign(f,'in.txt');reset(f);readln(f,n);

fori:=1 ton do beginwhile noteoln(f) do beginread(f,x);adaugare(bl[i],x)end;

readln(f);end;

writeln;df(1);

complet:=true;fori:=1 ton do ifnumarare(bl[i])n-1 thencomplet:=false;ifcomplet thenwrite('complet') elsewrite ('incomplet');

end.Exerciiu: Sse implementeze aplicaia de mai sus n limbajul c.

R2.6.7.Fiind dat un graf, sse verifice daceste aciclic.Rezolvare:

Un graf este aciclic daceste frcicluri. Presupunem c fiecare nod

face parte dintr-o component conex. Se ia fiecare muchie i dacextremitile sunt n aceeai component conex atunci adugndaceea muchie se formeazciclu; dacnu sunt n aceeai componentconextoate nodurile care sunt n aceeai componentcu extremitateaa doua trec n componenta conexa extremitii 1.

Implementare Pascal:Var f:text;

a:array[1..1000]ofinteger; n:integer; nume:string;procedureciclic;

vari,j,k:integer;beginwriteln('Care este numele fisierului de intrare ?');readln(nume);assign(f,nume); reset(f);readln(f,n);fori:=1 ton doa[i]:=i;whilenotseekeoln(f) do

begin

readln(f,i,j);


58/158

85

ifa[i]=a[j] thenbeginwriteln('Graful din fisierul ',nume,' contine cel putin un ciclu');

close(f); halt;end;fork:=1 ton do ifa[k]=a[j] thena[k]:=a[i];end;writeln('Graful din fisierul ',nume,' nu contine cicluri');close(f);

end;begin

ciclic

end.Implementare C:

#include#include#include#includeFILE*f;intn,a[10];

voidciclic(){inti,j,k;fscanf(f,"%d",&n);for(i=1;i


59/158

86

R2.6.8. Se dun graf i un nod - considerat ca nodul nr. 1; secere sse determine toate nodurile accesibile din acest nod.

Rezolvare:

Implementare Pascal:var

a: array[1..20,1..20] ofinteger; {matricea de adiacenta}c: array[1..20] ofinteger;{vectorul unde pastram nodurile accesibile}n,i,j,k,p:integer; gasit:boolean;

beginwrite('dati numarul de noduri; n=');readln(n);

writeln('dati matricea de adiacenta:');fori:=1 ton doforj:=1 ton doread(a[i,j]);c[1]:=1; k:=1; gasit:=true; i:=1;whilei


60/158

87

fori:=1 ton doforj:=1 ton doa[i,j]:=0;while noteof(f) do begin

readln(f,i,j);

a[i,j]:=1; a[j,i]:=1end;fori:=1 ton-2 do forj:=i+1 ton-1 do

fork:=j+1 ton doif(a[i,j]=1) and(a[j,k]=1) and(a[k,i]=1) thenwriteln(i,' ',j,' ',k);

end.

2.7. Arbori

Fie Gun graf orientat. Geste un arbore cu radacina r, dacexistn

Gun vrf rdin care oricare alt vrf poate fi ajuns printr-un drum unic.Adncimeaunui vrf este lungimea drumului dintre rdcina iacest vrf; nlimea unui vrf este lungimea celui mai lung drumdintre acest vrf i un vrf terminal.nlimeaarboreluieste nalimeardcinii; nivelul unui vrf este nlimea arborelui minus adncimeaacestui vrf.

Reprezentarea unui arbore cu rdcinse poate face prin adrese,ca i n cazul listelor nlnuite. Fiecare vrf va fi memorat n treilocaii diferite, reprezentnd informaia propriu-zisa vrfului (valoa-

rea vrfului), adresa celui mai vrstnic fiu i adresa urmtorului frate.Pstrnd analogia cu listele nlnuite, dac se cunoate de la nceputnumrul maxim de vrfuri, atunci implementarea arborilor cu rdcinase poate face prin tablouri paralele.

Dac fiecare vrf al unui arbore cu rdacin are pn la n fii,arborele respectiv este n-ar.

ntr-un arbore binar, numrul maxim de vrfuri de adncime keste 2k. Un arbore binar de nlime i are cel mult 2i+1-1 vrfuri, iardac are exact 2i+1-1 varfuri, se numeste arbore plin. Vrfurile unui

arbore plin se numeroteazn ordinea adncimii.Un arbore binar cu n vrfuri i de nlime ieste complet, dacse obine din arborele binar plin de nlime i, prin eliminarea, daceste cazul, a vrfurilor numerotate cu n+1, n+2, , 2i+1-1. Acest tip dearbore se poate reprezenta secvenial folosind un tablou T, punndvrfurile de adncime k, de la stnga la dreapta, n poziiile T[2k],T[2k+1], , T[2k+1-1] (cu posibila excepie a nivelului 0, care poate fiincomplet). Un arbore binar este un arbore n care fiecare vrf are celmult doi descendeni, fcndu-se distincie ntre descendentul stng i

descendentul drept al fiecrui vrf.


61/158

Reprezentarea arborilor binariReprezentarea prin paranteze: se ncepe cu rdcina arborelui, iarfiecare vrf care are descendeni este urmat de expresiile ataatesubarborilor care au ca rdcindescendenii vrfului, desprite prinvirgul i cuprinse ntre paranteze. Dac lipsete un descendent sub-expresia corespunztoare este cuvntul vid. Pentru arborele de maisus, reprezentarea este: 6(2(1,(4(3,5)), 8(7, 9(,10)))Reprezentarea standard: n care pentru fiecare vrf i este precizat des-cendentul su stng ST(i) descendentul su drept DR(i) = i informaiaasociatv`rfului INF(i):

static:ST i DR sunt doutablouri ST=(0, 1, 0, 3, 0, 2, 0,7, 0, 0)DR=(0, 4, 0, 5, 0, 8, 0, 9,10,0) rad=6

dinamic:

type arbore=^nod;nod=record

inf:integer;

st,dr:arbore;end;

typedef struct nod{int inf;struct nod *st;

struct nod *dr;}arbore;si se declara arbore *rad;

Reprezentarea cu doi vectori DESC i TATA: n vectorul DESC,avnd valori 1, 1,0 se precizeaz pentru fiecare nod ce fel dedescendent este el pentru printele su iar n vectorul TATA se indicpentru fiecare vrf, nodul printe. Pentru exemplul de mai sus:

TATA=(2,6,4,2,4,0,8,6,8,9) DESC=(-1,-1,-1,1,1,0,-1,1,1,1)

88


62/158

89

Parcurgerea arborilor binari

preordine:se viziteaz rdcina, se traverseaz subarborele stngn preordine, se traverseazsubarborele drept n preordine;

inordine: se traverseaz subarborele stng n inordine, seviziteazrdcina, se traverseazsubarborele drept n inordine;

postordine: se traverseaz subarborele stng n postordine, setraverseaz subarborele drept n postordine, se traverseazrdcina.

Aplicaia 2.7.1.Sse creeze un arbore binar i apoi sse parcurgnpreordine, s se caute un nod n arbore, sse afieze cheile de pe unanumit nivel dat, sse afieze drumurile de la rdcinla frunze i s

se calculeze adncimea arborelui creat.Rezolvare:

Implementare Pascal:programarb_binar;type arbore=^nod;

nod =recordst,dr:arbore; inf:integer end;varp:arbore;k,x,y,max,z:integer;a:array[1..100] ofinteger;{Procedura creare arbore binar}

procedurecreare(varp:arbore);varx:integer;begin

read(x);ifx=0 thenp:=nil

else beginnew(p); p^.inf:=x;write('Dati stanga lui ',x); creare(p^.st);write('Dati dreapta lui ',x); creare(p^.dr);

end;end;{Procedura parcurgere arbore binar - prin preordine}procedurepreordine(p:arbore);beginifpnil then begin

write(p^.inf,' ');preordine(p^.st); preordine(p^.dr);end;

end;


63/158

90

{Cautarea unui nod din arbore}functioncautare(p:arbore; x:integer):boolean;begin

ifp=nil thencautare:=falseelse ifx=p^.inf thencautare:=trueelsecautare:= cautare(p^.st,x) orcautare(p^.dr,x);

end;{Afisarea tuturor cheilor de pe nivelul dat}procedurenivel(p:arbore;k,x:integer);beginifpnil then begin

ifk=x thenwrite(p^.inf,' ');

nivel(p^.st,k+1,x);nivel(p^.dr,k+1,x);end;

end;{Drumurile de la radacina la frunze}proceduredrum_frunze(p:arbore;k:integer);vari:integer;beginif(p^.st=nil)and(p^.dr=nil) then begin

a[k]:=p^.inf;fori:=1 tok dowrite(a[i],' ');writelnend

else ifpnil then begina[k]:=p^.inf;drum_frunze(p^.st,k+1);drum_frunze(p^.dr,k+1);end;

end;{Afisarea numarului maxim de nivele}procedureadancime(p:arbore;k:integer; varmax:integer);beginifpnil then begin

ifk>max thenmax:=k;adancime(p^.st,k+1,max);adancime(p^.dr,k+1,max);end

end;


64/158

91

begincreare(p);preordine(p);

{Pentru procedura cautare}read(x);writeln(cautare(p,x));{Pentru procedura nivel}write('Nivelul= ');read(y);nivel(p,0,y);{Pentru procedura drum_frunze}drum_frunze(p,1);{Pentru procedura adancime}adancime(p,0,max);

writeln('Numarul de nivele este: ',max);end.

Implementare n C++ :

#include #include #include #includetypedef struct nod{

intinf;structnod *st, *dr;}arbore;

arbore *rad;inta[10], max=0;arbore *creare(){intx;arbore *p;coutx;if(x==0) returnNULL;

else{ (p)=(arbore*) malloc(sizeof(arbore)); (p)->inf=x;cout


65/158

92

voidinordine(arbore *p){if(p){

inordine(p->st); printf("%d",p->inf); inordine(p->dr);

}}voidpostordine(arbore *p){if (p){

postordine(p->st); postordine(p->dr); printf("%d",p->inf);}

}intcautare(arbore *p, intx){if(p){

if(p->inf==x) return1;returncautare(p->st,x)||cautare(p->dr,x);}

else return0;}voidnivel(arbore*p, int k,int x){if(p){

if (k==x) printf("%d ",p->inf);nivel(p->st,k+1,x); nivel(p->dr,k+1,x);

}}voiddrum_frunze(arbore*p,int k){inti;

if((p->st)&&(p->dr)) {a[k]=p->inf;for(i=1;iinf;drum_frunze(p->st,k+1); drum_frunze(p->dr,k+1);}

}}voidadancime(arbore *p, intk){if (p) {

if(k>max) max=k; adancime(p->dr,k+1) ;adancime(p->st,k+1);

}}


66/158

93

voidmain(){intx;rad=creare();

preordine(rad);printf("inf cautata:");scanf("%d", &x);if (cautare(rad,x)) printf("exista");elseprintf("nu exista");coutx;cout


67/158

94

procedureinserare(varp:arbore;x:integer);varq:arbore;begin

new(q);q^.inf:=x;q^.st:=nil;q^.dr:=nil;ifp=nil thenp:=qelse ifp^.inf=x thenwrite('Exista')

else ifp^.inf


68/158

95

Implementare C++:#include#include

#includetypedef structnod {intinf; nod *st,*dr;}arbore;arbore *rad;arbore *q;voidadaug(arbore* &p,int x){if(p==NULL){

p=newnod;p->inf=x;p->st=p->dr=NULL;

}else if(p->inf>x) adaug(p->st,x);else if(p->infdr,x);

elsecout dr);}

}

arbore *cauta(arbore*p, int x){if(p==NULL) returnNULL;else if(p->infst;cauta(p,x);}else if(p->inf>x){

q=p;p=p->st; cauta(p,x);}else returnp;

}


69/158

96

voidsterge(arbore *&r,intx){arbore *t,*q1,*p;int a;

t=cauta(r,x);if(t==NULL){coutst){if(t->infinf) q->st=NULL;delete t;}

else if(t->st==NULL&&t->st){if(q->infinf) q->dr=t->st; elseq->st=t->st;delete t;}

else if(t->st==NULL&&t->dr){if(q->inf>t->inf) q->st=t->dr; elseq->dr=t->dr;delete t;}else{

p=t;while (p->st!=NULL){q=p;p=p->st;}}

q1=t;t->inf=p->inf;if(p->dr==p->st){

q->st=NULL;delete p;}

else{q->st=p->dr;delete p;}

while(q1->st&&q1->infst->inf){a=q1->inf;q1->inf=q1->st->inf; q1->st->inf=a;q1=q1->st;}

}


70/158

97

void main(){int x;arbore *rad=0;

creare(rad);inordine(rad);sterge(rad,2);

}

Probleme rezolvate n limbajul Pascal

R2.7.1. Sse scrie un subprogram pentru afiarea numrului cheilornegative i pozitive dintr-un arbore binar.

procedurep3(p:arbore);beginifpnil then begin

p3(p^.st);ifp^.inf=0 thennr2:=nr2+1;p3(p^.dr);end;

end;R2.7.2. S se scrie un subprogram pentru afiarea cheilor imparedintr-un arborele binar.

procedurep2(p:arbore);beginifpnil then begin

ifp^.inf mod2 =1 thenwrite(p^.inf,' ');p2(p^.st); p2(p^.dr)end

end;R2.7.3. Sse scrie un subprogram pentru aflarea produsului cheilor

pozitive dintr-un arborele binar.

functionp4(p:arbore):longint;beginifpnil thenifp^.inf >0 thenp4:=p^.inf*p4(p^.st)*p4(p^.dr)

elsep4:=p4(p^.st)*p4(p^.dr)elsep4:=1

end;


71/158

98

R2.7.4. S se scrie un subprogram pentru aflarea numrului defrunze dintr-un arborele binar .

functionp5(p:arbore):integer;beginifp=nil thenp5:=0 elseif(p^.st=nil) and(p^.dr=nil) thenp5:=1

else p5:=p5(p^.st)+p5(p^.dr)end;

R2.7.5.. Sse scrie un subprogram pentru afiarea nodurilor care auun succesor dintr-un arbore binar.

procedurep6(p:arbore);begin

ifpnil then beginif((p^.st=nil) and(p^.drnil)) or((p^.stnil) and(p^.dr=nil))

thenwrite(p^.inf,' ');p6(p^.st); p6(p^.dr)end

end;

R2.7.6. S se scrie un subprogram pentru aflarea numrului denoduri de pe un nivel dat dintr-un arbore binar.

functionp7(p:arbore;k:integer):integer;beginifpnil thenifk=l thenp7:=1+p7(p^.st,k+1)+p7(p^.dr,k+1)

elsep7:=p7(p^.st,k+1)+p7(p^.dr,k+1)elsep7:=0

end;

Probleme propuse:

1. Se d un graf orientat cu n noduri. S se verifice dac exist unnod avnd gradul interior n-1 i gradul exterior 0.2. Fie G = (X,U) un graf orientat i farcircuite. Sse determine o

renumerotare a vrfurilor sale astfel ncat dac (u,v)U, atuncinumrul de ordine al lui u este mai mic dect numrul de ordine allui v (sortare topologic).

3. Fie G =(X,U) un graf orientat cu n vrfuri. Sse determine un altgraf avnd aceleai vrfuri, aceeai matrice a drumurilor i avndun numr minim de arce (se pot scoate, introduce noi arce).


72/158

99

4. La un turneu particip n juctori, fiecare juctor jucnd pe rndmpotriva celorlali juctori. tiind cnu existjocuri egale, sseconstruiasc o listcare s cuprind toi juctorii astfel ncat doi

juctori i, j sunt alturi dacjuctorul i la nvins pe juctorul j.5. La curtea regelui Artur s-au adunat 2n cavaleri i fiecare din ei areprintre cei prezeni cel mult n-1 dumani. S se arate c Merlin,consilierul lui Artur, poate s-i aeze n aa fel pe cavaleri la omasa rotund nct nici unul dintre ei snu stea alturi de vreunduman.

6. Fie G=(X,U) un graf conex cu n noduri. Sse determine eficientcel mai mic k astfel nct tergnd nodurile etichetate cu 1,2...k, naceastordine s rezulte un graf ale crui componente conexe au

toate cel mult n/2 noduri.7. S se determine, ntr-un graf conex, un ciclu care conine dounoduri date, dar nu conine un al treilea nod.

8. Numim transpusul unui graf G = (X,U), graful care are aceeaimulime de noduri, arcele sale fiind arcele grafului G, dar avndsens opus. Dndu-se G prin matricea de adiacensau prin liste devecini, sse determine n fiecare caz transpusul grafului dat.

9. Find date n persoane n care fiecare persoanse cunoate pe sinei eventual alte persoane. S se formeze grupuri n care fiecare

persoanscunoasctoate celelalte persoane din grup (o persoanaparine unui singur grup). Relaia x cunoate pe y nu este nmod normal nici simetric, nici tranzitiv.

Indicaie: Se asociazproblemei date un graf orientat cu n noduri i seconstruiete matricea de adiacen (a[i,j]=1 daca i cunoaste pe j =i 0dac i nu cunoate pe j). Pentru fiecare persoan neataat la unmoment dat unui grup se va construi grupul din care face parteaceasta. Soluia nu este unic.

10. Sse determine, ntr-un graf turneu, un drum elementar care trece

prin toate vrfurile. Un graf turneu este un graf orientat cuproprietatea c ntre oricare douvrfuri distincte existun arc inumai unul.

Indicaie:Se adaugarcul format din nodurile 1 i 2 ntr-o listliniar.Fiecare din vrfurile urmtoare se adaug la drumul creat anterior fien fa, fie la sfrit, fie intercalat n list.11. Fie G=(X,U) un graf ponderat. Sse calculeze diametrul grafului.

Se numete diametrul unui graf, notat d(G), d(G)=max{l[i]/ iX},unde l[i] este lungimea drumului maxim care are ca extremitate

iniialvrful i.


73/158

100

12. Fie G un graf orientat n care fiecare arc are asociat un cost pozi-tiv. Sse determine un circuit elementar care s treacprin toatevrfurile grafului care saibcost minim.

13. Se considerun grup de n persoane. Fiecare persoana are cel puinn/2 prieteni i cel mult k dumani n grup. Una din persoane are ocarte pe care fiecare dorete so citeasc. Sse determine o mo-dalitate prin care cartea scircule pe la fiecare persoano singurdat, transmiterea ei facndu-se numai ntre doi prieteni, iar nfinal cartea sajungdin nou la proprietarul crii.

14. Pentru un graf dat n numerotare aciclic (orice arc u = (x,y) din Usatisface condiia x


74/158

101

3. Metode pentru rezolvarea problemelor

3.1. MetodaDivide et Impera

3.1.1. Prezentarea metodei

Metoda general de programare cunoscut sub numele de divide etimpera (dezbin i stapnete) const n mprirea repetat a uneiprobleme n subprobleme de acelai tip, dar de dimensiune mai mic,urmat de combinarea soluiilor subproblemelor rezolvate pentru aobine soluia problemei iniiale. Fiecare subproblem se rezolvdirect dac dimensiunea ei este suficient de mic nct s poat firezolvat imediat cu un procedeu specific, altfel este mprit n

subprobleme mai mici folosind acelai procedeu prin care a fostdescompus problema iniial. Procedeul se reia pn cnd, n urmadescompunerilor repetate, se ajunge la probleme care admit rezolvareimediat.

Algoritmul fiind de natur repetitivi deoarece subproblemeleau aceeai form cu cea a problemei iniiale, metoda Divide etimpera poate fi implementatelegant folosind o funcie recursiv.

n continuare este datfuncia generalcare implementeazalgoritmul.

functiondivimp(X: problema)if(X este suficient de mica) then y rezolv(X)

else{descompune problema x n subproblemele X1, X2,, Xkfori 1 tok doyidivimp(Xi)

/* combiny1, y2, , ykpentru a obine y soluia problemei X */y combin(y1, y2, , yk)

returny}Uneori recursivitatea se poate nlocui cu un ciclu iterativ. Versiuneaiterativ poate fi mai rapid i folosete mai puin memoriecomparativ cu varianta recursiv care utilizeaz o stiv pentrumemorarea apelurilor.3.1.2. Probleme rezolvate

R3.1.1.[Cel mai mare divizor comun]Fie n numere naturale nenulex1, x2,,xn. Sse calculeze cmmdc pentru numere date.


75/158

102

Rezolvare:programdivizor_comun;var x:array[1..25] of integer; n, i:integer;

functionDivizor(a,b:integer):integer;beginwhileab doifa>b thena:=a-b elseb:=b-a;Divizor := aend;

functioncmmdc(lo,hi:integer):integer;varm:integer;begin

if(hi-lo


76/158

103

var n,i,pos:integer;ch:char;

begin

write('n = ');readln(n);writeln('Introduceti numerele');fori:=1 ton do beginwrite('x[',i,'] = '); readln(x[i]) end;repeat

writeln;write('Numarul cautat = ');readln(nr);pos := cauta(1,n);ifpos 0 then

writeln(nr,' se afla in sir la pozitia ', pos)elsewriteln(nr,' nu se afla in sir!');write('Continuati (y/n) ?[y] ');ch:=UpCase(readkey);

untilch = 'N';end.R3.1.3. [Sortare rapid]Fie n N* i numerele x1, x2,,xn. Sse scrieo procedurrecursivde sortare (quicksort) n ordine cresctoare anumerelor date.

Rezolvare:#includevoidQSort (int *table, int left,int right){

intleftp,rightp,aux;unsignedtype = 1;leftp =left;rightp=right;do{

if( table[leftp]>table[rightp] ){

type ^= 1;aux = table[leftp];table[leftp] = table[rightp];table[rightp] = aux;}

elsetype ? rightp--: leftp++;}while(leftp < rightp);if( leftp-left > 1) QSort(table,left,leftp-1);if( right-rightp >1) QSort(table,rightp+1,right);

}


77/158

104

voidmain(){intn,i;intx[100];

printf(n = ); scanf(%d,&d);for(i=0;i


78/158

105

voidMSort(inttabel[],inttemp[], intlo, inthi){intmid, k, t_lo, t_hi;if(lo >= hi) return;

mid = (lo+hi) / 2;MSort(tabel,temp, lo, mid);MSort(tabel,temp, mid+1, hi);t_lo = lo;t_hi = mid+1;for(k = lo; k hi || tabel[t_lo] < tabel[t_hi]) && (t_lo


79/158

106

4. Se d o plac de tabl cu lungimea x i limea y avnd n guridate prin coordonatele lor ntregi. Se cere sse decupeze o bucatdreptunghiularde arie maximi frguri tiind csunt permise

numai tieturi orizontale i verticale.5. Se consider un vector de lungime n. Se numete plierea

vectorului operaia de suprapunere a unei jumti (donatoare)peste cealalt jumtate (receptoare). Dacn este impar elementuldin mijloc se elimin. Elementele rezultate dup pliere vor aveanumeroatarea jumtii receptoare. Plierea se poate repeta pncnd se obine un singur element (final). Scriei un program cares determine toate elementele finale posibile i s afiezesuccesiunile de plieri corespunztoare. Rezolvai aceiai probleminnd cont cla pliere fiecare element receptor se dubleazi dinacesta se scade elementul donator corespunztor.

6. Rezolvai problema turnurilor din Hanoi folosint dou tije demanevr. Comparai numrul de mutri efectuate.

7. Fie P(x) un polinom de grag n cu coficieni reali. S se evaluezepolinomul n punctul x0folosind metoda Divide et Imera.

8. Scriei o procedurDivide et Impera pentru inversarea unui irde caractere.

9. Se d un dreptunghi prin dimensiunile sale numere naturale.Dreptunghiul trebuie descompus n ptrate cu laturi numerenaturale, paralele cu laturile dreptunghiului iniial. Se cerenumrul minim de ptrate n care se poate descompunedreptunghiul.

10. Se dau un ptrat i un cerc. Se cere sse calculeze aria lor comuncu precizie de o zecimal. Coordonatele se citesc de la tastaturisunt numere reale. Aria se va afia pe ecran.

11. Un arbore cartezian al unui vector este un arbore binar definitrecursiv astfel: rdcina arborelui este elementul cel mai mic dinvector; subarborele stng este arborele cartezian al subvectoruluistng (fade poziia elementului din rdcin); subarborele drepteste arborele cartezian al subvectorului drept. Se dun vector dedimensiune n. Sse afieze arborele su cartezian.


80/158

107

3.2. Metoda programrii dinamice

3.2.1. Principii fundamentale ale programrii dinamice

Programarea dinamic, ca i metoda divide et impera, rezolvproblemele "combinnd" soluiile subproblemelor. Un algoritm bazatpe programare dinamicrezolvfiecare subproblemo singurdati,apoi, memoreaz soluia ntr-un tablou, prin aceasta evitndrecalcularea soluiei dac subproblema mai apare din nou isubprobemele care apar n descompunere nu sunt independente.

Metoda programrii dinamice se aplic problemelor deoptimizare. n problemele de optim metoda const n determinareasoluiei pe baza unui ir de decizii d1, d2, d3....dn, unde di transform

problema din starea si-1n starea si.Paii pentru rezolvarea unei probleme folosind programareadinamic:

1. Caracterizarea structurii unei soluii optime;2. Definirea recursiva valorii unei soluii optime;3. Calculul valorii unei soluii optime4. Construirea unei soluii optime din informaia calculat.

Principii fundamentale ale programrii dinamice:1. Dac d1, d2, ... dn este un ir optim de decizii care duc un

sistem din starea iniial n starea final, atunci pentru orice i(1in) d1, d2, ... di este un ir optim de decizii.2. Dac d1, d2, ... dn este un ir optim de decizii care duc un

sistem din starea iniial n starea final, atunci pentru orice i(1in) di, di+1, ... dn este un ir optim de decizii.

3. Dacd1, d2, ... , di, di+1... dneste un ir optim de decizii careduc un sistem din starea iniialn starea final, atunci pentruorice i (1in) d1, d2,... , di i di, di+1, ... dn sunt douirurioptime de decizii.

3.2.2. Probleme rezolvate

R3.2.1. [Subir cresctor maximal] Se consider un ir de n numerentregi. Sse determine cel mai lung subir cresctor din acesta.

Exemplu: n=87 1 8 2 11 4 12 3

Subirul cresctor maximal: 7 8 11 12 cu lungimea 4

Rezolvare:Se construiete tabloul L reprezentnd lungimea maxima

unui subir maximal care l conine ca prim element pe a[i] astfel


81/158

108

L[n]=1 i L[i]=1+max{L[j]/ j>i i a[j]>a[i]} pentru i de la n-1 la 1(metoda nainte - deoarece soluia unei subprobleme se afl pe bazasubproblemelor din urm).

Implementare Pascal:var i,j,n,poz,max:integer;

l,a:array[1..30] of integer;begin

write('n=');read(n);fori:=1 ton do begin write('a[',i,']='); read(a[i]) end;fori:=1 ton dol[i]:=0;l[n]:=1;fori:=n-1 downto1 do

beginmax:=0;forj:=1+i ton do

if(a[j]>a[i]) and(maxa[poz]) and(l[i]=max-1) then beginpoz:=i;write(a[poz],' ');max:=max-1end;

i:=i+1end

end.

Implementare C:

#includevoidmain(){

intn,i,j,poz,max,a[100],l[100];printf("n=");scanf("%d",&n);

for(i=1;i


82/158

109

for(i=1;i0;i--){

max=0;for(j=i+1;j1){if((a[i]>a[poz]) &&(l[i]==max-1)) {poz=i;printf("%d ",a[poz]);max=max-1;}

i++;}

}

Exerciiu: S se rezolve aceast problem folosind varianta napoide programare dinamic (soluia unei subprobleme se afl pe bazasubproblemelor dinainte).

Indicaie: Tabloul L se construiete astfe L[1]=1 i L[i]=1+max{L[j]/j


83/158

110

fori:=1 ton doread(a[i]);fori:=n downto1 dobegin

max:=0;

forj:=i+2 ton do if(maxmax then begin

max:=l[i];poz:=iend;

writeln('suma maxima este: ',l[1]);max:=l[1];poz:=1;write('sirul: ');repeat

write(a[poz],' '); i:=poz+2;while(i


84/158

111

while((i


85/158

112

a[n,n]=1;a[n,k]=a[n-k,0]pentru n2k;a[n,k]=a[n-k,i]pentru i de la 1 la k.

Implementare C:#includevoidmain(){

intn,i,k,j,p,a[100][100];printf("n=");scanf("%d",&n);a[1][0]=1;a[1][1]=1;for( i=2;i


86/158

113

ifl[i-1,j]>l[i,j-1] thenl[i,j]:=l[i-1,j]+a[i,j]elsel[i,j]:=l[i,j-1]+a[i,j];

writeln(l[n,m]); max:=l[n,m];p:=n;q:=m; write(a[n,m],' ');

while(p1) and(q1) do beginifl[p-1,q] = l[p,q]-a[p,q] thenp:=p-1 elseq:=q-1;write(a[p,q],' ');end;

write(a[1,1]);end.

Exerciiu: Sse implementeze aplicaia de mai sus n C.

3.2.3. Probleme propuse

1. [Triunghi] Se considerun triunghi de numere. Sse calculeze ceamai mare dintre sumele numerelor ce apar pe drumurile ce pleacdinvrf i ajung la bazi sse reconstituie drumul de summaxim. npunctul (i,j) se poat

15827872 Tehnici de Programare

Documents

Transcript of 15827872 Tehnici de Programare