Tydzień temu nauczyliśmy się jak dynamicznie alokować pamięć dla tablicy jednowymiarowej. Wyraz ,,dynamicznie’’ oznaczał tyle, że rozmiar tablicy, którą chcemy zaalokować, poznamy dopiero w trakcie wykonywania programu i nie jesteśmy w stanie go określić (konkretną liczbą) na etapie kompilacji. Kod dokonujący dynamicznej alokacji tablicy jednowymiarowej wygląda tak:
#include <stdlib.h>
void main() {
double *tab;
int n;
"Podaj n: ");
printf("%d", &n);
scanf(
double *)malloc(n * sizeof(double));
tab = (// ... operacje na tablicy
free(tab); }
Dziś nauczymy się:
Język C pozwala na używanie tablic wielowymiarowych. Wyobraźmy sobie – tablica dwuwymiarowa doskonale nadaje się do przechowywania np. macierzy1. Przyjrzyjmy się więc fragmentowi kodu, który zadeklaruje dwuwymiarową tablicę o wymiarze 3×4. Możemy ją utożsamić z macierzą o takim samym wymiarze.
void main() {
double A[3][4]; // deklaracja tablicy 2-wymiarowej
0][0] = 1.; // przypisanie wartosci
A[0][1] = 1.5; // poszczegolnym elementom
A[0][2] = 0.;
A[0][3] = -2.7;
A[//...
2][3] = 8.;
A[ }
Przypomnijmy, że w przypadku tablic deklarowanych statycznie nie ma potrzeby ich zwalniania. Kompilator sam o to dba (tak jak w przypadku wszystkich zmiennych, które do tej pory deklarowaliśmy – one też są automatycznie niszczone przez kompilator). Powyższą macierz możemy też wypełnić wartościami w nieco zgrabniejszy sposób niż przez zapisanie dwunastu kolejnych linijek przypisań. Możemy to zrobić już w trakcie deklaracji tablicy, dzięki liście inicjalizującej. Dokonuje się tego tak (dla przypomnienia: znak ,,\’’ oznacza, że długa instrukcja będzie kontynuowana w następnej linii):
double A[3][4] = {{1., 1.5, 0., -2.7},\
3., 2.5, 7., 0.},\
{-0., 1., -3., 8.}}; {
W ten sposób stworzymy poniższą macierz: A=(11.50−2.7−32.57001−38) Pozostaje wytłumaczyć jeszcze, w jaki sposób odwołujemy się do elementów w dwuwymiarowej tablicy. Robimy to analogicznie do tablicy jednowymiarowej, tylko tym razem podajemy dwa indeksy. Wartość pierwszego indeksu to numer wiersza, drugiego – numer kolumny. Przykładowo, do elementu macierzy a32 odwołamy się przez napisanie a[2][1]
. W ten sposób możemy wyłuskać wartość przechowywaną pod tym elementem lub za pomocą operatora ,,=’’ przypisać temu elementowi nową wartość.
W funkcji main()
napisz kod, w którym zadeklarujesz i zainicjalizujesz dowolnymi wartościami dwie różne tablice dwuwymiarowe. Jedna ma przechowywać macierz kwadratową o wymiarze 2×2, a druga macierz kwadratową o wymiarze 3×3. Napisz kod, który dla każdej z tych macierzy policzy wyznacznik.
Czas na dynamiczną alokację. Dwuwymiarową tablicę o rozmiarze N×M alokujemy w następujący sposób:
Podsumowując, będziemy mieli w pamięci N bloków, każdy o długości M. Spójrzmy na poniższy kod:
double **A;
double **)malloc(N * sizeof(double *)); A = (
Przypomnijmy sobie, że jednowymiarową tablicę alokowaliśmy wykorzystując wskaźnik do typu double
. Tym razem będziemy alokować wskaźnik do wskaźnika na typ double
. Dlatego używamy ,,podwójnego’’ wskaźnika. W instrukcji powyżej, adres zwracany przez funkcję malloc()
rzutujemy więc na podwójny wskaźnik double **
. Wywołując funkcję malloc()
musimy wiedzieć, ile miejsca potrzebujemy. Przechowywać będziemy wskaźniki (do odpowiednich tablic jednowymiarowych przechowujących wiersze), dlatego jako argument funkcji sizeof()
podajemy double *
.
Teraz możemy zaalokować tablice jednowymiarowe do przechowywania wierszy:
for(int i = 0; i < N; ++i)
double *)malloc(M * sizeof(double)); A[i] = (
Każdemu z elementów pierwszej tablicy przyporządkowaliśmy tablicę do przechowywania każdego z wierszy. Tym razem adres zwrócony przez funkcję malloc()
rzutujemy na typ double *
, a argumentem funkcji sizeof()
jest typ zmiennej przechowywanej w tej tablicy, czyli już zwykła zmienna double
. Tablica dwuwymiarowa jest już gotowa – możemy jej używać.
Po zakończeniu pracy z tablicą, trzeba koniecznie zwolnić pamięć wykorzystywaną przez nią. Najpierw zwalniamy tablice odpowiadające każdemu z wierszy, a na końcu zwalniamy pierwotną tablicę wskaźników do wierszy. Dokonuje tego poniższy kod:
for(int i = 0; i < N; ++i)
free(A[i]);
free(A);
Zbierzmy wszystkie instrukcje w jednym miejscu. Chcemy zaalokować dwuwymiarową tablicę zmiennych typu int
. Dokonujemy tego tak:
/* alokacja pamieci */
int **A;
int **)malloc(N * sizeof(int *));
A = (for(int i = 0; i < N; ++i)
int *)malloc(M * sizeof(int));
A[i] = (
/* wykonujemy dowolne operacje na tablicy */
/* zwalniamy pamiec */
for(int i = 0; i < N; ++i)
free(A[i]); free(A);
main
w sposób dynamiczny miejsce dla macierzy A o wymiarze [3×3] oraz dwóch 3-elementowych wektorów v1 i v2. Wypełnij macierz i jeden z wektorów dowolnymi liczbami.drukujMacierz
, która:
maxElem
, która dla zadanej macierzy zwraca do funkcji main
wartość największego co do modułu elementu tej macierzy oraz jego indeksy i i j.main
kod, który dokona mnożenia macierzy A przez wektor v1 a wynik zapisze do wektora v2. Mnożenie macierzy przez wektor określone jest wzorem: wi=m−1∑j=0aijvjvoid matVecMultiply(double **A, double *v1, double *v2, int n)
i dokonaj wywołania z funkcji main
. 6. Zmodyfikuj powyższy program tak, aby rozmiar n był wczytywany z klawiatury. Zaś elementy tablicy były generowane zgodnie ze wzorem aij=i+1j+1,(i,j=0,…,n−1) a elementy wektora według wzoru vi=i+1,(i=0,…,n−1) Następnie oblicz iloczyn tej macierzy przez ten wektor, korzystając ze swojej funkcji matVecMultiply
. Wynik wyświetl na ekranie oraz sprawdź czy jest poprawny2. 7. Napisz funkcję
double **A, double **B, double **C,\
matMatMultiply(int nA, int mA, int nB, int mB)
służącą do mnożenia dwóch macierzy prostokątnych (A o wymiarze nA×mA i B o wymiarze nB×mB). Wynik powinien być zapisany do macierzy C. Zadbaj w funkcji main
o to, aby pamięć zaalokowana dla macierzy C była odpowiedniej wielkości – zgodnej z regułami mnożenia macierzy. Uwaga: Pamiętaj, aby zwolnić dynamicznie alokowaną pamięć3.
Zastanów się dlaczego poniższy kod nie działa poprawnie?
void initialize_vec_BAD(int *ptr, int N) {
int *)malloc(N * sizeof(int));
ptr = (for (int j = 0; j < N; ++j)
3 * j;
ptr[j] =
"Wewn. funkcji initialize:\n");
printf(for (int j = 0; j < N; ++j) {
"%d ", ptr[j]);
printf(
}"\n");
printf(
}
int main() {
int N = 10;
int *v;
initialize_vec_BAD(v, N);
"Wewn. funkcji main:\n");
printf(for (int j = 0; j < N; ++j){
"%d ", v[j]);
printf(
}"\n");
printf(
free(v);
getchar(); }
Popraw deklarację i ciało funkcji initialize_vec_BAD
.
Wskazówka: prawidłowa deklaracja w języku C powinna wyglądać tak:
void initialize_vec(int **ptr, int N)
Tak naprawdę, tablica może przechowywać o wiele więcej struktur. Przykładowo programując grę w szachy moglibyśmy użyć dwuwymiarowej tablicy o wymiarze 8x8 i w odpowiednie pola tej tablicy wpisać liczby, które symbolizowałyby konkretną figurę. A gra w statki? Można podobnie. Z drugiej strony, w obliczeniach numerycznych wielkie macierze o rozmiarze rzędu kilkuset tysięcy do kilku milionów elementów i większe, przechowuje się w postaci tablicy jednowymiarowej. W zagadnieniach inżynierskich macierze są często rzadkie, tzn. takie, które w stosunku do całkowitej liczby swoich elementów mają bardzo niewiele elementów, które nie są zerem. Taką macierz efektywnie jest trzymać w pamięci jako tablicę jednowymiarową (przyjmując specjalny format, który pomija wszystkie zera – np. format CSR (ang. Compressed Sparse Row) jest szeroko stosowanym formatem zapisywania macierzy rzadkiej w trzech tablicach jednoelementowych). Tak wielka macierz przechowywana jawnie najpewniej nie zmieściłaby się w pamięci żadnego dostępnego nam komputera.↩︎
Dla takiej macierzy i takiego wektora łatwo jest wygenerować analityczny wynik. Zapisz sobie małą macierz według zadanego wzoru i odpowiadający wektor a na pewno szybko zauważysz prawidłowość. Będziesz wtedy wiedzieć, jaki wynik powinien dać program. Tak się testuje programy na wczesnych etapach rozwoju.↩︎
Niezwolnienie pamięci prowadzi do jej wycieków i w przypadku pewnych operacji wykonywanych w pętlach może doprowadzić do tego, że Twój program wykorzysta całą pamięć operacyjną komputera i przestanie działać.↩︎