Liste simplu înlănţuite alocate dinamic

Liste simplu înlănţuite alocate dinamic

Liste simplu înlănţuite alocate dinamic

Colegiul Naţional de Informatică “Spiru Haret” Suceava

profesor Gabriela – Rodica Freitag

Cuprins:

Noţiunile de pointer şi variabilă dinamică

Structuri de date

Lista. Definiţie. Declarare

Operaţii cu liste simplu înlănţuite

Aplicaţii

Alocarea dinamică este metoda prin care unei variabile de memorie sau unei structuri de date i se alocă spaţiu sau se eliberează spaţiul de memorie ocupat de ea în timpul execuţiei programului, în funcţie de necesităţi. Variabilele care folosesc alocarea dinamică se numesc variabile dinamice.

Variabilele dinamice nu se declară, nu au nume şi se folosesc în program prin intermediul variabilelor de tip pointer alocate static. O variabilă de tip pointer se caracterizează prin faptul că valorile pe care le poate memora sunt adrese de memorie. Declarare: tip * nume unde: tip - tipul datei socată la adresa indicată de pointer

* - operatorul de referinţă nume - numele variabilei de tip pointer

În momentul în care în program trebuie folosită o variabilă dinamică, se cere sistemului să i se aloce spaţiu în HEAP. Pentru alocare se foloseşte operatorul new:

nume=new tip;iar pentru eliberarea spaţiului de memorie alocat în Heap se foloseşte operatorul delete:

delete nume;

cuprins

Structura de date este o noţiune abstractă, prin care se înţelege un ansamblu de date caracterizat prin relaţiile existente între ele şi a operaţiilor care pot fi efectuate cu datele respective. Clasificarea structurilor de date se poate face în funcţie de:

tipul datelor- structuri de date omogene, adică toate datele componente sunt de acelaşi tip (ex. tabloul)

- structuri de date neomogene, adică pot conţine date de tipuri diferite(ex. înregistrare). alocarea memoriei:

- static - structura de date ocupă o zonă de memorie de dimensiune fixă, alocată pe întreaga durată a execuţiei blocului în care este declarată. - dinamic - structura de date ocupă o zonă de memorie de dimensiune variabilă, alocată pe parcursul execuţiei programului la cererea explicită a programatorului.

Structura de date este o noţiune abstractă, prin care se înţelege un ansamblu de date caracterizat prin relaţiile existente între ele şi a operaţiilor care pot fi efectuate cu datele respective. Clasificarea structurilor de date se poate face în funcţie de:

tipul datelor- structuri de date omogene, adică toate datele componente sunt de acelaşi tip (ex. tabloul)

- structuri de date neomogene, adică pot conţine date de tipuri diferite(ex. înregistrare). alocarea memoriei:

- static - structura de date ocupă o zonă de memorie de dimensiune fixă, alocată pe întreaga durată a execuţiei blocului în care este declarată. - dinamic - structura de date ocupă o zonă de memorie de dimensiune variabilă, alocată pe parcursul execuţiei programului la cererea explicită a programatorului.

cuprins

Nodul este o unitate de informaţie elementară care poate conţine informaţii utile şi date de legătură.Lista este o structură de date constituită dintr-o succesiune de elemente, numite noduri, aflate într-o relaţie de ordine.

Definiţii Există următoarele tipuri de liste: lista liniară simplu înlănţuită - legăturile între noduri sunt liniare şi într-un singur sens. lista liniară dublu înlănţuită – fiecare nod este legat prin pointeri atât de nodul anterior, cât şi de nodul următor. lista circulară – ultimul nod adresează primul nod.

struct nod{ tip info; nod *urm(*ant); }; nod *prim, *ultim;

info – va conţine informaţia utilă memorată în nodul curent. Tipul acestui câmp poate fi orice tip C++ .

urm - câmp ce reţine adresa nodului următor (sau ant – adresa nodului anterior).

Operaţiile elementare

crearea primului nod (iniţializarea listei)

inserarea unui element într-o listă extragerea unui element dintr-o listă accesarea unui element dintr-o listă afişarea elementelor unei liste

Declararea listei înlănţuite

cuprins

Operaţiile elementare care se pot executa asupra unei liste liniare simplu înlănţuite:

O listă liniară simplu înlănţuită este o structură de forma:

1. Crearea primului nod2. Inserarea unui nod

adăugarea unui nod la începutul listei adăugarea unui nod la sfârşitul listei inserarea unui nod înaintea unui anumit nod din listă inserarea unui nod după un anumit nod din listă

3. Ştergerea unui nod ştergerea primului nod din listă ştergerea ultimului nod din listă ştergerea unui anumit nod din listă

4. Căutarea unui element în listă

5. Afişarea elementelor listei

cuprins

adr1

… infon-1 adrninfon-2 adrn-1 infon

adr2 adrn-2 adrn-1 adrn

NULL info1 adr2 info2 adr3

info NULL

prim

Crearea unei liste liniare simplu înlănţuite

se alocă spaţiu de memorie în zona HEAP prim=new nod; se completează informaţia utilă din noul nod creat

cin>>priminfo; se completează câmpul urm cu valoarea NULL, deoarece nodul este unic în listă primurm=NULL; se păstrează valoarea variabilei prim şi în variabila ultim

ultim=prim;

void creare (nod *&prim, nod *&ultim){ prim=new nod;

cin>>priminfo;primurm=NULL; ultim=prim;

}

cuprins

| initializare LSI | | adăugare la inceput | | adăugare la sfârşit | | inserare inaintea unui nod | | inserare după un nod | | ştergerea primului nod | | ştergerea ultimului nod | | ştergerea unui nod | | căutarea unui nod | | afişarea LSI |

se alocă spaţiu de memorie în zona HEAP prim=new nod; se completează informaţia utilă din noul nod creat

cin>>priminfo; se completează câmpul urm cu valoarea NULL, deoarece nodul este unic în listă primurm=NULL; se păstrează valoarea variabilei prim şi în variabila ultim

ultim=prim;

, ultim

se alocă memorie în zona HEAPp=new nod;

se citeşte informaţia utilă din noul nodcin>>pinfo;

se leagă nodul creat in faţa primului nod al listei

purm=prim; se modifică adresa primului nod al listei

prim=p;

void adăugare_inc ( nod *&prim){ nod *p=new nod;

cin>>pinfo;purm=prim;prim=p;

}

Adăugarea unui nod la începutul listei

DEMO

cuprins


se alocă memorie în zona HEAPp=new nod;

se citeşte informaţia utilă din noul nodcin>>pinfo;

se leagă nodul creat in faţa primului nod al listei

purm=prim; se modifică adresa primului nod al listei

prim=p;

void adaugare_inc ( nod *&prim){ nod *p=new nod;

cin>>pinfo;purm=prim;prim=p;

}

Adăugarea nodului cu informaţia 4 la începutul listei

cuprins

adr1

2 adr31 adr2 3

adr2 adr3

NULL

primprimp

4 adr1


se alocă spaţiu de memorie în zona HEAP p=new nod; se completează informaţia utilă din noul nod creat cin>>pinfo; se completează câmpul urm cu valoarea NULL,

deoarece nodul nou este ultimul în listă purm=NULL; se leagă de listă noul nod ultimurm=p; se modifică adresa ultimului nod ultim=p;

void adăugare_sf ( nod *&ultim){ nod *p=new nod;

cin>>pinfo;purm=NULL;ultimurm=p; ultim=p;

}

Adăugarea unui nod la sfârşitul listei

DEMO

se alocă spaţiu de memorie în zona HEAP p=new nod; se completează informaţia utilă din noul nod cin>>pinfo; se completează câmpul urm cu valoarea NULL, deoarece nodul nou este ultimul în listă purm=NULL; se leagă de listă noul nod ultimurm=p; se modifică adresa ultimului nod ultim=p;

void adăugare_sf ( nod *&ultim){ nod *p=new nod;

cin>>pinfo;purm=NULL;ultimurm=p; ultim=p;

}

Adăugarea nodului cu informaţia 4 la sfârşitul listei

2 adr31 adr2 3

adr2adr3

NULL

prim ultim

4

p

NULLp

ultim

cuprins


se alocă spaţiu de memorie în zona HEAP

p=new nod; se completează informaţia utilă din

noul nod creatcin>>pinfo;

se va căuta în listă nodul ce conţine în câmpul info valoarea k (fie q adresa acestui nod) şi se va crea legatura intre listă şi noul nod

