Mehrdimensionale C++ Arrays

Dieser Unterpunkt baut auf dem Thema C++ Arrays, Zeiger und Referenzen der vorigen Vorlesung auf und betrachtet mehrdimensionale C++ Arrays. Mehrdimensionale C++ Arrays werden im Prinzip als ein Array von Arrays dargestellt und sie beschreiben einen Matrix-ähnlichen integrierten Datentyp. Für einen Typ T entspricht "T Name[m][n];" der Deklaration einer $(m \times n)$-Matrix, wobei die einzelnen Elemente vom gleichen Typ T sein müssen. Möchten wir z.B. eine $(m \times n)$-Matrix ${\bf \cal A}$, bestehend aus Gleitkommazahlen vom Typ double in einem C++ Programm als ein integriertes Array deklarieren, so würden wir die folgende Anweisung in den Quelltext schreiben: double A[m][n]; \[ \begin{equation} {\bf \cal A} =\left( \begin{array}{cccc} a_{11} & a_{12} & ... & a_{1n}\\ a_{21}& a_{22}& ...&a_{2n} \\ ...& ...& ...& ...\\ a_{m1}& a_{m2}& ...& a_{mn}\\ \end{array} \right) = (a_{ij})_{i=1,2,...,m \, ; \, j=1,2,...,n} \quad \Longrightarrow \quad \hbox{Deklaration z.B. mit: double A[m][n];} \end{equation} \] Im Folgenden werden wir zunächst auf

Mehrdimensionale C++ Arrays und Zeiger

In gleicher Weise wie auch bei eindimensionalen Arrays sind mehrdimensionale C++ Arrays mittels des Konstruktes des Zeigers implementiert. Die einzelnen Elemente eines Arrays (z.B. "double A[m][n]") sind in Form von Zeigern auf die eindimensionalen Zeilen-Unterarrays geordnet. Der Zugriff auf den Wert eines Array-Elementes kann entweder durch die Angabe des entsprechenden Matrix-Indexes erfolgen (A[i][j]), oder durch den dereferenzierten Wert seiner Zeigerposition im Array erfolgen ( *(A[i] + j) bzw. *(zeiger_A + i*n + j) ). Dies Eigenschaften von mehrdimensionale C++ Arrays wollen wir nun, am Beispiel von int-Arrays näher betrachten.

In dem folgenden C++ Programm werden zwei int-Arrays definiert, die den folgenden zwei Matrizen ${\bf \cal A}$ und ${\bf \cal B}$ entsprechen: \[ \begin{equation} \hbox{$(3 \times 5)$-Matrix} \quad {\bf \cal A} =\left( \begin{array}{ccccc} 1 & 2 & 3 & 4& 5\\ 21 & 22 & 23 & 24 & 25 \\ 51 & 52 & 53 & 54 & 55\\ \end{array} \right) \quad , \qquad \hbox{$(5 \times 3)$-Matrix} \quad {\bf \cal B} =\left( \begin{array}{ccc} 1 & 2 & 3\\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \\ 13 & 14 & 15 \\ \end{array} \right) \end{equation} \]

Array_mehrdim_zeiger.cpp
/** Definition von integrierten mehrdimensionalen C++ Arrays 
 * (m x n)-Matrix: Eine Matrix mit m Zeilen und n Spalten
 * hier speziell eine (3 x 5)-Matrix A und eine (5 x 3)-Matrix B 
 **/
#include <iostream>                     // Ein- und Ausgabebibliothek

