Algorithmen & Datenstrukturen
Programmieren 1


von Prof. Jürgen Plate

1.8 Datenstrukturen

1.8.1 Datenorientierte Programmentwicklung

In der kommerziellen Datenverarbeitung treten sehr oft Problemstellungen auf, bei denen es weniger auf die Algorithmen ankommt (weil diese sehr einfach sind), sondern auf die Umformung der gegebenen Daten. So gibt es zum Beispiel Listengeneratoren; das sind Programme, die Listen erzeugen, also nichts anderes tun als Daten, die bereits bekannt sind, in eine übersichtliche Form zu bringen. Für die Aufgabenstellung ist der Algorithmus selbst von geringer Bedeutung. Hier kommt es in erster Linie auf die Ein- und Ausgabedaten sowie deren Umformung an. So hat sich neben der problemorientierten Programmentwicklung die datenorientierte Programmentwicklung herausgebildet. Hier wird zuerst die Datenstruktur für jede zu verarbeitende Datenmenge definiert. Danach stellt man fest, welche Arten der Zuordnung existieren. Dabei sollen

unterschieden werden. Dann werden alle Einzeloperationen in ungeordneter Reihenfolge aufnotiert und anschließend jede Operation den Datenstrukturdiagrammen und den daraus entwickelten Programmstrukturen zugeordnet. Dieses Entwurfsprinzip ist aber ausschließlich für umformende Problemstellungen geeignet.

Wichtig für die allgemeinen Probleme ist, daß die Eingabe- und Ausgabedaten eines Programms genau analysiert und strukturiert werden. Das führt meist auch zu kürzeren und übersichtlicheren Programmen. Bei der Datenanalyse können Sie folgendermaßen vorgehen:

Es hat sich auch beim Entwurf von Programmiersprachen schnell herausgestellt, die zu verarbeitenden Daten nach ihrer Art, ihrem Typ, zu unterscheiden. In strukturierten Sprachen ist es üblich, alle verwendeten Variablen am Anfang eines Programmes summarisch aufzuführen. Das trägt zu dessen Verständlichkeit und Leserlichkeit wesentlich bei. Insbesondere gehört zu einer guten Dokumentation die explizite Angabe des Wertebereiches einer jeden Variablen. Die wichtigsten Gründe dafür sind die folgenden:

  1. Die Kenntnis des Wertebereiches einer Variablen ist entscheidend für das Verständnis eines Algorithmus. Ohne explizite Angabe des Wertebereiches ist es meistens schwierig, festzustellen, welche Art von Objekten eine Variable repräsentiert, und die Ermittlung möglicher Fehler wird erheblich erschwert.
  2. Die Zweckmäßigkeit und die Korrektheit eines Programms sind in den meisten Fällen abhängig von den Anfangswerten der Argumente, und sie sind nur für bestimmte Bereiche garantiert. Daher gehört es zur Dokumentation eines Algorithmus, daß diese Bereiche explizit aufgeführt sind.
  3. Der Speicherbedarf für die Repräsentation einer Variablen im Speicher eines Computers hängt von deren Wertebereich ab. Damit ein Compiler die nötigen Speicherzuordnungen vornehmen kann, ist die Kenntnis der Wertebereiche unerläßlich.
  4. Operatoren, die in Ausdrücken vorkommen, sind nur für gewisse Wertebereiche ihrer Argumente wohldefiniert. Ein Compiler kann auf Grund der angegebenen Wertebereiche prüfen, ob die vorkommenden Kombinationen von Operatoren und Operanden zulässig sind. Die Angabe der Wertebereiche der Variablen dient also als Redundanz zur Überprüfung des Programms während seiner Übersetzung.
  5. Die Realisierung von Operatoren in Rechenanlagen hängt unter Umständen von den Wertebereichen der Operanden ab. Ihre Kenntnis ist daher oft zu einer zweckmäßigen und effizienten Realisierung unerläßlich. So werden z. B. in den meisten Rechenanlagen verschiedene interne Darstellungsarten für ganze und für reelle Zahlen verwendet, und die detaillierten Abläufe von arithmetischen Operationen unterscheiden sich stark für die beiden Darstellungsweisen.
  6. Eine automatische Prüfung von Grenzverletzungen während das Programm abläuft durch das Laufzeitsystem ist möglich --> sichere Programme (auf Kosten der Geschwindigkeit).

1.8.2 Datentypen

An dieser Stelle wird nur allgemain auf Datentypen sowie deren Bedeutung und Eigenschaften eingegangen, wobei aber teilweise schon die Notation der Sprache C verwendet wird. In einem späteren Kapitel werden die Besonderheiten der Datentypen in C ausführlicher behandelt.

Der Wertebereich einer Variablen spielt eine derart wichtige Rolle in der Charakterisierung einer Variablen, daß er als deren Typ bezeichnet wird. Die Werte eines Bereichs werden als Konstanten von diesem Typ bezeichnet. Es wird daher die bindende Konvention eingeführt, daß in jedem Programm alle Variablen vereinbart werden. Dies geschieht durch Angabe einer Liste der gewählten Variablen-Bezeichnungen und deren Typen. Eine Variablen-Vereinbarung habe allgemein die Form

TYP variable

wobei "variable" eine Variablen-Bezeichnung und "TYP" der Typ der Variablen ist. Falls mehrere Variablen vom gleichen Typ vereinbart werden sollen, wird die Kurzform

TYP v1, v2 ,..., vn (n > 1)

