Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza















LISTE SIMPLU INLANTUITE

c



loading...








ALTE DOCUMENTE

Operatori si expresii
Probleme nesolutionate inca
Operatori aritmetici
Variabile externe
Tipuri
INTRARI SI IESIRI (I/O) IN C
FUNCTII SI STRUCTURA PROGRAMULUI C
INTRARI / IESIRI STANDARD
Notiuni primare de programare in Pascal si C
INSTRUCTIUNEA RETURN


LISTE SIMPLU ĪNLĂNŢUITE

1.    Continutul lucrarii

Īn lucrare sunt prezentate operatiile importante asupra listelor simplu īnlantuite si particularitatile stivelor si cozilor.

2.      Consideratii teoretice

Lista este o multime finita si ordonata de elemente de acelasi tip. Elementele listei se numesc noduri.

Listele pot fi organizate sub forma statica, de tablou, caz īn care ordinea este implicit data de tipul tablou unidimensional, sau cel mai des, sub forma de liste dinamice, īn care ordinea nodurilor este stabilita prin pointeri. Nodurile listelor dinamice sunt alocate īn memoria heap. Listele dinamice se numesc liste īnlantuite, putānd fi simplu sau dublu īnlantuite.

Īn continuare se vor prezenta principalele operatii asupra listelor simplu īnlan 434d36e tuite.

Structura unui nod este urmatoarea:

typedef struct tip_nod TIP_NOD;

Modelul listei simplu īnlantuite este prezentat īn fig. 2.1.



Fig. 2.1. Model de lista simplu īnlantuita

Pointerii prim si ultim vor fi declarati astfel:

TIP_NOD *prim, *ultim;

2.1     Crearea unei liste simplu īnlantuite

Crearea unei liste simplu īnlantuite se va face astfel:

a)      Initial lista este vida:

prim = 0; ultim = 0;

b)      Se genereaza nodul de introdus:

n=sizeof(TIP_NOD);

p=(TIP_NOD *)malloc(n);     /* rezervare spatiu de memorie īn heap*/

citire date īn nodul de adresa p;

c)      Se fac legaturile corespunzatoare:

p->urm = 0;  /*nodul este ultimul īn lista */

if(ultim != 0) ultim->urm = p;  /* lista nu este vida */

else prim = p;

/* nodul p este primul introdus īn lista */

ultim=p;


2.2     Accesul la un nod al unei liste simplu īnlantuite

Īn functie de cerinte, nodurile listei pot fi accesate secvential, extragānd informatia utila din ele. O problema mai deosebita este gasirea unui nod de o cheie data si apoi extragerea informatiei din nodul respectiv. Cautarea nodului dupa cheie se face liniar, el putānd fi prezent sau nu īn lista.

O functie de cautare a unui nod de cheie "key" va contine secventa de program de mai jos; ea returneaza adresa nodului respectiv īn caz de gasire sau pointerul NULL īn caz contrar:

TIP_NOD *p;

p=prim;

while( p != 0 )  if (p->cheie == key)

else p=p->urm;

return 0;               /* nu exista nod de cheie = key */

2.3     Inserarea unui nod īntr-o lista simplu īnlantuita

Nodul de inserat va fi generat ca la paragraful 2.1; se presupune ca are pointerul p.

Daca lista este vida, acest nod va fi singur īn lista:

if (prim == 0)

Daca lista nu este vida, inserarea se poate face astfel:

a)      īnaintea primului nod

if(prim != 0)


b)      dupa ultimul nod:

if (ultim != 0)

c)    īnaintea unui nod precizat printr-o cheie "key":

- se cauta nodul de cheie "key":

TIP_NOD  *q, *q1;

q1=0; q=prim;

while(q!=0)

- se insereaza nodul de pointer p, facānd legaturile corespunzatoare:

if(q!=0)

else

}

d)    dupa un nod precizat printr-o cheie "key":

- se cauta nodul avānd cheia "key":

TIP_NOD *q;

q=prim;

while(q!=0)

-  se insereaza nodul de adresa p, facānd legaturile corespunzatoare:

if (q !=)0)

2.4     stergerea unui nod dintr-o lista simplu īnlantuita

La stergerea unui nod se vor avea īn vedere urmatoarele probleme: lista poate fi vida, lista poate contine un singur nod sau lista poate contine mai multe noduri.

De asemenea se poate cere stergerea primului nod, a ultimului nod sau a unui nod dat printr-o cheie "key".

a)      stergerea primului nod

TIP_NOD *p;

if(prim!=0)


b)      stergerea ultimului nod

TIP_NOD *q, *q1;

