Liste simplu inlantuite ordonate

Cand folosim o lista simplu inlantuita ordonata?

Folosim o lista inlantuita ordonata atunci cand avem definita o relatie de ordine pe multimea elementelor listei; cu alte cuvinte atunci cand nodurile trebuiesc inlantuite dupa un anumit criteriu de ordine (de exemplu crescator sau descrescator dupa un anumit camp).

Vom lua cazul unui dictionar implementat cu lista simplu inlantuita. Structura unui nod va fi:

typedef struct  elemnod

void main()

Crearea unui nou nod o vom face cel mai probabil intr o functie separata, urmand ca apoi sa introducem nodul creat la locul sau in lista. Sunt exemplificate in imagine operatiile efectuate; urmariti codul si in paralel reprezentarea grafica corespunzatore (bucata de cod are aceeasi culoare cu reprezentarea grafica a efectului produs)

nod *creare_nod(char *cuv, char *expl)

Adaugarea intr-o lista simplu inlantuita ordonata

Daca dorim ca nodurile listei sa fie parcurse dupa un anumit criteriu (de exemplu crescator dupa campul cuvant , trebuie ca introducerea unui nou nod in lista sa se faca astfel incat sa nu se strice ordinea listei (altfel spus, il vom introduce la locul lui); pentru exemplul considerat, vom introduce noul nod inaintea primului nod cu campul cuvant mai mare decat campul sau cuvant

Adaugarea la inceputul listei

Daca nodul nou are campul cuvant mai mic decat campul cuvant al primului nod

nod *adaug_incep(nod *nou)

Adaugarea la sfarsitul listei

void adaug_sfs(nod *nou, nod *p)

Adaugarea dupa nodul p al listei

void adaug_mijl(nod *nou, nod *p)

Observatie: cele 2 functii, adaug_sfs si adaug_mijl difera doar la legatura 1, care am vazut ca se poate scrie la fel (urmariti comentariile din adaug_sfs). Rezulta ca putem scrie o singura functie pentru adaugarea la sfarsit si in interiorul listei; mai exact, functia pentru adaugare dupa nodul p din interiorul listei acopera si cazul cand nodul p este ultimul.

Stergerea dintr-o lista simplu inlantuita ordonata

Daca dorim sa eliminam un nod din lista, memoria pe care acesta o ocupa va trebui eliberata, pentru a fi folosita la adaugarea de alte noduri; daca nu o eliberam explicit cu functia free, ea va ramane marcata ca fiind ocupata pe durata executiei programului si nu va putea fi folosita. De aceea, inainte de a reface legaturile pentru ca nodul de sters sa fie eliminat din lista, adresa lui va fi memorata intr-o varialbila pentru a fi eliberata ulterior zona de memorie dedicata lui.

Stergerea primului nod

nod sterg_incep(nod *p)

Stergerea ultimului nod

Daca nu avem un pointer care sa ne retina adresa ultimului nod, parcurgem lista si ne oprim inaintea ultimului nod

nod sterg_sfs(nod *p)

Stergerea nodului de dupa nodul p

Parcurgem lista si ne oprim inaintea nodului pe care vrem sa il stergem, adica la nodul p

nod sterg_incep(nod *p)

Observatie: cele 2 functii, sterg_sfs si sterg_mijl difera doar la legatura 2, care am vazut ca se poate scrie la fel (urmariti comentariile din sterg_sfs). Rezulta ca putem scrie o singura functie pentru stergerea la sfarsit si in interiorul listei; mai exact, functia pentru stergere a nodului de dupa nodul p din interioru listei acopera si cazul cand acesta este ultimul.

Exemplu cu lista simplu inlantuita ordonata

Problema rezolvata efectueaza operatiile de adaugare, stergere si cautare intr-o lista simplu inlantuita ordonata. Adaugarea se va face astfel incat lista sa ramana ordonata.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

/* tipul pentru nodul lista */

typedef struct elem

nod;

/* cauta in lista indicata de p nodul cu campul info = inf si

returneaza pointerul catre acel nod, daca nodul cautat nu exista returneaza NULL */

nod *caut(nod *p, float inf)

Functia listez parcurge lista si pentru fiecare nod

afiseaza informatia memorata. */

void listez(nod *p)

/* Functia sterg elimina din lista (indicata de pointerul

p) nodul ce are campul info egal cu argumentul inf */

nod *sterg(nod *radacina, float inf)

else

if (radacina->info==inf)

else

else // nodul cautat nu exista

printf('Eroare: identificatorul %f nu apare in listan', inf);

return radacina;

}

}

