Liste - liste liniare alocate simplu inlantuit

O lista liniara este o colectie de n≥0 noduri, x1, x2, . ,xn, aflate intr-o relatie de ordine. Astfel, x1 este primul nod al liste, x2 este al doilea nod al liste xn este ultimul nod.

Liste liniare alocate simplu inlantuit

O astfel de lista are aceasta forma:

              ..

x1 x2 xn

Se numeste simplu inlantuit deoarece nodurile au doar un camp care pointeaza spre acelasi tip. Cu alte cuvinte, de la nodul x1 se poate ajunge la nodul x2, dar nu si invers.

Nodul xn, fiind ultimul, trebuie sa contina in campul adr valoarea 0 (sau NULL deoarece acesta nu mai trebuie sa pointeze spre nimic.

Dezavantajele listelor liniare simplu inlantuit:

1. Accesul la un nod al listei se face prin parcurgerea nodurilor care il preced. Aceasta necesita un efort de calcul.

2. Informatiile de adresa sunt prezente in cadrul fiecarui nod, deci ocupa memorie.

In urmatoarea aplicatie C++, va voi prezenta atat cum se creeaza o lista liniara alocata simplu inlantuit, cat si operatiile fundamentale ce se pot efectua asupra ei.

// Atentie! Valorile din lista sunt unice!

#include<iostream>

using namespace std;

struct nod                                // definesc structura de nod.

*p,*u,*it ; /* variabilele p si u reprezinta primul si

ultimul nod din lista. */

int N,operatie,ok,K,val ;                      // N este numarul de noduri.

void adauga ( int val )

nod *c ;

c = new nod ;

c->info = val ;

c->adr = NULL;

u->adr = c ;

u = c ;

if( p->adr == NULL ) p->adr = u ;

/* subprogramul de mai sus, adauga, va introduce un nou nod, la sfarsitul listei. Intai se verifica daca lista este goala. Daca da, se creeaza un nou nod a carei valoare este val, iar acesta este si primul si ultimul nod al listei. Altfel, utilizez un nod nou, c, cu c->inf o= val si, fiind ultimul nod al listei, nu trebuie sa pointeze spre nimic, deci c->adr=NULL. De asemenea, u devine penultimul nod, si trebuie sa pointeze spre ultimul, adica c. Astfel

u->adr=c si u=c, pentru ca u este mereu ultimul nod din lista (precum p e mereu primul). */

void adauga_k ( int val, int poz )

nod *c ;

c = new nod ;

c->info = val ;

c->adr = NULL ;

if( poz == 1 )

Analiza: TEST DE EVALUARE Matematica – Inmultirea si impartirea Document online: Analiza variantei in variabilitatea bifactoriala. testul duncan. (modelul de baza)

int i ;

for( it = p , i = 2 ; i != poz ; i++, it = it->adr ) ;

c->adr = it->adr ;

it->adr = c ;

/* Spre deosebire de subprogramul adauga, subprogramul adauga_k aduga un nod nou in lista, pe o pozitie anume (pozitia K). Daca pozitia este invalida (daca e mai mare decat numarul de noduri sau mai mica decat 1) se va afisa un mesaj de eroare, acest test fiind facut in programul principal (in main).

Daca pozitia este chiar numarul de noduri + 1, atunci problema se reduce la adaugarea nodului pe ultima pozitie in lista ( subprogramul Adauga)

Daca pozitia este chiar 1, se creeaza un nod nou, c, in care va fi memorata valoarea val, si care va pointa spre p (cu alte cuvinte, c trebuie sa fie pus in spatele lui p) iar p va deveni c, intrucat p e mereu primul nod din lista.

In cazul in care pozitia apartine intervalului (1,N+1) folosesc o variabila de tip nod, it, si parcurg lista, pana ce it va avea pozitia k-1.

POZ:          k-2 k-1 k k+1

it

c

Astfel, nodul c trebuie sa pointeze spre nodul de pe pozitia K, deci nodul de dupa it, acesta fiind de fapt it->adr. Nodul it trebuie sa pointeze spre nodul c.

int cauta ( int val )

/* subprogramul de mai sus, cauta, parcurge lista si returneaza 1 in cazul in care a gasit valoarea cautata, sau 0 in caz contrar */

void sterge ( int val )

for( a = p, b = p->adr ; b ; a = a->adr, b = b->adr )

if( b->info == val )

a->adr = b->adr ;

delete b ;

b = NULL ;

return ;

}

