|
|
|
ALGORITMI PENTRU PRELUCRAREA LISTELOR SIMPLU INLANTUITE
Presupunem ca informatia este o valoare intreaga
struct nod
; // informatia pentru legatura
nod *prim, *ultim, *p; // pointeri pentru exploatarea listei
int x; // pentru valoarea ce se atribuie campului cu informatii
In lista vida nodurile prim si ultim nu exista, adresa lor are valoarea NULL. Aceasta stare se testeaza prin conditia prim=ultim=NULL
Pentru testarea unei liste daca este vida se poate implementa functia operand este_vida(), care va returna 1 daca lista este vida si 0 daca lista nu este vida.
I. Initializarea listei
Se creeaza lista vida (nodurile prim si ultim nu exista, li se atribuie adresa NULL).
Se foloseste functia procedurala init(), ai carei parametri prim si ultim de tip nod, se transmit prin referinta (sunt parametri de iesire).
void init (nod *&prim, nod *&ultim)
II. Crearea listei
Algoritmul de creare a unei liste (adaugarea primului nod la lista vida)
P1. Se adauga primul nod la lista (nodul prim).
P2. Cat timp mai exista informatie, executa:
se adauga un nod la lista
III. Adaugarea primului nod la lista
Nodurile prim si ultim au aceeasi adresa.
P1. Se cere alocarea de memorie pentru nodul prim.
P2. Se scrie informatia in nodul prim.
P3. Adresei de legatura a nodului prim i se atribuie valoarea NULL.
P4. Nodului ultim i se atribuie adresa nodului prim.
Se foloseste functia procedurala adaug_nod(), ai carei parametri prim si ultim, de tip nod, se transmit prin referinta (sunt parametri de iesire).
void adaug_nod (nod *&prim, nod *&ultim)
IV. Adaugarea unui nod in lista
Se doreste adaugarea unui nod p in lista.
Se poate face:
1. in fata primului nod
P1. Se cere alocarea de memorie pentru nodul p.
P2. Se scrie informatia in nodul p.
P3. Nodul p se leaga de nodul prim.
P4. Nodului p inserat devine nod prim.
Se foloseste functia procedurala adaug_prim(), al carei parametru prim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void adauga_prim (nod *&prim)
2. dupa ultimul nod
P1. Se cere alocarea de memorie pentru nodul p.
P2. Se scrie informatia in nodul p.
P3. Nodul p este nod terminal (nu se leaga de nimic, adresa de legatura este NULL).
P4. Nodul ultim se leaga de nodul p adaugat.
P5. Nodul p inserat devine nod ultim.
Se foloseste functia procedurala adaug_prim(), al carei parametru ultim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void adauga_ultim (nod *&ultim)
3. in interiorul listei
3. a. in interiorul listei – dupa nodul cu adresa q.
P1. Se cere alocarea de memorie pentru nodul p.
P2. Se scrie informatia in nodul p.
P3. Nodul p se leaga de succesorul nodului q.
P4. Nodul q se leaga de nodul p adaugat.
P5. Daca nodul q a fost ultimul nod, nodul p inserat devine nod ultim.
Se foloseste functia procedurala adaug_dupa(), ai carei parametri de tip nod, se transmit astfel:
- adresa nodului q (nodul dupa care se face inserarea) se transmite prin valoare (este parametru de intrare);
- ultim (adresa ultimului nod) se transmite prin referinta (este parametru de intrare-iesire).
void adauga_dupa (nod *q, nod *&ultim)
3. b. in interiorul listei – inainte de nodul cu adresa q.
Trebuie ca noul nod p sa fie introdus dupa predecesorul nodului q. Deoarece nu se cunoaste predecesorul unui nod se va proceda astfel:
- se va adauga nodul p dupa nodul q;
- in nodul p se va memora informatia continuta de q;
- in nodul q se va memora noua informatie.
P1. Se cere alocarea de memorie pentru nodul p.
P2. Se copiaza informatia din nodul q in nodul p.
P3. Se scrie in nodul q informatia care trebuie adaugata in lista.
P4. Nodul p se leaga de succesorul nodului q.
P5. Nodul q se leaga de nodul p adaugat.
P6. Daca nodul q a fost ultimul nod, nodul p inserat devine nod ultim.
Se foloseste functia procedurala adaug_in_fata(), ai carei parametri de tip nod, se transmit astfel:
- adresa nodului q (nodul dupa care se face inserarea) se transmite prin valoare (este parametru de intrare);
- ultim (adresa ultimului nod) se transmite prin referinta (este parametru de intrare-iesire).
void adauga_in_fata (nod *q, nod *&ultim)
V. Parcurgerea listei
Se viziteaza secvential toate nodurile listei.
Se foloseste functia procedurala parcurge(), al carei parametru prim de tip nod se transmite prin valoare (este parametru de intrare).
void parcurge (nod *prim)
Observatie
Paralela intre parcurgerea unui vector si parcurgerea unei liste
|
|
Vectorul |
Lista |
|
Variabila folosita pentru parcurgere |
i de tip int pentru indicele elementului curent din vector |
p de tip pointer catre tipul nod al listei pentru adresa elementului curent din lista |
|
Initializarea variabilei |
i = 0 – indicele primului element din vector |
p = prim – adresa primului nod din lista |
|
Trecerea la elementul urmator |
i = i + 1 – se incrementeaza indicele |
p = p→urm – pointerului i se atribuie adresa nodului urmator |
|
Conditia de terminare |
i = = n – indicele i are prima valoare mai mare decat cea a ultimului element |
p = = NULL – adresa memorata in pointerul p este constanta NULL |
VI. Cautarea unui nod in lista
Se doreste cautarea unui nod p in lista.
Se foloseste functia operand caut(), cu tipul pointer catre tipul nod.
Precizari:
- parametrul functiei este parametrul prim, de tip nod si se transmite prin valoare (este parametru de intrare);
- valoarea locala p de tip pointer catre nod se foloseste pentru parcurgerea listei; este initializata cu adresa primului nod;
- adresa nodului gasit se memoreaza in pointerul p care va fi returnata de functie.
Se poate cauta:
6.a. Un nod care indeplineste o anumita conditie, numita conditie, exprimata printr-o expresie logica care contine cel putin un camp cu informatie din nod (valoarea conditiei este dependenta de informatia continuta in nod).
Algoritmul:
- se porneste de la primul nod;
- se parcurge lista, pana la identificarea nodului ce indeplineste conditia sau pana se termina lista.
nod *caut (nod *prim)
6.b. Un nod care se afla pe o anumita pozitie, numita poz.
Algoritmul:
- se porneste de la primul nod;
- se parcurge lista, pana cand s-au parcurs poz noduri sau pana se termina lista.
Se foloseste variabila locala nr de tip int pentru a numara pozitiile parcurse. Initial are valoarea 1.
nod *caut (nod *prim, int poz)
VII. Eliminarea unui nod din lista
Dupa eliminarea nodului din pozitia p din lista se va elibera zona de memorie ocupata.
Eliminarea unui nod se face numai daca lista nu este vida.
Se poate face:
1. eliminarea primului nod
P1. Se salveaza adresa nodului prim in pointerul q.
P2. Succesorul nodului prim devine nod prim.
P3. Se cere eliberarea zonei de memorie de la adresa memorata in pointerul q.
Se foloseste functia procedurala elimina_prim(), al carei parametru prim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void elimina_prim (nod *&prim)
2. eliminarea ultimului nod
P1. Se salveaza adresa nodului ultim in pointerul q.
P2. Se cauta predecesorul ultimului nod parcurgand lista de la primul nod pana la predecesorul nodului terminal (nodul care are ca adresa de legatura NULL).
P3. Predecesorul nodului ultim devine nod terminal (adresa lui de legatura este NULL).
P4. Predecesorul nodului ultim devine nod ultim).
P5. Se cere eliberarea zonei de memorie de la adresa memorata in pointerul q.
Se foloseste functia procedurala elimina_ultim(), al carei parametru ultim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void elimina_ultim (nod *prim, nod *&ultim)
3. eliminarea unui nod din interiorul listei
Trebuie eliminat nodul p, deci predecesorul lui p trebuie legat de succesorul sau. Deoarece nu se cunoaste predecesorul unui nod se va proceda astfel:
- in nodul p se va memora informatia continuta de succesorul sau;
- se va elimina succesorul lui p.
P1. Se salveaza adresa nodului p in pointerul q.
P2. Se copiaza in nodul p:
- informatia propriu-zisa;
- adresa nodului de legatura;
P3. Se cere eliberarea zonei de memorie de la adresa memorata in pointerul q.
P4. Daca succesorul nodului p era ultimul nod, atunci nodul p devine nod ultim.
Se foloseste functia procedurala elimina(), ai carei parametri de tip nod, se transmit astfel:
- adresa nodului p (nodul care se elimina) se transmite prin valoare (este parametru de intrare);
- ultim (adresa ultimului nod) se transmite prin referinta (este parametru de intrare-iesire).
void elimina (nod *p, nod *&ultim)
VIII. Eliberarea spatiului de memorie ocupat de lista
Se parcurge lista, incepand cu primul nod, si se elimina nod cu nod.
P1. Se initializeaza pointerul p cu adresa primului nod din lista prim (p←prim).
P2. Cat timp nu s-a parcurs toata lista (p <> NULL) executa:
P3. Se salveaza adresa nodului p in pointerul q.
P4. Se trece la succesorul nodului p (p←p→prim).
P5. Se cere eliberarea zonei de memorie de la adresa memorata in pointerul q.
Se revine la Pasul 2.
P6. Primul nod nu mai are adresa alocata (prim←NULL).
Se foloseste functia procedurala eliberare(), al carei parametru prim, de tip nod, se transmite prin referinta (este parametru de intrare-iesire).
void eliberare (nod *&ultim)
prim = NULL;}
