Structuri de date dinamice

Structuri de date dinamice

Un pointer (variabila referinta) este o variabila ce contine adresa unei alte variabile, numite statice, carora li se aloca un spatiu de memorie pe toata durata blocului unde au fost declarate. Variabilele de tip referinta se numesc dinamice, ele putindu-se creea independent de structura programului, cu o procedura standard, numita NEW pentru PASCAL si MALLOC pentru C.

Variabilele referinta nu apar explicit intr-o declaratie de tip si nu pot sa fie referite direct printr-un identificator. Un tip pointer P consta dintr-un numar nelimitat de adrese de memorie ale variabilelor de un anumit tip (T). Se spune ca P este legat la T.

Definirea tipului referinta

type <identificator>=* <identificator de tip>

Exemplu:

int *p1, *p2 ;

Se definesc doua tipuri de pointer numite p1 si p2 ce indica spre variabilele de tip intreg.

Declararea unei variabile de tip referinta

Se face prin indicarea numelui pointerului precedat de caracterul *. Semnificatia acestui mod de referire este urmatoarea: *p reprezinta valoarea variabilei ce se afla memorata la adresa indicata de pointerul p.

Exemplu:

In exemplul urmator, pointerului 'p1' i s-a alocat o adresa libera din memorie prin procedura "malloc". La adresa respectiva s-a inscris valoarea variabilei 'i'. Prin atribuirea p2=p1, variabila 'j' va contine ca valoare, aceeasi valoare ca si variabila 'i'.

int *p1, *p2;

int i, j;

Observatii

-Desi se pot face atribuiri unor variabile de tip referinta, valoarea acestora nu se poate vizualiza, nefiind considerata un numar intreg.

-Orice variabila de tip referinta poate primi o valoare speciala (numita NIL, respectiv NULL in 'C') cu urmatoarea specificatie: - respectiva variabila nu va indica spre nici o adresa de memorie.

Variabile referinta asociate structurilor de tip articol

In cazul cind un tip de variabile referinta p este legat la un tip de date T, apelul procedurii malloc (p1), unde p1 este un pointer de tipul 'p' declarat, are ca efect alocarea unei zonei de memorie cu o dimensiune egala cu aceea a unei variabile din tipul T si atribuirea adresei de inceput a zonei de memorie pointerului p1. Daca tipul de date T este de tipul articol cu parte varianta, atunci se calculeaza lungimea zonei in cazul partii variante celei mai mari (lungime acoperitoare).

O aplicatie importanta a folosirii pointerilor o constituie implementarea prin programe a structurilor de date abstracte, de tipul grafurilor finite. Considerind o structura de date de tip articol 'T' care contine unul sau mai multe cimpuri de tipul pointer, se poate construi o structura de graf finit considerind 'T' ca multimea nodurilor grafului si pointerii drept arce.

Cel mai simplu exemplu il constitue o lista simplu inlantuita:

typedef struct nod

arc;

Am notat cu 'inf' cimpul ce contine informatia utila a nodului si cu 'urm' cimpul ce este un pointer de tipul arc, adica spre un articol de acelasi tip.

O reprezentare grafica a acestui tip este urmatoarea:

Referirea unui cimp al unui articol de acest tip se poate face astfel:

arc *p

p->inf -reprezinta cimpul inf al unui articol referit de pointerul p;

p->urm-reprezinta cimpul "urm" al unui articol referit de pointerul p (adresa urmatorului articol din lista)

Observatie:

Tipul referinta este singurul care permite definirea unui tip de date dupa definirea lui insusi.

Alocarea si dealocarea memoriei

Alocarea spatiului de memorie necesar se face cu ajutorul procedurii NEW() pentru PASCAL si cu functia MALLOC() pentru limbajul C. Folosind de multe ori procedura NEW, spatiul de memorie ramas disponibil se poate micsora foarte mult. Daca insa intr-un punct al programului se poate renunta la spatiul alocat unor variabile referinta, se poate folosi procedura DISPOSE, complementara procedurii NEW, sau cu functia FREE(x) pentru limbajul C. DISPOSE(x) (respectiv FREE(x)) elibereaza spatiul de memorie alocat variabilei referinta x.

