Tablice dwuwymiarowe

Tablice dwuwymiarowe o wartościach liczbowych reprezentują macierze. W języku C definicja tablicy

dwuwymiarowej wygląda następująco:

typ nazwa[liczba_wierszy][liczba_kolumn];

np.

int tab[5][10];

definiuje tablicę typu

int

o 5 wierszach i 10 kolumnach. Indeksy

zmieniają się od wartości 0, zatem

tab[0][2]

jest odwołaniem do elementu tablicy z wiersza 0 i

kolumny 2 (trzeciej z kolei). Elementy tablicy umieszczone są w pamięci komputera wierszami, co

oznacza, że element

tab[i][j]

sąsiaduje z elementem

tab[i][j+1],

natomiast ostatni

element jednego wiersza sąsiaduje z pierwszym elementem kolejnego wiersza np.

tab[0][9]

sąsiaduje z

tab[1][0].

Tablicę można zainicjować podając listę wartości początkowych w

nawiasach klamrowych. Każdy wiersz inicjowany jest w osobnej podliście. Analogicznie jak w

przypadku tablic jednowymiarowych, jeśli liczba wartości początkowych jest mniejsza niż liczba

elementów tablicy, pozostałe elementy zostają wyzerowane. Definicja:

int tab[2][3]={{0, 1, 2}, {9, 8, 7}};

tworzy tablicę:

0 1 2

9 8 7

W języku C tablica dwuwymiarowa jest rzeczywiście tablicą jednowymiarową, której elementami są

tablice jednowymiarowe (wiersze tablicy dwuwymiarowej). Można ją interpretować jako tablicę

wskaźników do wierszy

(tab[0], tab[1],..). tab[0], tab[1],..

podobnie jak

tab

są stałymi, można się do nich odwoływać w programie, ale nie można ich modyfikować. Nazwa

tablicy

tab

jest zarazem adresem elementu

tab[0][0],

a także adresem wiersza zerowego

(tab[0]).

Zatem

tab, &tab[0][0], tab[0]

mają takie same wartości, natomiast

tab[1]

jest adresem pierwszego wiersza tablicy (drugiego z kolei), czyli adresem elementu

tab[1][0].

Usytuowanie elementów tablicy tab w pamięci przedstawia poniższy schemat. Czerwonymi literami

oznaczono adresy, a strzałki wskazują na docelowe miejsca w pamięci.

tab

tab[0]

tab[0][0] tab[0][1] tab[0][2] tab[0][2]

tab[1]

tab[1][0] tab[1][1] tab[1][2] tab[1][2]

Wczytywanie i wypisywanie macierzy wierszami

Aby wczytać tablicę wierszami trzeba zastosować dwie pętle

for.

Zewnętrzna pętla związana jest z

numerami wierszy, natomiast wewnętrzna z numerami kolumn. Poniższy program wczytuje tablicę

dwuwymiarową, przy założeniu, że kolejne elementy wczytywane są wierszami i wyświetla ją na

ekranie w taki sposób, że każdy wiersz znajduje się w nowej linii.

#include <stdio.h>
#include <stdlib.h>
#define N 3
#define M 4

int main()
{
int a[N][M];
int i,j;
for (i=0; i<N; i++)
for (j=0; j<M; j++)
scanf("%d",&a[i][j]);
printf("\n\nmacierz wierszami:\n");
for (i=0; i<N; i++)
{
printf("\n");
for (j=0; j<M; j++)
printf("%d ",a[i][j]);
}
printf("\n");
}

Wczytywanie macierzy kolumnami

Przy wczytywaniu tablicy kolumnami zewnętrzna pętla związana jest z numerami kolumn, natomiast

wewnętrzna z numerami wierszy. Poniższy fragment program wczytuje tablicę dwuwymiarową,

której elementy wczytywane są z klawiatury kolumnami.

for (j=0; j<M; i++)
for (i=0; i<N; j++)
scanf("%d",&a[i][j]);

Przykład - zliczanie elementów niezerowych nad główną przekątną wraz z przekątną

Zadanie polega na policzeniu ile jest elementów niezerowych w zadanej macierzy

