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* malloc (type*) 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 = (int*) malloc( 100 * sizeof(int) );


calloc:

type* ptr = (type*) 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 = (int*) calloc( 100, sizeof(int) );


realloc:

type* ptr = (type*) 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 = (int*) malloc( 100 * sizeof(int) );
a = (int*) realloc( 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 my_realloc care are acelaşi efect şi antet ca funcţia realloc. În main se va afişa rezultatul funcţiei după fiecare apel şi se va compara cu rezultatul funcţiei realloc. Pentru afişarea valorii unui pointer se poate folosi %p în funcţia printf.

Se va afişa şi conţinutul zonei realocate (de la adresa rezultată).

Funţia my_realloc trebuie să respecte următorul prototip:

void* my_realloc (void *p, int n)

Pentru copierea datelor de la vechea adresă la noua adresă se va folosi funcţia memcpy din biblioteca string!


Problema 3.

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 4.

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)


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. [BONUS]

Să se scrie o funcţie pentru interclasarea a doi vectori ordonaţi de pointeri la şiruri într-un singur vector de pointeri. Şirurile au cel mult 19 caractere. La operaţia de interclasare nu se vor muta în memorie şirurile. Programul va afişa pe ecran vectorul interclasat rezultat din funcţie (cele două liste de şiruri se introduc ordonat).

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

char** interclaseaza(int n1, char (*s1)[20], int n2, char (*s2)[20]); // n1, n2 - numarul de siruri din vectorii s1, respectiv s2

// Alternativ, se poate folosi următorul antet echivalent:
// (cereţi explicaţii suplimentare dacă vreo una din declaraţii nu vă este clară)

char** interclaseaza(char **s1, char **s2);

Va trebui să alocați memorie pentru un nou vector de char *, dar nu și pentru șiruri (nu se alocă altă memorie pentru ele). Acest vector va fi rezutatul funcției. De exemplu, pentru a aloca un vector de n1 + n2 de char * (pointeri pentru șiruri) folosiți: char ** s3 = (char**) malloc ((n1 + n2) * sizeof(char*)).

Exemplu:

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

Problema 7. [BONUS]

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