Inhaltsverzeichnis
I Grundlagen der strukturierten Programmierung 5
1 Einleitung 6
1.1 Historie Programmiertechniken 6
1.2 Programmieren lernen 7
1.3 Einfache L osungen sind die besten L osungen 7
2 Algorithmen und Programme 9
2.1 Algorithmen 9
2.2 Darstellungsformen 11
2.3 Freitext 13
2.4 Pseudo-Code 13
2.5 Laufzeiten von Algorithmen 13
3 Einf uhrung in C 14
3.1 Hello World 14
3.2 Programmiersprachen 14
3.3 Operatoren 16
3.4 C-Schl usselw orter (Keywords) 16
3.5 Bezeichner 16
3.6 Kommentare 16
3.7 Programm-Layout 17
3.8 Der Pr aprozessor 18
3.9 Die Standardbibliothek 19
4 Einfache Datentypen 22
4.1 Einf uhrung 22
4.2 Ganze Zahlen 23
4.3 Fließkommazahlen 26
5 Ausdr ucke 28
5.1 Einf uhrung 28
5.2 Operatoren 30
5.3 Funktionen 33
INHALTSVERZEICHNIS
2
5.4 Typisierung 33
5.5 Reihenfolge bei der Berechnung von Ausdr ucken 34
5.6
Ubungen 34
6 Verzweigungen 35
6.1 Einf uhrung 35
6.2 Die einfache Verzweigung (if-else) 36
6.3 Die mehrfache Verzweigung (switch-case) 40
6.4 Der tern are Operator “? :“ 41
6.5 Beispiele 41
6.6 Aufgaben und
Ubungen 45
7 Schleifen 46
7.1 Einf uhrung 46
7.2 Die drei Schleifenarten 46
7.3 Darstellungsarten 47
7.4 Die z ahlergesteuerte Schleife 47
7.5 Die kopfgesteuerte Schleife 52
7.6 Die fußgesteuerte Schleife 54
7.7 Mischformen - Endlosschleife und Spr unge 55
7.8 Tipps zur Schleifenauswahl 56
7.9 Beispiele 57
7.10
Ubungen 66
8 Zeiger 68
8.1 Zeiger 68
8.2 Einf uhrung 68
8.3 Operatoren f ur Zeiger 68
8.4 Hauptspeichermodell 68
9 Modulare Programmierung 70
9.1 Einf uhrung 70
9.2 Die Schnittstelle 72
9.3 Prototypen 73
9.4 G ultigkeitsbereich von Variablen 73
9.5 Globale Variablen 74
9.6 Call-by-value und Call-by-Reference 74
9.7 Module 75
9.8 Beispiele 76
9.9 Aufgaben 81
10 Strukturierte Datentypen 82
10.1 Konstanten 82
INHALTSVERZEICHNIS
3
10.2 Aufz ahlungen 83
10.3 Felder 83
10.4 Zeichenketten (Strings) 85
10.5 Strukturen 88
10.6 Zeiger und Strukturen 89
10.7 Dynamische Felder 89
10.8 Eigene Typen 91
10.9 Beispiele 92
10.10
Ubungen 93
10.11Minesweeper 94
10.12Datums-Check 94
10.13Bin¨ ar-Dezimal-Umwandlung 94
10.14Game of life 94
11 Sortieren 95
11.1 Einf uhrung 95
11.2 Bubble-Sort 95
11.3 Sortieren durch direktes Tauschen 97
11.4 Quicksort 99
11.5 Beispiele 99
II Algorithmen und Datenstrukturen 101
12 Dateiverarbeitung 102
12.1 Einf uhrung 102
12.2
O ffnen und schließen 102
12.3 Dateien mit variabler Satzl ange 105
12.4 Dateinamen als Parameter 106
12.5 Datenaustausch mit Tabellenkalkulationsprogrammen 107
12.6 Beispiele 108
13 Rekursion 111
13.1 Einf uhrung 111
13.2 Einfache Anwendungen 113
13.3 Vor- und Nachteile von Rekursion 115
13.4 Weitere Anwendungen 117
13.5 Backtracking-Algorithmen 127
13.6
Ubungen 136
14 Dynamische Datenstrukturen 139
14.1 Einf uhrung 139
14.2 Die sortierte lineare Liste 140
INHALTSVERZEICHNIS
4
14.3 Der Kellerspeicher (Stack) 144
14.4 Die Schlange (Queue) 145
A C-Standard-Bibliothek 149
A.1 Einf uhrung 149
A.2 stdio.h 149
A.3 ctype.h 151
A.4 math.h 152
A.5 string.h 152
A.6 time.h 153
A.7 stdlib.h 153
A.8 limits.h 153
A.9 float.h 154
B C-Syntax 155
C Priorit at der Operatoren 157
D ASCII-Tabelle 158
Teil I
Grundlagen der strukturierten
Programmierung
Kapitel 1
Einleitung
1.1 Historie Programmiertechniken
bis 60er-Jahre Unstrukturierte Programmierung
70er-Jahre Strukturierte Programmierung
80er-Jahre Modulare Programmierung
90er-Jahre Objektorientierte Programmierung
1.1.1 Vor der strukturierten Programmierung
In den 60er-Jahre war das GOTO-Statement (Sprunganweisung) der wichtigste Teil in den Programmen, die gesamte Ablaufsteuerung musste ¨ uber GOTO programmiert werden. Dies hatte
zur Folge, daß die Programme sehr schlecht verst¨ andlich waren, schwierig zu warten und Programmierung als “Kunst“ verstanden wurde.
1.1.2 Strukturierte Programmierung
Ende der 60er entwickelte sich unter den Informatikern eine Debatte um Sinn und Unsinn des GOTOs. Ausl¨ oser war eine Ver¨ offentlichung von Dijkstra namens “Goto Statements Considered Harmful“ 1968.
Dijkstra: “Jeder Programmierer, der ein fehlerfreies Programm entwerfen m¨ ochte muß sich davon ¨ uberzeugen, daß sein Programm terminiert. In einem Programm, in dem eine unbegrenzte Anzahl von GOTO-Anweisungen eingebracht wurde, ist es sehr schwer zu sagen, an welcher Stelle das Programm bei einem Fehler h¨ angt, bzw. nicht terminiert. Bei der strukturierten Programmierung gibt es nur zwei M¨ oglichkeiten, daß ein Programm nicht abbricht. Entweder bei einer Rekursion oder in einer Wiederholungsschleife. Das macht die Fehlersuche wesentlich einfacher.“
Diese Ver¨ offentlichung kann als die Geburtsstunde der Strukturierten Programmierung angesehen werden.
Es wurde ein mathematischer Beweis gef¨ uhrt, daß sich jede Programmieraufgabe ¨ uber eine Abfolge der folgenden drei Ablaufstrukturen l¨ osen l¨ asst:
• Sequenz
• Auswahl
KAPITEL 1. EINLEITUNG 7
• Wiederholung
Ein zweites Ziel der strukturierten Programmierung war die Top-Down-Entwurfsmethode (vom Groben zum Detail), die durch die strukturierte Programmierung unterst¨ utzt wurde (Wirth).
So standen die 70er Jahre im Zeichen der strukturierten Programmierung. Unter dem Ziel des wiederverwendbaren Codes kam in den 80ern die Modulare Programmierung hinzu.
Seit den 90ern heißt das Schlagwort “Objektorientierte Programmierung“. Diese erweitert die strukturierte modulare Programmierung nochmals.
Die Programmiersprache Cwurde Anfang der 70 von Brian Kernighan und Dennis Ritchie an den Bell-Laboratories entwickelt und Mitte der 80er von Bjarne Stroustroup um objektorientierte Konzepte zu C++erweitert. Aber auch andere strukturierte Programmiersprachen wie Pascal wurden im Lauf der Zeit zu objektorientierten Sprachen erweitert (Object-Pascal, Delphi).
Chat einen hohen Verbreitungsgrad, ist als Programmiersprache von Kleinst- bis hin zu Großrechnern verf¨ ugbar und auf allen Betriebssystemen zu Hause. Es eignet sich f¨ ur Einsteiger zum Erlernen der Strukturierten Programmierung und kann sp¨ ater durch C++zum Erlernen der Ob-jektorientierten Programmierung weitergef¨ uhrt werden.
1.2 Programmieren lernen
“Die einzige M¨ oglichkeit, eine neue Programmiersprache zu lernen, ist, Programme mit ihr zu schreiben.“ (Brian Kernighan und Dennis Ritchie). Das vorliegende Skript ist eine theoretische Abhandlung ¨ uber die strukturierte Programmierung. Trotz vieler Beispiele kann es aber die Programmierpraxis am Computer nicht ersetzen. ¨
Ubung ist durch nichts zu ersetzen -außer durch noch mehr ¨
Ubung!
1.3 Einfache L¨ osungen sind die besten L¨ osungen
Neun Thesen zur Einfachheit (Quelle: Internet):
• Das Einfache hat zu tun mit dem Richtigen, dem Naheliegenden, dem Selbstverst¨ andlichen.
• Einfaches sollte nicht verkompliziert werden; Kompliziertes sollte nicht vereinfacht werden. Albert Einstein sagte einmal: “Man sollte alles so einfach wie m¨ oglich machen, aber nicht einfacher.“
• Nur das Einfache hat die Voraussetzung zeitlos und Allgemeingut zu werden.
• Das Einfache kennt keine Urheber als Person; es entsteht, ist pl¨ otzlich da - und keiner weiß woher; ist Ziel und Resultat zugleich.
• Das Einfache ist weniger eine Frage des Technischen - sondern mehr ein Problem der geistigen Grundeinstellung zum Technischen.
• Auch das Einfache kann High-Tech sein, muß es sogar, wollen wir energie- und materialgerecht konstruieren. Dennoch: das Einfache ist bescheiden, sinnf¨ allig, leicht zu nutzen, umzunutzen und zu beseitigen.
• Das Einfache ist nicht das Primitive, das Simple oder L¨ andliche; vielmehr ist das Einfache ein Produkt des kollektiven Nachdenkens und Entstehens. Somit ist das Einfache das Reifgewordene, die reife Frucht eines meist langen Prozesses.
KAPITEL 1. EINLEITUNG 8
• Das Vulg¨ are ist ein Feind des Einfachen - im Alltag, in der Kunst und in der Sprache.
• Das Einfache muß werden, man kann es finden; aber es l¨ aßt sich nicht herbeizwingen.
Kapitel 2
Algorithmen und Programme
2.1 Algorithmen
Das Fremdwort Algorithmus leitet sich vom Namen des mittelalterlichen persischen Mathematikers Abu Jaf’ar Mohammed ibn Mˆ usˆ a al-Khowˆ arizm ab.
Unter einem Algorithmus versteht man
eine zusammenh¨ angende Folge von Handlungsanweisungen zur L¨ osung eines Problems
Beispiele f¨ ur Algorithmen:
• Bedienungsanleitung eines Feuerl¨ oschers
• Berechnung des gr¨ oßten gemeinsamen Teilers zweier Zahlen (GGT)
• L¨ osung der Quadratischen Gleichung
Eigenschaften eines Algorithmus sind
Allgemeinheit Ein Algorithmus soll eine ganze Problemklasse mit unendlich vielen Auspr¨ agungen l¨ osen k¨ onnen. Ein Algorithmus, der lediglich den GGT der Zahlen 75 und 93 berechnen kann, ist kein Algorithmus.
Endlichkeit Diese Forderung gilt gleich in zweierlei Hinsicht.
• Ein Algorithmus soll durch einen endlichen Text beschreibbar sein.
• Ein Algorithmus muß innerhalb endlicher Zeit fertig werden.
So kann es keinen Algorithmus geben, der die Zahl π vollst¨ andig berechnet, da in endlich vielen Schritten immer nur eine endliche Anzahl von Dezimalstellen dieser nichtperiodischen, unendlich langen Zahl berechnet werden kann.
Determiniertheit Die Ausgabedaten m¨ ussen eindeutig von den Eingabedaten abh¨ angen. Auch die mehrmalige Anwendung des Algorithmus auf die gleichen Eingabedaten muß immer die gleiche Ausgabe erzeugen.
Rekursivit¨ at Ein Algorithmus kann zur L¨ osung eines Problems auf andere Algorithmen zur¨ uckgreifen. So greift etwas der Euler-Algorithmus zur Berechnung eines GGTs auf den Algo- rithmus zur Berechnung einer Rest-Division (“Modulo“) zur¨ uck.
KAPITEL 2. ALGORITHMEN UND PROGRAMME 10
Greift ein Algorithmus auf sich selber zur¨ uck, so nennt man ihn “Rekursiv“. Beispiel: Berechnung der Fakult¨ at:
Korrektheit Ein Algorithmus muss eine korrekte L¨ osung des Problems liefern.
Die Elementaroperationen des Algorithmus m¨ ussen eindeutig interpretierbar sein, d.h. f¨ ur alle Situationen muß festgelegt sein, was zu geschehen hat.
Algorithmus 1: GGT nach Euklid (1)
1. Sei a > 0, b > 0, a >= b
2. Berechne r = a MOD b
3. Wenn r = 0 dann ggt = b, STOP
4. Setze a = b, b = r , gehe zu Schritt 2
Eine mathematisch identische Anweisung ist:
Algorithmus 2: GGT nach Euklid (2)
1. Sei a > 0, b > 0
2. Solange a <> b ersetze die gr¨ oßere Zahl durch die Differenz der zwei Zahlen
3. ggt = b (oder ggt = a)
Hintergrund des Algorithmus ist eine Zeit der Mathematik, in der Addition und Subtraktion weniger Aufwand bedeutete als Multiplikation und Division. Der Euklid-Algorithmus l¨ ost das Teiler-Problem ¨ uber Subtraktionen!
2.1.1 Ablaufstrukturen
Zur Realisierung eines Algorithmus dienen Ablaufstrukturen. Achtung, nicht alle Programmiersprachen kennen alle Ablaufstrukturen (Zitat eines Computerkurs-Teilnehmers: “Mein Computer kennt die ELSE nicht!“).
• Sequenz oder Block
• Wenn Dann
• Wenn Dann Sonst
• Alternativen
• Kopfgesteuerte Schleife
• Fußgesteuerte Schleife
• Z¨ ahlschleife
Diese Ablaufstrukturen lassen sich beliebig aneinanderreihen sowie ineinander schachteln.
KAPITEL 2. ALGORITHMEN UND PROGRAMME 11
2.1.2 Programmieren
Programme sollten in der Praxis stets erst als Algorithmus auf Papier oder wenigstens im Kopf entstehen. Erst in einem zweiten Schritt erfolgt die Kodierung in eine gew¨ ahlte Programmiersprache. Anderes Vorgehen f¨ uhrt unweigerlich zu einer “Try-and-Error-Programmierung“, die normalerweise mehr Zeit in Anspruch nimmt als eine saubere Algorithmenbildung.
2.1.3 Vorhandenes Wissen nutzen
In den nunmehr 30 Jahren Strukturierter Programmierung sind sehr viele Standard-Probleme mit Algorithmen gel¨ ost worden. Strukturierte Programmierung bietet einfache Einbindung von “Fremd-Algorithmen“ ¨ uber Schnittstellen.
Beispiele:
• Berechnung von Ostern ¨ uber Algorithmen nach Gauss oder Knuth.
• Sortierung von Zahlen ¨ uber den Quicksort-Algorithmus
• Berechnung des Frequenzspektrums eines Signals ¨ uber den FFT-Algorithmus (Fast-Fourier-Transformation)
• Kompression von Dateien ¨ uber LZW-Algorithmus (Lempel-Zif-Welch).
2.2 Darstellungsformen
Algorithmen k¨ onnen auf verschiedene Arten dargestellt werden.
Freitext
Pseudo-Code
Programm-Code
Struktogramm
Ablaufplan
Aufgrund der guten Eignung f¨ ur die strukturierte Programmierung werden hier die Algorithmen meist als Struktogramm dargestellt. Der Vollst¨ andigkeit halber werden die wichtigsten Ablaufstrukturen auch als Ablaufplan gezeigt.
2.2.1 Struktogramme
Struktogramme unterst¨ utzen die Forderung der strukturierten Programmierung, daß Programme nur “von oben nach unten“ ablaufen, in idealer Weise. Struktogramme gehen auf einen Vorschlag von Nassi-Schneidermann zur¨ uck (Anfang 70er-Jahre, teilweise findet man auch den Begriff Nassi-Schneidermann-Diagramm) und sind in der DIN 66261 verankert.
Als wichtigstes Struktogramm-Element dient der Anweisungsblock, dargestellt durch ein Rechteck: Anweisung
Am Ende eines Programms erfolgt immer ein R¨ ucksprung, im Struktogramm dargestellt durch den Return-Block:
KAPITEL 2. ALGORITHMEN UND PROGRAMME 12
R¨ ucksprung
Beispiel Mittelwertberechnung
Das folgende Struktogramm stellt einen Algorithmus zur Berechnung des Mittelwerts zweier Zahlen dar: Mittelwertberechnung
2.2.2 Ablaufplan
Ein Programmablaufplan besteht aus verschiedenen geoemtrischen Formen, die jeweils eine Bedeutung haben. Das Rechteck steht f¨ ur Aktionen, Punkte dienen zur Verkn¨ upfung. Programmablaufpl¨ ane haben an Bedeutung verloren und f¨ ur die strukturierte Programmierung steht des sehr gut geeignete Werkzeug Struktogramm zur Verf¨ ugung. Ablaufpl¨ ane haben teilweise jedoch eine bessere Visualisierung, weshalb sie “nebenbei“ behandelt werden. Programmablaufpl¨ ane sind in der DIN 66001 verankert.
Mittelwert
h
A
B Folie 2
KAPITEL 2. ALGORITHMEN UND PROGRAMME 13
2.3 Freitext
2.4 Pseudo-Code
setze m = (z1 + z2) / 2
2.4.1 Programm-Code
2.5 Laufzeiten von Algorithmen
Bei Algorithmen, die auf Massendaten angewandt werden ist das Verhalten der Laufzeit in Abh¨ angigkeit von der Datenmenge interessant. Oft ist mit einer Verdoppelung der Datenmenge mehr als eine Verdoppelung der Laufzeit verbunden. Die wichtigsten Funktionen sind:
n
n 2
n 3
n ∗ ld (n)
Kapitel 3
Einf ¨ uhrung in C
3.1 Hello World
In der Informatik erfolgt eine Einf¨ uhrung in eine neue Programmiersprache klassischerweise mit einem kleinen Programm, welches nichts anderes macht als “Hello world!“ auf den Bildschirm zu schreiben.
Bildschirmausgabe:
Hello World!
Folie 3
3.2 Programmiersprachen
Der Prozessor eines Computers kann lediglich einfache Befehle verarbeiten, den sog. Maschinencode. Unterschiedliche Prozessoren haben unterschiedliche Maschinenbefehle. Um in der Informatik unabh¨ angig von der Hardware zu werden, wurden sog. Hochsprachen entwickelt, deren Sprachumfang unabh¨ angig von der eingesetzten Hardware ist. Um nun diese Hochsprache dem Prozessor verst¨ andlich zu machen muss sie in den jeweiligen Maschinencode “¨ ubersetzt“ werden.
KAPITEL 3. EINF ¨ UHRUNG IN C 15
3.2.1 Der GNU-C-Compiler
Der Compiler wird in der Kommandozeile aufgerufen:
> gcc helloworld.c
und produziert unter Linux eine ausf¨ uhrbare Datei namens a.out. Dies kann nun gestartet werden:
> ./a.out
Hello world! >
3.2.2 Die sprachlichen Elemente von Programmiersprachen
Schl¨ usselw¨ orter sind die W¨ orter, aus denen die Programmiersprache besteht (bsp if oder else).
Literale sind kleinste nicht mehr teilbare Zeichenfolgen wie etwa die Operatoren “+“ und “−“.
Bezeichner sind Namen, die der Programmierer nach bestimmten Vorgabe selbst vergeben kann, z.B. f¨ ur Variablen, Typen oder Module.
Konstanten sind fest eincodierte Werte wie 3.14 oder “Hallo“.
Trennzeichen dienen dazu, die restlichen Zeichenklassen zu trennen. Die Trennzeichen sind meist das Leerzeichen, das Zeilenendezeichen sowie horizontaler und vertikaler Tabulator und das Seitenvorschibszeichen.
KAPITEL 3. EINF ¨ UHRUNG IN C 16
In Ckommen noch die Pr¨ aprozessor-Direktiven hinzu, die obwohl sie eigentlich nicht zur Programmiersprache geh¨ oren trotzdem im Programmcode stehen.
3.3 Operatoren
Operatoren haben Argumente, die in der N¨ ahe des Operators stehen. Je nach Zahl der Argumente spricht man un¨ aren Operatoren (Operatoren mit einem Argument, z.B. das Minuszeichen im Ausdruck a = −b;), bin¨ aren Operatoren (Operatoren mit zwei Argumenten,z.B. das Pluszeichen im Ausdruck a = b + c;) oder tern¨ aren Operatoren (Operatoren mit drei Argumenten, siehe Verzweigungen)
3.4 C-Schl¨ usselw¨ orter (Keywords)
Die folgenden W¨ orter sind elementarer Bestandteil der Sprache C. Sie d¨ urfen daher weder als Variablen- noch als Funktionsname etc. vorkommen:
In den Beispielprogrammen werden diese Schl¨ usselw¨ orter der besseren Lesbarkeit wegen fett gesetzt.
3.5 Bezeichner
Unter Bezeichnern versteht man Namen, die der Programmierer frei vergeben kann. Diese Namen dienen der eindeutigen Kennzwichnung von Variablen, Modulen, Strukturen, Klassen, ...
Um anhand des Bezeichnernamens R¨ uckschl¨ usse auf den Typ des Bezeichners ziehen zu k¨ onnen macht es evtl Sinn, als ersten Buchstaben des Bezeichners die Bezeichnerart anzugeben. Oft wird dieser signifikante Buchstaben noch durch einen Tiefstrich vom restlichen Namen abgesetzt.
d Fließkommazahl (double)
i Ganze Zahl (integer) f Modul (function) s Struktur (struct) c Klasse (class)
3.6 Kommentare
Kommentare dienen dazu, den Programmcode lesbarer und verst¨ andlicher zu machen. Sie sollten Informationen, die nicht im Programmcode stecken, enthalten.
In Ckann auf zwei Arten ein Kommentar eingef¨ ugt werden:
• Der mehrzeilige Kommentar beginnt mit der Zeichenfolge /* und endet mit der Zeichenfolge */. Er dient vor allem dazu, am Programmanfang Informationen ¨ uber das Programm
(Zweck, Copyright, Datum, Version etc.) anzugeben. Im Zuge der Programmentwicklung dient er aber auch dazu, Programmteile vor einer Compilierung zu sch¨ utzen.
/∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
Kommentar−Demo M e h r z e i l i g e r Kommentar
KAPITEL 3. EINF ¨ UHRUNG IN C 17
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/
. . . a = 2; / ∗ Kommentar−Anfang a = 3; b = 4; Kommentar−Ende ∗ / c = 5 . . .
Folie 5
• Der einzeilige Kommentar beginnt mit der Zeichenfolge // und geht immer bis zum Ende der Editor-Zeile.
i n t main ( ) {
a = 2 ; / / H i e r s t e h t e i n Kommentar ; a=3 a =4; . . .
Folie 6
Sinnlose Kommentare sind bsp.
a = b + c ; / / S e t z e a a u f Summe von b und c
Derartige Kommentare haben keinen Nutzen und verschlechtern die Lesbarkeit eines Programms.
3.7 Programm-Layout
C-Programme sind mit Ausnahme des einzeiligen Kommentars und der Pr¨ aprozessor-Direktiven von der Zeile im Programmeditor unabh¨ angig. Die folgenden zwei C-Programme sind exakt identisch:
Obwohl es keine exakten Vorgaben gibt wie ein C-Programm auszusehen hat gelten die folgenden Regeln:
• Pro Editor-Zeile ein C-Statement
• Verbundanweisungen werden eine Tab-Taste einger¨ uckt
• Bl¨ ocke werden eine Tab-Taste einger¨ uckt
KAPITEL 3. EINF ¨ UHRUNG IN C 18
Auch macht es Sinn, zusammengeh¨ orende Programmteile durch Leerzeilen von anderen Teilen abzutrennen. Es dient jedoch nicht der ¨ Ubersichtlichkeit, zwischen allen Editorzeilen eine Leerzeile einzuf¨ ugen.
Es haben sich drein Einr¨ uckungsarten etabliert (hier am vorgegriffenen Beispiel einer if-Anweisung):
• Geschweifte Klammer noch in der ersten Zeile
i f ( a > b ) {
p r i n t f (” a i s t g r o e s s e r a l s b ! ” ) ; } i f ( a > c ) . . .
• Geschweifte Klammer umgebrochen in der Linie, innerhalb der Klammern einger¨ uckt
i f ( a > b )
{
p r i n t f (” a i s t g r o e s s e r a l s b ! ” ) ; } i f ( a > c ) . . .
• Geschweifte Klammer umgebrochen einger¨ uckt, innerhalb der Klammern nicht weitereinger¨ uckt
i f ( a > b )
{
p r i n t f (” a i s t g r o e s s e r a l s b ! ” ) ; } i f ( a > c ) . . .
3.8 Der Pr¨ aprozessor
Die wichtigsten Direktiven:
#include
#include ”header” Headerfile header wird eingebunden, Suche relativ zum aktuellen Verzeichnis (f¨ ur eigene Module)
#define M NAME
#define M NAME(idlist) sequence Makro mit Parametern, Achtung Seiteneffekte!
#undef M NAME l¨ oscht Makro M_NAME
#ifdef M NAME Pr¨ uft, ob Makro M_NAME definiert ist, wenn nicht, werden die folgenden C-Anweisungen bis zum korrespondierenen #endif entfernt
#else Alternative zum #ifdef
#elif Alternative zum #ifdef mit weiterer Bedingung
#endif Gegenst¨ uck zu #ifdef
#defined ( list ) Kompliziertere Fallunterscheidungen, Verkn¨ upfung mehrerer Bedingungen mit && (logisches Und) und || (logisches Oder) m¨ oglich
KAPITEL 3. EINF ¨ UHRUNG IN C 19
Mit einigen C-Compilern (wie etwa gcc) lassen sich auch Makros ¨
den Compiler ¨ ubergeben, ohne dass diese im C-Quellcode stehen m¨ ussen.
gcc test.c -DM_DEBUG -DGROESSE=10
Dies ist beim gcc den Pr¨ aprozessor-Kommandos
#d e f i n e M DEBUG 1
#d e f i n e GROESSE 1 0
¨ aquivalent.
3.9 Die Standardbibliothek
Mit den Schl¨ usselw¨ ortern der Programmiersprache Cl¨ asst sich zwar “im Prinzip“ ein Programm schreiben, jedoch stehen f¨ ur den Programmieralltag so wichtige Funktionen wie bsp. formatierte Ausgabe, Berechnung einer Quadratqurzel o.¨ a. nicht zur Verf¨ ugung.
Daher wurden solche Funktionen in der Standard-Bibiothek zusammengefasst, die zu jedem C-Compiler mitgeliefert wird (siehe Anhang).
3.9.1 Ein- und Ausgabe
Das printf-Kommando
Das printf-Kommando dient dazu, Ausdr¨ ucke am Bildschirm formatiert auszugeben (print-formatted). Es besteht aus einem Format-String und evtl. Ausdr¨ ucken. Der Formatstring kann Platzhalter f¨ ur Ausdr¨ ucke enthalten, diese Platzhalter werden bei der Ausf¨ uhrung des printf-Kommandos durch die ausgewerteten Ausdr¨ ucke ersetzt:
int a = 2, b = 3;
printf (”%d + %d = %d\n”, a, b, a+b);
In diesem Beispiel wird der erste %d-Platzhalter durch das Ergebnis des Ausdrucks “a“ er-setzt(2), der zweite Platzhalter %d wird durch das Ergebnis des Ausdrucks “b“ (3) und der dritte Platzhalter %d durch das Ergebnis des Ausdrucks “a+b“ (5), am Bildschirm erscheint
2 + 3 = 5
Folgende Platzhalter sind im printf-Kommando definiert:
%d Dezimalzahl (ganze Zahl), C-Typ int
%i wie %d
%ld Dezimalzahl (ganze Zahl), C-Typ long int
%x Hexadezimalzahl, kleine Buchstaben a. . . f, C-Typ int
KAPITEL 3. EINF ¨ UHRUNG IN C 20
%X Hexadezimalzahl, gro0e Buchstaben A. . . F, C-Typ int
%o Oktalzahl, C-Typ int
%u Dezimalzahl ohne Vorzeichen, sonst wie %d, C-Typ int
%c Ein einzelnes Zeichen, C-Typ char
%s Ein Zeichenfeld (String), C-Typ char []
%f Fließkommazahl, C-Typ float
%lf Fließkommazahl, C-Typ double
%e Fließkommazahl in Exponentialschreibweise, C-Typ float
%E wie %e, aber mit großem E, C-Typ float
%le Fließkommazahl in Exponentialschreibweise, C-Typ double
%% Da % einen Platzhalter anzeigt ist f¨ ur das %-Zeichen ein spezieller Platzhalter notwendig
Bildschirmausgabe:
78 ’N’, hex 4E, okt 116
0.142857 = 1.428571E-01 a=-0.000000 x=1069697316 Au backe! Folie 9
Es obligt dem Programmierer, den korrekten Platzhalter f¨ ur die Datentypen zu w¨ ahlen!
Zur Steuerung des Bildschirmausgabe existieren sog. Escape-Sequenzen (siehe Datentypen). Das in diesem Beispiel vorkommen \n sorgt bei der Bildschirmausgabe f¨ ur einen Umbruch in die n¨ achste Zeile.
Das scanf-Kommando
Analog zum printf-Kommando, das die Bildschirmausgabe macht, gibt es zur Eingabe per Tastatur das scanf-Kommando (scan-formatted). Es funktioniert analog zum printf-Kommando mit zwei Unterschieden:
• Der Formatstring sollte nur aus Format-Platzhaltern bestehen
• Statt Ausdr¨ ucken zu diesen Platzhalten m¨ ussen Variablen stehen, denen der Adressoperator & vorangestellt wird (siehe Zeiger).
KAPITEL 3. EINF ¨ UHRUNG IN C 21
Bildschirmausgabe:
Geben Sie zwei Zahlen zur Addition ein: 2.1 -3.4 2.100000 + -3.400000 = -1.300000
Kapitel 4
Einfache Datentypen
4.1 Einf¨ uhrung
Im Laufe eines Programms m¨ ussen variable Werte abgespeichert werden, etwa die Eingaben des Programmanwenders. Andernfalls w¨ urde jeder Programmlauf exakt dasselbe Ergebnis bringen.
Programme m¨ ussen sich im Laufe ihrer Abarbeitung Werte - meist Zahlen - “merken“. Viele Programmiersprachen unterscheiden dabei zwischen ganzen Zahlen (Integer) und Kommazahlen (float). Zum “merken“ dieser Werte wird Speicher ben¨ otigt, je nach Art des Datums (singular von Daten) unterschiedlich viel:
Bildschirmausgabe:
Byte-Gr¨ oßen von Variablentypen
Typ Gr¨ oße char 1 short int 2 int 4 long int 4 float 4 double 8 long double 12
KAPITEL 4. EINFACHE DATENTYPEN 23
4.2 Ganze Zahlen
Der Datentyp der ganzen Zahlen entspricht der erst einmal der mathematischen Menge Z der ganzen Zahlen. Da jedoch der Speicherplatz im Computer begrenzt ist, wird je nach Gr¨ oße des f¨ ur eine Zahl resvierten Speichers unterschiedlicher Wertebereich verwendet:
Die asymetrische Verteilung des Wertebereichs bei den Integern mit Vorzeichen folgt aus der Tatsache, daß die Zahl 0 kein negatives Komplement hat. Mit den zur Verf¨ ugung stehenden 8
Bit einer char-Variablen lassen sich 2 8 = 256 verschiedene Zust¨ ande darstellen, diese werden den Zahlen -128 (−2 7 ) bis 127 (2 7 − 1) zugeordnet. Da die Grenzen vom verwendeten Compiler abh¨ angig sind k¨ onnen die tats¨ achlichen Grenzen der Datei limits.h (Seite ??) entnommen werden.
Mit Integer-Zahlen wird korrekt gerechnet, es entstehen keine Rundungsfehler. Wird jedoch im Zuge der Berechnung eines Ausdrucks der Zahlenbereich verlassen, so wird statt des korrekten Ergebnisses der Zahlenbereich am “anderen Ende“ wieder betreten und ein falsches Ergebnis berechnet:
E ' $
Ein kleines Programm zeigt dies:
Bildschirmausgabe:
126 + 2 = -128
KAPITEL 4. EINFACHE DATENTYPEN 24
Im Kreis der char-Zahlen kommt eben zwei Stellen nach 126 die Zahl 128!
F¨ ur Integerzahlen stehen die Rechenoperatoren +, −, ∗, / und % zur Verf¨ ugung. / arbeitet dabei als Ganzzahldivision, % als Restdivision.
Bildschirmausgabe:
9 / 4 = 2 rest 1
Char-Zahlen k¨ onnen auf mehrere Arten im Programm codiert werden:
Zahl Direkte Angabe im Zehnersystem: int a = 123;
Zeichen Direkte Angabe eines Zeichens in Hochkomma: int a = ’A’;
Escape-Sequenz Einige spezielle Zeichen, die Auf der Tastatur nicht existieren, k¨ onnen als Escape-Sequenz eingegeben werden: int a = ’\n ’;
Oktal-Zahl Auf eine Backslash folgend wird eine dreistellige Zahl als Oktalzahl interpretiert: int a = ’\012’;
Hexadezimal-Zahl Auf Backslash-x folgend wird eine zweistellige Zahl als Hexadezimalzahl interpretiert: int a = ’\x20 ’;
Die folgenden Escape-Sequenzen sind definiert:
\n (newline) Zeilenvorschub , entspricht RETURN bei der Tastatureingabe
\t Tabulator , auf dem Bildschirm wird ein Tabulator [TAB] - Sprung gemacht
\b Backspace , letztes Zeichen wird gel¨ oscht
\r Carriage Return
\a Pieps (alert)
\f Seitenvorschub (formfeed) f¨ ur Drucker
\0 String-Endmarkierung verwendet
\\ Backlash , erzeugt einen \
\’ Hochkomma
\“ Anf¨ uhrungszeichen
KAPITEL 4. EINFACHE DATENTYPEN 25
\0ddd ASCII-Zeichen in oktaler Notation
\xdd ASCII-Zeichen in hexadezimaler Notation
Die Entsprechung zwischen Zahlenwert und Zeichen findet sich in der Code-Tabelle. Weit verbreitet ist der ASCII-Code (American standard-code for information-interchange, Seite 158). Dieser Code standardisiert die Kontrollzeichen (Escape-Sequenzen), die Buchstaben A...Z, Ziffern etc. Nicht standardisiert sind alle Zeichen, die in der amerikanische Sprache nicht vorkommen, wie etwa die deutschen Umlaute:
Bildschirmausgabe:
¨ A: 196
¨ O: 214 ¨ U: 220 ¨ a: 228 ¨ o: 246 ¨ u: 252 ß: 223 Diese Bildschirmausgabe entstand unter Linux!
Escapesequenzen k¨ onnen auch innerhalb von Zeichenketten (Strings) vorkommen.
Bildschirmausgabe:
KAPITEL 4. EINFACHE DATENTYPEN 26
65 A
Jetzt piepts! ’C’ - ’A’ = 2
4.3 Fließkommazahlen
Fließkommazahlen unterliegen weniger dem Problem des Zahlenbereichs, sondern dem Problem von Rundungsfehlern:
Bildschirmausgabe:
1000.000000 + 0.001000 = 1000.000977
10000.000000 + 0.000100 = 10000.000000
Eine Variable vom Typ float wird intern mit vier Byte gespeichert, sie kann also 2 32 = 4294967296 (ca. 4 Milliarden) verschiedene Werte annehmen. Mit diesem Wertevorrat muß nun der mathematische Zahlenbereich von −∞ bis +∞ abgebildet werden - unendlich viele Zahlen. Daraus folgt, daß eben nicht jede Kommazahl durch den Datentyp float dargestellt werden kann.
Intern werden Fließkommazahlen als zwei Integer-Zahlen, der Mantisse und dem Exponent gespeichert:
KAPITEL 4. EINFACHE DATENTYPEN 27
Als G¨ utekriterium wird die L¨ ange der Mantisse im Dezimalsystem angegeben.
Da auch diese Werte Compilerabh¨ angig sind k¨ onnen die aktuellen Werte der Bibiliothek float.h (Seite ??) entnommen werden.
Entstehen bei arithmetischen Berechnungen Mantissen mit diesen L¨ angen so muß mit Rundungs- fehlern gerechnet werden.
Kapitel 5
Ausdr ¨ ucke
5.1 Einf¨ uhrung
5.1.1 Allgemeines
Zu einem Operator geh¨ oren die sog. Operanden. Je nach Zahl der Operanden nennt man einen Operator “un¨ ar“ (ein Operand), “bin¨ ar“ (zwei Operanden) oder “tern¨ ar“ (drei Operanden, es gibt in C nur einen tern¨ aren Operator der im Kapitel “Verzweigungen“ behandel wird).
Un¨ are Operatoren:
Bin¨ are Operatoren:
KAPITEL 5. AUSDR ¨ UCKE 29
5.1.2 Priorit¨ at von Operatoren
5.1.3 Assoziativit¨ at von Operatoren
Rechtsassoziativ sind alle un¨ aren Operatoren und alle Zuweisungsoperatoren.
Linsassoziativ sind die restlichen Operatoren.
5.1.4 Reihenfolge der Auswertung
Mit Ausnahme der Logischen Operatoren && und || ist in C-Standard nicht spezifiziert, welcher der zwei Operanden eines bin¨ aren Operators zuerst ausgewertet wird. Daher ist es in C leider m¨ oglich, Ausdr¨ ucke zu schreiben, die von Compiler zu Compiler unterschiedliche Ergebnisse bekommen.
b = 1;
a = (b = b + 1) + 2 ∗ b ;
Je nachdem, ob der linke Operand des +-Operators (b = b + 1) oder der rechte Operand (2 ∗ b) zuerst ausgewertet wird hat die Variable a am Schluß den Wert 4 oder 6!
5.1.5 Seiten- und Nebeneffekte
KAPITEL 5. AUSDR ¨ UCKE 30
In C ist also die Ver¨ anderung von Variablen innerhalb der Auswertung eines Ausdrucks m¨ oglich. Dies nennt man Nebeneffekt(e) des Ausdrucks. Gleichzeitig wird der Wert einer Zuweisung weiterverwertet, dies nennt man einen Seiteneffekt:
p r i n t f (”%d” , a = 2 + 3 ) ;
Hier gibt es einen Seiteneffekt (a wird auf den Wert 5 gesetzt) und einen Seiteneffekt (der Wert 5 wird an printf () weitergereicht). Ein weiteres Beispiel f¨ ur einen Ausruck mit Seiten- und Nebeneffekten ist
a = b = 1;
Nebeneffekte sind das Ver¨ andern der Variablen a und b, ein Seiteneffekt entsteht durch das Verwenden des Zuweisungswertes von b f¨ ur die Zuweisung a.
5.2 Operatoren
5.2.1 Diverse Operatoren
5.2.2 Arithmetische Operatoren
5.2.3 Relationale Operatoren
KAPITEL 5. AUSDR ¨ UCKE 31
5.2.4 Logische Operatoren
Logische Operatoren k¨ onnen auf auf ganzzahlige wie auch auf Fließkomma-Operanden ange- =0 als “Logisch wahr“ (1) und Operanden = 0 als wandt werden. Dabei werden Operanden
“Logisch falsch“ (0) gewertet. Das Ergebnis einer logischen Operation ist ein Int-Wert 0 oder 1.
Bei den logischen Operatoren ist die Reihenfolge der Auswertung der Operanden “links vor rechts“. Ist das Ergebnis der logischen Operation vor Auswertung des zweiten Operanden bereits klar (ertser Operand “wahr“ beom ODER-Operator oder erster Operand “falsch“ beim UND-Operator) so wird der zweite Operand nicht ausgewertet!
a = 1;
b = 1 | | + + a ;
a hat am Ende den Wert 1, da der rechte Operand der ODER-Operators nicht mehr ausgewertet wird. Boolesche Logik:
5.2.5 Bit-Operatoren
Die Bit-Operatoren sollten nur f¨ ur vorzeichenlose ganze Zahlen verwendet werden. Sie operieren (im Gegensatz zu den logischen Operatoren) auf jedem Bit des Operanden getrennt.
Beispiele:
Zu bemerken ist, daß bei den Schiebe-Operatoren >> und << der linke Operand bin¨ ar und der rechte Operand dezimal verarbeitet wird.
KAPITEL 5. AUSDR ¨ UCKE 32
5.2.6 Kombinierte Zuweisungs-Operatoren
Bei diesen Operatoren erfolgt eine Zuweisung zusammen mit einer anderen Operation. So kann in C der Code a = a + b durch a += b ersetzt werden.
5.2.7 Increment- und Decrement-Operatoren
In der Programmierung kommen sehr h¨ aufig Ausdr¨ ucke wie a = a + 1 oder b = b − 1 vor. Diesen Vorgang nennt man Incrementieren bzw. decrementieren (erh¨ ohen oder vermindern) von Variablen. In C gibt es f¨ ur diese Ausdr¨ ucke die Operatoren ++ und −− in Pr¨ a- und Postfix-Schreibweise
So kann der C-Code a = a + 1 k¨ urzer geschrieben werden durch a++ (Postfix-Schreibweise) oder ++a (Pr¨ afix-Schreibweise). Unterschiede zwischen Post- und Pr¨ afixschreibweise ist in der Operator-Reihenfolge. Im C-Ausdruck a = b++ wird erst der Variablen a der Wert der Variablen b zugewiesen und anschließend b incrementiert. Im C-Ausdruck a = ++b wird erst b incrementiert und anschließend erfolgt die Zuweisung.
Bildschirmausgabe:
a=2 b=3 c=4 Folie 10
5.2.8 Speicher-Operatoren
Bei diesen Operatoren erfolgt eine Zuweisun zusammen mit einer anderen Operation. So kann in C der Code a = a + 1 durch a += 1 ersetzt werden.
KAPITEL 5. AUSDR ¨ UCKE 33
5.3 Funktionen
Funktionen bestehen aus einem Funktionsnamen und einer Anzahl von Argumenten, die in Klammern hinter dem Funktionsnamen stehen (siehe Modulare Programmierung). Als Beispiel soll hier die Sinus-Funktion gezeigt werden. Sie ben¨ otigt ein Argument (Parameter), n¨ amlich den Winkel in der Maßeinheit Radiant:
Bildschirmausgabe:
Geben Sie einen Winkel in Grad ein: 30
sin(30.000000 ◦ ) = 0.500000
Das Argument der sin()-Funktion ist selbst wieder ein Ausdruck!
In C selbst gibt es nur eine Funktion, namlich die sizeof ()-Funktion. In der C-Standardbibliothek sind viele Funktionen implementiert.
Die Parameter einer Funktion sind selbst wieder Ausdr¨ ucke. Hat eine Funktion mehrere Parameter so ist die Reihenfolge der Auswertung dieser Ausdr¨ ucke nicht im C-Standard spezifiziert:
a = 1;
p r i n t f (”%d %d” , a , ++ a ) ;
Je nach Compiler kann die Bildschirmausgabe dieses Programms “1 2“ oder aber “2 2“ sein!
5.4 Typisierung
C geht bei der Berechnung von Ausdr¨ ucken davon aus, dass es sich um Integer-Zahlen handelt. Erst wenn der Compiler auf eine Fließkommazahl st¨ oßt schaltet er ab dieser Stelle auf Fließkommaarithmetik um. So wird der Variablen b in dem Codefragment double b = 1 / 2; nicht der Wert 0.5 sondern der Wert 0 zugewiesen. Warum? Weil zuerst der Ausdruck 1 / 2 ausgewertet wird, links und rechts des Divisionsoperator stehen ganze Zahlen, also erfolgt eine Integerdivison, deren Ergebnis 0 ist. Dieses Ergebnis wird jetzt der double-Variablen b zugewiesen.
Abhilfe schafft hier nur das Erzwingen eines Typs, entweder durch einen direkten Typecast, in dem der Typ in Klammer vorangestellt wird (double b = (double) 1 / 2;) oder durch Eingabe von mindestens einer Fließkommnazahlen vor oder direkt nach dem Divisionsoperator (double b = 1.0 / 2;).
Die Vergleichsoperatoren haben als Ergebnistyp immer Integer!
KAPITEL 5. AUSDR ¨ UCKE 34
5.5 Reihenfolge bei der Berechnung von Ausdr¨ ucken
Operatoren werden in einer bestimmten Reihenfolge abgearbeitet. Die Priorit¨ at der Operatoren wird dazu in Klassen eingeteilt. Folgen Operatoren derselben Klasse aufeinander, so erfolgt die Abarbeitung meist von links nach rechts. Allgemein gilt daß Klammern (auch Funktionsklammern) die allerh¨ ochste Priorit¨ at haben.
5.6 ¨ Ubungen
• Entwickeln Sie ein Programm, das die Umrechnung eines Vektors von Kartesischen Ko-ordinaten in Polarkoordinaten erm¨ oglicht und ein weiteres Programm f¨ ur die umgekehrte Richtung.
• Entwickeln Sie ein Programm, das nach Eingabe einer Strecke in Km (nur ganze Zahlen) und einer Geschwindigkeit) die Fahrzeit in Stunden und Miuten berechnet.
• Entwicklen Sie ein Programm, das f¨ ur einen Schiefen Wurf anhand von Startgeschwindigkeit v 0 und Wurfwinkel α Wurfweite und max. Flugh¨ ohe berechnet und ausgibt.
Kapitel 6
Verzweigungen
6.1 Einf¨ uhrung
Ein kleines Programm zur Division von Zahlen liest Zahlen von der Tastatur ein und gibt den Quotienten aus:
Bildschirmausgabe:
localhost:[programme]> ./a.out
Geben Sie zwei Zahlen ein: 9 4 9 / 4 = 2 Rest 1 localhost:[programme]> ./a.out Geben Sie zwei Zahlen ein: 9 0 Gleitkomma-Ausnahme localhost:[programme]> Folie 11
Statt des nichtssagenden Ergebnisses “inf“ sollte besser ein Text ”Durch 0 darf nicht geteilt werden“ o.¨ a. erscheinen. Dazu darf die Division nur f¨ ur den Fall dass der Nenner ungleich 0 ist durchgef¨ uhrt werden.
Mit Verzweigungen k¨ onnen Programmbl¨ ocke abh¨ angig von einer Bedingung ausgef¨ uhrt werden.
KAPITEL 6. VERZWEIGUNGEN 36
6.2 Die einfache Verzweigung (if-else)
6.2.1 Darstellungsarten
Struktogramm
Die Beschriftung ist sehr frei, als Bedingung kann Freitext, Ausdr¨ ucke in C-Notation oder Pseudo-Code stehen. Statt “Ja“ und “Nein“ ist auch “1“ und “0“ oder “true“ und “false“ denkbar. Die Seite von if- und else-Teil ist beliebig.
Ablaufplan
6.2.2 Anwendung
Division
In C gibt es zur Verzweigung das if-else-Kombination:
Syntaxdiagramm 1: if-else-Statement
¨
KAPITEL 6. VERZWEIGUNGEN 37
Der gesamte else-Teil ist optional, d.h. ein if kann auch ohne zugeh¨ origes else vorkommen.
Der Bedingungsausdruck innerhalb der runden Klammer kann jeder g¨ ultige C-Ausdruck sein. Er wird ausgewertet und auf einen Wert ungleich 0 gepr¨ uft. Logische Werte k¨ onnen auch arithmetisch verarbeitet werden, logisch “Wahr“ hat den arithmetischen Wert 1 und logisch “Falsch“ hat den arithmetischen Wert 0. Wird ein Zahlenwert (int oder float) logisch verarbeitet (d.h. uber einen Logik-Operator verkn¨ upft) so erfolgt eine Art Typecast zu einem Logikwert: ¨
Die Bedingungsausdr¨ ucke if (a != 0) ... und if (a ) ... sind damit identisch, die Ausdr¨ ucke if (a == 0) ... und if (! a) ebenfalls. Wird der Negationsoperator “!“ auf Zahlenwerte (Ganze Zahlen oder Fließkommazahlen) angewandt so wird bei diesen Zahlenwerten ebenfalls ein Logik-Typecast erzwungen und folgendermaßen ausgewertet:
Damit kann das Eingangsbeispiel zur Division von Zahlen verbessert werden:
6.2.3 Schachtelung von if-else-Verzweigungen
Programmcode wie
i f ( a > 0)
p r i n t f ( ”a > 0!\ n” ) ; i f ( b > 0) p r i n t f ( ”b > 0!\ n” ) ; e l s e p r i n t f ( ”b <= 0!\n” ) ;
sind auif den ersten Blick nicht eindeutig, da es zu zwei if-Bedingungen nur ein else-Statement gibt. Dieses else k¨ onnte nun zu if (a > 0) oder zu if (b > 0) geh¨ oren. Im Struktogramm sehen die zwei M¨ oglichkeiten folgendmaßen aus:
i f ( a > 0)
KAPITEL 6. VERZWEIGUNGEN 38
p r i n t f ( ”a > 0!\ n” ) ;
i f ( b > 0) p r i n t f ( ”b > 0!\ n” ) ; e l s e p r i n t f ( ”b <= 0!\n” ) ;
else geh¨ ort zum ersten if
Dieses Uneindeutigkeit wird in den meisten Programmiersprachen - auch in C - folgendermaßen gel¨ ost:
else-Bedingungen geh¨ oren immer zum letzten if in der aktuellen Schachtelungsebene!
Folgender Sachverhalt soll in C codiert werden:
¨
Eine erste Codierung sieht folgendermaßen aus:
s c a n f (”%d%d” , & a , & b ) ;
i f ( a > 0) i f ( b > 0 ) { / / Block X . . . } e l s e { / / Block Y . . . } Folie 17
In diesem Beispiel wird jedich im Fall a > 0 und b < 0 der Block Y ausgef¨ uhrt, was laut Struktogramm falsch ist. Der Fehler resultiert daraus, dass ein else-Kommando eben zum letzten if in der aktuellen Blockschachtelungsebene geh¨ ort, in diesem Beispiel also zu if (b > 0).
Um ein korrektes Programm zu erhalten gibt es jetzt drei M¨ oglichkeiten:
• Setzen einer Block-Klammer
s c a n f (”%d%d” , & a , & b ) ;
i f ( a > 0 ) { i f ( b > 0 ) { / / Block X . . . } } e l s e { / / Block Y . . . }
KAPITEL 6. VERZWEIGUNGEN 39
Folie 18
Da if (b > 0) und else jetzt in unterschiedlichen Klammerebenen liegen, geh¨ ort das else zu if (a > 0), da dieses in der selben Klammerebene liegt.
• Invertierung der ¨ außeren Bedingung
s c a n f (”%d%d” , & a , & b ) ;
i f ( a < = 0) { / / Block Y . . . } e l s e i f ( b > 0 ) { / / Block X . . .
}
Da zwischen if (a <= 0) und else keine weiteren if-Bedingungen befinden steht hier das richtige Paar beeinander.
• Leeres else
s c a n f (”%d%d” , & a , & b ) ;
i f ( a > 0)
} e l s e ; e l s e { / / Block Y . . . } Folie 20
In diesem Fall gibt es zwei if-else-Paare, wobei das Paar if (b > 0)−else komplett in die Anweisung zu if (a > 0) eingeschachtelt ist.
6.2.4 Die Verarbeitung von Eingabefehlern
H¨ aufig wird am Anfang eines Programm bzw. nach der Dateneingabe eine Fehler¨ uberpr¨ ufung vorgenommen. Diese ist prinzipiell auf zwei Arten m¨ oglich:
• Wenn ein Fehler Auftritt wird das Programm direkt verlassen. Dadurch wird kein else-Teil und keine Schachtelung n¨ otig, das Programm hat aber mehrere return-Stellen.
• Die Fehlerabfrage wird ¨ uber einen if-else-Block abgehandelt. Das Programm wird dann immer am Ende verlassen, es wird jedoch eine Schachtelungsebene verbraucht.
KAPITEL 6. VERZWEIGUNGEN 40
6.3 Die mehrfache Verzweigung (switch-case)
6.3.1 Darstellungsarten
Struktogramm
h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h
Wenn eine Mehrfache Verzweigung abh¨ angig von einem Integer-Ausdruck ist so kann auch mit dem switch-case-Statement gearbeitet werden. Wichtig in C ist, dass
• der Ausdruck am Beginn des switch-case-statements ausgewertet wird und
• die Auswahlwerte konstante Integerwerte sein m¨ ussen.
Eine weitere Besonderheit in C ist, dass das switch-case-Statement ab der gefundenen Variante bis zum Ende abgearbeitet wird. Da dies im Allgemeinen unerw¨ unscht ist muss am Ende jeder Auswahl das break-statement stehen. Es ist keine Block-Klammer n¨ otig!
Beispiel: In einem Betrieb gibt es verschiedene Rabattklassen. Rabattklasse 0 entspricht 0% Rabatt, Rabattklasse 1 entspricht 3% Rabatt, Rabattklassen 2 und 3 entsprechen 5% Rabatt. Ein Programm soll vom Anwender eine Rabattklasse anfordern und den entsprechenden Rabatt ausgeben: Rabatt-Berechnung
KAPITEL 6. VERZWEIGUNGEN 41
6.4 Der tern¨ are Operator “? :“
In Programmen kommen oft Anweisungen wie die folgende vor:
i f (< Bedingung>)
x = < Ausdruck >; e l s e x = < A n d e r e r Ausdruck >;
Wichtig ist, dass abh¨ angig von einer Bedingung einer von zwei Ausdr¨ ucken ausgewertet wird. Dies kann durch den tern¨ aren Operator vereinfacht werden:
x = (
6.4.1 Beispiele zum Tern¨ aren Oprator
Berechnung des absoluten Werts einer Zahl:
i n t a = − 3, b =2, a b e t r a g , b b e t r a g ;
a b e t r a g = ( a > = 0) ? a : − a ; b b e t r a g = ( b > = 0) ? b: − b ;
6.5 Beispiele
6.5.1 Ein einfacher Rechner
Es soll ein einfaches Rechenprogramm geschrieben werden welches vom Anwender eine Rechnung im Format
F¨ ur die Abfrage des Operators bietet sich das switch-case-Statement an. Zu beachten ist
KAPITEL 6. VERZWEIGUNGEN 42
nat¨ urlich die Division, bei der die Division durch 0 abgefangen werden muß: Einfacher Rechner mit switch-case
KAPITEL 6. VERZWEIGUNGEN 43
Bildschirmausgabe:
Geben Sie eine Rechnung ein: 2/-3
2.000000/-3.000000 = -0.666667
Geben Sie eine Rechnung ein: 4/0
Eingabefehler!
Geben Sie eine Rechnung ein: 3¨ o2
Eingabefehler!
6.5.2 Berechnung der qudratischen Gleichung nach der Mitternachts-formel
F¨ ur eine allgemeine quadratische Funktion der Form y = ax 2 + bx + c sollen die Nullstellen der Funktion gefunden werden. Dazu dient die sog. Mitternachtsformel √
Wird als Koeffizient a jedoch der Wert 0 eingegeben so reduziert sich die Parabel auf eine Gerade, die Mitternachtsformel kann nicht mehr angewandt werden. Statt dessen muss die Nullstelle der Gerade y = bx + c gefunden werden nach der Formel
−c
= 0) sind wieder verschiedene Fallunterberechnet werden. In beiden F¨ allen (a = 0 und a
scheidungen zu beachten, bei der Mitternachtsformel kann der Radikand (der Wert unter dem Wurzelzeichen) gr¨ oßer als 0 sein (in diesem Fall gibt es zwei Nullstellen), er kann gleich 0 sein
(eine Nullstelle) oder er kann kleiner als 0 sein (keine Nullstelle). Im Falle der Geraden kann der Wert b ungleich 0 sein (eine Nullstelle) oder gleich 0 sein (je nach Wert von c keine oder unendlich viele Nullstellen). Insgesamt sind also sechs verschieden F¨ alle zu unterscheiden: Quadratische Gleichung
KAPITEL 6. VERZWEIGUNGEN 44
Bei der Implementierung ist das switch-case-statement von Interesse. Die Vorzeichenfunktion uber den logischen Ausdruck (x > 0) − (x < 0) double signum(double x ) kann mit einem Trick ¨
simuliert werden. Die beiden Summanden sind logische Ausdr¨ ucke, die zu 1 oder 0 ausgewertet und anschließend subtrahiert werden. Dieser Ausdruck wird in C folgendemaßen ausgewertet: ⎧
Die Fallunterscheidung c = 0 erfolgt ¨ uber den tern¨ aren Operator. Folie 26
KAPITEL 6. VERZWEIGUNGEN 45
Bildschirmausgabe:
L¨ osung der quadratischen Gleichung y = a x^2 + b x +c
Geben Sie die Koeffizienten a, b und c ein: 1 0 -2
y = 1.00 x^2 + 0.00 x + -2.00
Parabel mit zwei Nullstellen bei 1.414214 und -1.414214
6.6 Aufgaben und ¨ Ubungen
6.6.1 Bremsweg
Der Bremsweg eines Autos setzt sich zusammen aus Fahrstrecke w¨ ahrend der Reaktionszeit des Fahrers und dem eigentlichen Bremsweg.
Schreiben Sie ein Programm, das nach Eingabe einer Geschwindigkeit den Bremsweg brechnet und ausgibt.
6.6.2 Schulnoten
Ein Lehrer m¨ ochte anhand von einzelnen Noten das Endergebnis berechnen. Seine Endnote setzt sich folgendermaßen zusammen:
e =
Die schriftliche Note setzt sich aus vier gleichgewichteten Noten zusammen. Das Ergebnis soll als Dezimalnote (eine Stelle nach dem Komma), als ganze Note und als Text angezeigt werden.
6.6.3 Sortieren
Es sollen drei Zahlen eingegeben und der Gr¨ oße nach aufsteigend sortiert ausgegeben werden.
Kapitel 7
Schleifen
7.1 Einf¨ uhrung
Oft ist es n¨ otig, Programmcode mehrfach auszuf¨ uhren. Sollen beispielsweise alle Teiler einer Integerzahl Z ausgegeben werden so ist f¨ ur jede Zahl zwischen 1 und Z zu pr¨ ufen ob die Restdivision 0 ergibt. Wenn der Anwender die Zahl Z zum Zeitpunkt des Programmlaufs eingeben kann weiss der Programmierer noch nicht, wie viele Zahlen zu pr¨ ufen sind. Die Pr¨ ufung muss also - obwohl nur in einer Programmzeile codiert - mehrfach durchlaufen werden. Dazu dienen Schleifen.
Pseudocode:
lies z ein
f¨ ur jedes i von 1 bis z wenn z Restdiv i = 0 Ausgabe i
7.2 Die drei Schleifenarten
Z¨ ahlergesteuert Die z¨ ahlergesteuerte Schleife dient einfach dazu, Programmcode mehrfach abzuarbeiten. Die Zahl der Durchl¨ aufe muss beim Beginn der Schleife bekannt sein.
Fußgesteuert Die fußgesteuerte Schleife dient dazu, Programmcode abh¨ angig von Bedingungen im Programmcode der Schleife zu wiederholen. Beispielsweise wird eine Eingabe eines Anwenders solange wiederholt bis er eine positive ganze Zahl eingegeben hat.
Kopfgesteuert Die kopfgesteuerte Schleife dient dazu, Programmcode abh¨ angig von Bedingungen im Programmcode vor und in der Schleife zu wiederholen.
Bei den Bedingungen f¨ ur Schleifen ist es leider nicht einheitlich, ob eine Abbruchbedingung oder eine Weitermachbedingung angegeben wird.
KAPITEL 7. SCHLEIFEN 47
7.3 Darstellungsarten
7.3.1 Struktogramm
F¨ ur die drei Schleifenarten gibt es spezielle Struktogrammelemente:
Z¨ ahlergesteuerte Schleife
7.3.2 Programmablaufplan
Im Programmablaufplan m¨ ussen die Schleifen “von Hand“ gezeichnet werden:
Z¨ ahlergesteuerte Schleife Fussgesteuerte Schleife Kopfgesteuerte Schleife
7.4 Die z¨ ahlergesteuerte Schleife
Die z¨ ahlergesteuerte Schleife wird dann eingesetzt, wenn bereits am Beginn der Schleife klar ist, wie oft die Schleife durchlaufen wird.
Beispiel: Ein Programm soll vom Anwender 5 Zahlen per Tastatur einlesen und die Summe ausgeben. Zwar k¨ onnte dies auch ohne Schleife - durch entsprechend viele Lese-Kommandosgeschehen, eine ¨ Anderung auf 10 oder 100 Zahlen w¨ are jedoch nur mit viel Aufwand m¨ oglich. Mittel der Wahl ist hier eine z¨ ahlergesteuerte Schleife mit 5 Schleifendurchl¨ aufen: 5 Zahlen addiern
Wichtig ist bei solchen Aufgaben, die Summenvariable mit 0 zu initialisieren. Wird dies vergessen, so ist der Wert von summe am Anfang willk¨ urlich, je nach Compiler unterschiedlich.
KAPITEL 7. SCHLEIFEN 48
Eine ¨ Anderung des Programms auf 10 oder 100 Zahlen ist jetzt einfach, es muss lediglich die obere Grenze der Schleife ver¨ andert werden.
7.4.1 Syntax
Syntaxdiagramm 2: for-Schleife
¨ ¨
7.4.2 Wahl des Schleifenz¨ ahlers
Die ¨ Aquivalenz zwischen z¨ ahlergesteuerter Schleife und kopfgesteuerter Schleife l¨ asst auch die Verwendung von Fließkommazahlen als Schleifenz¨ ahler sinnvoll erscheinen. Dies ist in anderen Sprachen wie etwa Pascal nicht m¨ oglich. Aufgrund der Probleme mit der Fließkommaarithmetik muss auch von der Verwendung von Fließkommazahlen als Schleifenz¨ ahler dringend abgeraten werden.
Als Beispiel soll folgende Summe berechnet werden:
x = 1000 + 1000.001 + 1000.002 + . . . + 1000.049 + 1000.05
Mit etwas Denkarbeit l¨ asst sich das Ergebnis exakt berechnen:
x =
Nun kann nach der Gaußschen Summenformel berechnet werden:
x = 51000 +
Das folgende Programm berechnet die Summe dreimal, einmal mit einer Fließkommazahl (einfache float) als Schleifenz¨ ahler, einmal mit einer Integerzahl als Schleifenz¨ ahler und einmal direkt nach Gauß. Die Summe der Rechenfehler bei der Fließkommaschleife ist dabei so hoch, daß die Schleife sogar einmal zuviel durchlaufen wird:
KAPITEL 7. SCHLEIFEN 49
Bildschirmausgabe:
Jetzt die Schleife mit der float-Variablen:
Summe: 52001.277344, Anzahl: 52
Jetzt die Schleife mit der int-Variablen:
Summe: 51001.269531, Anzahl: 51
Jetzt direkt nach Euler:
Summe: 51001.273438, keine Schleife!
Das Ergebnis sollte jedesmal sein: 51001.275!
Folie 32
Zwar sind alle Ergebnisse durch Rundungsfehler in der Fließkommaarithmetik nicht korrekt, die mit einer Integervariablen gesteuerte Schleife hat jedoch wenigtsens die richtige Anzahl von Schleifendurchl¨ aufen! Die Probleme lassen sich zwar durch Verwendung des Typs double statt float verkleinern jedoch letztendlich nicht l¨ osen.
KAPITEL 7. SCHLEIFEN 50
Z¨ ahlergesteuerte Schleifen sollten immer eine Integervariable als Schleifenz¨ ahler haben!!! In anderen Programmiersprachen (Pascal, Modula) ist die Verwendung einer Fließkommazahl als Schleifenz¨ ahler gar nicht erst m¨ oglich. Muß aus irgendwelchen Gr¨ unden eine Schleife uber eine Fließkommazahl laufen sollte statt der z¨ ahlergesteuerten Schleife die kopf- oder fußge¨
steuerte Schleife zum Einsatz kommen.
Die direkte Berechnung nach der Gaußschen Summenformel bringt das genaueste Ergebnis (aber selbst dieses ist nicht korrekt, da die Mantisse der Zahl 51001.275 acht Stellen lang ist und den Genauigkeitsbereich der float-Variablen mit max. sieben Stellen ¨ uberschreitet), die Summierung ¨ uber die Integer-gesteuerte Schleife bringt ein besseres Ergebnis als die Summierung ¨ uber
die Float-gesteuerte Schleife, da sich bei letzterer die Rundungsfehler in der Schleifenvariablen aufaddieren.
7.4.3 Schachtelung von z¨ ahlergesteuerten Schleifen
Ist der Schleifenk¨ orper einer Schleife selbst wieder eine Schleife so spricht mach von Schachtelung von Schleifen. Dabei wird h¨ aufig die Z¨ ahlvariable der ¨ außeren Schleife als eine der Grenzen der inneren Schleife verwendet: Struktogramm zur Ausgabe eines Dreiecks
Bildschirmausgabe:
* ** *** **** ***** ****** ******* ******** *********
KAPITEL 7. SCHLEIFEN 51
Bildschirmausgabe:
i=1
i=2 i=3 i=4 i=5 ********* i=6 *********** i=7 ************* i=8 *************** i=9 *****************
KAPITEL 7. SCHLEIFEN 52
Bildschirmausgabe:
1| 1
2| 2 3| 3 4| 4 5| 5 10 15 20 25 6| 6 12 18 24 30 36 7| 7 14 21 28 35 42 49 8| 8 16 24 32 40 48 56 64 9| 9 18 27 36 45 54 63 72 81 10| 10 20 30 40 50 60 70 80 90 100 --+---------------------------------------| 1 2 3 4 5 6 7 8 9 10
7.5 Die kopfgesteuerte Schleife
Bei der kopfgesteuerten Schleife wird die Abbruchbedingung vor dem Schleifenk¨ orper ¨ uberpr¨ uft.
Dies hat zur Folge, daß die Schleife u.U. gar nicht durchlaufen wird.
7.5.1 Syntax
In Cwird die kopfgesteuerte Schleife als while-Schleife implementiert.
Syntaxdiagramm 3: while-Schleife
¨ ¨ ¨
Beispiel: Vermutung Es existiert die Vermutung, dass die Folge von nat¨ urlichen Zahlen mit
f¨ ur jeden Startwert irgendwann die Zahl 1 erreicht.
Da die Schleife - falls der Anwender 1 eingibt - ¨ uberhaupt nicht durchlaufen werden darf ist die kopfgesteuerte Schleife die richtige Wahl:
KAPITEL 7. SCHLEIFEN 53
Uberpr¨ ufung if (3 ∗ zahl + 1 > UINT MAX) ... Die Bedingung “INT-Bereich verlassen?“ ist kritisch. Eine ¨
w¨ urde bereits w¨ ahrend der Berechnung des Ausdrucks den INT-Bereich verlassen. Daher muß die Bedingung nach den mathematischen Regeln f¨ ur Ungleichungen unter Ber¨ ucksichtigung der Integer-Berechnung umgeformt werden:
Bildschirmausgabe:
localhost:[vorlesung]> ./a.out
Geben Sie eine nat¨ urliche Zahl ein: 0 Eingabefehler! localhost:[vorlesung]> ./a.out Geben Sie eine nat¨ urliche Zahl ein: 3 Zahl 1: 10 Zahl 2: 5 Zahl 3: 16 Zahl 4: 8 Zahl 5: 4
KAPITEL 7. SCHLEIFEN 54
Zahl 6: 2
Zahl 7: 1 localhost:[vorlesung]> ./a.out Geben Sie eine nat¨ urliche Zahl ein: 3000000001 Zahlenbereich verlassen! localhost:[vorlesung]>
7.6 Die fußgesteuerte Schleife
Bei der fußgesteuerten Schleife wird die Abbruchbedingung nach dem Schleifenk¨ orper ¨ uberpr¨ uft.
Dies hat zur Folge, daß die Schleife mindestens einmal durchlaufen wird.
7.6.1 Syntax
In Cwird die fußgesteuerte Schleife als do-while-Schleife implementiert.
Syntaxdiagramm 4: do-while-Schleife
¨ ¨ ¨ ¨
Achtung: W¨ ahrend in vielen anderen Programmiersprachen am Fuß der Schleife ein Abbruchkriterium steht (repeat-until in Pascal), wird in Cstattdessen ein “Weitermachkriterium“ ausgewertet, das das logische Komplement des Abbruchkriteriums ist! Im Struktogramm (das zusammen mit Pascal entwickelt wurde) ist nur das repeat-until-Symbol vorhanden.
Beispiel: Eingabecheck Ein Programm fordert vom Anwender eine Zahl an, diese muß zwischen 1 und 10 (jeweils inclusive) liegen. Die Eingabe wird - da sie evtl. wiederholt werden mussin einer Schleife codiert. Da die Eingabe mindestens einmal erfolgen muss ist die fußgesteuerte Schleife die richtige Wahl:
Bildschirmausgabe:
Geben Sie eine Zahl zw. 1 und 10 ein: 0
Geben Sie eine Zahl zw. 1 und 10 ein: 20
KAPITEL 7. SCHLEIFEN 55
Geben Sie eine Zahl zw. 1 und 10 ein: 4
Bravo, Sie haben es geschafft!
7.7 Mischformen - Endlosschleife und Spr¨ unge
Oft ist die Abbruchbedingung weder am Kopf noch am Ende der Schleife g¨ unstig. In einem solchen Fall behilft man sich mit einer Endlosschleife die ¨ uber einen speziellen Befehl verlassen wird. Endlos-Schleife
Endlosschleife
h
Folie 38
Die Endlosschleife kann in Cmit den Konstrukten while (1) ..., do ... while (1) oder for (;;) ... programmiert werden, wobei das while- und for-Konstrukt zu bevorzugen sind, da am Schleifenbeginn die Endlosschleife abgelesen werden kann.
7.7.1 break
Der break-Befehl dient dazu, eine Schleife zu verlassen. Das Beispiel des Eingabecheck soll so ver¨ andert werden, dass nach einer Fehleingabe ein Fehlertext am Bildschirm erscheint. Mit einer
KAPITEL 7. SCHLEIFEN 56
der Standardschleifen m¨ usste folgendes progreammiert werden:
Bildschirmausgabe:
Geben Sie eine Zahl zw. 1 und 10 ein: 0
Eingabefehler!
Geben Sie eine Zahl zw. 1 und 10 ein: 4
Bravo, Sie haben es geschafft!
7.7.2 continue
Der continue-Befehl dient dazu, an den Beginn der Schleife zu springen und den n¨ achsten Schleifendurchlauf zu starten. Er wird innerhalb von z¨ ahler- und kopfgesteuerten Schleifen eingesetzt.
7.8 Tipps zur Schleifenauswahl
Welche der drei Schleifenarten gew¨ ahlt wird kann nach folgendem Struktogramm beantwortet werden:
KAPITEL 7. SCHLEIFEN 57
@ @
7.9 Beispiele
7.9.1 Berechnung aller Teiler einer Zahl
Es soll eine ganze Zahl eingegeben werden und dann alle ganzzahligen Teiler der eingegebenen Zahl berechnet und ausgegeben werden. Berechnung aller Teiler einer Zahl
KAPITEL 7. SCHLEIFEN 58
7.9.2 Beliebig viele Zahlen addieren
Ein Anwender soll Zahlen einegeben k¨ onnen und nach jeder Eingabe die Summe aller eingegebenen Zahlen sehen k¨ onnen. Zum Abbruch des Programms dr¨ uckt er die Eingabe-Ende-Taste (
7.9.3 GGT-Berechnung nach Euklid
Euklid fand heraus, daß sich die Berechnung des gr¨ oßten gemeinsamen Teilers zweier Zahlen (ganze Zahlen) sich ¨ uber Subtraktion ganz ohne Divisionen l¨ osen l¨ asst:
Algorithmus 3: Euklid
Solange die zwei Zahlen unterschiedlich sind ersetze die gr¨ oßere Zahl durch die Differenz der zwei Zahlen
Dieser Algorithmus fordert zwingend eine Schleife. Da die Zahl der Schleifendurchl¨ aufe unbekannt ist, scheidet die Z¨ ahlergesteuerte Schleife aus. Wenn die zwei Zahlen von vorneherein gleich sind (Trivialfall, kann aber in der Praxis vorkommen) darf die Schleife nicht durchlaufen werden. Daher ist die kopfgesteuerte Schleife die richtige Wahl. GGT nach Euklid
KAPITEL 7. SCHLEIFEN 59
Bildschirmausgabe:
Geben Sie zwei ganze Zahlen > 0 ein: 125 105
Zwischenergebnis: Zwischenergebnis: Zwischenergebnis: Zwischenergebnis: Zwischenergebnis: Zwischenergebnis: Zwischenergebnis: Zwischenergebnis: Zwischenergebnis:
GGT(125,105)=5
Folie 43
7.9.4 Gaußsche Summenformel
Nach Gauß gilt
Es soll ein Programm geschrieben werden, das die Gaußsche Summenformel f¨ ur die Zahlen von 1 bis 100 ¨ uberpr¨ uft, indem es die Summe ¨ uber eine Schleife berechnet und mit dem Ergebnis
KAPITEL 7. SCHLEIFEN 60
der Summenformel vergleicht. Gauß- ¨ Uberpr¨ ufung
KAPITEL 7. SCHLEIFEN 61
7.9.5 Nullstellenbestimmung nach der Mittelwertregel
Die Mittelwertregel dient dazu, n¨ aherungsweise die Nullstelle einer Funktion zu berechnen, die exakt nicht oder nur mit großem Aufwand berechenbar ist. Dazu wird von zwei x-Werten x 1 und x 2 ausgegangen, zwischen denen sich exakt eine Nullstelle befindet. Nun werden die Vorzeichen der Funktion an der Stelle x 1 und x m = (x 1 +x 2 )/2 berechnet. Sind diese Vorzeichen unteschielich so befindet sich die Nullstelle zwischen x 1 und x m , andernfalls befindet sie sich zwischen x m und x 2 . Nun folgt einer Wiederholung der Berechnung mit dem halbierten Intervall. Die Wiederholung erfolgt so lange, bis x 1 und x 2 nahe genug beieinanderliegen.
Algorithmus 4: Mittelwertregel - Nullstellen von f (x )
1. Initialisiere x 1 und x 2 so dass zwischen x 1 und x 2 genau eine Nullstelle ist und lege Δ x > 0 fest
2. Berechne x m = (x 1 + x 2 )/2, f (x1) und f (xm )
3. Wenn Vorzeichen von f (x1) und f (x1) gleich sind setze x 1 = x m sonst setze x 2 = x m
4. Wenn x 2 − x 1 > Δ x gehe zu Schritt 2, sonst fertig
Nullstellenbestimmung nach der Mittelwertregel
KAPITEL 7. SCHLEIFEN 62
Bildschirmausgabe:
1: 0.0000000000 100.0000000000 2: 0.0000000000 50.0000000000 3: 0.0000000000 25.0000000000 4: 0.0000000000 12.5000000000 5: 0.0000000000 6.2500000000 6: 0.0000000000 3.1250000000 7: 0.0000000000 1.5625000000 8: 0.7812500000 1.5625000000 9: 1.1718750000 1.5625000000 10: 1.3671875000 1.5625000000 11: 1.3671875000 1.4648437500 12: 1.3671875000 1.4160156250 13: 1.3916015625 1.4160156250 14: 1.4038085938 1.4160156250 15: 1.4099121094 1.4160156250 16: 1.4129638672 1.4160156250 17: 1.4129638672 1.4144897461 Berechnung der Nullstelle von y=x^2 - 2: Zwischen 1.413727 und 1.414490
7.9.6 Zahlenraten ¨ uber Intervallhalbierung
Der Anwender denkt sich eine Zahl, der Computer versucht diese Zahl zu erraten. Die schnellste Technik ist die Methode der Intervallhalbierung, die z.B. auch bei Suche in einem Datenfeld zum
KAPITEL 7. SCHLEIFEN 63
Einsatz kommt:
Algorithmus 5: Intervallhalbierung
1. Lege Ausgangsintervall (Grenzen links und rechts) fest
2. Berechne mitte des Intervalls
3. Wenn am Ziel dann fertig
4. Wenn L¨ osung links von der Mitte sein muss dann setze rechts = mitte, sonste setze links = mitte
5. Gehe zu Schritt 2
KAPITEL 7. SCHLEIFEN 64
KAPITEL 7. SCHLEIFEN 65
7.9.7 Primzahlenberechnung
Ein erster einfacher Algorithmus testet alle ungeraden Zahlen ab 3 bis zur oberen Grenze in einer √
Z¨ ahlergesteuerten Schleife. Innerhalb dieser Schleife wird f¨ ur jede ungerade Zahl von 3 bis getestet. Wird ein Teiler gefunden oder die obere Grenze
verlassen. Eine Merker-Variable prim dient dazu, nach der inneren Schleife die Prim-Eigenschaft anzugeben. Da die innere Schleife evtl. ¨ uberhaupt nicht durchlaufen wird (im Fall zahl = 3) ist f¨ ur die innere Schleife eine kopfgesteuerte Schleife die richtige Wahl: Primzahlen - Einfachstversion
KAPITEL 7. SCHLEIFEN 66
Bildschirmausgabe:
2 3 5 7 11 13 17 19
7.10 ¨ Ubungen
7.10.1 Zahlenraten
Schreiben Sie ein Programm bei dem sich der Computer eine Zahl zuf¨ allig sucht (Funktionen rand und srand in der Bibliothek stdlib.h) und der Anwender muss die Zahl erraten. Am Schluß soll die Zahl der Rateversuche ausgegeben werden.
7.10.2 Roulette-Simulation
Zwei Spieler gehen in ein Casino und spielen Roulette. Sie setzen immer auf “Rot“, haben aber unterschiedliche Taktiken:
Spieler 1 setzt immer 10 Euro.
Spieler 2 startet mit 10 Euro und verdoppelt seinen Einsatz immer wenn er verloren hat. Wenn er gewinnt startet er wieder mit 10 Euro
Schreiben Sie ein Simulationsprogramm, das f¨ ur 1000 Spiele den Gesamtgewinn / Gesamtverlust f¨ ur die beiden Spieler simuliert. Da die Taktik von Spieler 2 eigentlich immer zu Gewinn f¨ uhrt sch¨ utzt sich die Bank gegen diese Taktik ¨ uber ein Limit, z.B. darf der Einsatz auf “Rot“ maximal
1000 Euro betragen. In diesem Fall startet Spieler 2 - falls er durch die Verdoppelung des Einsatzes 1000 Euro ¨ ubersteigen w¨ urde - wieder mit 10 Euro. Die Wahrscheinlichkeit, dass “Rot“ kommt ist p Rot = 18 37 . In diesem Fall bekommt der Gewinner
seinen Einsatz doppelt zur¨ uck. Im Falle von “Nicht Rot“ ist der Einsatz verloren. “Nicht-Rot“ bedeutet “Schwarz“ oder “0“, da die 0 weder “Rot“ noch “Schwarz“ ist.
KAPITEL 7. SCHLEIFEN 67
Beachten Sie, dass bei der Verdoppelung der Eins¨ atze evtl. der Zahlenbreich Integer verlassen werden kann!
7.10.3 Sch¨ atzung von π nach der Monte-Carlo-Methode
Es wird auf den ersten Qudadranten (0 ≤ x ≤ 1, 0 ≤ y ≤ 1) mit einer Rechteckverteilung f¨ ur die x - und y-Werte geschossen und gez¨ ahlt, wieviele Treffer innerhalb des Einheitskreises sind. g ≈ π Mit i = Treffer innerhalb Einheitskreis und g = Schußzahl gilt i
4
7.10.4 Dezimal-Bin¨ ar-Umrechnung
Schreiben Sie ein Programm, das eine einzugebende positive Integer in das Bin¨ arformat umwandelt und ausgibt.
7.10.5 Nimm-Spiel
Zwei Spieler nehmen von einem 21 Z¨ undh¨ olzer umfassenden Stapel abwechselnd ein bis vier Z¨ undh¨ olzer weg.
1. Entwickeln Sie ein Programm, das einen der zwei Spieler simuliert, so dass jemand gegen den Computer spielen kann.
2. Verallgemeinern Sie Ihr Programm so, daß s (anf¨ angliche Stapelh¨ ohe), n (max. wegnehmbare Z¨ undh¨ olzer) und wer den ersten Zug macht eingegeben werden kann.
Gewinnstrategie: 1. Setze zug = s modulo (n+1)
2. Wenn zug > 0 gilt, dann nimm zug Streichh¨ olzer vom Stapel. Ansonsten besteht sowieso keine Chance, in eine Gewinnposition zu kommen. Nimm deshalb eine beliebige Menge von Streichh¨ olzern (zwischen 1 und n).
Kapitel 8
Zeiger
8.1 Zeiger
8.2 Einf¨ uhrung
Variablen werden vom C-Compiler irgendwo im Hauptspeicher abgelegt. W¨ ahrend der Programmierer ¨ ublicherweise ¨ uber den Variablennamen auf eine Variable zugreift, kann auch ¨ uber die
Adresse einer Variablen im Hauptspeicher auf diese Variable zugegriffen werden.
Hauptspeicheradressen sind immer positive ganze Zahlen.
Der Nutzen von Zeigern ist die Call-By-Reference bei der modularen Programmierung, dynamische (zur Laufzeit des Programms erzeugte) Felder und dynamische Datenstrukturen.
8.3 Operatoren f¨ ur Zeiger
Die Adresse einer Variablen erh¨ alt man ¨ ubder den Adessoperator &. Soll bei einem Zeiger
nicht der Wert des Zeigers, sondern der Wert der Hauptspeicheradresse auf die der Zeiger zeigt ver¨ andert werden so ist ein Zeigeroperator * voranzustellen.
8.4 Hauptspeichermodell
Im folgenden Beispiel wird mit vier Variablen - zwei Integern und zwei Zeigern auf Integer - gearbeitet. Die Adressen der Variablen werden ab der Hauptspeicheradresse 1000 vermutet. Welche Adresse tats¨ achlich verwendetg wird h¨ angt von Compiler, Betriebssystem und weiteren Faktoren ab, der Programmierer hat keinerlei Einfluß darauf.
KAPITEL 8. ZEIGER 69
Kapitel 9
Modulare Programmierung
9.1 Einf¨ uhrung
Doppelt programmierte Ausgabe
In obigem Struktogramm wiederholt sich der Ausgabeblock drei mal, er muß also dreimal editiert werden und im Falle von ¨ Anderungen auch dreimal ver¨ andert. Nun wird dieser Block in ein Unterprogramm ausgabe() ausgelagert, welches aus dem Hauptprogramm heraus dreimal aufgerufen wird: Unterprogramm ausgabe
9.1.1 Syntax eines Unterprogramms
Allgemein besteht ein C-Programm aus mehreren Funtionen (Unterprogrammen). Genau eine Funktion muß den Namen main tragen. Je nachdem, ob der Funktion main aus dem Betriebssystem heraus Parameter ¨ ubergeben werden bzw. ob das Programm an das Betriebssystem einen
KAPITEL 9. MODULARE PROGRAMMIERUNG 71
R¨ uckgabewert ¨ ubermittelt (unter Unix ¨ ublich) lautet die Schnittstelle f¨ ur main unterschiedlich:
void
main ( )
{
/ / Keine P a r a m e t e r ¨
u b e r g a b e , k e i n e R¨ uckgabe
void
main (
i n t
,
char
∗
)
{
/ / P a r a m e t e r ¨
i n t
main (
i n t
,
char
∗
)
{
/ / Kein P a r a m e t e r ¨
i n t
main (
i n t
,
char
∗
)
{
/ / P a r a m e t e r ¨ Unterprogramm main
Vorteile von modularer Programmierung:
• Wiederkehrende Programmbl¨ ocke m¨ ussen nur einmal implementiert werde, daraus folgt auch weniger Wartungsaufwand
• Die Kapselung von Daten erm¨ oglicht unabh¨ angige Entwicklung der Module
• Module k¨ onnen wiederverwendet werden (engl. reusable code)
Beispiel: Es sollen ein Programm geschrieben werden, welches drei Fliesskommazahlen einliest und die Mittelwerte aller m¨ oglichen Zahlenpaare ausgibt.:
Dieselbe Aufgabe gel¨ ost mit einem selbstgeschriebenen Modul mittelwert:
KAPITEL 9. MODULARE PROGRAMMIERUNG 72
Im Modul main gibt es keine Anweisungen mehr wie der Mittelwert zu berechnen ist sondern nur noch daß der Mittelwert zu berechnen ist. Diese Anweisungen wie der Mittelwert zu berechnen ist sind vollkommen gekapselt im Modul mittelwert:
9.2 Die Schnittstelle
Der Datenaustausch zwischen einem aufrufendem Programm und einem aufgerufenen Modul wird ¨ uber die Schnittstelle geregelt. Beide am Aufruf beteiligten Module m¨ ussen ausser dieser Schnittstelle nichts vom anderen Modul wissen.
double mittelwert(double a, double b) {
double m = (a + b) / 2;
return m; }
¢ ¢ ¢ ¢ ¢ ¢ void main() { ¢
... ¢ ¢ m1 = mittelwert(z1, z2)
Folie 55
Die Pfeile symbolisieren die Wert¨ ubergabe, d.h. im Modul mittelwert bekommt die Variable a den Wert der Variablen z1 aus dem Modul main, b bekommt den Wert von z2. Bei der R¨ uckgabe
KAPITEL 9. MODULARE PROGRAMMIERUNG 73
wird der Wert der Variablen m aus dem Modul mittelwert an die Variable m1 im Modul main zur¨ uckgegeben.
9.3 Prototypen
Der C-Compiler compiliert den Quellcode von oben nach unten. Alle Funktionen m¨ ussen vor ihrem Aufruf deklariert werden. Da - indbesondere bei indirekter Rekursion - nicht immer eine Reihenfolge gefunden werden kann, wurde in C die Tehcnik der Prototypen eingef¨ uhrt.
Ein Prototyp besteht aus einer normalen Funktionsdeklaration, wobei statt des Funktionsblocks ein “;“ steht und die Variablennamen in der Schnittstelle weggelassen werden k¨ onnen.
Syntaxdiagramm...
9.4 G¨ ultigkeitsbereich von Variablen
9.4.1 Variablen
Wird in C eine Funktion aufgerufen, so legt der Compiler die Variablen der Funktion neu an. Dabei ist es egal, ob es sich Variablennamen der Funktion mit den Variablenname der anderen Funktionen ¨ uberschneiden oder nicht.
9.4.2 Lokale Variablen
9.4.3 Statische Variablen
Statische Variablen werden ¨ uber das Schl¨ usselwort static augezeichnet. Sie unterscheiden sich folgendermaßen von “normalen“ (dynamischen) Variablen:
• Sie werden beim ersten Aufruf der Funktion automatisch mit dem Wert 0 initialisiert.
• Wenn eine Funktion wiederholt aufgerufen wird so beh¨ alt die statische Variable zwischen den Funntionsaufrufen ihren Wert.
Listing 9.3: Unterschied zwischen normalen und statischen Variablen
KAPITEL 9. MODULARE PROGRAMMIERUNG 74
Bildschirmausgabe:
modul_d() wird zum 1. mal aufgerufen!
modul_s() wird zum 1. mal aufgerufen!
modul_d() wird zum 1. mal aufgerufen!
modul_s() wird zum 2. mal aufgerufen!
modul_d() wird zum 1. mal aufgerufen!
modul_s() wird zum 3. mal aufgerufen!
modul_d() wird zum 1. mal aufgerufen!
modul_s() wird zum 4. mal aufgerufen!
modul_d() wird zum 1. mal aufgerufen!
modul_s() wird zum 5. mal aufgerufen!
9.5 Globale Variablen
Variablen k¨ onnen in C auch außerhalb der einzelnen Funktionen deklariert werden. Sie gelten dann in allen Funktionen, die im Zuge der Compilierung nach der Deklaration kommen.
Global deklarierte Variablen werden gerne als Schnittstelle zwischen Modulen eingesetzt. Bei aller Einfachheit wird dabei jedoch das Prinzip der Kapselung in der Strukturierten Programmierung verletzt. Eine saubere Schnittstelle ist oft die bessere Wahl.
9.6 Call-by-value und Call-by-Reference
9.6.1 Call-by-value
Als ¨ Ubergabeparameter sind beim Call-by-value auch Konstanten m¨ oglich, dies ist bei Call-byreference nicht m¨ oglich, es erscheint ein Compilerfehler.
9.6.2 Call-by-reference
Unter “Call-by-reference“ vesteht man den Mechanismus, daß an ein Unterprogramm nicht der
Wert einer Variablen sondern die Adresse einer Variablen ¨ ubergeben wird. Pascal und C++ un-
terst¨ utzen echtes Call-by-reference, in C muss dieser Vorgang ¨
Da Adressen von Variablen ¨ ubergeben werden sind keine Konstanten zul¨ assig.
KAPITEL 9. MODULARE PROGRAMMIERUNG 75
Bildschirmausgabe:
Ausgangswerte: x=1.200000 y=2.700000
swap_by_value: x=1.200000 y=2.700000 swap_by_ref : x=2.700000 y=1.200000
In dem Beispiel kommt der sog. Dreieckstausch zum Einsatz:
¡ a
9.7 Module
H¨ aufig werden zusammengeh¨ orende Funktionen zu sog. Modulen zusammengefasst. Ein Modul besteht ¨ ublicherweise aus zwei Dateien:
KAPITEL 9. MODULARE PROGRAMMIERUNG 76
1. Die Implementierungsdatei enth¨ alt die Implementierung der Funktionen. Diese Datei hat die Endung “.c“
2. Die Header-Datei enth¨ alt die Funktionsprototype und evtl. Pr¨ aprozessor-Konstanten. Diese Datei hat die Endung “.h“.
Hauptprogramm und Modul k¨ onnen nun getrennt entwickelt und kompiliert werden:
Die Compilierung erfolgt nun gemeinsam:
> gcc module_vektorrechnung_main.c module_vektorrechnung.c
9.8 Beispiele
9.8.1 GGT nach Euklid
Ein Modul GGT ben¨ otigt zur Berechnung des gr¨ oßten gemeinsamen Teilers zweier Zahlen diese zwei Zahlen (Datentyp Integer) und gibt eine Integerzahl zur¨ uck. int ggt(int a, int b)
KAPITEL 9. MODULARE PROGRAMMIERUNG 77
main()
9.8.2 Mittelwertregel
Bei der Mittelwertregel wird die ¨ Anderung des Programms zur Anpassung an andere Funktionen
einfacher, da die math. Funktion nur noch einmal - im C-Modul f - programmiert werden muss:
KAPITEL 9. MODULARE PROGRAMMIERUNG 78
9.8.3 Prim-Eigenschaft einer ganzen Zahl
KAPITEL 9. MODULARE PROGRAMMIERUNG 79
9.8.4 Drehen eines zweidimensionalen Vektors
Es soll ein Modul geschrieben werden, welches eine Drehung eines zweidimensionalen Vektors durchf¨ uhrt. Die Drehung erfolgt durch Multiplikation der Drehmatrix mit dem Vektor:
Dabei sind x 1 und y 1 die Koordinaten des Ausgangsvektors, α der Drehwinkel und x 2 und y 2 die Koordinaten des gedrehten Vektors. Ohne Nutzung der Matrixschreibweise lauten die Formeln:
Dieses Modul ben¨ otigt als Eingangsparameter X- und Y-Wert des Vektors und muss X- und Y-Wert auf irgendeine Art und Weise zur¨ uckgeben.
Da ein einfacher Modulaufruf mit Call-by-value und Return-Wert nicht geht sollen zwei L¨ osungsm¨ oglichkeiten gezeigt werden:
1. Aufruf und Wert¨ ubergabe der Vektorkoordinaten Call-by-reference
2. L¨ osung ¨ uber eine Struktur vektor, die X- und Y-Koordinate beinhaltet und als Returnwert zur¨ uckgegeben werden kann.
KAPITEL 9. MODULARE PROGRAMMIERUNG 80
KAPITEL 9. MODULARE PROGRAMMIERUNG 81
9.9 Aufgaben
9.9.1 Zufallszahl
Entwickeln Sie eine Funktion int zufallszahl (int , int) die als Parameter durch zwei Int-Zahlen einen Bereich bekommt und eine Zufallszahl in diesem Bereich zur¨ uckliefert. Beim allerersten Aufruf von zufallszahl soll zudem der Zufallszahlengenerator per srand(time(NULL)) initialisiert werden.
Kapitel 10
Strukturierte Datentypen
10.1 Konstanten
H¨ aufig kommen in Programmen an mehreren Stellen Zahlenwerte mit derselben Bedeutung vor. So wird etwa ein Programm zur Berechnung der Flugbahn einer Rakete mehrfach die physikalische Konstante g (Erdanziehung) mit dem numerischen Wert 9.81 ben¨ otigen. in C gibt es nun mehrere M¨ oglichkeiten, dies zu l¨ osen.
1. An mehreren Stellen kommt die Zahl 9.81 als Konstante vor. Dies macht das Programm unleserlich. Ausserdem m¨ usste - falls sich aus irgendeinem Grund der Wert der Konstante einmal ¨ andert - das Programm vor der Neucompilierung an vielen Stellen ver¨ andert werden.
2. Der Wert von 9.81 wird in einer Pr¨ aprozessor-Konstanten gehalten:
#d e f i n e g 9.81
i n t main ( ) { . . . e = m ∗ g ∗ h ; }
3. Der Wert von 9.81 wird in einer Variablen gehalten:
i n t main ( ) {
double g = 9.81 . . . e = m ∗ g ∗ h ; }
4. Der Wert von 9.81 wird in einer Variablen gehalten:
i n t main ( ) {
double g = 9.81 . . . e = m ∗ g ∗ h ; g = 2; // Gef¨ a h r l i c h ! ! ! ! }
5. Der Wert von 9.81 wird in einer Konstanten gehalten:
i n t main ( ) {
const double g = 9 . 8 1
KAPITEL 10. STRUKTURIERTE DATENTYPEN 83
. . .
e = m ∗ g ∗ h ;
g = 2 ; / / C o m p i l e r−F e h l e r ! ! ! }
10.2 Aufz¨ ahlungen
enum { k r e u z , p i k , h e r z , k a r o } ;
/ ∗ S e l b e Wirkung wie c o n s t i n t k r e u z = 0 ; c o n s t i n t p i k = 1 ; c o n s t i n t h e r z = 2 ; c o n s t i n t k a r o = 3 ; ∗ /
enum { k a r o =9, h e r z , p i k , k r e u z } ;
/ ∗ S e l b e Wirkung wie c o n s t i n t k r e u z = 1 2 ; c o n s t i n t p i k = 1 1 ; c o n s t i n t h e r z = 1 0 ; c o n s t i n t k a r o = 9 ; ∗ /
enum { k a r o =9, h e r z =10, p i k =11, k r e u z =12};
/ ∗ S e l b e Wirkung wie c o n s t i n t k r e u z = 1 2 ; c o n s t i n t p i k = 1 1 ; c o n s t i n t h e r z = 1 0 ; c o n s t i n t k a r o = 9 ; ∗ /
10.3 Felder
Oft muss eine gr¨ oßere Zahl von Variablen gespeichert werden. Hierzu bieten sich Felder an. Bei einem Feld handelt es sich um eine indizierte Variable, wobei der Index eine nat¨ urlich Zahl ist. In
KAPITEL 10. STRUKTURIERTE DATENTYPEN 84
Cgehen die Werte des index immer von 0 bis (anzahl-1). Das folgende Programm liest 5 Zahlen ein und gibt sie in umgekehrter Reihenfolge wieder aus:
Bildschirmausgabe:
Geben Sie die 0. Zahl ein: 1
Geben Sie die 1. Zahl ein: 5 Geben Sie die 2. Zahl ein: 3 Geben Sie die 3. Zahl ein: 7 Geben Sie die 4. Zahl ein: 6 Sie haben als 4. eingegeben: 6 Sie haben als 3. eingegeben: 7 Sie haben als 2. eingegeben: 3 Sie haben als 1. eingegeben: 5 Sie haben als 0. eingegeben: 1
10.3.1 Feldgrenzen
In C obliegt es dem Programmierer, auf die Einhaltung von Feldgrenzen zu achten. Wird der Index-Bereich eines Feldes verlassen so entstehen Artefakte, es k¨ onnen andere Variablen ver¨ andert werden, Speicherabst¨ urze entstehen etc.
Im folgenden Beispiel werden zwei Character-Arrays angelegt und das zweite Array wird unter Nichteinhaltung der Feldgrenzen ver¨ andert:
KAPITEL 10. STRUKTURIERTE DATENTYPEN 85
Bildschirmausgabe:
Wort1 Wort2 ’Hallo’ ’Welt!!!’ ’HalZo’ ’Welt!!!’ ’HalZo’ ’Welt!!! HalZo’
10.3.2 Initialisierung von Feldern
10.4 Zeichenketten (Strings)
Programme m¨ ussen oft nicht nur Zahlen als Variablen f¨ uhren sondern auch Texte. Dazu gibt es in vielen Programmiersprachen den Datentyp “string“. In C stehen lediglich Zeichenfelder -Character-Arrays - zur Verf¨ ugung.
Um trotzdem einigermaßen komfortabel mit Strings arbeiten zu k¨ onnen stehen in der Bibliothek string.h Funktionen zur Stringverarbeitung zur Verf¨ ugung.
10.4.1 Die Funktionen zur Stringverarbeitung
char *strcpy(char *dest, const char *src); Die Funktion strcpy() kopiert die Zeichenkette, auf die der Zeiger src zeigt, inklusive des Endezeichens an die Stelle, auf die dest zeigt. Die Zeicheketten d¨ urfen sich nicht ¨ uberlappen und dest muß groß genug sein.
char *strncpy(char *dest, const char *src, size t n); Die Funktion strncpy() tut dasselbe wie strcpy mit dem Unterschied, daß nur die ersten n Byte von src kopiert werden. Ist kein Endezeichen innerhalb der ersten n Bytes,so wird das Ergebnis nicht durch das Endezeichen abgeschlossen.
strcat
KAPITEL 10. STRUKTURIERTE DATENTYPEN 86
strncat
strchr
strrchr
strcmp
strncmp
atoi
atof
sprintf
sscanf
10.4.2 Einlesen von Strings
Die Funktion scanf aus der Bibliothek stdio.h liest Strings separiert durch Leer- und Tab-Zeichen ein (also genaugenommen Worte). Soll ein String mit Leerzeichen eingelesen werden so sind die Funktionen gets bzw. fgets zu verwenden.
Da Felder und Zeiger ¨ aquivalent sind ist beim scanf-Befehl f¨ ur Strings kein Adressoperator n¨ otig!
10.4.3 Parsen von Strings
Unter einem Parser versteht man ein Programm, welches einen Eingabetext in seine Bestandteile -W¨ orter - zerlegt. Oft werden diese W¨ orter auf verschiedene Wortarten untersucht, diesen Vorgang nennt man die lexikalische Analyse (siehe Compilerbau). Das folgende Programm macht noch keine lexikalische Anlayse sondern zerlegt lediglich den Eingabetext in die einzelnen W¨ orter, wobei die Worte durch Leerzeichen und Tab-Zeichen getrennt sein d¨ urfen und sowohl vor dem ersten als auch nach dem letzten Wort diese Trennzeichen erlaubt sind.
Aus einem String kann mit der Funktion sscanf (string-scan-formatted) wortweise gelesen werden. Trennzeichen werden zwar ignoriert, m¨ ussen jedoch - um den Start-Zeiger korrekt vorsetzen zu k¨ onnen, manuell ¨ uberlesen werden.
KAPITEL 10. STRUKTURIERTE DATENTYPEN 87
Die Funktion parser() setzt bei ihrem allerersten Aufruf den Zeiger p auf den Anfang des Eingabetextes und liest das erste Wort. Bei jedem weiteren Aufruf wird das n¨ achste Wort gelesen und zur¨ uckgegeben, bis der Parser am EIngabeende angelangt ist. Ein Nachteil des Vorliegenden Parsers soll nicht unerw¨ ahnt bleiben: Die Funktion parser() kann pro Programmlauf nur einen Eingabetext zerlegen. Soll ein zweiter Eingabetext zerlegt werden (neudeut “geparsed“) so muss durch irgendeine Konstruktion der Zeiger p zur¨ uckgesetzt werden.
10.4.4 Kommandozeilenparameter
Oft m¨ ussen C-Programme aus der Kommandozeile des Betriebssystems heraus Parameter ¨ ubernehmen und verarbeiten. Als Beispiel seien die Dateikoperprogramme cp unter Unix und copy unter DOS/Windows genannt. Diese Programme erhalten von der Kommandozeile mindestens zwei Parameter, n¨ amlich Quell- und Zieldatei.
Um Kommandozeilenparameter zu verarbeiten, muß das Modul main zwei Parameter ¨ ubernehmen, n¨ amlich erstens eine Integer-Variable, die die Zahl der Parameter angibt und zweitens einen Zeiger auf einzweidimensionales Character-Feld:
Der erste Parameter (Nummer 0) ist immer der Programmaufruf, alle weiteren Parameter werden angeh¨ angt:
Bildschirmausgabe:
localhost:[vorlesung]> gcc datentypen2_kommandozeile.c
KAPITEL 10. STRUKTURIERTE DATENTYPEN 88
localhost:[vorlesung]> ./a.out Hier kommen "die Parameter" 4 Parameter ¨ ubergeben: Parameter 0: ’./a.out’ Parameter 1: ’Hier’ Parameter 2: ’kommen’ Parameter 3: ’die Parameter’ localhost:[vorlesung]>
10.5 Strukturen
KAPITEL 10. STRUKTURIERTE DATENTYPEN 89
10.6 Zeiger und Strukturen
Wird mit Zeigern auf Strukturen gearbeitet (siehe Funktion “student sort()“) ergeben Probleme: In der Reihenfolge der Operatoren wird der .-Operator vor dem *-Operator ausgewertet. Wird also ein Zeiger auf eine Struktur verwendet, so w¨ urde in dem Ausdruck *p.x implizit eine Klammersetzung *(p.x) erfolgen was falsch w¨ are (in diesem Fall wird p.x als Zeiger betrachtet. Daher muß explizit eine Klammersetzung erfolgen: (*p).x. Da dies Megraufwand und Fehleranf¨ alligkeit bedeutet gibt es den Pfeil-Operator -> der Zeiger und Struktur vereint: p->x.
10.7 Dynamische Felder
Ein großes Problem bei Feldern ist die Tatsache, dass die Feldgr¨ oße bereits zum Zeitpunkt der Compilierung festgelegt werden muß.
Eine andere M¨ oglichkeit besteht darin, den Speicher erst zur Laufzeit des Programms zu belegen. Felder k¨ onnen daher so groß angelegt werden wie sie zur Laufzeit des Programms tats¨ achlich n¨ otig sind.
10.7.1 Zeiger-Arithmetik
In C sind Zeiger typisiert, d.h. ein Zeiger auf eine Integer-Variable wird etwas anders behandelt als ein Zeiger auf eine Fließkommavariable.
10.7.2 Eindimensionale dynamische Felder
KAPITEL 10. STRUKTURIERTE DATENTYPEN 90
10.7.3 Mehrdimensionale dynamische Felder
Im Hauptspeicher des Computers wird dieses zweidimensionale Feld als eindimensionales Feld abgelegt:
Babei berechnet such der eindimensionale Index aus den zwei Indizes des zweidimensionalen Feldes nach der Formel index = 4 ∗ zeile + spalte.
Wird nun mit dynamischen mehrdimensionalen Feldern gearbeitet muss man sich um die Berechnung der Speicheradresse aus den einzelnen Indizes des (subjektiv) mehrdimensionalen Feldes selber k¨ ummern. Idealerweise legt man sich eine Funktion index oder - noch besser - eine parameterisierte Pr¨ aprozessorersetzung an. Diese hat den Vorteil, dass zur Laufzeit des Programms nicht jedesmal zur Indesberechnung in ein Unterprogramm gesprungen wird.
KAPITEL 10. STRUKTURIERTE DATENTYPEN 91
10.8 Eigene Typen
Mit dem Sch¨ usselwort typedef lassen sich aus Strukturen und Aufz¨ ahlungen eigene Typen machen. Dadurch kann bei Bezug auf diese Typen das Schl¨ usselwort struct bzw. enum weggelassen werden. Ohne typedef
s t r u c t v e k t o r {
double x ; double y ; } ;
s t r u c t v e k t o r f [ 1 0 ] ;
s t r u c t v e k t o r v e k t o r a d d ( s t r u c t v e k t o r v1 , s t r u c t v e k t o r v2 ) ;
Mit typedef
typedef s t r u c t {
double x ; double y ;
} v e k t o r ; / / v e k t o r i s t j e t z t e i n e i g e n e r z u l ¨ a s s i g e r Typ v e k t o r f [ 1 0 ] ;
v e k t o r v e k t o r a d d ( v e k t o r v1 , v e k t o r v2 ) ;
typedef enum { k a r o =9, h e r z , p i k , k r e u z } f a r b e ;
f a r b e f ;
f o r ( f = karo ; f <= k r e u z ; f++)
. . .
KAPITEL 10. STRUKTURIERTE DATENTYPEN 92
typedef char s t r i n g [ 2 5 5 ] ;
s t r i n g s1 , s2 ;
10.9 Beispiele
10.9.1 Primzahlberechnung “Sieb des Eratosthenes“
Eratosthenes (griechischer Mathematiker, ca. 200 v. Chr.) ersann folgenden Algorithmus, um alle Primzahlen von 3 bis zu einer Zahl N zu berechnen:
Algorithmus 6: Sieb des Eratosthenes
Ausgangslage: F¨ ur alle ungeraden Zahlen von 3 bis 39 wird eine 1 gespeichert:
F¨ ur die Zahl 3 ist eine 1 gespeichert, daher Ausgabe der Zahl und alle ungeraden Vielfachen von 3 werden auf 0 gesetzt:
F¨ ur die Zahl 5 ist eine 1 gespeichert, daher Ausgabe der Zahl und alle ungeraden Vielfachen von 5 werden auf 0 gesetzt:
F¨ ur die Zahl 7 ist eine 1 gespeichert, daher Ausgabe der Zahl und alle ungeraden Vielfachen von 5 werden auf 0 gesetzt:
F¨ ur die Zahl 9 ist eine 0 gespeichert, sie ist daher keine Primzahl:
Implementierung 1 verwendet ein Character-Array mit N Elementen. Da nur die ungeraden Zahlen von 3 bis N verarbeitet werden wird ca. 50 % Speicher verschwendet:
KAPITEL 10. STRUKTURIERTE DATENTYPEN 93
10.9.2 Primzahlberechnung ¨ uber Primfaktorentest
10.10 ¨ Ubungen
10.10.1 Textformatierung
Entwickeln Sie ein Programm, welches den Input aus der Standardeingabe in Blocksatz formatiert. Die Blocksatzbreite soll als Parameter ¨ ubergeben werden k¨ onnen, wird sie nicht ¨ ubergeben so gilt der Defaultwert 72.
KAPITEL 10. STRUKTURIERTE DATENTYPEN 94
10.11 Minesweeper
Schreiben Sie ein Programm f¨ ur das bekannte Spiel “Minesweeper“. Die Angabe des Feldes auf das man zieht erfolgt per Tastatur, das Spielfeld soll 8*8 Felder groß sein, die Zahl der Minen soll eingegeben werden k¨ onnen.
10 Bomben!
+--------+ +--------+
8| 7| 6| 5| 4| 3| 2| 1| +--------+ +--------+ ABCDEFGH ABCDEFGH Zug 1: a1 Zug 2:
10.12 Datums-Check
Schreiben Sie eine Funktion int datum ok(char ∗ text); welche den ¨ ubergebenen Text ¨ uberpr¨ uft.
Handelt es sich um ein korrektes Datum (z.b. “01.01.1970“) so soll eine 0 zur¨ uckgegeben werden, andernfalls eine 1. Diese Funktion soll wiederum eine Funktion int schaltjahr (int jahr );’ benutzen welche im Falle eines Schaltjahrs eine 0 und andernfalls eine 1 zur¨ uckgibt.
10.13 Bin¨ ar-Dezimal-Umwandlung
Schreiben Sie ein Programm, das eine einzugebende Bin¨ arzahl in das Dezimalsystem umrechnet und ausgibt.
10.14 Game of life
Implementieren Sie Conway’s “Game of life“.
Kapitel 11
Sortieren
11.1 Einf¨ uhrung
Daten w¨ aren ohne sinnvolle Sortierung in einem Datenfriedhof begraben. Stellt man sich vor, man m¨ usse in einem unsortierten Telefonbuch nach einer Nummer suchen, so erkennt man schnell die Sinnlosigkeit des Unterfangens. Man erkennt auch, daß f¨ ur die Suche des Teilnehmers zu einer bekannten Telefonnummer das g¨ angige Telefonbuch keine Hilfe bietet.
Computer suchen zwar in unsortierten Daten schneller als Menschen, trotzedem macht eine Sortierung aus Performancegr¨ unden Sinn.
11.2 Bubble-Sort
Algorithmus 7: Bubble-Sort
• Wiederhole (n-1) mal
- Vergleiche jedes Element mit dem n¨ achsten und tausche falls falsch sortiert
Bubble-Sort mit n Zahlen
KAPITEL 11. SORTIEREN 96
Bildschirmausgabe:
Durchgang 0: 9 1 5 2 4 3 8 0
Durchgang 1: 1 5 2 4 3 8 0 9 Durchgang 2: 1 2 4 3 5 0 8 9 Durchgang 3: 1 2 3 4 0 5 8 9 Durchgang 4: 1 2 3 0 4 5 8 9 Durchgang 5: 1 2 0 3 4 5 8 9 Durchgang 6: 1 0 2 3 4 5 8 9 Durchgang 7: 0 1 2 3 4 5 8 9
Folie 60
Man kann erkennen, dass die großen Zahlen sehr schnell sortiert sind (die 9 steht bereits nach dem ersten Durchlauf an der richtigen Stelle, die 8 nach dem zweiten, ...), kleine Zahlen aber sehr langsam unten einsortiert werden, die 0 steht erst nach dem letzten Druchlauf an der richtigen Stelle. Die Zahl 4, die eigentlich bereits am Anfang an der richtigen Stelle steht wird erst zwei Stellen nach links und dann wieder zwei Stellen nach rechts sortiert. Daran erkennt man, dass dieser Algorithmus zwar einfach aber ineffizient ist.
An der Art und Weise, wie die kleinen Zahlen nach links sortiert werden, orientiert sich der Name dieses Algorithmus.
KAPITEL 11. SORTIEREN 97
11.3 Sortieren durch direktes Tauschen
Die schlechte Effizienz des Bubble-Sort-Algorithmus resultiert aus der hohen Zahl von Vertauschungen, die im Lauf der Sortierung u.U. sogar wieder r¨ uckg¨ angig gemacht werden. Es klingt plausibel, dass eine Effizienz-Steigerung dadurch erreicht werden kann, wenn man nur sinnvolle Vertauschungen vornimmt.
Algorithmus 8: Sortieren durch direktes Tauschen
Der Algorithmus des “Sortierens durch direktes Tauschen“ sucht im gesamten Feld das kleinste Element und stellt es an die erste Stelle. Dann wird ab dem zweiten Element das kleinste Element gesucht und an die zweite Stelle getauscht usw.
Die Zahl der Tauschvorg¨ ange ist bei n Zahlen damit maximal n − 1, die Zahl der Vergleiche n−1
i=1 i = 1 2 ∗ n ∗ (n − 1) 1 + 2 + ... + (n − 2) + (n − 1) =
Sortieren durch direktes Tauschen
KAPITEL 11. SORTIEREN 98
Bildschirmausgabe:
Durchgang 0: 9 1 5 2 4 3 8 0 Durchgang 1: 0 1 5 2 4 3 8 9 Durchgang 2: 0 1 5 2 4 3 8 9 Durchgang 3: 0 1 2 5 4 3 8 9 Durchgang 4: 0 1 2 3 4 5 8 9 Durchgang 5: 0 1 2 3 4 5 8 9 Durchgang 6: 0 1 2 3 4 5 8 9 Durchgang 7: 0 1 2 3 4 5 8 9
Folie 62
KAPITEL 11. SORTIEREN 99
11.4 Quicksort
void quicksort(int links, int rechts)
11.5 Beispiele
11.5.1 Studentenverwaltung
F¨ ur die Studentenverwaltung soll ein Programm geschrieben werden, mit dem eine beliebige Anzahl von Studenten erfasst werden kann. NAch der Erfassung erfolgt eine Sortierung nach Nachname und - bei gleichem Nachnamen - nach Vorname als zweitem Sortierkriterium.
KAPITEL 11. SORTIEREN 100
Kapitel 12
Dateiverarbeitung
12.1 Einf¨ uhrung
Programme m¨ ussen oft Daten auch ¨ uber die Einschaltzeit des Computers hinaus speichern.
Dazu m¨ ussen die Daten auf nichtfl¨ uchtige Speichermedien im Computer - meist Festplatten oder Disketten - gespeichert werden.
Bei intensiver Nutzung von Daten ist irgendwann jedoch der Schritt vom dateibasierten Programm zu einem datenbankbasierten Programm unter Nutzung einer kommerziellen Datenbank sinnvoll.
12.2 ¨ Offnen und schließen
Analog zu den Schreib- und Lesebefehlen printf und scanf gibt es Befehle zum Schreiben in bzw. Lesen aus Dateien. Zus¨ atzlich zur normalen Bildschirmausgabe und Tastatureingabe (die ab sofort Standardausgabe bzw. Standardeingabe heissen) m¨ ussen Dateien jedoch vor Schreib-und Lesezugriffen ge¨ offnet und nach den Zugriffen wieder geschlossen werden. Beim Lesen aus Dateien kann evt. die Datei zu Ende sein.
Alle vorgestellten Befehle zur Dateiverabeitung befinden sich in der Bibliothek stdio.h. Die Pfade der Dateien sind in Unix-Notation geschrieben.
12.2.1 Standard-Dateien
Unter Csind die folgenden drei Dateien immer ge¨ offnet:
stdin Eingabe, normalerweise Tastatur
stout Ausgabe, normalerweise Bildschirm
sterr Fehlerausgabe, normalerweise Bildschirm
Diese Dateien k¨ onnen durch Ein- und Ausgabeumleitung bzw. die Betriebssystem-Pipe ver¨ andert werden.
12.2.2 Datei ¨ offnen
Zum ¨ Offnen von Dateien dient die Funktion file * fopen(char * pfad, char *modus):
KAPITEL 12. DATEIVERARBEITUNG 103
FILE ∗ d a t e i ;
d a t e i = f o p e n ( ”/ e t c / h o s t s ” , ” r ” ) ;
Der erste Parameter ist der Pfad der Datei in einer im Betriebssystem ¨ ublichen Notation, also etwa
/home/meinverzeichnis/text.txt unter Unix oder c:\Eigene_Dateien\test.txt unter Microsoft-Betriebssystemen.
Achtung unter Microsoft-Betriebssystemen: Da der Backslash in C-Strings ein Sonderzeichen einleitet (etwa "\n" f¨ ur Neue Zeile ) muss f¨ ur einen echten Backslash dieser im C-Quellcode doppelt einegegeben werden (Bsp. "c:\\Eigene_Dateien\\test.txt").
Der zweite Parameter gibt den Zugriffsmodus an:
Falls die Datei nicht wie gew¨ unscht ge¨ offnet werden kann (Lesemodus bei nicht vorhandener Datei oder fehlende Rechte unter Unix) so hat der zur¨ uckgegebene Zeiger den Wert NULL:
FILE ∗ d a t e i ;
d a t e i = f o p e n ( ”/ e t c / h o s t s ” , ” r ” ) ; i f ( d a t e i == NULL) {
p r i n t f ( ” D a t e i konnte n i c h t g e ¨ o f f n e t werden ! ” ) ; r e t u r n ; }
12.2.3 Datei schliessen
Nachdem eine Datei bearbeitet wurde muss sie wieder geschlossen werden. Dies ist bei Schreibzugriffen auf Dateien besonders wichtig. Dazu dient die Funktion fclose(file *datei).
FILE ∗ d a t e i ;
d a t e i = f o p e n ( ”/ e t c / h o s t s ” , ”w” ) ; f c l o s e ( d a t e i ) ;
12.2.4 Unformatierte Ein- / Ausgabe
fread
fwrite
12.2.5 Positionierungsbefehle
fseek
ftell
Formatierte Ein- / Ausgabe
Analog zur Funktion scanf gibt es die Funktion fscanf (file-scan-formatted) um aus Dateien zu lesen:
KAPITEL 12. DATEIVERARBEITUNG 104
FILE ∗ d a t e i ;
i n t z a h l ;
d a t e i = f o p e n ( ”/ e t c / h o s t s ” , ” r ” ) ; f s c a n f ( d a t e i ,”%d”,& z a h l ) ; p r i n t f ( ”Aus D a t e i g e l e s e n : %d” , z a h l ) ; f c l o s e ( d a t e i ) ;
Zeilenweises einlesen
Im Gegensatz zum formatierten Einlesen werden beim zeilenweisen Einlesen Textdateien unabh¨ angig von Leerzeichen Zeile f¨ ur Zeile in ein Zeichenfeld eingelesen. Dazu dient die Funktion fgets(char *string, int maxlaenge, file *datei).
12.2.6 In Datei schreiben
Analog zur Funktion printf gibt es die Funktion fprintf mit der formatierte Ausgabe in eine Datei m¨ oglich ist. Beim schreibenden Zugriff auf Datein ist der Schreibmodus der fopen-Funktion zu beachten:
w (Write-Modus) Die Datei wird - falls sie schon existiert - gel¨ oscht. Anschließend wird eine leere Datei angelegt.
a (Append-Modus) Die Datei wird - falls sie noch nicht existiert - als leere Datei angelegt. Bei den folgenden Schreibzuugriffen wird an die Datei angeh¨ angt
FILE ∗ d a t e i ;
i n t z a h l = 7 ;
KAPITEL 12. DATEIVERARBEITUNG 105
d a t e i = f o p e n ( ”/ e t c / h o s t s ” , ”w” ) ;
f p r i n t f ( d a t e i ,”%d\n” , z a h l ) ; f c l o s e ( d a t e i ) ;
12.2.7 Dateiende
Um Dateien mit unbekannter L¨ ange verarbeiten zu k¨ onnen ist es n¨ otig das Ende der Eingabe -Dateiende genannt - zu erkennen. Dazu dient die Funktion feof(file *in).
Die Verwendung wurd im Abschnitt “Zeilenweises Einlesen“ gezeigt.
12.3 Dateien mit variabler Satzl¨ ange
Dateien mit variabler Satzl¨ ange bestehen aus einzelnen Zeilen, die durch ein Zeilenendezeichen voneinander getrennt sind. Durch die Variable Satzl¨ ange m¨ ussen gespeicherte Daten nicht mit Leerzeichen aufgef¨ ullt werden, was Speicherplatz spart. Nachteilig ist die Tatsache, dass ein Programm nicht direkt einen bestimmten Datensatz suchen kann, da die Position eines Datensatzes in der Datei nicht direkt berechnet werden kann.
Das folgende Programm liest aus einer Datei, die nur aus Zahlen besteht, die Zahlenwerte ein und gibt die Anzahl der Zahlen sowie die Summe in eine Ausgabedatei aus:
KAPITEL 12. DATEIVERARBEITUNG 106
Eingabedatei:
1.23
3.245 5.23
5.32
Ausgabedatei:
4 Zahlen gelesen!
Summe: 15.025000
12.4 Dateinamen als Parameter
KAPITEL 12. DATEIVERARBEITUNG 107
12.5 Datenaustausch mit Tabellenkalkulationsprogram-
men
Oft ist es n¨ otig, Daten mit Tabellenkalkulationsprogrammen wie StarCalc oder Microsoft Excel auszutauschen. Dabei muss beachtet werden, dass diese Programme Zahlen oft mit Dezimalkomma statt Dezimalpunkt abspeichern. Deshalb muss in den C-Programmen manuell das Komma durch einen Punkt bzw. der Punkt durch ein Komma ersetzt werden.
12.5.1 Dateien mit Trennzeichen (CSV)
Ein h¨ aufig genutztes Format f¨ ur den Datentransfer zwischen Programmen ist die sog. CSV-Datei (Character-separated values) bei der die Informationen durch ein bestimmtes Trennzeichen getrennt werden. Als Trennzeichen wird h¨ aufig der Tabulator oder auch Semikolon oder Komma benutzt. In einem ersten Versuch wollen wird die ersten 10 Quadratzahlen und Quadratwurzeln in einer CSV-Datei speichern:
KAPITEL 12. DATEIVERARBEITUNG 108
Die produzierte CSV-Datei: Die produzierte Fix-Format-Datei:
1 1 1,000000 2 4 1,414214 3 9 1,732051 4 16 2,000000 5 25 2,236068 6 36 2,449490 7 49 2,645751 8 64 2,828427 9 81 3,000000 10 100 3,162278
Diese Datei kann jetzt mit Tabellenkalkulationsprogrammen weiterverarbeitet werden.
12.5.2 Dateien mit fester L¨ ange
Alternativ zum Trennen der Daten ¨ uber ein Trennzeichen kann auch mit fixer Zahlenl¨ ange gearbeitet werden. Der Formatstring zum Formatieren der Ausgabe ist im obigen Programm auskommentiert enthalten.
12.6 Beispiele
12.6.1 Sortieren einer Datei
Eine Datei die int-Zahlen enth¨ alt soll sortiert und formatiert (eine Zahl pro Zeile) in eine zweite Datei kopiert weren.
KAPITEL 12. DATEIVERARBEITUNG 109
12.6.2 Sieb des Eratosthenes
Um bei der oberen Grenze nicht an den Hauptspeicher gebunden zu sein wird der Algorithmus “Sieb des Eratosthenes“ mit einer Datei als Speichermedium implementiert.
KAPITEL 12. DATEIVERARBEITUNG 110
Wenn die Promzahlen bis 4 Milliarden (4 ∗ 10 9 ) berechnet werden sollen wird eine Datei mit der Gr¨ oße von 2 ∗ 10 9 Byte (≈ 2 GB) ben¨ otigt!
Kapitel 13
Rekursion
13.1 Einf¨ uhrung
Es stand sehr schlimm um des Bandwurms Befinden.
Ihn juckte immer etwas hinten. Dann konstatierte Doktor Schmidt, Nachdem er den Leib ihm aufgeschnitten, Daß dieser Wurm an W¨ urmern litt, Die wiederum an W¨ urmern litten ... Joachim Ringelnatz 1883-1934
13.1.1 Begriffsbildung
Unter dem Begriff der Rekursion versteht man eine Programmiertechnik, bei der sich ein Unterprogramm selbst wieder aufruft:
void rekursives_modul()
{ ... rekursives_modul(); ... }
void main()
{ ... rekursives_modul(); ... } Folie 64
Es existiert ein Beweis von Nikolaus Wirth (einer der Urv¨ ater der strukturierten Programmierung) dass sich jedes Problem in der Informatik sowohl rekursiv als auch iterativ l¨ osen l¨ asst.
13.1.2 Schwierigkeit
Selbstverst¨ andlich muss jede Rekursion einmal beendet werden. Andernfalls entsteht eine End- losrekursion (vergleichbar mit einer Endlosschleife) die (im Gegensatz zur Endlosschleife) schnell
KAPITEL 13. REKURSION 112
in einem Programmabsturz endet. Daher muss gew¨ ahrleistet werden, dass eine Bedingung f¨ ur den Rekursionsabbruch erf¨ ullt wird.
Auch ist im Einzelfall zu kl¨ aren, ob die iterative oder die rekursive L¨ osung des Problems zu bevorzugen ist.
13.1.3 G¨ ultigkeit von Variablen
Wenn eine Funktion aufgerufen wird so erh¨ alt sie ihre eigenen Variablen in der Symboltabelle. Bei jedem rekursiven Aufruf werden wieder neue Variablen - unter dem selben Namen - angelegt. Am Ende einer rekursiv aufgerufenen Funktion wird an die Stelle des Aufrufs zur¨ uckgesprungen und der Wert der Variablen in dieser aufrufenden Rekursionsebene wiederhergestellt.
Dieses Speicherverfahren nennt man Kellerspeicher oder Stack oder auch LIFO-Speicher (Last In - First Out).
Das folgende Beispiel zeigt deutlich, dass die Variable zahl in jeder Rekursionsebene einen anderen Wert hat. Durch Vergleich der Variable zahl mit der Konstanten MAX_REKURSION und dem rekursiven Aufruf rekursion(zahl + 1) wird sichergestellt, dass die Abbruchbedingung der Rekursion erf¨ ullt wird. Nach dem rekursiven Aufruf stehen die alten Variablenwerte wieder zur Verf¨ ugung.
KAPITEL 13. REKURSION 113
Bildschirmausgabe:
zahl=0
zahl=1 zahl=2 zahl=3 zahl=4 zahl=4 zahl=3 zahl=2 zahl=1 zahl=0
Wie kommt nun diese Bildschirmausgabe zustande?
Es sei noch erw¨ ahnt, daß statische Variablen in C (z.B. static int zahl) nicht bei jedem rekursiven Aufruf neu angelegt werden sondern immer die Variable des ersten Aufrufs verwendet wird.
13.2 Einfache Anwendungen
13.2.1 Die Berechnung der Fakult¨ at
Die Fakult¨ at einer ganzen Zahl n ist definiert als
⎧
Hierbei handelt es sich um eine iterative Definitition, um ein Produkt aus Zahlen. Alternativ kann die Fakult¨ at auch rekursiv definiert werden:
Die Fakult¨ at auf der rechten Seite der Definition ist also Bestandteil der Berechnung der Fakult¨ at, Folie 67 dies nennt man eine rekursive Definition.
Analog zu iterativer und rekursiver Definition der Fakult¨ at kann nun die Funktion fakultaet iterativ und rekursiv implementiert werden:
KAPITEL 13. REKURSION 114
13.2.2 Der gr¨ oßte gemeinsame Teiler
Der Euklidsche Algorithmus zur Berechnung des GGTs zweier nat¨ urlicher Zahlen geht folgendermaßen:
Solange die zwei Zahlen unterschiedlich sind ersetze die gr¨ oßere Zahl durch die Differenz der zwei Zahlen ⎧
KAPITEL 13. REKURSION 115
13.3 Vor- und Nachteile von Rekursion
Die Fibonacci-Zahlenfolge ist folgendermassen definiert: ⎧
Sie l¨ asst sich am einfachsten durch eine Rekursive Funktion berechnen:
Bildschirmausgabe:
Geben Sie eine Zahl ein: 5
Aufruf 1: zahl = 5 Aufruf 2: zahl = 3 Aufruf 3: zahl = 1 Aufruf 4: zahl = 2 Aufruf 5: zahl = 0 Aufruf 6: zahl = 1
KAPITEL 13. REKURSION 116
Aufruf 7: zahl = 4 Aufruf 8: zahl = 2 Aufruf 9: zahl = 0 Aufruf 10: zahl = 1 Aufruf 11: zahl = 3 Aufruf 12: zahl = 1 Aufruf 13: zahl = 2 Aufruf 14: zahl = 0 Aufruf 15: zahl = 1 Fibonacci(5) = 5 Modul fibonacci wurde 15 mal aufgerufen! Folie 69
Aufrufbaum f¨ ur fibonacci(5) (aus Platzgr¨ unden “fibo“ statt “fibonacci“):
fibo(1)
Hier zeigt sich, daß eine iterative L¨ osung zwar weniger elegant aber deutlich performanter ist. Bereits bei der Berechnung der 40. Fibonacci-Zahl lassen sich deutliche Laufzeitunterschiede feststellen.
Anm.: Wenn man diesen Baum im Preorder-Verfahren durchl¨ auft (erst Knoten ausgeben, dann linken Teilbaum abarbeiten, dann rechten Teilbaum abarbeiten) so erh¨ alt man wieder die BS-Ausgabe des Fibonacci-Programms!
KAPITEL 13. REKURSION 117
13.4 Weitere Anwendungen
13.4.1 Bin¨ are Suche
Auch die Bin¨ are Suche kann auf einfache Weise rekursiv implementiert werden. Voraussetzung f¨ ur die Bin¨ are Suche ist ein sortiertes Array. Eine rekursiv definierte Funktion binaere_suche gibt - wenn der gesuchte Wert sich nicht an der mittleren Stelle befindet, das Ergebnis der rekursiven Suche im linken bzw. rechten Teilintervall zur¨ uck:
• Berechne Mitte des Intervalls
• Wenn Zahl gefunden gib Position zur¨ uck
• Wenn gefundene Zahl zu groß rufe binaere_suche mit linkem Teilintervall als Parameter rekursiv auf
• Wenn gefundene Zahl zu klein rufe binaere_suche mit rechtem Teilintervall als Parameter rekursiv auf
int binsuche_rek(zahl,links,rechts) {
int mitte = (links + rechts) / 2;
printf("\nSuche %d %d %d",links, rechts, mitte);
if (links == rechts && array[mitte] != zahl)
return -1; // Zahl nicht gefunden if (array[mitte] > zahl)
return binsuche_rek(zahl, links, mitte-1); //Zahl muss links sein if (array[mitte] < zahl)
return binsuche_rek(zahl, mitte+1, rechts); // Zahl muss rechts sein return mitte; // Treffer }
13.4.2 Rekursive Sortieralgorithmen
Quicksort
Die bisher kennengelernten Sortieralgorithmen haben alle das Laufzeitverhalten n 2 . Der hier vorgestellte Algorithmus geht stattdessen mit n ∗ ld (n). Durch diesen eklatanten Geschwindig-keitsvorteil nannte der Entwickler dieses Algorithmus, Hoare, ihn eben Quicksort.
Die Grundidee des Quicksort ist die, ein Zahlenfeld so in zwei Teile zu zerlegen, daß diese Teile nebeneinander richtig sortiert sind:
KAPITEL 13. REKURSION 118
feld [i ] < feld [j ] f¨ ur allei ∈ Teil 1 undj ∈ Teil 2
Dazu wird wahllos eine Zahl des Feldes als Grenzwert zwischen den Feldern herangezogen (meist die mittlere Zahl, dies ist aber nicht zwingend notwendig). Dann werden von aussen kommend Zahlen gesucht, die im falschen Teil liegen. Durch das Tauschen von zwei Zahlen die jeweils im falschen Teil liegen wird ein sehr effizienter Tausch vorgenommen: void quicksort(int links, int rechts)
Die durch die Vertauschung entstandenen Teile m¨ ussen nicht gleich groß sein (und sind dies i.A. auch nicht).
KAPITEL 13. REKURSION 119
Bildschirmausgabe:
Ausgangswerte: 4 2 8 7 1 6 3 5
Quicksort-Aufruf, Testzahl ist 7
4 2 |
KAPITEL 13. REKURSION 120
l r Zu tauschen:
4 2
Nach Tausch:
4 2
Zu tauschen:
4 2
Nach Tausch:
4 2
Quicksort beendet!
Quicksort-Aufruf, Testzahl ist 5
4 2 | l Zu tauschen:
4 2
Nach Tausch:
4 2
Quicksort beendet!
Quicksort-Aufruf, Testzahl ist 2
4 2 | l Zu tauschen:
4 2 | l Nach Tausch: 1 2 4 3 | l Zu tauschen: 1 2 4 3 | l Nach Tausch:
1 2 |
KAPITEL 13. REKURSION 121
r l Quicksort beendet!
Quicksort-Aufruf, Testzahl ist 4
4 3 | | l r Zu tauschen: 4 3 | | l r Nach Tausch: 3 4 | | r l Quicksort beendet!
Quicksort-Aufruf, Testzahl ist 5
5 6 | | l r Zu tauschen: 5 6 | l Nach Tausch: 5 6 | l Quicksort beendet!
Quicksort-Aufruf, Testzahl ist 7
7 8 | | l r Zu tauschen: 7 8 | l Nach Tausch: 7 8 | l Quicksort beendet! Nach quicksort: 1 2 3 4 5 6 7 8
Mergesort
Der Mergesort macht sich die das einfache Mischen zweier in sich sortierter Felder zu nutze.
KAPITEL 13. REKURSION 122
1 3 5 6 2 4 7 8
void mergesort(int links, int rechts)
KAPITEL 13. REKURSION 123
13.4.3 Die T¨ urme von Hanoi
Die Aufgabe
In einem Kloster bei Hanoi haben M¨ onche die Aufgabe, einen Turm aus 64 unterschiedlich großen Scheiben von einer Stange auf eine andere Stange zu versetzen. Wenn Sie mit dieser Arbeit fertig sind ist der Sage nach das Ende der Welt gekommen.
Zum Versetzen der Scheiben gelten die folgenden Regeln:
• Es darf immer nur eine Scheibe gleichzeitig bewegt werden
• Es darf nie eine gr¨ oßere Scheibe auf eine kleinere Scheibe gelegt werden
M¨ onch 1 hat hier die Aufgabe, den Turm aus vier Scheiben von Stange 1 auf Stange 2 zu versetzen. Da er nicht weiss, wie das geht, hilft er sich folgendermaßen:
1. Er bittet M¨ onch 2, die oberen drei Scheiben auf Stange 3 zu versetzen
2. Er setzt die Scheibe 4 von Stange 1 auf Stange 2 um
3. Er bittet M¨ onch 2, die oberen drei Scheiben von Stange 3 auf Stange 2 zu versetzen
Diese drei Schritte grafisch:
1.
KAPITEL 13. REKURSION 124
2.
3.
M¨ onch 2 hat also die Aufgabe bekommen, einen Turm betstehend aus drei Scheiben von Stange 1 auf Stange 3 zu versetzen. Er macht sich das Leben ebenfalls einfach indem er M¨ onch 3 bittet, die obersten beiden Scheiben von Stange 1 nach Stange zwei zu versetzen. Danach vesetzt dann selber Scheibe 3 von Stange 1 nach Stange 3 und l¨ asst dann von M¨ onch 3 die Scheiben 1 und 2 von Stange 2 nach Stange 3 vesetzten.
Dieses Verfahren kann verallgemeinert werden:
Um einen Turm von n Scheiben von Stange X nach Stange Y zu vesetzen versetzt man erst einen Turm mit n-1 Scheiben von Stange X nach Stange Z, anschliessend versetzt man Scheibe n von X nach Y und dann den Turm von Stange Z auf Stange Y. Modul hanoi
Die Berechnung der Zugzahl ist - wenn man das rekursive Verfahren verstanden hat - einfach:
Ohne den mathematischen Beweis zu liefern kann geschrieben werden
zugzahl (h) = 2 h − 1
Die M¨ onche von Hanoi brauchen f¨ ur ihren 64 Scheiben hohen Turm also - unter der Annahme
daß sie pro Sekunde eine Scheibe versetzen - 2 64 − 1 Sekunden was etwa 500 Millarden Jahren entspricht.
KAPITEL 13. REKURSION 125
L¨ osung
Es werden zwei L¨ osungen vorgestellt. Die erste soll die Kompaktheit des L¨ osungsalgorithmus zeigen und verzichtet auf grafische Bildschirmausgabe. Die zweite zeigt den L¨ osungsweg auch grafisch.
KAPITEL 13. REKURSION 126
Bildschirmausgabe:
Geben Sie die Turmhoehe ein: 3 Ausgangslage:
X
XXX
KAPITEL 13. REKURSION 127
XXXXX | |
Zug 1: 1 nach 2
| XXX XXXXX
Zug 2: 1 nach 3
| | XXXXX
Zug 3: 2 nach 3
| | XXXXX
Zug 4: 1 nach 2
| | | XXXXX
Zug 5: 3 nach 1
| | X XXXXX
Zug 6: 3 nach 2
| | X XXXXX
Zug 7: 1 nach 2
| | | XXXXX
13.5 Backtracking-Algorithmen
13.5.1 Einf¨ uhrung
Bei Entscheidungsproblemen hat man oft das Problem einer mehrstufigen Entscheidung. Beispielsweise bei der Fahrt durch eine Stadt kann man an einer Kreuzung links oder rechts abbiegen oder auch geradeaus weiterfahren, an der n¨ achsten Kreuzung stellt sich genau dasselbe Problem wieder. Um nun etwa alle m¨ oglichen Wege zwischen zwei Punkten zu finden (ohne eine Strasse doppelt zu befahren) muss man sehr viele M¨ oglichkeiten durchspielen.
Mit solchen Problemen besch¨ aftigen sich die sogenannten Backtracking-Algorithmen. Sie versuchen bei einer Entscheidung alle M¨ oglichkeiten und gehen - wenn sie in eine Sackgasse geraten - zur Stelle der jeweils letzten Entscheidung zur¨ uck.
KAPITEL 13. REKURSION 128
13.5.2 Das R¨ osslsprung-Problem
Auf einem Schachbrett (f¨ ur unser Beispiel der Gr¨ oße 5x5) soll ein Springer im Feld A1 starten und nach 24 Z¨ ugen im Feld E5 ankommen. Unterwegs darf kein Feld doppelt betreten werden (daraus folgt dass jedes Feld genau einmal betreten werden darf und muss).
D¨ ur den Springerzug gilt “Springe zwei Felder waagrecht oder senkrecht und dann ein Feld zur Seite“.
5
4
3
2
1
A B C D E
Als Speicher f¨ ur das Schachbrett wird ein globales zweidimensionales Array der Gr¨ oße 5*5 verwendet. Um die Zugfolge abspeichern zu k¨ onnen bedeutet der Wert=0 im Array “Feld frei“ und ein Wert> 0 die Zugnummer.
KAPITEL 13. REKURSION 129
Die Funktion Zug arbeitet als Backtracking-Funktion folgendermaßen:
Algorithmus 9: Springerzug
1. Wenn ein Feld belegt ist oder der Sprung das Schachbrett verlassen hat verlasse die Funktion
2. Belege das Feld
3. Wenn Zugzahl < 25
• versuche alle acht Springerz¨ uge
sonst
• Ausgabe
4. Gebe Feld frei
Modul Springerzug, Brettgr¨ oße n*n
KAPITEL 13. REKURSION 130
Die Bildschirmausgabe bringt insgesamt 56 L¨ osungen, aus Platzgr¨ unden nur die ersten zwei L¨ osungen:
KAPITEL 13. REKURSION 131
Bildschirmausgabe:
L¨ osung 1:
23 18 11 6 25
10 5 24 17 12 19 22 13 4 7 14 9 2 21 16 1 20 15 8 3 Bitte eine Taste dr¨ ucken...
L¨ osung 2:
23 16 11 6 25
10 5 24 17 12 15 22 19 4 7 20 9 2 13 18 1 14 21 8 3 Bitte eine Taste dr¨ ucken... ...
13.5.3 Wegsuche im Labyrinth
Die Maus im folgenden Irrgarten startet links oben und m¨ ochte den K¨ ase rechts unten finden. Da sie ein Informatik-Studium absolviert hat und zudem sehr neugierig ist m¨ ochte sie nat¨ urlich alle m¨ oglichen Wege zum K¨ ase finden:
Kommt die Maus an eine Stelle, an der sie nicht mehr (ohne ein Feld ein zweites mal zu betreten)
KAPITEL 13. REKURSION 132
weiterkommt geht sie bis zur letzten Abzweigung zur¨ uck und biegt dort anders ab. void mauszug(int zeile, int spalte)
KAPITEL 13. REKURSION 133
Bildschirmausgabe:
Wollen Sie jeden mauszug ausgeben? n +-----+ | XX | |X | | X X| | X | | X@| +-----+
+-----+
|::XX | |X: | |::X X| |:X:::| |:::X#| +-----+Hmmm, leckerer K¨ ase!
KAPITEL 13. REKURSION 134
+-----+
|::XX | |X::: | | X:X| | X ::| | X#|
+-----+Hmmm, leckerer K¨ ase!
13.5.4 Wegsuche im Straßen-Netz
In einem Staßennetz sollen alle m¨ oglichen Fahrwege zwischen zwei Ortschaften berechnet werden. Das folgende Straßennetz gibt die Verbindungen mit den jeweiligen Wegstrecken an:
4
A
5
KAPITEL 13. REKURSION 135
Modul fahre
F¨ ur die Implementierung werden zwei Felder ben¨ otigt, eines dient als Merker, in welchen St¨ adten man schon war und das andere als Merker f¨ ur die Wegstrecke.
KAPITEL 13. REKURSION 136
Bildschirmausgabe:
6 St¨ adte: A B C F G H -> 15 km 5 St¨ adte: A B C F H -> 10 km 5 St¨ adte: A B F G H -> 16 km 4 St¨ adte: A B F H -> 11 km 5 St¨ adte: A B G F H -> 12 km 4 St¨ adte: A B G H -> 11 km 6 St¨ adte: A C B F G H -> 17 km 5 St¨ adte: A C B F H -> 12 km 6 St¨ adte: A C B G F H -> 13 km 5 St¨ adte: A C B G H -> 12 km 6 St¨ adte: A C F B G H -> 17 km 5 St¨ adte: A C F G H -> 12 km 4 St¨ adte: A C F H -> 7 km
7 St¨ adte: A D E F B G H -> 20 km 8 St¨ adte: A D E F C B G H -> 19 km 6 St¨ adte: A D E F G H -> 15 km 5 St¨ adte: A D E F H -> 10 km 6 St¨ adte: A D F B G H -> 17 km
7 St¨ adte: A D F C B G H -> 16 km 5 St¨ adte: A D F G H -> 12 km 4 St¨ adte: A D F H -> 7 km
7 St¨ adte: A E D F B G H -> 22 km 8 St¨ adte: A E D F C B G H -> 21 km 6 St¨ adte: A E D F G H -> 17 km 5 St¨ adte: A E D F H -> 12 km 6 St¨ adte: A E F B G H -> 21 km
7 St¨ adte: A E F C B G H -> 20 km 5 St¨ adte: A E F G H -> 16 km 4 St¨ adte: A E F H -> 11 km
13.6 ¨ Ubungen
13.6.1 Straßennetz
Modifizieren Sie das Programm Straßennetz so, dass es nur die k¨ urzeste Strecke ausgibt bei der alle St¨ adte angefahren werden.
KAPITEL 13. REKURSION 137
13.6.2 Permutationen
Die Zahl der Permutationen zweier Zahlen kann folgendermaßen berchnet werden:
Mit etwas Mathematik bekommt man auch eine rekursive L¨ osung:
mit den Abbruchbedingungen f¨ ur die Rekursion
F¨ ur die Rekursive Definition ist die Abbruchbedingung wichtig: Entwickeln Sie je ein rekursiv und ein iterativ arbeitendes Modul zur Berechnung der Permutationen zweier Zahlen.
Berechnnen Sie mit diesem Programm die Wahrscheinlichkeit von Sechs Richtigen im Lotto 49
13.6.3 Zahlenraten
¨ Andern Sie das Zahlenratespiel aus dem Kapitel Schleifen auf eine rekursive L¨ osung um.
13.6.4 Acht Damen
Auf einem Schachbrett sollen acht Damen so positioniert werden, dass keine Dame eine andere bedroht:
8 7 6 5 4 3 2 1 A B C D E F G H
Entwickeln Sie einen rekursiven L¨ osungsalgorithmus und ein Programm, das einfach auf andere Brettgr¨ oßen ge¨ andert werden kann (per Pr¨ aprozessor-Konstante). Zur Vereinfachung kann es evtl. sinnvoll sein, erst ein Programm “Acht T¨ urme“ zu entwickeln (in diesem Fall ist die Zahl der L¨ osungen = n! mit n = eindimensionaler Brettgr¨ oße).
Entwickeln Sie den rekursiven Algorithmus am besten mit einem 4*4-Schabrett “von Hand“.
13.6.5 Getr¨ ankeautomat
Ein Getr¨ ankeautomat muß mit 2.50 DM passend bedient werden. Er akzeptiert die M¨ unzen 10 DPf, 50 DPf, 1 DM und 2 DM. Auf wieviele Arten kann bezahlt werden (Reihenfolge des Einwurfs spielt eine Rolle)?
KAPITEL 13. REKURSION 138
13.6.6 Bildschirmausgabe
Welche Bildschirmausgabe produziert das folgende Programm:
Kapitel 14
Dynamische Datenstrukturen
14.1 Einf¨ uhrung
14.1.1 Allgemeines
Um gr¨ oßere Mengen von Daten im Hauptspeicher zu speichern werden oft Arrays (Felder) eingesetzt. Diese sind zwar einfach zu programmieren, haben in der Praxis jedoch Nachteile:
• Die Gr¨ oße des Array muss bereits zum Zeitpunkt der Compilierung festgesetzt werden.
• Zu groß angelegte Arrays belasten vor allem bei Mehrbenutzersystemen den Computer
• Spezielle Datentypen wie etwa sortierte Listen sind nur mit viel Rechenaufwand zu Implementieren
Zur Veranschaulichung soll in eine sortierte Adressdatei ein neuer Datensatz eingef¨ ugt werden. Bei Implentierung mit Arrays zeigt sich, dass alle Datens¨ atze, die in der Sortierung nach dem neu einzuf¨ ugenden Satz kommen, eine Stelle nach hinten verschoben werden m¨ ussen:
Zum Einf¨ ugen des Namens ”Bergerm¨ ussen nun alle Datens¨ atze ab Pos. 1 nach rechts verschiben werden:
¨ Uber dynamische Hauptspeicherzuweisung und Zeigervariablen (Pointer) lassen sich solche Vorg¨ ange effizienter l¨ osen. In den Schaubildern werden die gespeicherten Daten als K¨ astchen dargestellt, die Zeigerkomponenten als Pfeile. Alle Beispiele beziehen sich auf Integer-Zahlen als Speicherdatum.
14.1.2 Strrukturen und Zeiger
Bei dynamischen Datenstrukturen werden als Datentyp Strukturen eingesetzt, die neben den zu speichernden Daten einen oder mehrere Zeiger auf sich selbst haben. Je nach der logischen Zeigerart sprocht man bei den Dynmischen Datenstrukturen von, Kellerspeichern, Listen, Ketten (Schlangen) und B¨ aumen.
s t r u c t m e i n e d a t e n s t r u k t u r {
i n t e g e r wert1 ; double w e r t 2 ;
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 140
s t r u c t d a t e n s t r u k t u r ∗ z e i g e r ;
} ;
Achtung: Hinter der Ende-Klammer der Struktur folgt ein “;“!
14.1.3 C-Kommandos
Die C-Kommandos zur dynamischen Hauptspeicherverwaltung finden sich (mit Ausnahme von sizeof) in der Bibliothek malloc.h:
malloc Funktion die dynamisch Speicher reserviert.
free Gibt dynamische Speicher wieder frei.
sizeof Berechnet die Gr¨ oße einer Datenstruktur in Bytes.
14.2 Die sortierte lineare Liste
14.2.1 Struktur
Die sortierte lineare Liste ist eine Hauptspeicherstruktur, die den Zeigern entlang sortiert aufgebaut wird. Es wird also beim Speichern und l¨ oschen abh¨ angig vom zu speichernden / l¨ oschenden Wert die richtige Stelle in der Liste gesucht und gespeichert bzw. gel¨ oscht.
14.2.2 Speichern
Beim Speichern werden vier F¨ alle unterschieden:
• Neue Liste
• Neues erstes Element der Liste
• Neues letztes Element der Liste
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 141
• Neues Element innerhalb der Liste
In diesem Fall muss mit zwei Zeigern die zwei Listenelemente gesucht werden, zwischen denen das neue Element einzuf¨ ugen ist. In der Musterl¨ osung ist es nicht m¨ oglich, denselben Zahlenwert zweimal zu speichern.
Speichern in sortierte linearer Liste
14.2.3 L¨ oschen
Zwei F¨ alle m¨ ussen unterschieden werden:
• L¨ oschen des ersten Elements der Liste (Anfangs- und evtl. Ende-Zeiger m¨ ussen ver¨ andert werden
• L¨ oschen innerhalb oder am Ende der Liste
14.2.4 Musterl¨ osung
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 142
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 143
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 144
14.3 Der Kellerspeicher (Stack)
Unter einem Kellerspeicher versteht man einen Speicher, bei dem immer die zuletzt gespeicherten Daten zuerst gelesen werden. Dieses Last-In-First-Out-Prinzip (LIFO) wird etwa zur Berechnung arithmetischer Ausdr¨ ucke verwendet.
r r
14.3.1 Struktur
Jedes Datenelement besteht aus den Datenfeldern und einem Zeiger auf das n¨ achste Element der Schlange.
14.3.2 Musterl¨ osung
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 145
14.4 Die Schlange (Queue)
Bei der Schlange erfolgt das Speichern immer am Ende der Schlange w¨ ahrend das Lesen im- mer am Anfang der Schange erfolgt. Dies wird das First-In-First-Out-Prinzp (FIFO) genannt.
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 146
Manchmal wird diese Speicherform auch Eimerkettenspeicher genannt.
Bei der Implementierung ist zu beachten, dass die Richtung der Zeiger entgegen der Laufrichtung der Schlange ist. Durch je einen Zeiger f¨ ur Anfang und Ende der Schlange kann ohne Schleifen gespeichert und gelesen werden, wodurch der Rechenaufwand unabh¨ angig von der L¨ ange der Schlange wird.
14.4.1 Struktur
Jedes Datenelement besteht aus den Datenfeldern und einem Zeiger auf das n¨ achste Element der Schlange.
14.4.2 Speichern
Beim Speichern sind zwei F¨ alle zu unterscheiden:
• Wenn die Schlange vor dem Speichern leer war so ist der Startzeiger auf das neue Datenelement zu setzen.
• Andernfalls muss der Next-Zeiger des letzten Datenelements auf das neue Element zeigen.
14.4.3 L¨ oschen
Auch beim L¨ oschen ist eine Fallunterscheidung n¨ otig. Da der L¨ oschvorgang sich prim¨ ar nur auf den Kopf der Schlange auswirkt muss beim L¨ oschen des letzten Elements zus¨ atzlich der Ende-Zeiger auf NULL gesetzt werden.
14.4.4 Musterl¨ osung
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 147
KAPITEL 14. DYNAMISCHE DATENSTRUKTUREN 148
Anhang A
C-Standard-Bibliothek
A.1 Einf¨ uhrung
stdio.h Standard-Ein- und Ausgabefunktionen
ctype-h Funktionen zur Klassifikation von Char-Codes
math.h Funktionen zur Mathematik]
string.h Funktionen zur Stringverarbeitung]
time.h Funktionen zur Zeitverarbeitung
stdlib.h Diveres Hilfsfunktionen
limits.h Bereichsgrenzen f¨ ur Integer-Konstanten
A.2 stdio.h
clearerr Teste Stream-Status und setze ihn zur¨ uck.
fclose Schließe einen Stream.
fdopen Funktionen zum ¨ Offnen eines Streams.
feof Teste Streamstatus und setze ihn zur¨ uck.
ferror Teste Streamstatus und setze ihn zur¨ uck.
fflush Schreibe ausstehende Daten des Streams.
fgetc Hole das n¨ achste Zeichen oder Wort vom Eingabestream.
fgetline Hole eine Zeile vom Stream.
fgetpos Re-positioniere den Positionszeiger des Streams.
fgets Hole eine Zeile vom Stream.
fileno Teste den Stream-Status und setze ihn zurueck.
fopen Funktionen zum ¨ Offnen eines Streams.
fprintf Gib Text formatiert auf dem Stream aus.
ANHANG A. C-STANDARD-BIBLIOTHEK 150
fpurge Flushe einen Stream.
fputc Gib ein Zeichen oder Wort auf dem Stream aus.
fputs Gib eine Zeile auf dem Stream aus.
fread Bin¨ ares Lesen von einem Stream.
freopen Funktionen zum ¨ Offnen eines Streams.
fropen ¨ Offne einen Stream.
fscanf Formatiertes Einlesen.
fseek Repositioniere einen Stream.
fsetpos Repositioniere einen Stream.
ftell Repositioniere einen Stream.
fwrite Bin¨ ares Schreiben auf einem Stream.
getc Hole das n¨ achsten Zeichen oder Wort vom Eingabestream.
getchar Hole das n¨ achsten Zeichen oder Wort vom Eingabestream.
gets Hole eine Zeile vom Eingabestream.
getw Hole das n¨ achsten Zeichen oder Wort vom Eingabestream.
mktemp Erzeuge einen eindeutigen tempor¨ aren Dateinamen.
perror Systemfehlermeldungen.
printf Formatierte Ausgabeumwandlung.
putc Gib ein Zeichen oder Wort auf dem Stream aus.
putchar Gib ein Zeichen oder Wort auf dem Stream aus.
puts Gib eine Zeile auf dem Stream aus.
putw Gib ein Zeichen oder Wort auf dem Stream aus.
remove L¨ osche einen Verzeichniseintrag.
rewind Repositioniere einen Stream.
scanf Formatiertes Einlesen.
setbuf Stream-Puffer Operationen.
setbuffer Stream-Puffer Operationen.
setlinebuf Stream-Puffer Operationen.
setvbuf Stream-Puffer Operationen.
sprintf Formatierte Ausgabeumwandlung.
sscanf Formatiertes Einlesen.
strerror Systemfehlermeldungen.
sys errlist Systemfehlermeldungen.
ANHANG A. C-STANDARD-BIBLIOTHEK 151
sys nerr Systemfehlermeldungen.
tempnam Routinen f¨ ur tempor¨ are Dateien.
tmpfile Routinen f¨ ur tempor¨ are Dateien.
tmpnam Routinen f¨ ur tempor¨ are Dateien.
ungetc Lege ein Zeichen zur¨ uck in den Eingabestream.
vfprintf Formatierte Ausgabeumwandlung.
vfscanf Formatiertes Einlesen.
vprintf Formatierte Ausgabeumwandlung.
vscanf Formatiertes Einlesen.
vsprintf Formatierte Ausgabeumwandlung.
vsscanf Formatiertes Einlesen.
A.3 ctype.h
i n t i s a l n u m ( i n t c ) ;
i n t i s a l p h a ( i n t c ) ; i n t i s a s c i i ( i n t c ) ; i n t i s b l a n k ( i n t c ) ; i n t i s c n t r l ( i n t c ) ; i n t i s d i g i t ( i n t c ) ; i n t i s g r a p h ( i n t c ) ; i n t i s l o w e r ( i n t c ) ; i n t i s p r i n t ( i n t c ) ; i n t i s p u n c t ( i n t c ) ; i n t i s s p a c e ( i n t c ) ; i n t i s u p p e r ( i n t c ) ; i n t i s x d i g i t ( i n t c ) ; i n t t o u p p e r ( i n t c ) ; i n t t o l o w e r ( i n t c ) ;
isalnum() pr¨ uft auf alphanumerische Zeichen, es ist ¨ aquiva lent zu (isalpha(c) || isdigit(c)).
isalpha() pr¨ uft auf Buchstaben, in der Standard-C-Spracher weiterung ist es ¨ aquivalent zu (isupper(c) || islower(c)). In anderen Spracherweiterungen k¨ onnen weitere Zeichen sein, f¨ ur die isalpha() wahr ist - Zeichen, die weder Groß- noch Kleinbuchstaben sind.
isascii() pr¨ uft, ob c ein 7-bit unsigned char ist, das dem ASCII Zeichensatz entspricht. Diese Funktion ist eine BSD-und auch SVID-Erweiterung.
isblank() pr¨ uft auf Leerzeichen, also ein Space oder ein Tab. Diese Funktion ist eine GNU-Erweiterung.
iscntrl() pr¨ uft auf Kontrollzeichen.
isdigit() pr¨ uft auf Ziffern ab.
isgraph() pr¨ uft auf druckbare Zeichen außer Leerzeichen ab.
islower() pr¨ uft, ob c ein Kleinbuchstabe ist.
ANHANG A. C-STANDARD-BIBLIOTHEK 152
isprint() pr¨ uft auf druckbare Zeichen inklusive Leerzeichen ab.
ispunct() pr¨ uft auf druckbare Zeichen, die kein Leerzeichen und kein alphanumerisches Zeichen sind.
isspace() pr¨ uft auf Freizeichen. In derC-POSIX-Spracherweiterung sind dies: Leerzeichen, Sei-tenvorschub (’\f’), Zeilenumbruch (’\n’), Carriage Return (’\r’), Horizontaler Tabulator (’\t’) und vertikaler Tabulator (’\v’).
isupper() pr¨ uft auf Großbuchstaben ab.
isxdigit() pr¨ uft, ob c eine hexadezimales Ziffer ist, also eines der Zeichen 0 1 2 3 4 5 6 7 8 9 0 a b c d e f A B C D E F.
tolower konvertiert den Buchstaben c in den entsprechenden Kleinbuchstaben, falls dies geht.
toupper konvertiert den Buchstaben c in den entsprechenden Großbuchstaben, falls dies geht.
A.4 math.h
double s i n ( double ) x ) ;
double c o s ( double x ) ; double tan ( double x ) ; double a s i n ( double ) x ) ; double a c o s ( double x ) ; double a t a n ( double x ) ; double atan2 ( double x , double y ) ; double pow ( double b a s e , double e x p o n e n t ) ; double f a b s ( double x ) ; i n t abs ( i n t x ) ; double f l o o r ( double x ) ; double c e i l ( double x ) ; double exp ( double x ) ; double s q r t ( double x ) ;
A.5 string.h
i n t s t r c a s e c m p ( const char ∗ s1 , const char ∗ s2 ) ;
char ∗ s t r c a t ( char ∗ d e s t , const char ∗ s r c ) ; char ∗ s t r c h r ( const char ∗ s , i n t c ) ; i n t strcmp ( const char ∗ s1 , const char ∗ s2 ) ; i n t s t r c o l l ( const char ∗ s1 , const char ∗ s2 ) ; char ∗ s t r c p y ( char ∗ d e s t , const char ∗ s r c ) ; s i z e t strcspn ( const char ∗ s , const char ∗ r e j e c t ) ; char ∗ s t r d u p ( const char ∗ s ) ; char ∗ s t r f r y ( char ∗ s t r i n g ) ; s i z e t strlen ( const char ∗ s ) ;
char ∗ s t r n c a t ( char ∗ d e s t , const char ∗ s r c , s i z e t n ); i n t strncmp ( const char ∗ s1 , const char ∗ s2 , s i z e t n ); char ∗ s t r n c p y ( char ∗ d e s t , const char ∗ s r c , s i z e t n ); i n t s t r n c a s e c m p ( const char ∗ s1 , const char ∗ s2 , s i z e t n ); char ∗ s t r p b r k ( const char ∗ s , const char ∗ a c c e p t ) ; char ∗ s t r r c h r ( const char ∗ s , i n t c ) ; char ∗ s t r s e p ( char ∗ ∗ s t r i n g p , const char ∗ d e l i m ) ;
ANHANG A. C-STANDARD-BIBLIOTHEK 153
s i z e t strspn ( const char ∗ s , const char ∗ a c c e p t ) ;
char
∗
s t r s t r (
const char
∗
h a y s t a c k ,
const char
∗
n e e d l e ) ;
char
∗
s t r t o k (
char
∗
s ,
const char
∗
d e l i m ) ; s i z e t strxfrm (
char
∗
d e s t ,
const char
∗
s r c , s i z e t n );
char
∗
i n d e x (
const char
∗
s ,
i n t
c ) ;
char
∗
r i n d e x (
const char
∗
s ,
i n t
c ) ;
A.6 time.h
t i m e t time ( time t ∗ t ) ;
time() liefert die Zahl der Sekunden seit 1970-01-01 0:00 Uhr. Wird als Argument ein Zeiger ubergeben so wird der Zeitwert auch in dem Haupspeicherbereich auf den t zeigt gespei¨ chert.
A.7 stdlib.h
double a t o f ( char ∗ t e x t ) ;
i n t a t o i ( char ∗ t e x t ) ; i n t rand ( ) ; void s r a n d ( unsigned i n t z ) ;
atof() wandelt den Beginn eines Strings, der durch text angegeben wird, in eine Double-Zahl um.
atoi() Funktion konvertiert einen String in eine Integerzahl. Dabei ist text ein Zeiger auf den String, der konvertiert werden soll. Der ¨ ubergebene String wird dabei nach den ersten passenden Zeichen durchsucht und diese werden konvertiert.
rand() liefert eine Pseudozufalls-Ganzzahl (integer) zwischem 0 und RAND MAX.
srand() setzt ihr Argument als Ursprung f¨ ur eine neue Reihe von Pseudozufalls-Ganzzahlen ein, welche von rand() geliefert werden. Diese Sequenzen sind durch Aufruf von srand() mit dem selben Ursprungswert wiederholbar. Um bei jedem Programmlauf einen anderen Startwert mit srand zu setzen wird gerne als Argument das Ergebnis der Funktion time() verwendet: srand(time(NULL));.
A.8 limits.h
In dieser Bibliothek werden mit #define Konstanten f¨ ur die Grenzen der Int-Bereiche definiert (Auszug aus einer limits.h):
# define CHAR_BIT 8
# define SCHAR_MIN (-128) # define SCHAR_MAX 127 # define UCHAR_MAX 255 # define SHRT_MIN (-32768) # define SHRT_MAX 32767 # define USHRT_MAX 65535 # define INT_MIN (-INT_MAX - 1) # define INT_MAX 2147483647 # define UINT_MAX 4294967295
ANHANG A. C-STANDARD-BIBLIOTHEK 154
# define LONG_MAX 2147483647L
# define LONG_MIN 2147483648L # define ULONG_MAX 4294967295L
Je nach Compiler-Implemntierung k¨ onnen unterschiedliche Werte definiert sein.
A.9 float.h
In dieser Bibliothek werden mit #define Konstanten f¨ ur die Grenzen und Genauigkeiten der Fließkomma-Datentypen definiert (Auszug aus einer float.h):
#define FLT_MAX 3.40282347e+38F
#define FLT_MIN 1.17549435e-38F #define DBL_MAX 1.7976931348623157e+308 #define DBL_MIN 2.2250738585072014e-308 #define FLT_EPSILON 1.19209290e-07F #define DBL_EPSILON 2.2204460492503131e-16 #define FLT_DIG 6 #define DBL_DIG 15
Die Konstanten ... MAX und ... MIN geben gr¨ oßten und kleinsten darstellbaren Wert an (klein im Sinne von “nahe beiu Null“. Die Konstanen geben die kleinste m¨ ogliche Differenz zweier Zahlen an und die Konstanten ... DIG die Mantissenl¨ ange.
Anhang B
C-Syntax
Syntaxdiagramm 5: Bezeichner
Syntaxdiagramm 6: Nicht-Ziffer ¨ ¨ ¨ ¨ ¨ ... ...
Syntaxdiagramm 7: Ziffer
¨
Syntaxdiagramm 8: Nicht-Null-Ziffer ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
Syntaxdiagramm 9: for-Schleife
¨ ¨
Syntaxdiagramm 10: while-Schleife
¨ ¨ ¨
E while E ( E Ausdruck E ) E Anweisung E
© © ©
Syntaxdiagramm 11: do-while-Schleife
ANHANG B. C-SYNTAX 156
¨ ¨ ¨ ¨
E do E Anweisung E while E ( E Ausdruck E E
) © © © ©
Syntaxdiagramm 12: if-else-Statement ¨
Syntaxdiagramm 13: switch-case-Statement
¨ ¨ ¨
E switch E ( E Ausdruck E ) E Anweisung E
© © ©
Anhang C
Priorit ¨ at der Operatoren
Anhang D
ASCII-Tabelle
Die ASCII-Codes 0 bis 31 (dez) stellen Steuerzeichen dar. In der Tabelle sind nur die Steuerzeichen eingetragen, f¨ ur die es in C Escapesequenzen gibt. stellt das Leerzeichen dar.
Die Codes von 128-255 (dez) sind nicht standardisiert, und von Betriebssystem zu Betriebssystem unterschiedlich belegt. So k¨ onnen Programme, die deutsche Umlaute verwenden, auf einem anderen Bestriebssystem z.B. falsche Anzeigen verursachen. In Zeiten der 7-bit-Datenverarbeitung musste - da es keine Codes > 127 gab - im ASCII-Code einige Zeichen durch die deutschen Umlaute ersetzt werden. So gibt es eine deutsche Variante des 7-bit-ASCII-Codes.
Programme, die auf unterschiedlichen Plattform laufen sollen, m¨ ussen daher die deutschen Umlaute in Variablen halten, die z.B. beim Programmstart abh¨ angig vom Betriebssystem initialisiert werden.
Index
Arrays,
siehe
Felder
Backtracking, 127
Bin¨ are Suche, 117 time.h, 153 ctype.h, 151
Dateien
¨ offnen, 102 Zugriffsmodus, 103 Datentypen, 22 Fließkommazahlen, 26 Ganze Zahlen, 23 Dreieckstausch, 75
Escape-Sequenzen, 24
Fakult¨ at, 113
Felder, 83 float.h, 154
GGT, 76, 114
Gr¨ oßter gemeinsamer Teiler, siehe GGT
Hanoi, T¨ urme von, 123
Intervallhalbierung, 63
Kommandozeilenparameter, 87
limits.h, 153
math.h, 152
Mittelwertregel, 61
Nebeneffekt, 29
Operatoren
Priorit¨ at, 29, 157
Primzahlen, 65
Rekursion, 111
Schleifen, 46
Fußgesteuert, 54 Kopfgesteuert, 52 Z¨ ahlergesteuert, 47 Seiteneffekt, 29
Arbeit zitieren:
Winfried Bantel, 2001, Strukturierte Programmierung in C, München, GRIN Verlag GmbH
Dieser Text kann über folgende URL aufgerufen und zitiert werden:
Einbetten
DOI
Produktlebenszyklus und seine Bedeutung im Marketing
BWL - Didaktik, Wirtschaftspädagogik
Unterrichtsentwurf, 21 Seiten
Schülerfirma in der SFG – Erfahrungen aus Rheinland-Pfalz
Pädagogik - Heilpädagogik, Sonderpädagogik
Examensarbeit, 116 Seiten
Pädagogik - Allgemeine Didaktik, Erziehungsziele, Methoden
Hausarbeit (Hauptseminar), 21 Seiten
Bauwirtschaftliche und baubetriebswirtschaftliche Untersuchung zum Ein...
Ingenieurwissenschaften - Bauingenieurwesen
Diplomarbeit, 124 Seiten
Winfried Bantel hat den Text Strukturierte Programmierung in C veröffentlicht
Winfried Bantel hat einen neuen Text hochgeladen
Produktlebenszyklus und seine Bedeutung im Marketing
BWL - Didaktik, Wirtschaftspädagogik
Unterrichtsentwurf, 21 Seiten
Schülerfirma in der SFG – Erfahrungen aus Rheinland-Pfalz
Pädagogik - Heilpädagogik, Sonderpädagogik
Examensarbeit, 116 Seiten
Pädagogik - Allgemeine Didaktik, Erziehungsziele, Methoden
Hausarbeit (Hauptseminar), 21 Seiten
Bauwirtschaftliche und baubetriebswirtschaftliche Untersuchung zum Ein...
Ingenieurwissenschaften - Bauingenieurwesen
Diplomarbeit, 124 Seiten
Mit Fallbeispielen aus realen ...
Thomas Grechenig, Mario Bernhart, Roland Breiteneder, Karin Kappel
Lehrbuch der Softwaretechnik: Basiskonzepte und Requirements Engineeri...
Basiskonzepte Und Requirements...
Helmut Balzert
Genetische Algorithmen - Strat...
Ingrid Gerdes, Frank Klawonn, Rudolf Kruse
0 Kommentare