Reprezentacja macierzy w pamięci komputera


Tematy pokrewne   Podrozdziały
Macierze
Podstawowe pojęcia dotyczące macierzy
Reprezentacja macierzy w pamięci komputera
Mnożenie macierzy przez skalar
Dodawanie macierzy
Transponowanie macierzy
Mnożenie macierzy
Potęgowanie macierzy
Eliminacja Gaussa
Eliminacja Gaussa-Crouta
Wyznacznik macierzy
Rozkład LU
Rozkład LU – rozwiązywanie układu równań liniowych
Rozkład LU – macierz odwrotna
Rozkład LU – wyznacznik macierzy
Podstawowe operacje na tablicach
  Deklarowanie tablic wielowymiarowych
Tworzenie tablic dynamicznych
Tworzenie macierzy dynamicznych
Macierze dynamiczne o dynamicznych rozmiarach
Odczyt macierzy

Deklarowanie tablic wielowymiarowych

Macierze mogą być reprezentowane w pamięci komputera przez tablice dwuwymiarowe. Rozwiązanie to przydaje się w przypadku, gdy z góry znany jest rozmiar macierzy.

Lazarus

Deklarację tablicy w języku Pascal umieszczamy w sekcji deklaracji zmiennych var. Składnia deklaracji tablicy dwuwymiarowej jest następująca:

 

nazwa_tablicy : array[1..liczba wierszy,1..liczba_kolumn] of typ_elementów;

nazwa_tablicy  –  tworzona jest wg zwykłych reguł tworzenia nazw zmiennych w języku Pascal
liczba_wierszy  – określa liczbę wierszy w macierzy
liczba_kolumn  – określa liczbę kolumn w macierzy
typ_elementów  – określa rodzaj informacji przechowywanej w każdym elemencie

 

Słowa array oraz of są słowami kluczowymi, które muszą się pojawić w deklaracji tablicy. Poniżej podajemy kilka przykładów:

 

var
  ...
  a : array[1..3,1..3] of integer; // macierz a 3x3 liczb całkowitych
  x : array[1..4,1..3] of double;  // macierz x 4x3 liczb rzeczywistych
  c : array[1..8,1..5] of char;    // macierz c 8x5 znakowa
  ...
 

Dostęp do elementów macierzy wymaga dwóch indeksów – indeksu wierszowego oraz indeksu kolumnowego. Poniższy przykład inicjuje główną przekątną macierzy a:

 

  a[1,1] := 1;
  a[2,2] := 7;
  a[3,3] := 5;

 

Code::Blocks

Deklarację tablicy umieszczamy w języku C++ na liście deklaracji zmiennych. Składnia jest następująca:

 

typ_danych nazwa_tablicy[liczba_wierszy][liczba_kolumn];

typ_danych  –  określa rodzaj informacji przechowywanych przez deklarowane zmienne
nazwa_tablicy  – tworzona jest wg zwykłych reguł tworzenia nazw zmiennych w języku C++
liczba_wierszy  – określa liczbę wierszy w macierzy
liczba_kolumn  – określa liczbę kolumn w macierzy

 

Poniżej podajemy kilka przykładów deklaracji tablic w C++:

 

...
int    a[3][3];  // macierz a 3x3 liczb całkowitych
double x[4][3];  // macierz x 4x3 liczb rzeczywistych
char   c[8][5];  // macierz c 8x5 znakowa
...
 

Ze względu na specyfikę języka C++ indeksy rozpoczynają się od 0 a nie od 1. Dostęp do elementów macierzy wymaga dwóch indeksów – indeksu wierszowego oraz indeksu kolumnowego. Poniższy przykład inicjuje główną przekątną macierzy a:

 

a[0][0] = 1;
a[1][1] = 7;
a[2][2] = 5;

 

Free Basic

Deklarację tablicy umieszczamy w języku Free Basic w instrukcji Dim. Składnia jest następująca:

 

Dim As typ_danych nazwa_tablicy(1 To liczba_wierszy, 1 To liczba_kolumn)

typ_danych  –  określa rodzaj informacji przechowywanych przez deklarowane zmienne
nazwa_tablicy  – tworzona jest wg zwykłych reguł tworzenia nazw zmiennych
liczba_wierszy  – określa liczbę wierszy w macierzy
liczba_kolumn  – określa liczbę kolumn w macierzy

 

Poniżej podajemy kilka przykładów deklaracji macierzy:

 

...
Dim As Integer a(1 To 3,1 To 3) ' macierz a 3x3 liczb całkowitych
Dim As Double x(1 To 4,1 To 3)  ' macierz x 4x3 liczb rzeczywistych
...
 