int main(){                             // Hauptfunktion
    const int m = 3;
    const int n = 5;
    int A[m][n] = { { 1, 2, 3, 4, 5},
                    {21,22,23,24,25},
                    {51,52,53,54,55} }; // Definition eines (3x5)-Integer-Arrays ((3x5)-Matrix)
    int B[n][m] = { { 1, 2, 3},
                    { 4, 5, 6},
                    { 7, 8, 9},
                    {10,11,12},
                    {13,14,15} };       // Definition eines (5x3)-Integer-Arrays ((5x3)-Matrix)
                    
    int* zeiger_A = &A[0][0];           // Definition des Zeigers auf das Integer-Array A 
    
    constexpr int anz_elem_A = sizeof(A)/sizeof(A[0][0]); // Gesamte Anzahl der Elemente im Array A
    constexpr int dim_m = sizeof(A)/sizeof(A[0]);         // Dimension m des Arrays (Anzahl der Zeilen der Matrix A)
    constexpr int dim_n = sizeof(A[0])/sizeof(A[0][0]);   // Dimension n des Arrays (Anzahl der Spalten der Matrix A)
    
    printf("Matrix A: \n");
    for(int i=0; i < m; ++i){        // Anfang Schleife 1 (Zeilen der Matrix) 
        printf("| ");
        for(int j=0; j < n; ++j){    // Anfang Schleife 2 (Spalten der Matrix) 
            printf("%3i ", A[i][j]); // Ausgabe des Matrixwertes A_{ij}
        }                            // Ende der 1.Schleife 
        printf("| \n");
    }                                // Ende der 1.Schleife 
    
    printf("\nMatrix B: \n");
    for(int i=0; i < n; ++i){        // Anfang Schleife 1 (Zeilen der Matrix) 
        printf("| ");
        for(int j=0; j < m; ++j){    // Anfang Schleife 2 (Spalten der Matrix) 
            printf("%3i ", B[i][j]); // Ausgabe des Matrixwertes B_{ij}
        }                            // Ende der 1.Schleife 
        printf("| \n");
    }                                // Ende der 1.Schleife 
    
    printf("\nDie Adresse des mehrdimensionalen Arrays A entspricht der Referenz seines ersten Elementes:\n");
    printf("&A[0][0] = %p , A[0] = %p und zeiger_A = %p\n\n", &A[0][0], A[0], zeiger_A);
    printf("Der Ausdruck A[i] ist der Zeiger auf die i-te Zeile der Matrix A:\nA[0] = %p , A[1] = %p und A[2] = %p \n\n", A[0], A[1], A[2]);
    printf("Die gesamte Anzahl der Elemente im Array A ist %i \n\n", anz_elem_A);
    printf("Das Array A entspricht einer (m x n)-Matrix mit m = %i und n = %i \n\n", dim_m, dim_n);
    
    printf("Navigieren in Arrays:\n");
    printf("Der Zugriff auf ein Element des Arrays kann entweder ... \n");
    printf("... durch die Angabe des Matrix-Indexes erfolgen A[i][j]: z.B. A[2][3] = %i \n", A[2][3]);
    printf("... oder durch den dereferenzierten Wert seiner Zeigerposition im Array erfolgen *(A[i] + j): z.B. *(A[2] + 3) = %i \n", *(A[2] + 3));
    printf("    dies ist gleichbedeutend mit *(zeiger_A + i*n + j): z.B. *(zeiger_A + 2*5 + 3) = %i \n\n", *(zeiger_A + 2*5 + 3));
}

Die Werte der Arrays werden direkt bei ihrer Deklaration initialisiert. Zusätzlich wird der Zeiger auf das Array "A" mittels der Referenz seines ersten Elementes definiert (int* zeiger_A = &A[0][0];). Ähnlich wie bei eindimensionalen Arrays kann man mittels des sizeof(...) Befehls die gesamte Anzahl der Elemente im Array und die Dimensionen des Arrays bestimmen. Mittels zweier geschachtelter for-Schleifen werden dann die Matrizen im Terminal ausgegeben. Die Ausgabe der einzelnen Matrixwerte wird hierbei mittels der Anweisung "printf("%3i ", A[i][j]);" gemacht. Man hätte die Werte "A[i][j]" auch auf Basis des Zeigerkonstruktes wie folgt formulieren können: *(A[i] + j)); bzw. *(zeiger_A + i*n + j));
Da das Navigieren im Array auf Zeigerbasis zunächst ein wenig unübersichtlich erscheint, werden am Ende des Programms einige Adressen/Referenz- und Zeigereigenschaften von mehrdimensionalen C++ Arrays im Terminal ausgegeben. Die linke Abbildung veranschaulicht die gesamte Terminalausgabe des Programms.

