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;
printf("Podaj n: ");
scanf("%d", &n);
tab = (double *)malloc(n * sizeof(double));
// ... 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 \times 4\). Możemy ją utożsamić z macierzą o takim samym wymiarze.
void main() {
double A[3][4]; // deklaracja tablicy 2-wymiarowej
A[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.;
}
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):
W ten sposób stworzymy poniższą macierz: \[
\mathbf{A} =
\left(
\begin{array}{cccc}
1 & 1.5 & 0 & -2.7 \\ -3 & 2.5 & 7 & 0 \\ 0
& 1 & -3 & 8
\end{array}
\right)
\] 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 \(a_{32}\) 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 \times 2\), a druga macierz kwadratową o
wymiarze \(3 \times 3\). Napisz kod,
który dla każdej z tych macierzy policzy wyznacznik.
Czas na dynamiczną alokację. Dwuwymiarową tablicę o rozmiarze \(N \times 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:
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:
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:
Zbierzmy wszystkie instrukcje w jednym miejscu. Chcemy zaalokować
dwuwymiarową tablicę zmiennych typu int
. Dokonujemy tego
tak:
/* alokacja pamieci */
int **A;
A = (int **)malloc(N * sizeof(int *));
for(int i = 0; i < N; ++i)
A[i] = (int *)malloc(M * sizeof(int));
/* 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 \times 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: \[
w_i = \sum\limits_{j=0}^{m-1}{a_{ij}v_j}
\]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 \[
a_{ij} = \frac{i+1}{j+1}, (i, j = 0, \ldots, n-1)
\] a elementy wektora według wzoru \[
v_i = i+1, (i = 0,\ldots,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ę
służącą do mnożenia dwóch macierzy prostokątnych (\(\bf{A}\) o wymiarze \(n_A \times m_A\) i \(\bf{B}\) o wymiarze \(n_B \times m_B\)). Wynik powinien być
zapisany do macierzy \(\bf{C}\). Zadbaj
w funkcji main
o to, aby pamięć zaalokowana dla macierzy
\(\bf{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) {
ptr = (int *)malloc(N * sizeof(int));
for (int j = 0; j < N; ++j)
ptr[j] = 3 * j;
printf("Wewn. funkcji initialize:\n");
for (int j = 0; j < N; ++j) {
printf("%d ", ptr[j]);
}
printf("\n");
}
int main() {
int N = 10;
int *v;
initialize_vec_BAD(v, N);
printf("Wewn. funkcji main:\n");
for (int j = 0; j < N; ++j){
printf("%d ", v[j]);
}
printf("\n");
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:
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 \(8 x 8\) 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ć.↩︎