... übt

C

• Array von Pointern auf struct (Zugriff und Funktionsparameter)
  

• Pointer auf Array von Pointern auf struct (Zugriff und Funktionsparameter)
  

• Migration einer cmdline-Variante in eine GUI-Variante mit gtk
  

Die Nutzung von C scheint sich auf den ersten Blick nicht wesentlich von der anderer prozeduraler Sprachen zu unterscheiden. Interessant wird es, wenn es um das Handling von Arrays geht. Für mich interessant, weil ich Themen aus der Bildverarbeitung mit C bearbeiten will und hier Matrizen eine zentrale Rolle spielen. Auf ein Beispiel zur Übung für den Einsatz von Arrays stiess ich in einer Rätselzeitschrift, in der Matrizen mit Buchstaben dargestellt waren, die bestimmte Worte in Anordnungen horizontal, vertikal, diagonal und nach links oder rechts gelesen enthalten.

Beispiel

Die folgende Matrix (6 Spalten, 5 Zeilen) besteht pro Element aus einem Einzelbuchstaben:

Hier findet sich unter anderem in der 5. (letzten) Zeile ab der 1. Spalte das Wort "durst" von links nach rechts gelesen und in der 2. Zeile ab der 2. Spalte das Wort "weit" nach rechts unten gelesen.

Algorithmus

Vorgaben:
Die Eigenschaften eines Elementes der Matrix werden als Struktur (struct) abgebildet und die Zeiger auf die Strukturen in der Suchmatrix entsprechend der Ausgangsmatrix angeordnet. Die Attribute der Strukturelemente sind die x- und y-Koordinaten der Position, der Inhalt = Buchstabe an der Position und die Zeiger auf die 8 Nachbarn.
Bezogen auf ihre Position haben die Elemente verschiedene Anzahlen von Nachbarn:

• Eckelemente besitzen 3 Nachbarn
• Seitenelemente, die keine Eckelemente sind, besitzen 5 Nachbarn
• alle übrigen inneren Elemente besitzen 8 Nachbarn

Ablauf:

1. Suche den 1. Buchstaben des Suchwortes in der Suchmatrix.
2. Wenn der Buchstabe nicht gefunden wird, gibt es das Suchwort in der Matrix nicht.
3. Wenn der Buchstabe gefunden wird suche den 2. Buchstaben des Suchwortes bei den direkten Nachbarn des gefundenen 1. Buchstabens. Wird der 2. Buchstabe nicht gefunden, gibt es das Suchwort in der Matrix nicht.
4. Wenn der 2. Buchstabe gefunden wird, merke dir die relative Position des Nachbarn zum 1. Buchstaben (links, links oben, oben, rechts oben, rechts, rechts unten, unten und links unten) und suche die folgenden Buchstaben des Suchwortes in der entsprechenden Richtung.
5. Wird das Suchwort nicht bis zum letzten Zeichen in der Richtung gefunden, existiert es nicht in der Matrix ansonsten merke dir den erfolgreichen Fund.
6. Suche die Umgebung des 1. Buchstaben weiter ab, bis alle Nachbarn überprüft sind.
7. Danach führe das Verfahren mit dem nächsten Element der Matrix durch, bis alle Elemente der Matrix abgearbeit sind.

Umsetzung

• Deklaration der Struktur eines Elementes der Suchmatrix als "struct PuzzleItem". Das Strukturelement "frequenz" wird in dem hier umgesetzten Algorithmus nicht verwendet.

  struct PuzzleItem {
   int x,y; // Position in der Matrix
   char inhalt; // Buchstabe
   float frequenz; // Haeufigkeit des Auftretens
   struct PuzzleItem *lo,*o,*ro,*l,*r,*lu,*u,*ru; // Umliegende 8 Nachbarn
  } ;
  

• Puzzlematrix:

  struct PuzzleItem *puzzle[MAXY][MAXX];
  

• Belegung der Attribute Position (x, y) und Buchstabe (inhalt) der Elemente in der Suchmatrix über die Funktion "initPuzzle".
  
  Deklaration:

  void initPuzzle(struct PuzzleItem *item, int x, int y, char buchstabe, float rate);
  

  Aufruf:

  initPuzzle(puzzle[j][i], j, i, *(global_rmatrix+j*(global_px)+i), 0.0);
  

• Belegung der Nachbarschaftsattribute der Elemente in der Suchmatrix über die Funktion "initPuzzleEnv".
  
  Deklaration:

  void initPuzzleEnv(struct PuzzleItem *(*matrix)[MAXX], int x, int y);
  

  Aufruf:

  initPuzzleEnv(puzzle, global_px-1, global_py-1);
  

Einstieg in die Wortsuche über die Funktion "sucheWort". Die Unterfunktionen "umgebungssuche" und "richtungssuche_<Richtung>" übernehmen die eigentliche Suche.

Deklaration:

void sucheWort(struct PuzzleItem *(*matrix)[MAXX], const gchar *suchwort, int xdim, int ydim, char ergebnis[1024])

Aufruf:

sucheWort(puzzle, suchwort, global_px, global_py, fund)

Die aufgeführten Funktionen sind in die Funktionen der grafischen Oberfläche integriert:

• Callback "end": Beendet das Programm
  ... gtk_main_quit

• Callback "suchwort_enter_callback": holt sich das Suchwort, initialisiert die Suchmatrix, sucht und gibt das Ergebnis aus
  ... gtk_entry_get_text, show_warning, initPuzzle, initPuzzleEnv, sucheWort, show_info

• Callback "open_file": Öffnet die Datei mit einer Buchstabenmatrix, liest die Datei ein und stellt sie in der Textarea des Fensters dar
  ... gtk_file_chooser_dialog_new, readMatrix, showMatrix

Fazit

• Das modulare Programmieren mit Funktionen ist die beste Vorbereitung für die Migration in eine GUI-Variante.
• Die Handhabung von Arrays von Pointern wird bei Übergabe als Funktionsparameter über Verschachtelungstiefen immer schwieriger.
• Die maximale Größe eines Arrays muss zum Zeitpunkt der Deklaration bekannt sein.
• Die Weitergabe eines Pointers auf einen Speicherbereich von Elementen ist bei Funktionsübergabe leichter zu handhaben. Der Aufwand der Indexberechnung eines Elementes erscheint gering im Vergleich zur verminderten Komplexität.
• Das Speichermanagement ist beim Arbeiten mit Pointern aktiv zu steuern, Stichworte: malloc und free
• Eine große Hilfe beim Wiedereinstieg in diese C-Spezialitäten waren die Beiträge anderer User im Internet zu dem Thema. Vielen Dank dafür.

C-Code