Anwendung: Multiplikation zweier Matrizen

Wir möchten nun die beiden Matrizen ${\bf \cal A}$ und ${\bf \cal B}$ miteinander multiplizieren. Allgemein gilt für die Multiplikation einer $(m \times n)$-Matrix ${\bf \cal A}$ mit einer $(n \times l)$-Matrix ${\bf \cal B}$ die folgende Formel: ${\bf \cal C} = {\bf \cal A} \cdot {\bf \cal B}$ mit \[ \begin{equation} c_{ij} = \sum_{k=1}^n a_{ik} \, b_{kj} \quad \, , \quad i=1,2,...,m \, ; \, j=1,2,...,l \quad , \end{equation} \] wobei die entstehende Produktmatrix ${\bf \cal C}$ eine $(m \times l)$-Matrix ist. Für unsere speziellen Matrizen gilt \[ \begin{equation} {\bf \cal C} = {\bf \cal A} \cdot {\bf \cal B} = \underbrace{ \left( \begin{array}{ccccc} 1 & 2 & 3 & 4& 5\\ 21 & 22 & 23 & 24 & 25 \\ 51 & 52 & 53 & 54 & 55\\ \end{array} \right) }_{\hbox{$(3 \times 5)$-Matrix}} \cdot \underbrace{ \left( \begin{array}{ccc} 1 & 2 & 3\\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \\ 13 & 14 & 15 \\ \end{array} \right) }_{\hbox{$(5 \times 3)$-Matrix}} = \underbrace{ \left( \begin{array}{ccc} 135 & 150 & 165 \\ 835 & 950 & 1065 \\ 1885 & 2150 & 2415\\ \end{array} \right) }_{\hbox{$(3 \times 3)$-Matrix}} \quad . \end{equation} \]

Die Multiplikation der Matrizen ${\bf \cal A}$ und ${\bf \cal B}$ ist in dem folgenden C++ Programm mittels dreier geschachtelter for-Schleifen realisiert worden.

Array_mehrdim_mult.cpp
/** Matrix Multiplikation 
 * (m x l)-Matrix = (m x n)-Matrix * (n x l)-Matrix
 * Spezialfall
 * (m x m)-Matrix = (m x n)-Matrix * (n x m)-Matrix
 * C[m][m] = A[m][n] * B[n][m]
 * hier speziell eine (3 x 5)-Matrix A und eine (5 x 3)-Matrix B 
 **/
#include <iostream>                     // Ein- und Ausgabebibliothek

int main(){                             // Hauptfunktion
    const int m = 3;                    // Dimension der Zeilen der Matrix A
    const int n = 5;                    // Dimension der Spalten der Matrix A
    
    int A[m][n] = { { 1, 2, 3, 4, 5},
                    {21,22,23,24,25},
                    {51,52,53,54,55} }; // Definition eines (3x5)-Integer-Arrays, (3x5)-Matrix
                    
    int B[n][m] = { { 1, 2, 3},
                    { 4, 5, 6},
                    { 7, 8, 9},
                    {10,11,12},
                    {13,14,15} };       // Definition eines (5x3)-Integer-Arrays, (5x3)-Matrix
                    
    int C[m][m];                        // Deklaration eines (3x3)-Integer-Arrays, (3x3)-Matrix
    
    // Matrix Multiplikation C = A * B
    for(int i=0; i < m; ++i){                          // Anfang Schleife 1 (Zeilen der Matrix C) 
        for(int j=0; j < m; ++j){                      // Anfang Schleife 2 (Spalten der Matrix C)
            C[i][j] = 0;                               // Anfangs-Initialisierung von C_{ij}
            for(int k=0; k < n; ++k){                  // Anfang Schleife 3 (Summationsschleife) 
                C[i][j] = C[i][j] + A[i][k] * B[k][j]; // Matrix Multiplikation
            }                                          // Ende der 3.Schleife
        }                                              // Ende der 2.Schleife 
    }                                                  // Ende der 1.Schleife
    
    // Terminal Ausgabe der Matrix C
    printf("Die Matrix Multiplikation ergibt C = A * B : \n");
    for(int i=0; i < m; ++i){        // Anfang Schleife 1 (Zeilen der Matrix) 
        printf("| ");
        for(int j=0; j < m; ++j){    // Anfang Schleife 2 (Spalten der Matrix) 
            printf("%3i ", C[i][j]); // Ausgabe des Matrixwertes C_{ij}
        }                            // Ende der 2.Schleife 
        printf("| \n");
    }                                // Ende der 1.Schleife 
}

