Continutul Practicii Temaclasa Lista Simplu Inlantuita

Ministerul Educaţiei şi Cercetării a României Universitatea „Dunărea de Jos” din Galaţi Facultatea de Stiinţe Matematică-Informatică

Proiect de practica:

”Clasa lista simplu inlantuita”

Realizat de: Stanila Liudmila Coordonat de: Manea Ecaterina

1

Subiectul 3

Clasa lista simplu inlantuita : -

-

-

campuri membre ; constructuri ; metode pentru obtinerea valorilor campurilor ; modificarea valorilor campurilor; metode pentru adaugarea unui element la inceputul listei; adaugarea unui element la sfarsitul listei; cautarea unui element in lista; inserarea unui element in lista inaintea unui element dat; inserarea unui element in lista dupa un element dat; stergerea primului element din lista; stergerea ultimului element din lista; stergerea unui element din interiorul listei; modificarea unui element al listei; afisarea informatiei dintr-un element al listei; parcurgerea si afisarea listei.

2

Structurile dinamice de date reprezinta date structurate ale caror componente se aloca in mod dinamic. Alocarea dinamica a componentelor structurii impune un mecanism prin care o noua componenta aparuta este legata in succesiunea logica de corpul structurii deja format pana atunci. Rezulta ca fiecare componenta, pe langa informatia propriu-zisa pe care o detine, contine si o informatie de legatura cu componenta de care se leaga logic in succesiune. Informatia de legatura va fi adresa componentei spre care se realizeaza succesiunea logica, iar mecanismul se mai numeste alocare inlantuita dupa adrese. In functie de tipul inlantuirii realizate intre componente exista urmatoarele tipuri de organizari: - structuri liniare/ liste (deschise sau inchise – circulare ); - structuri arborescendente; - structuri retea. Structura liniara se mai numeste si lista. Lista este o multime finita si ordonata de elemente de acelasi tip. Elementele listei se numesc noduri. Modul de inlantuire prin adrese a componentelor se poate face: - intr-un singur sens, generandu-se lista simplu-inlantuita; - in ambele sensuri, generandu-se lista dublu-inlantuita. Folosim o listă înlănţuită ordonată atunci când nodurile trebuiesc înlănţuite după un anumit criteriu de ordine (de exemplu crescător sau descrescător după un anumit câmp). O componenta a unei liste simplu-inlantuite se declara ca o data structurata de tip articol, formata din doua campuri : informatia propriu-zisa si informatia de legatura. Informatia propriu-zisa poate fi, la randul ei structurata sau nu. Variabila adresa necesara a fi definita pentru alocarea dinamica a unei componente va avea ca tip de baza tipul structurii componentei (tipul articol). Sunt posibile mai multe forme de declarare si definire a variabilei adresa a unei componente: a) se poate defini un tip general de date de tip adresa, numit adr: typdef struct componenta {tip_informatie info; componenta *leg;}*adr; b) se poate defini numai structura unei componente si apoi se pot declara variabile de referinta Constructori: Pentru crearea, initializarea, copierea si distrugerea obiectelor, in C++ se folosesc functii membre speciale, numite constructori si destructori. Constructorul este apelat automat la eliminarea unui obiect al clasei, la incheierea timpului de viata sau, in cazul variabilelor dinamice, este solicitat prin program (cu operatorul delete), inclusiv pentru obiecte temporare. Aceste functii efectueaza operatii prealabile utilizarii obiectului creat, respectiv eliminarii lui. Alocare si eliminarea memoriei necesare datelor membre ramane in sarcina compilatorului. Astfel constructurul este apelat dupa alocarea memoriei necesare pentru datele membre ale obiectului (in faza finala a crearii obiectului). Constructorii se declara si se definesc similar cu celelalte functii membre, dar se disting de acestea prin unele caracteristici: - numele functiilor constructor coincide cu numele clasei careia ii apartin; - in declaratie si in definitie nu se specifica nici un tip de rezultat (nici macar void); - nu se pot utiliza pointeri catre constructori; - costructorii pot avea parametri si pot fi supradefiniti. Un constructor fara parametri se numeste costructor implicit. Daca o clasa nu dispune de constructori compilatorul va genera automat un constructor implicit. Operatiile care se pot executa asupra listelor sunt foarte variate: adaugari, inserari, extrageri, cautari, concatenari, divizari, sortari. a) adăugarea într-o listă simplu înlănţuită ordonată : Dacă dorim ca nodurile listei să fie parcurse după un anumit criteriu (de exemplu crescător după câmpul cuvant), trebuie ca introducerea unui nou nod în listă să se facă astfel încât să nu se strice ordinea listei (altfel 3

spus, îl vom introduce la locul lui); pentru exemplul considerat, vom introduce noul nod înaintea primului nod cu câmpul cuvant mai mare decât câmpul său cuvant.

