[C++] Liste liniare dublu inlantuite

[Nytro]

Ce am facut la scoala pe la ora... :

/**************************
  (c) Popescu Ionut 2009
**************************/

#include<iostream.h>

struct Nod
{
    int inf;
    Nod * leg1, * leg2;   
} * prim1, * ultim1;

int i, n, x, tip, y;

// Functia adauga un nod in fata primului

void adaugare_inainte(int x, Nod *& prim)
{
    Nod * p;
    p = new Nod;
    p -> inf = x;
    p -> leg1 = NULL;
    p -> leg2 = prim;
    prim = p;   
}

// Functia adauga un nod dupa ultimul

void adaugare_dupa(int x, Nod *& ultim)
{
    Nod * p;
    p = new Nod;
    p -> inf = x;
    p -> leg1 = ultim;
    p -> leg2 = NULL;
    ultim = p;   
}

// Functia afiseaza lista de la inceput

void afisare_inceput(Nod * prim)
{
    Nod * p;
    p = new Nod;
    p = prim; 
    cout<<"Afisare de la inceput\n------------------------------------\n";  
    while(p)
    {
        cout<<p -> inf<<" ( "<<p -> leg2<<" )"<<"\n";
        p = p -> leg2;  
    }
    cout<<"------------------------------------\n";
}

// Functia afiseaza lista de la sfarsit

void afisare_sfarsit(Nod * ultim)
{
    Nod * p;
    p = new Nod;
    p = ultim; 
    cout<<"Afisare de la sfarsit\n------------------------------------\n";  
    while(p)
    {
        cout<<p -> inf<<" ( "<<p -> leg1<<" )"<<"\n";
        p = p -> leg1;   
    }
    cout<<"------------------------------------\n";
}

// Functia introduce un nod de valoare x, dupa nodul cu valoarea y

void inserare_dupa(int x, int y, Nod * prim)
{
    Nod * p, * q;
    p = new Nod;
    q = new Nod;
    p -> inf = x;
    q = prim;
    while(q -> inf != y && q != NULL) { q = q -> leg2; }
    p -> leg1 = q;
    p -> leg2 = q -> leg2;
}

// Functia introduce un nod de valoare x, inainte de nodul cu valoarea y

void inserare_inainte(int x, int y, Nod * prim)
{
    Nod * p, * q;
    p = new Nod;
    q = new Nod;
    p -> inf = x;
    q = prim;
    while(q -> inf != y && q != NULL) { q = q -> leg2; }
    p -> leg1 = q -> leg1;
    p -> leg2 = q;
}

// Main-ul

int main()
{
    prim1 = new Nod;
    ultim1 = new Nod;

    cout<<"Noduri : ";
    cin>>n;

    cout<<"\nSelectati tipul de adaugare: \n1) Dupa ultimul element\n2) Inaintea primului element\n\nTip : ";
    cin>>tip;

    cout<<"\n------------------------------------\n";

    cout<<"Nod 1 : ";  
    cin>>x;

    prim1 -> inf = x;
    prim1 -> leg1 = NULL;
    prim1 -> leg2 = NULL;
    ultim1 = prim1; 

    for(i = 2; i <= n; i++)
    {
        cout<<"Nod "<<i<<" : ";
        cin>>x;
        if(tip == 2) adaugare_inainte(x, prim1);
        else adaugare_dupa(x, ultim1);
    }

    cout<<"\n------------------------------------\n\n";

    cout<<"Selectati tipul de afisare: \n1) De la inceput\n2) De la sfarsit\n\nTip : ";
    cin>>tip;

    if(tip == 2) afisare_sfarsit(ultim1);
    else afisare_inceput(prim1);

    // Introducem un nod dupa o valoare

    cout<<"\n------------------------------------\n";

    cout<<"Introduce un nod dupa valoarea : ";
    cin>>y;

    cout<<"Valoare de introdus : ";
    cin>>x;

    inserare_dupa(x, y, prim1);

    afisare_inceput(prim1);

    // Introducem un nod inainte de o valoare

    cout<<"\n------------------------------------\n";

    cout<<"Introduce un nod inainte valoarea : ";
    cin>>y;

    cout<<"Valoare de introdus : ";
    cin>>x;

    inserare_dupa(x, y, prim1);

    afisare_inceput(prim1);

    return(0);
}

Pastebin:

http://pastebin.com/f5f6c720b

Alta versiune ( nu mai stiu, cred ca e mai noua )

#include<iostream.h>

struct Nod
{
    int inf;
    Nod * legs, * legd;   
} * prim, * ultim;

int i, n, x, y;

void adaugare_inainte(int x)
{
    Nod * p;
    p = new Nod;
    p -> inf = x;
    p -> legs = NULL;
    p -> legd = prim;
    prim -> legs = p;
    prim = p; 
}

void adaugare_dupa(int x)
{
    Nod * p;
    p = new Nod;
    p -> inf = x;
    p -> legd = NULL;
    p -> legs = ultim;
    ultim -> legd = p;
    ultim = p;
}

