Liceul Teoretic "Henri Coanda"

CRAIOVA

PROIECT DE ATESTAT

LISTE LINIARE SIMPLU INLANTUITE

1. NOTIUNI INTRODUCTIVE

DEFINITIE O lista liniara simplu inlantuita este o lista liniara care respecta urmatoarele reguli:

Fiecare element al listei memoreaza o informatie de acelasi tip;

Oricare element din interiorul listei are un succesor;

Exista un element pentru care nu exista succesor ,pe care-l vom numi ultimul element;

Exista un element al listei care nu are predecesor si pe care-l vom numi primul element;

Listele implementate dinamic aduc urmatoarele avantaje:

Segmentul de date al memoriei este degrevat de memorarea elementelor listei,ele fiind retinute in zona HEAP a memoriei;

Listele pot avea dimensiune variabila in functie de necesitati;

Spatiul de memorie ocupat de elementele listei este alocat sau eliberat in functie de necesitati;

Lista liniara simplu inlantuita se reprezinta astfel:

Scopul utilizarii listelor este de a economisi spatiu de memorie, motiv pentru care se foloseste alocarea dinamica in locul celei statice (utilizata in cazul tablourilor).

Accesul la un element al listei se poate face doar secvential, parcurgand elementele aflate inaintea sa in inlantuire.

In general, asupra unei liste se pot face operatii de insertie/adaugare de noduri, stergere de noduri si parcurgerea nodurilor.

Pentru a putea folosi o lista, este necesar sa fie retinuta adresa de inceput a listei (adresa primului nod). Ne vom referi in continuare la aceasta adresa prin pointerul prim.

1.2 OPERATII SPECIFICE LISTELOR LINIARE SIMPLU INLANTUITE

1.2.1 CREAREA LISTEI SIMPLU INLANTUITE:

Crearea listei se poate realiza prin urmatorii pasi:

P1: plecam de la o lista vida,deci primul element este 0;

P2: alocam spatiu pentru un element nou:p1 =new(nod);

P3: citim informatia aferenta noului element:

cin>>p->info_s;

P5: se refac legaturile: u1=c1;

Afisarea listei se realizeaza folosind urmatorul subprogram:

Nodul curent ia adresa primului nod: c1=p1;

Cat timp adresa nodului curent este diferita de 0 (c!=0), afisam informatia nodului curent : cout<<c1>info_s<<' ';

1.2.3. INSERAREA UNUI ELEMENT IN LISTA:

1.2.3.1 INSERAREA LA INCEPUTUL LISTEI LINIARE SIMPLU INLANTUITE

Pasii:

P1: se aloca spatiu: c=new(nod);

P2: se completeaza campul adresa : c->adr_urm=Adaug();

P3: se realizeaza legatura cu primul element:c->info=nr;

P4: se muta primul termen, pe noul termen si se returneaza, in cazul in care nu adaugam nimik se afisaza valoarea 0;

1.2.3.2 INSERAREA UNUI NOD INAINTEA ALTUIA DE INFORMATIA DATA

P1: Se citeste un nod oarecare, k;

P2: Daca informatia primului nod coincide cu nodul pe care l-am adaugat de la tastatura, atunci se afisaza informatia nodului adaugat: d->info_s=kk;

Nodul urmator va lua valoarea primului nod: d->rmator=p1; p1=d;

1.2.3.3 INSERAREA UNUI NOD DUPA UN ALTUL DE INFORMATIE DATA

Se da nodul dupa care dorim sa adaugam un alt nod k;

Cat timp informatia nodului current este diferita de cea a nodului adaugat (c->info_s!=k) si nodul e diferit de 0, nodul curent ia adresa nodului urmator : c1=c1->urm;

Daca nodul curent este diferit de 0, atunci nu exista nodul cu informatia k, in caz contrar se da informatia nodului adaugat;

1.2.3.4. INSERAREA LA SFARSITUL LISTEI LINIARE SIMPLU INLANTUITA

nou

PASII:

- P1: ne deplasam cu un pointer curent pe ultimul element al listei;

- P2: alocam spatiu pentru noul element;

- P3: completam campul info;

- P4: in campul urmator punem 0 ;

- P5: legam ultimul element al listei de noul element;

1.2.3.6. ELIMINAREA UNUI ELEMENT DIN LISTA

Atunci cand stergem un element dintr-o lista trebuie sa fim atenti la urmatoarele aspecte

Lista sa nu fie vida, caz in care nu avem ce sterge

Sa refacem corect legaturile astfel incat lista sa ramana simplu inlantuita si sa poata fi parcursa secvential;

Sa eliberam zona de memorie din HEAP ocupata de variabila dinamica eliminata din lista ; in caz ca omitem acest lucru vom ocupa spatiu de memorie nejustificat fara a mai avea acces la acele locatii;

Sa returnam corect adresa primului element daca acesta a fost cumva sters.

Observatii:

In situatia stergerii unui nod din lista apar de asemenea cele trei situatii anterior descrise (nod de la inceputul, de la sfarsitul sau din mijlocul listei).

Principala grija a programatorului in cazul stergerii unui nod trebuie sa fie eliberarea spatiului de memorie alocat nodului care a fost sters si mentinerea integritatii listei (prin stergerea nodului, sa nu se 'rupa' lista).

1.2.3.7. ELIMINAREA PRIMULUI ELEMENT DIN LISTA

Stergerea primului element presupune:

P1: memorarea intr-o alta variabila(p)a adresei primului element;

P2: actualizarea variabilei p1 cu adresa p1^.urm;

P3: eliberarea variabilei dinamice avand adresa data de variabila p;

In cazul in are este selectat primul nod si se doreste stergerea informatiei dinaintea primului nod va fi afisat

ELIMINAREA DE LA SFARSITUL LISTEI

PASII:

P1: parcurgerea listei pana la penultimul nod si retinerea intr-o variabila a adresei ultimului element;

P2: penultimul element va fi urmat de 0;

P3: eliberarea spatiului din HEAP ocupat de ultimul element al listei initiale;

1.2.3.9. STERGEREA UNUI NOD DE INFORMATIE DATA

P1: Se da un nod k;

P2: Daca informatia primului nod este egala cu nodul k, stergem primul nod, spatial ocupat de primul nod va fi eliberat;

P3: Cat timp informatia nodului urmator este diferita de k, pentru nodul care va fi sters, informatia de adresa a predecesorului va retine adresa nodului successor; Memoria ocupata de nodul care urmeaza a fi sters este eliberata;

1.2.4.0. STERGEREA UNUI NOD DUPA INFORMATIA DATA DE LA TASTATURA

P1: Se da un nod k;

P2: Cat timp informatia nodului este diferita de k, se trece la nodul urmator;

P3: Nodul urmator ia adresa urmatoare si se sterge;

2. APLICATIE

Se se creeze o lista simplu inlantuita si sa se afiseze. Sa se efectueze si urmatoarele operatii ale listei simplu inlantuite: cautarea unui element: adaugarea inaintea unui element, la sfrasitul listei in interiorul listei si a unui element dat, stregerea primului element,

Mod de lucru:

P1: se utilizeaza o procedura de creare a listei

P2: se utilizeaza o procedura de afisare a listei

P3: se creaza cate o procedura pentru fiecare operatie a listei simplu inlantuite

Aplicatia realizeaza urmatoarele:

BIBLIOGRAFIE

TUDOR, SORIN, VLAD, HUTANU, MANUAL CLASA A XI-A

Programere in limbajul C++ pentru liceu-Marinel

Serban,Emanuela Cerchez