Adaugarea unui element la inceputul listei:

Dacă nodul nou are câmpul cuvant mai mic decât câmpul cuvant al primului nod nod*adaug_incep (nod*nou){ nou->urm; (nou->urm pointeaza spre primul nod din lista) prim=nou; (prim pointeaza acum spre nou, care a devenit primul nod al listei) }. Adăugarea la sfârşitul listei

void adaug_sfs(nod *nou, nod *p){ ( anterior s-a parcurs lista pana la ultimul nod p)nou->urm =NULL; (se poate scrie si nou->urm=p-urm, deoarece p->urm=NULL) p->urm=nou; ( p->urm pointeaza spre nou, care acum este ultimulnod al listei) }. b) cautarea unui element in lista: Operatia de cautare (lookup) returneaza valoarea “adevarat” daca elementul cu valoarea x apartine listei, si valoarea “false”, daca elementul nu apartine listei. În funcţie de cerinţe, nodurile listei pot fi accesate secvenţial, extrăgând informaţia utilă din ele. O problemă mai deosebită este găsirea unui nod de o cheie dată şi apoi extragerea informaţiei din nodul respectiv. Căutarea nodului după cheie se face liniar, el putând fi prezent sau nu în listă. 4

O funcţie de căutare a unui nod de cheie “key” va conţine secvenţa de program de mai jos; ea returnează adresa nodului respectiv în caz de găsire sau pointerul NULL în caz contrar: TIP_NOD *p; p=prim; while( p != 0 ) if (p->cheie == key) { /* s-a găsit nodul de cheie dată */ /* el are adresa p */ return p; } else p=p->urm; return 0; /* nu există nod de cheie = key */ c ) inserarea unui nod intr-o lista simplu inlantuita: Operatia de inserare consta in adaugarea unui nou element x unei liste L. Pozitia in care se poate insera noul element este oricare pozitie in lista: inaintea primului element (in aceasta situatie se modifica capul listei), dupa ultimul element, sau intre oricare doua elemente. Este admisa inserarea unui nou element care are aceeasi valoare cu un alt element component al listei. Se presupune ca are pointerul p. Daca lista este vida, acest nod va fi singur în lista: if (prim == 0) { prim=p; ultim=p; p->urm=0; } Daca lista nu este vida, inserarea se poate face astfel: a) înaintea primului nod if(prim != 0) { p->urm = prim; prim = p; } b) dupa ultimul nod: if (ultim != 0) { p -> urm = 0; ultim -> urm = p; ultim = p; } d) stergerea unui nod dintr-o lista simplu inlantuita: Operatia de stergere a unui element dintr-o lista inseamna eliminarea unui element x dintr-o lista. Daca in lista exista mai multe elemente cu aceeasi valore, se specifica suplimentar care dintre acestea se elimina. La stergerea anui nod se va avea in vedere : dacă dorim să eliminăm un nod din listă, memoria pe care acesta o ocupa va trebui eliberată, pentru a fi folosită la adăugarea de alte noduri; dacă nu o eliberăm explicit cu funcţia free, ea va rămâne marcată ca fiind ocupată pe durata execuţiei programului şi nu va putea fi folosită. De aceea, înainte de a reface legăturile pentru ca nodul de şters să fie eliminat din listă, adresa lui va fi memorată într-o varialbilă pentru a fi eliberată ulterior zona de memorie dedicată lui. Ştergerea primului nod nod *sterg_incep(nod *p){ nod *q q=prim; // q retine adresa primului element al listei prim=q->urm; // prim pointeaza acum spre al 2-lea nod din lista, devenit primul free(q); // eliberam memoria ocupata de fostul prim element }

5

Ştergerea ultimului nod Dacă nu avem un pointer care să ne reţină adresa ultimului nod, parcurgem lista şi ne oprim înaintea ultimului nod nod *sterg_sfs(nod *p){ nod *q; q=p->urm; // q retine adresa ultimului element al listei p->urm=NULL; // sau p->urm=q->urm , deoarece q->urm==NULL // nodul(*q)este sters dpdv al listei, deoarece nu se mai poate ajunge la el free(q); // eliberam memoria ocupata de ultimul element (de la adresa stocata in q) }

Ştergerea nodului de după nodul p

Parcurgem lista şi ne oprim înaintea nodului pe care vrem să îl ştergem, adică la nodul p nod *sterg_incep(nod *p){ nod *q; q=p->urm; // q retine adresa ultimului element al listei p->urm=q->urm; // nodul (*q) este sters dpdv al listei, deoarece nu se mai poate ajunge la el free(q); //eliberam memoria ocupata de ultimul element }

Parcurgerea unei liste simplu inlantuite: Consideram: cap- contine adresa primului element din lista. O parcurgere inseamna prelucrarea pe rand a tuturor elementelor listei, in ordinea in care acestea apar in lista. Vom avea o variabila pointer p care va indica pe rand fiecare element al listei: p=cap; while (p!=0){ (prelucreaza p-> data) p=p->leg; } for {p=cap; p!=0; p=p->leg{ (prelucreaza p->data) }

6

Problema rezolvată efectuează operaţiile de adăugare, ştergere şi căutare într-o listă simplu înlănţuită ordonată. Adăugarea se va face astfel încât lista să rămână ordonată. #include <stdio.h> #include <stdlib.h> #include <string.h> #include /* tipul pentru nodul lista */ typedef struct elem { float info; struct elem *urm; } 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) { for ( ; p!=NULL && p->infourm); /* cautam doar pana la primul element mai mare decat inf (daca el nu exista), deoarece lista e ordonata, deci nu mai are sens sa parcurgem mai departe*/ if (p!=NULL && inf==p->info) return p; /* daca info a fost gasit in lista */ return NULL; /* daca nu a fost gasita */ } /*

Functia listez parcurge lista si pentru fiecare nod afiseaza informatia memorata. */ void listez(nod *p) { printf("Un nod ocupa %d octeti, pointerul catre nod ocupa %d octeti\n", sizeof(*p), sizeof(p)); for ( ; p!=NULL; p=p->urm) printf("(adr=%p) |%6g| %p | \n",p,p->info, p->urm); } /* Functia sterg elimina din lista (indicata de pointerul p) nodul ce are campul info egal cu argumentul inf */ nod *sterg(nod *radacina, float inf) { nod *aux, *p; if (radacina==NULL){ // lista vida printf("Eroare: lista e vida\n"); return NULL; } else if (radacina->info==inf){ // sterg primul element aux=radacina; radacina=radacina->urm; free(aux); return radacina; }

7

*/

}

else{ // parcurgem lista pana gasim nodul cu info=infonou sau pana la sfarsit for(p=radacina; p->urm!=NULL && p->urm->infourm); if (p->urm != NULL && p->urm->info==inf) // nodul cautat exista { aux=p->urm; p->urm=aux->urm; // adica p->urm=p->urm->urm; free(aux); } else // nodul cautat nu exista printf("Eroare: identificatorul %f nu apare in lista\n", inf); return radacina; }

/*Functia introduc insereaza un nod in lista ordonata, Functia returneaza pointerul catre inceputul listei modificate */ nod * introduc(nod *radacina, float infonou) { nod *nou, *p; if ((nou=(nod *)malloc(sizeof(nod)))==NULL) { /* daca nu e memorie suficienta pentru a crea un nod nou,se da un mesaj de eroare dupa care se termina functia sise returneaza NULL */ printf("Eroare: memorie insuficienta\n"); return NULL; } 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){ // iintroduc la inceput nou->urm=radacina; radacina=nou; } else{ // inserare in int listei sau la sfarsit for(p=radacina; p->urm!=NULL && p->urm->infourm); nou->urm=p->urm; p->urm=nou; } return radacina; } /* Functia main afiseaza meniul programului,citeste comanda */ /* si apeleaza functia corespunzatoare */ void main(void) { char o; float val; nod *radacina=NULL, *p; /* pastreaza inceputul listei */ puts(""); while(1) { puts(""); /* se afiseaza meniul programului */ puts("a : adauga un nod"); puts("c : cauta si tipareste un nod"); puts("s : sterge un nod");

8

puts("l : listeaza tot"); puts("t : termina programul"); printf("\nOptiunea: "); while(isspace(o=getchar()) ); puts(""); switch (tolower(o)) { case 'a': { printf("adauga nr="); scanf("%f", &val); radacina=introduc(radacina, val); break;} case 'c': { puts("cauta si tipareste un nod"); printf("nr="); scanf("%f", &val); if ((p=caut(radacina, val))!=NULL) /* cauta nodul in lista */ printf(" Valoare:%f\n", p->info); else printf("Eroare: Identificator nedefinit\n"); break; } case 's':{ printf("stergere nr="); scanf("%f", &val); radacina=sterg(radacina, val); /* sterge nodul din lista */ break;} case 'l':{ puts("listare"); listez(radacina); break;} case 't': return; default: printf("Eroare : Comanda inexistenta\n"); } } }

9