In cazul in care x este o variabila referinta catre o structura de tip articol cu parti variante, se poate aloca si dealoca pentru x doar spatiul necesar unei variante.

Probleme rezolvate

Dindu-se un vector de numere reale, sa se lege numerele intre ele, folosind variabile de tip pointer, specificind pentru fiecare numar, valoarea sa si numarul de ordine si sa se afiseze apoi numerele in ordinea respectiva.

Vom folosi o variabila de tip articol cu trei cimpuri: - valoarea numarului (KEY), indicele atasat numarului in vectorul initial (INF) si un pointer spre urmatorul articol (NEXT).

Articolul corespunzator ultimului numar din vector, contine valoarea NULL in cimpul pointerului. Vom mai folosi o variabila tip pointer pentru parcugerea articolelor, initializandu-se prima data cu valoarea adresei primului articol.

#include <stdio.h>

#include <stdlib.h>

#include <alloc.h>

typedef struct lista

plist;

int    vect[10];

plist    *p1, *p, *p0;

int    x;

int    i, j;

char    ch;

void main()

while (ch!='n')

p = (plist *)malloc(sizeof(plist));

p->nr = vect[1];

p->ind = 1;

p->urm = NULL;

p0 = p;

for (j = 2; j <= i; j++)

printf('Numerele introduse sunt: n');

p = p0;

while (p != NULL)

2. Dindu-se pentru o grupa de studenti examenele restante ale fiecarui student, sa se realizeze o statistica privind examenele cu cele mai multe restante.

Vom identifica un student prin numarul grupei si numele sau, iar un examen restant prin initiala (notat simbolic prin una din literele A,B,C,D,E,F) si nota obtinua la examen (notam cu 0 neprezentarea la examen).

Realizam astfel o lista cu toti studentii dintr-o grupa, inlantuiti cu ajutorul unui pointer. Dar pentru fiecare student trebuie realizata lista examenelor restante, lista aceasta se inlantuie cu ajutorul unui alt pointer.

Va rezulta o structura de felul urmator:

Un articol de tipul student va contine campurile:

-nume

-prenume

-pointer spre urmatorul student

-pointer spre primul examen din lista examenelor restante

Un articol de tipul examen restant contine cimpurile:

-initiale examen

-nota examen

-pointer spre urmatorul examen restant pentru acelasi student

Daca un student nu are examene restante, pointerul spre primul examen restant va avea valoarea NULL. Pentru introducerea informatiilor, cit si pentru detectarea examenului cu cele mai multe restante se vor parcurge doua cicluri: unul exterior pentru lista studentilor, iar pentru fiecare student, un ciclu interior pentru lista examenelor restante.

#include <stdio.h>

#include <stdlib.h>

#include <alloc.h>

typedef struct examen

pexamen;

typedef struct student

pstud;

int    rest['F'+1];

int x[6];

char nume, prenume;

pexamen *pe1, *pe2;

int i, j, k, t, nr;

pstud *ps0, *ps1, *ps2;

char    ch;

void main()

while (!(j == 71));

printf('Mai sunt studenti? [y/n] n');

do while (!(ch=='y' || ch=='Y' || ch=='N' || ch=='n'));

} while (!(ch=='N' || ch=='n'));

for (ch = 'A'; ch <= 'F'; ch++) rest[ch] = 0;

ps1 = ps0;

while (ps1 != NULL)

ps1 = ps1->urms;

}

else ps1 = ps1->urms;

}

x[0] = rest['A'];

x[1] = rest['B'];

x[2] = rest['C'];

x[3] = rest['D'];

x[4] = rest['E'];

x[5] = rest['F'];

do

} while (!(i == 0));

if (x[5] == rest['A'])

printf('Materia A are cele mai multe restante. n');

if (x[5] == rest['B'])

printf('Materia B are cele mai multe restante. n');

if (x[5] == rest['C'])

printf('Materia C are cele mai multe restante. n');

if (x[5] == rest['D'])

printf('Materia D are cele mai multe restante. n');

if (x[5] == rest['E'])

printf('Materia E are cele mai multe restante. n');

if (x[5] == rest['F'])

printf('Materia F are cele mai multe restante. n');

printf('n');

for (i = 65; i <= 70; i++)

