Liste liniare


O lista liniara este o succesiune ordonata de elemente cu proprietatile:
- exista primul si ultimul element;
- fiecare element, cu exceptia ultimului, are un succesor
- fiecare element, cu exceptia primului, are un predecesor
lista01.jpg
Listele liniare pot fi memorate secvential, intr-un vector, sau inlantuit (cu pointeri).
Pentru a reprezenta succesiunea elementelor in cadrul unei liste se folosesc sageti catre succesorul fiecarui element:
lista02.jpgNULL
In cazul alocarii inlantuite a listelor informatia memorata in fiecare element este formata din:
- informatia utila (valoarea elementului din lista)
- informatia de legatura (adresa urmatorului element)
nod.JPG

Principalele operatii cu liste sunt:

1. Crearea listei
2. Adaugarea (inserarea) unui element in lista.
Inserarea poate fi facuta:
-la inceputul listei
-la sfarsitul listei
-in interior
3. Stergerea (extragerea) unui element din lista
Stergerea poate fi facuta:
-la inceputul listei
-la sfarsitul listei
-in interior
4. Parcurgerea listei si prelucrarea elementelor
Operatii suplimentare
5. Cautarea unui element
6. Determinarea elementelor de valoare minima/maxima
7. Selectarea elementelor care au aceeasi proprietate
8. Concatenarea a doua liste
9. Sortarea elementelor unei liste
10. Interclasarea a doua liste sortate

Liste liniare (vectori de structuri):

REZOLVARI:
P1.
distanta.png



P2.

P3.



GRILE BALCALAUREAT:
Grile liste inlantuite 2007:Bac CPP 2007
Bac_intcpp_S2_2009.pdf
Bac_intcpp_S3_2009.pdf


Stiva si Coada teorie :






A. GRILE

STIVA: Stiva.pdf

COADA: Coada.pdf


GRILE:



B. FISE DE LUCRU:

B1. Stiva si coada:

Probleme rezolvate:
1. Stiva: varianta cu functii

Flaviu Dan
Stiva cu numere pare Ionut
6. Coada:

EVALUAREA valorii unor functii folosind stiva
1. Funcţia lui Manna-Pnueli:
Manna.png
Exemplu pentru n=8:
F(8)=(r2)=F(F(10))=F(11)=...=11
a) F(10)=(r2)=F(F(12))=F(11)=11
b) F(12)=(r1)=11
c) F(11)=(r2)=F(F(13))=(r1)=F(12)=(r1)=11
Programul cpp:
2. Funcţia lui Ackermann:
Ackermann.png
Exemplu pentru m=1 şi n=1:
Ack(1,1)=(r3)=Ack(0,Ack(1,0))=Ack(0,2)=(r1)=3
a) Ack(1,0)=(r2)=Ack(0,1) =(r1)=2
Programul cpp:

OPŢIONAL
Aplicatie la coada Algoritmul lui Lee