Liste circulare
In unele aplicatii este necesar sa se prelucreze structuri de date inlantuite simple sau duble circulare. Acestea se obtin din liste liniare printr-o singura operatie daca lista este simpla sau prin doua operatii daca lista este dubla:
Fie urmatoarea lista dubla definite astfel:
struct nod
{int info;
nod * next,* back;};
nod*prim,*ultim;
prim ultim
0 0
Lista devine circulara prin operatiile:
ultim->next=prim; //urmatorul ultimului devine primul
prim->back=ultim; //precedentul
primului devine ultimul
Prin urmare nici un nod nu va mai contine pentru campurile *next sau *back valoarea 0 (ultimul si primul in cazul listelor liniare) ceea ce va determina modificarea functiei de parcurgere in scopul prelucrarilor .
prim
ultim
Iata o solutie de generare a unei liste duble circulare de intregi pornind de la o lista liniara dubla si o modalitate de parcurgere a listei circulare astfel obtinute:
#include<iostream.h>
#include<conio.h>
struct Nod
{int info;
Nod *next,*back;};
Nod *prim, *ultim;
int n;
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 creaza_lista_circulara()
{ultim->next=prim;
prim->back=ultim;
}
void afiseaza_lista_circulara(Nod *c) //se parcurge lista pornind de la o adresa transmisa
{for(int i=1;i<=n;i++)
{cout<<c->info<<" ";
c=c->next;}
}
void main()
{int 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();
creaza_lista_circulara();
cout<<endl<<"afiseaza
lista circulara incepand de la primul :"<<endl;
afiseaza_lista_circulara(prim);
cout<<endl<<"afiseaza
lista circulara incepand de la al doilea :"<<endl;
afiseaza_lista_circulara(prim->next);
cout<<endl<<"afiseaza
lista circulara incepand de la ultimul :"<<endl;
afiseaza_lista_circulara(ultim);
getch();
}
Probleme propuse:
Problema 1
Sa se genereze o lista circulara care prelucreaza numere intregi:
a) sa se parcurga lista incepand de la primul nod in ambele sensuri
b) sa se parcurga lista incepand de la ultimul nod in ambele sensuri
c) sa se parcurga lista in ambele sensuri din doua in doua elemente de n ori
d) sa se parcurga n elemente pornind de la primul din p in p elemente. De exemplu, daca lista contine valorile: 1,2,3,4,5,6,7,8 si n=10 iar pasul este 3 atunci se va afisa: 1,4,7,2,5,8,3,6,1,4
Problema 2
Un numar de n copii se gasesc in cerc urmand ca unul dintre ei sa iasa din cerc. N si cele n nume se citesc din fisierul copii.in. In fisierul cantec.in este scris un cantecel despartit in silabe. De la tastatura se citeste numele unui copil de la care se incepe “numaratoarea”. Sa se determine numele copilului care iese din cerc.
Exemplu:
copii.in
5
adi
dan
cristi
ana
alexandru
cantec.in
a la ba la por to ca la
Daca se incepe de la dan iese ana.
Fiind data o lista circulara sa se determine cate elemente are lista
Problema 4.
Sa se determine daca o lista este liniara sau circulara
Problema 5. Cifrul
Un cifru contine n marcaje (valorile de la 1 la n). Din fisierul date.txt se citesc perechi x y reprezentand numarul de rotatii si sensul de rotatie (orar sau antiorar, unde y =1 pt sens orar si y=2 pt sens antiorar). Sa se afiseze codul obtinut. Ex pt marcajele 1,2,3,4,5,6,7,8,9,10 si perechile:
3 1
4 1
2 1
4 2
5 2
se obtine codul 3 6 7 4 10
Problema 6
Problema 7
Sa se descompuna doua liste circulare in doua liste circulare cu numar apropiat de elemente
Problema 8
Sa se grupeze zerourile intr-o lista circulara.