verwendet, wobei v1 ... vn Variablenbezeichnungen sind und TYP wiederum entweder eine Typenbezeichnung oder eine Typenbeschreibung ist. Die Konvention, alle verwendeten Bezeichnungen am Anfang eines Programms zu vereinbaren, hat zudem den großen Vorteil, daß ein Compiler bei jeder im Programm vorkommenden Bezeichnung prüfen kann, ob sie überhaupt vereinbart ist. Im negativen Fall, der z. B. durch Schreibfehler verursacht wird, kann der Compiler durch eine entsprechende Fehlermeldung auf den Lapsus aufmerksam machen. Die zusätzliche Redundanz wird also wiederum zur Erhöhung der Programmiersicherheit ausgenutzt. Wie werden Datentypen in einem Programm eingeführt, und welche Wertbereiche können durch Computer zweckmäßig dargestellt werden? Vorerst sei bemerkt, daß es üblich ist, Datentypen in verschiedene Arten einzuteilen. Das wesentliche Merkmal eines Typs ist die Struktur seiner Werte. Ist ein Wert unstrukturiert, also nicht in einzelne Komponenten zerlegbar, so wird er - und damit auch sein Typ - als skalar bezeichnet. Ist er dagegen in einzelne Komponenten zerlegbar, nennt man ihn strukturiert.

Konstante

Konstante sind Datenwerte, die direkt in der Anweisungsfolge eines Programms eingetragen werden können (Standardbezeichnung, z. B. Zahlen). Als Konstante bezeichnet man üblicherweise auch Namen für Datenwerte (frei wählbare Bezeichnung). Durch die Vereinbarung von Konstanten-Namen wird ein ganz bestimmter Datenwert mit einem Namen versehen und ist über diesen Namen jederzeit zugreifbar. Der Wert einer Konstanten kann nicht geändert werden. Konstante dienen der Übersichtlichkeit und Lesbarkeit von Programmen; z. B.: 

Pi = 3,1415 
Maximum = 10000 
Autor = "Johann Wolfgang von Goethe"

Bei der Programmiersprache C findet man zwei Varianten der Konstantenvereinbarungen: 

const float Pi = 3.1415
#define Pi 3.1415

Die erste Form entspricht dem aktuellen ANSI-Standard und ist zu bevorzugen. Die zweite Variante ist älter und definiert eigentlich nur ein Makro. Vor der eigentlichen Übersetzung wird im gesamten Text die Zeichenkette "Pi" durch "3.1415" ersetzt.

Variablen

Anstelle der behandelten Datengrößen werden im Programm Namen eingesetzt, die als variable Größen oder kurz als "Variablen" bezeichnet werden. Jede Variable besitzt also einen Namen und einen Wert. Sie stellt somit einen "Behälter" für ihren Wert dar. Der Compiler reserviert entsprechend dem Typ eine bestimmte Menge Speicherplatz für den "Behälter". Die Variable kann als Benennung von einem oder mehreren Speicherworten aufgefaßt werden.

In C gibt es zwei verschiedene Arten von Vereinbarungen, Definitionen und Deklarationen.Der Begriff der Vereinbarung umfasst sowohl die Definition als auch die Deklaration.

Definitionen

Deklarationen legen nur die Art der Variablen bzw. die Schnittstelle der Funktionen, d. h. die Funktionsköpfe, fest. Während Definitionen von Variablen und Funktionen dazu dienen, Datenobjekte bzw. Funktionen im Speicher anzulegen, machen Deklarationen Datenobjekte bzw. Funktionen bekannt, die in anderen Übersetzungseinheiten definiert werden oder in derselben Übersetzungseinheit erst nach ihrer Verwendung definiert werden.

Eine Deklaration umfasst stets den Namen eines Objektes und seinen Typ. Damit weiß der Compiler, mit welchem Typ er einen Namen verbinden muß. Kurz ausgedrückt:

Definition = Deklaration + Reservierung des Speicherplatzes

Die Zuweisung eines Wertes an eine Variable ist eine fundamentale Operation in Computerprogrammen. Eine Variable zeigt eine Verhaltensweise, die einer Wandtafel ähnlich ist: Sie kann jederzeit gelesen werden (sie liefert den Wert) andererseits ausgewischt und überschrieben werden. In fast allen höheren Programmiersprachen müssen Variablen vor ihrer Verwendung deklariert werden - so auch in C. Es wird dabei der Typ der Variablen (siehe unten: Datentypen) und ein Bezeichner angegeben. Z. B.: 

int Anzahl, Summe, I, J;
float DM_Betrag;

Die Zuweisung eines Wertes an eine Variable wird im allgemeinen durch das Operatorzeichen = bezeichnet (zur Unterscheidung vom Gleichheitszeichen verwenden manche Programmiersprachen auch einen Linkspfeil oder ":="):

Wichtig ist die Unterscheidung zwischen Wertzuweisung und Gleichung im mathematischen Sinn. So würde die mathematische Gleichung

X = X + 1

wenig Sinn machen (es gibt nämlich keine Lösung), in einer Programmiersprache bedeutet der Ausdruck jedoch "Addiere 1 zum Wert von X und speichere das Ergebnis wieder in X" oder kürzer "Erhöhe X um 1". Noch ein Beispiel:

In C ist eine Wertzuweisung auch bei der Definition erlaubt. Es handelt sich um ein sehr sinnvolles Feature, denn eine Variable besitzt nach der Deklaration noch keinen definierten Wert. Nicht initialisierte Variablen (d. h. Variablen ohne Anfangswert) sind oft die Ursache von Programmfehlern. Beispiel: 