q1=0; q=prim;

if(q!=0)

if(q==prim)

else

elib_nod(q);

}

c)      stergerea unui nod de cheie "key"

TIP_NOD *q, *q1;

/* cautare nod */

q1=0; q=prim;

while (q!=0)

if(q != 0) 

else

2.5     stergerea unei liste simplu īnlantuite

Īn acest caz, se sterge īn mod secvential fiecare nod:

TIP_NOD *p;

while( prim != 0) 

ultim=0;

2.6     Stive


Stiva este o lista simplu īnlantuita bazata pe algoritmul LIFO (Last In First Out), adica ultimul nod introdus este primul scos. Modelul stivei, care va fi avut īn vedere īn continuare, este prezentat īn fig.2.6.1.

Fig. 2.6.1. Model de stiva

Fiind o structura particulara a unei liste simplu īnlantuite, operatiile principale asupra unei stive sunt:

- push - pune un element pe stiva; functia se realizeaza conform paragrafului 2.3.a., adica prin inserarea unui nod īnaintea primului;

- pop          - scoate elementul din vārful stivei; functia se realizeaza conform paragrafului 2.4.a., adica prin stergerea primului nod;

- clear - stergerea stivei; functia se realizeaza conform paragrafului 2.5.

Īn concluzie, accesul la o stiva se face numai pe la un capat al sau.


2.7.  Cozi

Coada este o lista simplu īnlantuita, bazata pe algoritmul FIFO (First In First Out), adica primul element introdus este primul scos. Modelul cozii  care va fi avut  īn vedere īn consideratiile


urmatoare, este prezentat īn fig.2.7.1.

Fig.2.7.1. Model de coada

Deci coada are doua capete, pe la unul se introduce un element, iar de la celalalt capat se scoate un element.

Operatiile importante sunt:

-     introducerea unui element īn coada - functia se realizeaza prin inserarea dupa ultimul nod, conform celor prezentate la paragraful 2.3.b.;

-     scoaterea unui element din coada - functia se realizeaza prin stergerea primului nod, conform celor prezentate la paragraful 2.4.a.;

-     stergerea cozii - functia se realizeaza conform paragrafului 2.5.

3.   Mersul lucrarii

3.1.Sa se defineasca si sa se implementeze functiile pentru structura de date

typedef stuct LISTA;

avānd modelul din fig.3.1.



3.2.Sa se implementeze o lista ca un tablou static ce contine pointeri la nodurile de informatie din heap, conform modelului din fig.3.2.

3.3. De la tastatura se citesc cuvinte. Sa se creeze o lista simplu īnlantuita ordonata alfabetic, care contine īn noduri cuvintele distincte si frecventa lor de aparitie. Se va afisa continutul listei īn ordine alfabetica .

3.4. Se considera un depou de locomotive cu o singura intrare si cu o singura linie de cale ferata, care poate cuprinde oricāte locomotive. Sa se scrie programul care realizeaza dispecerizarea locomotivelor din depou.

Programul prelucreaza comenzi de intrare īn depou a unei locomotive, de iesire din depou a unei locomotive si de afisare a locomotivelor din depou.

3.5.   Aceeasi problema 3.4, cu deosebirea ca depoul are intrarea la un capat si iesirea la capatul opus.

3.6.   Sortarea topologica.

Elementele unei multimi M sunt notate cu litere mici din alfabet. Se citesc perechi de elemente x, y (x, y apartin multimii M) cu semnificatia ca elementul x precede elementul y. Sa se afiseze elementele multimii M īntr-o anumita ordine, īncāt pentru orice elemente x, y cu proprietatea ca x precede pe y, elementul x sa fie afisat īnaintea lui y.

3.7.Sa se scrie programul care creeaza doua liste ordonate crescator dupa o cheie numerica si apoi le interclaseaza.

3.8.Sa se conceapa o stuctura dinamica eficienta pentru reprezentarea matricelor rare. Sa  se scrie operatii de calcul a sumei si produsului a doua matrice rare. Afisarea se va face in forma naturala.

3.9.Sa se conceapa o structura dinamica eficienta pentru reprezentarea īn memorie a polinoamelor. Se vor scrie functii de calcul a sumei, diferentei, produsului si īmpartirii a doua polinoame.

3.10. Se citeste de la tastatura o expresie postfixata corecta sintactic. Sa se scrie programul de evaluare a sa. Expresia contine variabile formate dintr-o litera si operatorii binari +, -, *, /.



Document Info


Accesari: 5637
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.

 


Copyright © Contact (SCRIGROUP Int. 2014 )