0

Balanescu Cristian - Teorie Stiva

Stiva - o lista liniara simplu inlantuita care se construieste pe principiul "ultimul intrat, primul iesit".
-are un singur capat care se numeste varful stivei, singurele operatii admise sunt adaugarea unui nod in varful stivei si extragerea unui nod din varful stivei.
O stiva stimuleaza asezarea unor obiecte unul peste celalalt (cum ar fi, de exemplu, farfurii, caramizi, etc.) si adaugarea unor noi obiecte nu se poate face decat deasupra celorlalte, iar de luat nu se pot lua obiecte decat de deasupra (pentru ca, altfel, se "darama" stiva).

Adaugarea in stiva(elem, V, n)
if v[n-1] = n-1
return "stiva plina"
v[v[n-1]] = elem
v[n-1] = v[n-1] + 1
return "succes"

Stergerea din stiva(V, n)
if v[n-1] = 0
return "stiva goala"
elem = v[v[n-1] - 1]
v[n-1] = v[n-1] + 1
return elem;

Problema: Într-o stivă ce memorează numere întregi se introduc, în ordine,următoarele numere:
1,2,3,4,5,6,7. Câte numere trebuie să eliminăm din stivă astfel ca în vârful stivei să se găsească
numărul 5?

a. 5 b. 2 c. 3 d. 4

7
6
5
4
3
2
1
Pentru a avea în vârful stivei valoarea 5 trebuie să eliminăm maxim două valori,strict două valori şi anume (7,6).

0

Verba Roxana - teorie

Cazuri particulare de liste:
• Coada
• Stiva

Coada- o lista liniara simplu inlantuita care se construieste pe principiul “ primul intrat, primul iesit”

Coada are doua capete :
• Prin capatul din dreapta introducem noduri in coada
• Prin capatul din stanga extragem noduri.

Coada este mult utilizata in sistemele de operare ( in rutinele de alocare a resurselor, un exemplu foarte cunoscut fiind coada de asteptare a documentelor ce asteapta la tiparit atunci cand se da comanda de tiparire la o imprimanta pentru mai multe documente) sau in programe de simulare.
O coada in care adaugarile si eliminarile de elemente se po face numai la cele doua capete ale listei se numeste coada completa. Structura statica adecvata memorarii unei cozi complete este coada rulanta.

Adaugarea in coada(elem, V, n)
v[n-2] = (v[n-2] + 1) mod (n-2)
if v[n-1] = v[n-2]
return "coada plina"
V[V[n-1]] = elem
return "succes"

Stergerea din coada(V,n)
if v[n-1] = v[n-2]
return "coada goala"
v[n-1] = (v[n-1] + 1) mod (n-2)
return V[V[n-1]]

Problema: o garnitura de tren are in componenta o locomotiva si sase vagoane. locomotiva este numerotata cu 1 si vagoanele in continuare. Sa se adauge dupa primul vagon, vagonul de dormit care se va nota cu 11.

int main ()
{struct nod { int x; nod*urm;}
*p, *u, *l, *p1, *u1;
p=new nod;
p->x=1;
p=u;
p->urm=NULL;
for(i==2;i<=7;i++) {l=new nod; l->x=i;
l1->urm=l;
u=l;
l1->urm=NULL;}

l=p;
p1=new nod;
p1=l;
p=p->urm;
u1=new nod;
u1=p;
p1->urm=u1;
p=p->urm;
l=new nod;
l->x=11;
u1->urm=l;
u1=l;
u1->urm=NULL:
u1->urm=p;}

return 0;}


0

Serban Cristina. Variante liste

Varianta 1


1. Se consideră o coadă în care iniţial au fost introduse, în această ordine, elementele cu valorile 1 şi 2:
. Se notează cu AD(x) operaţia prin care se adaugă elementul cu valoarea x in coada
şi cu EL operaţia prin care se elimină un element din coadă. Câte
elemente va conţine coada în urma executării secvenţei de operaţii:
AD(4);EL;EL;AD(5);EL;AD(3)?

a. 3 b. 1 c. 2 d. 5


