Plan

  • Tipul structura/ inregistrare – recapitulare
  • Liste simplu înlănțuite
  • Liste dublu înlănțuite
  • Stive
  • Cozi

Tipul struct

  • recapitulare de la laboratorul 3

Liste simplu înlănțuite

(LIFO, declarație simplă)

Citirea unei liste simplu înlănțuită

void citesteListaSimpla(listaSimpla& L) {
    unsigned int nrElemente;
    cout<<"Dati numarul de elemente: ";
    cin>>nrElemente;
    tipDate element;
    L=NULL; listaSimpla p;
    for (unsigned int i=1; i<=nrElemente; i++)
    {
        cout<<"Dati elementul al "<<i<<"-lea: ";
        cin>>element; p=new nod; p->info=element;
        p->urm=L;L=p;
    }
}

Afișarea unei liste simplu înlănțuite

void afiseazaListaSimpla(listaSimpla L) {
    listaSimpla p; p=L;
    while (p!=NULL) {
        cout<<p->info<<", ";
        p=p->urm;
    }
    cout<<"\n";
}

Un program exemplu

int main() {
    cout<<"Program cu liste\n\n"; listaSimpla L;
    cout<<"Citire:\n"; citesteListaSimpla(L);
    cout<<"Afisare:\n"; afiseazaListaSimpla(L);
    return 0; 
}

Listă dublu înlănțuită

(s-a folosit o structură, mecanismul este FIFO)

#define tipDate int
struct nod {
    tipDate info;
    nod* urm;
    nod* prec;
};

struct listaDubla {
    nod* prim; nod* ultim;
    unsigned int lungime;
};

Inițializarea listei

void initializeazaListaDubla(listaDubla& L)
{
    L.lungime=0;
    L.prim=NULL; L.ultim=NULL;
}

Adăugarea unui element la listă

void adaugaLaListaDublaElement(listaDubla& L, tipDate element) {
    if (L.lungime==0) {
        L.prim=new nod; L.prim->info=element;
        L.prim->urm=NULL; L.prim->prec=NULL;
        L.ultim=L.prim; L.lungime++; 
    }
    else {
        nod* p; p=new nod;
        p->info=element; p->urm=NULL;
        p->prec=L.ultim; L.lungime++;
        L.ultim->urm=p; L.ultim=p;
    }
}

Citirea listei dublu înlănţuite

void citesteListaDubla(listaDubla& L)
{
    unsigned int nrElemente;
    cout<<"Dati numarul de elemente: ";
    cin>>nrElemente;
    tipDate element;
    for (unsigned int i=1; i<=nrElemente; i++)
    {
        cout<<"Dati elementul al "<<i<<"-lea: ";
        cin>>element;
        adaugaLaListaDublaElement(L, element);
    }
}

Afişarea listei dublu înlănţuite

void afiseazaListaDubla(listaDubla L)
{
    nod* p=L.prim;
    while (p!=NULL)
    {
        cout<<p->info<<", ";
        p=p->urm;
    }
    cout<<"\n";
}

Funcţia main() și programul exemplu

#include <iostream>
using namespace std;
#define tipDate int
int main()
{
    cout<<"Program cu liste dublu-inlantuite\n\n";
    listaDubla L;
    initializeazaListaDubla(L);
    cout<<"Citire:\n";
    citesteListaDubla(L);
    cout<<"Afisare:\n";
    afiseazaListaDubla(L);
    return 0;
}

Execuția programului

Ştergerea unui element

void stergeElement(listaDubla L, unsigned int pozitieElement) { 
// sterge un element de pe o pozitie din interior
    nod* p=L.prim;
    nod* q; nod* r;
    for (unsigned int i=1; i<=pozitieElement-1; i++)
        p=p->urm;
    q=p->prec; r=p->urm;
    q->urm=r; r->prec=q;
    delete p;
    L.lungime--;
}

Execuţia programului