/*Functia introduc insereaza un nod in lista ordonata,

Functia returneaza pointerul catre inceputul listei modificate */

nod * introduc(nod *radacina, float infonou)

nou->info=infonou; /* se salveaza infonou in nodul nou */

nou->urm=NULL;

/* nodul nou este inserat in lista ordonata astfel incat ea ramane ordonata

si dupa inserare. Lista este parcursa cautandu-se primul nod avand

campul info mai mare sau egal cu info */

if (radacina==NULL) // lista vida

radacina=nou;

else

if (p->info>infonou)

else

return radacina;

/* Functia main afiseaza meniul programului,citeste comanda */

/* si apeleaza functia corespunzatoare */

void main(void)

case 'c':

case 's':

case 'l':

case 't':

return;

default:

printf('Eroare : Comanda inexistentan');

}

}

Liste simplu inlantuite circulare

O lista simplu inlantuita va fi circulara daca ultimul ei nod (campul sau urm mai exact) va pointa spre primul sau nod. Putem sa ne reprezentam astfel acest tip particular de lista:

Lista fiind circulara, nu mai are un prim nod si un ultim nod (de regula, dar nu neaparat, noi hotaram cum implementam); vom avea un nod curent (il vom boteza crt). Acest nod poate sa aiba diverse semnificatii, in functie de problema.

Aplicatii cu liste simplu inlantuite

Coada (FIFO)

Coada este o lista simplu inlantuita (poate sa fie si circulara) in care stergerea se face la inceput si adaugare se face doar la sfarsit (se zice ca este de tip FIFO = First In Firs Out).

Pentru implementarea cu lista simplu inlantuita vom folosi 2 pointeri, unul pentru primul nod (de aici vom sterge) si unul pentru ultimul nod (aici vom face adaugarea).

Daca implemetam coada circular,  in pointerul crt vom stoca adresa ultimului element introdus; astfel, adaugarea unui nod nou se va face dupa nodul (*crt) crt pointand apoi spre nodul nou introdus). De sters vom sterge nodul de dupa crt, deoarece acesta este nodul introdus cel mai "devreme".

Stiva (LIFO)

Stiva este o lista simplu inlantuita (poate fi si circulara) in care atat stergerea cat si adaugarea se fac la sfarsitul listei (este de tip LIFO=Last In First Out), deci vom avea nevoie de un singur pointer pentru referirea la lista.

Probleme propuse

Problema 1: rularea exemplului

Rulati programul din exemplu.

Problema 2: implemetarea unei cozi cu lista simplu inlantuita

Definim o coada de asteptare pentru clienti care asteapta sa li se monteze telefon. O noua cerere va fi trecuta la sfarsitul cozii; cererile se vor solutiona in ordinea sosirii si vor fi scoase din coada de asteptare (deci stergerea se va face la inceput). O cerere contine : numele titularului, adresa de instalare a postului telefonic si data cererii; acestea vor fi alocate dinamic.

Programul va permite si retragerea unei anumite cereri (urmata de stergerea nodului respectiv), precum si actualizarea unei cereri (daca titularul a schimbat adresa), aceasta actualizare neafectand pozitia titularului in coada de asteptare.

Implementati coada cu lista simplu inlantuita, retinand in 2 pointeri adresele primului si ultimului element;

Problema 3: functii recursive pentru liste

Rescrieti functiile adaug si sterg ale programul de mai sus in maniera recursiva.

Probleme extra:

1. Modificati programul 2 pentru a face lista circulara, retinand adresa unui singur nod ca referinta la lista.

2. Simulati apelul recursiv al unei functii (factorial, Akerman, etc.) folosind o stiva.