Download - Curs-baze1 Lorena Batagan
-
7/23/2019 Curs-baze1 Lorena Batagan
1/29
Programarea calculatoarelor
Cursul 1
Curs 1
-
7/23/2019 Curs-baze1 Lorena Batagan
2/29
ORGANIZAREA INTERN
A DATELOR
Informaia, data i cunotina
Clasificarea datelor
Structuri statice de date
Structuri dinamice de date
-
7/23/2019 Curs-baze1 Lorena Batagan
3/29
Clasificarea datelor
Abordare la nivel logic
Dup natur:
- numerice: naturale, ntregi, reale, complexe;
- alfabetice
- alfanumerice- logice
Dup numrul de valori n timpul execuiei programului:
- variabile
- constante propriu-zise (literali)- constante simbolice
Dup numrul de valori memorate concomitent:
- elementare (scalare)
- structurate (structuri de date)
-
7/23/2019 Curs-baze1 Lorena Batagan
4/29
Dup adresa fizic de memorie n timpul execuiei:- structuri statice
- structuri dinamice
Dup modul de referire a elementelor:
- cu acces secvenial
- cu acces direct
Dup natura elementelor:
- omogene
- eterogene
Dup mediul de memorare:
- interne (n memoria principal)
- externe (pe medii magnetice: fiiere, baze de date)
Clasificarea structurilor de date
Dup tipul elementelor:- cu elemente date scalare
- cu elemente date structurate (structur recursiv)
-
7/23/2019 Curs-baze1 Lorena Batagan
5/29
Abordare la nivel fizic
Reprezentarea intern a datelor numerice naturale (ntregi fr semn)
Virgul fix aritmetic (1 sau 2 octei)
7 1 0
Codul utilizat: cod direct
Plaja de valori: [0, 28-1]
Reprezentarea intern a datelor numerice ntregi (ntregi cu semn)
Virgul fix algebric (1, 2 sau 4 octei)
Codul utilizat:
- pentru numere pozitive: cod direct
- pentru numere negative: cod complementar
Plaja de valori: [-27, 27-1]
7 1 0
s
6
-
7/23/2019 Curs-baze1 Lorena Batagan
6/29
Reprezentarea intern a datelor numerice reale
Virgul mobil
Fracie (23/52 bii)Caracteristic (8/11 bii)S
Normalizare: n = (-1)s * 1,fracie * 2exponent
Caracteristica = exponent + 127 simpl precizie
Caracteristica = exponent + 1023 dubl precizie
Codul utilizat: cod direct
Plaja de valori:
- simpl precizie: [-1038, 1038]
- dubl precizie: [-10307, 10307]
-
7/23/2019 Curs-baze1 Lorena Batagan
7/29
Reprezentarea intern a datelor alfabetice i alfanumerice
Codul ASCII un caracter pe octet 256 de caractere distincte
Codurile ASCII Caracterele
0 31 Coduri de control
32 47 Caractere speciale de pe tastatur
4 8 5 7 C i f r e l e a r a b e d e l a 0 l a 9
5 8 6 4 C a r a c t e r e s p e c i a l e d e p e t a s t a t u r
6 5 9 0 L i t e r e l e m a r i a l e a l f a b e t u l u i l a t i n
9 1 9 6 C a r a c t e r e s p e c i a l e d e p e t a s t a t u r
9 7 1 2 2 L i t e r e l e m i c i a l e a l f a b e t u l u i l a t i n
1 2 3 1 2 7 C a r a c t e r e s p e c i a l e d e p e t a s t a t u r
1 2 8 2 5 5 C a r a c t e r e g r a f i c e
Reprezentarea intern a datelor logice
adevrat - 1 reprezentat n virgul fix, pe un octet
fals - 0 reprezentat n virgul fix, pe un octet
-
7/23/2019 Curs-baze1 Lorena Batagan
8/29
Structuri statice de date
Masivul:
structur de date omogen,
cu acces direct
organizat pe mai multe nivelurintre elementele exist o relaie ierarhic.
Caracteristici:
numr dimensiuni,
numr de elemente pe dimensiune,
tipul de date al elementelor.
-
7/23/2019 Curs-baze1 Lorena Batagan
9/29
Funcii:
Adr - adresa unui element
Depl - deplasamentul unui element
Rang - rangul unui element
Lung - lungimea unui element.
Structuri statice de date
-
7/23/2019 Curs-baze1 Lorena Batagan
10/29
Vectorulmasiv unidimensional
X
x1 x2 xn
Reprezentare intern
x1 x2 xi ...... xn
X
Depl(xi)
Referire element
Adr(xi) = Adr(X) + Depl(xi)
Depl(xi) = (rang(xi) - 1) * l
rang(xi) = I, pentru i=1,n
-
7/23/2019 Curs-baze1 Lorena Batagan
11/29
Vectorulmasiv unidimensional
Sortare
Inserare elementSterge element
Interschimb element
Determin valoarea minim
Determin valoarea maxim
Cautare
Operaii cu doi sau mai muli vectori
Produs scalar
Produs vectorial
InterclasareSuma
Prelucrri totale sau pariale
Diferite moduri de parcurgere
-
7/23/2019 Curs-baze1 Lorena Batagan
12/29
Matricea
-masiv bidimensional
Numr dimensiuni: 2
Organizare pe linii i coloane: m x n
Spaiul ocupat: m x n x Lung(tip_elem)
Memorare:
Lexicografic (vector de linii)
Invers lexicografic (vector de coloane)
mnmm
ij
n
n
aaa
a
aaa
aaa
...
.........
...
...
21
22221
11211
-
7/23/2019 Curs-baze1 Lorena Batagan
13/29
A
l1 l2 lm
a1,na1,2a1,1 am,nam,2am,1
A
c1 c2 cm
a1,na1,2a1,1 am,nam,2am,1
Matricea
-masiv bidimensional
-
7/23/2019 Curs-baze1 Lorena Batagan
14/29
Matricea
-masiv bidimensional
Reprezentare intern: Lexicografic
Invers lexicografic
a1,1 a1,2 ai,j ...... am,n
a
Linia 1
a1,1 a2,1 ai,j ...... am,n
a
Coloana 1
-
7/23/2019 Curs-baze1 Lorena Batagan
15/29
Matricea
-masiv bidimensional
Referire elemente
Adr(ai,j) =Adr(A) + Depl(ai,j)
Depl(ai,j) = (Rang(ai,j) - 1) * Lung(tip_elem)
Rang(ai,j) = (i - 1) * n + j memorare lexicografic
Rang(ai,j) = (j - 1) * m + i memorare invers lexicografic
-
7/23/2019 Curs-baze1 Lorena Batagan
16/29
Matricea
-masiv bidimensional
Matrice ptraticDiagonala:PrincipalSecundar
Triunghiul:SuperiorInferior
Matricea unitateMatrice simetric
Matrice rare
-
7/23/2019 Curs-baze1 Lorena Batagan
17/29
Matricea
-masiv bidimensional
Inserare linie/coloantergere linie/coloanInterschimb linii/coloaneUrma matriceiTranspusa unei matricePrelucrri totale sau parialeOperaii cu dou sau mai multe masive
nmulireSuma
Diferite moduri de parcurgere
-
7/23/2019 Curs-baze1 Lorena Batagan
18/29
Masivul tridimensional
Numr dimensiuni: 3Vector de matrice/Plane de matriceT(p, m,n) = vector dep elemente de tipmatrice m x n
Spaiul ocupat: p x m x n x Lung(tip)
pm
n
-
7/23/2019 Curs-baze1 Lorena Batagan
19/29
Masivul tridimensional
Referirea elementelor
Adr(ti,j,k) =Adr(t) + Depl(ti,j,k)
Depl(ti,j,k) = (Rang(ti,j,k) - 1) * Lung(tip)
Rang(ti,j,k) = ((i - 1) * m + j - 1) * n + k memorarelexicografic
Rang(ti,j,k) = ((k - 1) * m + j - 1) * p + i memorare inverslexicografic
-
7/23/2019 Curs-baze1 Lorena Batagan
20/29
Masivul multidimensional
Numrul de dimensiuni > 3Rangul elementelor: generalizareUtile n diferite aplicaiiGeneralizare a elementelor prezentate
-
7/23/2019 Curs-baze1 Lorena Batagan
21/29
Articolul
Structur de dateneomogenAcces directntre elemente
exist o relaie deordine ierarhicOrganizat pe maimulte niveluri dearborescen
Articol
Cmpi Cmp2 Cmpi .. Cmpn
E21 E22
-
7/23/2019 Curs-baze1 Lorena Batagan
22/29
Articolul
Cmpuri elementare date fr descendeni
Date de grup date care au descendeni
Articolul data de grup de cel mai nalt nivel
Utilizate frecvent in lucrul cu fiiere
-
7/23/2019 Curs-baze1 Lorena Batagan
23/29
Articolul
Reprezentare intern:
Juxtapunerea datelor elementare
Datorit alinierilor:Lung(articol) >= Lung(cimpi)
Referire elemente:
Prin nume, relativ la variabila de tip articolDeplasare fa de adresa de nceput
-
7/23/2019 Curs-baze1 Lorena Batagan
24/29
Articolul
Factura
nr_fact data_emiterii UM cantitate pret valoare furnizor
an luna zi denumire cod_fiscal
Variabila de tip articol: fact
Referire cmp zi: fact.data_emiterii.zi
-
7/23/2019 Curs-baze1 Lorena Batagan
25/29
Structuri dinamice de date
Graf orientatG = (X, U); X = {x1, x2, , xn}; (xi, xj) U
H = (Y, V); Y X
Drum de lungime n (n cel putin 1- contine un drum elementar)
Drum elementar - drumul care contine numai varfuri distincte
Circuit - Un drum in care primul varf coincide cu ultimul
-
7/23/2019 Curs-baze1 Lorena Batagan
26/29
Arbore
Nod de ordin n1
2 3
4 5 6 7
8 9 10 11
1
2
3
4
-
7/23/2019 Curs-baze1 Lorena Batagan
27/29
Lista simplu nlnuit
Lista dublu nlanuit
La={(di,si)|diD,si P}
Ls={(pi,di,si)|diD,pi,si P}
Operaii pe liste: traversare, inserare, tergere etc.
-
7/23/2019 Curs-baze1 Lorena Batagan
28/29
Stiva (lista LIFO)
Coada (lista FIFO)
Operaii pe stiv: inserare n capul stivei, tergere din
capul stivei, citirea din capul stivei.
Operaii specifice: inserare n spate, tergere din faa
cozii, citirea din faa cozii.
-
7/23/2019 Curs-baze1 Lorena Batagan
29/29
Bibliografie 1. I. Gh. Roca, B. Ghilic-Micu, C. Cocianu, M. Stoica, C. Uscatu, M.
Mircea, L. Btgan, C. Silvestru, Bazeleprogramrii calculatoarelor.
Teorie i aplicaii n C, Ed. ASE, Bucureti, 2006, ISBN 973-594-591-6
2. I. Gh. Roca, B. Ghilic-Micu, C. Cocianu, M. Stoica, C. Uscatu,
Programarea calculatoarelor. tiina nvrii unui limbaj de programare,
Teorie i aplicaii, Ed. ASE, 2003
3. Ion Smeureanu, Marian Drdal, Programarea n limbajul C/C++, Ed.
CISON, Bucureti 2004, ISBN 973-99725-7-8