int I = 0, Anzahl = 111;
float X = 0.0;
Merke: Steht die Variable auf der rechten Seite einer Zuweisung, bezeichnet sie ihren Inhalt. Steht die Variable auf der linken Seite einer Zuweisung bezeichnet Sie einen Behälter.

Ausdrücke

Ein Ausdruck (engl. Expression) ist eine Formel (eine Rechenregel), die stets einen (Resultat-)Wert liefert. Der Ausdruck besteht aus Operanden (Konstante, Variablen und Funktionen) und Operatoren. Operatoren werden üblicherweise eingeteilt in

Sofern Ausdrücke mit mehr als einem Operator vorkommen, ist die Reihenfolge ihrer Ausführung eindeutig festzulegen. Dies kann durch drei Möglichkeiten erfolgen:

Die Hierarchie nimmt in der oben aufgeführten Liste von oben nach unten zu, d. h. Klammern binden stärker als Vorrangregeln und diese stärker als die Reihenfolge. Der Begriff "Ausdruck" beschränkt sich nicht auf arithmetische Ausdrücke (z. B. a * y + b), es gibt auch logische oder mengentheoretische Ausdrücke oder Ausdrücke, die Zeichen, Zeichenfolgen oder Speicheradressen zum Ergebnis haben.

Ausdrücke und Anweisungen

Anweisungen und Ausdrücke sind nicht das Gleiche. Sie unterscheiden sich durch den Rückgabewert: Was ist aber nun genau der Rückgabewert? Das soll anhand des Ausdrucks 13 + 16.5 erklärt werden. Durch die Anwendung des Additionsoperators + auf seine Operanden 13 und 16.5 ist der Rückgabewert des Ausdrucks eindeutig festgelegt. Aus den Typen der Operanden ergibt sich auch der Typ des Rückgabewertes. Werden wie in diesem Beispiel unterschiedliche Datentypen in einem Ausdruck verwendet, führt der Compiler eine sogenannte implizite Typumwandlung nach vorgegebenen Regeln durch. Als erstes prüft der Compiler die Typen der Operanden. Der eine Operand ist vom Typ int, der andere vom Typ float. Damit ist eine Addition zunächst nicht möglich. Es muß zuerst vom Compiler eine für den Programmierer unsichtbare sogenannte implizite Typumwandlung der Zahl 13 in den Typ float (also zu 13.0) durchgeführt werden. Erst dann ist die Addition möglich. Der Rückgabewert der Addition ist die Zahl 19.5 vom Typ float. Jeder Rückgabewert hat also auch einen Typ.

In C gibt es

Die ersten drei Anweisungen werden im Kapitel 2 ausführlich behandelt, auf die letze Form wird hier eingegangen.In C kann man durch Anhängen eines Semikolons an einen Ausdruck erreichen, daß dieser zu einer Anweisung wird. Man spricht dann von einer sogenannten "Ausdrucksanweisung". In einer solchen Ausdrucksanweisung wird der Rückgabewert eines Ausdruckes nicht verwendet. Lediglich wenn Seiteneffekte zum Tragen kommen, ist eine Ausdrucksanweisung sinnvoll. Dazu ein Beispiel: 
int i = 0;            /* Zuweisung eines Anfangswertes an die Variable    */

5 * 5;                /* zulaessig, aber nicht besonders sinnvoll         */
                      /* Der Rueckgabewert von 5 * 5 wird nicht verwendet */

i++;                  /* Sinnvoll - i wird um 1 erhoeht (siehe spaeter)   */
Generell gilt:

In C kann jeder Ausdruck eine Anweisung werden und einen Rückgabewert haben.

Bezeichner

Wie haben gesehen, daß man Konstante und Variablen mit frei wählbaren Bezeichnungen (Namen) versehen kann. Daneben gibt es in jeder Programmiersprache noch Bezeichner für Unterprogramme (Prozeduren und Funktionen, siehe später) und sogenannte Standardbezeichner, welche die Schlüsselworte (reserved Words) der Programmiersprache und vordefinierte Unterprogramme (Standardfunktionen, Standardprozeduren) benennen und die in der Regel nicht anderweit verwendet werden dürfen.

L-Werte und R-Werte

Ausdrücke habe eine unterschiedliche Bedeutung, je nachdem, ob sie links oder rechts vom Zuweisungsoperator stehen. Wie schon erwähnt steht beim Ausdruck a = b die rechte Seite für einen Wert, während der Ausdruck auf der linken Seite die Stelle angibt, an der der Wert zu speichern ist. Wenn wir das Beispiel noch etwas modifizieren, wird der Unterschied noch deutlicher: 
a = a + 5*c
Beim Namen a ist rechts vom Zuweisungsoperator der Wert gemeint, der in der Speicherzelle a gespeichert ist, und links ist die Adresse der Speicherzelle a gemeint, in der der Wert des Gesamtausdrucks auf der rechten Seite gespeichert werden soll. Aus dieser Stellung links oder rechts des Zuweisungsoperators wurden auch die Begriffe L-Wert und R-Wert abgeleitet.

Ein Ausdruck stellt einen L-Wert ("lvalue" oder "left value") dar, wenn er sich auf ein Speicherobjekt bezieht. Ein solcher Ausdruck kann links und rechts des Zuweisungsoperators stehen.

