Liste simplu si dublu inlantuite, liniare si circulare
15O lista inlantuita este o structura de date in care obiectele sunt aranjate intr-o anumita ordine.Spre deosebire de un tablou, in care ordinea este determinata de indicii tabloului ,ordinea intr-o lista inlantuita este determinata de un pointer continut in fiecare obiect.Listele inlantuite asigura o reprezentare mai simpla si mai flexibila pentru multimi dinamice, suportand toate operatiile clasice : adauga element,elimina element,cauta element etc nu neaparat eficient.
O lista poate avea una din urmatoarele forme .Ea poate fi simplu inlantuita sau dublu inlantuita,poate fi sortata sau nu si poate fi liniara sau circulara.
O lista dublu inlantuita este caracterizata din 3 campuri :
- back – referinta catre elementul anterior din lista
- value – valoarea elementului (cheie) de la pozitia curenta in lista
- next – referinta catre urmatorul element din lista
Unei liste simplu inlantuite i se omite referinta catre elementul anterior(back).Astfel putem spune ca avem informatii referitoare doar la urmatorul element,informatiile catre anteriorul lipsind.
Daca o lista este sortata crescator elementul din capul listei este elementul minim iar elementul maxim ultimul din lista.Daca o lista este nesortata cheile pot avea diferite valoare,nerespectand o ordine crescatoare sau descrescatoare.
O lista simplu inlantuita este liniara daca ultimul element din lista are referinta nula catre urmatorul element.O lista dublu inlantuita este liniara daca primul element are referinta nula catre elementul precedent iar ultimul element din lista are referinta nula catre urmatorul element din lista.
O lista simplu inlantuita este circulara daca ultimul element din lista pointeaza catre primul din lista.O lista dublu inlantuita este circulara daca primul element din lista pointeaza catre ultimul element din lista iar ultimul element din lista are referinta catre primul. Cred ca ati inteles principiile ce stau la baza nu? 😀
Mai jos avem 2 surse explicate ce reprezinta sursele unor liste dublu inlantuite liniara si circulare nesortate cu majoritatea operatiilor de baza.Ca tema trebuie sa faceti lista simplu inlantuita circulara si liniara (este foarte simplu).
Lista liniara dublu inlantuita
Lista circulara dublu inlantuita
Tema :
1. (Problema lui Joseph) Se considera n persoane aranjate in cerc. Incepand cu o pozitie
particulara p0 se efectueaza numararea persoanelor si, in mod brutal se executa fiecare
cea de-a m-a persoana; cand este executata o persoana, cercul se inchide dupa eliminarea
aceateia. Executia se termina cand ramane o singura persoana; aceasta va ramane in viata.
– Sa scrie o procedura (un modul) care afiseaza persoanele in ordinea in care au fost
executate ;
– Presupunand ca se doreste salvarea unei anume persoane, sa se construiasca un modul
care sa determine pozitia p0 astefel incat, daca numaratoarea incepe cu i0, atunci
persoana salvata sa fie cea dorita.
– Sa se scrie un program C (C++) care sa testeze cele doua module.
2.Se citeste de la intrare un sir de numere intregi.
a) Sa se plaseze numerele citite intr-o lista dublu inlantuita, prin inserari repetate in fata
listei.
b) Sa se afiseze lista creata in ordinea inversa citirii numerelor.
c) Sa se insereze un numar citit de la intrare in fata unei pozitii citite de la intrare.
d) Se se stearga un element aflat in fata unei pozitii citita de la intrare.
In fisierul lista.txt se gaseste un sir de numere intregi scrise toate pe un singur rand,separate prin spatiu.Nu se cunoaste cate nr sunt in fisier.
Sa se creeze llsi cu nr din fisier apoi sa se afiseze cel mai mare dintre aceste numere.Help me pls:(
Dany sa fie clar ca noi nu facem temele, doar iti dau sfaturi
Pentru a citi pana cand ramai fara numere si a determina maximul :
max = -(1<<20); while(scanf("%d",&n) != -1) { adauga_in_lista(n); if(max<n ) max=n; }Referitor la listele inlantuite, ai articolul in fata, ce mai vrei? 🙂
ms mult de ajutor dar eu vreau toata pb
nu se poate?:D
Nu, imi pare rau. 🙂
deci oricand am nevoie de ajutor ma ajuti?
doar sa ma ajuti nu sami spui cum se face:P
Salut!!!
Zimi te rog cum se rezolva urmatarea problema :
De la tastatura se citeste un text t. Caracterele acestuia sunt iinserate (in ordinea in care apar in text )intr-o lista liniara. Sa se insereze in lista caracterul”>” inaintea fiecarei vocale din lista . Afisati Inainte si dupa
Nu rezolvam probleme, doar dam indicatii dar pe forum.
Astept indicatiile …….
Nu vad ca tu sa fi pus o intrebare pe forum. Daca ai pus, inseamna ca nu am vazut-o, dar daca n-ai pus, n-ar fi normal sa pui prima data intrebarea? 😀
hi there! am o probl d genu: sa se creeze o lista circulara simplu inlatuita din care sa se stearga nr negative..
vreau o mica idee..pls:)
eu vreau doar indicatie:)
Se creeaza o lista in care ordina de acces este inversa celei in care sunt citite numerele bla bla bla.
cum pot sa parcurg lista de la coada la cap?
miam dat seama dar mersi oricum 😉
citirea listelor circulare simplu inlantuire se face la fel ca la listele liniare simplu inlantuire?
Aproape la fel. Trebuie doar sa link-uiesti primul cu ultimul element mereu.