Die Implementierung der eigentlichen Multiplikation im Quelltext wurde mittels der Index-Schreibweise realisiert, da diese dem mathematischen Formalismus sehr ähnelt:
$ c_{ij} = \sum_{k=1}^n a_{ik} \, b_{kj} \quad \Longleftrightarrow \qquad $ for(int k=0; k < n; ++k){ C[i][j] = C[i][j] + A[i][k] * B[k][j]; }
Nach der Berechnung der einzelnen Elemente des Arrays wird die Produktmatrix ${\bf \cal C}$ schließlich im Terminal ausgegeben.

Mehrdimensionale C++ Arrays und Funktionen

Arrays lassen sich nicht direkt als Wert übergeben. Stattdessen kann man ein C++ Array als Zeiger auf sein erstes Element übergeben (mit einer zusätzlichen Angabe seiner Dimensionen). Im folgenden C++ Programm wurde eine void-Funktion dem Hauptprogramm ausgelagert, die zur Aufgabe hat eine $(m \times n)$-Matrix im Terminal auszugeben.

Array_mehrdim_funktion.cpp
/** Matrix Multiplikation mit ausgelagerter print-Funktion
 * (m x l)-Matrix = (m x n)-Matrix * (n x l)-Matrix
 * Spezialfall
 * (m x m)-Matrix = (m x n)-Matrix * (n x m)-Matrix
 * C[m][m] = A[m][n] * B[n][m]
 * hier speziell eine (3 x 5)-Matrix A und eine (5 x 3)-Matrix B 
 **/
#include <iostream>                        // Ein- und Ausgabebibliothek

//Ausgelagerte Funktion, Ausgabe der (m x n)-Matrix im Terminal
void print_Matrix(int* M, int dim_1, int dim_2){ // Anfang des Anweisungsblockes 
    for(int i=0; i < dim_1; ++i){                // Anfang Schleife 1 (Zeilen der Matrix) 
        printf("| ");
        for(int j=0; j < dim_2; ++j){            // Anfang Schleife 2 (Spalten der Matrix) 
            printf("%3i ", M[i*dim_2 +j]);       // Ausgabe des Matrixwertes M_{ij}
        }                                        // Ende der 2.Schleife 
        printf("| \n");
    }                                            // Ende der 1.Schleife 
}                                                // Ende der Funktion