Ein Ausdruck, der keinen L-Wert darstellt, stellt einen R-Wert ("rvalue" oder "right value") dar. Er darf nur rechts des Zuweisungsoperators stehen. Einem R-Wert kann man also nichts zuweisen.

Es gilt:

1.8.3 skalare Standardtypen

Wie schon erwähnt, ist die summarische Auflistung der Variablen und Konstanten wichtig für die Verständlichkeit des Programms. Insbesondere gehört zu einer guten Dokumentation die explizite Angabe des Wertebereichs. Nachfolgend werden vier äußerst häufige Standardtypen definiert, die in jedem Datenverarbeitungssystem als bekannt vorausgesetzt werden. Trotzdem sind nicht alle Typen auch in jeder Programmiersprache verfügbar. So kennt C nicht den Typ "Boolean" und Basic kennt nur "Real" und "String". Man kann die fehlenden Typen jedoch in fast allen höheren Programmiersprachen "nachempfinden".

1.8.4 strukturierte Typen

Feld (Array)

Variablen dieses Typs besitzen eine Menge von Komponenten gleichen Typs und haben folgende Eigenschaften:

Wie man sieht, werden die Komponenten der Array-Variablen A mit dem Index I durch A[I] bezeichnet. Anstelle des Indexwertes kann, abhängig von Indextyp, auch ein beliebiger Ausdruck stehen, z. B.: A[i + j].

Zwei Array-Variablen werden als gleich bezeichnet, wenn sie vom selben Typ sind (d. h. identische Vereinbarung besitzen) und alle Komponenten paarweise gleich sind (d. h. A = B, wenn A[i] = B[i] für alle i des Indexbereichs).

Als Komponententyp eines Array kann auch wieder ein Arraytyp verwendet werden --> mehrdimensionale Arrays. Die Vereinbarung wird in den Programmiersprachen zu einer verkürzten Vereinbarung zusammengezogen:

int A [100][50]

Verbund (Record, Structure)

Im Gegensatz zu Array besitzen Verbunde Komponenten unterschiedlichen Typs und stellen damit die flexibelste Datenstruktur dar. Ein Record besteht aus einer festen Anzahl von Komponenten, wobei jede Komponente mit einem eigenen Namen bezeichnet wird, die Vereinbahrung stellt sich damit folgendermaßen dar: 
struct Recordbezeichner
   {
   Komponententyp Komponentenbezeichner;
   Komponententyp Komponentenbezeichner;
   Komponententyp Komponentenbezeichner;
   Komponententyp Komponentenbezeichner;
   };
Man kann nach der schließenden Klammer auch gleich noch eine Variable deklarieren. Beispiele: 
struct Kundensatz
   {
   int Kundennummer;
   char Name[20];
   char Vorname [20];
   float Umsatz;
   } Kunde;

struct Datumstyp
   {
   int Tag;
   int Monat;
   int Jahr;
   } Datum;
Deklarier man die Variablen getrennt von der Record-Definition, sieht das so aus: 
sruct Recordbezeichner Variablenbezeichner;
Als Record-Komponenten können wieder beliebige Datentypen stehen, also auch wieder Array- oder Recordtypen. Umgekehrt kann auch ein Array Records als Komponenten besitzen (z. B. ein Array mit Komponenten vom oben gezeigten Kundentyp).

Auf einzelne Komponenten des Records wird über die Kombination des Recordnamens und der gewünschten Recordkomponente zugegriffen. Als Trennzeichen zwischen den Namen wird ein Punkt verwendet (hier gibt es Unterschiede bei den einzelnen Programmiersprachen), z. B.:

Datum.Tag oder Kunde.Name

Auch hier kann - je nach Aufbau des Records - eine mehrstufige Referenz notwendig sein.

1.8.5 Dateien

Alle bisher betrachteten Datentypen haben sich dadurch ausgezeichnet, daß der Wert einer Variablen durch ihren Namen referenziert wurde und die Zahl der Komponenten bei der Vereinbarung festgelegt wurde. Es stellt sich die Frage, welcher Datentyp verwendet werden soll, wenn die Zahl der Komponenten nicht von Anfang an festliegt. Ein zweiter Aspekt ist die Ein-/Ausgabe. Die bisher behandelten Variablen liegen im Arbeitsspeicher. Es muß also eine Möglichkeit zur permanenten Speicherung von Daten ausserhalb des Hauptspeichers geboten werden - und zur Ein-/Ausgabe über beliebige Geräte.

Dateien sind ein allgemeines Konzept für die permanente Speicherung bzw. Ein-/Ausgabe. Dateien bestehen aus beliebig vielen Komponenten eines bestimmten Datentyps. Je nach Dateiart können die einzelnen Komponenten sequentiell oder wahlfrei gelesen werden. Am Ende einer Datei können weitere Komponenten hinzugefügt werden. Die Abbildung der abstrakten Dateistruktur auf reale Speichergeräte (Platte, Band, Drucker, etc.) erfolgt durch das Betriebssystem.

Eine Datei besitzt also lauter Komponenten gleichen Typs. Zusammen mit der Dateivariable wird implizit auch ein Pufferbereich im Arbeitsspeicher definiert, der mindestens eine Dateikomponente (--> aktueller Wert) aufnehmen kann. Auf diesen Datenwert wird dann über die Dateivariable zugegriffen. Zusammen mit dem Typ "Datei" müssen einige Standardoperationen definiert sein, die den Zugriff auf die Datei erlauben:

Nach Art des Zugriffs auf die Komponenten wird unterschieden in sequentielle Dateien und Dateien mit wahlfreiem Zugriff.

Textdateien

Dateien, dessen Komponenten Schriftzeichen sind (Typ Character), nehmen eine Schlüsselrolle ein, da die Eingabe- und Ausgabedaten der meisten Computerprogramme Textfiles sind (darunter fällt beispielsweise auch die Druckausgabe). Ein Programm kann vielfach allgemein als eine Datentransformation von einer Textdatei in eine andere aufgefaßt werden (z. B. höhere Sprache --> Assembler).

Nun sind Texte i. a. in Zeilen unterteilt, und es stellt sich die Frage, wie diese Zeilenstruktur auszudrücken ist. In der Regel enthält der in einem DVS verwendete Zeichencode spezielle Steuerzeichen, von denen eines als Zeilenende-Zeichen verwendet werden kann. Bedauerlicherweise verhindert die Realisierung von Textdateien auf Betriebssystemebene eine einfache Realisierung der Textdatei als "FILE OF Character".

Übersicht Datentypen

Die folgende Übersicht zeigt eine Einordnung der Datentypen nach ihren Eingenschaften. Nicht alle Typen sind in jeder Programmiersprache vorhanden. Einige der Typen werden später besprochen, einige auch gar nicht.

1.9 Softwarequalitätssicherung

Bisher wurde vom Algorithmus, von Datenstrukturen und Programmen gesprochen. Sowohl beim Algorithmus Entwickeln als auch beim Programmieren schleichen sich Fehler ein. Der Softwarebenutzer erwartet aber ein fehlerfreies Produkt. Streckenweise ist dies sogar überlebenswichtig. Beispielsweise dürfen die Avioniksoftware oder auch die Software zur Steuerung von Geräten in der Intensivmedizin keine Fehler aufweisen, deren Auswirkungen in irgendeiner Weise ein Menschenleben gefährden können. Ziel einer jeden Softwareentwicklung muß es demnach sein, ein 'möglichst' fehlerfreies Produkt zu erstellen. Fehlerfreiheit ist aber nur ein Qualitätsaspekt. Vor allem müssen auch die dem Nutzer zugesicherten Produkteigenschaften vorhanden sein usw.. Allgemein läßt sich eine sogenannte Softwarequalität definieren:

Wichtig ist daß die Erfüllung der o.g. Erfordernisse quantitativ beschreibbar vorgegeben und somit objektiv überpüfbar ist. Gebräuchlich sind hier sechs Qualitätsmerkmale die in der Softwarebeurteilung zum Tragen kommen:

  1. Funktionalität
  2. Zuverlässigkeit
  3. Benutzbarkeit
  4. Effizienz
  5. Änderbarkeit
  6. Übertragbarkeit

Für jedes dieser Merkmale existieren unterschiedliche Maßstäbe und Verfahren um eine quantitative Erfüllung zu überprüfen. Jede Abweichung vom gewünschten Ergebnis ist ein Fehler. Ideal wäre es Fehler zu vermeiden bevor sie entstehen. Prävention ist eine Strategie die sich auszahlt: Betrachten wir einmal wo Fehler entstehen, wenn man den Bogen von der Anforderungsdefinition bis hin zum Test und Integration hin spannt und wie sich diese auswirken:

(entnommen aus "Lehrbuch der Software-Technik" von Helmut Balzert)

Das wichtigste ist also mit dem Kunden, dem Softwarenutzer, zu reden und die Anforderungen möglichst genau und widerspruchsfrei zu erfassen. Aber wie findet man nun die Fehler, die man vermeiden möchte?

Hier gibt es verschiedene Strategien. Zum Einen kann man durch Vorgaben, wie z.B. Programmierrichtlinien, Checklisten und den Einsatz von entsprechenden Werkzeugen, Programmiersprachen und Methoden im Vorfeld den Rahmen für den einzelnen Softwareentwickler festlegen (sog. konstruktives Qualitätsmanagement) . Gewisse Tricks in der Programmierung werden untersagt, die Art und der Umfang der Kommentierung des Quellcodes vorgegeben und eine Programmiersprache gewählt, die passend zur zu lösenden Aufgabe ist und dem Ausbildungsstand der beteiligten Programmierer entsprechen.

Zum Anderen prüft man mittels Tests ob das was Geschaffen wurde mit dem übereinstimmt was vorgegeben war (sog. analytisches Qualitätsmanagement). Was Vorgegeben ist richtet sich nach der Phase in der Softwareentwicklung in der man sich befindet. Wie getestet werden kann richtet sich nach den Möglichkeiten und dem Aufwand den man investieren möchte. Welche Arten von Tests gibt es eigentlich?

1.9.1 Testen von Software

In den vorangegangenen Abschnitten war vom Algorithmus die Rede, der die Computer-programmierbare Lösung einer Aufgabe darstellt. Aufgabe eines Tests wäre es zu zeigen ob ein gefundener und fertig formulierter Algorithmus auch das leistet was in der Aufgabenforderung formuliert wurde. Eine einfache Vorgehensweisen hierfür ist der Schreibtischtest:

Schreibtischtest

