DVODIMENZIONALNI DINAMIČKI NIZOVI - MATRICE U PROGRAMSKOM JEZIKU C++

Sadržaj stranice

Dobrodošli na stranicu posvećenu dvodimenzionalnim i višedimenzionalnim nizovima u C++! Ova stranica nudi sve ključne informacije, primere koda i praktične savete o radu sa matricama i višedimenzionalnim strukturama podataka. Pomoću tabele sadržaja možete brzo preskočiti na interesantne sekcije i pronaći sadržaj koji vas zanima.

Uvod: Statički i dinamički nizovi u C++

U programiranju, posebno u C++ jeziku, rad sa nizovima je čest i neophodan kada je potrebno organizovati podatke na strukturiran način. Nizovi mogu biti statični ili dinamički alocirani, a razumevanje razlika između njih je ključno za efikasno upravljanje memorijom.

Statički nizovi

Statički nizovi su nizovi čija se veličina određuje u vreme kompajliranja i ne može se menjati tokom izvršavanja programa. Deklarišu se na sledeći način:

int matrica[3][3]; // Deklaracija statičkog 3x3 dvodimenzionalnog niza

Dinamički nizovi

Dinamički nizovi su nizovi čija se veličina može definisati u vreme izvršavanja. Alociraju se na hipu, a upravljanje memorijom se obavlja eksplicitno korišćenjem operatora new i delete.

int** matrica = newint*[m]; // Alokacija niza pokazivačafor (int i = 0; i < m; i++) {
    matrica[i] = newint[n]; // Alokacija svakog reda
}        
        

Memorija mora biti eksplicitno oslobođena:

for (int i = 0; i < m; i++) {
    delete[] matrica[i]; // Brisanje svakog reda
}
delete[] matrica; // Brisanje niza pokazivača

Bolja alternativa: std::vector

Iako je dinamička alokacija pomoću new i delete fleksibilna, bolji i moderniji način upravljanja nizovima u C++ jeziku je korišćenje std::vector iz biblioteke <vector>. Vektori automatski upravljaju memorijom, eliminišući potrebu za ručnim oslobađanjem memorije i smanjujući rizik od curenja memorije.

Primer ekvivalenta dinamičke matrice korišćenjem std::vector:

#include <vector>
#include <iostream>

