Übungen zu Algorithmen und Datenstrukturen 1

Übungen zu Algorithmen und Datenstrukturen 1 - Übung 2

1. String Tokenizer

a) Spezifikation korrekt und vollständig?

Die Beschreibung eines Tokens ist für mein Dafürhalten etwas kompliziert und auch nicht korrekt. Nicht "gefolgt von einem Zeichen aus delim" sondern "gefolgt von delim".
Nicht eindeutige Formulierungen wie "soll" bei der Beschreibung des Alg.
Letzter Absatz enthält interne Spezifika des Alg., welche in der Spezifikation nichts zu suchen haben.
Behandlung des Falles - es kommen bestimmte Zeichen aus dem Delimiter in der Zeichenkette vor aber nicht alle - fehlt => erübrigt sich wenn der Token korrekt definiert wird.
Behandlung des Falles Delimiter > Zeichenkette fehlt.
Behandlung von leeren Zeichenketten bzw. Delimiters fehlt.

b) Bessere Spezifikation

Ein "Token" ist eine nicht leere Zeichenkette, welche durch einen "Delimiter" (bspw. ';') begrenzt ist. Dieser Delimiter kann auch aus mehreren Zeichen bestehen.
Der strtock() Algorithmus kann dazu benutzt werden, den String s in einzelne Tokens zu zerlegen. Beim ersten Aufruf von strtok() muss die Zeichenkette s als erstes Argument übergeben werden. Zurückgeg. wird der erste gefunden Token begrenzt mit dem übergebenen Delimiter delim in der Zeichenkette. Sollen weitere Tokens aus der Zeichenkette extrahiert werden, kann der Alg. erneut mit einer leeren Zeichenkette als Argument aufgerufen werden. Der Parameter delim kann bei mehrmaligen Aufrufen mit verschiedenen Werten übergeben werden.
Wird kein Token (mehr) gefunden, wird eine leere Zeichenkette zurückgeg.
Ist der Delimiter delim in der Zeichenkette nicht enthalten, ist die ganze Zeichenkette ein Token und es wird die ganze Zeichenkette zurückgeg.
Sind die Anz. der Zeichen im übergebenen Delimiter delim größer als die Anz. der Zeichen in der Zeichenkette s, wird eine leere Zeichenkette zurückgeg.
Ist der übergebene Delimiter delim leer, wird die ganze Zeichenkette zurückgeg.
Ist die übergebene Zeichenkette s leer, wird eine leere Zeichenkette zurückgeg.

2. Pattern Matching

Spezifikation

Gesucht ist ein Algorithmus

int search(↓char[]
text ↓char[] pattern)

, der eine Zeichenkette pattern in einer anderen Zeichenkette text sucht.
Die Zeichenketten sind Aneinanderreihungen von Zeichen aus dem Zeichensatz ISO-8859-15.
Wird die Zeichenkette pattern in text gefunden, wird die Position von pattern in text zurückgeg. (Pos. des ersten Zeichens in text = 0). Wird sie nicht gefunden, wird -1 zurückgeg.
Ist eine der übergebenen Zeichenketten leer, wird -1 zurückgeg.
Der Algorithmus ist in Jana zu formulieren.