Der Schreibtischtest simuliert den Einsatz des Algorithmus im 'Kopf'. Anhand einer sinnvollen Auswahl von Eingabedaten wird händisch das richtige Funktionieren des Algorithmus Schritt für Schritt nachvollzogen. Richtig heißt hier, daß in jedem Schritt der Algorithmus das tun muß was der Erfinder eigentlich gewollt hat und natürlich auch die bekannte richtige Ausgabe liefert. Der Schreibtischtest ist heute obligatorisch für jeden Softwareentwickler. Jedes Stück neue Software wird im 'Kopf' in dieser Form getestet, denn jede Teilsoftware hat definierte Eingabedaten und muß in irgendeiner Form bekannte Ausgabedaten erzeugen. Viele Denkfehler werden dabei aufgedeckt und können 'aufwandsarm' beseitigt werden. Aber: Es ist aber auf gar keinen Fall der einzige Test!!

Stillschweigend wurde hier vorausgesetzt, daß sinnvolle Testfälle bekannt sind. Das heißt für einen Satz Eingabedaten ist das Ergebnis, die Ausgabedaten, bekannt. Nur dann kann ein Test auf richtiges/falsches Funktionieren des Algorithmus und seiner Implementierung als Computerprogramm überhaupt durchgeführt werden. In der Regel können auf Grund der Komplexität nicht alle möglichen Variationen der Eingabedaten für Tests verwendet werden. Hat z.B. eine Programmfunktion zwei Eingangsvariable deren jeweiliger Wertebereich 2^64 ist, so wären theoretisch 2^128 unterschiedliche Eingabedaten-Möglichkeiten zu testen. Selbst wenn nur eine Picosekunde für jeden einzelnen Test veranschlagt wäre, so käme man auf knapp 4 * 10^21 Tage Rechenzeit. Damit ist klar, daß nicht alle Fehler durch Tests aufgedeckt werden können. Deshalb ist es nicht verwunderlich, wenn Tests des Softwareentwicklers keine Fehler mehr zu Tage bringen, Tests des Softwareanwenders aber schon. Die sinnvolle Auswahl der Testfälle ist entscheidend. Dazu gibt es unterschiedliche Sichtweisen, was getestet werden soll. Hier zwei Beispiele:

Black-Box Test

Der Black-Box-Test ist ein sog. funktionaler Test. Er betrachtet das Softwaresystem (Algorithmus) als schwarzen Kasten, in den man nicht hineinschauen kann. Der Anwender einer Software ist ein klassischer Black-Box Tester. Er ist nur an den versprochenen Funktionen interessiert, wie die Software intern funktioniert ist ihm egal. Also werden im Black-Box-Test alle vereinbarten Funktionen durch systematische Benutzung mit sinnvollen Testfällen aus Anwendungssicht benutzt. Dies ist in der entsprechenden Spezifikation im Vorhinein niedergelegt. Der Black-Box-Test ist der klassische Abnahmetest. Der Kunde, der Software kauft, testet sie nach der Lieferung, oftmals im Beisein des Entwicklers, und wenn sie aus seiner Sicht funktioniert muß er sie bezahlen. Auch in der Entwickung selbst wird dieses Verfahren häufig eingesetzt. Jeder Algorithmus und jede Programmfunktion ist i.d.R. schriftlich spezifiziert, d.h. es ist festgelegt was sie unter welchen Umständen wie können muß. Somit testet der Entwickler sein Programm gegen die Spezifikation mit daraus abgeleiteten Testfällen.

Problematisch beim Black-Box-Testverfahren ist die sogenannte Testüberdeckung. Die Internas des Programms werden nicht berücksichtigt. So kann es vorkommen, daß gewisse Programmteile, wie Schleifen oder Abfragen, bei solchen Tests nie oder immer mit 'harmlosen' Daten durchlaufen werden. Sinnvolle Testfälle, die sich nicht aus der Verwendung, sondern einzig aus dem Aufbau und der Formulierung des Programms ergeben, werden beim Black-Box-Test nicht systematisch durchgeführt. Die Konsequenz: unendeckte Fehler.

Um dies zu vermeiden gibt es das Prinzip des wesentlich aufwendigeren White-Box-Tests.

White-Box-Test

Ausgehend vom Programmquelltext werden im White-Box-Test der Kontrollfluß des Programms untersucht und Testfälle daraus abgeleitet. Der Kontrollfluß ist der Weg durch das Programm den dessen Ausführung durch den Rechner nimmt. Alle möglichen Wege mit allen möglichen Datenkombinationen zu testen ist i.d.R. zu aufwendig.

Eine Variante des White-Box-Tests sieht vor, daß die Testfälle so generiert werden, daß zumindest alle Programmanweisungen mindestens einmal durchlaufen werden. Dieser wird Anweisungsüberdeckungtest oder auch Co -Test genannt.

Durch Verzweigungen im Programm kann eine Anweisung auf mehreren Wegen erreicht werden. Der Anweisungsüberdeckungstest nimmt hier keine Rücksicht. Hauptsache jede Anweisung ist einmal durchlaufen:

(entnommen aus "Lehrbuch der Software-Technik" von Helmut Balzert)

Im Bild steht jeder Kreis für eine Anweisung des in der Bildmitte aufgeschriebenen C++-Programms und jeder Pfeil für einen möglichen Pfad den das Programm während seiner Ausführung nehmen kann. Diese Art der Graphik nennt man Kontrollflußgraph. Wie links im Bild zu erkennen ist wird bei einem Anweisungsüberdeckungstest von n-Start bin n-Final jede Anweisung n1 - n6 durchlaufen aber nicht unbedingt jeder Pfeil.