int main() {
    int m = 3, n = 3;
    std::vector<std::vector<int>> matrica(m, std::vector<int>(n)); // Alokacija m x n matricefor (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            matrica[i][j] = i * n + j; // Popunjavanje matrice vrednostima
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << matrica[i][j] << " ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}        
        

Prednosti std::vector u odnosu na ručnu dinamičku alokaciju:

• Automatska uprava memorijom – nema potrebe za eksplicitnim delete pozivima.
• Sigurnost – smanjen rizik od curenja memorije.
• Jednostavnija sintaksa – olakšava manipulaciju nizovima.
• Efikasnost – bolje upravljanje memorijom i keširanjem podataka.

Iz ovih razloga, kada radite sa nizovima u C++, preferirajte korišćenje std::vector umesto eksplicitne dinamičke alokacije pomoću new i delete.

Uvod u dinamičku alokaciju matrica

U prethodnom članku „Dvodimenzionalni nizovi – matrice“ objašnjeno je kako se radi sa statičkim nizovima, gde se memorija rezerviše unapred i dimenzije matrice (m×n) ostaju nepromenjene tokom izvršavanja programa. U ovom članku biće opisano kako da se memorija definiše dinamički pomoću pokazivača, što omogućava kasniju promenu dimenzija matrice.

Primer: Dinamički niz sa mogućnošću promene dimenzija

Pretpostavimo da želimo da učitamo matricu celih brojeva dimenzija 4×3, gde se dimenzije (broj redova i kolona) mogu promeniti u toku programa. Ovo se može uraditi korišćenjem pokazivača na celobrojne podatke (int*), pri čemu svaki red predstavlja dinamički niz, a cela matrica je niz pokazivača, odnosno pokazivač na pokazivač (npr. int** A).

Važno je napomenuti da se definisanje ovih pokazivača – a samim tim i dinamičkih nizova i matrica – razlikuje u programskim jezicima C i C++ zbog uvođenja operatora new i delete u C++. U C++-u, dinamičko kreiranje memorije obezbeđuje operator new, pa se pokazivač A kreira na sledeći način:

Dalje, kreiranje i učitavanje matrice može se realizovati na sledeći način:

Da bi se ispisala učitana matrica, koristi se ugnježdena for petlja:

Napomena o oslobađanju memorije:

Po završetku rada sa dinamički alociranom matricom, važno je osloboditi memoriju kako bi se izbeglo curenje memorije:

Prednosti dinamičkih nizova:

• Fleksibilnost – veličina niza se može definisati u vreme izvršavanja.
• Efikasno korišćenje memorije – alocira se samo onoliko memorije koliko je stvarno potrebno.
• Velike strukture podataka – omogućava kreiranje nizova koji prevazilaze kapacitet steka.

Nedostaci dinamičkih nizova:

• Povećana složenost – programer mora ručno osloboditi memoriju kako bi se sprečilo curenje memorije.
• Sporija alokacija – operacije na hipu su sporije u odnosu na operacije na steku.

Kada koristiti statične, a kada dinamičke nizove?

• Statički nizovi: Koristite ih kada je veličina matrice poznata unapred, što rezultira jednostavnijim i bržim kodom.
• Dinamički nizovi: Koristite ih kada veličina matrice zavisi od korisničkog unosa ili drugih faktora koji se određuju u vreme izvršavanja programa.

Prednosti korišćenja std::vector umesto dinamičkih nizova

C++ standardna biblioteka pruža strukturu podataka std::vector, koja pojednostavljuje upravljanje dinamičkom memorijom i eliminiše potrebu za ručnom alokacijom i oslobađanjem memorije pomoću new i delete. Korišćenjem vektora, program postaje sigurniji i lakši za održavanje.

Prednosti std::vector:

• Automatska alokacija i oslobađanje memorije – nema potrebe za ručnim pozivima new i delete.
• Bolja bezbednost – vektori sprečavaju curenje memorije i probleme sa pokazivačima.
• Jednostavniji kod – smanjuje se broj linija koda i izbegavaju se složene operacije sa pokazivačima.

Ovaj način korišćenja vektora omogućava automatsko oslobađanje memorije po završetku programa i pojednostavljuje sintaksu u odnosu na rad sa pokazivačima.

Ispisivanje matrica u C++

Za ispisivanje matrice u C++ koristi se ugnježdena for petlja. Na primer, ukoliko imamo matricu a dimenzija m×n, kod za ispisivanje može izgledati ovako:

cout << "Matrica ispisivanje:" << endl;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " ";

    }
cout << endl;

}

Posle pokretanja i unosa podataka, u konzoli će biti prikazana matrica.

Kopiranje matrice u C++ jeziku

Da bi se kopirali elementi dinamički alocirane matrice, kreiraćemo posebnu funkciju koja prima kao parametar pokazivač na matricu i dimenzije m i n. Prosleđivanjem pokazivača na matricu obezbeđuje se da svaka promena izvršena unutar funkcije bude odraz na originalnu matricu. Kopiranje se, dakle, vrši prepisivanjem podataka u novu matricu, koja se zatim vraća kao povratna vrednost.

int **copyMatrix(int **original, int m, int n) {
int **copy;

    copy = newint*[m]; // Alokacija niza pokazivača (m redova)
for (int i = 0; i < m; i++) {

        copy[i] = newint[n]; // Alokacija memorije za svaki red (n kolona)
for (int j = 0; j < n; j++) {

            copy[i][j] = original[i][j]; // Kopiranje vrednosti

        }

    }
return copy; // Vraća kopiranu matricu

}

Budući da se matrica ispisuje više puta, preporučuje se kreiranje posebne funkcije za ispisivanje, koja prima pokazivač na matricu i dimenzije m i n kao parametre.

// Funkcija za ispis matrice
void printMatrix(int **matrix, int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";

        }
cout << endl;

    }

}

U glavnoj funkciji, nova matrica se kreira pozivom funkcije za kopiranje, a zatim se ispisuje:

int **B;

B = copyMatrix(A, m, n);

printMatrix(B, m, n);

Nakon pokretanja aplikacije, prikazaće se rezultat kopiranja elemenata matrice.

Transponovana matrica

Transponovana matrica se dobija zamenom redova i kolona početne matrice. Ovaj postupak je često koristan, na primer, u procesu određivanja inverzne matrice.

Transponovana matrica (A^T) se može odrediti u posebnoj funkciji, kao što je prikazano u sledećem kodu:

void transponovana(int **a, int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Zamena elemenata: a[i][j] se menja sa a[j][i]
int temp = a[i][j];

            a[i][j] = a[j][i];

            a[j][i] = temp;

        }
cout << endl;

    }

}

Napomena: U unutrašnjoj for petlji, iteracija počinje sa j = i, jer su elementi u kolonama sa j ≤ i već zamenjeni.

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

Računanje determinante kvadratne matrice

U nastavku je prikazan primer zadatka gde se unosi veličina kvadratne matrice, a zatim se učitavaju njeni elementi. Funkcija koja računa determinantu koristi rekurzivan algoritam.

Primer ulaza:
3
3 5 6
2 -6 3
0 1 7

Primer izlaza:
-193

Ovaj zadatak detaljno objašnjava koncept rekurzivnih algoritama za računanje determinante, što može biti korisno za dublje razumevanje algebarskih operacija nad matricama.

Modernizacija koda u novijim verzijama C++

U modernom C++-u uvedene su brojne značajke koje čine kod sažetijim, čitljivijim i sigurnijim. Iako prethodni primeri prikazuju tradicionalni način rada sa dinamičkim matricama, sledeći odeljak daje uvid u neke od najznačajnijih poboljšanja koja možete primeniti koristeći moderne standarde:

Range-based for petlje

Umesto klasičnih for petlji koje koriste indeksiranje, range-based for petlje omogućavaju direktnu iteraciju kroz elemente kontejnera, čime se kod pojednostavljuje i čini preglednijim.

Primer:

for (const auto& element : container) {
    cout << element << endl;
}
        

Smart pointer-i

Upotreba pametnih pokazivača (kao što su std::unique_ptr i std::shared_ptr) umanjuje rizik od curenja memorije, jer se upravljanje životnim ciklusom objekata vrši automatski.

Primer:

std::unique_ptr<int[]> array(newint[size]);
        

Initializer liste

Inicijalizacija kontejnera pomoću initializer list-eva pojednostavljuje kod i omogućava pregledniju sintaksu.

Primer:

std::vector<int> v = {1, 2, 3, 4, 5};
        

Lambda izrazi

Lambda izrazi omogućavaju definisanje anonimnih funkcija direktno na mestu korišćenja. Ovo je naročito korisno pri pisanju prilagođenih komparatora za sortiranje ili drugih operacija koje zahtevaju kratke funkcije.

Primer:

sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    return a > b;
});
        

Implementacijom ovih modernih tehnika, primeri koda mogu biti ne samo ažurirani, već i prilagođeni najboljim praksama savremenog C++ programiranja. Ovaj dodatak pruža korisnicima smernice za unapređenje koda bez potrebe za izmenom postojećih primera.

U ovom primeru prikazujemo kako koristiti modernije pristupe za rad sa dinamičkim dvodimenzionalnim nizovima u C++.

1️⃣ Korišćenje std::vector za dinamičke dvodimenzionalne nizove

Koristimo std::vector kako bismo olakšali upravljanje memorijom i izbegli ručne alokacije.

// Uključivanje biblioteka#include<iostream>#include<vector>void popuniMatricu(std::vector<std::vector<int>>& matrica, int m, int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            matrica[i][j] = i * n + j + 1;
        }
    }
}

void prikaziMatricu(conststd::vector<std::vector<int>>& matrica) {
    for (constauto& red : matrica) {
        for (int vrednost : red) {
            std::cout << vrednost << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    int m = 3, n = 4;
    std::vector<std::vector<int>> matrica(m, std::vector<int>(n));

    popuniMatricu(matrica, m, n);
    prikaziMatricu(matrica);

    return 0;
}
        

2️⃣ Korišćenje std::unique_ptr za dinamičke nizove

Koristimo pametne pokazivače kako bismo automatski upravljali memorijom.

// Uključivanje biblioteka#include<iostream>#include<memory>int main() {
    int m = 3, n = 4;
    std::unique_ptr<std::unique_ptr<int[]>[]> matrica = std::make_unique<std::unique_ptr<int[]>[]>(m);

    for (int i = 0; i < m; i++) {
        matrica[i] = std::make_unique<int[]>(n);
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            matrica[i][j] = i * n + j + 1;
            std::cout << matrica[i][j] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}
        

✅ Zaključak

Najbolji izbor zavisi od slučaja upotrebe:

• std::vector - Najlakši i najbezbedniji za većinu situacija.
• std::unique_ptr - Sigurniji način za ručno upravljanje memorijom.
• std::array - Najbrži za statičke nizove fiksne veličine.

Pametni pokazivači

Pametni pokazivači (smart pointers) u C++-u, kao što su std::unique_ptr, std::shared_ptr i std::weak_ptr, koriste se za automatsko upravljanje dinamički alociranom memorijom. Njihova glavna prednost je da se memorija automatski oslobađa kada objekt više nije u upotrebi, čime se smanjuje rizik od curenja memorije i drugih grešaka povezanih sa ručnim upravljanjem memorijom (new i delete).

Kada i zašto koristiti pametne pokazivače?

Automatsko oslobađanje memorije: Pametni pokazivači koriste princip RAII (Resource Acquisition Is Initialization) da bi osigurali da se memorija oslobodi čim objekat izađe iz opsega.
Bezbednost: Oni pomažu da se izbegnu greške kao što su dvostruko oslobađanje memorije (double deletion) ili curenje memorije (memory leak).
Jednostavnost koda: Kod postaje čitljiviji i jednostavniji za održavanje jer ne morate ručno pratiti kada se memorija oslobađa.

Primer upotrebe pametnih pokazivača za dinamičku matricu (drugi primer)
U ovom primeru ćemo kreirati dvodimenzionalnu matricu kao jedan kontinuirani blok memorije, što može biti efikasnije u pogledu pristupa memoriji. Koristićemo std::unique_ptr sa tipom pokazivača na niz (int[]).

Objašnjenje:
- Alociramo jedan blok memorije veličine m * n.
- Kreiramo pomoćnu funkciju indeks, koja iz dvodimenzionalnih koordinata (i, j) računa odgovarajući indeks u jednodimenzionalnom nizu.
- Koristimo ove koordinate za pristup elementima matrice.

// Funkcija za konverziju 2D indeksa u 1D indeksint indeks(int i, int j, int n) {
    return i * n + j;
}
// Funkcija za popunjavanje matricevoid popuniMatricu(int* matrica, int m, int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            matrica[indeks(i, j, n)] = i + j; // Primer: zbir indeksa reda i kolone
        }
    }
}
// Funkcija za ispis matricevoid prikaziMatricu(int* matrica, int m, int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << matrica[indeks(i, j, n)] << " ";
        }
        std::cout << endl;
    }
}
int main() {
    int m = 3, n = 4;
// Kreiranje pametnog pokazivača za kontinuirani blok memorije
    std::unique_ptr<int[]> matrica = std::make_unique<int[]>(m * n);


    popuniMatricu(matrica.get(), m, n);

    prikaziMatricu(matrica.get(), m, n);

return 0;
}
    

U ovom primeru, funkcija std::make_unique alocira memoriju za m * n elemenata tipa int. Funkcija indeks se koristi za pretvaranje dvodimenzionalnih koordinata u odgovarajući indeks u jednodimenzionalnom nizu. Na ovaj način se postiže efikasniji pristup memoriji, a pametni pokazivač automatski oslobađa memoriju kada matrica izađe iz opsega.

Dodatno objašnjenje:
Zašto koristiti pametne pokazivače?
Oni automatski upravljaju memorijom, što smanjuje šansu za greške kao što su curenje memorije.
Kod postaje sigurniji i jednostavniji za održavanje jer nema potrebe za ručnim pozivima delete[].
Kada koristiti ovaj pristup?
Kada radite sa velikim dinamičkim strukturama podataka ili kompleksnim objektima, a želite da se brinete samo o logici aplikacije, a ne o upravljanju memorijom.