Dostęp do elementów macierzy wymaga dwóch indeksów – indeksu wierszowego oraz indeksu kolumnowego. Poniższy przykład inicjuje główną przekątną macierzy a:

 

a(1,1) = 1
a(2,2) = 7
a(3,3) = 5

 

Tworzenie tablic dynamicznych – przypomnienie

Tablica dynamiczna jest strukturą danych, która jest tworzona przez program w trakcie jego wykonywania. Zaletą tablicy dynamicznej jest to, iż dopasowuje się ona dokładnie do wymagań programu, nie marnując bez potrzeby pamięci. Procedura tworzenia tablicy dynamicznej w każdym z naszych trzech języków jest podobna (w języku Free Basic jest w zasadzie identyczna z językiem C++):

 

Tworzenie wskaźnika do danych
FreePascal Code::Blocks FreeBASIC
type
  dptr = array of typ_elementów;
...
var
  A : dptr;
typ_elementów * A;
Dim A As typ_elementów Ptr
Rezerwowanie obszaru pamięci na tablicę A zawierającą n elementów
SetLength(A,n);
A = new typ_elementów[n];
A = New typ_elementów[n]
Dostęp do elementów za pomocą indeksów od 0 do n-1
A[i] := ...
A[i] = ...
A[i] = ...
Usunięcie tablicy dynamicznej, gdy przestanie być potrzebna
SetLength(A,0);
delete [] A;
Delete [] A
Przekazywanie tablicy dynamicznej jako parametru dla procedury/funkcji
procedure p( A : dptr)
void p(typ_elementów * A)
Sub p(A As typ_elementów Ptr)

 

Tworzenie macierzy dynamicznych

Rozwiązanie opiera się na utworzeniu dynamicznej tablicy wskaźników o m elementach (m – liczba wierszy macierzy). Następnie tworzymy dynamicznie m tablic n elementowych (n – liczba kolumn macierzy) i ich adresy przypisujemy poszczególnym wskaźnikom z pierwszej tablicy dynamicznej. Ze względu na specyfikę tablic dynamicznych indeksy muszą jedynie rozpoczynać się od wartości 0, a nie 1. Pierwsza tablica jest tablicą wskaźników wierszy. Kolejne elementy tej tablicy wskazują kolejne wiersze macierzy.

 

Tworzenie wskaźnika do danych
FreePascal Code::Blocks FreeBASIC
type
  nptr = array of typ_elementów;
  mptr = array of nptr;
...
var
  A : mptr;
typ_elementów ** A;
Dim A As typ_elementów Ptr Ptr
Rezerwowanie obszaru pamięci na macierz A[m x n]
SetLength(A,m);
for i := 0 to m - 1 do
  SetLength(A[i],n);
A = new typ_elementów * [m];
for(i = 0; i < m; i++)
  A[i] = new typ_elementów[n];
A = New typ_elementów Ptr [n]
For i = 0 To m
  A[i] = New typ_elementów[n]
Next
Dostęp do elementów za pomocą indeksów od 0 do n-1
A[i][j] := ...
A[i][j] = ...
A[i][j] = ...
Usunięcie tablicy dynamicznej, gdy przestanie być potrzebna
for i = 0 to m - 1 do
  SetLength(A[i],0);
SetLength(A,0)
for(i = 0; i < m; i++)
  delete [] A[i];
delete [] A;
For i = 0 to m - 1
  Delete A[i]
Next
Delete [] A
Przekazywanie macierzy dynamicznej jako parametru dla procedury/funkcji
procedure p( A : mptr)
void p(typ_elementów ** A)
Sub p(A As typ_elementów Ptr Ptr)

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje liczbę wierszy i kolumn macierzy, tworzy tablicę dynamiczną, którą wypełnia liczbami 0, gdy suma indeksów wierszowego i kolumnowego jest parzysta i 1, gdy suma ta jest nieparzysta. Wynikowa macierz zostaje wyświetlona.

 

Lazarus
// Tworzenie macierzy dynamicznej
// Data: 8.02.2011
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program matrix;

type
  NInt = array of integer; // typ tablic wierszy
  MInt = array of NInt;    // typ tablicy wskaźników

// Procedura wypełnia macierz i wyświetla ją
//------------------------------------------
procedure p(m,n : integer; A : MInt);
var
  i,j : integer;
begin
  for i := 0 to m - 1 do
    for j := 0 to n - 1 do A[i][j] := (i + j) mod 2;

  for i := 0 to m - 1 do
  begin
    for j := 0 to n - 1 do write(A[i][j],' ');
    writeln;
  end;