Beim sog. Zweigüberdeckungtest, auch C1-Test genannt, werden Testfälle so konstruiert, daß alle Zweige durchlaufen werden. Dieser ist einsichtig aufwendiger als der Anweisungsüberdeckungstest. Aber selbst dieser reicht nicht aus um alle Fälle abzudecken.

Schleifen (while..) und datenabhängige Verzweigungen (if..else..) führen zu unterschiedlichen Wegen durch das Programm, diese werden Pfade genannt. Die Kombination der beschrittenen Zweige, im Bild von oben nach unten betrachtet, hat unterschiedliche Auswirkungen und kann somit Fehlerquelle sein. Dieses berücksichtigen die sehr aufwendigen Pfadüberdeckungtests. Selbst hier ist noch nicht alles getan. Die datenabhängigen Verzweigungen haben meist komplexe Entscheidungsbedingungen:

if (A && B || C ) {...} else { ...}

Das Ergebnis True/False der Bedingung A && B || C hängt von den Ergebnissen der Bewertung der Teilausdrücke A, B, C ab. Eigentlich müßten für alle möglichen Wertekombinationen diese Teilausdrücke die Verzweigung getestet werden. Im Pfadüberdeckungstest wird hierauf nicht Rücksicht genommen. Erst der sog. Bedingungsüberdeckungstest kümmert sich darum.

Betrachtet man nun noch die möglichen Daten die ein Programm erzeugt und die es eingespeist bekommt, so finden noch die sogenannten datenflußorientierten Testverfahren Anwendung. Statt nur den Kontrollfluß zu betrachten wird hier der Datenfluß mit den möglichen Werten und Wertebereichen der einzelnen Variablen im Programm untersucht.

In der Praxis wird man sich für einen sinnvollen realisierbaren Mix aus den vorgestellten White-Box-Testverfahren und dem Black-Box-Testverfahren entscheiden.

Bei der Auswahl der Testdaten kann man sich von folgenden Gesichtspunkten leiten lassen:

1.9.2 Verifikation von Software

Testen von Software führt i.d.R. nicht zu fehlerfreier Software, da nicht alles getestet wird. Das Gebiet der Verifikation von Software nimmt für sich in Anspruch den quasi allgemeinen mathematischen Beweis anzutreten, daß ein gegebenes Programm korrekt (fehlerfrei) ist und für alle zu bearbeitenden Eingabedaten fehlerfrei funktioniert. Damit braucht man nicht mehr zu testen. Die Aufwand liegt darin, zu definieren was korrekt ist. Dazu ein Beipiel aus dem "Lehrbuch der Software-Technik":

Es soll ein Programm geschrieben werden, daß aus einer beliebigen reelen Zahl A und einer positiven ganzen Zahl B die Potenz AB ermittelt. Ein Programm das dieses Problem löst, ist dann korrekt, wenn folgende Beziehungen gelten:

Alle zulässigen Eingabewerte für die Basis werden durch A und für den Exponenten durch B dargestellt. Im Gegensatz zum Testen werden hier keine konkreten Werte wie z. B. A = 3.14 und B = 5 angenommen. Die in der Graphik als Anfangs- und Endebedingung gekennzeichneten Stellen werden als Zusicherungen (Assertions) bezeichnet. Das im nachstehenden Bild gezeigte Programm Potenzieren löst das Problem auf Grund folgender mathematischer Zusammenhänge:

Die Anfangs- und Endebedingung kann sofort hingeschrieben werden. Nun sind alle Anweisungen und Pfade des Programmablaufplans durchzugehen und zu zeigen, daß man aus der Anfangsbedingung durch das Programm die Endebedingung erhält. Die Schleife möge man sich vorläufig als aufgeschnitten denken. Die an der Stelle (2) gegebene Zusicherung ist der Angelpunkt des ganzen Verfahrens. Diese muß zunächst intuitiv gefunden werden und in geeigneter Weise formuliert werden. Ausgehend von dieser Behauptung (2) können nun weitere Zusicherungen abgeleitet werden. Zusicherung (3) ergibt sich aus (2), da Exponent = 0 ist und Basis0 = 1 gilt. (4) folgt unmittelbar aus (2). Um (7) aus (5) abzuleiten, wird (5) in die äquivalente Form (6) umgeschrieben. Durch Ersetzen in (6) von Ergebnis * Basis durch Ergebnis und Exponent-1 durch Exponent ergibt sich dann (7). Der Exponent muß in (7) gerade sein! (8) ist interessanterweise identisch zu (7). (7)/(8) kann in (9) umgeformt werden ( (x*x)(y/2) = x(2*y/2) = xy ). Durch Ersetzen von Exponent/2 durch Exponent und Basis * Basis durch Basis in (9) erhält man (10). Danach ist in (10) der Exponent gerade oder ungerade aber größer gleich Null. Schließt man nun die Rückwärtsschleife von (10) nach (2), so sieht man die Übereinstimmung der Zusicherungen (10) und (2). Damit ist die Schleife widerspruchsfrei geschlossen.

Die Zusicherung (2) gilt offenbar für den ersten Durchlauf der Schleife, da mit Ergebnis = 1 , mit Basis = A und Exponent = B der Ausdruck Ergebnis*BasisExponent = AB wahr ist. Aufgrund des geführten Beweises gilt die Zusicherung auch für den zweiten Durchlauf und allen folgenden Durchläufen. Damit ist bewiesen, daß das Programm tatsächlich AB liefert, wenn es das Ende erreicht.