purm=qurm;qurm=p;

Inserarea unui nod după nodul ce are memorat în câmpul info valoarea k

DEMO

void ins_după (nod *prim, int k){ nod *p=new nod;

cin>>pinfo; nod *q=prim;while (qinfo!=k)

q=qurm;purm=qurm;

qurm=p;}

Inserarea nodului cu informaţia 4 după nodul a cărui informaţie este 2

adr1

cuprins


se alocă spaţiu de memorie în zona HEAP

p=new nod; se completează informaţia utilă din

noul nod creatcin>>pinfo;

se va căuta în listă nodul ce conţine în câmpul info valoarea k (fie q adresa acestui nod)

se va crea legatura intre listă şi noul nod

purm=qurm;qurm=p;

void ins_după (nod *prim, int k){ nod *p=new nod;

cin>>pinfo; nod *q=prim;while (qinfo!=k)

q=qurm;purm=qurm;

qurm=p;}

1 adr2 3 NULL

prim ultim

4

p

2 adr3

adr3

p

q

se alocă spaţiu de memorie în zona HEAP pentru noul nod

p=new nod; se completează informaţia utilă din noul nod

cin>>pinfo; se va căuta în listă nodul anterior celui ce

conţine în câmpul info valoarea k (fie q adresa acestui nod) şi se va crea legatura intre listă şi noul nod

purm=qurm;qurm=p;




conţine în câmpul info valoarea k (fie q adresa acestui nod) şi se va crea legatura intre listă şi noul nod

purm=qurm;qurm=p;

void ins_înainte ( nod *&prim, int k ){ nod *p=new nod;

cin>>pinfo;if(priminfo==k){ purm=prim;

prim=p;}else{ nod *q=prim;

while(qurm info!=k)q=qurm;

purm=qurm;qurm=p;

}}





purm=qurm;qurm=p;

}}

Inserarea unui nod înaintea nodului ce are memorat în câmpul info valoarea k

DEMO




conţine în câmpul info valoarea k (fie q adresa acestui nod)

se va crea legatura intre listă şi noul nodpurm=qurm;qurm=p;




conţine în câmpul info valoarea k (fie q adresa acestui nod)

se va crea legatura intre listă şi noul nodpurm=qurm;qurm=p;





purm=qurm;qurm=p;

}}





purm=qurm;qurm=p;

}}

adr1

Inserarea nodului cu informaţia 4 înainte de nodul a cărui informaţie este 2

adr2 3

adr2 adr3

NULL

prim ultim

4p

2 adr3

adr2

p1

cuprins


q

se reţine adresa primului nod în pointerul p p=prim; se modifică adresa primului nod cu adresa nodului

urmator prim=purm;

se şterge efectiv primul nod adresat de p eliberând memoria ocupată

delete p;

se reţine adresa primului nod în pointerul p p=prim; se modifică adresa primului nod cu adresa nodului

urmator prim=purm;

se şterge efectiv primul nod adresat de p eliberând memoria ocupată

delete p;

void şterg_prim (nod *&prim){ nod * p=prim;

prim=purm;delete p;

}

void şterg_prim (nod *&prim){ nod * p=prim;

prim=purm;delete p;

}

Ştergerea primului nod

adr2 3

adr2 adr3prim ultim

42 adr31 NULLultim

prim

cuprins


p

se mută pointerul p de la primul la penultimul nodp=prim;while (purm!=ultim)

p=purm; se şterge fizic ultimul nod

delete ultim; se completează câmpul de adresă al penultimului nod

cu valoarea NULL, deoarece nodul p este acum ultimul nod din listă

purm=NULL; se modifică pointerul ultim cu adresa ultimului nod

ultim=p;

void şterg_ultim ( nod *&ultim ){ nod *p=prim;

while (purm!=ultim) p=purm;

delete ultim;purm=NULL;ultim=p;

}

Ştergerea ultimului nod

adr2 3

adr2 adr3prim ultim

42 adr31 NULLultim

ultim

cuprins


NULL

pp p

fie q adresa nodului anterior celui de şters, transmisă prin parametru

se obţine adresa nodului de şters p=qurm;

se leagă nodul q de nodul următor nodului de ştersqurm=purm;

se şterge efectiv nodul de la adresa pdelete p;