end;

// *** PROGRAM GŁÓWNY ***
//-----------------------

var
  A     : MInt;
  n,m,i : integer;
begin
  write('m = '); readln(m);
  write('n = '); readln(n);

  // tworzymy tablicę wskaźników

  SetLength(A,m);

  // tworzymy kolejne tablice wierszy

  for i := 0 to m - 1 do SetLength(A[i],n);

  // wypełniamy i wyświetlamy macierz

   p(m,n,A);

  // najpierw usuwamy tablice wierszy

  for i := 0 to m - 1 do SetLength(A[i],0);

  // teraz usuwamy tablicę wskaźników

  SetLength(A,0);

end.
Code::Blocks
// Tworzenie macierzy dynamicznej
// Data: 8.02.2011
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>

using namespace std;

// Procedura wypełnia macierz i wyświetla ją
//------------------------------------------
void p(int m, int n, int ** A)
{
  int i,j;

  for(i = 0; i < m; i++)
    for(j = 0; j < n; j++) A[i][j] = (i + j) % 2;

  for(i = 0; i < m; i++)
  {
    for(j = 0; j < n; j++) cout << A[i][j] << " ";
    cout << endl;
  }
}

// *** PROGRAM GŁÓWNY ***
//-----------------------

int main()
{
  int ** A,n,m,i;

  cout << "m = "; cin >> m;
  cout << "n = "; cin >> n;

  // tworzymy tablicę wskaźników

  A = new int * [m];

  // tworzymy kolejne tablice wierszy

  for(i = 0; i < m; i++) A[i] = new int [n];

  // wypełniamy i wyświetlamy macierz

   p(m,n,A);

  // najpierw usuwamy tablice wierszy

  for(i = 0; i < m; i++) delete [] A[i];

  // teraz usuwamy tablicę wskaźników

  delete [] A;

  return 0;
}
Free Basic
' Tworzenie macierzy dynamicznej
' Data: 8.02.2011
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

' Procedura wypełnia macierz i wyświetla ją
'------------------------------------------
Sub p(m As Integer, n As Integer, A As Integer Ptr Ptr)

  Dim As Integer i,j

  For i = 0 To m - 1
    For j = 0 To n - 1
      A[i][j] = (i + j) Mod 2
    Next
  Next

  For i = 0 To m - 1
    For j = 0 To n - 1
      Print Using "& ";A[i][j];
    Next
    Print
  Next
  
End Sub

Dim A As Integer Ptr Ptr
Dim As Integer n,m,i

Input "m = ",m
Input "n = ",n

' tworzymy tablicę wskaźników

A = New Integer Ptr [m]

' tworzymy kolejne tablice wierszy

For i = 0 To m - 1
  A[i] = New Integer [n]
Next

' wypełniamy i wyświetlamy macierz

   p(m,n,A)

' najpierw usuwamy tablice wierszy

For i = 0 To m - 1
  Delete [] A[i]
Next

' teraz usuwamy tablicę wskaźników

Delete [] A

End
Wynik
m = 10
n = 20

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

 

Macierze dynamiczne o dynamicznych rozmiarach

Czasami występuje konieczność zmiany rozmiaru macierzy (np. gdy usuwamy lub dodajemy wiersz/kolumnę). Istnieją wtedy dwa rozwiązania:
  1. Tworzymy macierz o maksymalnym rozmiarze mm x nn. Wewnątrz tej macierzy operujemy na podmacierzy o rozmiarze m x n, gdzie mmm i nnn. Wymiary m i n możemy dowolnie zmieniać, dopóki są zachowane te dwie nierówności. Rozwiązanie to jest nieefektywne pamięciowo, lecz szybkie w działaniu.
  2. Dla macierzy m x n tworzymy macierz nieco większą o rozmiarze mm x nn, gdzie mm = m + z, nn = n + z. Tak utworzona macierz posiada w zapasie z wierszy oraz kolumn. Zatem m i n mogą odpowiednio rosnąć do momentu, aż zostanie spełniona jedna z nierówności:
        m > mm lub n > nn.
    Gdy tak się stanie, tworzymy nową macierz o rozmiarze (m + z) x (n + z). Przenosimy do niej zawartość starej macierzy. Starą macierz usuwamy z pamięci i przypisujemy jej nową macierz. Wymiary mm i nn odpowiednio uaktualniamy: mm = m + z, nn = n + z.

    Podobnie możemy postępować przy zmniejszaniu rozmiaru macierzy. Jeśli będzie spełniona jedna z nierówności:
        mmm - 2z lub nnn - 2z,
    to macierz możemy zmniejszyć. Tworzymy nową macierz o rozmiarze (m + z) x (n + z). Przenosimy do niej zawartość starej macierzy, a starą macierz usuwamy z pamięci. Starej macierzy przypisujemy nową macierz i uaktualniamy wymiary mm i nn.
    Możesz zastanawiać się, dlaczego w powyższych nierównościach pojawiło się 2z zamiast z. Powód jest bardzo prosty – po zmniejszeniu rozmiaru macierzy wciąż chcemy posiadać z wierszy i kolumn zapasu.