Raspunsul este c.2 deoarece doar doua valori au ramas dupa eliminare.



Varianta 2

3. Se consideră o stivă în care iniţial au fost introduse, în această ordine,
elementele cu valorile 1, 2 şi 3, ca în figura alăturată. Se notează cu
AD(x) operaţia prin care se adaugă elementul cu valoarea x în vârful
stivei şi cu EL operaţia prin care se elimină elementul din vârful stivei.
Care sunt valorile ultimelor două elemente eliminate din stivă în urma
executării secvenţei de operaţii: AD(4);EL;EL;AD(5);EL;EL?

Valorile ultimelor doua elemente eliminate din stiva in urma executarii secventei de operatii sunt 2 si 5.


Varianta 6


Se consideră o listă liniară simplu înlănţuită
alocată dinamic, cu cel puţin două
elemente. Fiecare element al listei reţine în
câmpul urm adresa elementului următor din
listă sau NULL dacă nu există un element
următor.
while (...)
p=p->urm;
delete p->urm; free (p->urm);
p->urm=NULL;
Ştiind că variabila p reţine adresa primului element din listă, care dintre expresiile următoare
poate înlocui punctele de suspensie în secvenţa de instrucţiuni de mai sus astfel încât, în
urma executării acesteia, să fie eliminat ultimul element al listei?

a. p->urm->urm!=NULL b. p->urm!=NULL
c. p!=NULL d. p->urm->urm==NULL

Raspunsul este c pt ca p nu trebuie sa fie nul ca sa se poate executa programul.
0

Suciu Lorena

Liste circulare simplu inlantuite





Def : O lista circulara simplu inlantuita este o lista in care ultimul element contine campul ce adreseaza elementul urmator, adresa primului element.


O lista circulara poate fi asimetrica sau simetrica dupa cum elementele listei sunt dublete, respectiv triplete, adica contin un pointer sau doi pointeri.


Listele circulare se mai numesc si liste inchise, celelalte purtand numele de liste deschise.


La operatiile specifice listelor circulare trebuie sa tinem cont, in plus, si de legaturile existente intre ultimul nod si primul nod.










{


p=new mod;


cin>>p->info;


p=u;


u->urm=p;


l=new mod;


cin>>l->info;


u->urm=l;


u=l;


u->urm=p;


l=p;


cout<info;


while(l->urm!=p;)


{l=l->urm;


cout<info;}


cout<info;


return 0;}




0

Babutia Ruth


























Structurii de date alocate dinamic
Structurile da date alocate dinamic sunt structuri ale caror componente se aloca in timpul executarii programului.
Tipuri de strcuturii dinamice
-liniare
-arborescente
-retea
Structurile de date liniare se numesc:
- liste: liste liniare simplu inlantuite
liste liniare dublu inlantuite
Operatiile cele mai inportante ale unei liste sunt:
- crearea unei liste
- adaugarea sau inserarea unui nod in lista
- stergerea sau eliminarea unui nod din lista
- parcurgerea unei liste.

Structura unui nod este:
struct nod
{
tip informatibila;
nod *urm;
}
*p, *l, *u;