/*subprogramul de mai sus are rolul de a sterge un nod cu o anumita valoare.

In cazul in care nodul era tocmai pe prima pozitie in lista, se utilizeaza urmatorul rationament: pentru ca primul nod trebuie sa fie sters, al doilea nod va deveni primul, insa pentru ca nimic nu pointeaza spre primul nod, trebuie mai intai sa il salvam intr-o alta variabila de tip nod ( a=p; ). Apoi, al doilea devine primul (p=p->adr;). De abia acum se poate sterge primul nod, adica a (pentru ca p este al doilea). Astfel, a fiind sters, al doilea nod a devenit primul. Un caz aparte este acela in care lista are un singur element, si acesta trebuie sters, deci p va deveni egal cu u si ambele vor avea valoarea NULL.

Daca nodul cautat nu e pe prima pozitie, este parcursa lista, folosind doua noduri auxiliare, a si b, pana cand a va fi in spatele nodului care trebuie sters, iar b va fi tocmai nodul care trebuie sters. Daca nodul care trebuie sters este tocmai ultimul, se utilizeaza un rationament asemanator celui de mai sus: u devine penultimul, adica a, b este sters si adresa lui u va fi NULL. Daca nodul nu este ultimul, a va pointa spre nodul urmator lui b, adica spre b->adr, iar b este sters. */

void sterge_k ( int poz )

for( a = p , b = p->adr, i = 2 ; i != poz ; a = a->adr, b = b->adr, i++ ) ;

if( b == u )

a->adr = b->adr;

delete b ;

b = NULL ;

/* subprogramul sterge_k este foarte asemanator cu subprogramul sterge, pentru ca in loc de a cauta o valoare, se cauta o pozitie. Asadar, sunt exact aceleasi cazuri precum in cazul subprogramului sterge */

void afisare ()

/* subprogramul afisare parcurge lista si afiseaza toate elementele ei */

int main()

break;

case 2 :

cout<<'Introduceti nodul : ' ;

cin>>val;

cout<<'Introducei pozitia : ' ;

cin>>K;

if( K < 1 || K > N+1 ) /* se testeaza validitatea pozitiei si se afiseaza un mesaj de eroare in caz contrar */

if( cauta(val) )

cout<<'Nodul se afla deja in listan';

else

break;

case 3 :

cout<<'Introduceti nodul : ' ;

cin>>val ;

if( cauta(val) )

cout<<'Nodul se afla in lista!n';

else

cout<<'Nodul nu se afla in lista!n';

break ;

case 4 :

cout<<'Introduceti nodul : ' ;

cin>>val ;

if( N == 0 ) /* in cazul in care lista este deja goala, nu poate fi folosit subprogramul sterge */

ok = 0 ;

sterge(val) ;

if( !ok ) /* variabila ok testeaza daca a fost sters nodul cerut si afiseaza un mesaj de eroare in caz contrar */

cout<<'Nodul nu se afla in lista!n';

else

break ;

case 5 :

cout<<'Introduceti pozitia : ' ;

cin>>K ;

if( N == 0 )

if( K < 1 || K > N )

sterge_k(K);

N--;

cout<<'Nodul a fost sters!n';

break ;

case 6 :

if( N )

afisare();

else

cout<<'Lista este goala!n';

break ;

case 0 :

cout<<'Iesiren';

break ;

default :

cout<<'Comanda necunoscuta!n'; /* in cazul in care s-a citit de la tastatura o comanda care nu se afla in meniul principal, se afiseaza un mesaj de eroare */

break;

}

cout<<'nn';

}

return 0 ;