APLICATII - STRUCTURI DE DATE DERIVATE DIN STRUCTURA DE LISTA
1.Se cere sa se implementeze operatorii de prelucrare pentru
liste dublu inlantuite, utilizind drept suport de implementare structuri de
date de tip:
a) tablou
b) pointer
c) cursor.
Fiecare din aceste implementari se vor realiza in doua variante:
una obisnuita si o a doua , in care lista e circulara, avind un nod fictiv
care "inchide lista ".
Se vor masura timpii de executie ai operatorilor, facind aprecieri asupra
performantelor.
2.O lista dublu inlantuita existenta in memorie contine o expresie aritmetica
in notatie postfix, in care operanzii sint reprezentati prin litere mici, iar
operatorii pot fi +, -, * sau / , nodurile avind urmatoarea structura:
type pointer=^nod;
nod=record oper:char; {litera (numele variabilei) sau unul din operatorii
admisi }
val:real; {valoarea operandului sau 0 daca nodul
corespunde unui operator }
urm,ant:pointer {inlantuirile inainte si inapoi}
end;
Sa se scrie cite o procedura de evaluare a expresiei in urmatoarele variante:
-reducind pe rind cite trei noduri (continind 2 operanzi si un operator)
la un nod continind rezultatul partial, pina la reducerea listei la un singur
nod continind rezultatul final
-folosind o stiva in care se depun valorile operanzilor si rezultatele
partiale (se va implementa stiva printr-o lista sau tablou)
Pe parcursul evaluarii, se vor face verificarile privind corectitudinea
expresiei, o eroare find semnalata printr-un mesaj si oprind evaluarea
expresiei. Sa se compare timpii de executie ai celor doua variante.
3.Este posibil sa fie memorate doua structuri de date de tip stiva intr-un
acelasi tablou, una crescind de la pozitia 1 spre sfirsit, cealalta in sens
invers. Se cere sa se redacteze o procedura PUSH(X,S) unde S este una sau alta
dintre stive. Procedura va include toate testele de eroare necesare, care vor
fi semnalate prin mesaje corespunzatoare.
4.Se cere sa se elimine recursivitatea din urmatoarele proceduri:
function combinari(n,m:integer):integer; {calculeaza combinari de n luate cite
m presupunind ca 0<=m<=n si n>=1}
begin
if (n=1) or (m=0) or (m=n) then
combinari:=1
else
combinari:=combinari(n-1,m)+combinari(n-1,m-1)
end;
procedure inversare(var l:lista); {inverseaza lista l}
var x:tip_element;
begin
if not {lista vida} then
begin
x:=furnizeaza(primul(l),l);
suprima(primul(l),l);
inversare(l);
insereaza(l,x,fin(l))
end
end;
Sa se compare timpii de executie pentru variantele recursiva si nerecursiva.
5.O coada cu doua capete (DEQUEUE) este o lista in care elementele pot fi
suprimate sau inserate la ambele capete. Se cere sa se dezvolte implementarea
unor astfel de cozi utilizind structuri de tip tablou, pointer si cursor.
Matrici rare
Proiectati un sistem de gestionare a matricilor rare patrate de dimensiune
n x n , identificate printr-un indice, care sa permita realizarea urmatoarelor
operatii:
- initializeaza(i) - initializeaza matricea cu numarul i
- creaza(i) - citeste matricea i
- aduna(i,j,k) - creaza matricea k ca suma a matricilor i si j
- inmulteste(i,j,k) - creaza matricea k ca produs al matricilor i si j
- tipareste(i) - tipareste matricea i ( ca matrice patratica )
Se cere:
- sa se descrie si sa se justifice alegerea modului de implementare a
matricilor
- sa se implementeze operatorii si sa se evalueze timpii lor de executie
prin functia O.
Polinoame
Sa se implementeze intr-o maniera eficienta un sistem de gestionare a
polinoamelor, identificate prin cate un indice, care sa permita realizarea
interactiva a operatiilor:
vide - initializeaza toate polinoamele
vid(i) - face vid polinomul i
citeste(i) - citeste polinomul i ( perechile de coeficient- putere
ale lui x )
tipareste(i) - tipareste polinomul i sub forma externa uzuala
evalueaza(i) - pentru un x citit, tipareste valoarea polinomului i
aduna(i,j,s) - creaza polinomul s ca suma a celor i si j
inmulteste(i,j,p) - creaza polinomul p ca produs al celor i si j
terminare.
Sa se evalueze performantele implementarii din punctul de vedere al memoriei
utilizate si al timpilor de executie.
Secventa de perechi valide
Se da initial o secventa care defineste perechi de simboluri,
de genul (simbol_sting, simbol_drept).
Se da apoi urmatoarea regula pentru testarea unei secvente de simboluri:
Secventa este considerata valida daca contine numai simboluri
care pot fi puse in corespondenta in perechi in felul urmator:
1.- fiecare pereche contine un simbol de tipul simbol_sting si unul
de tipul simbol_drept, simbolul sting precede totdeauna simbolul drept
2.- fiecare simbol face parte din exact o pereche
3.- secventa de simboluri care apar intre simbol_sting si
simbol_drept pentru fiecare pereche trebuie sa satisfaca cond 1, 2
Ex:
pentru perechile de simboluri:
A Z
left right
( )
{ }
[ ]
secventa de mai jos este valida:
A left ( ( ) { [ ] { } } ) left right right Z [ ]
Programul principal va citi o secventa de simboluri si va determina
daca respecta regula anterior definita.
Varianta1: Se va implementa si utiliza TDA lista dublu inlantuita. Programul
va folosi o lista dublu inlantuita pentru rezolvarea
problemei potrivirilor
Varianta2:Se va implementa si utiliza TDA stiva. Programul va folosi
o stiva pentru rezolvarea problemei potrivirilor
Joc - numaratoare
Un grup de copii este asezat in cerc si participa la urmatorul
joc: initial, se stabileste un numar N si se alege (aleator) un copil
de la care se incepe numaratoarea, si care este eliminat primul.
Apoi, tot al N-lea participant este eliminat
din cerc, jocul continua pina cind ramine un singur participant.
Sa se scrie un program care citeste numele participantilor
la joc, numarul N si afiseaza numele persoanelor in ordinea inversa
eliminarii lor (ultimul ramas, cistigatorul, va fi afisat primul).
Se va folosi o lista circulara simplu inlantuita pentru
memorarea cercului copiilor.