int main(){                             // Hauptfunktion
    const int m = 3;                    // Dimension der Zeilen der Matrix A
    const int n = 5;                    // Dimension der Spalten der Matrix A
    
    int A[m][n] = { { 1, 2, 3, 4, 5},
                    {21,22,23,24,25},
                    {51,52,53,54,55} }; // Definition eines (3x5)-Integer-Arrays, (3x5)-Matrix
                    
    int B[n][m] = { { 1, 2, 3},
                    { 4, 5, 6},
                    { 7, 8, 9},
                    {10,11,12},
                    {13,14,15} };       // Definition eines (5x3)-Integer-Arrays, (5x3)-Matrix
                    
    int C[m][m];                        // Deklaration eines (3x3)-Integer-Arrays, (3x3)-Matrix
    
    // Matrix Multiplikation C = A * B
    for(int i=0; i < m; ++i){                          // Anfang Schleife 1 (Zeilen der Matrix C) 
        for(int j=0; j < m; ++j){                      // Anfang Schleife 2 (Spalten der Matrix C)
            C[i][j] = 0;                               // Anfangs-Initialisierung von C_{ij}
            for(int k=0; k < n; ++k){                  // Anfang Schleife 3 (Summationsschleife) 
                C[i][j] = C[i][j] + A[i][k] * B[k][j]; // Matrix Multiplikation
            }                                          // Ende der 3.Schleife
        }                                              // Ende der 2.Schleife 
    }                                                  // Ende der 1.Schleife
    
    printf("\nMatrix A: \n");
    print_Matrix(&A[0][0], m, n);                      // Aufruf der Funktion, Matrix A, (m x n)-Matrix
    
    printf("\nMatrix B: \n");
    print_Matrix(&B[0][0], n, m);                      // Aufruf der Funktion, Matrix B, (n x m)-Matrix
    
    printf("\nDie Matrix Multiplikation ergibt C = A * B : \n");
    print_Matrix(&C[0][0], m, m);                      // Aufruf der Funktion, Matrix C, (m x m)-Matrix
}

Die Funktion "void print_Matrix(int* M, int dim_1, int dim_2){ ... }" wird dann im Hauptprogramm dreimal aufgerufen, um die Matrizen ${\bf \cal A}$, ${\bf \cal B}$ und ${\bf \cal C}$ darzustellen. Man beachte hierbei, dass beim Aufruf der Funktion im Hauptprogramm (z.B. für die Matrix ${\bf \cal A}$: print_Matrix(&A[0][0], m, n);) die Adresse des ersten Elementes der Matrix übergeben wird (&A[0][0]) - man hätte hier auch '&A[0]' schreiben können, jedoch nicht '&A'. Das folgende Bild veranschaulicht die Terminalausgabe.

Die oben definierte Funktion hat jedoch mehrere Nachteile und wir werden später, im Themenbereich der Objekt-orientierten Programmierung sehen, dass man durch eine Kapselung des Programms eine Funktion entwerfen kann, die es dem Anwender erleichtert, die print_Matrix(..)-Funktion aufzurufen. Ein wichtiger Anwendungsbereich der Objekt-orientierten Programmierung besteht darin, C++-Klassen und Funktionen zu erstellen, die von anderen Programmierern verwendet werden können. Die Anwendung der geschriebenen Programme sollte dabei möglichst einfach und fehlerfrei sein. Die Anwendung unserer Funktion "void print_Matrix(int* M, int dim_1, int dim_2){ ... }" ist jedoch nicht so einfach und gerade bei der Angabe der Dimensionen des Arrays (int dim_1, int dim_2) kann der Anwender einen Fehler machen, der dann das Programm zum Absturz bringen könnte. Auch ist die print_Matrix Funktion auf ganzzahlige Matrizen beschränkt, was dem Anwender vielleicht nicht klar ist.

In dem folgenden C++ Programm sind die oben genannten Nachteile der print_Matrix Funktion behoben. Das Programm wurde von Herrn Johannes Misch erstellt und es verwendet, in einer eleganten Template-Funktion, zwei ineinander geschachtelte bereichsbasierte for-Schleifen. Beim Aufrufen der Funktion aus dem Hauptprogramm 'print_Matrix( A );' muss der Anwender lediglich das Array in die Argumentenliste der Funktion schreiben und abhängig vom Datentyp der Matrixelemente und der Dimension des Arrays verwendet die Template-Funktion den geeigneten Matrixtyp.