void inserare_dupa(int x, int y)
{
    Nod * p, * q;
    p = new Nod;
    p -> inf = x;
    q = prim;
    while(q -> inf != y && q -> legd) { q = q -> legd; }
    p -> legd = q -> legd;
    q -> legd = p;
    p -> legs = q; 
}

void inserare_inainte(int x, int y)
{
    Nod * p, * q;
    p = new Nod;
    p -> inf = x;
    q = prim;   
    while(q -> inf != y && q -> legd) { q = q -> legd; }
    p -> legd = q;
    p -> legs = q -> legs;
    q -> legs -> legd = p;
    q -> legs = p;
}

void stergere_nod(int x)
{
    Nod * p;
    p = prim;
    int g = 1;
    while(p)
    {
        if(p -> inf == x)
        {
            p -> legs -> legd = p -> legd;
            p -> legd -> legs = p -> legs;
            delete(p);
            g = 0;
            break;   
        }
        p = p -> legd;
    }
    if(g) cout<<"Nodul nu a fost gasit\n\n";
}

void afisare_inceput()
{
    Nod * p;
    p = prim;
    cout<<"Afisare de la inceput : \n";
    cout<<"\n-------------------------------\n";
    while(p)
    {
        cout<<p -> inf<<" ( "<<p -> legs<<" ) ( "<<p -> legd<<" ) \n";
        p = p -> legd;   
    }
    cout<<"\n-------------------------------\n";
}

void afisare_sfarsit()
{
    Nod * p;
    p = ultim;
    cout<<"Afisare de la sfarsit : \n";
    cout<<"\n-------------------------------\n";
    while(p)
    {
        cout<<p -> inf<<" ( "<<p -> legs<<" ) ( "<<p -> legd<<" ) \n";
        p = p -> legs;   
    }
    cout<<"\n-------------------------------\n";
}

void meniu()
{
    int optiune;

    cout<<"Alege o optiune : \n\n";
    cout<<"1) Adaugare nod la inceput\n";
    cout<<"2) Adaugare nod la sfarsit\n";
    cout<<"3) Inserare nod dupa o valoare\n";
    cout<<"4) Inserare nod inainte de o valoare\n";
    cout<<"5) Stergere nod\n";
    cout<<"6) Afisare de la inceput\n";
    cout<<"7) Afisare de la sfarsit\n";
    cout<<"8) Iesire\n";

    cout<<"Optiunea selectata : ";
    cin>>optiune;
    cout<<"\n-------------------------------\n";

    switch(optiune)
    {
        case 1:
            cout<<"Valoare de introdus ( inainte ) : ";
            cin>>x;
            adaugare_inainte(x);
            cout<<"\n-------------------------------\n";
            break;
        case 2:
            cout<<"Valoare de introdus ( dupa ) : ";
            cin>>x;
            adaugare_dupa(x);
            cout<<"\n-------------------------------\n";
            break;  
        case 3:
            cout<<"Valoare de inserat ( dupa ) : ";
            cin>>x;
            cout<<"Valoarea dupa care sa se introduca : ";
            cin>>y;
            inserare_dupa(x, y); 
            cout<<"\n-------------------------------\n";
            break; 
        case 4:
            cout<<"Valoare de inserat ( inainte ) : ";
            cin>>x;
            cout<<"Valoarea inainte de care sa se introduca : ";
            cin>>y;
            inserare_inainte(x, y);  
            cout<<"\n-------------------------------\n";
            break;
        case 5:
            cout<<"Stergere nod de valoare : ";
            cin>>x;
            stergere_nod(x); 
            cout<<"\n-------------------------------\n"; 
            break;
        case 6:
            afisare_inceput();
            break;
        case 7:
            afisare_sfarsit();
            break;
        case 8:
            exit(0);
            break;               
        default:
            cout<<"Optiunea selectata nu exista\n\n";
            cout<<"\n-------------------------------\n";      
    }
    meniu();
}

int main()
{
    prim =  new Nod;

    cout<<"Valoarea primului nod :";
    cin>>x;

    // Crearea primului nod care e si ultimul

    prim -> inf = x;
    prim -> legs = NULL;
    prim -> legd = NULL;
    ultim = prim;

    meniu();

    return(0);   
}

Pastebin:

http://pastebin.com/d14e11198

Nu am stat sa comentez fiecare linie de cod.

Edited April 7, 2009 by Nytro

[a13x4nd7u]

Pot sa postez si eu ce am facut la orele de informatica? (la programare ma refer)

[Nytro]

Pai da, dar nu orice programel simplu, astea sunt cam toate functiile care se pot face cu liste liniare dublu inlantuite. Bine, teoretic, adica sunt cele mai importante.

[noidee]

Pai da, dar nu orice programel simplu, astea sunt cam toate functiile care se pot face cu liste liniare dublu inlantuite. Bine, teoretic, adica sunt cele mai importante.

Legea numarul 1 in programare cu pointeri:

- absolut orice pointer pe care il aloci trebuie sa il si eliberezi

[Nytro]