Lazarus
// Zwiększanie rozmiaru macierzy
// A - macierz
// m - liczba wierszy
// n - liczba kolumn
// z - zapas
//------------------------------
procedure inc_matrix(var A : mptr; m,n,z : integer);
var
  i : integer;
begin
  if (m > Length(A)) or (n > Length(A[0])) then
  begin
    SetLength(A,m+z);
    for i := 0 to m+z-1 do SetLength(A[i],n+z);
  end;
end;

// Zmniejszanie rozmiaru macierzy
// A - macierz
// m - liczba wierszy
// n - liczba kolumn
// z - zapas
//-------------------------------
procedure dec_matrix(var A : mptr; m,n,z : integer);
var
  i : integer;
begin
  if (m <= Length(A)-z-z) or (n <= Length(A[0])-z-z) then
  begin
    SetLength(A,m+z);
    for i := 0 to m+z-1 do SetLength(A[i],n+z);
  end;
end;
Code::Blocks
// Zwiększanie rozmiaru macierzy
// A - macierz
// m - liczba wierszy
// n - liczba kolumn
// z - zapas
// mm- maksymalna liczba wierszy
// nn- maksymalna liczba kolumn
//------------------------------
void inc_matrix(dane ** & A, int m, int n, int z, int & mm, int & nn)
{
  int i,j;
  dane ** T;

  if((m > mm) || (n > nn))
  {
    T = new dane * [m+z];
    for(i = 0; i < m+z; i++)
    {
      T[i] = new dane [n+z];
      if(i < mm)
      {
        for(j = 0; j < nn; j++) T[i][j] = A[i][j];
        delete [] A[i];
      }
    }
    delete [] A;
    mm = m + z;
    nn = n + z;
    A = T;
  }
}

// Zmniejszanie rozmiaru macierzy
// A - macierz
// m - liczba wierszy
// n - liczba kolumn
// z - zapas
// mm- maksymalna liczba wierszy
// nn- maksymalna liczba kolumn
//------------------------------
void dec_matrix(dane ** & A, int m, int n, int z, int & mm, int & nn)
{
  int i,j;
  dane ** T;

  if((m <= mm-z-z) || (n <= nn-z-z))
  {
    T = new dane * [m+z];
    for(i = 0; i < mm; i++)
    {
      if(i < m+z)
      {
        T[i] = new dane [n+z];
        for(j = 0; j < n+z; j++) T[i][j] = A[i][j];
      }
      delete [] A[i];
    }
    delete [] A;
    mm = m + z;
    nn = n + z;
    A = T;
  }
}
Free Basic
' Zwiększanie rozmiaru macierzy
' A - macierz
' m - liczba wierszy
' n - liczba kolumn
' z - zapas
' mm- maksymalna liczba wierszy
' nn- maksymalna liczba kolumn
'------------------------------
Sub inc_matrix(ByRef A As dane Ptr Ptr, m As Integer, n As Integer, z As Integer,_
               ByRef mm As Integer, ByRef nn As Integer)
  Dim As Integer i,j
  Dim As dane Ptr Ptr T

  If (m > mm) OrElse (n > nn) Then
    T = New dane Ptr [m+z]
    For i = 0 To m+z-1
      T[i] = New dane [n+z]
      If i < mm Then
        For j = 0 To nn-1: T[i][j] = A[i][j]: Next
        Delete [] A[i]
      End If
    Next
    Delete [] A
    mm = m + z
    nn = n + z
    A = T
  End If
End Sub