void şterg_nod ( nod *q ){ nod *p=qurm;

qurm=purm;delete p;

}

Ştergerea nodului cu informaţia 2 din listă

adr2 3

adr2 adr3prim ultim

42 adr31 NULLultimadr3

cuprins


q p

se pleacă de la primul nod al listei salvându-se adresa lui în variabila p

cât timp nu s-a ajuns la ultimul nod al listei execută - se afişează informaţia din nodul curent - se trece la următorul nod din listă

void afişare ( nod *prim ){ nod *p=prim;

while(p!=NULL){ cout<<pinfo;

p=purm;}

}

void afişare ( nod *prim ){ nod *p=prim;

while(p!=NULL){ cout<<pinfo;

p=purm;}

}

Afişarea nodurilor listei

... NULL info1 adr2 info2 adr3 infon-1 adrninfon-2 adrn-1 infon

adr2adr1 adrn-2 adrn-1 adrn

cuprins


se citeşte în variabila x informaţia pe care o căutăm

se parcurge lista de la primul nod către ultimul comparându-se de fiecare dată x cu informaţia din nodul curent

funcţia căutare va returna adresa primului nod cu informaţia x din listă sau NULL dacă nu există un astfel de nod

se citeşte în variabila x informaţia pe care o căutăm

se parcurge lista de la primul nod către ultimul comparându-se de fiecare dată x cu informaţia din nodul curent

funcţia căutare va returna adresa primului nod cu informaţia x din listă sau NULL dacă nu există un astfel de nod

nod *căutare (nod *prim){ int x;

cin>>x;nod *p=prim;while(p!=NULL && pinfo!=x)

p=purm;return p;

}

nod *căutare (nod *prim){ int x;

cin>>x;nod *p=prim;while(p!=NULL && pinfo!=x)

p=purm;return p;

}

Căutarea nodului ce conţine în câmpul info valoarea reţinută în variabila x

... NULL info1 adr2 info2 adr3 infon-1 adrninfon-2 adrn-1 infon

adr2adr1 adrn-2 adrn-1 adrn

cuprins


1. Se citesc dintr-un fişier text numere naturale. Se cere afişarea acestora în ordine crescătoare folosind sortarea prin inserţie.

Ideea de bază a metodei constă în a considera primele valori sortate, urmând să inserăm valoarea curentă citită din fişier în şirul deja sortat. Prin utilizarea listelor înlănţuite, inserţia este mai simplă întrucât nu necesită deplasarea componentelor ca în cazul vectorilor.

>>>cuprins

2. Se citesc dintr-un fişier text numere naturale. Se cere să se creeze o listă simplu înlănţuită, iar apoi să se inverseze legăturile dintre noduri.

După inversarea legăturilor, primul nod va deveni ultimul, al doilea nod al listei iniţiale va indica spre primul, al treilea către al doilea, etc.. Vom utiliza trei pointeri p, q şi r (p adresează primul nod al listei cu legăturile inversate, q, primul nod al listei cu legăturile iniţiale, iar r, nodul următor nodului q).

>>>cuprins

3. Fie două polinoame P(x) şi Q(x). Să se afişeze polinomul sumă S(x)=P(x)+Q(x).

Bibliografie >>>cuprins

Fişierul text conţine date referitoare la monoamele celor două polinoame. Polinoamele se memorează cu ajutorul a două liste simplu înlănţuite ordonate descrescător după gradul necunoscutei. Polinomul sumă se obţine folosind algoritmul de interclasare a celor două liste într-o altă listă.

1. George Daniel Mateescu, Informatică pentru liceu şi bacalaureat. Manual clasa a XI-a, ed. Donaris, Sibiu 2006

2. Mariana Miloşescu, Informatică intensiv. Manual clasa a XI-a, ed. Didactică şi Pedagogică, Bucureşti 2006

3. Dana Lica, Doru Popescu Atanastasiu, Radu Boriga, Fundamentele programării. Culegere de probleme pentru clasele IX-XI, ed. L&S Soft, Bucureşti 2003

4. Clara Ionescu, Adina Bălan, Informatică pentru grupele de performanţă, clasa a X-a, ed. Dacia Educaţional, Cluj-Napoca 2004

home

Liste simplu înlănţuite alocate dinamic

Documents

Transcript of Liste simplu înlănţuite alocate dinamic