Crearea, parcurgerea, si afisarea unei liste:
int main( )
{ struct nod
{ int x;
nod *urm;} *p, *u, *l, *q;
int n, i, y;
cout<<"n=";cin>>n;
p=new nod;
cout<<" citeste o valoare:"; cin>>p->x;
u=p;
u->urm=NULL;
for(i=2;i<=n;i++) { l=new nod; cin>>l->x;
u->urm=l;
u=l;
u->urm=NULL;
l=p;
k=0;
whike( l!=NULL)
{ if(l->%2==0)
k++;
l=l->urm;}
{ cout<x<<" "; l=l->urm; }
return o;}

Adaugarea unui nod in lista:
l=new nod;
l->urm=p;
p=l;
p->x=p->urm->x;


Adăugarea la sfârşitul listei



Dacă dorim ca nodurile listei să fie parcurse după un anumit criteriu (de exemplu crescător după câmpul cuvant), trebuie ca introducerea unui nou nod în listă să se facă astfel încât să nu se strice ordinea listei (altfel spus, îl vom introduce la locul lui); pentru exemplul considerat, vom introduce noul nod înaintea primului nod cu câmpul cuvant mai mare decât câmpul său cuvant.



Adăugarea la începutul listei





Adăugarea la sfârşitul listei




Adăugarea după nodul p al listei





Ştergerea dintr-o listă simplu înlănţuită ordonată


Dacă dorim să eliminăm un nod din listă, memoria pe care acesta o ocupa va trebui eliberată, pentru a fi folosită la adăugarea de alte noduri; dacă nu o eliberăm explicit cu funcţia free, ea va rămâne marcată ca fiind ocupată pe durata execuţiei programului şi nu va putea fi folosită. De aceea, înainte de a reface legăturile pentru ca nodul de şters să fie eliminat din listă, adresa lui va fi memorată într-o varialbilă pentru a fi eliberată ulterior zona de memorie dedicată lui.





Ştergerea ultimului nod







Ştergerea nodului de după nodul p









0

Liste liniare simplu inlantuite.





O lista liniara este o segventa finita de n elemente (componente) de acelasi tip de nod 1,nod 2,...nod n numite si noduri aflate intr-o relatie de ordine.

In cadrul unei liste sunt puse in evidenta :
- un element numit primul element;
- un element numit ultimul element;
- cate un singur element succesor pentru fiecare element al listei (cu exceptia ultimului element, care nu are succesor);
- cate un singur element predecesor pentru fiecare element al listei (cu exceptia primului element, care nu are predecesor);


Pentru a pune in evidenta succesiunea nodurilor, o lista o putem reprezenta astfel:



Componentele listei pot fi date elementare sau date structurate.

Operatiile cele mai importante definite pe liste sunt :
- crearea unei liste;
-parcugerea unei liste;
-adaugarea (inserarea) unui nou nod in lista;
- stergerea (eliminarea) unui nod din lista;
-afisarea listei.

Stergerea unui element dintr-un anumit loc din lista presupune deplasarea elementelor finale ale listei pentru a fi ocupat locul elementului ce se elimina.

void stergere(int val)

{Nod *c,*a;

c=prim;

if(prim->info==val)

{a=prim;

prim=prim->urm;

delete a;}

else

{while(c->urm->info!=val )

c=c->urm;

a=c->urm;

c->urm=a->urm;

if(a==ultim) ultim=c;

delete a;} }



Adaugarea (inserarea) unui nod in lista se poate face:
- in fata primului nod;
- in interiorul listei;
- dupa ultimul nod din lista.

Adaugarea (inserarea) in fata primului nod:

Acesta este cazul cel mai simplu: trebuie doar alocat elementul, legat de primul element din lista si repozitionarea capului listei:


l=new nod;
l->urm=p;
p=l;
p->x=p->urm->x;


Adaugarea (inserarea) unui nod in interiorul listei:
-se parcurge lista pana ce identificam nodul din lista dupa care se fae inserarea. Cautarea nodului se poate face in functie de informatia utila, fie in functie de numarul de ordine al nodului din lista.

q=new nod;
q->urm=l->urm;
l->urm=q;
q->x=q->urm->x;

Adaugarea (inserarea) la sfarsitul listei
In acest caz trebuie intai parcursa lista si dupa aceea adaugat elementul si legat de restul listei. De asemenea, trebuie avut in vedere cazul in care lista este vida.

void InserareSfarsit(Element* &cap, Date val)
{
// Alocare si initializare nod
Element *elem = new Element;
elem->valoare = val;
elem->urmator = NULL;
// daca avem lista vida
if (cap == NULL)
// doar modificam capul listei
cap = elem;
else
{
// parcurgem lista pana la ultimul nod
Element *nod = cap;
while (nod->urmator != NULL)
nod = nod->urmator;
// adaugam elementul nou in lista
nod->urmator = elem;
}
}













0

Participanti

Babutia Ruth
Balanescu Cristian
Suciu Lorena
Serban Cristina
Verba Roxana
 
Copyright © Grupa1info