Mehrdimensionale Reihungen in C

Eindimensionale Reihungen

Beispiel zur Definition einer Reihung »a« ohne Initialisierer

int a[ 3 ];

Beispiel zur Definition einer Reihung »a« mit Initialisierer

int a[ 3 ]={ 0, 1, 2 };

Beispiel zur Definition eines Zeigers auf eine Reihung mit Laufzeitgröße

int *a = malloc( 3 * sizeof *a );

Eine eindimensionale Reihung R ist eine (endliche) Folge von n Objekt gleichen Typs, die im Speicher aufeinander folgen.

Falls 0 ≤ i < n, bezeichnet der Ausdruck R [i ] die Komponente i der Reihung R.

/ Präsenzübung Lesen einer Reihung aus einer Datei: Lesen Sie die drei Werte einer Reihung mit drei Komponenten vom Typ »double« aus »stdin« und schreiben Sie das Produkt dieser Reihung mit der Zahl 2 nach »stdout«.
/ Präsenzübung Lesen einer Reihung mit dynamischer Größe aus einer Datei: Lesen Sie die Werte einer Reihung mit Komponenten vom Typ »double« aus »stdin« und schreiben Sie das Produkt dieser Reihung mit der Zahl 2.0 nach »stdout«.; Um Unterschied zur vorherigen Aufgabe ist diesmal die Anzahl der Werte erst zur Laufzeit bekannt und wird als erster Wert (ganzzahlig) eingelesen. Die Eingabe »5 2.0 2.0 2.0 2.0 2.0« steht beispielsweise für eine Reihung mit 5 Werten, die alle 2.0 sind.

Nachtrag: Ausrichtung

Bestimmte Objekte können nur an bestimmten Adressen stehen (etwa an geradzahligen Adressen). Normalerweise wird dies von C automatisch gewährleistet, kann aber vom Programmierer außer Kraft gesetzt werden. Deswegen ist es nicht gewährleistet, daß das folgende Programm immer »3.14« ausgeben wird.

Erzeugen eines möglicherweise falsch ausgerichteten Zeigers

#include <stdio.h> /* printf */
#include <stdlib.h> /* EXIT_SUCCESS */

int main( void )
{ double a[ 2 ];
  double * p =( double * )(( char * )a + 1 );
  *p = 3.14; printf( "%g\n", *p );
  return EXIT_SUCCESS; }

Speicher, der von »malloc« erhalten wurde, ist jedoch für jeden denkbaren Objekttyp immer richtig ausgerichtet (also beispielsweise immer bei einer durch 64 teilbaren Adresse). Genauso wird beim automatischen oder statischen Anlegen eines Objektes natürlich schon von C sichergestellt, daß dieses richtig ausgerichtet ist.

Zweidimensionalität durch Verschachtelung

Zweidimensionale Reihungen lassen sich auch durch eine „Reihung von Reihungen gleicher Größe“ darstellen. Diese muß aber durch eine „Reihung von Zeigern auf Reihungen gleicher Größe“ realisiert werden muß, da Reihungen nicht direkt in anderen Reihungen enthalten sein können (insofern sind Reihung als Objekte etwas unterprivilegiert).

Eine Reihung »a« von Zeigern auf Reihungen »a0« und »a1«

#include <stdio.h>
#include <stdlib.h>

int const a0[ 4 ]={ 1, 2, 3, 4 };
int const a1[ 4 ]={ 4, 5, 6, 7 };

int const( * const a[ 2 ])[ 4 ]={ &a0, &a1 };

int main( void )
{ int row; for( row = 0; row < 2; ++row )
  { int col; for( col = 0; col < 4; ++col )
    printf( "%d ",( *a[ row ])[ col ]);
    printf( "\n" ); }
  return EXIT_SUCCESS; }

stdout

1 2 3 4
4 5 6 7

Situation nach den Initialisierungen

a
.---.      a0
|   |    .-----------------.  
|   |    |.---.---.---.---.|
| o----->|| 1 | 2 | 3 | 4 ||
|   |    |'---'---'---'---'|
|   |    '-----------------'
|---|      a1
|   |    .-----------------.
|   |    |.---.---.---.---.|
| o----->|| 4 | 5 | 6 | 7 ||
|   |    |'---'---'---'---'|
|   |    '-----------------'
'---'

Heterogene Darstellung

Das voranstehende Beispiel läßt sich meist vereinfachen, indem man in der Reihung der Zeilen Zeiger auf »int« speichert (anstatt Zeiger auf Reihungen). Nur enthält der Typ dann nicht mehr die Anzahl der Spalte (=4). Hier könnten die einzelnen Zeilen also auch unterschiedliche Längen haben, die Reihung ist also insofern „heterogen“.

