Software de Sistem
5.3 EXCLUDEREA MUTUALA FARA ASTEPTARE ACTIVA Metodele precedente, inclusiv cele care rezolva...
Acest curs prezinta Algoritmi si Tehnici de Programare Avansata. Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).
Arhiva contine 1 fisier doc de 16 pagini .
Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.
Fratele cel mare te iubeste, acest download este gratuit. Yupyy!
Domeniu: Calculatoare
Tabloul = structura de date de acelasi tip care ocupa o zona continua de memorie.
* in limbajul JAVA acelasi tip poate fi si clasa Object
int tab[]=new int[10];
* pt String trebuie utilizata conversia cast
AVANTAJE:
- accesul rapid la elementele tabloului prin index[]
DEZAVANTAJE:
-manipularea (adaugare,inserare,stergere) se realizeaza prin deplasarea elementelor sau modificarea structurii.
Lista = set de noduri, intre noduri existand legatura.
Legaturile pot fi unidirectionale si bidirectionale.
* informatia stocata in cadrul unui nod poate sa aiba orice natura, de asemenea in cadrul unui nod exista obligatoriu legatura catre nodul urmator = referinta
* in cazul legaturii bidirectionale exista referinta si catre nodul precedent
AVANTAJE:
* nu necesita zone continue de memorie
* alocarea dinamica a unui nod (new) distribuie nodul intr-o zona libera.
* in limbajul C++ stergerea nodului dintr-o lista presupune si invocarea metodei delete care bifeaza acea zona ca fiind libera
* in JAVA nu exista operatia delete, eliminarea nodurilor sterse (bifarea nodurilor sterse ca fiind libere) fancandu-se automat.
* manipulare facila a nodurilor (inserare, adaugare, stergere)
DEZAVANTAJE:
* accesul dificil la elementele listei
* de obicei exista o referinta catre capul listei (t)
* accesul catre alte elemente facandu-se secvential, lista se va parcurge de la t pana la final.
In functie de legatura dintre noduri:
1) liste simplu inlantuite (legatura intr-un sens)
2) liste dublu inlantuite (legatura in ambele sensuri)
O lista se poate termina cu legatura catre un nod special sau referinta catre "null" sau catre primul nod (t) => liste circulare.
Nod.java
Structura.java
Testare.java
class Nod {
Object val;
Nod urmator;
// Nod precedent;
public Nod (Object val) {
this.val = val;
urmator = null;
precedent = null;
} //constructor
//fiind vorba de campuri publice nu e necesar sa definim metodele specifice (get/set)
}
Fie urmatoarea lista:
class Nod {
int val;
Nor urmator;
public Nod (public Nod) {
this.val=val;
urmator=null;
}
}
Testare.java
Nod t = new Nod(3);
t.urmator = new Nod(5);
t.urmator.urmator = new Nod(7);
t.urmator.urmator.urmator = new Nod(9);
* este esential sa cunoastem modul in care incheie lista deoarece parcurgerea secventiala trebuie sa se incheie.
* in cazul aceste "null" e conditia de incheiere.
Parcurgerea secventiala:
Nod x=t;
//x are rolul variabilei increment cauta i din
//for (int i=0;i<N;i++)
//pentru parcurgere
while (x != null) {
x=x.urmator; //i++
}
Inserarea pentru o lista simpla inlantuita:
Nod z = new Nod(9);
z.urmator = t.urmator.urmator;
t.urmator.urmator = z;
Obs: la operatia de inserare intr-o lista se conecteaza mai intai elementul nou creat.
Problema:
Fie o lista de noduri de dimensiune data. Lista reprezinta memoria disponibila pentru program. Se vor implementa operatii de creare, inserare, stergere, pt o lista folosind nodurile din lista memoriei.
Algoritmi si Tehnici de Programare Avansata: Tablouri, liste, cozi, algoritmi, arbori, sortari