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






LISTE SIMPLU INLANTUITE

c











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: 5512
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 )