Eine Reihung »a« von Zeigern auf Reihungen int-Objekte »1, 2, 3, …« und »4, 5, 6, …«

#include <stdio.h>
#include <stdlib.h>

int const a0[ 4 ]={ 1, 2, 3, 4 };
int const a1[ 4 ]={ 4, 5, 6, 7 };

int const * const a[ 2 ]={ a0, a1 };

int main( void )
{ int row; for( row = 0; row < 2; ++row )
  { int col; for( col = 0; col < 4; ++col )
    printf( "%d ", a[ row ][ col ]);
    printf( "\n" ); }
  return EXIT_SUCCESS; }

stdout

1 2 3 4
4 5 6 7

Situation nach den Initialisierungen

a
.---.     
|   |     a0
|   |    .---.---.---.---.
| o----->| 1 | 2 | 3 | 4 |
|   |    '---'---'---'---'
|   |
|---|     
|   |     a1
|   |    .---.---.---.---.
| o----->| 4 | 5 | 6 | 7 |
|   |    '---'---'---'---'
|   |
'---'

Falls eines der Beispielprogramme abgeändert werden soll, kann es natürlich nötig werden, einige Verwendungen des Typqualifizierers »const« zu entfernen, falls in der abgeänderten Version ein Bezeichner für einen Schreibzugriff verwendet werden soll.s

Die bishergezeigten Vorgehensweisen sind hinsichtlich der Initialisierung etwas komplizierter als bei statischen Reihungen nötig. Sie dienen der Vorbereitung des Verständnisses des dynamischen Aufbaus von Reihungen.

Zeigerarithmetik

Manchmal hält man es für effizienter, in der Schleife Zeigerarithmetik einzusetzen, aber bei modernen Compilern muß dies nicht unbedingt vorteilhaft sein.

Zeigerarithmetik statt Indizierung

#include <stdio.h>
#include <stdlib.h>

int const a0[ 4 ]={ 1, 2, 3, 4 };
int const a1[ 4 ]={ 4, 5, 6, 7 };

int const * const a[ 2 ]={ a0, a1 };

int main( void )
{ int const * const *row; for( row = a; row < a + 2; ++row )
  { int const *comp; for( comp = *row; comp < *row + 4; ++comp )
    printf( "%d ", *comp );
    printf( "\n" ); }
  return EXIT_SUCCESS; }

stdout

1 2 3 4
4 5 6 7

Definition zweidimensionaler Reihungen

C unterstützt das Definieren einer Reihung mit mehreren Indizes und verschachtelten Initialisierern, die dann wie in den beiden vorangegangenen Beispielen verwendet werden kann.

Der Typ dieser Reihung enthält eine Information über die Breite einer Zeile (=Anzahl der Spalten), so daß Indexumrechnungen, wie oben dargestellt, ermöglicht werden.

Eine Reihungsdefinition mit mehreren Dimensionen und entsprechender Initialisierung

#include <stdio.h>
#include <stdlib.h>

#define ROWS 2
#define COLS 4

int a[ ROWS ][ COLS ]=
{ { 1, 2, 3, 4 }, 
  { 4, 5, 6, 7 }};

int main( void )
{ int row; for( row = 0; row < ROWS; ++row )
  { int col; for( col = 0; col < COLS; ++col )
    printf( "%d ", a[ row ][ col ]);
    printf( "\n" ); }
  return EXIT_SUCCESS; }

stdout

1 2 3 4
4 5 6 7

Situation nach den Initialisierungen

      a
     .---.---.---.---.
a[0] | 1 | 2 | 3 | 4 |
     .---.---.---.---.
a[1] | 4 | 5 | 6 | 7 |
     '---'---'---'---'

Wahl der Bezeichner Die Bezeichner »row« und »col« wurden extra so gewählt, daß sie gleichviel Zeichen haben. Die Bezeichner »ROWS« und »COLS« ergeben sich in systematischer Weise aus ihnen. Dadurch sehen richtige Vergleiche, wie »col < COLS« auch „richtiger“ aus als „(meist) falsche Vergleiche“ wie »col < ROWS«.