' Zmniejszanie rozmiaru macierzy
' A - macierz
' m - liczba wierszy
' n - liczba kolumn
' z - zapas
' mm- maksymalna liczba wierszy
' nn- maksymalna liczba kolumn
'------------------------------
Sub dec_matrix(ByRef A As dane Ptr Ptr, m As Integer, n As Integer, z As Integer,_
               ByRef mm As Integer, ByRef nn As Integer)
  Dim As Integer i,j
  Dim As dane Ptr Ptr T

  If (m <= mm-z-z) OrElse (n <= nn-z-z) Then
    T = New dane Ptr [m+z]
    For i = 0 To mm - 1
      If i < m + z Then
        T[i] = New dane [n+z]
        For j = 0 To n+z-1: T[i][j] = A[i][j]: Next
      End If
      Delete [] A[i]
    Next
    Delete [] A
    mm = m + z
    nn = n + z
    A = T
  End If
End Sub

 

Odczyt macierzy ze standardowego wejścia

Przy odczycie macierzy będziemy stosowali następujący format danych wejściowych:

Dla macierzy kwadratowej pierwsza liczba określa jej rozmiar n. Następne n2 liczb określa elementy macierzy podawane kolejnymi wierszami. Na przykład:

Macierz:
  3 6 3  
  1 7 2  
  3 3 1  
Dane:

3
3 6 3
1 7 2
3 3 1

 

Dla macierzy prostokątnej pierwsze dwie liczby określają kolejno m – liczbę wierszy i n – liczbę kolumn macierzy. Następne m × n liczb określa m kolejnych wierszy po n elementów w każdym. Na przykład:

Macierz:
  3 6 3  
  1 7 2  
  4 2 0  
  3 3 1  
Dane:

4 3
3 6 3
1 7 2
4 2 0
3 3 1

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje dane dla macierzy ze standardowego wejścia, tworzy dynamicznie macierz, wprowadza do niej odczytane liczby i wyświetla jej zawartość.

 

Lazarus
// Odczyt macierzy
// Data: 21.12.2009
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program matrix;

type
  NInt = array of integer;
  MInt = array of NInt;
var
  A : MInt;
  n,m,iw,ik : integer;

begin
 
  // odczytujemy rozmiar macierzy

  read(m,n);

  // tworzymy tablicę wskaźników

  SetLength(A,m);

  // tworzymy tablice wierszy

  for iw := 0 to m - 1 do SetLength(A[iw],n);

  // odczytujemy elementy macierzy

  for iw := 0 to m - 1 do
    for ik := 0 to n - 1 do read(A[iw][ik]);
  writeln;

  // wyświetlamy macierz

  for iw := 0 to m - 1 do
  begin
    for ik := 0 to n - 1 do write(A[iw][ik]:4);
    writeln;
  end;

  // usuwamy macierz z pamięci

  for iw := 0 to m - 1 do SetLength(A[iw],0);

  SetLength(A,0);

end.
Code::Blocks
// Odczyt macierzy
// Data: 21.12.2009
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int ** A,n,m,iw,ik;

  // odczytujemy rozmiar macierzy

  cin >> m >> n;

  // tworzymy tablicę wskaźników

  A = new int * [m];

  // tworzymy tablice wierszy

  for(iw = 0; iw < m; iw++) A[iw] = new int[n];

  // odczytujemy elementy macierzy

  for(iw = 0; iw < m; iw++)
    for(ik = 0; ik < n; ik++) cin >> A[iw][ik];
  cout << endl;
  
  // wyświetlamy macierz
  
  for(iw = 0; iw < m; iw++)
  {
    for(ik = 0; ik < n; ik++) cout << setw(4) << A[iw][ik];
    cout << endl;
  }

  // usuwamy macierz z pamięci

  for(iw = 0; iw < m; iw++) delete [] A[iw];

  delete [] A;

  return 0;
}
Free Basic
' Odczyt macierzy
' Data: 21.12.2009
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim A As Integer Ptr Ptr
Dim As Integer n,m,iw,ik
 
Open Cons For Input As #1

' odczytujemy rozmiar macierzy

Input #1,m,n

' tworzymy macierz

A = New Integer Ptr [m]

For iw = 0 To m - 1
  A[iw] = New Integer [n]
Next

' odczytujemy elementy macierzy

For iw = 0 To m - 1
  For ik = 0 To n - 1
    Input #1,A[iw][ik]
  Next
Next
Print

Close #1

' wyświetlamy macierz

For iw = 0 To m - 1
  For ik = 0 To n - 1
    Print Using "####";A[iw][ik];
  Next
  Print
Next

' usuwamy macierz z pamięci

For iw = 0 To m - 1
  Delete [] A[iw]
Next

Delete [] A

End
Wynik
4 3
3 6 3
1 7 2
4 2 0
3 3 1

   3   6   3
   1   7   2
   4   2   0
   3   3   1

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.