Algoritmi și tehnici de programare avansată

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.