LISTE LINIARE DUBLU INLANTUITE
O listă dublu înlănţuită este o structură de date constituită dintr-o succesiune de elemente denumite noduri. Fiecare nod din listă conţine trei părţi: o parte de informaţie (în care sunt memorate informaţiile corespunzătoare nodului, specifice problemei) şi două părţi de legătură (în care este memorată adresa următorului element din listă şi respectiv adresa precedentului element din listă).
Pentru simplitate vom considera, fără a restrânge generalitatea, că informaţiile memorate în nodurile listei sunt numere întregi. Declaraţia structurii care reprezintă un nod dintr-o listă dublu înlănţuită cu informaţii întregi va fi:
struct Nod {
int inf;
struct Nod *urm, *pre; };
typedef struct Nod * Lista;
Inserarea unui nod într-o listă dublu înlănţuită
Pentru inserare vom implementa o funcţie denumită Insert cu trei parametri:
- Prim – pointer care conţine adresa primului nod din listă în care se face inserarea; acest parametru va fi transmis prin referinţă, deoarece în urma inserarii începutul listei se poate modifica;
- p – pointer care conţine adresa nodului din listă după care se face inserarea; daca p este NULL deducem că inserarea noului nod se va face la începutul listei;
- x – informaţia nodului care urmează să fie inserat în listă.
Vom aloca dinamic memorie pentru un nou nod, a cărui adresă o vom reţine în variabila pointer
q. În zona de informaţii vom memora valoarea x (q->inf=x).
La inserare apar două cazuri distincte. Dacă p==NULL noul nod va fi inserat la începutul listei; dacă p!=NULL inserarea se face în interiorul listei.
void Insert (Lista &Prim, Lista p, int x){
Lista q=new Nod;
q->inf=x; q->pre=p;
if (!p) // Inserare la inceputul listei
{q->urm=Prim;
if(Prim) Prim->pre=q;
Prim=q; }
else
{ q->urm=p->urm; p->urm=q;
if(q->urm) q->urm->pre=q;) }
}
Ştergerea unui nod dintr-o listă dublu înlănţuită
Pentru ştergere vom implementa o funcţie denumită Delete cu doi parametri:
- Prim – pointer care conţine adresa primului nod al listei din care se face ştergerea; acest parametru va fi transmis prin referinţă, deoarece în urma ştergerii, începutul listei se poate modifica;
- q – pointer care conţine adresa nodului din listă ce urmează a fi şters
Pentru simplitate vom utiliza doi pointeri suplimentari: p – care reţine adresa nodului ce precedă
nodul de şters şi r care reţine adresa nodului ce succedă nodul de şters
void Delete (Lista &Prim, Lista q){
Lista p=q->pre, r=q->urm;
if(p) p->urm=r;
else Prim=r;
if (r) r->pre=p;
delete q; }
EXEMPLU DE APLICATIE PENTRU EXPLOATAREA LISTELOR LINIARE DUBLU INLANTUITE
În program sunt incluse următoarele biblioteci:
<graphics.h>, <stdlib.h>, <stdio.h>, <conio.h>, <iostream.h>, <fstream.h>, <dos.h>, <string.h>
Lista dublu înlănţuită o creem cu o structură pe care o numim nod, ce conţine 2 pointeri de tip nod numiţi ante şi post, un vector de tip char de 30 de elemente denumit nume şi două variabile de tip float denumite lat şi lng. Liniile de cod pentru structura nod sunt următoarele:
struct nod{
nod * ante;
char nume[30];
float lat, lng;
nod * post;
};
Reprezentarea grafică a nodului este :
În acest document pentru a fi mai uşor de citit şi de parcurs,în reprezentările grafice a nodurilor, adresa nodului in memoria RAM va fi notat cu numere întregi.
Pointerul ante are rolul de a reţine adresa nodului dinaintea celui curent, în cazul în care nodul curent este primul nod din listă atunci ante va avea valoarea 0.
Pointerul post are rolul de a reţine adresa nodului ce urmează după cel curent, în cazul în care nodul curent este ultimul din listă atunci post va avea valoarea 0.
char nume[30] este un vector de tip caracter ce reţine maxim 30 de litere. Acest vector va reţine numele oraşului din listă.
Variabilele de tip float lat şi lng sunt două variabile ce sunt folosite pentru a reţine latitudinea şi longitudinea oraşului din listă.
În afară de struct nod , avem şi pointeri de tip nod ce ne vor ajuta să parcurgem lista înlănţuită.
Aceşti pointeri sunt scrişi astfel în program:
nod * curent , * prim, *ultim, * ajut, * aux;
Mai avem şi alte variabile care sunt scrise astfel în program:
int n=0, i, poz, pozcautat, gasit;
char oras[30], numefis[25];
Variabila n este folosită în program ca drept contor pentru a şti câte oraşe conţine lista.
Variabilele de tip int i, poz, pozcautat, gasit şi char oras[30] sunt folosite pentru a căuta un oraş în listă. Avem nevoie de ele în mai multe funcţii din program, cum ar fi: void inmijloc() , void stergint(), void modific(), void caut() .
char numefis[25] ne este de folos în program pentru a reţine numele fişierului în care salvăm lista, sau numele listei din care încărcăm lista.
A. Crearea unei liste noi
Instrucţiunea prim = new nod are rolul de a aloca în memoria RAM o adresă pentru un nou nod.
Adresa noului nod va fi reţinuta de pointerul prim
Următoarele instrucţiuni din cadrul funcţiei au rolul de a îi solicita pe rând utilizatorului să introducă numele, latitudinea şi longitudinea oraşului
Pentru ca aceste informaţii sa fie stocate la adresa reţinuta de pointerul prim sunt folosite următoarele instrucţiuni.
- gets(prim -> nume) care stocheaza numele introdus de utilizator în variabila nume.
- cin >> prim -> lat care stocheaza valoarea introdusă de utilizator în variabila lat.
- cin >> prim -> lng care stocheaza valoarea introdusă de utilizator în variabila lng.
Având in vedere ca funcţia in care ne aflăm crează primul nod din lista rezultă că partea de ante si post a nodului trebuie sa aibă valoarea 0. Pentru a face acest lucru folosim următoarele instrucţiuni, şi presupunem că adresa nodului creat este 23.
Următoarea instructiune din cadrul funcţiei este ultim = prim; . Îi atribuim pointerului ultim adresa reţinută de prim deoarece acest prim nod este deocamdată şi primul şi ultimul din lista noastră.
Ultima instrucţiune este : n=1; Avem un oraş în lista noastră.
.B. Parcurgerea listei de la stanga la dreapta
Primul cout din funcţie anunţa câte noduri (oraşe) are lista.
Al doilea cout ne spune ce face mai exact funcţia, adică opţiunea aleasă din lista de meniuri, şi anume că va afişa lista de la stanga la dreapta.
În această funcţie ne vom folosi de pointerul curent. Care îi dăm adresa reţinută de pointerul prim, folosind instrucţiunea curent=prim;
Pentru a parcurge lista, ne vom folosi de un ciclu while, care va rula, trecând prin fiecare nod atâta timp cât partea de post a nodului va fi diferită de 0. Ciclul while conţine două instrucţiuni, prima instrucţiune este un cout , care afisează pe ecran numele, latitudinea si longitudinea ce sunt stocate în memoria RAM către care arată pointerul curent. A doua instrucţiune din ciclul while ce realizează trecerea la următorul nod este:curent=curent->post;
Întrucât ciclul while ajunge la ultimul nod, dar afiseaza numele, latitudinea şi longitudinea penultimului nod, vom executa si următorul cout :
cout<<curent->nume<<" "<<curent->lat<<" "<<curent->lng<<endl;
Presupunem că avem 3 noduri (oraşe) în listă cu adresele: 23, 10, 30.
Funcţia parcurge următorii paşi:
1) Se afişează informaţia ce se găseşte la primul nod
2) Se execută instrucţiunea : curent = curent->post
3) Se verifică condiţia (curentpost!=0) , se trece la următorul nod
4) Se afişează informaţia ce se găseşte la adresa reţinută acum de pointerul curent adică 10
5) Se execută instrucţiunea : curent = curent->post
6) Se verifică condiţia (curentpost!=0) , se iese din ciclul while
7) Se execută instrucţiunea : cout<<curent->nume<<" "<<curent->lat<<" "<<curent->lng<<endl;
C. Parcurgerea listei de la dreapta la stanga
D. Inserarea unui nod in interiorul listei
E. Inserarea unui nod pe prima pozitie
F. Inserarea unui nod pe ultima pozitie
G. Stergerea unui nod din interiorul listei
H. Stergerea primului nod
I. Stergerea ultimului nod
J. Modificarea unui nod
K. Reprezentarea grafica a listei
K. Salvarea listei
L. Cautarea unui nod in lista
M. Meniul principal
N. Citirea listei din fisier
O. Meniul de pornire
P. si ... functia main()