Pai am functia sterge nod. In rest, toate functiile creaza un nod ( pointer ) asta e scopul lor. Daca ii sterg nu mai am nici o lista.

[inthel]

hmm

lasa-ma sa gicesc este a 10-a ... nu?

[noidee]

Pai am functia sterge nod. In rest, toate functiile creaza un nod ( pointer ) asta e scopul lor. Daca ii sterg nu mai am nici o lista.

Cand iesi din program dealoci resursele utilizate. Asa se programeaza profesional.

[Nytro]

Sunt pentru clasa a XI-a, profil mate-info, eu am 4 ore de info pe saptamana.

noidee: Da, dar nu cred ca e necesar. Adica, practic, sincer, mi se pare o prostie. Resursele sunt dezalocate automat, iar programul isi incheie executia mai rapid, fara alte instructiuni.

Ma mai jucam pe la scoala cu:

double p;

while(p = new double) { }

Dar la fel, cand se umplea memoria se "busea", cum imi place mie sa zic, dar memoria era eliberata.

[noidee]

noidee: Da, dar nu cred ca e necesar. Adica, practic, sincer, mi se pare o prostie. Resursele sunt dezalocate automat, iar programul isi incheie executia mai rapid, fara alte instructiuni.

Ma mai jucam pe la scoala cu:

double p;

while(p = new double) { }

Dar la fel, cand se umplea memoria se "busea", cum imi place mie sa zic, dar memoria era eliberata.

Asa e, nu e neaparat necesar. Timpul efectiv de executie nu ti-l scurteaza mult pentru ca ce nu faci tu va face sistemul de operare.

Totusi avem prostul obicei de a folosi cod pentru alte proiecte si data viitoare cand il vei folosi sunt sigur ca uiti ca nu ai dealocat pointerul ala si in felul asta iti incarci programul aiurea. Ca sa nu spun ca la programare embedded orice bit ocupat in plus inseamna dezastru.

Si daca tot folosesti c++ de ce nu ai facut clase si operatori?

[a13x4nd7u]

Si eu sunt clasa a 11-a la mate info intensiv info (7 ore pe saptamana) si nu am facut clase la scoala (dar asta nu inseamna ca nu am facut programe care folosesc clase).

[Nytro]

noidee: Da, ai dreptate, ar fi recomandat ca memoria sa fie eliberata. De exemplu, in VB6, mai folosesc CSocketMaster pentru a asculta pe un port. Si daca nu inchid socketul, la urmatoarea rulare a programului, nu mai pot asculta pe acel port. Nu folosesc clase pentrun ca nu prea ma pricep.

[PClaudiu]

Man, imagineaza-ti o chestie ipotetica. Softul tau ruleaza pe un server care intretine, sa zicem,satelitii cu ICBM-uri ale Statelor Unite. Vine un programator din asta bleg, face softul pentru server si uita sa dealoce pointerii. Programul ruleaza in continuu, la un moment dat va ramane fara memorie, si se va "elibera", cum spui tu. Ce crezi ca se va intampla cu rachetele? "Oh my god, buffer overflow, we're doomed!" Ce spui de asta? Nu ii pasa nimanui daca pe calculatorul tau nu dealoci pointerii, dar cand lucrezi la un proiect serios atunci asta ar trebui sa fie mai important chiar decat sa te inchei la prohap dupa ce ti-ai facut nevoile.

[Zatarra]

Nu cred ca e vorba de o chestie serioasa si stai linistit ca daca era un proiect sau ceva important se documenta mai mult, cauta mai multe variante in final alegand`o pe cea mai buna, cel putin asa ar fi normal. Oricum adevarul e ca adresele de memorie trebuie eliberate.. cum spunea si noidee :

- absolut orice pointer pe care il aloci trebuie sa il si eliberezi

[bylosul93]

Ai incercat sa folosesti STL-ul si vectorii specifici pentru a retine lista de adiacenta a grafului?

Nu mai scrii atat de mult si sunt destul de rapizi.Problema e ca nu se gaseste STL pe batranul Borland C++ 3.1 ci pe IDE-uri mai noi . Incearca sa te documentezi de STL si sa vezi ce minuni poate face. E practic si eficient:).

[loki]

CE-AVETI FRATILOR! Denumirea de "liste liniare dublu inlantuite" te duce cu gandul mai degraba la metodica, la algoritmica, nu la cazurile speciale in care uiti sa aloci sau nu pointeri.

Voi veniti cu cazuri particulare... Hai ca sunteti tari, care e tare sa imi explice cap coada cum se foloseste o lista liniara dublu inlantuita in BASIC? Dau 10 beri sa aud asta!

Nota 10 pentru "batranul borlandC++" - scopul lui a fost si este sa fie cel mai apropiat limbaj de limbajul de asamblare si de aceea tot ce se creeaza sub el va functiona rapid. 3.1 e depasit doar pentru ca a fost facut pentru single tasking dar trecand pe visual parca dispar totusi problemele de alocare.

STL=doar alt limbaj.

Edited June 14, 2009 by loki

[Andrei]

STL=doar alt limbaj.

genial:)))))