Schreibweise der Schleife Falls eine Reihung mit der Größe »SIZE« definiert wurde, dann ist die Schreibweise »for( i = 0; i < SIZE; …« beliebt, weil sie ein wiedererkennbares Muster darstellt, über das nicht mehr nachgedacht werden muß, wenn man es einmal auswendig gelernt hat. Die Schreibweise mit einem anderen Vergleichsoperator würde eine zusätzlich Subtraktion nötig machen »for( i = 0; i <= SIZE - 1; …«

Schönheit von Quelltext Es wird von vielen Programmierern als „schön“ empfunden, wenn richtige Ausdrücke im Quelltext auch bei oberflächlicher Betrachtung richtig und kurz aussehen. Oft werden Bezeichner und Schreibweise so gewählt, daß sich dies so ergibt.

/ Lebensdauer: Welche Lebensdauer hat das Objekt a?
o statisch
o automatisch
o alloziert

Beispiel mit gelegentlich vorkommendem Flüchtigkeitsfehler

#include <stdio.h>

int a[ 2 ][ 4 ]={{ 1, 2, 3, 4 },{ 4, 5, 6, 7 }};

int main( void ){ printf( "%d\n", a[ 2, 4 ]); }

Bei einer zweidimensionalen Objektdefinition wird auch ohne Initialisierung Speicher für eine zweidimensionale Matrix reserviert.

Bereitstellung von 8 Byte

char a[ 2 ][ 4 ];

Wird eine Reihung von Zeigern definiert (wie weiter oben), so wird auch nur Speicher für diese Reihung bereitgestellt (nicht für die von den Zeigern eventuell referenzierten Objekte).

Bereitstellung von 2 Zeigern

char * a[ 2 ];

Indexumrechnungen

Eine Alternative zu zweidimensionalen Reihungen als „verschachtelte“ eindimensionale Reihungen wären Indexumrechnungen wie im folgenden Beispiel. Jedoch entspricht die von C verwendete Zeigerarithmetik effektiv gerade diesen Umrechnungen.

Da die Größe einer Reihung beim Übersetzen bekannt sein muß (anders als in C99 ) muß manchmal der Präprozessor verwendet werden, wenn Namen vergeben werden sollen.

Eine Reihung mit Indexumrechnung

#include <stdio.h>
#include <stdlib.h>

#define ROWSIZE 4

int a[ 2 * ROWSIZE ]={ 1, 2, 3, 4, 4, 5, 6, 7 };

int main( void )
{ int row; for( row = 0; row < 2; ++row )
  { int col; for( col = 0; col < ROWSIZE; ++col )
    printf( "%d ", a[ ROWSIZE * row + col ]);
    printf( "\n" ); }
  return EXIT_SUCCESS; }

stdout

1 2 3 4
4 5 6 7

Zweidimensionale Reihungen als Argumente

Die bei zweidimensionalen Reihungen nötigen Umrechnungen kann C nur erledigen, wenn es die Zeilenbreite (=Anzahl der Spalten) einer zweidimensionalen Reihung auch kennt. Daher muß diese bei zweidimensionalen Reihungen angegeben werden, wenn sie Funktionsparameter sein soll. Die Anzahl der Zeilen wird für die Umrechnung nicht benötigt und kann daher in diesem Fall entfallen.

Übergabe einer Reihung als Argument

#include <stdio.h>
#include <stdlib.h>

void print( int const a[][ 4 ])
{ int row; for( row = 0; row < 2; ++row )
  { int col; for( col = 0; col < 4; ++col )
    printf( "%d ", a[ row ][ col ]);
    printf( "\n" ); }}

int main( void )
{ int const a[ 2 ][ 4 ]=
  { { 1, 2, 3, 4 }, 
    { 4, 5, 6, 7 }};
  print( a );
  return EXIT_SUCCESS; }

stdout

1 2 3 4
4 5 6 7

Kompliziertere Typdefinitionen lassen sich immer von innen nach außen (und dann von rechts nach links) lesen: „In der Funktion »print« ist der Parameter »a« eine Reihung von Reihungen mit 4 konstanten int-Werten“.

/ Lebensdauer: Welche Lebensdauer hat das Objekt a?
o statisch
o automatisch
o alloziert

Die Angabe der Zeilenanzahl ist bei der Parameterdeklaration möglich »void print( int const a[ 2 ][ 4 ])« wird aber ignoriert.

/ Präsenzübung Verarbeitung von Matrizen mit Dateien: Lesen Sie die neun Werte einer 3×3-Matrix mit Komponenten vom Typ »double«.; Geben Sie das Produkt dieser Matrix mit der Zahl 2 aus.

Allokation von Reihungen

Die in C eingebaute Umrechnung von Indizes für zweidimensionale Reihungen setzt voraus, daß deren Zeilenbreite bei der Übersetzung bekannt ist. Wenn dies nicht zutrifft, bietet C keine solche Unterstützung mehr. Daher hört man manchmal auch – nicht ganz richtig –, daß C keine zweidimensionalen Reihungen kennte. (C99 bietet allerdings Unterstützung für zweidimensionale Reihungen auch mit erst zur Laufzeit bekannten Dimensionen und automatischer Lebensdauer, die sogenannten „VLAs “.)

In diesem Fall muß der Programmierer dann wieder auf das Verfahren der Darstellung einer Reihung durch eine Reihung von Zeilenreihungen zurückgreifen. Im folgenden Beispiel wird gleich Speicher für alle Matrixkomponenten auf einmal angefordert, weil dies die Ressourcenbehandlung vereinfacht.

Beispiel mit dynamischer Allokation

#include <stdio.h>  /* printf */
#include <stdlib.h> /* malloc, free, EXIT_SUCCESS */

int main( void )
{ int rows = 2;
  int width = 4;
  double * buff = malloc( rows * width * sizeof * buff );
  double ** row = malloc( rows * sizeof buff );
  int c; int r;

  if( !buff || !row )abort(); 

  for( r = 0; r < rows; ++r )row[ r ]=( buff + r * width * sizeof * buff );

  row[ 0 ][ 0 ]= 1; row[ 0 ][ 1 ]= 2; row[ 0 ][ 2 ]= 3; row[ 0 ][ 3 ]= 4;
  row[ 1 ][ 0 ]= 4; row[ 1 ][ 1 ]= 5; row[ 1 ][ 2 ]= 6; row[ 1 ][ 3 ]= 7;

  for( r = 0; r < rows; ++r )
  { for( c = 0; c < width; ++c )printf( "%3.0f ", row[ r ][ c ]);
    printf( "\n" ); }

  return EXIT_SUCCESS; }

stdout

  1   2   3   4
  4   5   6   7

/ Lebensdauer

Welche Lebensdauer hat das Objekt row?
o statisch
o automatisch
o alloziert

Es ist nicht immer richtig, das Program bei einem Scheitern sofort abzubrechen, aber in manchen Fällen möglich; das hängt von der Aufgabenstellung ab (den Anforderungen an eine Programm). (Es wäre im Falle von Funktionen, die in verschiedenen Programmierprojekten verwendet werden können sollen im allgemeinen nicht richtig.) Normalerweise muß der mit »malloc« angeforderte Speicher auch wieder mit »free« freigegeben werden. Aber im Falle des obigen Programms würde dies direkt vor »abort()« oder »return« erfolgen und ist in diesem Fall nicht nötig, weil der gesamte vom Prozeß allozierte Speicher beim Beenden des Prozesses ohnehin freigegeben wird. Dies wird von der C -Spezifikation allerdings nicht garantiert, ist aber eine Eigenschaft der meisten Betriebssysteme.

/ Präsenzübung Verarbeitung von Matrizen dynamischer Größe mit Dateien: Lesen Sie die Werte einer Matrix mit Komponenten vom Typ »double« ein und geben Sie das Doppelte dieser Matrix aus.; Die ersten beiden ganzzahligen Werte geben die Anzahl der Zeilen und der Spalten an.
/ Übung Verarbeitung von Matrizen dynamischer Größe mit Dateien (schwieriger): Lesen Sie die Werte zweier Matrizen mit Komponenten vom Typ »double« aus der Datei »dat.mat« und der Datei »dat1.mat« und schreiben Sie das Produkt dieser beiden Matrizen (insofern es für diese Matrizen definiert ist) in die Datei »result.mat«.; Diesmal wird die Größe der Matrizen aber nicht am Anfang der Dateien angegeben. Deswegen muß jede Datei zweimal gelesen werden: Beim ersten Mal, um die Dimensionen der Matrizen zu ermitteln, beim zweiten Mal, um die Werte einzulesen. (Falls das zu schwierig ist, dann können Sie die Dimensionen doch weiterhin am Anfang der Datei angeben.); Hinweis Zur Vereinfachung kann zunächst vorübergehend auch erst einmal auf eine sorgfältige Behandlung von Fehlern und Ressourcen verzichtet werden, die dann aber nachgeholt werden sollte, wenn das Programm unter günstigen Umständen (also bei korrekten Eingaben) arbeitet.; Hinweis Versuchen Sie für sich wiederholende Aufgaben, jeweils Funktionen zu definieren, die Sie dann wiederverwenden.; Hinweis Testen Sie das Programm nicht monolithisch (als ganzes) sondern modular (in Einzelteilen). Testen Sie also die Programmteile zum Einlesen einer Matrix, zum Multiplizieren zweier Matrizen und zum Ausgeben einer Matrix jeweils einzeln, bevor Sie ihr Programm als Ganzes testen.; Hinweis Testen Sie das Programm schließlich auch unter ungünstigen Umständen: Wie verhält es sich, wenn die Eingabedateien fehlen oder wenn die Matrizen nicht multipliziert werden können oder eine Eingabedatei keine richtige Matrix enthält? Ein Programm höchster Qualität würde alle diese Probleme erkennen und korrekt melden, aber es ist nicht sicher, ob sich der dafür nötige Aufwand immer lohnt.