curs-baze1 lorena batagan

7/23/2019 Curs-baze1 Lorena Batagan

1/29

Programarea calculatoarelor

Cursul 1

Curs 1


2/29

ORGANIZAREA INTERN

A DATELOR

Informaia, data i cunotina

Clasificarea datelor

Structuri statice de date

Structuri dinamice de date


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)


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)


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


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/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


8/29


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.


9/29

Funcii:

Adr - adresa unui element

Depl - deplasamentul unui element

Rang - rangul unui element

Lung - lungimea unui element.



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


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


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


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



14/29

Matricea


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


15/29

Matricea


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


16/29

Matricea


Matrice ptraticDiagonala:PrincipalSecundar

Triunghiul:SuperiorInferior

Matricea unitateMatrice simetric

Matrice rare


17/29

Matricea


Inserare linie/coloantergere linie/coloanInterschimb linii/coloaneUrma matriceiTranspusa unei matricePrelucrri totale sau parialeOperaii cu dou sau mai multe masive

nmulireSuma

Diferite moduri de parcurgere


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


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


20/29

Masivul multidimensional

Numrul de dimensiuni > 3Rangul elementelor: generalizareUtile n diferite aplicaiiGeneralizare a elementelor prezentate


21/29

Articolul

Structur de dateneomogenAcces directntre elemente

exist o relaie deordine ierarhicOrganizat pe maimulte niveluri dearborescen

Articol

Cmpi Cmp2 Cmpi .. Cmpn

E21 E22


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


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


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


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


26/29

Arbore

Nod de ordin n1

2 3

4 5 6 7

8 9 10 11

1

2

3

4


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.


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.


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

curs-baze1 lorena batagan

Documents