Probleme propuse

1. Dindu-se un vector de numere intregi sa, se scrie un program care leaga elementele vectorului intre ele, dar in ordine inversa.

2. Dindu-se informatiile referitoare la o grupa de studenti, conform problemei rezolvate 2, sa se scrie un program care realizeaza o statistica cu studentii cu cele mai multe restante.

Se poate introduce un cimp de codificare a studentilor conform numarului lor de ordine din condica.

3. Una din tehnicile de reprezentare a masivelor bidimensionale cu ajutorul masivelor unidimensionale utilizeaza masivele de pointeri. Intrarile masivului de pointeri indica catre liniile tabloului bidimensional. Se pot ivi doua situatii: alocarea liniilor se face intr-un vector de linii sau se face dinamic. Pentru ambele situatii sa se faca proceduri pentru:

a) Testarea faptului daca o matrice bidimensionala patrata este sau nu simetrica;

b) Adunarea a doua masive bidimensionale de numere reale reprezentate astfel.

4. In contextul situatiei a doua din cadrul problemei anterioare, sa se faca proceduri pentru:

a) Citirea unei matrici bidimensionale;

b) Afisarea unei matrici bidimensionale;

c) Rearanjarea liniilor unei matrici bidimensionale in ordine crescatoare relativ la suma elementelor unei linii;

d) Determinarea transpusei unei matrici bidimensionale;

e) Inmultirea a doua matrici bidimensionale.

5. a) Fiind dat un tablou A de N numere intregi, scrieti o procedura care sa produca un vector de pointeri (indici) P, de dimensiune N astfel incit numerele A[P[1]], A[P[2]],..,A[P[N]] sa fie ordonate crescator.

b) Aceeasi problema pentru un masiv bidimensional de dimensiune MxN, in acest caz P avind dimensiunea MxN, elementele sale fiind inregistrari de tipul:

type pointer=record

linie: integer;

coloana: integer;

end;

astfel incit numerele: A[ P[1].linie, P[1].coloana ],, A[ P[MxN].linie, P[MxN].coloana ] sa fie ordonate crescator (parcurgerea se face pe linii).

6. Se considera trei vectori DATA, P, S. Ordinea intregilor din vectorul DATA este specificata de P si S. Astfel, P[i] si S[i] indica spre predecesorul si succesorul intregului memorat in DATA[i]. O valoare 0 indica faptul ca nu exista predecessor, sau succesor. Se cere:

a) Pornind de la valorile din vectorul DATA sa se creeze vectorul P si S, astfel incit DATA sa fie ordonat crescator;

b) Daca in masivul DATA sint pastrate N valori si pentru aceste valori vectorii P si S sint construiti corect, sa se scrie o procedura de actualizare a lui P si S in cazul cind pe pozitia N+1 din masivul DATA se adauga un nou element, astfel incit DATA sa ramina ordonat crescator.

7. Fie A un masiv de tip real cu I si N doi intregi pozitivi. Se defineste functia

/ A[ I ] daca I=N

M(A, I, N)=

max(M(A, I+1, N), A[I]) daca I<N

Sa se scrie o functie recursiva pentru MAX.

8. Se marcheaza N puncte distincte pe circumferinta unui cerc. Se pune problema: cite unghiuri pot fi desenate astfel incit laturile unghiurilor sa se sprijine pe trei din cel N puncte?

9. Se considera N puncte distincte ca in exercitiul anterior. Se pune problema: in cite moduri pot fi selectate K puncte distincte din cele N puncte date?

10. Se da o permutare a numerelor 1, 2, 3, , n. Fie N numarul de intregi care il depasesc pe i, cu i oarecare.

Exemplu:

N₁ =2; N₂ =3; N₃ =1; N₄ =4;

Sa se scrie o procedura care va efectua permutari si care va tipari numerele N₁ , N ₂, , N_n pentru fiecare permutare.

11. Se presupune ca este data o lista dublu legata L. Sa se scrie o procedura recursiva pentru inversarea listei L.

12. Sa se scrie o procedura recursiva care determina daca doua liste simplu legate sint identice. Aceasta inseamna ca ele trebuie sa aiba aceeasi structura si aceleasi date in cimpurile corespunzatoare.