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 = new int*[m]; // Alokacija niza pokazivača
for (int i = 0; i < m; i++) {
matrica[i] = new int[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 matrice
for (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:
int **A;
// Deklaracija pokazivača na pokazivač (dinamička matrica)
A = new int*[n]; // Alokacija memorije za redove matrice
Dalje, kreiranje i učitavanje matrice može se realizovati na sledeći način:
// Deklaracija dvodimenzionalnog niza
int **A;
// Alokacija memorije za redove
A = new int*[n];
for (int i = 0; i < n; i++) {
// Alokacija memorije za svaki red (m kolona)
A[i] = new int[m];
for (int j = 0; j < m; j++) {
// Unos elemenata matrice
cin >> A[i][j];
}
}
Da bi se ispisala učitana matrica, koristi se ugnježdena for petlja:
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << A[i][j] << " ";
}
cout << endl;
}
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:
for (int i = 0; i < n; i++) {
delete[] A[i]; // Brisanje svakog reda
}
delete[] A; // Brisanje niza pokazivača
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.
// Alternativno rešenje korišćenjem std::vector
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// Kreiranje dvodimenzionalnog vektora
vector<vector<int>> A(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> A[i][j];
}
}
// Ispis matrice
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << A[i][j] << " ";
}
cout << endl;
}
return 0;
}
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.
Testirajte svoj kod u editoru ispod!
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 = new int*[m]; // Alokacija niza pokazivača (m redova)
for (int i = 0; i < m; i++) {
copy[i] = new int[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.
Inverzna matrica A-1
Transponovana matrica (AT) 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:
{
transponovana(A, n); // poziv funkcije transponovana
cout << "Transponovana matrica" << endl;
ispisatiMatricu(A, n);
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(new int[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(const std::vector<std::vector<int>>& matrica) {
for (const auto& 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 indeks
int indeks(int i, int j, int n) {
return i * n + j;
}
// Funkcija za popunjavanje matrice
void 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 matrice
void 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.
|
Sledeće
Stringovi u C++ jeziku >| |