vineri, 14 martie 2014
vineri, 7 martie 2014
Liste simplu înlănțuite
Liste simplu înlănțuite
Listele simplu înlănțuite sunt structuri de date dinamice omogene.
Spre deosebire de masive, listele nu sunt alocate ca blocuri omogene de memorie, ci ca elemente
separate de memorie. Fiecare nod al listei conține, în afară de informația utilă, adresa următorului element. Aceasta organizare permite numai acces secvențial la elementele listei.
Pentru accesarea listei trebuie cunoscută adresa primului element (numită capul listei); elementele următoare sunt accesate parcurgând lista.
Lista simplu înlănțuită poate fi reprezentată grafic astfel:
Listele simplu înlănțuite sunt structuri de date dinamice omogene.
Spre deosebire de masive, listele nu sunt alocate ca blocuri omogene de memorie, ci ca elemente
separate de memorie. Fiecare nod al listei conține, în afară de informația utilă, adresa următorului element. Aceasta organizare permite numai acces secvențial la elementele listei.
Pentru accesarea listei trebuie cunoscută adresa primului element (numită capul listei); elementele următoare sunt accesate parcurgând lista.
Lista simplu înlănțuită poate fi reprezentată grafic astfel:
Probleme propuse
Probleme propuse:
1. Într-o stivă au fost introduse în această ordine, numerele 5, 7, 3, 8. Precizaţi numărul minim de
elemente care trebuie extrase din stivă pentru a fi siguri că s-a extras inclusiv elementul cu valoarea 3 şi care este elementul aflat în vârful stivei după extragerea acestui element?
2. Care va fi valoarea elementului aflat în vârful unei stive iniţial vidă şi care este numărul de elemente rămase în stivă, după efectuarea, în această ordine, a următoarelor operaţii: se introduce valoarea 3; se introduce valoarea 7; se introduce valoarea 5; se extrage un element; se introduce valoarea 2; se introduce valoarea 4; se extrage un element.
3. Se consideră o stivă în care iniţial au fost introduse, în această ordine, elementele 1,2,3,4,5,6. Dacă se notează cu PUSH x operaţia prin care se adaugă un element cu informaţia x în stivă şi cu POP operaţia prin care se elimină un element din stivă, care este elementul aflat în mijlocul stivei după executării secvenţei de operaţii: POP; PUSH 7; PUSH 8; POP; POP;?
1. Într-o stivă au fost introduse în această ordine, numerele 5, 7, 3, 8. Precizaţi numărul minim de
elemente care trebuie extrase din stivă pentru a fi siguri că s-a extras inclusiv elementul cu valoarea 3 şi care este elementul aflat în vârful stivei după extragerea acestui element?
2. Care va fi valoarea elementului aflat în vârful unei stive iniţial vidă şi care este numărul de elemente rămase în stivă, după efectuarea, în această ordine, a următoarelor operaţii: se introduce valoarea 3; se introduce valoarea 7; se introduce valoarea 5; se extrage un element; se introduce valoarea 2; se introduce valoarea 4; se extrage un element.
3. Se consideră o stivă în care iniţial au fost introduse, în această ordine, elementele 1,2,3,4,5,6. Dacă se notează cu PUSH x operaţia prin care se adaugă un element cu informaţia x în stivă şi cu POP operaţia prin care se elimină un element din stivă, care este elementul aflat în mijlocul stivei după executării secvenţei de operaţii: POP; PUSH 7; PUSH 8; POP; POP;?
Stiva
Stiva e un tip special de listă la care toate inserțiile și suprimările se execută la un singur capăt, numit vârful stivei. Stiva e o listă tip LIFO (Last In First Out).
Asupra tipului abstract de date stivă sunt definiți următorii cinci operatori:
1.INIȚIALIZARE(S) - face stiva S vidă ( inițializează lista corespunzătoare )
2.VIRFST(S) - furnizează elementul din vârful stivei ( deci primul nod al listei )
3.POP(S) - suprimă elementul din vârful stivei
4.PUSH(x,S) - inserează elementul x în vârful stivei pe care îl actualizează
5.STIVID(S) - funcție booleană ce e adevărată dacă stiva este vidă.
Cele mai avantajoase implementări ale structurii de date stivă sunt cele cu ajutorul tipului pointer și al tipului tablou.
Despre ultimul element pus pe stivă se spune că este vârful stivei, despre primul că este baza stivei.
Vârful stivei se modifică de fiecare dată când punem/eliminam un element din stiva.
Cu alte cuvinte accesul este permis doar la vârful stivei:
· un element se poate pune în stivă numai după elementul aflat în vârful stivei şi după aceasta operație el ajunge vârful stivei;
· se poate scoate de pe stiva numai elementul aflat în vârful stivei şi după aceasta operație în vârful stivei rămâne elementul care a fost pus pe stiva înaintea lui.
Stiva poate fi implementată atât static, folosindu-ne de un vector unidimensional cât şi dinamic, folosindu-ne de o listă simplu înlănțuită.
Coada
Coada e tot un tip special de listă în care elementele sunt inserate la un capăt ( spate ) și sunt suprimate la celălalt ( față ); se mai numesc liste FIFO ( First In First Out ), adică de tip primul venit, primul servit.
Se definesc următorii operatori:
1.INIȚIALIZARE(C) - face coada ( lista ) vidă
2.FATZA(C) - funcție ce returnează primul element al cozii C
3.ADAUGĂ(x,C) - inserează elementul x în spatele cozii
4.SCOATE(C) - suprimă primul element al lui C
5.VID(C) - funcție ce e adevărată dacă coada este vidă.
Cele mai uzuale implementări ale cozii sunt cu ajutorul tipului pointer și al tablourilor circulare.
Coada bazată pe prioritate e structura de date abstractă care permite inserția unui nou element și suprimarea celui mai mare element dintre cele existente. Structura diferă de coadă ( din care se suprimă primul venit, deci elementul cel mai vechi ) și de stivă ( din care se suprimă ultimul venit, deci cel mai nou ).
Asupra acestei structuri de date, ale cărei elemente sunt articole cu chei ( sau priorități ), se definesc operațiile :
GENEREAZĂ - o coadă bazată pe priorități, pornind de la N elemente ( succesiune de inserții )
INSEREAZĂ - un nou element
EXTRAGE - cel mai mare element
ÎNLOCUIRE - a celui mai mare element cu unul nou, mai puțin prioritar ( inserție + suprimare )
SCHIMBĂ - prioritatea unui element ( suprimare + inserție )
SUPRIMĂ - un element oarecare, precizat
REUNEȘTE - două cozi în una singură.
Ca implementări a acestei structuri de date, sînt mai uzuale cele ce folosesc liste neordonate, liste ordonate după prioritate, ansamble.
vineri, 14 februarie 2014
Liste
O listă este o colecție de elemente de informație (noduri) aranjate intr-o anumită ordine. Lungimea unei liste este numărul de noduri din listă. Structura corespunzătoare de date trebuie să ne permită să determinăm eficient care este primul/ultimul nod in structură și care este predecesorul/succesorul unui nod dat
(dacă există). Iată cum arată cea mai simplă listă, lista liniară:
O listă circulară este o lista în care, după ultimul nod, urmează primul nod, deci fiecare nod are succesor si predecesor. Câteva dintre operațiile care se efectuează asupra listelor sunt: inserarea
(adăugarea) unui nod, extragerea (ștergerea) unui nod, concatenarea unor liste, numărarea elementelor unei liste etc. Implementarea unei liste se realizează în două moduri: secvențial și înlănțuit.
Implementarea secvențială se caracterizează prin plasarea nodurilor în locații succesive de memorie, în conformitate cu ordinea lor în listă. Avantajele acestui mod de implementare sunt accesul rapid la predecesorul/succesorul unui nod și găsirea rapidă a primului/ultimului nod. Dezavantajele sunt modalitățile relativ complicate de înserarea/ștergere a unui nod și faptul că, în general, nu se folosește
întreaga memorie alocată listei: Implementarea înlănțuită se caracterizează prin faptul că fiecare nod conține
două părți: informația propriu-zisă și adresa nodului succesor. Alocarea memoriei pentru fiecare nod se poate face în mod dinamic, în timpul rulării programului. Accesul la un nod necesită parcurgerea tuturor predecesorilor săi, ceea ce conduce la un consum mai mare de timp pentru această operație. În schimb, operațiile de inserare/ștergere sunt foarte rapide. Se consumă exact atât spațiu de memorie
cât este necesar dar, evident, apare un consum suplimentar de memorie pentru înregistrarea legăturii către nodul succesor. Se pot folosi două adrese în loc de una, astfel încât un nod să conțină pe lângă adresă nodului succesor și adresă nodului predecesor. Obtinem astfel o lista dublu inlantuita, care poate fi traversată
în ambele direcții.
Listele înlănțuite pot fi reprezentate prin tablouri. în acest caz, adresele
nodurilor sunt de fapt indici ai tabloului.
O alternativă este să folosim două tablouri val și next astfel: să memorăm informația fiecarui nod în locația val[i], iar adresa nodului său succesor in locația next[i]. Indicele locatiei primului nod este memorat în variabila p. Vom conveni că, pentru cazul listei vide, să avem p =0 și next[u] = 0 unde u reprezintă ultimul nod din lista. Atunci, val[p] va conține informația primului nod al listei, next[p] adresa
celui de-al doilea nod, val[next[p]] informația din al doilea nod, next[next[p]] adresa celui de-al treilea nod, etc. Acest mod de reprezentare este simplu dar apare problema gestionării locațiilor libere. O soluție este să reprezentăm locațiile libere tot sub formă unei liste înlănțuite. Atunci, ștergerea unui nod din lista
inițială implică inserarea sa în listă cu locații libere, iar inserarea unui nod în lista inițială implică ștergerea sa din listă cu locații libere. Pentru implementarea listei de locații libere, putem folosi aceleași tablouri dar avem nevoie de o altă variabilă, freehead, care să conțină indicele primei locații libere din val și next. Folosim
acelea și convenții: dacă freehead =0 înseamnă că nu mai avem locații libere, iar
next[ul] = 0 unde ul reprezintă ultima locație liberă.
vineri, 24 ianuarie 2014
Structuri - noțiuni fundamentale
Aspecte teoretice
Există situaţii
în care tipurile de date învăţate până în prezent nu ne sunt de mare folos.
Presupunem că
dorim să prelucrăm date referitoare la mai multi elevi.
Astfel, pentru
fiecare elev cunoaştem:
1. Numele – char
[20];
2. Prenumele –
char[20];
3. Media la
matematică – float;
4. Media la
informatică –float;
5. Vârsta – int;
Observăm că
informaţiile referitoare la un elev sunt de tipuri eterogene: şiruri de
caractere, numere reale sau întregi. Cum am putea rezolva problema cu ajutorul
cunoştinţelor de care dispunem? Ar fi necesari 5 vectori, câte unul pentru
fiecare informaţie. O astfel de abordare este greoaie şi inflexibilă. Este mult
mai util să folosim un tip de dată prin care fiecărui elev să-i corespundă o singură
înregistrare.
Soluţia C++
constă în folosirea tipului de date struct, care permite gruparea sub aceeaşi
denumire a mai multor variabile (numite câpuri) de tipuri diferite, cât şi
accesul şi operarea cu aceste câmpuri. Tipul struct mai poartă şi denumirea de
tip de înregistrare.
O structură este
compusă dintr-un număr de componente de anumite tipuri.Componentele structurii se
numesc câmpuri.
Fiecare câmp
trebuie să aparţină unui tip de date deja definit sau unui tip standard.
A. 1. Sintaxa declarării unei structuri:
struct [nume_structura] {
tip_1 camp_1;
tip_2 camp_2;
………………
tip_n camp_n;
} [ lista_variabile_structura ];
Exemplul 1: Se defineşte structura elev care are 5 câmpuri
A. 1. Sintaxa declarării unei structuri:
struct [nume_structura] {
tip_1 camp_1;
tip_2 camp_2;
………………
tip_n camp_n;
} [ lista_variabile_structura ];
Exemplul 1: Se defineşte structura elev care are 5 câmpuri
Obs: Cele două structuri sunt echivalente, câmpurile care au acelaşi tip de date pot fi declarate în cadrul aceleiaşi declarări de tip, separate prin virgulă.
A.2 Există două posibilităţi de declarare a variabilelor care alcătuiesc structura:
1. Scriind la sfârşit numele variabilelor:
struct Elev
{ char nume[20], prenume[20];
float media_mate, media_info;
int varsta;
} e1,e2;
2. Declarând variabilele aşa cum suntem obişnuiţi:
Elev e1, e2;
Definiţia structurii poate fi făcută:
În cadrul funcţiei main()
Înaintea funcţiei main() (caz recomandat)
OBS: Numele structurii şi lista variabilelor pot lipsi dar nu simultan.
În cazul în care numele structurii lipseşte spunem că variabilele au tip structură anonim.
A.3. Sintaxa de definire a unui tip structură:
typedef struct {
tip_1 camp_1;
tip_2 camp_2;
………………
tip_n camp_n;
} nume_tip;
A.4. Accesarea unui câmp al unei variabile a de tip structură, se face astfel:
a.camp_1;
a.camp_2;
…………
Pentru accesul la câmpurile unei variabile de tip struct se foloseşte operatorul de
selecţie directă, notat cu ‘.’, operator cu prioritate maximă.
Dacă inr este o variabilă de tipul Elev atunci:
-inr.nume – reprezintă şirul nume al variabilei inr;
-inr.nume[0] - reprezintă primul caracter al şirului nume;
-inr.nota_mate – reprezintă câmpul nota_mate al variabilei inr.
Între două variabile de acelaşi tip struct se poate folosi atribuirea.
Dacă inr1, inr2 sunt două variabile de tip elev, prin atribuirea inr1=inr2, variabila inr1
ia aceeaşi valoare ca variabila inr2. O astfel de atribuire se mai numeşte copiere bit cu bit.
Exemplu 4:
typedef struct {
char nume [20];
char prenume [20];
float media;
} Elev;
Elev S;
Accesul variabilei de tip struct S la câmpurile nume,
prenume, medie se face astfel:
S.nume;
S.prenume;
S.media;
B. 1. Citirea unei variabile de tip structură:
struct nume_structura{
tip_1 camp_1;
tip_2 camp_2;
………………
tip_n camp_n;
} a;
Exemplu 5:
typedef struct {
char nume [20];
char prenume [20];
float media;
}Elev;
Elev e;
B.2. Afisarea unei variabile de tip structura:
struct nume_structura{
tip_1 camp_1;
tip_2 camp_2;
………………
tip_n camp_n;
} a;
C. Structuri imbricate
OBSERVAŢIE: Este posibilă definirea unei structuri ale cărei componente sunt de tipul structură,
definite anterior. Câmpurile de tip structură se numesc structuri imbricate (incluse).
Exemplu 7:
struct Adresa{
char strada [20];
char cartier [20];
int nr;
};
typedef struct {
char nume [20];
float media;
Adresa detalii;
}Elev;
Elev S;
Accesarea componentelor variabilei S se face astfel:
S.nume
S.detalii.strada
S.detalii.cartier
S.detalii.nr
D. Vectori de structuri (înregistrări)
Se poate declara un tablou cu elemente de tip structură.
Exemplu 8:
typedef struct {
char nume [20];
char prenume [20];
float media;
}Elev;
Elev a[20];
D.1. Citirea a “n” componente ale vectorului “a” se poate face astfel
D.2. Afisarea a “n” componente ale vectorului “a” se poate face astfel:
Asocierea unui nume pentru un tip de dată
Tipurile predefinite ale limbajului (de exemplu int, char, float) se identifică printr-un nume. După
cum am văzut şi la definirea unui tip struct îi putem atribui un nume.
De fapt, programatorul poate asocia un nume oricărui tip de date, indiferent dacă acesta este un tip predefinit
sau definit de el, utlizând instrucţiunea typedef:
Se recomandă ca numele tipului de date nou Nume_tip să fie scris cu prima literă mare, astfel încât poate să
fie foarte uşor diferenţiat de un tip standard (predefinit). Numele asociat şi descrierea tipului sunt sinonime .
Aplicații (structuri de date)
Problema 2.
Într-o bibliotecă avem un număr de n cărți.Pentru fiecare carte se citește titlul, autorul și prețul.Să se afișeze listele cărților (titlul și prețul) în ordinea descrescătoare a prețului.
#include <iostream>
#include<cstring>
using namespace std;
typedef struct carti
{
char titlu[50];
char autor[50];
float pret;
char aux1[50],aux2[50];
};
carti v[100];
int main()
{int i,j,n,aux;
char aux1[50],aux2[50];
cin>>n;
for(i=1;i<=n;i++)
{cout<<"Titlul cartii: ";
cin>>v[i].titlu;
cout<<endl;
cout<<"Autor: ";
cin>>v[i].autor;
cout<<endl;
cout<<"Pret: ";
cin>>v[i].pret;
cout<<endl;
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(v[i].pret<v[j].pret)
{
aux=v[i].pret;
v[i].pret=v[j].pret;
v[j].pret=aux;
strcpy(aux1,v[i].titlu);
strcpy(v[i].titlu,v[j].titlu);
strcpy(v[j].titlu,aux1);
strcpy(aux2,v[i].autor);
strcpy(v[i].autor,v[j].autor);
strcpy(v[j].autor,aux2);
}
for(i=1;i<=n;i++)
cout<<v[i].pret<<" "<<v[i].titlu<<" "<<v[i].autor<<" ";
return 0;
}
Aplicații (stivă & coadă)
Probleme stivă & coadă.
1. Se consideră o stivă în care iniţial au fost introduse, în această ordine, elementele 1,2,3,4,5,6,7,8,9,10. Dacă se notează cu AD(x) operaţia prin care se adaugă un element cu informaţia x în stivă şi cu EL operaţia prin care se elimină un element din stivă, care este elementul aflat în vârful stivei după executarea secvenţei de operaţii: EL;EL;AD(11); AD(12); EL;EL; ?
Vârful stivei se modifică de fiecare dată când punem/eliminam un element din stiva.
Vârful stivei se modifică de fiecare dată când punem/eliminam un element din stiva.
2. Se consideră o coadă în care iniţial au fost introduse, în această ordine, elementele cu valorile 1 şi 2. Se
notează cu AD(x) operaţia prin care se adaugă elementul cu valoarea x în coadă şi cu EL operaţia prin
care se elimină un element din coadă. Câte elemente va conţine coada în urma executării secvenţei de
operaţii: AD(4);EL;EL;AD(5);EL;AD(3)?
Abonați-vă la:
Postări (Atom)