Wird jetzt noch nachgewiesen (nicht hier!) daß das Programm auch nach endlich vielen Wiederholungen aufhört (terminiert), so ist die Korrektheit des Programms formal bewiesen und es sind keine Tests nötig.

Der Aufwand den Verifikationsweg zu beschreiten ist enorm und wird in ausgesuchten Situationen beschritten. Es gibt abgewandelte Verfahren w.z.B. das symbolische Testen die öfter in der Praxis eingesetzt werden. Das Fehlerfinden mittles Testens mittels Testfälle ist das bisher am häufigsten eingesetzte Verfahren.

Auf die Möglichkeit von Zusicherungen zum Programmtest wird im folgenden Kapitel nochmals sprachbezogen eingegangen.

1.9.3 Testplanung und Testdokumentation

In der Praxis wird zwar getestet, aber oftmals ziel- und planlos. Sollte doch getestet worden sein, so meistens ohne Protokoll. Treten später Fehler auf, so kann der Entwickler nicht lernen warum der Fehler bis zum Auftreten unentdeckt blieb. Deshalb ist es wichtig einen Testplan zu erstellen, in dem -im einfachsten Fall- alle durchzuführenden Tests aufgeschrieben stehen. Jede Einzeltestbeschreibung nennt hier den Testgrund, eine Durchführungsanweisung, die Eingangsdatenbelegung und das zu erwartende Ergebnis im fehlerfreien Fall. Das zu führende Testprotokoll verzeichnet neben Verweis auf Testfall im Testplan, Zeitangaben, Angabe der Testperson das Ergebnis des Tests.

Damit ist es möglich nachzuvollziehen was getan und getestet wurde. Idealerweise setzt man heute Testwerkzeuge ein, die es gestatten Tests aufzuzeichnen und beliebig oft automatisch zu wiederholen. Diese Feature ist dann besonders gefragt wenn die Software erweitert wird und damit wieder vollständig getestet werden muß. Manuell wäre das sehr aufwendig bei großen Softwaresystemen.

Ist beim Testen ein Fehler erkannt worden, geht es an seine Lokalisierung und sodann an die Therapie. Typische Fehler:

Die überprüfung eines Programms auf Erfüllung seiner Spezifikation kann also nach zwei verschiedenen Methoden erfolgen:

  1. Formale Methode (Korrektheitsbeweis). Mittels logischer Herleitungen wird die Einhaltung der Bedingungen an die Zwischen- und Endergebnisse des Programms nachgewiesen.
  2. Empirische Methode (Testen). Mit bestimmten ausgesuchten Daten, für die das Ergebnis bekannt ist, wird das Programm ausprobiert. Dabei kann nur das Vorhandensein von Fehlern, nicht die Fehlerfreiheit nachgewiesen werden.

Zusammenfassung: Der Weg zum Programm

  1. Intuitives, schrittweises Entwickeln des Algorithmus, jedoch keine exakte Formalisierung der Darstellung und überwiegend nicht mathematische Problemstellungen.
  2. Einführen formalisierter Darstellungen und mathematischer Formeln.
  3. Darstellung in Struktogrammen. Gliederung in Module und Unterprogramme.
  4. Entwickeln der Algorithmen bis zu einer rein formalen Stufe (höhere Programmiersprache).
  5. Codieren. Gegebenenfalls Umsetzen in Assemblersprache.

Beispiel: Algorithmus für die Lösung einer quadratischen Gleichung

Definition des Problems:

Ermittle die Lösung einer quadratischen Gleichung der Form

A*X2 + B*X + C = 0

Formalisieren des Problems:

Struktogramm:

Anmerkungen zum Struktogramm:

Programm in C-Notation:

Die Sprachelemente von C werden erst in den kommenden Kapiteln behandelt. Daher soll Ihnen diese Auflistung nur einen Vorgeschmack bieten. 
/* Quadratische Gleichung */

#include <stdio.h> 
#include <math.h> 

void main(void)
  {
  float a, b, c, d, xl, x2;          /* Variablenvereinbarung */

  printf("Bitte geben Sie die Werte fuer a, b und c ein: ");
  scanf("%f %f %f", &a, &b, &c);     /* Einlesen der Parameter */
  if (a == 0.0) 
    {                                /* Lineare Gleichung */
    if (b != 0.0)
      {
      x1 = -c/b;
      printf("Lineare Gleichung: x = %f \n", x1);
      }
    else
      { 
      if (a != 0.0)
        printf("Widerspruch!\n"); 
      else
        printf("Allgemeingültig!\n");
      }
    }
  else                               /* Quadratische Gleichung */
    {
    d = b*b - 4*a*c;                 /* Diskriminante berechnen */
    if (d == 0.0) 
      {
      x1 = -b/(2*a);
      printf("eine reelle Lösung x = %f \n", x1);
      }
    else 
      {
      if (d > 0.0)
        {
        x1 = (-b + sqrt(d)/(2*a);
        x2 = (-b - sqrt(d)/(2*a);
        printf("Zwei reelle Lösungen: x1 = %f, x2 = %f \n", x1, x2);
        }
      else /* d < 0 */
        printf("Keine reelle Lösung\n");
      }
    }
  }

Programm-Dokumentation ist wie Sex - ist er gut, dann ist es sehr, sehr gut; ist er schlecht, ist es besser als gar nichts.
Zum Inhaltsverzeichnis Zum nächsten Abschnitt

Copyright © FH München, FB 04, Prof. Jürgen Plate