Array_mehrdim_funktion_template.cpp
/** Matrix Multiplikation mit ausgelagerter print-Funktion
 * (m x l)-Matrix = (m x n)-Matrix * (n x l)-Matrix
 * Spezialfall
 * (m x m)-Matrix = (m x n)-Matrix * (n x m)-Matrix
 * C[m][m] = A[m][n] * B[n][m]
 * hier speziell eine (3 x 5)-Matrix A und eine (5 x 3)-Matrix B 
 * Diese Version benutzt eine Template-Funktion und bereichbasierte for-Schleifen zur Terminalausgabe der Matrix
 * Diese Version des C++ Programm wurde von Johannes Misch erstellt ( misch@itp.uni-frankfurt.de )
 **/
#include <iostream>
#include <iomanip>

// Dies ist ein funktions-template. Eine Blaupause fuer funktionen die der Compiler verwendet um funktionen nach bedarf zu erstellen
// Die funktion akzeptiert ein array der form T arr[a][b];
// sie bestimmt sowohl den type 'T', als auch die groesse des arrays automatisch anhand ihres arguments
template <typename T, std::size_t a, std::size_t b>
void print_Matrix( const T (&M)[a][b] )
{
	// range-based for loops iterieren ueber alle elemente einer collection, in diesem fall ueber alle alle zeilen der matrix
	// const heisst dass wir die zeile nicht modifizieren
	// auto sagt dem compiler, dass er den typ automatisch anhand des initializers bestimmen soll
	// es ist eine reference, weil wir keine Kopie der zeile haben wollen, sondern nur lesen
    for ( const auto& row : M )
    {                
        std::cout << "| ";
        for ( const auto value : row ) // diesmal machen wir eine kopie, da dies fuer die meisten fundamentalen typen (wie z.b. int) besser ist
        {
            std::cout << std::setw(8); //wir setzen die breite der naechsten ausgabe auch mindestens 8 zeichen. Dadurch wird die matrix "schoen" dargestellt
            std::cout << value << ' ';
        }
        std::cout << "|\n";
    }
}

int main()
{
	
    constexpr int m = 3; // Dimension der Zeilen der Matrix A
    constexpr int n = 5; // Dimension der Spalten der Matrix A
	//constexpr bezeichnet eine compile-time konstante. Built-in arrays muessen eine compile-time konstante groesse haben.
    
    // Definition eines (3x5)-Integer-Arrays, (3x5)-Matrix
	// 'const' heisst das wir dieses array waehrend der restlichen laufzeit nicht mehr aendern werden
	// man sollte i.A. immer 'const' verwenden wenn man nicht vor hat die variable zu veraendern
    const int A[m][n] =  
    { 
        {  1,  2,  3,  4,  5 },
        { 21, 22, 23, 24, 25 },
        { 51, 52, 53, 54, 55 } 
    };

    // Definition eines (5x3)-Integer-Arrays, (5x3)-Matrix
    const int B[n][m] = 
    { 
        {  1,  2,  3 },
        {  4,  5,  6 },
        {  7,  8,  9 },
        { 10, 11, 12 },
        { 13, 14, 15 } 
    };

    // Definition eines (3x3)-Integer-Arrays, (3x3)-Matrix. Automatische initializierung mit 0
	// Dieses array is nicht 'const' da es das ergebnis enthalten wird
    int C[m][m] = {}; // eine leere initializer-list fuert dazu das alle werte im array mit 0 initialized werden
    
    // Matrix Multiplikation C = A * B
    for ( int i=0; i < m; ++i )
    {
        for ( int j=0; j < m; ++j )
        {
            for ( int k=0; k < n; ++k )
            {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    
    std::cout << "\nMatrix A: \n";
    print_Matrix( A ); // Dies ruft print_Matrix<int,3,5> auf. Der compiler bestimmt diese parameter automatisch anhand des types von 'A'

    std::cout << "\nMatrix A: \n";
    print_Matrix( B );
    
    std::cout << "\nDie Matrix Multiplikation ergibt C = A * B : \n";
    print_Matrix( C );
    
}