Faceți căutări pe acest blog

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



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. 


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)? 





Structuri de date

      Datele apar frecvent sub formă unor  colecții de date de diferite tipuri, menite
 să faciliteze prelucrarea în cadrul rezolvării unei anumite probleme concrete.
      Datele structurate, numite uneori și structuri de date, sunt constituite din mai
 multe date elementare (uneori de același tip, alteori de tipuri diferite), grupate cu
 un anumit scop și după anumite reguli.
   Exemple. 
 1. Un șir finit de numere reale a1, a2, ..., an poate fi reprezentat ca o dată
 structurată (tablou unidimensional sau vector).
 2. O matrice

         a1,1 a1,2 ··· a1,n
         a2,1 a2,2 ··· a2,n
         ···      ···   ...  ···  
        am,1 am,1 ··· am,n

 poate fi reprezentată ca o dată structurată (tablou bidimensional) specificand fiecare
 element prin doi indici (de linie și de coloană).
      O structură de date este deci o colecție de date, eventual de tipuri diferite,
 pe care s-a definit o anumită organizare și căreia îi este specific un anumit mod de
 identificare a elementelor componente. Componetele unei structuri de date pot fi
 identificate prin nume sau prin ordinea pe care o ocupă în cadrul structurii.
      Structurile de date pot fi create pentru a fi depozitate în memoria internă
 (aceste structuri de date se numesc structuri interne) sau în memoria externă (se
 numesc structuri externe, sau fisiere). Structurile interne au un caracter de date
 temporare (ele dispar odată cu încetarea activității de prelucrare) iar cele externe
 au un caracter de date permanente (mai bine spus, de lungă durată).

Aplicații

Problema 3.

 Se citesc datele a n elevi(nume,media pe semestrul I, media pe semestrul al II-lea,numarul de absente);Ordonati descrescator dupa media pe semestrul I.


#include <iostream>
#include<cstring>

using namespace std;

typedef struct elev
{
    char nume[50];
    float m1,m2;
    int abs;
}e;
e v[100];

int main()
{int i,j,n;
float aux;
char naux[50];
cout<<"n= ";
cin>>n;
for(i=1;i<=n;i++)
{
    cout<<"nume elev: "<<" ";
    cin>>v[i].nume;
    cout<<"media pe semestrul I: "<<" ";
    cin>>v[i].m1;
    cout<<"media pe semestrul al II-lea: "<<" ";
    cin>>v[i].m2;
    cout<<"numar absente: "<<" ";
    cin>>v[i].abs;
    cout<<endl;

}
for(i=1;i<=n;i++)
   for(j=i+1;j<=n;j++)
    if(v[i].m1<v[j].m2)
{
    aux=v[i].m1;
    v[i].m1=v[i].m2;
    v[i].m2=aux;
    strcpy(naux,v[i].nume);
    strcpy(v[i].nume,v[j].nume);
    strcpy(v[j].nume,naux);

}
 for(i=1;i<=n;i++)
     cout<<v[i].nume<<" ";

    return 0;
}