kwadratowej

a[n][n]

ponad główna przekątną biorąc pod uwagę również elementy z przekątnej. Interesujący

fragment macierzy przedstawiony jest poniżej:

a[0][0] a[0] [1] a[0][2] a[0][3]

a[1][0] a[1] [1] a[1][2] a[1][3]

a[2][0] a[2] [1] a[2][2] a[2][3]

a[3][0] a[3] [1] a[3][2] a[3][3]

Warto zauważyć, że elementy tablicy, które będziemy rozważać, mają oba indeksy, czyli numer

wiersza i numer kolumny, identyczne (są to elementy z przekątnej) lub indeks drugi, określający

numer kolumny jest większy od indeksu pierwszego, określającego numer wiersza. Przeglądanie

tablicy można więc zorganizować w ten sposób, że w zewnętrznej pętli zmienna sterująca

i

będzie

wskazywała numer wiersza i będzie się zmieniała od

0

do

n-1,

natomiast pętla wewnętrzna będzie

sterowana indeksem kolumny

j

i będzie się zmieniała od aktualnego numeru wiersza

- i,

czyli od

elementu z przekątnej do końca wiersza

(n-1).

Oto kod programu:

#include <stdio.h>
#include <stdlib.h>
#define W 4
#define K 4

int main()
{
int i,j,s=0;
int a[W][K];
for(i=0;i<W;i++)
for(j=0;j<K;j++)
scanf("%d",&a[i][j]);
for(i=0;i<W;i++)
{
printf("\n");
for(j=0;j<K;j++)
printf("%3d ",a[i][j]);
}
for (i=0;i<W;i++)
for(j=i;j<K;j++)
if(a[i][j]!=0) s++;
printf("\n\t%d el. niezerowych nad gl. przekatna\n",s);
}

A oto przykładowy wynik działania programu z obrysowanym czerwoną linią obszarem ponad

przekątną:

Tablice dwuwymiarowe jako parametry funkcji

Programy przetwarzające tablice dwuwymiarowe wygodnie jest podzielić na funkcje, których

zadaniem będzie wczytanie, wypisywanie tablic oraz inne operacje. Jak już wiemy tablice są

przekazywane przez adres, co oznacza, że w odniesieniu do tablic funkcja działa w samej przestrzeni

adresowej, co funkcja wywołująca. Aby przekazać do funkcji tablicę dwuwymiarową jako parametr

trzeba podać poza nazwą również liczbę kolumn tablicy. Liczba kolumn wraz z wskaźnikiem do

początku tablicy wnosi wystarczą informację o rozmieszczeniu elementów, liczba wierszy nie jest

istotna. Definiując parametry formalne można podać oba wymiary tablicy:

int n,m,a[n][m];

jak np. w funkcji

czytaj_wierszami

lub tylko liczbę kolumn:

int m,a[][m];

jak w funkcji

pisz_wierszami.

Funkcje występujące w programie są typu

void

, co oznacza, że nie zwracają one żadnej wartości,

ich zadaniem jest wypełnienie tablicy, lub wypisanie jej zawartości na ekranie.

Oto kod programu:

#include <stdio.h>
#include <stdlib.h>
#define N 3
#define M 4

void czytaj_wierszami(a,n, m)
int n,m,a[n][m];
{
int i,j;
for (i=0; i<n; i++)
{
for (j=0; j<m; j++)
scanf("%d",&a[i][j]);
}
}

void czytaj_kolumnami(a, n, m)
int n,m,a[n][m];
{
int i,j;
for (i=0; i<m; i++)
{
printf("\n");
for (j=0; j<n; j++)
scanf("%d",&a[j][i]);
}
}

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

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

int main(int argc, char *argv[])
{
int a[N][M];
int i,j;
printf("\n\n");
czytaj_wierszami(a,N,M);
printf("\n\n\tmacierz wierszami:\n");
pisz_wierszami(a,N,M);
printf("\n\n\tmacierz kolumnami:\n");
pisz_kolumnami(a, N, M);
}

A oto efekt przykładowego uruchomienia programu:

Tablice dwuwymiarowe – wskaźniki, alokacja pamięci

Tablice w języku C mogą być zadeklarowane z użyciem dwóch wskaźników

(int **a;).

Wówczas pamięć dla tablicy należy zarezerwować korzystając z funkcji

malloc.

Ilustruje to

poniższy program. Program wczytuje tablicę dwuwymiarową

a

i tworzy tablicę jednowymiarową

(wektor

b

), której elementy są maksymalnymi elementami poszczególnych wierszy tablicy

wejściowej, a także wektor minimalnych elementów z poszczególnych kolumn danej tablicy (wektor

c

):

a[0][0] a[0] [1] a[0][2] … a[0][m] b[0] =max( a[0][i],i=0,..m)

a[1][0] a[1] [1] a[1][2]…. a[1][m] b[1] =max( a[1][i],i=0,..m)

a[2][0] a[2] [1] a[2][2] … a[2][m] b[2] =max( a[2][i],i=0,..m)

…. ….. …. …….. ……

a[n][0] a[n] [1] a[n][2] … an][m] b[m] =max( a[n][i],i=0,..m)

c[0] c[1] c[2] … c[n]

#include <stdio.h>
#include <stdlib.h>
#define N 5
#define M 5

int ffmax(int *x, int n)
{
int mm,i;
mm=x[0];
for(i=1; i<n; i++)
{
if( x[i] > mm )
mm=x[i];
}
return mm;
}

int ffmin(int **x, int k, int n)
{
int mm,i;
mm=x[0][k];
for(i=1; i<n; i++)
{
if( x[i][k] < mm )
mm=x[i][k];
}
return mm;
}



void czytaj_wierszami(int **a, int n, int m)

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

void pisz_wierszami(int **a, int n, int m)
{
int i,j;
for (i=0; i<n; i++)
{
printf("\n");
for (j=0; j<m; j++)
printf("%d ",a[i][j]);
}
}

void maxwier(int **a, int *b, int n, int m)
{
int i,j;
for(i=0;i<n;i++)
b[i]=ffmax(a[i],m);

}

void minkol(int **a, int *b, int n, int m)
{
int i,j;
for(i=0;i<m;i++)
b[i]=ffmin(a,i,n);
}

int main(int argc, char *argv[])
{
int **a;
int *b,*c;
int i,j;

if(!(a=(int**)malloc(N*sizeof(int*))))return 1;
for(j=0;j<N;j++)
if(!(a[j]=(int*)malloc(M*sizeof(int))))return 1;
if(!(b=(int*)malloc(N*sizeof(int))))return 1;
if(!(c=(int*)malloc(M*sizeof(int))))return 1;

czytaj_wierszami(a, N, M);
printf("\n\nmacierz wierszami:\n");
pisz_wierszami(a, N, M);

maxwier(a,b,N,M);
printf ("\n\nwynik:\n");
for (i=0;i<M;i++)
printf("%d ",b[i]);
printf ("\n\n\n");
minkol(a,c,N,M);
printf ("\n\nwynik:\n");
for (i=0;i<N;i++)
printf("%d ",c[i]);
printf ("\n\n\n");
for(i=0;i<M;i++)
free(a[i]);
free (a);
free(b);
free(c);
}

Rezerwacja pamięci dla tablicy a została wykonana za pomocą poleceń:

if(!(a=(int**)malloc(N*sizeof(int*))))return 1;

for(j=0;j<N;j++)

if(!(a[j]=(int*)malloc(M*sizeof(int))))return 1;

Najpierw zarezerwowane zostało N*sizeof( *int) (4*N) bajtów na tablicę wskaźników do wierszy, a

następnie N*M*4 bajtów na N wierszy po M elementów typu

int.

Jeśli funkcja

malloc

zakończy się

niepowodzeniem, co oznacza, że nie udało się zarezerwować miejsca w pamięci operacyjnej (na

stercie procesu) program kończy się zwracając kod błędu = 1. Zwolnienie pamięci realizowane jest za

pomocą funkcji

free.

A oto efekt przykładowego uruchomienia programu: