Inhalt

1. Fingerübungen
2. Berechnung aller Untermengen (C Bitoperationen)
3. Funktionen (Rationale Zahlen, Referenzübergabe, Tests)
4. Count - Zählen von Wörtern inklusive Testrahmen (C Zeiger und Strings)
5. Strings - Speicherverwaltung
6. Speicherverwaltung und Pointer am Beispiel von Fibonacci (C)
7. Erweiterbarer Testrahmen (C++ virtuelle Methoden)
8. Reguläre Ausdrücke und Automaten
9. Playing with Templates and Lambdas (C++14)
10. Parser combinators

Fingerübungen

Im folgenden betrachten wir Beispiele von Programmen. Dazu gibt es Veständnissfragen und kleinere Programmieraufgaben.

Boolesche Bedingungen

Was ist der Sinn und Zweck folgendes Programmtextes. Könnte ein Fehler darin versteckt sein?

while(a[i] != '\0' && i >=0 && i < MAX) {
  i++;
}

• Die Intention ist die Suche nach dem Ende eines String, siehe a[i] != '\0'.

• Da es in C keine “array out of bounds check” gibt, wird versucht via i >=0 && i < MAX unerlaubte Zugriffe abzufangen.

Passt alles?

Nicht ganz. Die Reihenfolgen der einzelnen Bedingungen sind falsch. Aus der Mathematik kennt man dass && ein kommutativer Operator ist. Dies gilt hier nicht mehr.

Z.B. die Anweisung a[i] != '\0' kann zu einer Speicherverletzung führen weil der Index i sich ausserhalb der erlaubten Grenzen befindet. Die Bedingungen i >=0 && i < MAX liefern daher FALSCH. Aber das Programm steigt von vorher aus, wegen der Speicherverletzung.

Deshalb sollte es richtig lauten.

while(i >=0 && i < MAX && a[i] != '\0') {
  i++;
}

1. Zuerst die Überprüfung, ob Indexgrenzen gültig sind.

2. Dann der Zugriff auf die Position.

Das Prinzip dahinter heisst “Kurzschlussauswertung”:

1. Im Falle von “UND” verknüpften Bedingungen werden diese in der textuellen Reihenfolge von links nach rechts ausgewertet.

2. Falls eine (Teil)Bedingung FALSCH liefert, liefert der ganze Ausdruck FALSCH.

3. Wichtig hier ist, dass die Anweisung a[i] != '\0' gar nicht ausgewertet wird.

Analog dazu ist die Auswertung von “ODER” verknüpften Bedingungen. Wiederum in textueller Reihenfolge von links nach rechts. Sobald eine (Teil)Bedingung WAHR liefert, liefert der ganze Ausdruck WAHR. Danach folgende Bedingungen werden nicht mehr ausgewertet.

Was bedeutet dies für die Verhersagbarkeit der zeitlichen Ausführung eines Programmes? Da auf Grund der Kurzschlussauswertung nicht alle (Teil)Bedingungen ausgewertet werden müssen, kann die Ausführungszeit sehr unterschiedlich sein.

Betrachte folgendes (künstliches) Beispiel.

if(x > 5 && factorial(y) > x)  {
}

• Angenommen x ist kleiner als 5. Dann wird der Ausdruck factorial(y) > x nicht ausgewertet.

• Angenommen x ist größer als 5. Der Ausdruck factorial(y) > x muss ausgewertet werden und kann je nach Paramter y einige Zeit in Anspruch nehmen (die Berechnungsformel für die Fakultät einer Zahl ist zwar einfach, benötigt aber einen gewissen Berechnungsaufwand).

Zusammengefasst. Je nach Wert des Parameters x ist die zeitliche Ausführung des Programms unterschiedlich.

Aber ist es nicht von Vorteil, einen Ausdruck wie factorial(y) > x erst gar nicht zu berechnen (wenn der linke Teil schon FALSCH liefert)? Jein. In gewissen Bereichen (man denke an eingebettete Systeme) möchte man, dass die zeitliche Ausführungen eines Programmes unabhängig ist von irgendwelchen Laufzeitparametern (“best case = worst case”). Das Prinzip der Kurschlussauswertung macht dies aber schwierig.

Wie könnte man die Kurschlussauswertung umgehen? Der oft angewendete Trick ist die Booleschen Operatoren durch ihre Bitweisen Pendants zu ersetzen.

Z.B. im folgenden Programmtext werden immer beide Bedingungen ausgewertet

if(x > 5 &  factorial(y) > x)  {
}

Die Regel lautet. Verwende & anstatt && und | anstatt ||. Dadurch wird die Kurzschlussauswertung umgangen.

Ist dies aber nicht gefährlich, siehe obiges Beispiel zum Arrayzugriff? Richtig. Falls aber gewünscht ist die Kurzschlussauswertung zu umgehen, muss das Programm umgeschrieben werden. Z.B. im Falle des obigen Beispiels

bool stop = false;
while(!stop) {
  if(i >=0 & i < MAX) {
         if(a[i] != '\0') {
             i++;
         } else {
             stop = true;
         }
  } else {
      stop = true; // out-of bounds
  }
}

Diese Lösung ist “aufwendiger” aber in gewisser Hinsicht ist der Programmablauf viel durchschaubarer. Solch ein Programmierstil wird vor allem in Bereichen angewandt in denen die Robustheit von Programmen (zeitliches Verhalten, Korrektheit, …) eine grosse Rolle spiel. Man denke an eingebettete Systeme im Flugzeug, Auto, Ampelsteuerung etc.

Kontrollstrukturen (Schleifen)

Vergleich von while, do-while und for Schleifen.

1. Geben Sie für jede Art von Schleife ein Beispiel.

2. Kann jede Schleifenart in die andere übersetzt werden?

3. Welche Schleife finden Sie am sinnvollsten?

4. Braucht man Schleifen überhaupt?

Schleifen sind in der Tat nicht notwendig, sobald ihre Programmiersprache rekursive Funktionsaufrufe unterstützt. Ein (praktisches) Problem dabei ist, dass die Schachtelungstiefe von Funktionsaufrufen in der Regel begrenzt ist

Zeiger

Betrachten Sie folgende Ausdrücke. Annahme dabei ist

int a[20];
int i,j;

a[i]

a[i] + j

*(a + i)

*(a + i) + j

Was machen die einzelnen Ausdrücke?

Betrachten Sie folgenden Programmtext.

int a[10];
int i;

i = 0;
while(i < 10) {
  a[i] = i;
  i++;
}

Schreiben Sie obiges Programm um. Dabei sollen Sie anstatt einer while Schleife eine for Schleife verwenden und anstatt des Arrayzugriffs nur Zeigerzugriffe verwenden.

Berechnung aller Untermengen (Bitoperationen)

C Programmierkonzepte: Bitoperationen, Schleifen und bedingte Anweisungen

Wir betrachten eine Menge von Elementen, z.B. {A, B, C, D}. Aus der Kombinatorik wissen wir, dass es genau 2^4 = 16 verschiedene Untermenge für eine Menge mit 4 Elementen gibt.

Für unser obiges Beispiel, gibt es folgende Untermengen.

 0 : {}
 1 : {A }
 2 : {B }
 3 : {A B }
 4 : {C }
 5 : {A C }
 6 : {B C }
 7 : {A B C }
 8 : {D }
 9 : {A D }
 10 : {B D }
 11 : {A B D }
 12 : {C D }
 13 : {A C D }
 14 : {B C D }
 15 : {A B C D }

Ihre Aufgabe ist es ein C Programm zu schreiben, welches die Menge aller Untermengen einer 4-elementigen Menge auf der Konsole ausgibt.

Lösungsidee

• Element in der Untermenge durch ein Bit repräsentiert
• Generiere alle möglichen Bitkombinatinen
• Für jede Bitkombination, teste ob Element vorhanden

Lösungsvorschlag 1

#include <stdio.h>

/*

Fuer Menge mit n Element gibt es 2^n (2 hoch n) Untermengen.
Mit Hilfe der Bitshiftoperation koennen wir 2^n einfach berechnen.
Wir schieben die 1, n Stellen nach links: 1 << n.

Jede Untermenge ist dargestellt als Zahl von 0 .. (1 << n) - 1.
Fuer jede Untermenge/Zahl testen wir welche Elemente vorkommen.
Die Elemente sind an Bitpositionen gebunden.
Fuer das i-te Element muessen wir testen, ob dieses Bit gesetzt ist.

Falls x die aktuelle Untermenge/Zahl, dann

   (x & (1<<i))

(1<<i) ist eine Bitmaske und wird Bitweise verundet mit x.
Dadurch testen wir, ob in x das i-te Bit gesetzt wird.

Falls ja, fuegen wir i zur aktuellen Untermenge hinzu.
Wir nehmen an, dass i=0 A ist, i=1 B ist, usw.
Um das i-te Element auszugeben, berechnen wir dessen Ascii-code.
Der ist 65+i wobei 65 der Ascii-code von A ist.

 */

int main() {
  int n = 4;
  int x,i;

  for(x=0; x < (1 << n); x++) {

    printf("\n { ");
    for(i=0; i < n; i++) {
      if(x & (1<<i)) {
        printf(" %c", 65+i);
      }

    }
    printf(" } \n");

  }

}

Lösungsvorschlag 2

Noch ein Vorschlag. Verwendet Funktionen (so haben wir weiteres Beispiel mit Funktionen). Der Vorschlag ist aber weniger allgemein. Behandelt nur den Fall n=4.

Falls Bit Position gesetzt liefere die Position als Wert zurück. Ansonsten gebe -1 zurück.

int test(unsigned short int x, int pos) {
  if (x & (1<<pos)) return pos;
  return -1;
}

Ausgabe von Element an bestimmer Position.

void printElem(unsigned short int x, int pos) {
  switch(pos) {
  case 0 : printf("A ");
           break;
  case 1 : printf("B ");
           break;
  case 2 : printf("C ");
           break;
  case 3 : printf("D ");
           break;
  }

}

Für alle möglichen Bitkombinationen (gleich alle Zahlen zwischen 0 und 15), teste für jede Position ob Element vorhanden.

int main() {
  unsigned short int x;
  int pos;

  for(x=0; x < 16; x++) {
    printf("\n %d : {", x);
    for(pos=0; pos<4; pos++) {
      printElem(x, test(x,pos));
    }
    printf("}");
  }
  printf("\n");

  return 0;
}

Erweiteren Sie die Aufgabe:

• Geben Sie die Menge aller Untermenge einer n-elementigen Menge aus, wobei n ein frei wählbarer Parameter ist.

• Als Namensbezeichnung für Elemente benutzen Sie einfach 1, 2, …

Lösung 2 komplett

# include <stdio.h>

int test(unsigned short int x, int pos) {
  if (x & (1<<pos)) return pos;
  return -1;
}

void printElem(unsigned short int x, int pos) {
  switch(pos) {
  case 0 : printf("A ");
           break;
  case 1 : printf("B ");
           break;
  case 2 : printf("C ");
           break;
  case 3 : printf("D ");
           break;
  }

}

int main() {
  unsigned short int x;
  int pos;

  for(x=0; x < 16; x++) {
    printf("\n %d : {", x);
    for(pos=0; pos<4; pos++) {
      printElem(x, test(x,pos));
    }
    printf("}");
  }
  printf("\n");

  return 0;
}

Was sticht ins Auge?

• In C/C++ ist es möglich “freistehende” Funktionen zu definieren welche nicht an eine Klasse gebunden sind.

• Funktionsdefinitionen dürfen nicht geschachtelt sein.

• Funktionen müssen erst deklariert werden bevor man die Funktion verwenden kann. Dies gilt auch für Variablen, Klassen etc.

• Jede Funktionsdefinition impliziert eine Funktionsdeklaration. Obige Reihenfolge ist wichtig. Aufgabe. Vertausche “main” mit “test” und kompiliere neu.

• Reihenfolgen kann vertauscht werden, solange “Vorwärtsreferenzen” gegeben sind. Betrachte folgende Variante.

# include <stdio.h>


// forward references
int test(unsigned short int x, int pos);
void printElem(unsigned short int x, int pos);

int main() {
  unsigned short int x;
  int pos;

  for(x=0; x < 16; x++) {
    printf("\n %d : {", x);
    for(pos=0; pos<4; pos++) {
      printElem(x, test(x,pos));
    }
    printf("}");
  }
  printf("\n");

  return 0;
}

int test(unsigned short int x, int pos) {
  if (x & (1<<pos)) return pos;
  return -1;
}

void printElem(unsigned short int x, int pos) {
  switch(pos) {
  case 0 : printf("A ");
           break;
  case 1 : printf("B ");
           break;
  case 2 : printf("C ");
           break;
  case 3 : printf("D ");
           break;
  }

}

• Wieso inferriert der Kompiler nicht automatisch diese Vorwärtsreferenzen? Zum Teil historisch bedingut. Aus Effizienzgründen versuchte man ursprünglich den Quelltext in einem Durchgang (“pass”) zu kompilieren.

Funktionen (Rationale Zahlen, Tests, Referenzübergabe)

Wir betrachten Funktionen und komplexe Datentypen an einem Beispiel. Ziel ist die Darstellung von rationalen Zahlen und Operationen auf rationalen Zahlen. In diesem Beispiel betrachten wir auch verschiedene Testansätze (User-Tests, Unit-Tests, Invarianten). Eingestreut finden sich eine Reihe von Aufgaben und Fragen. Es ist wichtig den kompletten Text zu lesen!

Rationale Zahlen

Eine rationale Zahl beschreibt das Verhältnis zweier ganzen Zahlen. Die eine wird als Zähler, die andere als Nenner bezeichnet. Z.B. 5 / 3 ist eine rationale Zahl mit Zähler 5 und Nenner 3. Wer es nochmal genauer nachlesen will siehe hier.

Hier ist eine direkte Darstellung in C als Struktur.

struct RZ_ {
    int Zaehler;
    int Nenner;
};

Wir verwenden die folgende Abkürzung.

typedef struct RZ_ RZ;

Im folgenden definieren wir eine Reihe von Funktionen welche rationale Zahlen manipulieren.

void printRZ(RZ x);            // Ausgabe
RZ scanRZ();                   // Eingabe
RZ multRZ(RZ x, RZ y);         // Multiplikation
RZ addRZ(RZ x, RZ y);          // Addition
RZ skaliereRZ(RZ x, int k);    // Skalierung

Obige Funktionsprototypen spezifizieren wie die einzelnen Funktionen verwendet werden. Z.B. RZ multRZ(RZ x, RZ y); spezifiert die Funktion multRZ als Funktion mit zwei Parametern vom Typ RZ und Rückgabe vom Typ RZ. Alternative Name für Funktionsprototyp sind Funktionsdeklaration oder auch Funktionssignatur.

Wir betrachten die Eingabe und Ausgabe welche jeweils Komponentenweise geschieht.

void printRZ(RZ x) {
  printf("%d/%d", x.Zaehler, x.Nenner);
}

RZ scanRZ() {
  RZ x;
  scanf("%d", &x.Zaehler);
  printf(" / ");
  scanf("%d", &x.Nenner);

  return x;
}

Der Einfachheithalber überprüfen wir nicht, ob der Nenner 0 ist. Betrachte scanf("%d", &x.Zaehler);. Der Ausdruck &x.Zaehler übergibt den Zähler als Referenz zur scanf Funktion. Der eingelesene String wird in eine Zahl umgewandelt und kann dadurch x.Zaehler zugewiesen werden.

Beachte. Der Ausdruck &x.Zaehler wird interpretiert als &(x.Zaehler). Sprich . hat eine höhere Präferenz als als &.

Es folgt skaliereRZ und addRZ. Die Definition von multRZ findet sich unten.

RZ addRZ(RZ x, RZ y) {
  RZ z, xTemp, yTemp;

  xTemp = skaliereRZ(x,y.Nenner);
  yTemp = skaliereRZ(y, x.Nenner);
  z.Zaehler = xTemp.Zaehler + yTemp.Zaehler;
  z.Nenner  = xTemp.Nenner;

  return z;
}

RZ skaliereRZ(RZ x, int k) {
  RZ z;

  z.Zaehler = x.Zaehler*k;
  z.Nenner  = x.Nenner*k;

  return z;
}

Beachte. Die Definition von addRZ verwendet skaliereRZ welches aber erst danach definiert wird. Dies ist kein Problem da wir oben schon alle Funktionen mit Hilfe von Funktionsprototypen spezifziert haben.

Betrachte addRZ. Mit Hilfe von skaliereRZ bringen wir x und y auf einen gemeinsamen Nenner. Von den daraus folgenden rationalen Zahlen, müssen wir dann nur noch die Zähler addieren.

Tests

Wie können wir sicherstellen, dass sich kein Bug in unserer Implementierung befindet. Durch Tests. Falls ein Test fehlschlägt, haben wir möglicherweise einen Bug entdeckt (Der Test selber könnte einen Bug haben!). Falls die Tests erfolgreich sind, heisst es nicht, dass es nicht doch noch einen Bug gibt. Zumindest aber, im Falle einer ausreichenden Anzahl von Tests, haben wir eine gewisse Sicherheit. Wir betrachten verschiedene Arten von Tests.

User-Tests

Der User liefert die Eingaben. Verschiedene Operationen werden ausgeführt. Anhand der Ausgabe überprüft der User ob es stimmt.

void test1() {
  RZ x, y, z;

  printf("Test 1 \n");

  printf("Eingabe1: \n");
  x = scanRZ();

  printf("\n Eingabe2: \n");
  y = scanRZ();


  printRZ(x); printRZ(y);

  printf("\n Add Ausgabe: ");
  printRZ(addRZ(x,y));

  printf("\n Mult Ausgabe: ");
  printRZ(multRZ(x,y));

}

Unit-Tests

Wir automatisieren User-Tests. Dies liefert dann Unit-Tests. Im Programm legen wir die Eingaben fest. Führen die Operation (oder eine Sequenz von Operationen) aus. Und vergleichen dann das berechnete mit dem erwarteten Ergebnis. Diese Test Methode ist unter dem Namen Unit-Tests bekannt. In vielen IDES sind Unit-Tests integriert (sogenannte boilerplate code wird von der IDE generiert).

Hier ein paar Unit-Tests für unser Beispiel.

void unitTest1() {
  RZ x, y, z;

  x.Zaehler = 5; x. Nenner = 3;
  y.Zaehler = 3; y.Nenner = 5;

  z = multRZ(x,y);

  if(z.Zaehler != z.Nenner)
     printf("\n Fehler");


  x.Zaehler = 2; x. Nenner = 3;
  y.Zaehler = 1; y.Nenner = 3;

  z = addRZ(x,y);

  if(z.Zaehler != z.Nenner)
     printf("\n Fehler");
}

Unit-Tests sind wichtig. Ein Nachteil ist, dass für jeden Testfall (Eingabe) und Operationssequenz das erwartete Ergebnis bekannt sein muss.

Invarianten

Assertions (auf Deutsch Zusicherung) sind Aussagen die an bestimmte Programmzustände gekoppelt sind. Invarianten sind Aussagen die immer gelten. Zumindest für mehrere Programmabfolgen wie z.B. Schleifen. Hier ist ein einfaches Beispiel.

int i;
i = 1;
i++;
// Assertion die prueft, dass i inkrementiert wurde und den Wert 2 hat
if(i != 2)
   printf("\n Fehler");

for(; i<10; i++) {

  // Invariante
  if(i <= 0)
    printf("\n Fehler");

}

i != 2 und i <= 0 sind beides Aussagen (also Assertions). Die Aussage i != 2 ist an einem bestimmte Programmzustand (Programmpunkt) gekoppelt. Die Aussage i <= 0 negiert soll für die Schleife gelten. Im letzteren Fall spricht man deshalb von einer Invariante.

Welche Invarianten gelten für unseren Fall?

Betrachte die Multiplikation rationaler Zahlen. Folgendes gilt:

n/m * m/n = (n*m) / (n*m)

Für Zahlen m und n, und Operation n/m * m/n gilt die Invariante das im Ergebnis Nenner und Zähler gleich sein müssen.

Angewandt auf unsere Implementierung.

int m,n;
RZ x,y,z;

  for(n = 1; n <6; n++) {
    for(m = 1; m < 6; m++) {
      x.Zaehler = n; x.Nenner = m;
      y.Zaehler = m; y.Nenner = n;
      z = multRZ(x,y);

      if(z.Zaehler != z.Nenner)
          printf("\n Fehler");

    }
  }

Finden sie weitere Invarianten (z.B. für addRZ).

Referenzübergabe

Betrachte folgende Variante von skaliereRZ. Die zu skalierende rationale Zahl wird als Referenz übergeben.

void skaliereRZ2(RZ *x, int k) {
  RZ z;

  (*x).Zaehler = (*x).Zaehler*k;
  (*x).Nenner  = (*x).Nenner*k;

}

Zur Erinnerung. Deklaration RZ *x spezifiert x als Referenz auf einen Wert vom Typ RZ. Um auf den eigentlich Wert (rationale Zahl) zuzugreifen, schreiben wir *x. Der Wert ist eine Struktur. Der Zugriff auf das Zaehler Element ist wie folgt: (*x).Zaehler.

Wir betrachten eine Variante von addRZ welche skaliereRZ2 verwendet.

RZ addRZ2(RZ x, RZ y) {
  RZ z;

  skaliereRZ2(&x,y.Nenner);
  skaliereRZ2(&y, x.Nenner);
  z.Zaehler = x.Zaehler + y.Zaehler;
  z.Nenner  = x.Nenner;

  return z;
}

Beachte: Bei Aufruf einer Funktion mit Referenzübergabe muss die Referenz und nicht der Wert übergeben werden. Deshalb finden wir z.B. skaliereRZ2(&x,y.Nenner). Mit &y üergeben wir die Referenz auf y, mit y.Nenner übergeben wir den Wert gespeichert im Nenner von y.

In der Implementierung von addRZ2 hat sich ein Fehler eingeschlichen. Die Addition zweier rationaler Zahlen wird nicht immer korrekt ausgeführt. Finden sie den Fehler mit Hilfe von Tests (z.B. Unit-Tests oder mit Hilfe von Invarianten). Beheben sie den Fehler.

Kürzen (Erweiterte Funktionalität)

RZ kuerzenRZ(RZ x);

Implementierung sie eine Funktion welche die rationale Zahl kürzt. Folgende Kürzungsregel gilt: (k * m) / (k * n) = m / n.

Komplettes Programm

Enthält Lösungsvorschläge für einen Teil der Aufgaben.

#include <stdio.h>


// Rationale Zahlen: Zaehler/Nenner.
// Repraesentiert als struct.
// Oft schreiben wir x1/x2 als Kurzform fuer x.Zahler/x.Nenner.
struct RZ_ {
    int Zaehler;
    int Nenner;
};

// Abkuerzende Schreibweise.
typedef struct RZ_ RZ;

// Geht auch direkt. Typedef kombiniert mit Strukturdeklaration.
/*
typedef struct RZ_ {
    int Zaehler;
    int Nenner;
} RZ;
*/

// Vorwaertsfunktions Deklarationen
void printRZ(RZ x);
RZ scanRZ();
RZ multRZ(RZ x, RZ y);
RZ addRZ(RZ x, RZ y);
RZ skaliereRZ(RZ x, int k);



// Ausgabe.
void printRZ(RZ x) {
  printf("%d/%d", x.Zaehler, x.Nenner);
}

// Eingabe.
RZ scanRZ() {
  RZ x;
  scanf("%d", &x.Zaehler);
  printf(" / ");
  scanf("%d", &x.Nenner);

  return x;
}

// Multiplikation ist Komponenteweise.
//   x1/x2 * y1/y2
// = (x1*y1) / (x2*y2)
RZ multRZ(RZ x, RZ y) {
  RZ z;

  z.Zaehler = x.Zaehler * y.Zaehler;
  z.Nenner = x.Nenner * y.Nenner;

  return z;
}

// Addition. Auf gemeinsamen Nenner bringen.
//   x1/x2 + y1/y2
// = (x1*y2) / (x2*y2)   +  (y1*x2) / (x2*y2)
// = (x1*y2 + y1*x2) / (x2*y2).
RZ addRZ(RZ x, RZ y) {
  RZ z, xTemp, yTemp;

  xTemp = skaliereRZ(x,y.Nenner);
  yTemp = skaliereRZ(y, x.Nenner);
  z.Zaehler = xTemp.Zaehler + yTemp.Zaehler;
  z.Nenner  = xTemp.Nenner;

  return z;
}

// Skaliere.
RZ skaliereRZ(RZ x, int k) {
  RZ z;

  z.Zaehler = x.Zaehler*k;
  z.Nenner  = x.Nenner*k;

  return z;
}


// Variante mit Referenzuebergabe.
void skaliereRZ2(RZ *x, int k) {
  RZ z;

  (*x).Zaehler = (*x).Zaehler*k;
  (*x).Nenner  = (*x).Nenner*k;

}

// Add Variante welche skaliereRZ2 verwendet
RZ addRZ2(RZ x, RZ y) {
  RZ z;

  skaliereRZ2(&x,y.Nenner);
  skaliereRZ2(&y, x.Nenner);
  z.Zaehler = x.Zaehler + y.Zaehler;
  z.Nenner  = x.Nenner;

  return z;
}

// Beachte:
// In C muessen all Variablen am Anfang der Funktion deklariert werden.
// In C++ duerfen Variablen auch innerhalb einer Funktion definiert werden.
void test1() {
  RZ x, y, z;

  printf("Test 1 \n");

  printf("Eingabe1: \n");
  x = scanRZ();

  printf("\n Eingabe2: \n");
  y = scanRZ();


  printRZ(x); printRZ(y);

  printf("\n Add Ausgabe: ");
  printRZ(addRZ(x,y));

  printf("\n Mult Ausgabe: ");
  printRZ(multRZ(x,y));

}

void unitTest1() {
  RZ x, y, z;

  x.Zaehler = 5; x. Nenner = 3;
  y.Zaehler = 3; y.Nenner = 5;

  z = multRZ(x,y);

  if(z.Zaehler != z.Nenner)
     printf("\n Fehler");


  x.Zaehler = 2; x. Nenner = 3;
  y.Zaehler = 1; y.Nenner = 3;

  z = addRZ(x,y);

  if(z.Zaehler != z.Nenner)
     printf("\n Fehler");
}

RZ inverseRZ(RZ x) {
  int tmp;

  tmp = x.Zaehler;
  x.Zaehler = x.Nenner;
  x.Nenner = tmp;

  return x;
}

void invarianten() {
  int i,n,m;
  RZ rz[4] = { {1,2}, {3,4}, {5,2}, {4,7} };   // Fest definierte Auswahl von Tests
  RZ x,y,z;
  n = 4;

  // mult: n/m * m/n liefert Zaehler == Nenner
  for(i=0; i<n; i++) {
    x = multRZ(rz[i], inverseRZ(rz[i]));
    if(x.Zaehler != x.Nenner)
        printf("\n Fehler");
  }


  for(n = 1; n <6; n++) {
    for(m = 1; m < 6; m++) {
      x.Zaehler = n; x.Nenner = m;
      y.Zaehler = m; y.Nenner = n;
      z = multRZ(x,y);

      if(z.Zaehler != z.Nenner)
          printf("\n Fehler");

    }
  }

  // add: 1/m + (m-1)/m liefert Zaehler == Nenner
  m = 10;
  for(i=2; i<m; i++) {
    x.Zaehler = 1; x.Nenner = i;
    y.Zaehler = i-1; y.Nenner = i;
    z = addRZ(x,y);
    if(z.Zaehler != z.Nenner)
      printf("\n Fehler %d %d %d \n", i, z.Zaehler, z.Nenner);
  }

  // add2 Variante
    for(i=2; i<m; i++) {
    x.Zaehler = 1; x.Nenner = i;
    y.Zaehler = i-1; y.Nenner = i;
    z = addRZ2(x,y);
    if(z.Zaehler != z.Nenner)
      printf("\n Fehler %d %d %d \n", i, z.Zaehler, z.Nenner);
  }
}




int main() {

  // test1();
  unitTest1();

  invarianten();
}

Count - Zählen von Wörtern inklusive Testrahmen (Zeiger und Strings)

Wir betrachten Strings und Manipulationen auf Strings. Hintergrund zu Strings. Siehe C - Teil 3.

Zählen von Wörtern

Ein Wort ist eine Sequenz von Zeichen in der das Leerzeichen (white-space) nicht vorkommt. Aufgabe ist es eine Funktion zu schreiben, die die Anzahl der Wörter in einem String zählt.

Verwenden Sie folgenden Funktionsprototypen.

int count(char* input);

Wir entwickeln eine Musterlösung für diese Aufgabe. Wichtig dabei ist der Nachweis der Korrektheit.

Um ein erstes Verständnis zu bekommen betrachten wir mögliche Eingaben und die erwarteten Ausgaben.

count("") ==> 0
count("Hallo") ==> 1
count("  Hallo") ==> 1
count("  Ha llo") ==> 2

Bevor man mit der Implementierung anfängt ist es elementar wichtig genau die Aufgabenstellung zu analysieren. WAS genau ist gefordert? WAS sind typische Eingaben und die erwarteten Ergebnisse?

Das WIE implementiere ich die Aufgabenstellung ist hier erst einmal zweitrangig.

Deshalb entwerfen wir als erstes einen Testrahmen, mit dessen Hilfe wir unsere Implementierung testen können. Von der “Java” Vorlesung sind Sie mit Unit-Tests vertraut. Solch ein Unit-Test Framework steht uns hier nicht zur Verfügung (gibt es natürlich auch für C/C++). Den notwendigen Testrahmen haben wir uns aber schnell selber gebaut.

Zuerst beschreiben wir die möglichen Testergebnisse.

typedef enum {
  OK,
  FAIL
} Test;

Ein Testfall besteht aus einem String und dem erwarteten Ergebnis. Wir schreiben eine kleine Hilfsfunktion, die einen Testfall ausführt und auf das erwartete Ergebnis testet.

Test testCount(char* input, int expected) {
  Test t;

  if(expected == count(input)) {
    t = OK;
  }
  else {
    t = FAIL;
  }
  return t;
}

Wir werden sicherlich eine Reihe von Testfällen benötigen, deshalb fassen wir einen Testfall in einer Struktur zusammen.

typedef struct {
  char* input;
  int expected;
} TestCase;

Folgende Hilfsfunktion erlaubt uns die automatische Ausführung einer ganzen Reihe von Testfällen.

void runTests(int no, TestCase test[]) {
  Test t;
  int i;

  for(i=0; i < no; i++) {
    printf("Test %d: ", i);
    t = testCount(test[i].input, test[i].expected);
    if(OK == t)
      printf("OK \n");
    if(FAIL == t)
      printf("FAIL \n");
  }
}

Eingabe no beschreibt die Anzahl der Testfälle. Die eigentlichen Testfälle werden als Array test bestehend aus Strukturen des Typs TestCase übergeben. Auf jeden Testfall wenden wir die Hilfsfunktion testCount an.

In unseren Fall protokollieren wir die Testergebnisse durch Aufgabe auf der Konsole. In Industrieprojekten werden die Testergebnisse normalerweise auf Platte geschrieben und mit der Versionsnummer der getesteten Software versehen.

Hier ist eine Auswahl signifikanter Testfälle.

int main() {
  const int testNo = 9;
  TestCase tests[9] = {
       {"", 0},
       {"Hallo", 1},
       {"  Hallo", 1},
       {"Hallo", 1},
       {"  Hallo  ", 1},

       {"Hal lo", 2},
       {" Hal lo", 2},
       {"Hal lo ", 2},
       {" Hal lo  ", 2}
     };

  runTests(testNo,tests);
}

Den Testrahmen haben wir also, wir haben aber immer noch keine einzige Zeile der Funktion count implementiert! Keine Angst kommt gleich. Die wichtige Nachricht an dieser Stelle ist: Ein Grossteil der Entwicklungszeit wird nicht auf das WIE verwendet, der meiste Entwicklungsaufwand beschäftigt sich mit WAS:

• … soll die Software eigentlich leisen?
• … ging schief, wo liegt der Fehler?
• …

Nun endlich zur eigentlichen Implementierung. Betrachten wir noch einmal die Beispieleingaben und -ausgaben.

count("") ==> 0
count("Hallo") ==> 1
count("  Hallo") ==> 1
count("  Ha llo") ==> 2

Im Falle des leeren Strings geben wir 0 zurück. Ansonsten suchen wir den Anfang eines Wortes? WIE machen wir das?

Entweder (a) wir befinden uns schon am Anfang eines Wortes, oder (b) das aktuelle Zeichen ist ein Leerzeichen.

Im Fall (b) überspringen wir alle Leerzeichen. Aha, wir haben die Aufgabe zerlegt in eine Teilaufgabe. Hier ist eine Funktion, die die Teilaufgabe (a) umsetzt.

char* leerzeichen(char* input) {
  while(*input == ' ')
    input++;
  return input;
}

Wir “iterieren” durch den String solange bis wir auf ein Zeichen treffen, welches nicht eine Leerzeichen ist. Rückgabe ist ein Zeiger auf das getroffene Nicht-Leerzeichen.

Betrachten wir Fall (a). Wir befinden uns am Anfang eines Wortes. Ein Wort besteht aus einer Sequenz von Nicht-Leerzeichen. Also iterieren wir durch den String bis wir auf ein Leerzeichen treffen. Das stimmt fast! Zu beachten ist hier der Spezialfall, dass wir das Ende des Strings erreichen. Fall (a) lässt sich wiederum sehr einfach mit Hilfe einer Funktion beschreiben.

char* zeichen(char* input) {
  while(*input != '\0' && *input != ' ')
    input++;
  return input;
}

Wir haben jetzt die einzelnen Teilaufgaben. Damit lässt sich nun die count Aufgabe einfach lösen.

Zuerst in Pseudo-Code:

Solange das Ende nicht erreicht ist:

1. Überspringe alle Leerzeichen

2. Fall Zeichen gefunden

   1. zähle Anzahl gefunder Wörter hoch
   2. Gehe zu Wortende

Hier ist die (literale) Umsetzung.

int count(char* input) {
  int cnt = 0;

  while(*input != '\0') {
    input = leerzeichen(input);
    if(*input != '\0') {
      cnt++;
      input = zeichen(input);
    }
  }
  return cnt;
}

Was kann man an der Lösung verbessern?

Performance. Z.B. leerzeichen und zeichen als inline deklararieren.

Die Namensgebung ist auch verbesserungswürdig. Anstatt leerzeichen ein treffender Name ist leerzeichenUeberspringen oder skipBlanks auf Englisch.

Als Anhang der komplette Programmcode

#include "stdio.h"

// Ueberspringe alle Leerzeichen
// Rueckgabe ist Zeiger auf das erste Nichtleerzeichen
char* leerzeichen(char* input) {
  while(*input == ' ')
    input++;
  return input;
}

// Scanne durch string solange bis wir auf ein
// Leerzeichen oder das Ende des Strings treffen.
// Effektiv ueberspringen wir ein Wort.
// Rueckgabe: Zeiger auf Ende oder Leerzeichen.
char* zeichen(char* input) {
  while(*input != '\0' && *input != ' ')
    input++;
  return input;
}


int count(char* input) {
  int cnt = 0;

  // Solange das Ende nicht erreicht ist:
  // 1. Ueberspringe alle Leerzeichen
  // 2. Falls Zeichen gefunden
  //     (a) setze Zaehler hoch
  //     (b) Gehe zu Wortende

  while(*input != '\0') {
    input = leerzeichen(input);
    if(*input != '\0') {
      cnt++;
      input = zeichen(input);
    }
  }
  return cnt;
}


typedef enum {
  OK,
  FAIL
} Test;

Test testCount(char* input, int expected) {
  Test t;

  if(expected == count(input)) {
    t = OK;
  }
  else {
    t = FAIL;
  }
  return t;
}


typedef struct {
  char* input;
  int expected;
} TestCase;


void runTests(int no, TestCase test[]) {
  Test t;
  int i;

  for(i=0; i < no; i++) {
    printf("Test %d: ", i);
    t = testCount(test[i].input, test[i].expected);
    if(OK == t)
      printf("OK \n");
    if(FAIL == t)
      printf("FAIL \n");
  }
}


int main() {
  const int testNo = 9;
  TestCase tests[9] = {
       {"", 0},
       {"Hallo", 1},
       {"  Hallo", 1},
       {"Hallo", 1},
       {"  Hallo  ", 1},

       {"Hal lo", 2},
       {" Hal lo", 2},
       {"Hal lo ", 2},
       {" Hal lo  ", 2}
     };

  runTests(testNo,tests);

}

Als Anhang: Zustandsbasierte Modellierung

#include "stdio.h"

/*

1. Woerter in einem String zaehlen.

Was ist ein Wort?
Wir definieren ein Wort als eine Sequenz von
Zeichen welche nicht getrennt ist durch Leerzeichen.

2. Zustands-basierte Modellierung.

Wir definieren unser Alphabet als die Menge

Sigma = { CH, EOS, WS }

wobei

EOS = Nullterminator

WS = Leerzeichen ('white space')

CH = Zeichen ('character')


Die Menge von Zustaenden und Transitionen ist wie folgt.

1 -- WS --> 1

1 -- EOS --> 2

1 -- CH --> 3

3 -- WS --> 1

3 -- CH --> 3

3 -- EOS --> 2

Menge von Zustaenden ist {1,2,3}

1 ist der Startzustand

3 ist der Finalzustand

Obiger Automat ist ein Beipsiel eines endlichen Automaten.

3. Zaehlen von Woertern.

Um die Woerten zu zaehlen, benoetigen wir neben einer Eingabe (Zeichen WS, CH, EOS)
auch eine Ausgabe (Anzahl der gefunden Woerter).

Dazu koennen wir einen Mealy/Moore Automaten verwenden.
Z.B. im Fall eines Mealy Automaten koennen wir auf die Transition eine Ausgabe legen.

Notation.

Wir schreiben

state1 -- In / Out --> state2

Fuer einen Uebergang von Zustand state1 nach Zustand state2,
falls das aktuelle Eingabesymbol In ist.
Als Ausgabe finden wir Out.
Ein Mealy Automate liefert einen Trace von Ausgabesymbolen.
Wir benutzen zur Vereinfachung eine Zustandsvariable.


-- / cnt=0 --> 1

1 -- WS --> 1

1 -- EOS --> 2

1 -- CH / cnt++ --> 3

3 -- WS --> 1

3 -- CH --> 3

3 -- EOS --> 2



 */



// Implementierung 1

char* scanWS(char* s) {

  while(*s == ' ') {
    s++;
  }
  return s;
}

int isCH(char c) {
  return (c != ' ' && c != '\0');
}

char* scanCH(char* s) {

  while(isCH(*s)) {
    s++;
  }
  return s;
}


int countWords(char* s) {
  int cnt = 0;

  s = scanWS(s);

  while(isCH(*s)) {
    cnt++;
    s = scanCH(s);
    s = scanWS(s);
  }
  return cnt;
}

// Implementierung 2
// Direkte Umsetzung des Modells.

int countWordsModell(char* s) {
  int state = 1;
  int cnt = 0;

  while(1) {
    switch(state) {
    case 1:
       if(*s == ' ')
     state = 1;
       if(*s == '\0')
     state = 2;
       if(isCH(*s)) {
     cnt++;
     state = 3;
       }
       break;
    case 2:
      return cnt;
    case 3:
       if(*s == ' ')
     state = 1;
       if(*s == '\0')
     state = 2;
       if(isCH(*s))
     state = 3;
       break;

    } // switch

   s++; // next symbol

  } // while
}



int main() {

  // Write your own tests and use cases :)

  return 1;
}

Strings - Speicherverwaltung

Speicherveraltung (malloc/free) am Beispiel von strings.

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

printf ist Teil der stdio Bibliothek. malloc und free sind Teil der stdlib Bibliothek.

char* initString(int n) {
  char* p = malloc((n+1) * sizeof(char));
  char* q = p;
  int i;
  for(i = 0; i < n; i++, q++) {
    *q = ' ';
  }
  *q = '\0';

  return p;
}

Die initString Funktion liefert einen String mit n Leerzeichen.

• Dazu werden n+1 Zeichen (char) mit Hilfe von `malloc’ allokiert.

• Die ersten n Stellen im String werden mit Leerzeichen beschrieben.

• Wichtig ist die Nullterminierung (zur Kennzeichnung des Ende des Strings) mittels des Ascii-codes 0.

int len(char* s) {
  int i = 0;
  while(*s != '\0') {
    s++;
    i++;
  }
  return i;
}

Wir berechnen die Länge eines Strings. Eine solche Funktion ist natürlich in der C Standard Bibliothek schon vorhanden. Zur Übung schreiben wir unsere eigene `len’ Funktion.

char* duplicateChars(char* s) {
  int i = len(s);
  char* t = initString(2*i);
  char* p = t;
  char* r = s;

  while(*s != '\0') {
    *p = *s;
    p++;
    *p = *s;
    p++;
    s++;

  }
  free(r);

  return t;
}

Die duplicateChars Funktion dupliziert jedes Zeichen in einem String.

• Dazu wird ein String entsprechender Größe angelegt.

• Wir iterieren über den bestehenden String und kopieren jedes Zeichen zweimal.

Beachte. Der bestehende String wird gelöscht. D.h. der von dem String belegte Speicher wird freigegeben. Siehe den Aufruf free(r).

Es folgt ein Anwendungsbeispiel.

int main() {
  char* s;
  char* t;

  s = initString(3);
  s[0] = '1';
  s[1] = '2';
  s[2] = '3';

  printf("\n %s", s);

  t = duplicateChars(s);
  printf("\n %s", t);

  return 1;
}

Der String “123” wird anglegt. Dann werden die Zeichen verdoppelt. Die zwei printf Ausgaben liefern.

123
112233

Beachte

Nach dem Aufruf duplicateChars(s) kann nicht mehr auf den String “123” referenziert via dem Zeiger s zugegriffen werden, da dieser Speicher freigegeben wurde (innerhalb von duplicateChars).

Der Speicher des String “112233” referenziert via dem Zeiger t wird nach Abschluss der main Routine nicht freigegeben (es fehlt free(t)). Wir haben dadurch ein Speicherleck.

Als Anhang der komplette Programmcode

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


char* initString(int n) {
  char* p = malloc((n+1) * sizeof(char));
  char* q = p;
  int i;
  for(i = 0; i < n; i++, q++) {
    *q = ' ';
  }
  *q = '\0';

  return p;
}


int len(char* s) {
  int i = 0;
  while(*s != '\0') {
    s++;
    i++;
  }
  return i;
}

char* duplicateChars(char* s) {
  int i = len(s);
  char* t = initString(2*i);
  char* p = t;
  char* r = s;

  while(*s != '\0') {
    *p = *s;
    p++;
    *p = *s;
    p++;
    s++;

  }
  free(r);

  return t;
}


int main() {
  char* s;
  char* t;

  s = initString(3);
  s[0] = '1';
  s[1] = '2';
  s[2] = '3';

  printf("\n %s", s);

  t = duplicateChars(s);
  printf("\n %s", t);

  return 1;
}

Speicherverwaltung und Pointer am Beispiel von Fibonacci (C)

Explizite Speicherverwaltung und Pointer sind ``trickreiche’’ C Themen Anhand eines erweiterten Beispiels sollen diesen Themen geübt werden. Als Beispiel betrachten wir Fibonacci.

Der komplette erarbeitete Source Code befindet sich im Anhang. Fragen und erweiterte Aufgaben befinden sich im Haupttext.

Fibonacci

In C kann die Fibonacci wie folgt ausgedrückt werden.

int fib(int n){
 int f1, f2;
 if (n<=1) return 1;
 f1=fib(n-1);
 f2=fib(n-2);
 return f1+f2;
}

Was ergibt der Aufruf fib(3)?

Die Funktionsaufrufabfolge kann durch einen Stack simuliert werden. Das Laufzeitsystem benutzt einen Run-Time Stack zur Verwaltung von Funktionsaufrufen Dieser Run-Time Stack kann mittels Debugger beobachtet werden

Aufgabe: Setzen Sie geignete break points und verfolgen Sie die Berechung von fib(3).

Run-Time Stack

Der Speicherbereich bei der Ausführung des Programmes ist wie folgt aufgeteilt.

 CODE
 STATIC DATA
 STACK
 ...
 HEAP

• CODE enthält den übersetzten und gelinkten Source Code
• STATIC DATA enthält alle statischen Datenanteile
• STACK ist der Speicherbereich für lokale Daten (Variablen definiert in Funktionen, Funktionsparameter und der Rückgabewerte)
• HEAP ist der Speicherbereich für dynamische Daten, die explizt vom Programm allokiert werden
• STACK und HEAP befinden sich in der Regel an gegenseitigen Enden des Speicherbereichs (wo genau hängt von Compiler/Platform ab). Beide Bereiche wachsen und schrumpfen zur Laufzeit.

Speicheradressen und Run-Time Stack

Folgende Variante der Fibonacci Implementierung, erlaubt es uns zu beobachten an welchem Ende des Speichers sich der Stack befindet.

int fib2(int n) {
 int f1, f2;
 int* nPtr;
 printf("fib2(%d)\n",n);
 nPtr = &n;
 printf("&n = %ld \n",(long int)nPtr);
 if (n<=1) return 1;
 f1=fib2(n-1);
 f2=fib2(n-2);
 return f1+f2;
}

• &n liefert Adresse der Variable n
• Dargestellt durch Pointer auf einen int Wert.
• Zur Ausgabe wird der Pointer in einen long int Wert gecastet

Nochmal Ausführung von Fibonacci

int fib(int n){
 int f1, f2;
 if (n<=1) return 1;
 f1=fib(n-1);
 f2=fib(n-2);
 return f1+f2;
}

 fib(4) -> fib(3)  -> fib(2)  -> fib(1)
                              -> fib(0)
                   -> fib(1)
        -> fib(2)  -> fib(1)
                   -> fib(0)

• Was fällt auf?
• Mehrfache Berechnung von z.B. fib(2)
• Idee:
  • Speichere Wert beim ersten Aufruf
  • Bei nochmaligen Aufruf führe ein “look-up” durch
• Vorteil: Erspannte mehrfache Berechnungen die zum gleichen Ergebnis führen
• Diese Technik ist auch bekannt als dynamische Programmierung
• Optimierung von Fibonacci durch Speicherung bereits berechneter Ergebnisse

Reine Funktionen

Funktion fib ist ein Beispiel einer reinen Funktion (auch Referenz transparent genannt, auf English pure/referentially transparent function). Eine reine Funktion liefert für jeden Aufruf bei gleicher Eingabe das gleiche Ergebnis. Im allgemeinen gilt dies für Funktionen in C nicht. Betrachte eine Funktion, deren Berechnung von einer globalen oder statischen Variablen abhängt.

Fibonacci Array

enum  Status {
  Full=0,
  Empty=1
};
struct Fib {
  int fib;
  enum Status status;
};
struct Fib fibArr[100];

Das Fibonacci Array dient zur Speicherung der ersten 100 Werte von Fibonacci.

• Wir benutzen ein enum um zu signaliseren, ob der Wert schon berechnet wurde.

Der Zugriff darauf geschieht via zweier Operationen:

• Speicheren einen berechnten Wert.
• Lookup eines Wertes.

Es folgt eine Implementierungsskizze beider Operationnen.

• Speichere Wert fib(n) = x:

  fibArr[n].fib = x;
  fibArr[n].status = Full;

• Lookup fib(n):

  if (fibArr[n].status == Full)
     return fibArr[n].fib;
  else
     return fib(n);

Aufgabe: Was fehlt in der Implementierungsskizze? (Hinweis: Die Länge des Fibonacci Arrays ist begrenzt)

Array versus Pointer

Wir wiederholen die Definition des Fibonacci Arrays und fügen eine Typdefinition hinzu.

enum  Status {
  Full=0,
  Empty=1
};
struct Fib {
  int fib;
  enum Status status;
};
struct Fib fibArr[100];
typedef struct Fib* FibPtr;

Der Typ FibPtr beschreibt einen Zeiger auf die Struktur Fib. Beachte:

• Der Name jedes Arrays stellt einen konstanten Zeiger auf das erste Arrayelement dar.
• Deshalb zeigt fibArr auf das erste Element in dem Array von 100 Element vom Typ der Struktur Fib.
• Effektiv ist fibArr ein Pointer vom Typ FibPtr.

Als nächstes gehen wir die Optimierung von Fibonacci mit Hilfe des Fibonacci Arrays an.

Ausgabe Fibonacci Array

Zuerst definieren wir eine Hilfsfunktion, die es uns erlaubt die einzelnen Elemente des Fibonacci Arrays auszugeben. Der erste Parameter ist ein Zeiger auf das erste Element und der zweite Parameter beschreibt die Länge des Arrays. Aktuell gehen wir von 100 Elementen aus, das kann sich ja aber auch ändern.

void printFibArray(FibPtr f, int len) {
  int i;

  for(i=0; i<len; i++) {
    printf("fib[%d]=",i);
    if(f[i].status == Empty) {
      printf("Empty\n");
    }
    else {
      printf("%d\n",f[i].fib);
    }
  }
}

Aufgabe: Durch falsche Anwendung ist der Parameter f möglicherweise gleich dem NULL Zeiger. Füge Sie eine Abfrage ein, die einen Zugriff auf NULL ausschliesst.

Allokation des Fibonacci Arrays

Wir allokieren ein Fibonacci Array von variabler Länge.

FibPtr allocFibArray(int len) {
  FibPtr f, f2;
  int i;
  f = malloc(sizeof(struct Fib) * len);
  f2 = f;
  for(i = 0, f2 = f; i < len; i++,f2++) {
    f2->status = Empty;
  }
  return f;
};

// Anstatt return, Uebergebe pointer
void allocFibArray2(int len, FibPtr* f) {
  *f = allocFibArray(len);
}

• In der ersten Variante wir das allokierte Fibonacci Array als Rückgabewert geliefert. Genau genau erhalten wir als Rückgabewert einen Zeiger auf das erste Element.

• Alternativ kann als Argument ein Speicherbereich für den Rückgabewert bereitgestellt werden.

• In der zweiten Variante, erhalten wir als Argument einen Zeiger auf FibPtr. Der Wert auf den der Zeiger zeigt wird gleich dem Zeiger auf das erste Element des Fibonacci Arrays gesetzt.

• Beide Varianten sind gleichwertig. Es ist eine Frage des Geschmacks/Stils, ob man Rückgabewerte verwendet oder diese via Zeiger als Argument übergibt.

Aufgaben:

• Was ist das Problem mit folgender Variante?

void allocFibArray2(int len, FibPtr f)

• In obiger Implementierung gehen wir davon aus, dass immer genügend Speicher vorhanden ist. Sprich der malloc Aufruf liefert uns den angeforderten Speicher.

  • Was könnte passieren im Falle von Speichermangel?
  • Skizzieren Sie eine Erweiterung von allocFibArray die Speichermangel abfängt.

Fibonacci und dynamische Programmierung

Wir gehen davon aus, dass ein Fiboncacci Array fester Größe gegeben ist. Zur Strukturierung verwenden wir eine Struktur, die die Arraylänge und den Zeiger auf das erste Arrayelement enthält.

struct FibArray {
  FibPtr f;
  int len;
};

Es folgt der Source Code von Fibonacci mit dynamischer Programmierung. Erklärungen finden sich im Anschluss.

int fib3(struct FibArray fa, int n){
  int f1, f2, fib;

 if (n <= 0) return 1;

 // Lookup
 if(n < fa.len) {
   if(fa.f[n].status == Full) {
     return fa.f[n].fib;
   }
 }

 // Berechne fib
 if (n<=1) {
   fib = 1;
 }
 else {
    f1=fib3(fa,n-1);
    f2=fib3(fa,n-2);
    fib = f1 + f2;
 }

 // Speichere fib Wert
 if(n < fa.len) {
   if(fa.f[n].status == Empty) { // Redundant?
     fa.f[n].status = Full;
     fa.f[n].fib = fib;
   }
 }
 return fib;
}

• Lookup falls schon berechet und Index innerhalb der gegebenen Arraygrenze lieft.

• Berechne fib, falls

  • erste Berechnung, oder
  • Index ausserhalb Grenze liegt

• Speichere Wert, falls Index innerhalb Grenzen liegt.

Aufgabe: Erklären Sie wieso die Redundant markiert Stelle überflüssig ist. (Erklärung findet sich im Anhang)

Dynamische Erweiterung des Fibonacci Array

Aufgabe: Implementieren Sie eine Variante, die eine dynamische Anpassung des Fibonacci Arrays erlaubt.

int fib4(struct FibArray* fa, int n);

fa wird nun als Pointer übergeben, so können wir von aussen Längenanpassungen sehen.

Eine Implementierung von fib4 findet sich im Anhang.

Zusammenfassung

Wir haben den Umgang mit Arrays, Pointer und manueller Speicherverwaltung am Beispiel von Fibonacci und dynamischer Programmierung geübt.

Anhang: Kompletter Source Code

#include "stdio.h"
#include "stdlib.h"

// Standard Fibonacci
int fib(int n){
 int f1, f2;
 printf("fib(%d)\n",n);
 if (n<=1) return 1;
 f1=fib(n-1);
 f2=fib(n-2);
 return f1+f2;
}

// Standard Fibonacci
// and print n's memory location
int fib2(int n) {
 int f1, f2;
 int* nPtr;
 printf("fib2(%d)\n",n);
 nPtr = &n;
 printf("&n = %ld \n",(long int)nPtr);
 if (n<=1) return 1;
 f1=fib2(n-1);
 f2=fib2(n-2);
 return f1+f2;
}

enum  Status {
  Full=0,
  Empty=1
};

struct Fib {
  int fib;
  enum Status status;
};

struct Fib fibArr[100];

typedef struct Fib* FibPtr;

void printFibArray(FibPtr f, int len) {
  int i;

  for(i=0; i<len; i++) {
    printf("fib[%d]=",i);
    if(f[i].status == Empty) {
      printf("Empty\n");
    }
    else {
      printf("%d\n",f[i].fib);
    }
  }
}

FibPtr allocFibArray(int len) {
  FibPtr f, f2;
  int i;

  f = malloc(sizeof(struct Fib) * len);

  f2 = f;
  for(i = 0, f2 = f; i < len; i++,f2++) {
    f2->status = Empty;
  }

  return f;
};

// Variante: Pointer auf zu allokierenden Speicherbereich
// wird als Argument uebergeben. Deshalb Uebergabe als
// 'Referenz' => pointer of pointer
void allocFibArray2(int len, FibPtr* f) {
  *f = allocFibArray(len);
}

struct FibArray {
  FibPtr f;
  int len;
};

// Fibonacci und dynamische Programmierung
int fib3(struct FibArray fa, int n){
  int f1, f2, fib;

 if (n <= 0) return 1;

 // Lookup falls schon berechnet
 // und Index innerhalb Grenzen ist
 if(n < fa.len) {
   if(fa.f[n].status == Full) {
     return fa.f[n].fib;
   }
 }

 // Berechne fib, weil
 // (a) erste Berechnung, oder
 // (b) Index ausserhalb Grenzen ist
 if (n<=1) {
   fib = 1;
 }
 else {
    f1=fib3(fa,n-1);
    f2=fib3(fa,n-2);
    fib = f1 + f2;
 }

 // Set fib Wert, falls Index innerhalb Grenzen ist
 if(n < fa.len) {
   if(fa.f[n].status == Empty) { // Redundant?
     fa.f[n].status = Full;
     fa.f[n].fib = fib;
   }
 }
 return fib;
}


// Redundant, weil falls nicht Empty => Full,
// aber dann haetten wir ja schon einen lookup
// durchgefuehrt und hatten den gespeicherten fib Wert
// zurueckgegeben. Also, muss der status hier immer Empty sein.



// Fibonacci und dynamische Programmierung
// mit dynamischer Anpassung von fa.
// Pointer auf FibArray, so dass wir Laengenaenderung
// von 'aussen' beobachten koennen.
int fib4(struct FibArray* fa, int n){
  int f1, f2, fib;

 if (n <= 0) return 1;

 if(n < fa->len) {
   if(fa->f[n].status == Full) {
     return fa->f[n].fib;
   }
 }
 // Dynamische Anpassung durch Verdopplung
 // (1) Allokieren neuen Speicherbereich
 // (2) Kopiere 'alt' nach 'neu'
 // (3) Gebe 'alt' frei
 else {
  FibPtr fPtr;
  int i;
  fPtr = allocFibArray(fa->len * 2);    // (1)
  for(i=0; i < fa->len; i++)            // (2)
              fPtr[i] = fa->f[i];
  free(fa->f);                          // (3)
  fa->f = fPtr;
  fa->len = fa->len * 2;
 }

 if (n<=1) {
   fib = 1;
 }
 else {
    f1=fib4(fa,n-1);
    f2=fib4(fa,n-2);
    fib = f1 + f2;
 }

 if(n < fa->len) {
   if(fa->f[n].status == Empty) { // Immer noch redundant?
     fa->f[n].status = Full;
     fa->f[n].fib = fib;
   }
 }
 return fib;
}
// if(fa->f[n].status == Empty) ist redundant
// aber NICHT if(n < fa->len),
// wir haben keine Garantie dass der erweiterte Bereich
// gross genug ist!

// Mittels defines Auswahl der jeweiligen Version
// #define STANDARD_FIB
// #define FIB_MEM_LOC
// #define FIB_DYN
#define FIB_DYN_DYN

int main() {

#ifdef STANDARD_FIB

  printf("fib(%d) = %d \n", 4,fib(4));

#endif

#ifdef FIB_MEM_LOC

  printf("fib2(%d) = %d \n", 4,fib2(4));

#endif


#ifdef FIB_DYN

  FibPtr f;
  struct FibArray fa;
  int len;

  len = 9;

  allocFibArray2(len,&f);
  printFibArray(f,len);

  fa.len = len;
  fa.f = f;

  fib3(fa,len+1);

  printFibArray(fa.f,fa.len);

#endif



#ifdef FIB_DYN_DYN

  FibPtr f;
  struct FibArray fa;
  int len;

  len = 9;

  allocFibArray2(len,&f);
  printFibArray(f,len);

  fa.len = len;
  fa.f = f;

  fib4(&fa,len*3);

  printFibArray(fa.f,fa.len);

#endif

  return 1;
}

Erweiterbarer Testrahmen (C++ virtuelle Methoden)

Wir betrachten eine Verallgemeinerung unseres Testrahmens.

Abstrakte Testklasse

Zuerst kapseln den allgemeinen Testfall in einer abstrakten Klasse.

typedef enum {
  OK,
  FAIL
} TestResult;


class TestCase {
  public:

  virtual TestResult execute() = 0;

};

Generische Testausführung

Die Testausführung kann dann generisch beschrieben werden.

void runTests(int no, TestCase* test[]) {
  TestResult t;
  int i;

  for(i=0; i < no; i++) {
    cout << "Test " << i << " ";
    t = test[i]->execute();
    if(OK == t)
      cout << "OK\n";
    if(FAIL == t)
      cout << "FAIL\n";
  }
}

Beachte: Virtuelle Methoden verlangen einen dynamischen Zeigertyp.

Spezielle Testinstanz

Wir können uns dann eine spezielle Testinstanz als Erweiterung der abstrakten Testklasse bauen.

class TestCount : public TestCase {
  char* input;
  int expected;
 public:
  TestCount(char* input_, int expected_) {
    input = input_; expected = expected_; }

  TestResult execute() {
     if(expected == count(input))
        return OK;
     return FAIL;
  }

};

Als Anhang der komplette Programmcode

Beachte: Wir bekommen die Warnung

warning: deprecated conversion from string constant to ‘char*’

Korrekterweise sollten wir entweder string benützen oder casten. Beides wurde hier der Einfachheithalber nicht gemacht.

#include <iostream>
using namespace std;


// Generischer Testrahmen

typedef enum {
  OK,
  FAIL
} TestResult;


class TestCase {
  public:

  virtual TestResult execute() = 0;

};

void runTests(int no, TestCase* test[]) {
  TestResult t;
  int i;

  for(i=0; i < no; i++) {
    cout << "Test " << i << " ";
    t = test[i]->execute();
    if(OK == t)
      cout << "OK\n";
    if(FAIL == t)
      cout << "FAIL\n";
  }
}

// Count Implementierung

char* leerzeichen(char* input) {
  while(*input == ' ')
    input++;
  return input;
}

char* zeichen(char* input) {
  while(*input != '\0' && *input != ' ')
    input++;
  return input;
}

int count(char* input) {
  int cnt = 0;

  while(*input != '\0') {
    input = leerzeichen(input);
    if(*input != '\0') {
      cnt++;
      input = zeichen(input);
    }
  }
  return cnt;
}

// Count Test Erweiterung

class TestCount : public TestCase {
  char* input;
  int expected;
 public:
  TestCount(char* input_, int expected_) {
    input = input_; expected = expected_; }

  TestResult execute() {
     if(expected == count(input))
        return OK;
     return FAIL;
  }

};


int main() {

  // Count Testfaelle

 const int testNo = 9;
  TestCase* tests[9] = {
    new TestCount("",0),
    new TestCount("Hallo", 1),
    new TestCount("  Hallo", 1),
    new TestCount("Hallo", 1),
    new TestCount("  Hallo  ", 1),
    new TestCount("Hal lo", 2),
    new TestCount(" Hal lo", 2),
    new TestCount("Hal lo ", 2),
    new TestCount(" Hal lo  ", 2)
  };

  runTests(testNo,tests);


}

Reguläre Ausdrücke und Automaten (C++)

Diese Aufgabe besteht aus folgenden Teilen:

1. Vereinfachung regulärer Ausdrücke

2. Transformation Regulärer Ausdrücke in endliche Automaten

3. Ausführung des endlichen Automaten

Teile der Aufgabe sind schon vorgegeben. Siehe Files RE.h und FSA.h. Ihre Aufgabe ist es, die fehlenden Teile zu vervollständigen. Die Grundgerüste der einzelnen Teilaufgaben finden Sie im ilias.

Reguläre Ausdrücke

In der theoretischen Informatik haben sie schon reguläre Ausdrücke kennengelernt. Mittels regulärer Ausdrücke lassen sich reguläre Sprache beschreiben, wobei eine Sprache aus einer Menge von Wörtern besteht. Jedes Wort besteht aus einer endlichen Anzahl von Zeichen. In unserem Fall stellen wir Zeichen als char dar. Deshalb sind Wörter nichts anderes als Strings.

Wir betrachten folgende syntaktischen Konstrukte:

• eps – “Epsilon” der leere String
• phi – “Phi” die leere Sprache
• c – das Zeichen c
• r1 + r2 – Alternative zwischen r1 und r2
  • Auch geschrieben als r1 | r2
• r1 r2 – Verkettung/Konkatenation von r1 mit r2
• r* – Kleenesche Hülle, entweder leerer String oder beliebige Verkettung von r

Die Sprache L(r) beschrieben durch den regulären Ausdruck r ist definiert wie folgt:

• L(phi) = {}
• L(eps) = { eps }
• L(c) = { c }
• L(r1 + r2) = { w | w in L(r1) oder w in L(r2) }
• L(r1 r2) = { w1 w2 | w1 in L(r1) und w2 in L(r2) }
• L(r*) = { w | w = eps oder w=w1 ... wn jedes wi in L(r) }

Im ersten Schritt bilden wir die Syntax von regulären Ausdrücken nach C++ ab. Dazu verwenden wir Vererbung.

class RE {};
class Phi : public RE {};
class Eps : public RE {};
class Ch : public RE {
 private:
  char c;
 public:
  Ch (char _c) { c = _c; }
};
class Alt : public RE {
 private:
  RE* r1;
  RE* r2;
 public:
  Alt (RE* _r1, RE* _r2) { r1 = _r1; r2 = _r2; }
};
class Conc : public RE {
 private:
  RE* r1;
  RE* r2;
 public:
  Conc (RE* _r1, RE* _r2) { r1 = _r1; r2 = _r2; }
};
class Star : public RE {
 private:
  RE* r;
 public:
  Star (RE* _r) { r = _r; }
};

Z.B. die abgeleitete Klasse Alt repräsentiert die Alternativen zwischen zwei regulären Ausdrücken. Die Alternativen werden als private Instanzvariablen r1 und r2 gespeichert. Beides sind Zeiger weil, wie wir noch sehen werden, wir virtuelle Methoden auf der Basisklassen und den Ableitungen definieren werden. Der Alt Konstruktor bekommt als Argument zwei reguläre Ausdrücke in C++ Repräsentation und initialisiert die Instanzvariablen.

Standard Methoden auf Regulären Ausdrücken

class RE {
 public:
  virtual REType ofType()=0;
  virtual string pretty()=0;
  virtual bool containsEps()=0;
};

ofType liefert einen enum Wert, der die Art des regulären Ausdrucks kennzeichnet. pretty ist eine “pretty print” Methode, die den regulären Ausdruck in einen String übersetzt. containsEps liefert true falls in der Sprache, die vom dem reguläre Ausdruck beschrieben wird, sich der leere String befindet.

Obige virtuelle Methoden sind schon für die abgeleiteten Klassen definiert. Zur Lösung der Aufgaben dürfen Sie weitere (virtuelle) Methoden zur Klasse RE hinzufügen.

Als Beispiel der Definition der virtuellen Methoden, betrachten wir die abgeleitete Klasse Alt.

enum REType {
  PhiType, EpsType, ChType,
  AltType, ConcType, StarType };

class Alt : public RE {
 private:
  RE* r1;
  RE* r2;
 public:
  Alt (RE* _r1, RE* _r2) { r1 = _r1; r2 = _r2; }
  REType ofType() { return AltType; }
  string pretty() {
    string s("(");
    s.append(r1->pretty());
    s.append("+");
    s.append(r2->pretty());
    s.append(")");
    return s;
  }
  bool containsEps() {
    return (r1->containsEps() || r2->containsEps());
  }
};