Programarea Calculatoarelor, seria CC

Laborator 8

Programe cu date alocate dinamic

În acest laborator veţi învăţa să:


Funcţii pentru alocarea memoriei (din stdlib.h):

malloc:

type* ptr = malloc(size_t size);

Unde size_t este un tip întreg fără semn (unsigned), dependent de arhitectură (pentru arhitectura 32bit, acesta este unsigned int).

Funcţia alocă o zonă continuă de memorie având dimensiunea de size octeţi şi returnează un pointer void* cu adresa de început a zonei de memorie alocată. Pentru a schimba tipul acestui pointer se foloseşte operatorul cast.

Exemplu:

int *a = malloc( 100 * sizeof(int) );

calloc:

type* ptr = calloc(size_t num, size_t size);

Funcţia alocă spaţiu de memorie pentru un vector cu num elemente, fiecare element avâdn dimensiunea size de octeţi şi returnează un pointer void* cu adresa de început a zonei de memorie alocată. Atenţie! Toţi biţii din această zonă de memorie sunt setaţi pe 0.

Exemplu:

int *a = calloc( 100, sizeof(int) );

realloc:

type* ptr = realloc(void* old_ptr, size_t size);

Unde old_ptr este adresa de început a zonei de memorie pe care dorim să o realocăm, size reprezintă noua dimensiune a zonei de memorie (în octeţi), iar ptr este adresa de început a zonei de memorie după realocare.

Funcţia realizează modificarea dimensiunii zonei de memorie referite de old_ptr.

Exemplu:

int *a = malloc( 100 * sizeof(int) );
a = realloc( a, 200 * sizeof(int) );

free:

void free(void* ptr);

Unde ptr reprezintă adresa zonei de memorie pe care dorim să o eliberăm.

strdup:

char *strdup( char *s );

Unde s reprezintă un string (şir de caractere terminat cu '\0').

Funcţia alocă o nouă zonă de memroie la care se copiază octeţii şirului s. Se returnează un pointer către începutul zonei de memorie unde s-a făcut copierea.

Problema 1.

Copiaţi şi rulaţi următorul program şi scrieţi câte un comentariu în care să explicaţi ce face fiecare instrucţiune. Este foarte important să înţelegeţi cum să folosiţi pointerii în C. Dacă nu înţelegeţi ceva din program, întrebaţi asistenţii.

# include <stdio.h>
# include <stdlib.h>
# include <string.h>

int main ()
{
     char c = 'a', *p, s[100];
     p = &c;
     printf ("%c %c %c", *p, *p+1, *p+2);
     s[0] = 'A'; s[1] = 'B'; s[2] = 'C'; s[3] = '\0';
     p = s;
     printf ("\n%s %s %c %s", s, p, *(p+1), p+1);
     strcpy (s, "\nacesta este un exemplu de lucru cu pointeri");
     printf ("%s", s);
     p += 17;
     for (; *p != '\0'; ++p) {
         if (*p == 'e')
              *p = 'E';
         if (*p == ' ')
              *p = '\n';
         }
     printf ("%s\n", s);
     return 0;
}

Programul va afişa următoarele linii:

a b c
ABC ABC B BC
acesta este un exemplu de lucru cu pointeri
acesta este un exEmplu
dE
lucru
cu
pointEri

Problema 2.

Să se scrie o funcţie cu acelaşi efect şi antet ca şi funcţia strdup şi să se verifice. Un exemplu de utilizare al funcţiei strdup este următorul:

char buf[512]; // aici se citeşte un şir
char *p; // adresă şir alocat dinamic
scanf("%s",buf); // citire şir
p=strdup(sir); // alocă memorie şi copiază şir la adresa p

Funcţia declarată trebuie să respecte următorul antet:

char* my_strdup (char *s)

Problema 3.

Scrieţi o funcţie care înlocuieşte într-un şir s prima apariţie a unui subşir dat s1 printr-un şir dat s2, folosind un vector intermediar alocat dinamic, în care se construieşte şirul rezultat. Se caută s1 în s, se copiază în vectorul auxiliar caracterele anteriorare lui s1 şi se concatenează cu s2 şi cu caracterele de după s1 (din s). În final se copiază din vectorul auxiliar în s.

Funcţia declarată trebuie să respecte următorul antet:

char* my_replace(char *s, char *s1, char *s2)

Exemplu:

Intrare Ieşire
imi nu-mi
mie imi plac pointerii 		mie nu-mi plac pointerii

Problema 4.

Să se scrie un program care citește numere de la tastatură până la întâlnirea numărului 0 și care le stochează într-un vector alocat dinamic, ce va fi realocat dacă este nevoie. La final, se va afișa vectorul stocat, pentru verificare.

Pentru acest lucru, vom avea nevoie de următoarele variabile:

Se va porni cu o capacitate ințială (de exemplu, cap = 5) și, în momentul în care citim un nou număr și nu mai există spațiu pentru a fi stocat (cap == n), se va crește capacitatea (fie printr-un anumit număr, fie se va dubla) și se va realoca vectorul v cu această noua capacitate.

Exemplu:

Intrare Ieşire
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Problema 5.

Să se scrie un program pentru citirea unor cuvinte (de la tastatură) şi afişarea numărului de apariţii al fiecărui cuvânt. Cuvintele au maxim 19 litere fiecare.

Se va folosi un vector de pointeri la cuvinte şi un vector de numere întregi. Variante:

Exemplu:

Intrare Ieşire
6
ana are
mere are mere mere 		ana 1
are 2
mere 3

Problema 6.

Liniarizarea unei matrici. Să considerăm următoarea problemă: dorim să calculăm C(n,k) folosind relaţia de recurenţă:

C(n,k) = C(n-1,k) + C(n-1,k-1)

Să considerăm că am ales să rezolvăm problema în următorul mod: definim o matrice c de dimensiuni suficient de mari, în care elementul c[i][j] reprezintă valoarea C(i,j). Vom iniţializa linia 1 a matricei (C(1,0) = C(1,1) = 1) şi vom calcula, pe rând, aplicând relaţia de recurenţă, valorile C(i,j) până când am obţinut valoarea cerută de problemă: C(n,k).

Acest algoritm rezolvă problema, dar prezintă un dezavantaj. Pentru calculul unei valori, trebuie păstrată în memorie o matrice de dimensiuni relativ mari, care ocupă multă memorie. În plus, observăm că pentru a calcula C(i,j), care se va afla pe linia i în matrice, avem nevoie doar de valori de pe linia i-1. Astfel, putem aduce o economie de memorie majoră în program dacă în loc să păstrăm întreaga matrice în memorie, păstrăm doar doi vectori vim1[] şi vi[] care să reprezinte liniile i-1, respectiv i din matrice.

Avem acum două optiuni:

Să se scrie un program care calculează valoarea lui C(n,k) prin metoda descrisă mai sus, reducând matricea la doi vectori, şi schimbând după fiecare pas, rolul jucat de aceşti doi vectori.

Exemplu:

Intrare Ieşire
5 3
 10
12 11
 12