Programski jezici → C → Dinamički nizovi i matrice

Dinamički nizovi i matrice u jeziku C

Dvodimenzionalni nizovi -matrice su objašnjeni u članku Dvodimenzionalni nizovi - matrice , gde memorija rezerviše statički, odnosno dimenzije matrice m*n se ne menjaju u toku programa. U ovom članku će biti opisano kako da se memorija definiše dinamički, upotrebom pokazivača, tako da se kasnije može promeniti.

Pretpostavimo da učitamo matricu celih brojeva dimenzija 4*3, tako da ove dimenzija mogu kasnije da se promene. Ovo se može uraditi pomoću pokazivača na celobrojne podatke(int*), tako da svaki red predstavlja po jedan dinamički niz na koji pokazuje pokazivač na red(int * r), a na skup svih redova, tj na matricu kao celinu, pokazuje pokazivač na pokazivač, npr. (int ** A).

Definisanje ovih pokazivača, pa samim tim dinamičkih nizova i matrica se razlikuje u programskim jezicima C i C++, što će biti pokazano u nastavku.

Objašnjenje koncepta: Dinamička vs. statička alokacija memorije

1. Šta je alokacija memorije?

U C jeziku, memorija može biti alocirana na dva glavna načina:

✅ Statički (kompajliranjem) – Veličina niza je poznata unapred i određuje se u trenutku kompajliranja.

✅ Dinamički (tokom izvršavanja) – Memorija se dodeljuje u toku rada programa, što omogućava veću fleksibilnost.

2. Kada koristiti dinamičku alokaciju?

Uporedne karakteristike statičke i dinamičke alokacije memorije:

Primer kada koristiti dinamičku alokaciju:

• Obrada podataka iz fajla, gde ne znamo unapred koliko će biti redova i kolona.
• Korisnički unos veličine matrice, gde korisnik određuje dimenzije u toku rada programa.
• Efikasna upotreba memorije, kako bismo alocirali samo onoliko koliko nam je potrebno.

3. Prednosti dinamičke alokacije

✅ Fleksibilnost – Možemo kreirati i koristiti memoriju on-the-fly.

✅ Efikasno korišćenje memorije – Ne troši se nepotrebno mnogo memorije kao kod statičkih nizova.

✅ Omogućava rad sa velikim podacima – Statički nizovi imaju ograničenje veličine na stack memoriju, dok malloc alocira memoriju u heap-u, gde možemo koristiti veće strukture.

💡 Primer: Statički alociran niz int matrix[1000][1000]; može izazvati stack overflow, dok će malloc koristiti heap memoriju, omogućavajući rad sa velikim podacima.

4. Potencijalni rizici i kako ih izbeći

🔴 Curenje memorije (Memory Leak)

• Problem: Ako zaboravimo da oslobodimo memoriju (free()), program će koristiti sve više memorije bez mogućnosti da je povrati.
• Rešenje: Uvek koristiti free() kada memorija više nije potrebna.

✅ Primer loše prakse (bez free()):

int **matrix = (int **)malloc(3 * sizeof(int *));
for (int i = 0; i < 3; i++) {
    matrix[i] = (int *)malloc(3 * sizeof(int));
}

// Ovdje nedostaje free(matrix) → curenje memorije!

✅ Ispravan način:

for (int i = 0; i < 3; i++) {
    free(matrix[i]);
}

free(matrix); // Oslobađanje glavnog pokazivača

🔴 Dereferenciranje nealokiranog pokazivača

• Problem: Ako koristimo pokazivač koji nismo inicijalizovali (NULL pokazivač), program može srušiti.
• Rešenje: Uvek proveriti da li je malloc uspeo.

✅ Primer dobre prakse:

int *arr = (int *)malloc(10 * sizeof(int));
if (arr == NULL) {
    printf("Alokacija nije uspela!\n");
    return 1;
}

Zaključak

Dinamička alokacija omogućava veću fleksibilnost i bolju kontrolu nad memorijom, ali zahteva pažljivo upravljanje kako bi se izbegle greške poput curenja memorije. Statička alokacija je sigurnija, ali ograničena veličinom i fleksibilnošću.

📌 Najbolja praksa:

✅ Koristi dinamičku alokaciju kada veličina podataka nije poznata unapred.

✅ Uvek oslobađaj memoriju pomoću free().

✅ Proveravaj uspešnost alokacije (if (ptr == NULL)).

Dvodimenzioni dinamički nizovi u C programskom jeziku

U programskom jeziku C se posmatrajući primer sa matricom na strani: Dvodimenzionalni nizovi - matrice u c++ može definisati red celih brojeva na sledeći način:

int *r = (int *)malloc(n * sizeof(int));

Funkcija malloc() koja se nalazi u standardnom zaglavlju <stdlib.h> alocira memoriju veličine n*4 bajta, u ovom slučaju, jer operator sizeof(int),daje veličinu int u bajtovima, a to je u ovom slučaju 4, jer int podaci toliko memorije zauzimaju u C jeziku.

Da bi se kreirala matrica veličine m*n uvešćemo pokazivač na pokazivač:

int **A = (int **)malloc(m * sizeof(int *));

S obzirom da se matrica kreira kao niz pokazivača, gde su ti pokazivači u stvari pokazivači koji pokazuju na pojedine redove u matrici, onda se ovde operator sizeof(odnosi na pokazivače na celobrojne podatke, pa otuda sizeof(int*). Kompletno kreiranje i učitavanje matrice bi bilo:

int **A;
int m = 4, n = 3;
A = (int **)malloc(n * sizeof(int *));
printf("Matrica?\n");

for (int i = 0; i < n; i++) {
    A[i] = (int *)malloc(n * sizeof(int));
    for (int j = 0; j < n; j++) {
        scanf("%d", &A[i][j]);
    }
}

Prvo se dinamički alocira memorija pokazivača "A" na pokazivače koji će pokazivati na redove u matrici. Redovi se kreiraju unutar for petlje kao A[i]. To je pokazivač na tekući red "i". Memorija za podatke u redu A[i] takođe mora da se dinamički alocira, pozivom malloc() funkcije.

Ostale funkcije za dinamičko alociranje memorije iz zaglavlja <stdlib.h>

Pored funkcije malloc() koja rezerviše memoriju, postoje još i funkcije:

realloc()- menja dimenziju prethodno rezervisane memorije sa malloc() funkcijom

free(A)-oslobađa memoriju na koju pokazuje pokazivač A

Kreiranje i učitavanje matrice bi bilo:

Ispisivanje matrica u C

printf("Matrica ispisivanje:\n");

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        printf("%3d", A[i][j]);
    }
    printf("\n");
}

Posle pokretanja i unosa podataka prikazaće se u konzoli:

Kopiranje matrice u C jeziku

Da bi kopirali elemente dinamičke matrice, napravićemo posebnu metodu za to i proslediti pokazivač matrice kao parametar, a takođe i dimenziju n. Prosleđivanjem pokazivača na matricu, obezbeđuje se da se bilo koja promena koja se odradi nad matricom unutar funkcije, odrazi na originalnu. Kopiranje, je zapravo prepisivanje podataka u novu matricu, koja se onda kao povratna vrednost vraća iz funkcije. Metoda je prikazana u nastavku:

int **copyMatrix(int **aT, int m, int n) {
    int **aC;
    // Alociramo memoriju za novu matricu aC
    aC = (int **)malloc(m * sizeof(int *));
    for (int i = 0; i < m; i++) {
        // Alociramo memoriju za svaku kolonu u redu matrice aC
        aC[i] = (int *)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            // Kopiramo podatke iz originalne matrice aT u novu matricu aC
            aC[i][j] = aT[i][j];
        }
    }
    return aC;
}

S obzirom da se matrica ispisuje više puta, kreiraćemo metodu za ispisivanje, koja će za parametre prihvatiti pokazivač na pokazivač, tj. pokazivač na matricu A i dimenzije matrice m i n. Metoda je prikazana u nastavku:

void ispisatiMatricu(int **a, int n) {
    // Prolazimo kroz sve redove matrice
    for (int i = 0; i < n; i++) {
        // Prolazimo kroz sve kolone matrice u tekućem redu
        for (int j = 0; j < n; j++) {
            // Ispisujemo element na poziciji [i][j] sa razmakom između brojeva
            printf("%d ", a[i][j]);
        }
        // Nakon što ispišemo jedan red, prelazimo u novi red
        printf("\n");
    }
}

Kod koji iz glavne (main) metode kreira novu matricu i poziva metodu za kopiranje, a zatim metodu za ispisivanje izgleda:

int **b;
// Pravimo kopiju matrice A sa dimenzijama m x n
b = copyMatrix(A, m, n);

// Ispisujemo kopiranu matricu koristeći funkciju ispisatiMatricu
ispisatiMatricu(b, m, n);

Ako sada pokrenemo aplikaciju prikazaće se:

Ovde je kod na početku izmenjen tako da omogućava da korisnik unese broj redova i kolona.

Transponovana matrica

Transponovanu matricu ćemo dobiti, kad polaznoj matrici zamenimo redove i kolone. Transponovana matrica se određuje u sklopu određivanja inverzne matrice.

Transponovana matrica A T
Inverzna matrica A-1

Transponovanu matricu možemo odrediti u posebnoj funkciji, kako je prikazano u nastavku:

void transponovana(int **a, int n) {
    // Prolazak kroz redove matrice
    for (int i = 0; i < n; i++) {
        // Prolazak kroz elemente iznad glavne dijagonale
        for (int j = i; j < n; j++) {
            // Zamena elemenata za transponovanje
            int b = a[i][j];
            a[i][j] = a[j][i];
            a[j][i] = b;
        }
    }
}

U unutrašnjoj tj. ugnježdenoj for petlji vrši se zamena elementa u i-tom redu i j-toj koloni sa elementom u j-redu i i-toj koloni. Unutrašnja pretlja ne počinje sa j=0, već sa j=i, jer je u kolonama sa j<=i, zamena već bila izvršena.

Poziv funkcije transponovana() se vrši u main() funkciji:

#include <stdio.h>

int main() {
    /* Pretpostavka: Inicijalizacija matrice A i n se već nalazi iznad ovog dela koda */
    // Poziv funkcije za transponovanje matrice
    transponovana(A, n);
    // Ispis informacije da je matrica transponovana
    printf("Transponovana matrica:\n");
    // Ispis elemenata transponovane matrice
    ispisatiMatricu(A, n);
}

Računanje determinante kvadratne matrice

Posmatrajmo sledeći primer:Učinati n, a zatim učitati elemente matrice dimenzija n*n. Napraviti funkciju koja računa determinantu matrice A, reda n*n, a zatim izračunati determinantu učitane matrice i rezultat prikazati na ekranu.
Primer:
Ulaz
3
3 5 6
2 -6 3
0 1 7
Izlaz
-193Zadatak je detaljno objašnjen na web strani:

Rekurzivni algoritmi

Detaljni primeri koda

U ovom delu prikazaćemo kako se alokiraju, inicijalizuju, koriste i oslobađaju dvodimenzionalni dinamički nizovi (matrice) u C jeziku.

1. Dinamička alokacija matrice

U C jeziku, dvodimenzionalni nizovi se alociraju pomoću pokazivača na pokazivač i funkcije malloc.

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

int main() {
    int rows = 3, cols = 4; // Dimenzije matrice
    int **matrix; // Pokazivač na niz pokazivača (redovi matrice)

    // 1. Alokacija memorije za niz pokazivača na redove
    matrix = (int **)malloc(rows * sizeof(int *));

    // 2. Alokacija memorije za svaki red
    for (int i = 0; i < rows; i++) {
        matrix[i] = (int *)malloc(cols * sizeof(int));
    }

    // 3. Inicijalizacija matrice
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // Primer vrednosti
            matrix[i][j] = i * cols + j;
        }
    }

    // 4. Ispis matrice
    printf("Matrica:\n");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }

    // 5. Oslobađanje memorije
    for (int i = 0; i < rows; i++) {
        free(matrix[i]);
    }
    free(matrix);
    return 0;
}

Objašnjenje koda:

• Koristimo malloc za alokaciju memorije.
• Alociramo memoriju za niz pokazivača (int **matrix).
• Svaki pokazivač pokazuje na niz int elemenata, što formira dvodimenzionalni niz.
• Memoriju oslobađamo obrnutim redosledom – prvo pojedinačne redove, zatim glavni niz pokazivača.

2. Alternativna alokacija (jedan pokazivač)

Moguće je alocirati dvodimenzionalni niz kao jedan niz, što smanjuje broj alokacija i poziva malloc:

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

int main() {
    int rows = 3, cols = 4;
    int *matrix; // jedan neprekidan blok od rows * cols elemenata

    // 1. Alokacija celokupne memorije odjednom
    matrix = (int *)malloc(rows * cols * sizeof(int));

    // 2. Inicijalizacija matrice
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // Primer vrednosti
            matrix[i * cols + j] = i * cols + j;
        }
    }

    // 3. Ispis matrice
    printf("Matrica:\n");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d ", matrix[i * cols + j]);
        }
        printf("\n");
    }

    // 4. Oslobađanje memorije
    free(matrix);
    return 0;
}

Prednosti ovog pristupa:

✅ Manji broj poziva malloc, što poboljšava performanse.

✅ Jednostavnije oslobađanje memorije (free(matrix), umesto petlje sa free(matrix[i])).

✅ Efikasnije korišćenje keš memorije procesora.

Zaključak

Postoje dva načina za alokaciju dinamičkih matrica u C jeziku:

1. Klasični način (pokazivač na pokazivač) – Fleksibilniji, ali zahteva više malloc poziva i složenije oslobađanje memorije.
2. Jedan niz sa aritmetikom pokazivača – Efikasniji pristup sa jednostavnijim oslobađanjem memorije.

Povezivanje sa srodnim temama

Za bolje razumevanje dinamičke alokacije memorije, preporučujemo da pogledate sledeće povezane članke:

• Osnove pokazivača u C jeziku – Razumevanje pokazivača je ključno za rad sa dinamičkom memorijom.
• Dinamičke matrice u C++-u – isti zadaci sa new/delete i sa vector.
• Strukture u jeziku C – sledeća lekcija: više podataka u jednoj celini.

Razumevanje ovih tema pomoći će vam da bolje shvatite kako funkcioniše dinamička alokacija i kako izbeći najčešće greške.

Proveri znanje