Liste liniare dublu  inlantuite

 

O componenta a unei liste dublu inlantuite se declara ca o data structurata de tip inregistrare, formata din trei campuri: informatia propriu-zisa (care poate fi de orice tip: numeric, caracter, pointer, tablou, inregistrare) si informatiile de legatura (adresa la care e memorata urmatoarea componenta si adresa la care e memorata precedenta componenta). Ultima componenta va avea informatia de legatura corespunzatoare urmatoarei adrese NULL (sau 0), cu semnificatia ca dupa ea nu mai urmeaza nimic (retine adresa „nici o adresa” a urmatoarei componente).La fel si in cazul primei componente pentru campul adresa precedenta.

 

0                                                                                                                                        0                                 

 

 

 

 

 

 

Conform celor enuntate anterior memorarea si prelucrarea acestor structuri de date este similara cu cea a listelor liniare simplu inlantuite, ba chiar unele prelucrari (cum ar fi stergerea si inserarea inainte se simplifica avand intr-un mod facil acces la componenta anterioara)

 

Se poate defini un tip de date structurat numit nod, ale carui campuri le numim info pentru informatia utila, next pentru adresa urmatoare si back pentru adresa precedenta.

 

De exemplu, pentru o lista de numere intregi, putem defini:

struct nod

   {int info;

    nod * next,* back;};

 

Componentele listei se vor aloca dinamic. Prelucrarea listei se va face tot prin intermediul a doi pointeri care acceseaza primul si respectiv ultimul element al listei unde  

Operatiile care se pot face utilizand liste dublu inlantuite sunt:

       crearea listei

-adaugarea unui element la inceputul listei

-adaugarea unui element la sfarsitul listei

-adaugarea unui element in interiorul listei

-stergerea elementului de la inceputul listei

-stergerea elementului de la sfarsitul listei

-stergerea unui element din interiorul listei

-traversarea listei, cu prelucrarea elementelor acesteia, intr-un „sens” sau celalalt

 

Iata o solutie de implementare a functiilor de creare ( si adaugare) si de parcurgere stanga-dreapta si dreapta-stanga.:

 

#include<iostream.h>

#include<conio.h>

 

struct Nod

      {int info;

       Nod *next,*back;

       };

 

Nod *prim, *ultim;

 

void creare_lista()

{Nod *c;

 c=new Nod;

 cout<<"info ";

 cin>>c->info;

 if(!prim)

   {prim=c;

    prim->next=0;

    prim->back=0;

    ultim=prim;

    }

 else

   {ultim->next=c;

    c->back=ultim;

    ultim=c;

    ultim->next=0;

   }

}

 

 

void listare_stanga_dreapta()

{Nod *c;

 c=prim;

 while(c)

    {cout<<c->info<<" ";

     c=c->next;}

}

 

void listare_dreapta_stanga()

{Nod *c;

 c=ultim;

 while(c)

    {cout<<c->info<<" ";

     c=c->back;}

}

 

 

 

void main()

   {int n,i;

    clrscr();

    cout<<"cate elemente va avea lista?";

    cin>>n;

    for(i=1;i<=n;i++)

      creare_lista();

    cout<<endl<<"Elementele listei de la stanga la dreapta sunt:"<<endl;

    listare_stanga_dreapta();

    cout<<endl<<"Elementele listei de la dreapta la stanga sunt:"<<endl;

    listare_dreapta_stanga();

    getch();

    } 

Aplicatie: Sa se implementeze operatiile cu liste liniare dublu inlantuite. Se va realiza cate o functie pentru fiecare operatie.

Probleme propuse:

 

1.       Sa se memoreze intr-o lista dubla n numere intregi. Care este primul element palindrom din dreapta?

2.       Sa se memoreze intr-o lista dubla n numere intregi. Sa se interschimbe primul element cu ultimul, al doilea cu penultimul etc. (informatiile utile).

3.    Sa se stearga prima si ultima valoare egala cu x dintr-o lista dubla

4.    Sa se insereze intre oricare doua elemente suma celorlalte

5.    O lista dubla retine caractere. Sa se determine daca sirul retinut de lista este palindrom. Se citeste un caracter k. Sa se insereze acest caracter inainte de fiecare vocala.

6.    fis1.txt si fis2.txt retin doua numere foarte mari sa se determine suma celor doua numere.

7.    Sa se determine cea mai lunga secventa crescatoare dintr-o lista dubla. Dupa afisare se va sterge aceasta secventa

8.    Sa se afiseze o lista ca perechi de numere: primul cu ultimul, al doilea cu penultimul s.a.m.d. pana la jumatate

9.    Fie o lista dubla. Sa se afiseze lista stanga-dreapta si dreapta stanga (icepand de la primul apoi de la ultimul). Se cunoaste adresa unui element oarecare din lista.

10. Sa se mute zerourile la sfarsitul unei liste duble. Nu se va folosi o lista intermediara