Grundlagen der Programmierung und Einführung in die …zeller/HomePage/VorlProg/programmieren1.pdf · textuelle Beschreibung nach formalen Regeln Natürliche Sprache - nicht formal

STUDIENGANG ANGEWANDTE INFORMATIK

STUDIENGANG INFORMATIONS- UND

KOMMUNIKATIONSTECHNIK

VORLESUNGSUNTERLAGEN ZU PROGRAMMIEREN 1

Grundlagen der Programmierung und Einführung in die Sprache C

Prof. Dr.-Ing. Silvia Keller

Ausgabe: 24.09.00 Seitenzahl: 108

Programmieren 1 Prof. Dr.-Ing. Silvia Keller Studiengang Angewandte Informatik Ausgabe: 24.09.00 Seite 2 von 108

INHALTSVERZEICHNIS

1 GRUNDLAGEN DER PROGRAMMIERUNG 4

1.1 Vom Problem zu Programm, der Algorithmus 41.1.1 Entwurf eines Algorithmus für ein Suchproblem 61.1.2 Programmablaufplan und Struktogramm 8

1.2 Arbeitsweise einer programmierbaren Rechenmaschine 15

1.3 Compiler, Interpreter, Binder, Lader 171.3.1 Compiler 171.3.2 Binder 181.3.3 Interpreter 18

1.4 Programmiersprachen 191.4.1 Syntaxdiagramme 191.4.2 Datentypen und Variablen 211.4.3 Operatoren, Ausdrücke, Anweisungen 241.4.4 Unterprogramme und Funktionen 25

2 EINFÜHRUNG IN DIE SPRACHE C 27

2.1 Aufbau und Struktur eines C-Programms 292.1.1 Funktionen in C 32

2.2 Elementare Datentypen, Variablen und Operatoren 382.2.1 Definition von Variablen 442.2.2 Gültigkeitsbereiche von Variablen 452.2.3 Die wichtigsten Operatoren 48

2.3 Kontrollstrukturen 552.3.1 Fallunterscheidungen 552.3.2 Schleifen 60

2.4 Ein-/Ausgaben zur Kommunikation mit dem Anwender 622.4.1. Formatierte Bildschirmausgabe 622.7.2. Eingabe von Tastatur 64

3 ELEMENTARE ALGORITHMEN 66

3.1 Suchen von Werten 66

3.2 Sortieren von Listen 683.2.1 Sortieren mit dem Verfahren InsertienSort 68

3.3 Sortieren und Suchen von strings 70

4 UNTERPROGRAMMTECHNIK 73

4.1 Prozeduren und Funktionen 74

4.2 Parameter 75

4.3 Definition von Funktionen in C 76


4.4 Makros 794.4.1 Vergleich Unterprogrammtechnik mit Makros 82

E Ergänzungen zu Operatoren und Ausdrücken 84E.1 Besondere Operatoren 84E.2 Implizite Typwandlung in Ausdrücken 86

5 TEST VON PROGRAMMEN 88

6 REKURSIVE ALGORITHMEN 91

6.1 Rekursion versus Iteration am Beispiel der Fakultät 91

6.2 Die Türme von Hanoi 95

5.3 Rekursives Sortieren 99

7 SORTIEREN UND SUCHEN NACH DEM HASH-VERFAHREN 102

7.1 Sortieren mit Hash-Funktionen 102

7.2 Suchen 103

7.3 Kollissionen 103

7.4 Löschen 104

7.5 Eigenschaften einer Hash-Funktion 1057.5.1 Beispiel für übliche Hash-Funktionen 1057.5.2 Beispiele für Kollissions-Funktionen 105

LITERATURVERZEICHNIS 106

A ANHANG 107A1 Rangfolge von Operatoren 107A2 Syntaxdiagramme 107A3 ANSI-Funktionen 108


1 Grundlagen der Programmierung

1 . 1 V O M P R O B L E M Z U P R O G R A M M , D E R A L G O R I T H M U S

Prof. Dr. - Ing. S.Keller FH Ravensburg-Weingarten echnische nformatik 22.09.1997

Algorithmen - Vom Problem zum Programm

Algorithmus

Hardwareorientierte problemorientierte Programmiersprache

textuelle Beschreibung nach formalen Regeln

Natürliche Sprache- nicht formal

Maschinensprache

Übersetzer( Compiler )

Entwerfen

ProblemProgramm Problemlösung

in grafischer Form

Ablaufpläne Struktogramme

Algorithmus: Eine Beschreibung, durch welche Operationen und Daten die Lösungeines Problems realisiert werden kann. Der Lösungsprozeß kommt nachendlich vielen Operationen zum Stillstand.

Zur Beschreibung eines Algorithmus benötigt man:

8 Vorrat von Operationen

8 Daten bestimmten Typs wie Zahlen, Buchstaben, logische Werte ...

8 Ausdrucksmittel zur Steuerung der Reihenfolge, in der die Operationen auszuführen sind

ð Kontrollstrukturen

Die Beschreibung kann erfolgen in:

8 grafischer Form: ð Ablaufpläne, Struktogramme

8 textlicher Form: ð Pseudocode, Programmiersprache

B e i s p i e l :

EIN KOCHREZEPT IST EIN ALGORITHMUS. DAS KOCHREZEPT BESCHREIBT EINEN PROZEß , WIE AUS DENZUTATEN EINE SPEISE ZUBEREITET WIRD. DATEN SIND DIE ZUTATEN/MENGEN. OPERATIONEN SIND MISCHEN,RÜHREN, SCHLAGEN, .....


D I E E N T W U R F S S C H R I T T E

P R O B L E M

ò

Feststellen und Festhalten von Randbedingungen

• Wie sehen die Eingangsdaten aus ?• Welche Resultate sind zu erzielen und in welcher Form ?• Welche Sonderfälle können auftreten und wie soll auf diese reagiert

werden ?

ò

Analyse der Problemstellung

• Einordnen in eine Problemklasse• Zerlegen in Teilprobleme und finden von Teillösungen• Zusammensetzen der Lösung aus den Teillösungen

ò

Entwurf eines Algorithmus ( i.a. in grafischer Form )

ò

Formulieren in einer Programmiersprache

ò

P R O G R A M M


1 . 1 . 1 E n t w u r f e i n e s A l g o r i t h m u s f ü r e i n S u c h p r o b l e m

Gegeben ist eine Liste von ganzen Zahlen und eine ganze Zahl N. Man soll feststellen,ob die Zahl N in der Liste enthalten ist.

E N T W U R F S S C H R I T T E :

A ) F e s t s t e l l e n d e r R a n d b e d i n g u n g e n

Es sind folgende Fragen noch zu klären:

8 Wie groß ist die Liste der Zahlen ? Ist die Länge fest oder variabel ? Wie erhält man die Längeder Liste, im Falle einer variablen Größe ?

Antwort: Die Länge der Liste ist variabel. Das Ende der Liste wird durch die Zahl-1 gekennzeichnet. Die Liste kann maximal 255 Werte enthalten.

8 In welchem Zahlenbereich liegen die Werte in der Liste ?Antwort: Die Liste enthält nur Zahlen >= 0. Der größte Wert wird durch die im

Rechner maximal darstellbare Zahl beschränkt.

8 Ist die Liste sortiert oder unsortiert ? Wenn sortiert, aufsteigend oder absteigend sortiert ?Antwort: Die Liste ist unsortiert

8 Wie soll das Ergebnis der Suche aussehen im falle daß die Zahl in der Liste vorkommt und imFalle, das die Zahl nicht in der Liste enthalten ist ?

Antwort: Wird die Zahl N in der Liste gefunden soll die Antwort lauten:Die Zahl N kommt an der Position i in der Liste vor.

Wird die Zahl N in der Liste nicht gefunden soll die Antwort lauten:Die Zahl N kommt in der Liste nicht vor

8 Wie soll das Ergebnis lauten, wenn die Zahl N mehrfach in der Liste vorkommt ?

Antwort: Es ist nur das erste Vorkommen der Zahl N in der Liste relevant.

B ) P r o b l e m a n a l y s e

Dieses Beispiel ist der erste Algorithmus, der in der Vorlesung behandelt wird. Es sind daher noch keineProblemklassen bekannt. Das Problem führt zur ersten elementaren Problemklasse „SUCHPROBLEM „.Eine Zerlegung in Teilprobleme ist nicht nötig, da es sich um ein elementare Problemklasse handelt.

C ) E n t w u r f

Erster Ansatz formuliert in natürlicher Sprache:Durchlaufe die Liste vom Anfang bis zum Ende und vergleiche jedes Listenelement mit der Zahl Nsolange bis entweder die Zahl N in der Liste gefunden wurde oder das Listenende erreicht ist

Zweiter Ansatz formuliert in einer vereinfachten formalen Schreibweise (Pseudosprache ):Algorithmus: SucheBenötigte Daten: Liste Liste von maximal 256 ganzen Zahlen. Das Ende der

Liste wird durch den Wert -1 angezeigt.

1 2 3 4 5 6 7 8

1. ZahlListe[1]

LetzteZahlListe[8]

N Die gesuchte ZahlIndex Die aktuelle Position eines Wertes in der Liste


Aktionen: Index := 1; ( Beginne mit dem ersten Wert in der Liste )Wiederhole die folgende Zuweisung solange bis Liste[Index] = N oder Liste[Index] = -1

Index:=Index+1 ( Nächste Position in der Liste )Falls Liste[Index] den Wert N hatte so antworte

Die Zahl N steht an Position Index in der Listesonst antworte

Die Zahl N kommt in der Liste nicht vor.

Index wird im Laufe des Algorithmus verändert und ist damit eine Variable. Werte, die sich nicht verändern,sind Konstanten .Der Algorithmus enthält folgende Kontrollstrukturen:

8 eine Wiederholung von Aktionen solange bis eine Bedingung erfüllt ist, die bedingte Schleife

8 In Abhängigkeit davon, ob eine Aussage wahr oder falsch ist sollen zwei unterschiedlicheAktionen erfolgen, die Fallunterscheidung

Dritte Variante grafisch formuliert als Programmablaufplan:

Index:=1

Schleifen-Bedingung

Index:=Index + 1

wahr

falsch Schleifen-Bedingung: Liste[Index] ungleich N und Liste[Index] ungleich -1

Liste[Index] = N

Die Zahl kommt an der Position Index in der Liste vor

Die Zahl kommt in der Liste nicht vor

wahr falsch

Schleife

Fallunterscheidung

D) Formuliert in der Programmiersprache C

void suche( int Liste[], unsigned int N )

{ unsigned short Index;

Index=0;

while ( Liste[Index] != N && Liste[Index] != -1 ) Index=Index+1;

if ( Liste[Index]== N )

printf(“Die Zahl %u steht an Position %hu in der Liste\n“, N, Index );

else printf(“Die Zahl %u kommt in der Liste nicht vor\n“,N );

}


In C wird das erste Element einer Liste immer mit dem Index 0 angesprochen.

In einer Liste mit 32 Werten wird der erste Wert mit dem Index 0 und der letzte Wert mit dem Index 31angesprochen.

B e i s p i e l :

int Liste[32]; /* Definition einer Liste mit 32 Werten */

Liste[0]=1; /* Erster Wert ist die Zahl 1 */

Liste[31]=32; /* Letzter Wert ist die Zahl 32 */

Im obigen Beispiel wurden folgende C Elemente verwendet:

Kommentarzeichen /* */Operatoren = Zuweisung eines Wertes an eine Variable

== Vergleich zweier Werte auf Gleichheit!= Vergleich zweier Werte auf Ungleich&& Logisches UND

Eine Ausgabe auf dem Bildschirm erfolgt über die Anweisung printf. Alle Stellen in printf, die mit % beginnen,werden durch Variablenwerte ersetzt.

1 . 1 . 2 P r o g r a m m a b l a u f p l a n u n d S t r u k t o g r a m m

Strukturtheorem: Um den Kontrollfluß eines Programms zu beschreiben reichen drei ( Böehm, Jacopini, 1966 ) Arten von Strukturblöcken aus ( Kontrollstrukturen eines Programms )

ðSequenz

Fallunterscheidung ( Selektion )

Schleife ( Iteration )

R E G E L N D E R S T R U K T U R I E R T E N P R O G R A M M I E R U N G :( Dijkstra, 1968 )

1. Ein Strukturblock hat genau einen Eingang und genau einen Ausgang

2. Aneinanderreihen und Ineinanderschachteln von Strukturblöcken ergibt wieder einen Strukturblock

3. Jeder Strukturblock muß mindestens einmal erreicht und verlassen werden

4. Elementare Strukturblöcke sind die Zuweisung ( a := b ) oder Unterprogrammaufrufe ( Makroblöcke )


1 . 1 . 2 . 1 P R O G R A M M A B L A U F P L Ä N E Z U R B E S C H R E I B U N G E I N E S A L G O R I T H M U S

Programmablaufpläne beschreiben die Abarbeitungsreihenfolge von Programmanweisungen.Grundelement ist ein Strukturblock, in dem eine elementare Anweisung abgearbeitet wird.

Anweisung

Dieses Grundelement kann in den 3 Arten von Strukturblöcken - Sequenz, Fallunterscheidung undSchleife - vorkommen.

Der Vorteil von Programmablaufplänen ist, daß sie sehr einfach und schnell gezeichnetwerden können. Nachteil ist jedoch, daß Strukturblöcke entstehen können, die denRegeln der strukturierten Programmierung widersprechen

A) Die Sequenz

entsteht durch Hintereinanderreihung von Strukturblöcken. Die Strukturblöcke werden in Pfeilrichtungnacheinander abgearbeitet.

Anweisung1

Anweisung2

Neuer Strukturblock SEQUENZ

B) Fallunterscheidung

Nach Auswertung von Aussagen wird entweder der Strukturblock Anweisung1 ausgeführt, wenn dieAussage wahr ergibt, oder es wird der Strukturblock Anweisung2 ausgeführt, wenn die Aussage falschergibt.

Anweisung2Anweisung1

Beding.wahr falsch

B e i s p i e l e :

• Wenn es regnet gehe ich Turnen sonst gehe ich Fußball spielen ( Natürliche Sprache )


• Pseudocode :

if Wetter=Regen then Turnen else Fußball spielenendif

Es gibt den Sonderfall, daß im Falle von falsch gar kein Strukturblock ausgeführt wird.

Anweisung1

Beding.wahr falsch

B e i s p i e l :

• Wenn ich im Lotto gewinne kaufe ich mir eine Villa ( sonst nicht )• if Lottogewinn=true then Villa kaufen endif

Es gibt auch Fallunterscheidungen, bei der nach Auswerten einer Bedingung mehrerer Fälle zuunterscheiden sind.

Anweisung1

Beding.

Anweisung2 Anweisungk Anweisungn

Fall1 Fall2 Fallk Falln

B e i s p i e l :

• Falls es regnet gehe ich turnen, falls es schneit gehe ich Ski fahren, falls es windet gehe ich surfen,falls die Sonne scheint gehe ich schwimmen sonst lese ich.

• In Pseudocode:

Case Wetter ofRegen : Turnen;Schnee: Skifahren;Wind: Surfen;Sonne: Schwimmen;else Lesen.;

endcase

Fußballsp.Turnen

wahr falschWetter =Regen

Turnen

Wetter

Ski fahren Surfen Schwimmen

Regen Schnee Wind Sonne

Lesen

sonst


C) Schleifen

Eine Schleife ist eine Wiederholung von Anweisungen in Abhängigkeit von einer Bedingung.Man unterscheidet zwei Varianten von bedingten Schleifen.

In der ersten Variante wird zuerst eine Bedingung geprüft. Ergibt die Auswertung der Bedingung wahr, sowerden die Anweisungen in der Schleife wiederholt, bis die Bedingung falsch wird. Bei dieser Art vonSchleife kann schon beim ersten Auswerten der Bedingung falsch ergeben, so daß die Anweisungen derSchleife nicht ausgeführt werden, d.h. die Schleife wird 0-mal durchlaufen.

B e i s p i e l :

• Solange es regnet arbeite ich am Schreibtisch• while Wetter=Regen do Arbeit am Schreibtisch endwhile

In der zweiten Variante werden zuerst die Anweisungen in der Schleife ausgeführt und dann erst dieBedingung geprüft. Ergibt die Auswertung der Bedingung wahr, so werden die Anweisungen in der Schleifewiederholt, bis die Bedingung falsch wird. Bei dieser Art von Schleife werden damit die Anweisungenmindestes einmal ausgeführt.

B e i s p i e l :

• Ich warte solange das Telefon nicht klingelt.• do warten while Telefon <> klingeln

Es gibt den Sonderfall einer Schleife, bei der von vornherein feststeht wie oft die Schleifedurchlaufen wird. Solche Schleifen nennt man Zählschleifen.

Im Unterschied zu den Zählschleifen ist bei bedingten Schleifen, die Anzahl von Durchläufen nicht vonvornherein bekannt ist, der Schleifenabbruch wird erst bei Ausführen der Schleifenanweisungen berechnet .

Es kann gezeigt werden, daß jeder Algorithmus auf die Variante 1 von bedingten Schleifenzurückgeführt werden kann d.h. jede bedingte Schleife der Variante 2 und jede Zählschleifekann durch eine bedingte Schleife der Variante 1 realisiert werden.

Bedingung

A

wahr

falsch

Bedingung

A

wahr

falsch


B e i s p i e l s t r u k t u r i e r t e r u n d u n s t r u k t u r i e r t e r P l ä n e

Strukturierter Plan:

Die Strukturblöcke werden entweder aneinandergereiht oder ineinander geschachtelt ( Hierarchische Verfeinerung )

Beding.wahr falsch

A

B

C D

E

Unstrukturierter Plan:

Merkmale sind:

8 der unkontrollierte Gebrauch von Sprüngen

8 es können keine Strukturblöcke gefunden werden

8 die Programmzustände sind damit nur schwer erkennbar

Beding.falsch

A

B

wahr

C

Beding.falsch

Dieser Strukturblock

hat 2 Ausgänge

Sprung in eine Schleife

• Weitere Beispiele siehe Übungsblatt 1


R e s ü m e e

8 Man kann auch in einer nicht strukturierten Programmiersprache wie Assembler oder C gutstrukturierte Programme erstellen

8 Die Verwendung einer strukturierten Sprache wie PASCAL bedeutet nicht, daß nur guteProgramme entstehen

8 Die Verwendung sinnvoller Bezeichner gehört ebenso zu einer guten Programmiertechnik wieeine saubere Strukturierung

1 . 1 . 2 . 2 S T R U K T O G R A M M E ( N A S S I - S C H N E I D E R M A N N - D I A G R A M M E )

Vorteil: Strukturblöcke können nur aneinandergereiht oder ineinander verschachtelt werden.Es können daher nur Strukturblöcke verwendet werden, die den Regeln der Strukturierten Programmierung folgen.

Nachteil: Komplexe und aufwendige Grafiken

Name des Algorithmus

KurzbeschreibungDatenobjekte

M-NAME

b

Makro-Block;wird in einem gesonderten Struktogramm verfeinertM-NAME : Bezeichner für Teilalgorithmus

Elementarblock;b: logische Beschreibung der Aktionen

Struktogramm zu einemAlgorithmus/Programm


Kontroll-struktur

Struktogramm Pseudocode C-Syntax

1Sequenz Anweisung1

Anweisung2

begin Anweisung1 Anweisung2end

{ Ausdruck1; Ausdruck2;}

2Fallunter-scheidung

A1

Bedingung

A2 A3 A4

a b sonstccase Bedingungofa: A1;b: A2;c: A3;sonst: A4;endcase

switch ( Bed ){ case a: A1; case b: A2; case c: A3; default: A4;}

Sonderfall:vollständigeAlternative

A1

A2

wahr falsch

Bedingung if Bedingungthen A1else A2endif

if ( Bed ) A1;else A2;

Sonderfall:einfacheAlternative

A1 ---

wahr falsch

Bedingung if Bedingungthen A1endif

if ( Bed ) A1;

3SchleifenBedingteSchleife

A1

solange Bedingung

A1

solange Bedingung

while Bedingungdo Anweisung1endwhile

do Anweisung1while Bedingung

while ( Bed ) A1;

do Anweisung1while ( Bed )

Zählschleife

A1

von i=Anfang bis EndeSchrittweite = k

Jede Zählschleife kann durch eine while-Schleiferealisiert werden

forSchleifenzähler :=Anfangswertto EndwertwithSchrittweite := kdo Anweisung1endfor

for(Sz=Aw;Sz<=Ew; Sz++) A1;

for(Sz=Aw;Sz>=Ew;Sz--) A1;


1 . 2 A R B E I T S W E I S E E I N E R P R O G R A M M I E R B A R E N R E C H E N M A S C H I N E


Von Neumann Rechnerarchitektur

8 Maschinenprogramm : Sequenz von Grundoperationen derMaschine

CPU

Speicher

Tastatur Bildschirm

Programme abarbeitenDatenwerte berechnen

Maschinenprogramm

veränderbare Variablen ( Daten ) des Programms

Daten eingeben Daten ausgeben

B a s i s z y k l u s d e r R e c h e n m a s c h i n e :

1. Maschinenbefehl aus dem Speicher holen

⇓

2. Programmzeiger auf das nächste Speicherwort setzen

⇓

3. Befehl interpretieren

⇓

4. Befehl ausführen

⇓

5. weiter bei 1



Arbeitsspeicher

0011011011111111000011001100110010101010

01

32

4

Speicherzelle8 Bit = 1 Byte

Speicheradresse

Die Speicherzellen sind fortlaufend nummeriert

Speicherzellen enthalten entweder - Maschinenbefehle oder - Daten

Befehl 1Befehl 2Befehl 3Befehl 4

Befehl 99Befehl 100Variable 1Variable 2

Programmzeiger

Beim Sprungbefehl wird der Programmzeiger auf einen bestimmten Befehl versetzt

Bei der Abarbeitung der Befehle wird der Programmzeiger automatisch immer auf den nächsten Maschinenbefehl verschoben

Sequentielle Abarbeitung der Maschinenbefehle


1 . 3 C O M P I L E R , I N T E R P R E T E R , B I N D E R , L A D E R


Programmierumgebung

8 Übersetzer, Binder und Lader sind Systemprogramme, die im Arbeitsspeicher liegen unddem Anwender ermöglichen den eigene Programme zu schreiben.

Quell-text

ÜbersetzterCompiler

Programm-objekt

LaderLoader

BinderLinker

lauffähiges-Maschinen-programm

VorgefertigteProgramm-

objekte

Maschinen-programm

Datei mit dem Progrannformuliert in einer

Programmiersprache Im Arbeitsspeicher

Datei enthält ein

unfertiges Programm in Maschinensprache

Datei mit einem

ausführbaren Maschinenprogramm

( Executable )

1 . 3 . 1 C o m p i l e r

Programme werden als Text formuliert ( Quelltext ) und durch einen Compiler in eine, der Rechenmaschineverständliche Sprache übersetzt. Der Compiler ist selbst ein Maschinenprogramm, das auf dem Rechnerausgeführt wird und zum Betriebssystem des Rechners gehört. Der Compiler speichert das übersetzteProgramm auf der Festplatte in einer Datei ab.

Die Aufgaben des Compilers sind:

8 Zeichenweises einlesen des als Text formulierten Programms ( Quelltext )

8 Erkennung von Grundsymbolen. Dies sind:

• Operatoren wie z.B. = , + , - , /, & .....

• Trennzeichen wie z.B. ( ) { } , : ; [ ] ......

• Schlüsselworte wie if, then, else, while, .....

• Konstanten wie 1, -5, +1.5, - 3e10 .....

• Bezeichner, das sind Namen für Programmobjekte, die der Programmierer selbstvergeben kann wie z.B. Variablennamen

8 Prüfen auf syntaktische KorrektheitJede Sprache wird aufgebaut aus Grundsymbolen z.B. besteht unsere natürlicheSprache aus Worten, die nur Zeichen aus unserem Alphabet enthalten. DieseGrundsymbole können nur nach bestimmten Regeln, die die Grammatik der Sprachedefinieren, zu Sätzen zusammengebaut werden.


B e i s p i e l f ü r e i n e G r a m m a t i k r e g e l d e r d e u t s c h e nS p r a c h e :

Ein Satz setzt sich zusammen aus Subjekt, Prädikat und Objekt.

Die Menge aller Grundsymbole und die grammatikalischen Regeln wird Syntax einerSprache genannt.

Zur Syntax einer Programmiersprache gehören daher Regeln, die angeben wie dieGrundsymbole der Programmiersprache miteinander kombiniert werden dürfen., so daßein korrektes Programm entsteht.

Diese Regeln können entweder in textueller Form ( Backus Nauer Form : BNF ) oderaber in grafischer Form, den Syntaxdiagrammen, angegeben werden.

8 Übersetzen des Textes in die MaschinenspracheEin Maschinenbefehl ist ein Speicherwort bestehend aus einer bestimmten Folge von0 und 1 Werten.

1 . 3 . 2 B i n d e r

Ein Programm benutzt i.a. vorgefertigte Programmobjekte, die nachträglich zu dem übersetzten Programmhinzugefügt werden. Solche vorgefertigten Programmobjekte sind Systemfunktionen wie z.B.Programmstücke mit denen man Daten einlesen und ausgeben kann( in der Programmiersprache C : printf zur Ausgabe auf dem Bildschirm ).

Der Programmierer kann sein Programm jedoch in einzelne Teile ( Programmodule ) zerlegen, die ergetrennt übersetzt, in Objektdateien speichert und dann später erst beim Binden alle diese vorübersetztenModule miteinander zu einem lauffähigen Programm zusammenfügt ( Modulares Programmieren ). Dasbeim binden entstandenen lauffähige Programm, das in einer Datei auf Festplatte gespeichert ist, nenntman executable.

Erst durch den Lader wird das in Maschinensprache übersetzte Programm von Datei in den Arbeitsspeichergeladen und dort von der CPU ausgeführt.

1 . 3 . 3 I n t e r p r e t e r

Ein Compiler übersetzt das Programm, das nur als komplett lauffähigen Programm in den Arbeitsspeichergeladen werden kann. Erst nach dem Laden des vollständigen Programms kann das Programmabgearbeitet werden. Fehler im Programm werden daher erst noch vollständiger Übersetzung entdeckt.

Interpreter übersetzen das Programm zeilenweise. Jede Zeile wird sofort in Maschinensprache übersetztund auch sofort ausgeführt. Fehler im Programmfluß können sofort während der Übersetzung erkanntwerden. Nachteil: Die Programmabarbeitung wird deutlich langsamer, da nach jeder Ausführung vonMaschinenanweisungen erst wieder der Interpreter nie nächste Zeile bearbeitet.


1 . 4 P R O G R A M M I E R S P R A C H E N

1 . 4 . 1 S y n t a x d i a g r a m m e

Syntaxdiagramme beschreiben die Aufbauregeln einer Programmiersprache. Die folgende Tabelle zeigt allegrafischen Symbole, die als Ausdrucksmittel in Syntaxdiagrammen vorkommen.

Regelform SyntaxdiagrammGrundsymbolDiese Symbole sind die Grundsymbole derProgrammiersprache und damit nicht weiterzerlegbar

A

Nichtterminales SymbolDies sind Symbole, die zur Beschreibung derRegeln notwendig sind und ersetzt werden durchneue Symbolfolgen. Diese Ersetzung endet immerdann, wenn nur noch Grundsymbole vorkommen.

a

Symbolfolge aAa

Ersetzungsregel ( Produktion )

Aab

AlternativeA

B

C

Option

aWiederholung

aCa

Wiederholung als Optionaa

C


B e i s p i e l e a u s d e r P r o g r a m m i e r s p r a c h e C

8 Bezeichner ( identifier )

Zeichen

Zeichen

Ziffer

8 Ziffer ( digit )

0 1 2 3 4 5 6 7 8 9

8 Zeichen

_ A Z a z... ...

Gültige Bezeichner sind damit: Index, index, INDEX, Zahl1, N10t2

Ungültige Bezeichner sind: 1DM, $wert, n%, suche-wert

8 Sequenz ( compound statement )

declaration statement

{ }

8 While-Schleife ( while statement )

while ( expression statement)


1 . 4 . 2 D a t e n t y p e n u n d V a r i a b l e n

Prof. Dr. - Ing. S.Keller FH Ravensburg-Weingarten Technische Informatik 29.09.1997

8 Datenwerte, die eine Anzahl vonSpeicherzellen imArbeitsspeicher belegen

8 Die Datenwerte können vomProgramm verändert werden

Datentypen und Variablen

Variable Datentyp

Arbeitsspeicher

8 Beschreibt den Wertebereicheiner Variable

8 Angaben für den Compiler wieviele Speicherzellen für dieDarstellung der Werte benötigtwerden und wie die Werte interndargestellt sind

8 belegen keinen Speicherplatz

Elementar

Strukturiert

Variablen sind Speicherzellen, deren Werte während der Programmabarbeitung verändert werdenBei der Definition erhält die Variable einen Namen. Über diesen Namen kann die Variable im Programmangesprochen werden. Eine Variable muß daher am Programmanfang vor ihrer Verwendung definiertwerden.

Konstanten sind Werte, die nicht veränderbar sind. Konstanten sind entweder

8 direkte Wertangaben wie z.B. 1, -1.5, ‘z’ oder

8 Namen, die einen konstanten Wert benennen wie z.B. der Konstantenname PI

B e i s p i e l f ü r e i n e V a r i a b l e n d e f i n i t i o n e n i n C

int zahl; /* Die Variable zahl wird definiert. Der Datentyp von Zahlist int */

int wert = 1; /* Die Variable wert wird definiert Die Speicherzelle wirdmit der Konstanten 1 vorbelegt */

B e i s p i e l f ü r K o n s t a n t e n i n C

#define FALSE 0 /* Die Konstante FALSE wird mit 0 festgelegt */

const double pi=3.1415926535; /* Die Konstante pi wird definiert und mit einem Wert vorbelegt */


1 . 4 . 2 . 1 E L E M E N T A R E D A T E N T Y P E N

Elementare Datentypen werden durch die Programmiersprache vorgegeben. Ein Wert wird in einemSpeicherwort abgelegt. Wobei ein Speicherwort 1, 2 oder auch mehrere Byte lang sein kann.

Elementare Datentypen sind:

8 Ganze Zahlen ( integer ) Eine Untermenge der ganzen Zahlen bilden die positiven ganzen Zahlen mit Werten >= 0 unddie natürlichen Zahlen mit Werten > 0

8 Reelle Zahlen ( real )

8 Zeichen ( character )Zeichen sind Buchstaben, Ziffern, Trennzeichen, Sonderzeichen und spezielleSteuerzeichen, die zur Ansteuerung von Ausgabegeräten benötigt werden.Im genormten ASCII-Zeichensatz werden 256 Zeichen in einem Byte codiert.

8 Logische Werte ( boolean )

Es gibt nur zwei mögliche Werte wahr (true) oder falsch (false ). Zur Darstellung derWerte würde daher 1 Bit genügen. Da der Arbeitsspeicher jedoch byteweise organisiertist, wird ein logischer Wert immer in einem Byte abgelegt.

8 Zeiger ( pointer )Zeiger sind Variablen, deren Wert als Referenz ( Zeiger ) auf ein Datenobjekt interpretiertwird.

Zeigervariable Datenobjekt

4711

Der Wert des Datenobjektes kann entweder direkt über den Namen der Variablen oderindirekt über den Zeiger angesprochen werden.

B e i s p i e l :

Direkte Ansprache über den Namen: „Herr Meier, würden Sie bitte wiederholen „

Indirekte Ansprache über Zeigen mit dem Zeigefinger: „ Würde Sie bitte wiederholen „

1 . 4 . 2 . 2 S T R U K T U R I E R T E D A T E N T Y P E N

Strukturierte Datentypen setzen sich aus mehreren Datenelementen zusammen und werden vomProgrammierer festgelegt. Die Programmiersprache stellt hierfür spezielle Konstruktionsregeln bereit.

8 Aufzählungstypen

Der Programmierer definiert eine geordnete Menge von möglichen Werten, die untereinem Typnamen zusammengefaßt werden. Die Ordnung wird durchAufzählungsreihenfolge festgelegt.

B e i s p i e l a u s C :

enum Tage { januar, februar, maerz, april, mai };


Die Werte werden durch den C Compiler hintereinander im Speicher abgelegt. Wobeijedem Wert eine Nummer beginnend mit 0 zugeordnet wird.

8 Zeichenketten ( string )Zeichenketten sind eine lineare Folge von Zeichen. Strings werden benötigt um Worteund Texte zu speichern.

8 Felder ( array )Felder sind Datenstrukturen, in denen alle Datenelemente vom gleichen Typ sind undnach Zeilen/Spalten-Regeln zusammengebaut werden.

Eindimensionale Felder sind Listen von gleichartigen Datenwerten. Die einzelnen Wertewerden hintereinander lückenlos im Arbeitsspeicher abgelegt. Auf einzelne Datenwertekann im Programm über Angabe der Position ( Index ) zugegriffen werden.

Beispiel: ( 1, 4, 7, 101, 66, 4711, 75, 35 )

Beispiel aus C:

int liste[32]; /* Definition einer Liste mit 32 ganzen Zahlen. */

liste [5]= 4711; /* In C wird das erste Element einer Listeimmer mit dem Index 0 angesprochen. In diesem Fall erhält daher das 6. Element inder Liste den Wert 4711 */

Mehrdimensionale Felder sind entsprechend der mathematischen Definition vonmehrdimensionalen Räumen zu verstehen z.B.

ist

015472511

324711

eine zweidimensionale Matrize.

Beispiel aus C:

int matrix[10][30]; /* Definition einer Matrix mit 10 Zeilen und 30 Spalten */

liste [0][0]= 4711; /* Das Datenelement in der 1. Zeile und 1. Spalte erhält den Wert 4711 */


8 Datensätze ( record )

Zusammenfassung von Datenelementen unterschiedlichen Typs zu komplexstrukturierten Datenobjekten. So können Daten zu einer Person wie Vorname,Nachnahme, Alter, Größe, Gewicht und Geburtsdatum in einer Variablen gespeichertwerden.

Vorname Nachname

Alter Geburtsdatum

Groesse Gewicht

1 . 4 . 3 O p e r a t o r e n , A u s d r ü c k e , A n w e i s u n g e n

Jede Programmiersprache stellt eine Menge von Operatoren für die Berechnung von komplexen Ausdrückenzu Verfügung.

Zu den Grundoperationen gehört:

8 der Zuweisungsoperator . Er wird benötigt um Variablen Werte zuweisen zu könnenBeispiel aus C: zahl = 5;

wert = zahl + 1;8 arithmetische Operatoren wie die MULTIPLIKATION, DIVISION, SUBTRAKTION, ADDITION

8 logische Operatoren zur Bestimmung von logischen werten von Ausdrücken wie UND, ODER,NICHT

8 Vergleichsoperatoren zum Vergleichen zweier Werten wie KLEINER, GRÖßER, KLEINER-GLEICH,GRÖßER-GLEICH, UNGLEICH, GLEICH

Die Operatoren werden zusammen mit Variablen und Konstanten zu komplexen Ausdrücken verknüpft.Jeder Ausdruck hat einen Wert als Resultat. Dieser Wert hat einen zugeordneten Datentyp. Will man denberechneten Wert aufheben, so muß man das Resultat in einer Variablen mit den korrekten Datentypspeichern ( Zuweisungsoperator )

B e i s p i e l a u s d e r S p r a c h e C

int zahl = 2, wert = 10;zahl * ( 5 + wert ) / ( zahl + 8 ); /* Ausdruck mit Resultat 3 */erg = zahl * ( 5 + wert ) / zahl + 10; /* Resultat wird in erg gespeichert */

Neben den Operatoren zu Bildung von Ausdrücken muß jede Programmiersprache Anweisungen zuVerfügung stellen, mit Hilfe derer man Daten einlesen und Ausgeben kann und die den Kontrollfluß desProgramms steuern.


1 . 4 . 4 U n t e r p r o g r a m m e u n d F u n k t i o n e n

Ein Unterprogramm ist eine Zusammenfassung eines Programmteils zu einem Programmobjekt, das einenNamen erhält und immer dann, wenn der Unterprogrammname im Programm auftaucht abgearbeitet wird.

G r ü n d e f ü r d i e E r s t e l l u n g v o n U n t e r p r o g r a m m e n :

8 Einsparen von Schreibarbeit, wenn Programmteile öfter an verschiedenen Stellen vorkommen

8 Wiederverwendung von schon vorhandenen Programmteilen z. B. die Verwendung vonUnterprogrammen, mit denen man Daten einlesen kann ( in C printf ) oder Datenwerte in eineDatei schreiben kann.

8 Klare Strukturierung von Programmen. Beim Entwurf eines komplexen Algorithmus wird das vorgegebene Problem in Teilproblemezerlegt. Jedes Teilproblem wird separat bearbeitet. Diese Teile werden dann als Unterprogrammerealisiert.

M a n u n t e r s c h e i d e t z w e i A r t e n v o n U n t e r p r o g r a m m e n

8 die Prozedur ist eine Zusammenfassung von Aktionen.

8 die Funktion hat die Aufgabe aus Eingangswerten einen Ergebniswert zu berechnen.

P a r a m e t e r v o n U n t e r p r o g r a m m e n

In ein Unterprogramm können auch Werte aus dem aufrufenden Programm übergeben werden.

Diese Werte werden als Parameter bezeichnet. DasUnterprogramm kann dann die Werte seiner Parameter inAnweisungen verwenden.

Betrachten wir als Beispiel die Definition einer Funktion. In der Mathematik wird eine Funktion z.B. in derForm y = sin ( x ) dargestellt.

Die Funktion heißt sin und berechnet den Sinus einer gegeben Zahl x. Eine Funktion erhält also eineeindeutigen Namen. x ist Platzhalter für den Eingangswert, y ist Platzhalter für den Ergebniswert derFunktion. Setzt man für x einen bestimmten Wert ein, so erhält man genau einen Ergebniswert. Wird inobiger Funktion für x der Wert 90 Grad eingesetzt erhält y den Wert 1.

Grafische Darstellung einer Funktion als Black Box

Den Platzhalter für den Eingangswert bezeichnet man inProgrammiersprachen als formalen Parameter einesUnterprogramms. Formale Parameter werden bei der Definitioneines Unterprogramms benötigt. Beim Aufrufen einesUnterprogramms wird dann der formale Parameter x durch einenkonkreten Wert ersetzt. Dieser Wert wird aktueller Parametergenannt.

Im Falle einer Funktion erhält man nach Abarbeitung des Unterprogramms einen Ergebniswert, den man ineiner Variablen ( hier y ) speichern muß. Prozeduren als Zusammenfassung von Aktionen können zwarWerte aus dem übergeordneten Programmteil erhalten, liefern jedoch keinen Wert zurück.

ProgrammParameter

Unterprogrammverwendet a und b

a b

sinx y

Eingabewert Ergebniswert

Algorithmus zurBerechnung des

Sinus


K o n t r o l l f l u ß b e i m U n t e r p r o g r a m m a u f r u f


8 wird genau einmalin den Arbeits-speicher geladen

Unterprogrammtechnik

UP-Name

Definition eines

Unterprogramms

8 mehrfache Verwendungdes Unterprogrammsim Hauptprogramm

Haupt-programm

UP-Name

UP-Name

Haupt-programm

Unter-programm

UP-Name

UP-Name

Arbeits-speicher

Anspringendes

Unterprogramms

Rücksprungins

Hauptprogramm

A u f r u f h i e r a r c h i e v o n U n t e r p r o g r a m m e n

Die Verwendung von Unterprogrammen dient hauptsächlich der hierarchischen Strukturierung vonProgrammen. Ein Hauptprogramm verwendet z.B. die Unterprogramme BERECHNE und TUE . DasUnterprogramm BERECHNE ruft die Unterprogramme POTENZ und WURZEL auf.. Das UnterprogrammTUE ruft das Unterprogramm AUSGABEZEILE aus. Das Unterprogramm AUSGABEZEILE verwendet einweiters Unterprogramm AUSGABEZEICHEN. Somit entsteht eine Aufrufhierarchie, die man grafischdarstellen kann.

Haupprog

BERECHN TUE

POTENZ WURZEAUSGABEZEILE

AUSGABEZEICHEN

Programmieren 1 Prof. Dr.-Ing. Silvia Keller Studiengang Angewandte Informatik Ausgabe: 24.09.00 Seite 27 v o n108

2 Einführung in die Sprache C

Geschichte von C

• 1965 MULTICS 1. Multiuser/ Multitasking Betriebssystem• 1969 UNIX Ken Thompson, 1. Version auf PDP-7, Assembler• 1970 Sprache B Ken Thompson, 2. Version UNIX auf PDP-7,

Grund Portierbarkeit• 1971 Sprache C Dennis M. Rithie ( AT&T),• 1973 UNIX Dennis Ritchie, Ken Thompson, 3. Version UNIX

auf PDP-11 ( 1000 Zeilen Assembler, Rest C )• 1977 Veröffentlichung Buch Rithie, Brian Kernighan:

" The C Programming Language "

– >> verschiedene UNIX Derivate und Portierungen• 1989 ANSI-Standard ( American National Standard Institute )

Prof. Dr. S. Keller FH Ravensburg-Weingarten/Technische Informatik Programmieren 3


C Compiler

8 Funktionalität des Präprozessors:

Quelltextmit

Steuer-anweisungen

für den Präprozessor

PräprozessorÜbersetzbarer

C-Quelltext

eigentlicherÜbersetzer

Programm-objekt

einzufügendeTextdateien

8 Einfügen zusätzlicher Textdateien8 Definition von Makros8 Bedingte Übersetzung

8 Der Präprozessor ist ein reinesTextverarbeitungsprogramm,kein Übersetzer


P R Ä P R O Z E S S O R A N W E I S U N G E N

Diese Anweisungen beginnen mit einem # und steuern die Aktionen des Präprozessors vor dereigentlichen Übersetzung :

Syntax: # <Anweisung>

Die beiden häufigsten Anweisungen, die in einem C-Programm vorkommen sind

8 die include-Anweisung

Sie bewirkt, daß an der aktuellen Position der Inhalt einer Textdatei einkopiert wird.

B e i s p i e l e

#include <stdio.h> /* Einfügen einer Textdatei mit dem Namen stdio.h. Diese Datei liegt in einem Systemverzeichnis */

#include “meintext.h“ /* Einfügen der Textdatei meintext.h.Diese Datei liegt im aktuellenArbeitsverzeichnis des Programmierers

*/8 die define -Anweisung

Diese Anweisung dient der Benennung von Textstücken, die häufig verwendet werden( Definition eines Textmakros ). Jedes Auftauchen des Makronamen ( Name desTextstückes ) bewirkt, daß an Stelle des Namen das durch den Makronamen benannteTextstück eingefügt wird ( Makroexpansion )

B e i s p i e l e

#define N 16 /* Festlegung, dass jedes Auftauchen vonN im Quelltext, durch 16 zu ersetzenist */

a = a + N ; /* N wird ersetzt durch 16 */

Die Define-Anweisung wird häufig benutzt um Konstanten im Programm zu benennen. DieKonstanten werden in einer Headerdatei definiert und immer bei Gebrauch über eine include-Anweisung eingebunden. Bei Änderung des Wertes so definierter Konstanten muß der Wertnur an einer Stelle ( in der Headerdatei ) geändert werden. Das C-Programm selbst bleibtunverändert.


2 . 1 A U F B A U U N D S T R U K T U R E I N E S C - P R O G R A M M S

Ein C-Programm besteht aus einem oder mehreren Unterprogrammen. Jedes Unterprogramm in C isteine Funktion. Prozeduren kennt die Programmiersprache C nicht.

Genau eine dieser Funktionen muß den Namen main haben. Diese Funktion main enthält das eigentlicheHauptprogramm. Jede weitere Funktion ist ein Unterprogramm des Hauptprogramms.Die Gesamtheit aller in einer Datei vorhandenen Funktionen bilden ein Modul.

Das einfachste C Programm besteht aus genau einem Modul. In diesemModul existiert genau eine Funktion mit den Namen main.

B e i s p i e l f ü r e i n e i n f a c h e s C - P r o g r a m m

/*********************************************************************//* Modul Erstprog.c enthält als einzigste Funktion die Funktion main *//*********************************************************************/#include <stdio.h>

/* stdio wird benötigt, da die ANSI-Funktion printf zur Ausgabe auf dem Bildschirm verwendet wird */

/* Definition des Hauptprogramms */int main(void){ char c; /* Definition einer Variablen vom Typ char ( Zeichen )*/

/* Ausgabe eines Textes auf dem Bildschirm */

printf(" \n------ ASCII-Tabelle --------------------------------------\n");

/* Zaehlschleife von Startwert char(0) bis Endwert char(z) */ /* Die Schleifenanweisung gibt ein Zeichen und eine ganze Zahl am Bildschirm aus */

for ( c='0'; c<='z'; c=c+1) printf("%c -> %i \t",c,c);

/* Ausgabe eines Textes auf dem Bildschirm */ printf(" \n-----------------------------------------------------------\n");

/* Beenden des Programms mit dem Rueckgabewert OK an das Betriebssystem */

return 0;}

Das Hauptprogramm ist eine Funktion ohne Parameter, die eine ganze Zahl berechnet.Das eine Funktion keine Parameter besitzt, wird durch das Schlüsselwort void angezeigt.Will man in einem Programm Bildschirmausgaben erzeugen, so muß man vordefinierte Funktionen, imobigen Beispiel die Funktion printf verwenden. Die Funktion printf ist ein vorübersetztesProgrammobjekt, das in Maschinensprache vorliegt, und zusammen mit ähnlichen vorübersetztenFunktionen in einer Funktionsbibliothek liegt Zu jeder Bibliothek gibt es eine Textdatei mit gleichemNamen, die man zusätzlich zu dem vorübersetzten Programmobjekt benötigt. Diese Texdatei wird alsHeaderdatei bezeichnet, da sie am Modulanfang ( Kopf des Moduls ) mit der #include-Anweisungeinkopiert werden muß. Die Funktion printf liegt in der Bibliothek stdio, also muß als erste Anweisung imModul, vor der Funktion main, die Headerdatei stdio.h einkopiert werden.

main()

Programm

Modul


Die Anweisungen eines Programms bzw. der Funktion main stehen zwischen { und }.{ kennzeichnet den Beginn der Programmanweisungen,} kennzeichnet das Ende der Programmanweisungen.

Jedes Programm benötigt Variablen zur Speicherung von Datenwerten. Eine Variable kann inProgrammanweisungen erst dann verwendet werden, wenn Name und Typ bekannt sind. Die Variablenmüssen daher immer am Anfang einer Funktion definiert werden, damit man sie in Anweisungenverwenden kann.

Eine Funktion wird durch die Anweisung return beendet. Der Wert hinter der return-Anweisung ist derErgebniswert der Funktion, der an das aufrufende Programm übergeben wird. Im Falle der Funktion mainist das aufrufende Programm das Betriebssystem des Rechners. Das Ergebnis der Funktion main ist 0,falls das Programm korrekt abgearbeitet wurde. Im Fehlerfall kann die Funktion main eine Fehlernummerübergeben.Im obigen Beispiel wird jedoch immer der Wert 0 als Ergebnis geliefert.

Wird ein Programm größer und komplexer, so zerlegt man dasProgramm in kleinere Untereinheiten (Unterprogramme). Das CProgramm besteht damit aus der Funktion main, die dasHauptprogramm enthält und einer Menge von weiteren Funktionen,die als Unterprogramme vom Hauptprogramm verwendet werden.Das Beispiel aus Kapitel 1.4.4 kann z.B. wie im Bild nebenanrealisiert sein. Das Programm besteht aus einem Modul, in demneben der Funktion main sechs weitere Funktionen vorkommen. DieAufrufhierarchie zu dem Programm ist in Kapitel 1.4.4 beschrieben

main()

berechne()

tue()

potenz()

wurzel()

AusgabeZeile()

AusgabeZeichen()

ProgrammModul


M o d u l a r e s P r o g r a m m

Im obigen Beispiel kann man einige Funktionen zu einer Gruppe zusammenfassen.

Die Funktionen potenz, wurzel,AusgabeZeile und AusgabeZeichen sindz.B. Programmteile, die soallgemeingültig sind, daß sie nicht nur indiesem Programm, sondern auch inanderen Programmen Verwendungfinden können, wenn man sie alseigenständige Programmobjekte ineinem eigenen Modul definiert.Man kann die sieben Funktionen ausobigem Programm also auf mehrereModule verteilen. Jedes Modul wirdunabhängig von den anderen Modulenübersetzt. Jede Funktion des Modulswird damit zu einem eigenständigenProgrammobjekt, das auch in anderenProgrammen benutzt werden kann.Durch diese Modularisierung entstehenProgrammbausteine, die alleine für sichkein lauffähiges Programm ergeben.

Durch den Binder können die Programmbausteine zu einem lauffähigen Programm zusammengebautwerden. Die vier Funktionen in Modul 3 können so auch in anderen Programmen verwendet werden.

Ein modulares Programm hat den Vorteil,

8 es ist gut strukturiert,

8 einfach zu warten und

8 enthält wiederverwendbare Programmbausteine.

main()berechne()

tue()

potenz()

wurzel()

AusgabeZeile()

AusgabeZeichen()

ProgrammModul 1

Modul 3

Modul 2


2 . 1 . 1 F u n k t i o n e n i n C


Funktionen in C

Definition

Funktions-aufruf

Prototyp

Verwendung einer Funktionnach der Definition im Modul

Verwendung der Funktionohne vorherige Defintion

im Modul

Ankündigung der Verwendung einer noch nicht

definierten Funktion

2 . 1 . 1 . 1 D E F I N I T I O N E I N E R F U N K T I O N E N

Eine Funktion in C besteht aus:

8 dem Funktionskopf

Dieser besteht aus dem Funktionsnamen, den formalen Parametern und dem Ergebnistyp

8 dem Funktionsrumpf

Der Funktionsrumpf enthält die Anweisungen der Funktion. Jede Funktion muß über eine Anweisung return einen Ergebniswert an das aufrufendeProgramm übergeben.



Vereinfachtes Syntaxdiagramm - Funktionsdefinition

identifier (type specifier )

parametertype list

compoundstatement

parametertype list

identifiertype specifier

,

compoundstatement

{ }

declaration statement

B e i s p i e l e :

Es soll eine Funktion zum addieren zweier ganzen Zahlen programmiert werden. Der Nameder Funktion soll add sein. Die Funktion benötigt zwei formale Parameter a und b. Beide sindganze Zahlen. Das Ergebnis der Funktion ist eine ganze Zahl.

int add(int a, int b) /* Funktionskopf */{ int erg; /* der Rumpf wird durch die {} zu einem Block

zusammengefasst */ erg = a+b; /* Addition beider Parameter */ return erg; /* Beenden der Funktion und Übergabe des Ergebnisses

an das Hauptprogramm */}

Es soll eine Funktion programmiert werden, die den Sinus einer reellen Zahl berechnet. DerName der Funktion soll sin sein. Die Funktion benötigt einen Parameter x. x ist eine reelleZahl. Das Ergebnis der Funktion ist eine reelle Zahl.

double sin( double x )

{ double y; /* Variable zur Speicherung des Ergebniswertes */

/* --------------------------------------------------------------- */

/* Hier ist ein Algorithmus zur Berechnung des Sinus implementiert */

/* --------------------------------------------------------------- */

return y; /* beenden der Funktion und Übergabe des Ergebnisses */

}


2 . 1 . 1 . 2 A U F R U F E N V O N F U N K T I O N E N

Im vorliegenden Beispiel verwendet das Hauptprogramm die beiden oben definierten Funktionen addund sin.Beim Aufrufen einer Funktion muß für jeden formalen Parameter ein aktueller Wert angegeben werden.Das Ergebnis wird einer Variablen zugewiesen. Aktueller Parameter der Funktion sin ist 90 Grad.Aktueller Parameter der Funktion add ist die Zahl 15 und das Ergebnis der Funktion add. Der aktuelleParameter einer Funktion kann also wieder über eine Funktion berechnet werden. Ein Aufruf der gleichenFunktion als Parameter ist möglich.

int main() /* Hauptprogramm */{ int erg; /* Definition der Variablen erg als ganze Zahl

*/ double y; /* Definition der Variablen y als reelle Zahl */

erg=add(15,add( 5, 4 )); /* Aufruf d. Funktion add mit aktuellenParametern */

y=sin(90.0); /* Aufruf der Funktion sin */ return 0; /* Beenden der Funktion. Rückgabewert ist o.k.

*/}


2 . 1 . 1 . 3 P R O T O T Y P E N V O N F U N K T I O N E N

Jeder Bezeichner kann in einem Programm nur dann verwendet werden, wenn der Bezeichner vorseiner ersten Verwendung dem Compiler bekannt gemacht wurde ( Definition von Programmobjekten ).

Die Funktion main im obigen Beispiel kann daher die beidenFunktionen add und sin nur dann verwenden, wenn im Modul alledrei Funktionen vorhanden sind und die beiden Funktionen add undsin vor der Funktion main definiert wurden.

B e i s p i e l

/***************************************************************************//* Modul HAUPT.c *//* Enthaelt die Funktionen add, sin, main *//* add und sin muessen vor main definiert sein *//***************************************************************************/

int add(int a, int b) /* Funktionskopf */{ int erg; /* der Rumpf wird durch die {} zu einem Block

zusammengefasst */ erg = a+b; /* Addition beider Parameter */ return erg; /* Beenden der Funktion und Übergabe desErgebnisses an das Hauptprogramm */}

double sin( double x )


/* --------------------------------------------------------------- */


/* --------------------------------------------------------------- */


}

int main() /* Hauptprogramm */{ int erg; /* Definition der Variablen erg als ganze Zahl */ double y; /* Definition der Variablen y als reelle Zahl */

erg=add(15,add( 5, 4 )); /* Aufruf d. Funktion add mit aktuellen Parametern */

y=sin(90); /* Aufruf der Funktion sin */ return 0; /* Beenden der Funktion. Rückgabewert ist o.k. */}

main()

add()

sin()

ProgrammModul HAUPT


Erstellt man ein modulares Programmkann diese Forderung nicht mehreingehalten werden.Wird z.B. main in einem Modul HAUPTund die Funktionen add und sin in einemModul MATH erstellt, so sind bei derÜbersetzung des Moduls HAUPT diebeiden Funktionsnamen noch nichtdefiniert. Damit das Modul maintrotzdem übersetzt werden kann, mußder Programmierer vor der Funktion main

die Verwendung beider externer Funktionen durch den Prototyp ankündigen. Der Prototyp macht demCompiler den Funktionsnamen, Anzahl und Typ der Parameter sowie den Ergebnistyp bekannt.

B e i s p i e l

/******************************************************************//* Modul HAUPT enthält nur die Funktion main *//******************************************************************/extern int add( int, int ); /* Prototyp von add */extern double sin ( double ); /* Prototyp von sin */

/* Jetzt kann main die beiden extern definierten Funktionen verwenden */



y=sin(90); /* Aufruf der Funktion sin */ return 0; /* Beenden der Funktion. Rückgabewert ist o.k. */

}

Die Prototypen werden auch dann benötigt, wenn alle drei Funktionen in einem Modul liegen, dieFunktion main jedoch vor den beiden Funktionen add und sin definiert wird. In diesem Fall entfällt jedochdas Schlüsselwort extern bei den Prototypen, da die Funktionen intern definiert werden.

main()

add()

sin()

ProgrammModul HAUPT

main()add()

sin ()

Programm

Modul HAUPT Modul MATH


B e i s p i e l

/**********************************************************************//* Modul HAUPT enthält alle drei Funktionen *//* Main wird jedoch vor add und sin definiert *//**********************************************************************/int add( int, int ); /* Prototyp von add */double sin ( double ); /* Prototyp von sin */

/* Jetzt kann main die beiden Funktionen verwenden */



y=sin(90); /* Aufruf der Funktion sin */ return 0; /* Beenden der Funktion. Rückgabewert ist o.k. */}int add(int a, int b) /* Funktionskopf */{ int erg; /* der Rumpf wird durch die {} zu einem Block

zusammengefasst */ erg = a+b; /* Addition beider Parameter */ return erg; /* Beenden der Funktion und Übergabe des Ergebnisses

an das Hauptprogramm */}double sin( double x )


/* --------------------------------------------------------------- */


/* --------------------------------------------------------------- */


}


2 . 2 E L E M E N T A R E D A T E N T Y P E N , V A R I A B L E N U N D O P E R A T O R E N

Datentypen in CProf. Dr. - Ing. S.Keller FH Ravensburg-Weingarten Technische Informatik Programmieren 3 10/28/97

Datentyp

Skalare Typen voidStrukturierte Typen

Zeigerarithmetische Typen

Ganze Zahlen

Aufzählungs-typen

ZeichenReelle Zahlen

Strukturenarray

Die Wertebereiche von skalaren Typen sind geordnet.Der Datentyp void ist ein spezieller Datentyp, der anzeigt, daß keine Typangabe möglich ist. Beispiele fürdie Verwendung von void werden im Verlauf der Vorlesung eingeführt.

G a n z e Z a h l e n

Der Wertebereich einer ganzen Zahl ist abhängig von der Anzahl von Binärziffern, die der Rechner zurDarstellung der Zahl verwendet.Bei vorzeichenbehafteten Zahlen, die n Bit dargestellt liegt der Wertebereich der Zahl bei:

- ( 2n-1 ) <= Zahl <= ( 2 n-1 ) -1

B e i s p i e l :Eine ganze Zahl wird auf dem PC in 16 Bit dargestellt.Der größte positive Wert ist in diesem Fall 215 – 1 = 32767,der kleinste negative Wert beträgt -32768.Addiert man auf den größten positiven Wert eine Konstante z.B. den Wert 1, so erhält man einenZahlenüberlauf. Der dargestellte Wert ist fehlerhaft. Das gleiche passiert, wenn man von der kleinstennegativen Zahl eine Konstante subtrahiert.Das folgende C-Programm demonstriert diesen Effekt.

/**************************************************************************/

/* Programm zur Demonstration eines Zahlenüberlaufes */

/**************************************************************************/

#include <stdio.h> /* Enthält den Prototyp von printf() */

/****** Festlegung von Namen für Konstanten ******************/

#define MAXINT 32767 /* Groesste positive ganze Zahl */

#define MININT -32768 /* Kleinste negative Zahl */


/************** Hauptptogramm **************************************/

int main(void)

{ int zahl1=MININT, zahl2=MAXINT;

printf(" Zahl2 enthält die größte positive Zahl: %i\n",zahl2);

/* Addiert man auf zahl2 eine positive Konstante so erhält man einen

Zahlenüberlauf */

zahl2 = zahl2 + 1;

printf(" Zahl2 + 1 ergibt den Wert: %i\n\n",zahl2);

printf(" Zahl1 enthält die kleinste negative Zahl: %i\n",zahl1);

/* Subtrahiert man auf zahl1 eine positive Konstante so erhält man einen

Zahlenüberlauf */

zahl1 = zahl1 - 1;

printf(" Zahl1-1 ergibt den Wert: %i\n",zahl1);

return 0;

}

Im Falle von positiven ganzen Zahlen, die mit n Bit dargestellt werden, ist der Wertebereich:

0 <= Zahl <= 2 n -1

B e i s p i e l :

Eine ganze Zahl wird auf dem PC in 16 Bit dargestellt.Der größte positive Wert ist in diesem Fall 216 - 1 = 65535.Addiert man auf diesen Wert die Konstante 1 so erhält man einen Zahlenüberlauf. Der dargestellte Wertist fehlerhaft.

/**************************************************************************/

/* Programm zur Demonstration eines Zahlenüberlaufes */

/**************************************************************************/

#include <stdio.h>

#define MAXINT 65535u


int main(void)

{ unsigned int zahl1=MAXINT;

printf(" Zahl1 enthält die groesste positive Zahl: %u\n",zahl1);

/* Addiert man auf zahl1 eine positive Konstante so erhält man einen

Zahlenüberlauf */

zahl1 = zahl1 + 1;

printf(" Zahl1+1 ergibt den Wert: %u\n",zahl1);

return 0;

}

In C gibt es mehrere Standardtypen:

8 int, long int , short int sind vorzeichenbehaftete ganze Zahlen

8 Mit dem Zusatz unsigned definiert man positive ganze Zahlen also:

unsigned int, unsigned long int, unsigned short int

I N T K O N S T A N T E N

Konstante Werte in einem Programm sind automatisch vom Typ int, falls keine weitere Angabe gemachtwird.Ein Wert kann als Dezimalzahl, als Oktalzahl ( Basis 8 ) oder als Hexadezimalzahl ( Basis 16 )angegeben werden.

B e i s p i e l e f ü r K o n s t a n t e n :

10 /* Dezimalkonstante vom Typ int */4711 /* Dezimalkonstante vom Typ int */4711u /* Dezimalkonstante vom Typ unsigned int */

-1 /* Dezimalkonstante vom Typ int */-1L /* Dezimalkonstante vom Typ long int */

0 /* Oktalkonstante vom Typ int */0xff /* Hexadezimalkonstante vom Typ int */


integer-KonstantenProf. Dr. - Ing. S.Keller FH Ravensburg-Weingarten Technische Informatik Programmieren 3 //

0Ziffer

Oktalkonstante

Nichtnull-Ziffer

Ziffer

0 ... 91 ... 9

Dezimalkonstante

0x Ziffer

0X

Hexadezimalkonstante

Dezimalkonstante

Oktalkonstante

Hexadezimalkonstante

L

L

l

l

U

U

u

u

longunsigned

R e e l l e Z a h l e n

Auch bei reellen Zahlen kennt C mehrere Typen, die sich in der Genauigkeit der Zahlendarstellungunterscheiden:

8 float,

8 double

8 long double

Bei der Verwendung reeller Zahlen sollte man beachten, daß eine reelle Zahl in einem Rechner alsDualzahl i.a. nicht exakt dargestellt werden kann. Ein Vergleich auf Gleichheit zweier reellen Zahlen istdaher sehr gefährlich. Auch ein Vergleich auf den exakten Wert 0 sollte vermieden werden.

D O U B L E K O N S T A N T E N

Konstante Werte in einem Programm sind automatisch vom Typ double, falls keine weitere Angabegemacht wird.


10.0 /* Festpunkt-Konstante vom Typ Double */4.711f /* Festpunkt-Konstante vom Typ float */1.0e3 /* Gleitkomma-Konstante vom Typ double */-1.5643L /* Festpunktkonstante vom Typ long double */-1e3 /* Gleitkommakonstante vom Typ double */.0 /* Festpunktkonstante vom Typ double */1e-1 /* Gleitkommakonstante vom Typ double */


double-KonstantenProf. Dr. - Ing. S.Keller FH Ravensburg-Weingarten Technische Informatik Programmieren 3 02.11.1997

Dezimalkonstante

Festpunktkonstante L

l

F

f

Exponent

Ziffer

Ziffer

Festpunktkonstante

.

.

Exponent

ZifferE

e

-

+

Z e i c h e n

Mit char definiert man ein Zeichen in 7 Bit ASCII-Code dargestellt ( 128 unterschiedliche Zeichen ).

T a b e l l e d e s 7 - B i t A S C I I - C o d e s

Binär 000 001 010 011 100 101 110 111Dezimal 0 1 2 3 4 5 6 7

0000 0 NUL DLE Leerzeich. 0 @ P ` p0001 1 SOH DC1 ! 1 A Q a q0010 2 STX XON " 2 B R b r0011 3 ETX DC3 # 3 C S c s0100 4 EOT XOF $ 4 D T d t0101 5 ENQ NAK % 5 E U e u0110 6 ACK SYN & 6 F V f v0111 7 BEL ETB ' 7 G W g w1000 8 BS CAN ( 8 H X h x1001 9 HT EM ) 9 I Y i y1010 A LF SUB * : J Z j z1011 B VT ESC + ; K [ k {1100 C FF FS , < L \ l |1101 D CR GS - = M ] m }1110 E SO RS . > N ^ n ~1111 F SI US / ? O _ o DEL

Im 8-Bit ASCII-Zeichensatz können neben den normalen alfanumerischen Zeichen auch nationaleZeichen wie ä, ö, ü ,ß codiert werden.Ein 8-Bit Zeichen wird mit dem Datentyp unsigned char definiert.

In C gibt es die Besonderheit, das der Datentyp char ( Zeichen ) doppel belegt ist. Der Typchar definiert neben einem Zeichen gleichzeitig auch eine ganze Zahl, die in 8 Bit gespeichertist. Dieser Datentyp wird z.B. für Variablen genutzt, die als Laufindex für ein array verwendetwird, um Speicherplatz zu sparen. Unsigned char definiert damit eine positive ganze Zahl mit 8Bit Speicherlänge. Welche Interpretation bei der Verwendung einer Variablen vom Typ chargewählt wird, bestimmt der Programmierer durch sein Programm.


B e i s p i e l :

Im Programmbeispiel „ Einfaches C Programm „ auf Seite 27 wird die Variable c bei derBildschirmausgabe einmal als Zeichen (%c) und ein weiteres mal als ganze Zahl (%i) interpretiert.

Z E I C H E N K O N S T A N T E N

Konstante Werte werden in ‘ ‘ angegeben. Steuerzeichen und bestimmte Sonderzeichen werden durch \gefolgt von einem Kennzeichen angegeben.


‘A’ /* der Buchstabe A */‘1’ /* Die Ziffer 1 als zeichen, nicht die ganze Zahl 1 */‘\n’ /* Das Steuerzeichen Newline */‘\t’ /* Das Steuerzeichen Tabulator */‘\a’ /* Signalton */‘\f’ /* Das Steuerzeichen Form feed ( Neue Seite ) */‘\r’ /* Das Steuerzeichen carriag return ( Wagenrücklauf ) */‘\\’ /* Das Zeichen \ */‘\’’ /* Das Zeichen ‘ */‘\“’ /* Das Zeichen “ */

A u f z ä h l u n g s t y p e n

Aufzählungstypen erhalten einen durch den Programmierer selbstvereinbarten Typnamen und werdendurch das Schlüsselwort enum definiert.

B e i s p i e l :

enum Tag = { Montag, Dienstag, Mittwoch, Donnerstag, Freitag, Samstag, Sonntag } ;

Tag ist hier der Typname. Die Bezeichner in {} sind die Werte des selbstvereinbarten Typs.


S p e i c h e r g r ö ß e u n d W e r t e b e r e i c h e l e m e n t a r e r D a t e n t y p e n

Die folgende Tabelle gibt die Speichergröße und Wertebereiche dieser Datentypen in C an.Die Speichergröße von int, unsigned int, long double und enum sind systemabhängig und daher nichtohne weiteres fehlerfrei portierbar.

Datentyp Speichergröße Wertebereich(signed) char 8 Bit -128 ... 127

7-Bit ASCII Darstellungunsigned char 8 Bit 0 ... 255

8-Bit ASCII Darstellungint Systemabhängig

32 Bit ( Windows NT, SUN ) - 2 147 438 648 ... 2 147 438 647short 16 Bit -32 768 ... 32 767long 32 Bit -2 147 483 648 ... 2 147 438 647unsigned int Systemabhängig

32 Bit ( Windows NT, Sun ) 0 ... 4 294 967 259unsigned short 16 Bit 0 ... 65 535unsigned long 32 Bit 0 ... 4 294 967 295float 32 Bit 3.4e-38 ... 3.4e+38

( 7 Stellen Genauigkeit)( 23-Bit Mantisse, 8 BitExponent)

double 64 Bit 1.7e-308 ... 1.7 e+308(15 Stellen Genauigkeit)( 52 Bit Mantisse, 11 BitExponent)

long double Systemabhängig64 Bit

dto

enum Systemabhängig32 Bit 0 ... 4 294 967 295

2 . 2 . 1 D e f i n i t i o n v o n V a r i a b l e n

Bei der Definition von Variablen muß der Datentyp und ein Bezeichner angegeben werden.

Datentyp Bezeichner

Initalisierung

,

Der Compiler reserviert für die Variable Speicherplatz, der Wert der Variablen wird jedoch nichtautomatisch mit dem Wert 0 vorbelegt. Die Variable hat den Wert, der zufällig im Speicher steht. Mankann bei der Definition einer Variablen einen Wert vorgeben. In diesem Fall wird der Compiler dieVariable mit dem angegebenen Wert vorbelegen ( Initialisierung ):

R e g e l n f ü r B e z e i c h n e r ( a u c h F u n k t i o n s n a m e n )

8 Erlaubt sind Buchstaben, Ziffern und "_". Erstes Zeichen des Namens darf keine Ziffer sein.

8 Ein Name darf maximal 32 Zeichen lang sein.

8 Groß-/Kleinschreibung wird unterschieden. Bsp: var , VAR und Var sind drei unterschiedliche Bezeichner.


B e i s p i e l e

int zahl; /* Definition einer ganzen Zahl ( integer ). Der Wert von zahl ist undefiniert */

float fwert; /* Definition einer reellen Zahl (float). Der Wert von fwert ist undefiniert */

int zahl = 0; /* Definition einer ganzen Zahl ( integer ). zahl wird

mit dem Wert 0 vorbelegt */

double dwert=1.41; /* Definition einer reellen Zahl (double). dwert wird mit der double-Konstanten 1.41 vorbelegt */

int liste[32]; /* Definition einer Liste mit 32 ganzen Zahlen */

int liste[10]={2,5,7,3,10,11,23,26,13,47}; /* Definition einer Liste mit 10 ganzen Zahlen. Die Liste wird mit Werten vorbelegt */

int liste[32]={1,2,3}; /* Definition einer Liste mit 32 Zahlen. Die Liste wird mit den Werten 1,2,3 vorbelegt. Alle noch fehlenden Komponenten erhalten den Wert 0 */

int liste[]={1,2,3,4,5,6,7,8,9}; /* Definition einer Liste mit 9 Werten. DieAnzahl der Werte kann sich der Compileraus der Initialisierung selbst berechnen */

2 . 2 . 2 G ü l t i g k e i t s b e r e i c h e v o n V a r i a b l e n

Prof. Dr. - Ing. S.Keller FH Ravensburg-Weingarten Technische Informatik 10/23/97

Gültigkeitsbereiche von Variablen

Modul 1 Modul 2

Funktion 1 Funktion 2

gm

l lFunktion 3 Funktion 4

ll

Modulglobal Global

Lokal Lokal

8 g ist eine globale Variable und kann daher von allen Funktionenverwendet werden

8 m ist eine modulglobale Variable und kann nur von Funktioneninnerhalb des Modul 1 verwendet werden

8 l sind lokale Variablen, die nur innerhalb einer Funktion gültigsind.

In C unterscheidet man 3 Gültigkeitsbereiche:

8 Lokale Variablen

Der Name einer Variablen ist nur lokal in dem Block gültig, in dem die Variabledefiniert wurde.


Ein Block ist eine Folge von Anweisungen, die in { } steht. Blöcke können geschachtelt werden. Enthält ein Block weitere Unterblöcke, so ist dieVariable auch in den darunterliegenden Blöcken sichtbar.

Wird eine Variable am Anfang einer Funktion definiert, so ist diese Variable gültig inallen Blöcken der gesamten Funktion. Wird eine Variable am Anfang eines Blockesinnerhalb der Funktion definiert, so ist die Variable nur innerhalb des Blockes gültig,außerhalb des Blocks ist die Variable nicht sichtbar.

Wird eine Variable in mehreren geschachtelten Blöcken definiert, so überdeckt dieVariable eines inneren Block die Variable mit gleichem Namen im übergeordnetenBlock.

B e i s p i e l :

int main(void){ int i,zahl=-1; /* zahl und i sind lokal gültig in

allen Blöcken der Funktion main */ while ( zahl <= 0 ) { zahl=zahl+10;

printf("zahl in while %i\n",zahl); for ( i=1; i <= 10; i=i+1)

{ int zahl=i+1; /* zahl wird lokal fürdiesen Block definiertund überdeckt zahl ausmain*/

printf("zahl in for %i\n",zahl);

} /* endfor */

printf("zahl in while %i\n",zahl);

} /* endwhile */

return 0;} /* Ende Programm */

8 Globale Variablen

Eine Variable, die am Modulanfang außerhalb einer Funktion definiert wird ist globalgültig. Eine globale Variable ist in jeder internen und externen Funktion, d.h. auchaußerhalb des Modul, sichtbar.



Gültigkeitbereiche von Variablen

8 GlobaleZahl ist global gültig in allenFunktionen und allen Blöcken innerhalbund außerhalb des Moduls

8 LokaleZahl ist gültig innerhalb derFunktion und in den Blöcken A und B

8 a in Block a ist gültig in Block a b in Block A ist gültig in Block A und

BlockB8 a in Block B ist gültig in Block B c ist gültig in Block B

Modul HAUPT

int main(void)

int GlobaleZahl;

int LokaleZahl;

Block A

Block B

int a,b;

int a,c;

B e i s p i e l :

/*************************************************************/

/* Programm: Globale und Lokale Variablen */

/*************************************************************/

int GlobaleZahl = 100; /* Die Variable GlobaleZahl ist sichtbar in allen internen und allen externen Funktionen */

int main(void)

{ int LokaleZahl; /* Lokale Variable ist nur sichtbar innerhalb main*/

LokaleZahl=GlobaleZahl;

GlobaleZahl=GlobaleZahl+1; /* Die Globale Variable wird veraendert */

return 0;

}

8 Modulglobale VariablenEine globale Variable kann durch Angabe eines zusätzlichen Schlüsselwortes staticim Gültigkeitsbereich eingeschränkt werden. Die Variable ist zwar innerhalb desModuls global, kann also von jeder Funktion verwendet werden. Außerhalb desModuls ist die Variable jedoch nicht mehr sichtbar.


2 . 2 . 3 D i e w i c h t i g s t e n O p e r a t o r e n

An dieser Stelle werden nur elementaren Grundoperationen von C eingeführt. Neben diesen Operatorenkennt C weitere Operatoren, die vor allem zur Programmoptimierung, zur Schreiberleichterung oder inVerbindung mit Zeigern verwendet werden. Diese Operatoren werden später an geeigneter Stelleeingeführt.

A R T I H M E T I S C H E O P E R A T O R E N

Operator Argumenttyp Ergebnistyp Bedeutung* int

floatintfloat

Multiplikation

/ (unsigned) int

float

int

float

Ganzzahlige DivisionSind beide Operanden ganze Zahlen ist dasErgebnis immer eine ganze Zahl.Nachkommastellen werden abgeschnitten

Undefiniert bei neg. Zahlen.Compiler kann aufrunden oder auch abrunden

Reelle DivisionIst mindestens ein Operand eine reelle Zahlist das Ergebnis ebensfalls reell.

% (unsigned) int int Rest bei ganzzahliger Division ( Modulo )Undefiniert auf negative Zahlen.Compilerabhängig ist Ergebnis entweder positiv odernegativ

+ intfloat

intfloat

Addition

- intfloat

intfloat

Subtraktion

B E I S P I E L E :

Ausdruck Ergebnis

5 / 2 2

5 / -2 -2 oder -3 ; Bei negativen Operanden ist die Division nicht definiert. Der kann Compiler kann auf- oder abrunden

x / 0 undefiniert ; Division durch 0 ist nicht erlaubt

1 / 3 0

1.0 / 3.0 0.3333

5 % 2 1

-5 % 2 -1 oder 1 ; Modulo ist auf negative Operanden nicht definiert


V E R G L E I C H E N D E O P E R A T O R E N

Operator Argumenttyp Ergebnistyp Bedeutung< int, float Boolean

FALSCH : 0WAHR: 1

Vergleich auf Kleiner

<= int, float Boolean Vergleich auf Kleiner oder Gleich> int, float Boolean Vergleich auf Größer>= int, float Boolean Vergleich auf Größer oder Gleich== int, float Boolean Vergleich auf Gleichheit

Vorsicht bei reellen Zahlen !!= int, float Boolean Vergleich auf Ungleichheit

Ein Datentyp Boolean gibt es in C nicht.Logische Werte werden in C auf ganze Zahlen abgebildet.

Der logische Wert falsch entspricht dem Wert 0. Der logische Wert wahr ist ein Wert ungleich 0.Wird als Ergebnis eines Vergleiches ein logischer Wert berechnet so wird der Ergebniswert wahr durchdie Zahl 1 repräsentiert.

B E I S P I E L E :

Ausdruck Ergebnis

5 < 2 0 ( FALSCH )

5 > 2 1 ( WAHR )

5 == 2 0

5 != 2 1

1.5 <= 3.0 1

(1.0/3.0 + 1.0/3.0 + 1.0/3.0) == 1.0 01.0 / 3.0 ergibt 0.33333333......Diese Zahl ist nicht exakt im Rechner darstellbar. Eswerden Stellen abgeschnitten. Die Addition dieser dreiunexakten Zahlen ergibt nicht den exakten Wert 1.0.Daher Vorsicht bei Vergleichen mit reellen Zahlen

L O G I S C H E O P E R A T O R E N

Operator Argumenttyp Ergebnistyp Bedeutung! Boolean Boolean Verneinung&& Boolean Boolean Logisches UND|| Boolean Boolean Logisches ODER


B E I S P I E L E :

Ausdruck Ergebnis

0 && 1 0

1 && 1 1

5 && 2 1

5 || 0 1

!5 0

0 || 1 1

(5 < 2) && (3 < 10) 0

B I T O P E R A T O R E N

Operator Argumenttyp Ergebnistyp Bedeutungint int Komplement

& int int bitweise UND^ int int bitweise exklusiv oder ( antivalenz )| int int bitweise ODER

Bei den Bitoperatoren wird eine ganze Zahl als Bitmuster interpretiert. Die Operatoren verrechnen danndie einzelnen Bitpositionen miteinander.

B e i s p i e l :

unsigned short muster1, muster2;muster1=16 erzeugt folgendes Bitmuster im Speicher: 0000 0000 0001 0000muster2=15 erzeugt folgendes Bitmuster im Speicher: 0000 0000 0000 1111

Verrechnet man diese beiden Variablen mit dem Bitoperator ODER ( | ),so entsteht folgendes Bitmuster: 0000 0000 0001 1111Dieses entspricht dem Dezimalwert 31.

B E I S P I E L E :

Ausdruck Ergebnis

16 & 32 0

15 & 7 7

16 | 32 48

15 | 7 15


2 . 2 . 4 . A u s d r ü c k e

Ein Ausdruck dient der Berechnung eines Wertes. Ein Ausdruck hat damit immer ein Resultat mit einemvorbestimmten Datentyp.


Ausdrücke

8 Ausdruck enthält Variabeln,Konstanten, Operatoren undFunktionsaufrufe

Ausdruck Resultat Datentyp

Ein Ausdruck setzt sich zusammen aus Variablen, Konstanten, Operatoren und Funktionsaufrufen.Der häufigste Ausdruck ist ein Zuweisungsausdruck. In einer Ergebnisvariablen wird durch denZuweisungsoperator = der berechnete Wert eines Ausdruckes gespeichert. Der Zuweisungsausdruck ist selbstwieder ein Ausdruck, der ein Resultat abliefert. In diesem Fall ist das Resultat der Wert, der in derErgebnisvariablen gespeichert wurde.


Zuweisungsausdruck

Ergebnisvariable = Ausdruck

Zuweisungsausdruck

Resultat Datentyp

8 Wert, der in Ergebnisvariabelgespeichert wurde

8 der in Ausdruckberechnete Wert wirdin Ergebnisvariablegespeichert

Linke Seite und rechte Seite vomZuweisungsoperator

müssen vom gleichen Datentyp sein

B E I S P I E L E F Ü R E I N F A C H E A U S D R Ü C K E

int zahl1=1,zahl2=10,zahl3=5;

char symbol=‘s’, zeichen=‘a’

double mitte=0.0,laenge=10.5;

Ausdruck Typ desErgebniswertes

Resultat

zahl2 - zahl1 int 9

zahl2 / zahl3 int 2

laenge / 2.0 double 5.25

zahl3 = zahl2 % zahl3 int 0symbol + 1 char ‘t’


Tauchen in einem Ausdruck mehrere Operanden auf, so werden die Operationen entsprechend derRangordnung der Operatoren ausgeführt.

Die Rangordnung kann durch Klammern verändert werden.

Im Ausdruck 1 + 2 * 5 hat der Operator * den höheren Rang also wird zuerst 2 * 5 berechnet und danachauf den Ergebniswert 10 der Wert 1 addiert ( -> 11 )Der Ausdruck 1 + 2 * 5 entspricht dem Ausdruck 1 + ( 2 * 5 ).Man kann die Berechnung durch Klammern verändern (1 + 2 ) * 5 ergibt als Resultat den Wert 15.

Im folgenden ist die Rangordnung der eingeführten Operatoren angegeben:

* < ! / + <= == & ^ | && || =

% - > !=>=

----------------------------------------------------------------------------------------------------------->Rangordnung

2 . 2 . 4 . 1 W A N D L U N G V O N D A T E N T Y P E N

Gegeben ist folgende Aufgabe:

Gegeben ist eine Liste mit 10 ganzen Zahlen. Sie sollen den Mittelwert dieserZahlenreihe berechnen.

Sie entwerfen dazu folgenden Algorithmus:

Algorithmus: MittelwertDaten: summe Summe aller 10 Zahlen mittelwert Mittelwert index Position einer Zahl in der Liste N Anzahl der Zahlen in der Liste

Aktionen: N hat den Wert 10bilde die Summe der N Zahlen durch addieren aller N Zahlen in der Liste in einerZählschleife

mittelwert = summe dividiert durch N.


P r o g r a m m a b l a u f p l a n

Index:=1

index <= N

summe:=summe + liste[index]

wahr

falsch

Zählschleife

summe:=0

Index:=Index + 1

mittelwert:=summe / N

Den Algorithmus realisieren Sie durch folgendes C Programm.

#include <stdio.h>

#define N 10

main()

{

int index,summe=0,liste[N]={2,4,6,4,4,10,8,3,9,7};

float mittelwert=0.0;

for (index=0; index<N; index=index+1)

{ summe=summe+liste[index]; }

mittelwert = summe/N;

printf("der Mittelwert = %f\n",mittelwert);

return 0;

}

Als Ausgabe erhalten Sie den Wert 5. 000000. Dieser Wert ist fehlerhaft. Korrekt wäre der Wert 5.700000

Der Fehler liegt daran, daß bei der Berechnung des Mittelwertes eine ganzzahlige Division erfolgt.Summe / N ergibt eine ganze Zahl.


L ö s u n g : U m w a n d l u n g d e s D a t e n t y p s i n t i n d e n D a t e n t y p f l o a t .

In C exisitiert ein Operator, Cast-Operator genannt, mit dem man eine Typwandlung erzwingen kann. ( type casting )

Cast-Operator : ( zu erzeugender Datentyp )

Der cast-Operator wirkt sich nur auf den aktuell folgenden Wert in einer Anweisung aus. Dar Datentypvon Variablen und Konstanten wird also nur kurzfristig für die momentane Berechnung geändert.

L ö s u n g s v e r s u c h # 1 :

Mit dem cast-Operator ändern Sie die Mittelwertberechnung wie folgt ab:

mittelwert = (float) ( summe/N );

Auch diese Lösung liefert den Wert 5.000 als Mittelwert.

E r k l ä r u n g :

Es wird zuerst der Wert von ( summe / N ) berechnet. Ergebnis ist eine ganze Zahl. Diese ganze Zahlwird in eine reelle Zahl gewandelt( 5 ---> 5.0000 ).

L ö s u n g s v e r s u c h # 2 :

Sie ändern die Mittelwertberechnung wie folgt:

mittelwert = (float) summe / (float) N ;

Der int Wert summe und die int Konstante N werden vor der Division in reelle Zahlen vom Typ floatgewandelt. Erst danach wird die Division durchgeführt. Jetzt erfolgt eine reelle Division mit dem Ergebnis5.7. Dieser float-Wert wird dann in mittelwert gespeichert.


2 . 3 K O N T R O L L S T R U K T U R E N

2 . 3 . 1 F a l l u n t e r s c h e i d u n g e n

E i n f a c h e A l t e r n a t i v e

if ( <Ausdruck> ) <Anweisung> ;

Wenn die Berechnung von <Ausdruck> den Wert wahr ( also ein Wert <> 0 ) ergibt, so führe diefolgende Anweisung aus.Jede Anweisung kann auch durch einen Anweisungsblock ( compound statement ) ersetzt werden. EinAnweisungsblock ist eine Folge von Anweisungen, die eingeschlossen ist in { }.

B e i s p i e l :

In einem Programm soll die Division durch 0 verhindert werden. Hat der Divisor den Wert 0, so soll derDivisor auf den Wert 1 gesetzt werden. Die Division kann damit fehlerfrei ausgeführt werden.

if ( divisor == 0 ) divisor = 1;

ergebnis = zahl / divisor ; /* diese Zeile wird auf jeden Fall ausgeführt */

Da eine ganze Zahl in C auch als Boolean verwendet werden kann, sieht man in C Programmen auchhäufig folgende Programmzeilen.

if ( ! divisor ) divisor = 1; /* Falls not divisor */

ergebnis = zahl / divisor ;

Hat der Divisor den Wert 0, so kann dieser Wert auch als logischer Wert FALSCH interpretiert werden.Da die fallunterscheidung aber für den Fall WAHR den Divisor auf 1 setzen soll muß der Logische Wertdes Divisor negiert werden.

Häufige Fehlersituationen:

Fall 1:

if ( x == 1 ) ; /* ; bedeuted leere Anweisung */

{ printf( " ..... "); /* Dieser Block wird in jedem Fall ausgeführt da das if */

x = 0; /* durch die leere Anweisung ; abgeschlossenwurde */

}

Ein ; nach der Bedingung in der Fallunterscheidung bedeutet in C leere Anweisung also tue nichts. DieFallunterscheidung hat demnach keine Wirkung, da nichts passiert. Der darauf folgende Block wird aufjeden Fall ausgeführt, da er nicht mehr zur Fallunterscheidung gehört.

Korrektur:if ( x == 1 )

{ printf(...);

x=0;

}


Fall 2:

if ( x=1 ) printf(" Der Wert von x ist %i \n ",x);

x wird im Bedingungsausdruck nicht mit dem Vergleichsoperator == mit dem Wert 1 verglichen sondernmit dem Zuweisungsoperator = auf den Wert 1 gesetzt. Der Ausdruck x=1 ergibt immer den Wert 1, alsowahr, so daß in jedem Fall eine Ausgabe erzeugt wird.

Korrektur:if ( x == 1) printf(....);

V o l l s t ä n d i g e A l t e r n a t i v e

if ( <Ausdruck> ) <Anweisung_wahr> ;else <Anweisung_falsch> ;

Wenn die Berechnung des Ausdrucks den Wert wahr ( <> 0 ) ergibt, so wird Anweisung_wahrausgeführt, sonst wird Anweisung_falsch ausgeführt.

B e i s p i e l

Der Modulo-Operator angewendet auf negativen Zahlen ist in C nicht definiert. Sie wollen diese Situationin Ihrem Programm vermeiden. Die Lösung sieht dann so aus:

if ( i<0 )

{ i = -i;

rest = i % 8;

}

else rest = i % 8;

B e i s p i e l :

Im Falle einer Division durch 0 soll eine Fehlermeldung erscheinen. Der Sonderfall 0 dividiert durch 0 sollerkannt werden und liefert den Wert 1.

if ( nenner == 0 )

if ( zaehler == 0 ) division = 1;

else printf("Division ist undefiniert \n ");

else division = zaehler / nenner ;

Im obigen Programmausschnitt wurde nenner und zaehler in einer geschachtelten Fallunterscheidungausgewertet.Geschachtelte Fallunterscheidungen sind oft unübersichtlich. In diesem Fall bietet sich eine elegantereLösung mit logischen Operatoren an.

if ( ( nenner == 0 ) && ( zaehler == 0 ) ) division = 1;

else if ( i != 0 ) division = zaehler / nenner ;

else printf(" Division ist undefiniert \n");


Häufige Fehlersituationen:Der ; vor else wird vergessen

F a l l u n t e r s c h e i d u n g m i t m e h r e r e n A l t e r n a t i v e n

switch ( <Ausdruck> ){ case <Konstantenausdruck_1> : <Anweisung_1> ; case <Konstantenausdruck_2> : <Anweisung_2> ; .... default: <Anweisung_sonst> ;}

Wenn Ausdruck den Wert Konstantenausdruck_1 hat , so führe Anweisung_1 und alle folgendenAnweisungen aus,wenn Ausdruck den Wert Konstantenausdruck_2 hat, so führe Anwweisung_2 und alle folgendenAnweisungen aus .....Hat Ausdruck einen Wert, der nicht in den case-Fällen genannt wird, führe die Anweisung_sonst und allefolgenden Anweisungen aus.

B e i s p i e l :Sie haben in einer Variablen ErrorNummer vom Typ unsigned short eine Fehlernummer gespeichert. Fürjede mögliche Fehlernummer soll ein Fehlertext am Bildschirm ausgegeben werden. Sie realisieren ihrProgrammstück wie folgt:

switch ( error_nummer )

{ case 1: printf("Falsche Eingabe");

case 2: printf("Falscher Parameter");

case 3: printf("unbekanntes Kommando");

default: printf("Unbekannte Fehlernummer");

}Dieses Programmstück arbeitet fehlerhaft. Die Ursache liegt in der Logik der switch-Anweisung.Hat die Variable ErrorNummer den Wert 1, so wird der erste case-Fall ( case 1: ) ausgeführt. Es erfolgtdie Bildschirmausgabe Falsche Eingabe. Danach werden jedoch noch alle folgenden Anweisungen inder switch-Anweisung ausgeführt. Es erscheinen am Bildschirm daher nacheinander die AusgabenFalscher Parameter , unbekanntes Kommando Unbekannte Fehlernummer.Damit im Falle case 1 nur die Anweisungen ausgeführt werden, die zu dem case Fall gehören, muß dieswitch-Anweisung explizit mit einer break-Anweisung verlassen werden.Das korrekte Programmstück sieht dann wie folgt aus:

switch ( error_nummer )

{ case 1: printf("Falsche Eingabe");

break;

case 2: printf("Falscher Parameter");

break;

case 3: printf("unbekanntes Kommando");

break;

default: printf("Unbekannte Fehlernummer");

break;

}


Jede Fallunterscheidung mit mehreren Alternativen kann durch Schachtelung von if / else -Anweisungenrealisiert werden. So kann z.B. die folgende switch-Anweisung

unsigned char zeichen;

switch ( zeichen)

{ case 'A': erg = a + b ;

break;

case 'Z': erg = zeichen;

break;

default: erg = 0;

}

return erg;

kann somit über folgendes Programmstück realisiert werden :

if ( zeichen == ‘A’ ) erg = a + b ;

else if ( zeichen == ‘Z’ ) erg = zeichen;

else erg = 0;

return erg;

B e i s p i e l

Soll in mehreren unterschiedlichen Fällen gleiche Aktionen passieren kann man diese Fälle zu einerGruppe zusammenfassen und die switch-Anweisung kürzer gestalten. Diese Situation zeigt das folgendeBeispiel. Auf die Zeichen ‘.’, ‘,’, ‘;’ und ‘:’ soll die gleiche Ausgabe erfolgen. Dies kann man explizit injedem case-Fall ausführen lassen und dann die switch-Anweisung mit einem break verlassen.

switch ( zeichen )

{ case '.': printf("Das Zeichen ist ein Trennzeichen");

break;

case ',': printf("Das Zeichen ist ein Trennzeichen");

break;

case ';': printf("Das Zeichen ist ein Trennzeichen");

break;

case ':': printf("Das Zeichen ist ein Trennzeichen");

break;

case '+': printf("Das Zeichen ist eine Addition");

break;

default: printf(" Das zeichen ist weder Trennzeichen noch Addition");}

Man kann jedoch alle gleichen Fälle hintereinander zu einer Gruppe zusammenfassen und alle case-Fälle mit einer leeren Anweisung füllen. Erst im letzen Fall der Gruppe läßt man die Fehlermeldungausgeben. Da in den Fällen ., , und ; nur die leere Anweisung ausgeführt wird und kein break dasVerlassen der switch-Anweisung veranlaßt wird in allen Fällen die Aktionen des case-Falles ‘:’ausgeführt. danach wird mit break die switch-Anweisung verlassen.


switch ( zeichen )

{ case '.':

case ',':

case ';':

case ':': printf("Das Zeichen ist ein Trennzeichen");

break;

case '+': printf("Das Zeichen ist eine Addition");

break;

default: printf(" Das zeichen ist weder Trennzeichen noch Addition");

}

Häufige Fehlersituationen:

Ein case-Fall wird nicht explizit durch break verlassen


2 . 3 . 2 S c h l e i f e n

B e d i n g t e S c h l e i f e n

while ( <Ausdruck> ) <Anweisung> ;

Vor Eintritt in die Schleife wird <Ausdruck> berechnet. Solange der errechne Wert wahr ist ( <> 0 ) wirdAnweisung ausgeführt. Wird der Wert falsch ( 0 ) berechnet, wird die Schleife verlassen, d.h. dieAnweisung wird nicht mehr ausgeführt. Die while-Schleife wurde in der Vorlesung am Beispiel des Such-Algorithmus eingeführt und erläutert.

do <Anweisung> while ( <Ausdruck> ) ;

Die Anweisung wird ausgeführt und danach der Ausdruck berechnet. Solange der errechne Wert wahr ist( <> 0 ) wird Anweisung ausgeführt. Ist der <Ausdruck> falsch ( 0 ) wird die Schleife verlassen, d.h. dieAnweisung wird nicht mehr ausgeführt. In der do/while-Schleife wird die Anweisung mindestens einmalausgeführt, während in einer while-Schleife die Anweisung auch niemals ausgeführt werden muß.Das Beispiel des Suchalgorithmus aus der Vorlesung kann auch mit einer do /while Schleife realisiertwerden. Man muß jedoch beachten, das die Anweisung ausgeführt wird bevor die Bedingung geprüftwird. Beginnt man daher mit Index=0 als Startwert, so wird in der Schleife Index zuerst um 1 erhöht undsteht damit auf dem Wert 1. In der nachfolgenden Bedingung muß jedoch das erste Listenelement ( Indexhat den Wert 0 ), in diesem Fall also Liste[Index-1] verglichen werden. Eine while-Schleife kann also nichtohne Änderungen in eine do/while-Schleife umgewandelt werden.

B e i s p i e l : S u c h a l g o r i t h m u s m i t d o / w h i l e - S c h l e i f e

void suche( int Liste[], unsigned int N )


Index = 0;

do Index = Index + 1 while ( Liste[Index-1] != N && Liste[Index-1] != -1);

if ( Liste[Index]== N )

printf(“Die Zahl %i steht an Position %hu in der Liste\n“, N, Index-1 );

else printf(“Die Zahl %i kommt in der Liste nicht vor\n“,N );

}


Z ä h l s c h l e i f e

Die Zählschleife wird immer dann genommen, wenn die Anzahl der Schleifendurchläufe vorgegeben ist.Typischerweise also, wenn alle Werte einer Liste mit fester Anzahl von Werten abgearbeitet werden soll.

for ( Initalialausdruck ; Bedinungsausdruck ; Ausführungsausdruck ) <Anweisung> ;

Bedeutung:

Initialausdruck: Dieser Ausdruck wird genau einmal vor dem Eintritt in die Schleifeausgeführt. Dies entspricht dem Anfangswert der Schleife.

Bedingungsausdruck: Dieser Ausdruck entspricht der Bedingung einer while-Schleife. Vor derAusführung der Schleifenanweisung wird dieser Ausdruck ausgewertet.Ergibt der Ausdruck wahr wird die Schleife ausgeführt. Gibt der Ausdruckfalsch wird die Schleife verlassen.

Ausführungsausdruck: Wurde <Anweisung> ( also die Schleife ) ausgeführt, so wird danach derAusführungsausdruck ausgeführt. Durch diese Anweisung kann derSchleifenzähler um Schrittweite k erhöht oder erniedrigt werden.

B e i s p i e l :

Es soll eine Liste mit 10 Werten am Bildschirm ausgegeben werden. Man beginnt mit dem 1. Wert in derListe. Dieser Wert wird mit dem Index 0 angesprochen. In der Zählschleife wird der Index fortlaufend um1 erhöht bis alle 10 Werte ausgegeben sind.

int main(void)

{ int Liste[10]={2,4,6,8,10,12,14,16,18,20};

unsigned short index;

for ( index=0; index < 10; index = index +1 ) printf(“%i“,liste[index]);

return 0;

}


2 . 4 E I N - / A U S G A B E N Z U R K O M M U N I K A T I O N M I T D E MA N W E N D E R

Zur Ausgabe von Datenwerten auf dem Bildschirm und zum Einlesen von Datenwerten von der Tastaturstellt ANSI-C vordefinierte Funktionen zu Verfügung.

2 . 4 . 1 . F o r m a t i e r t e B i l d s c h i r m a u s g a b e

Zur Ausgabe von Datenwerten auf dem Bildschirm exisiert in ANSI-C die vordefinierte Funktion printf().

Benötigte Headerdatei: stdio.h

Prototyp: int printf(<formatstring>, Werteliste );

Der <formatstring> ist ein Text, der neben auszugebenden Zeichen Formatangaben enthält. EineFormatangabe wird durch das Zeichen % eingeleitet. printf gibt den Text in <formatsring> zeichenweiseam Bildschirm aus. An der Stelle im Text, an dem das Zeichen % auftritt wird der Wert einer Variableneingefügt. Dazu nimmt printf den nächsten Wert aus einer Liste von Werten, die dem <formatstring>folgen.

Ein auszugebende Wert muß in printf() an zwei Stellen bekannt gegeben werden:

1. Die Position im Ausgabestrom und der Datentyp des Wertes wir über eine Formatangabe ( %...)im <formatstring> angegeben.

2. Der auszugebende Wert wird in der Werteliste angegeben. Als Wert kann eine Variable, eineKonstante, ein Ausdruck oder ein Funktionsaufruf angegeben werden. Wird in printf mehr als einWert ausgegeben sind die Werte durch , zu trennen. Für jede Formatangabe im <formatstring>muß auch ein Wert in der Werteliste vorhanden sein.

B e i s p i e l :

int main(void){ int zahl=111;

unsigned short index=10;

/* Ausgabe eines Textes am Bildschirm ohne neue Zeile am Ende */

printf(“Dieser Text erscheint am Bildschirm. Der Ausgabezeiger steht amTextende“);

/* Positionierung auf eine neue Zeile */

printf(“\n“);

/* Es werden zwei Textzeilen ausgegeben. */

/* In der 1. Zeile wird der Wert von zahl im Format int ( %i ) eingefuegt. */

/* In der 2. Zeile wird der Wert von index im Format unsigned short ( %hu )

eingefügt */

printf(“ Der Wert von zahl : %i \n Der Wert von index : %hu \n“,zahl,index);

return 0;

}

Dieses Programm produziert folgende Ausgabe:


Dieser Text erscheint am Bildschirm. Der Ausgabezeiger steht am Textende Der Wert von zahl : 111 Der Wert von index : 10

Die Formatangabe im Formatstring hat folgende Form:

%<Modus-Flag><Länge><.Stellen><Typ>Kennung

<Modus-flag>, <Länge>,<,.Stellen> und <Typ> können weggelassen werden, die Angaben sind alsooptional. Das %Zeichen und die Kennung müssen angegeben werden.

Modus-Flag - Linksbündige Ausgabe ( normal ist Rechtsbündig )+ Ausgabe von + falls Zahl positivLeerzeichen Ausgabe eines Leerzeichens für positive Zahlen, - für

negative# Einfügen einer 0 als erstes Zeichen einer Oktalzahl,

einfügen von 0x bei Hexadezimalzahlen, Ausgabe einesDezimalpunktes in allen Fällen

Länge Minimale Anzahl von Zeichen in der Ausgabe. Falls * angegeben wird, so wird für Länge der Wert des nächsten Wertes in der Werteliste genommen

Stellen Ganze Zahl (i,d,u,o,x): Mindestzahl der ZiffernReelle Zahl (f,e,g): Stellen hinter dem KommaString: Maximalzahl der ZeichenFalls * angegeben wird, so wird für Stellen der Wert des nächsten Wertes in der

Werteliste genommen

Typ Zusätzliche Angabe zu Kennungh Wert ist vom Typ short int ( zusammen mit i,d,u,o,x)l Wert ist vom Typ long int ( zusammen mit i,d,u,o,x)L Wert ist vom typ long double ( zusammen mit f,e,g)

Kennung:

Kennung Datentyp Darstellungi,d signed int Dezimalzahl mit neg. Vorzeichen oder ohne

Vorzeichen falls positivu unsigned int Dezimalzahl ohne Vorzeicheno,x,X unsigned int Oktal oder Hexidezimalf double

( float-Werte werden in doublegewandelt )

Darstellung mit Dezimalpunkt

e,E double Darstellung mit Exponentg,G double Dezimalpunkt oder Exponent abhängig vom

Wertc char ein ASCII-Zeichens char[] Zeichenfolge ( string )

W e i t e r e B e i s p i e l e :

int zahl = 5;

char zeichen=‘A’;

float ergebnis=0.5;


printf(“Zahl : %i zeichen : %x Quadrat : %i\n“, zahl, zeichen, zahl*zahl);

Ausgabe --> Zahl : 5 zeichen : 41 Quadrat : 25

printf(“Zahl hat den Wert %6d\n“ zeichen ist %c“, zahl,zeichen);

Zahl hat den Wert 5Zeichen ist A

printf(“Der Fehler betraegt %f %%\n“,ergebnis);

Der Fehler betraegt 0.500000%

printf(“Der Fehler betraegt %3.1f %%\n“,ergebnis);

Der Fehler betraegt 0.5%

2 . 7 . 2 . E i n g a b e v o n T a s t a t u r

Zum Einlesen von Datenwerten, die der Anwender auf seiner Tastatur eingibt, existiert in ANSI-C dievordefinierte Funktion scanf().

Benötigte Headerdatei: stdio.hPrototyp: int scanf(<formatstring>, Liste von Variablenadressen );

Der Formatstring hat eine ähnliche Form wie in printf().

Alle Zeichen im Formatstring, die keine Formatangabe bedeuten, werden als Eingabezeichenerwartet, müssen also auch vom Anwender eingegeben werden.

Dies macht normalerweise keinen Sinn. Der Formatstring enthält daher normalerweise nurFormatangaben, die mit % beginnen.

Die Formatangabe im Formatstring hat folgende Form:

%<*><Länge><Typ>Kennung

* Eingegebener Wert wird zwar interpretiert aber keiner Variablen zugewiesen d.h. Wertwird ignoriert

Länge Maximalzahl der zu interpretierenden Zeichen im Eingabestrom

Typ Zusätzliche Angabe zu Kennung

h Wert ist short int ( zusammen mit i,d,u,o,x)l Wert ist long int ( zusammen mit i,d,u,o,x)

Wert ist double ( zsammen mit f,e,g)L Wert ist long double ( zusammen mit f,e,g)


Kennung:

Kennung Datentyp der Eingabe Erwartete ZeichenfolgeI,d signed int Dezimalzahl ( ganzzahlig ) mit oder ohne

Vorzeichenu unsigned int Dezimalzahl ( ganzzahlig ) ohne Vorzeicheno,x,X unsigned int Oktalzahl oder Hexidezimalzahl ( ohne Präfix

0x )f,e,E,g,G float Reelle Zahl mit oder ohne Vorzeichen, mit

oder ohne Dezinmalpunkt, mit oder ohneExponent

c char ein ASCII-Zeichens char[] Zeichenfolge ( string )

Es wird immer nur ein Wort eingelesen.Trennzeichen für Wörter sind Leerzeichen,Zeilenende oder Tabulator.

B e i s p i e l e

int i;

scanf( “ Value : %d“,&i);

Dieser Funktionsaufruf erwartet folgende Eingabe an der Tastatur:8 Überlese alle Leerzeichen. Dann lese die Zeichenfolge Value :

8 Einlesen einer Dezimalzahl und speichern in der Variablen i.

scanf(“%d“,&i);

Dieser Funktionsaufruf erwartet als Eingabe eine Dezimalzahl.


3 Elementare Algorithmen

3 . 1 S U C H E N V O N W E R T E N

In Kapitel 1.1.1, Seite 6-7 wurde ein einfacher Suchalgorithmus „Lineares Suchen“ entwickelt, der in einerungeordneten Liste von Zahlen nach einer gegebenen Zahl sucht. Bei diesem Algorithmus muß imungünstigsten Fall die gesamte Liste durchsucht werden.

Enthält die zu durchsuchende Liste die Zahlen in einer aufsteigend sortierten Reihenfolge, so kann dieSuche wesentlich effizienter erfolgen. Die Idee dabei ist die, man durchsucht nur den teil der Liste, in derdie Zahl vorkommen kann. Sucht man z.B. die Zahl 5 in einer Liste von positiven ganzen Zahlen so mußnur der linke Teil der Liste durchsucht werden, in dem die Zahlen 0 bis 5 vorkommen können.

Der Algorithmus kann wie folgt beschrieben werden:

Gegeben ist eine Liste mit positiven ganzen Zahlen. Die Zahlen in der Liste sind aufsteigend sortiert. DieListe enthält eine feste Anzahl von Werten.

B e i s p i e l :

G e g e b e n i s t e i n e L i s t e m i t 1 0 Z a h l e n . G e s u c h t w i r d d i e Z a h l 5

Man vergleicht das mittlere Element ( hier den Wert an der Position 5 ) mit der gesuchten Zahl

Liste[Mitte] =Liste[5]=10 GLEICH 5 ?

Entweder ist die Zahl gefunden oder man kann den Suchbereich einschränken auf den rechten Teil derListe, wenn die gesuchte Zahl größer ist als der Wert an der mittleren Position oder auf den linken Teilder Liste, wenn die gesuchte Zahl kleiner ist als der Wert an der mittleren Position. In unserem Beispielist 5 kleiner Liste[5], , also wird der Suchbereich auf die linke Hälfte also die Positionen 0 .. . Mitte-1eingegrenzt.

Man wiederholt nun die Suchstrategie mit dem mittleren Element der linken Listenhälfte, hier neue Mitte =Position 2. Ein Vergleich Liste[2] GLEICH 5 ? ergibt FALSCH. Jetzt wird die Liste wieder halbiert. 5 istgrößer als 2 also wird die rechte Listenhälfte von Position Mitte+1 ... 4 genommen. Diese Liste enthält nurnoch zwei Elemente. Bestimmt man die Mitte so erhält man die Position 3. Ein VergleichListe[3] GLEICH 5 ? ergibt einen positiven Treffer. Die gesuchte Zahl ist gefunden.

Hätte man anstelle der Zahl 5 die Zahl 7 gesucht, so wäre auch hier das Vergleichsergebnis negativausgefallen. Da 7 größer ist als Liste[Mitte] müßte die Suche auf die rechte Hälfte ausgedehnt werden.Die rechte Hälfte enthält jedoch nur noch 1 Element. Den Wert 9 an der Position 4. Ein Vergleich ergibtListe[4] ist ungleich 5. Ein erneutes teilen der Liste ist jetzt nicht mehr möglich. Die Sucher endete dahermit dem Ergebnis Die Zahl 7 kommt in der Liste nicht vor.

Dieser Algorithmus ist unter dem Namen BINÄRES SUCHEN bekannt.

1 2 5 9 10 12 13 20 28 401 2 3 4 5 6 7 8 9 10Index ( Position )


V e r f a h r e n z u r B e r e c h n u n g d e r m i t t l e r e n P o s i t i o n :

1 2 3 4 5 6 7 8 9 10 11

MinPos MaxPos

MitteMinPos MaxPos

Beim Start kann das mittlere Element bestimmt werden durchMaxPos MinPos

MinPos-

+2

---> 11 1

21

-+ = 5 + 1 = 6

Wird die Suche auf die rechte Hälfte reduziert so berechnet sich die Mitte wie folgt:MinPos=7; MaxPos=11;

MaxPos MinPosMinPos

-+

2 =

11 7

27

-+ = 2 + 7 = 9

Diese Berechnung kann wie folgt vereinfacht werden:

MaxPos MinPosMinPos

-+

2 =

MaxPos MinPos MinPos- +2

2 =

MaxPos MinPos+

2

F o r m a l e t e x t u e l l e D a r s t e l l u n g i n P s e u d o c o d e :

Algorithmus Binäres Suchen

Objekte: Liste Liste mit n positiven ganzen Zahlen. Die Liste ist aufsteigendsortiert.

Zahl Die gesuchte ZahlMinPos Linke Position in der zu durchsuchenden ListeMaxPos Rechte Position in der zu durchsuchenden ListeMitte Mittlere Position in der zu durchsuchenden Liste

Aktionen:

Initialisierung MinPos=1MaxPos=n;Mitte = (MinPos + MaxPos) dividiert durch 2

solange Wert an der mittleren Position ungleich Zahl und die Liste noch Elemente enthält tue wenn liste[mitte] < Zahl dann MinPos = Mitte +1 sonst MaxPos = Mitte - 1

wenn liste[mitte] = Zahl dann Ausgabe „ Die Zahl kommt an Position mitte in der Liste vor „sonst Ausgabe „ Die Zahl kommt in der Liste nicht vor „.


3 . 2 S O R T I E R E N V O N L I S T E N

Sortieren ist eine häufig vorkommende Problemstellung in der Informationstechnik. Aus diesem Grundwurden mehrere unterschiedliche Algorithmen entwickelt, von denen jeder seine Vorteile und Nachteilehat. Es gibt einfache Verfahren, die jedoch bei großen Listen viel Laufzeit benötigen. Andere sind zwarwesentlich schneller benötigen aber vielleicht mehr Speicherplatz oder sind komplexer. Manunterscheidet folgende Sortierverfahren.

8 Sortieren durch Einfügen Bekannte Verfahren sind: InsertienSort, Shellsort

8 Sortieren durch Auswählen

SelectionSort ( wurde in Übung 3 eingeführt )8 Sortieren durch Austauschen

Bubblesort ( wird in Übung 7 eingeführt ) , Shakersort

8 Sortieren durch Teilen und MischenQuicksort und Mergesort werden in Programmieren 2 behandelt

Eine detaillierte Beschreibung aller in diesem Skript nicht beschriebenen Sortierverfahren kannnachgelesen werden in:

8 Niklaus Wirth: Algorithmen und Datenstrukturen,

8 Ralf Güting: Datenstrukturen und Algorithmen,

8 R. Sedgewick: Algorithmen,

8 K. Mehlhorn: Datenstrukturen und effiziente Algorithmen, Sortieren und Suchen Band 1,

8 Knuth: The Art of Computer Programming, Vol 3, Sorting and Searching

Im folgenden Abschnitt sei InsertienSort als Sortierverfahren durch Einfügen beschrieben.

3 . 2 . 1 S o r t i e r e n m i t d e m V e r f a h r e n I n s e r t i e n S o r t

Dieses Sortierverfahren wurde von einem alten Kartenspiel abgeleitet. Man hat eine Reihe vonungeordneten Karten und will diese Karten dem Wert entsprechend sortieren.

Beispiel:44 12 55 3

Man beginnt mit der 2. Karte. Man nimmt diese Karte aus der Reihe. Es bleibt eine linke Seite und einerechte Seite übrig. Ziel ist nun, die aktuell genommene Karte x in der linken Seite an die richtige Positioneinzufügen. Die rechte Seite bleibt unverändert.

Im Beispiel nimmt man die Karte mit dem Wert 12.

44

12

55 3

RechteSeite

LinkeSeite

Um diese Karte an die richtige Position zu bringen, schiebt man alle Karten,deren Wert größer ist als 12, um eine Position nach rechts.Hat man alle größeren Karten verschoben bleibt eine Lücke, in die man diegenommene Karte x einfügen kann.

Die Karte mit dem Wert 12 steht in unserem Beispiel danach an der 1. Position

Dieses Vorgehen wiederholt man für alle Karten, die auf der rechten Kartenseite liegen. Die nächstegewählte Karte ist also die Karte an der Position 2 +1 = 3. Diese Karte hat den Wert 55.

44

12

55 3

4412 55 3


Man nimmt die Karte aus der Reihe. Alle Karten auf der linken Seite habeneinen kleineren Wert, werden daher nicht verschoben.

Die Karte wird wieder an der selben Position eingefügt.

Die nächste Karte hat den Wert 3.

Man nimmt diese Karte aus der Reihe. Alle Karten links davon haben einengrößeren Wert und werden daher um eine Position nach rechts geschoben.

Als Lücke bleibt die 1. Position. An diese Stelle wird die genommene Karte eingefügt.

Dies war die letzte Karte in der Reihe. Die Reihe ist damit sortiert.

Der beschriebene Algorithmus kann durch folgendes C-Programm realisiert werden:

void InsertionSort(int liste [], int laenge ){ int KarteX; /* Aktuell genommene Karte */ int i,links; /* Positionen in der Liste */ /*----------------------------------------*/ /* Starte mit der zweiten Karte von links */ /* und wiederhole für alle rechten Karten */ /*----------------------------------------*/ for(i = 1; i<laenge; i=i+1 ) { KarteX=liste[i]; links=i-1; /*-----------------------------------------------------------------------*/ /* Verschiebe alle linken Karten, die groesser sind als KarteX nach rechts */ /*-----------------------------------------------------------------------*/ while ( (liste[links] > KarteX) && (links >= 0) ) { liste[links+1]=liste[links]; links=links - 1; } /*---------------------------------------------------*/ /* Fuege die KarteX an die verbleibende Position ein */ /*---------------------------------------------------*/ liste[links+1]=KarteX; }}

4412

55

3

Alle Karten linkshaben einenkleineren Wert

4412 55 3

4412 55

3

4412 55

3

4412 553


3 . 3 S O R T I E R E N U N D S U C H E N V O N S T R I N G S

Sortier- und Suchalgorithmen werden häufig benutzt um Namen also Zeichenketten zu sortieren und zusuchen.Deshalb soll an dieser Stelle die Behandlung von strings in der Programmiersprache C eingeführtwerden.Eine Zeichenkette ( string ) ist eine Folge von Zeichen. In der Programmiersprache C werden dieseZeichen in einem array ( Liste ) abgelegt. Ein string ist in C also ein array, in dem Zeichen gespeichertsind , und ist daher wie folgt zu definieren:

char string[256];

string ist eine Variable, in der 256 Werte abgelegt werden. Da eine Zeichenkette im Normalfall einevariable Anzahl von Zeichen enthält, wird in dem array das Ende der gültigen Zeichenfolge durch einSonderzeichen, das ASCII-Zeichen NUL ( Dezimalwert 0, Zeichenkonstante ‘\0’ ) gekennzeichnet. DieVariable string enthält somit maximal 255 gültige Zeichen eines string und das Endezeichen ‘\0’.

B e i s p i e l :

char name[12];0 11

K e l l e r 0 - - - - -

Durch Definition von name wird eine Array mit 12 Komponenten angelegt. Dieses Array enthält nach derDefinition ungültige Werte. Das Array kann mit dem Namen „Keller“ gefüllt werden durch einekomponentenweise Zuweisung der einzelnen Zeichen der Zeichenkette an die array-Komponenten:

name[0]=‘K’; name[1]=‘e’; name[2]=‘l’; name[3]=‘l’; name[4]=‘e’; name[5]=‘r’;name[6]=‘\0’;

Man kann das Array auch direkt bei der Definition analog einem array, das Zahlenwerten enthält,initialisieren:

char name[12]={‘K’,‘e’,’l’,’l’,’e’,’r’};

Der Rest des array wird automatisch mit 0 aufgefüllt. Damit wird das Endezeichen ‘\0’ automatisch ansEnde der Zeichenkette geschrieben.

Im Falle von strings ermöglicht C auch eine vereinfachte Schreibweise bei der Initialisierung:

char name[12]=“Keller“;

Die rechte Seite “Keller“ ist eine string-Konstante.

Möchte man die Größe des Array an die Länge des Namens anpassen um möglichst wenig Speicherplatzzu belegen, so ist folgende Initialisierung möglich:

char name[]=“Keller“;

Wird bei der Definition keine Anzahl von array-Komponenten angegeben, so berechnet sich der Compilerdie Anzahl selbst aus der Anzahl der angegebenen Initialwerte. In diesem Fall wird ein Array mit genau 7Komponenten ( 6 Zeichen für Keller + ‘\0’ ) erzeugt.Will man im Programm den Inhalt des Array ändern, im vorliegenden Beispiel also einen anderen Namenspeichern, so kann dies nur komponentenweise geschehen.

Beim Einlesen und bei der Ausgabe kann jedoch ein Wort oder eine Zeile komplett eingelesen bzw.ausgegeben werden:


Mit scanf kann ein array mit einem eingelesenen Wort beschrieben werden. Hier ist zu beachten, daßbeim Einlesen von strings der &-Operator entfällt. Ein Wort in der Eingabe ist getrennt durch Leerzeichen,Tabulator oder Neue Zeile.

scanf(„%s“, name); /* Liest ein Wort von der Tastatur ein */

Zum Einlesen einer kompletten Zeile inklusive Leerzeichen und Tabulatoren kann die Funktion gets(name) aus stdio benutzt werden.

Zur Ausgabe einer beliebigen Zeichenkette kann die Funktion printf() oder puts() verwendet werden.

printf(„%s“, name );

Während printf() an die Zeichenkette keine neue Zeile anfügt wird durch puts automatisch eine neue Zeileam Ende der Zeichenkette ausgegeben.

Da string kein eigener Datentyp ist, sondern als array von Zeichen realisiert wird, sind folgendeAusdrücke in C fehlerhaft:

string=„ Ein neuer text“; /* fehlerhafte Zuweisungen */string=name;

Die Zuweisung einer Stringkonstanten an eine Variable ist nur bei der Initialisierung möglich. EineÄnderung von string während der Programmlaufzeit, kann nur komponentenweise erfolgen.

string[0]=‘E’; string[1]=‘i’ ; ........ string[ ]=‘t’; string[ ]=‘\0’;

Eine char array kann auch nicht als Ganzes zugewiesen werden.

Will man die Zeichenfolge im array name dem array string zuweisen, so kann auch dies nurkomponentenweise geschehen.

Da Zeichenketten in einem Programm häufig benötigt werden, stellt C viele Standardfunktionen ( Bibliothek: string , Headerdatei string.h ) zur Bearbeitung von Zeichenketten zu Verfügung. Diewichtigsten davon werden an dieser Stelle aufgeführt. Weitere Funktionen können den Handbüchern zuANSI C entnommen werden.

Bestimmung der Länge einer Zeichenkette

Prototyp: size_t strlen( string );

Beispiel: strlen(„Keller“) liefert den Wert 6.

Kopieren einer Zeichenkette in ein char array

Prototyp: strcpy(ziel,string);

ziel muß ein char array sein.String kann entweder ein char array oder eine string-Konstante sein.

Beispiel: strcpy(string,name); strcpy(string,“Hulin“);

Anfügen einer Zeichekette string2 an eine Zeichenkette string1

Prototyp: strcat( string1, string2)

string1 muß ein char array sein. string2 kann entweder ein char array oder eine string-Konstante sein.


Vergleichen zweier Zeichenketten

Prototyp: int strcmp( string1, string2 )

Der Vergleich der Strings beginnt mit dem ersten Zeichen in jedem String und wird zeichenweisefortgesetzt, solange sich die Zeichen unterscheiden, oder das Ende des Strings erreicht wird.

Rückgabewert: Zahl kleiner 0 wenn string1 kleiner string2 0 wenn string1 gleich string2

Zahl größer 0 wenn string1 größer string2

3 . 3 . 1 S o r t i e r e n e i n e r L i s t e m i t N a m e n

Sie sollen mit einem bekannten Sortieralgorithmus eine Liste mit 10 Namen sortieren. JederName kann maximal 16 Zeichen lang sein.

Ein Name ist eine Zeichenkette und wird daher in einem Array mit 16 + 1 Element gespeichert.

K e l l e r ‘\0’ 0 0 0 0 0 0 0 0 0 00 15 16

Eine Liste von 10 Namen ist daher ein Array, dessen Komponenten selbst wieder ein array ( in diesemFall ein string ) sind.

#define ANZAHLNAMEN 10#define ANZAHLZEICHEN 16

char liste[ ANZAHLNAMEN ][ ANZAHLZEICHEN + 1 ]

B e i s p i e l f ü r e i n e L i s t e m i t 1 0 N a m e n

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16Zeile 0 K e l l e r ‘\0’ 0 0 0 0 0 0 0 0 0 0 liste[0] --1. NameZeile 1 H u l i N ‘\0’ 0 0 0 0 0 0 0 0 0 0 0 liste[1] -- 2. NameZeile 2 G a m p p ‘\0’ 0 0 0 0 0 0 0 0 0 0 0

Zeile 3 U s a d e l ‘\0’ 0 0 0 0 0 0 0 0 0 0

Zeile 4 B r u e m m e r ‘\0’ 0 0 0 0 0 0 0 0

Zeile 5 E r t e l ‘\0’ 0 0 0 0 0 0 0 0 0 0 0

Zeile 6 K o c h ‘\0’ 0 0 0 0 0 0 0 0 0 0 0 0

Zeile 7 S c h i l l i n g ‘\0’ 0 0 0 0 0 0 0

Zeile 8 A d e r m a n n ‘\0’ 0 0 0 0 0 0 0 0

Zeile 9 K r a g l e r ‘\0’ 0 0 0 0 0 0 0 0 0 liste[9]

Mit der Anweisung printf(“%i-ter Name = %s\n“, i, liste[i]);

kann ein Name aus der Liste am Bildschirm ausgedruckt werden.

Möchte man einen Namen verändern, so kann man hierzu die ANSI-Funktion strcpy aus string.hverwenden.

strcpy(liste[0], “Maier“); /* 1. Name in der Liste wird Maier */


4 Unterprogrammtechnik

Unterprogramme dienen hauptsächlich dazu, größere Programme in kleinere Untereinheiten zu zerlegen.So kann z.B. das Programm aus Übung 6 in wie folgt strukturiert werden:

Hauptprogramm zu Übung 6

BeginnEinlesen einer Liste von 20 Zahlen.Sortieren der Liste.Einlesen einer Zahl, die in der Liste gesucht werden soll.Binäre Suche .

Ende

Einlesen, Sortieren und BinäreSuche sind Untereinheiten, die als Unterprogramme realisiert werdenkönnen.

Das Struktogramm des Programms enthält 4 Makroblöcke. 3 Makroblöcke sind selbst definierteUnterprogramme. Jedes Unterprogramm wird durch ein eigenes Struktogramm beschrieben.

Der Makroblock EINLESEN ZAHL wird durch ein in C vordefiniertes Unterprogramm ( ANSI-Funktionscanf() ) realisiert. Dieser Makroblock wird daher nicht durch ein Struktogramm erklärt. Er wird alsgegeben hingenommen.

Hauptprogramm

EinlesenListe

Sortieren

Einlesen Zahl

BinaereSuche

Beschreibung des Makroblockes Sortieren

Sortieren

Index:=1

Index:=Index + 1

solange Liste[Index] ungleich N und Liste[Index] ungleich -1

Die Zahl kommt an der Position Index in der Liste vor

Die Zahl kommt in der Liste nicht vor

wahr falsch

wenn Liste[Index] = N


Ein Unterprogramm wird genau einmal definiert und liegt auch nur einmal im Speicher. Bei der Definitioneines Unterprogramms wird nur der Algorithmus beschrieben und im Speicher abgelegt. DasUnterprogramm wird jedoch nicht ausgeführt. Ein Unterprogramm wird erst ausgeführt, wenn imHauptprogramm das Unterprogramm verwendet wird ( Unterprogrammaufruf ). Durch denUnterprogrammaufruf werden alle Programmanweisungen des Unterprogramms ausgeführt und , fallsdas Unterprogramm eine Funktion ist, der Ergebniswert berechnet und an das Hauptprogrammübergeben.

Ein Unterprogramm kann mehrfach im Hauptprogramm verwendet werden. Jedes Unterprogramm kannselbst wieder Unterprogramme aufrufen. Ein Unterprogramm kann sowohl vom Hauptprogramm imgleichen Modul als auch von Unterprogrammen im gleichen oder in externen Modulen verwendet werden( Modulares Programmieren ). Beim Unterprogrammaufruf wird das Hauptprogramm verlassen und indas Unterprogramm verzweigt. Nach Ausführung des Unterprogramms wird wieder ins Hauptprogrammzurückgekehrt ( siehe Bild Kapitel 1, Seite... ).

4 . 1 P R O Z E D U R E N U N D F U N K T I O N E N

Die Programmiersprache C unterscheidet nicht in Prozeduren und Funktionen. In C sind alleUnterprogramme Funktionen. Eine Funktion liefert genau einen Wert als Ergebnis. Beispiel für eineFunktion ist die Berechnung des Sinus. Definitionsbereich und Wertebereich dieser mathematischenFunktion sind die rellen Zahlen. Die Funktion wird in C folgendermaßen definiert:

Prototyp der C Funktion:

double sinus( double x );

x ist Eingabewert in die Funktion.

Durch Aufruf der Funktion wird der Ergebniswert also sinus(x) berechnet und kann durch eine Zuweisungan eine Programmvariable im Programm verfügbar gemacht werden.

double y ;y = sinus(90);

Fehlt die Zuweisung, wird zwar der Wert in der Funktion berechnet, im aufrufenden Programm jedochnicht gespeichert und damit verworfen.

Eine Prozedur kann in C dadurch realisiert werden, daß man als Ergebnis einer Funktion den Datentypvoid angibt. void besagt in diesem Fall, daß die Funktion keinen Ergbnistyp besitzt, also eine Prozedurist.

Beispiel:

ProzedurAusgabeStern

Das Unterprogramm AusgabeStern produziertfolgende Ausgabe auf dem Bildschirm:

* * * * * * * * *

Das Unterprogramm ist eine reine Zusammenfassung von Programmanweisungen, ohne das ein Wertberechnet wird. Das Unterprogramm ist damit eine Prozedur. Das Unterprogramm wird in C wie folgtdefiniert:

Prototyp der Funktion: void AusgabeStern(void);

Funktionsinusx y

Eingabewert Ergebniswert

Programmieren 1 Prof. Dr.-Ing. Silvia Keller Studiengang Angewandte Info rmatik Ausgabe: 24.09.00 Seite 75 von 108

Der Unterprogrammaufruf kann nicht in einer Zuweisung verwendet werden, da kein Wert berechnet wird.Folgende Programmanweisung ist daher fehlerhaft:

erg = AusgabeStern(); /* fehlerhafter Unterprogrammaufruf */

AusgabeStern(); /* Korrekter Unterprogrammaufruf */

4 . 2 P A R A M E T E R

Um Werte aus dem Hauptprogramm ans Unterprogramm übergeben zu können, kann man bei derDefinition einer Funktion eine beliebige Anzahl von formalen Parametern festlegen. Ein formalerParameter verlangt die Angabe eines Parameternamens und eines Datentyps. Dar Name wird imUnterprogrammrumpf benötigt , um die einzelnen Eingabewerte benutzen zu können.

Beim Aufruf der Funktion werden Werte vom Hauptprogrammans Unterprogramm übergeben ( aktuellen Parameter ).

Die Parameter eines Unterprogramms kann man klassifiziereninû Import-Parameter,û Export-Parameter undû Import/Export-Parameter.


8 Bei der Parameterübergabe wird vomParameter eine Kopie erzeugt. DasUnterprogramm erhält nur die Kopie desaktuellen Wertes einer Variablen.

8 Wird im Unterprogramm der Parameterverändert, so wird nur die Kopie imUnterprogramm verändert. Nachverlassen des Unterprogramms ist derOriginalwert im Hauptprogrammunverändert vorhanden.

Unterprogrammtechnik - Klassifikation der Parameter

call by value call by reference

UP UPUP

Variable

Kopie

Variable Variable

Hauptprogramm HauptprogrammHauptprogramm

8 Diese Parameter werden als Variablen an dasUnterprogramm übergeben. Damit hat dasUnterprogramm Zugriff auf das Original imHauptprogramm und kann dieses auch verändern.

8 Bei export-Parametern wird die Variable durch dasUnterprogramm verändert ohne den Wert vorher zulesen.

8 Beim Import-/Exportparameter wird die Variablesowohl gelesen als auch geschrieben.

Import-Parameter Import-/Export-ParameterExport-Parameter

Formale Parameter

Unterprogrammverwendet a und b

a b


4 . 3 D E F I N I T I O N V O N F U N K T I O N E N I N C

<Ergebnistyp> <Funktionsname> ( <Formale Parameter> ) Funktionskopf{ /* Hier beginnt der Rumpf der Funktion */ Funktionsrumpf

/* Hier sollten alle lokale Variablen definiert werden */

/* Im Rumpf der Funktion muß mindestens eine return - Anweisung vorkommen */ /* Mit return wird das Ergebnis ans Hauptprogramm übergeben und das Unterprogramm

verlassen */

} /* Hier endet der Rumpf der Funktion */

Parameter werden in C grundsätzlich nach der Methode call by value übergeben, d. h. C kennt nurImport-Parameter.

B E I S P I E L :

Im Übungsblatt 2 wurde zur Umrechnung einer Dezimalzahl in eine Dualzahl eine Operation benötigt, diezwei Ergebnisse liefert. Eine ganzzahlige Division von zwei positiven ganzen Zahlen mit Berechnung desRest.

Hierfür kann man ein Funktion schreiben, die beide Operation ( ganzzahlige Division und Berechnungdes Rests ) zu einer Anweisung DivisionMitRest zusammenfaßt.

In C kann eine Funktion nur einen Wert als Ergebnisliefern, also entweder den Quotienten oder den Rest.Der zweite Wert muß daher als Export-Parameterrealisiert werden.

C kennt jedoch nur Import-Parameter.

Wie kann dieses Problem gelöst werden ?

Lösungsvorschlag:8 Verwendung globaler Parameter

Globale Variablen sind gültig in allen Programmobjekten und damit auch dem Unterprogrammzugänglich. Ein Unterprogramm kann damit Globale variablen verändern, ohne das diese als Parametererscheinen. Das Unterprogramm verändert also Variabeln, die außerhalb des Unterprogramms liegen.Dies nennt man Seiteneffekt. Seiteneffekt des Unterprogramms ist die Veränderung von Variablen, die inaus der Umgebung dem Unterprogramm zugänglich sind.

FunktionDivisionMitRest

zaehler Quotient

nenner Rest


zaehlerQuotientnenner

Rest

Import-Parameter

Export-Parameter


Das Unterprogramm kann damit folgendermaßen definiert werden:

long quotient=0, rest=0; /* Definition globaler Variabeln */

int main(void){ quotient = DivisionMitRest(4,3); printf(„ %li dividurt durch %li ergibt %li mit Rest li\n“,zaehler,nenner,quotient,rest);}long DivisionMitRest(long zaehler, long nenner){ rest = zaehler % nenner ; return zaehler / nenner ;}

S o n d e r f a l l : Ü b e r g a b e v o n e i n d i m e n s i o n a l e n L i s t e a n e i n e C - F u n k t i o n

Gegeben ist folgendes Problem:

Es ist ein Programm zu schreiben, welches eine Liste mit 2000 ganzen Zahlen definiert. Es soll einepositive ganze Zahl eingelesen werden. Diese Zahl soll in der Liste gesucht werden. Zum Suchen soll einUnterprogramm verwendet werden. Dieses Unterprogramm benötigt zwei Import-Parameter, die Liste mit2000 Zahlen und die zu suchende Zahl.

In diesem Fall müßten alle 2000 Werte der Liste einzeln als Kopie an das Unterprogramm übergebenwerden. Dies ist nicht sinnvoll. Deshalb übergibt C im Falle einer Liste den Variablennamen an dasUnterprogramm. Dies entspricht jedoch der Übergabemethode call by reference. Im Falle voneindimensionalen Listen macht C hier eine Ausnahme mit folgenden Nachteilen:

8 Es wird der Variablennname an das Unterprogramm übergeben. Die größer der Liste wirdnicht übergeben. Im Unterprogramm ist damit die Listengröße nicht mehr bekannt.

8 Alle Listenwerte stehen dem Unterprogramm im Original zu Verfügung. Eine Änderung vonListenwerten im Unterprogramm verändert damit die Originalliste. Ein Schutz vorÜberschreibung der Variable ist damit nicht mehr gegeben.

B e i s p i e l :

void suche( unsigned int n ); /* Prototyp der Funktion */

/*****************/

/* Hauptprogramm */

/*****************/

int main(void)

{ int Liste[N]={ 2,4,5,8,9,55,21,0,7,20,12,45,11,13,78, 45,23,78,90,189, -1 );

unsigned int zahl;


zaehlerQuotientnenner

Import-Parameter


printf(„Bitte gib die zu suchende Zahl ein: „);

scanf(„%u“,&zahl);

suche(Liste,N); /* Aufrufen der Funktion suche mit aktuellen Parametern */

return 0;

}

/*********************************************//* Definition einer Prozedur suchen() *//* Formale Parameter: Eine Liste Zahlen *//* eine zu suchende Zahl n *//*********************************************/

void suche( int Liste[], unsigned int n )


Index=0;

while ( Liste[Index] != n && Liste[Index] != -1 ) Index=Index+1;

if ( Liste[Index]== n )

printf(“Die Zahl %u steht an Position %hu in der Liste\n“, n, Index );

else printf(“Die Zahl %u kommt in der Liste nicht vor\n“,n );

}


4 . 4 M A K R O S

In Kapitel 4.1 wurde die Unterprogrammtechnik als Mittel zur Strukturierung und Vereinfachung vonProgrammen eingeführt. Eine Alternative zu Unterprogrammen, die aus nur wenigen Programmzeilenbestehen, sind Makros.

Ein Makro ist ähnlich einem Unterprogramm ein Programmteil, der unter einem Namen, demMakronamen, zusammengefaßt wird, und über den Namen im Programm verwendet werden kann. Wieein Unterprogramm, kann ein Makro auch formale Parameter erhalten, die bei der Verwendung durchaktuelle Werte ersetzt werden.

Bei der Verwendung eines Programmteils als Makro oder als Unterprogramm gibt es jedochUnterschiede, die im einen oder anderen Fall als Vorteil oder als Nachteil zu sehen sind.

Makros werden vor der Übersetzung eines C Programms definiert und ersetzt.Der C-Compiler besteht aus zwei Phasen ( siehe Kapitel 2, Seite 25 ).

In der ersten Phase wird vom Präprozessor ein Quelltext, der C-Sprachelemente und spezielleAnweisungen an den Präprozessor enthält, in einen Quelltext überführt, in dem nur noch gültige C-Sprachelemente vorkommen.

In der zweiten Phase wird dann der C-Quelltext vom Compiler in ein Programmobjekt übersetzt.

Der Präprozessor ist ein reines Textverarbeitungsprogramm, welches C-Sprachelemente unverändertverändert kopiert, aber Textelemente, die mit dem Sonderzeichen # beginnen, als Anweisungeninterpretiert, um Texte einzufügen oder zu verändern.

Eine Anweisung des Präprozessors ist die Anweisung #include , mit der man Textdateien an dieangegebene Position einfügen kann. Eine weitere Anweisung ist #define. Mit define kann man ein Makrodefinieren.

Ein Makro besteht aus einem Makronamen und einem Programmtext. Nach der Definition wird derMakroname als Platzhalter für den Programmtext verwendet d.h. taucht der Makroname in einemProgramm auf, wird der Makroname durch den Programmtext ersetzt. Diese Textersetzung übernimmtder Präprozessor und wird Makroexpansion genannt.



Makros

Programmtext

Makro-definition

Makro-Expansion

MakronameMakrorumpf

Programmtext

Programmtext

Quelltext vor Präprozessor

Quelltext nach Präprozessor

a=a*b;Makronameb=a++ *c;b++;Makronamereturn b;

a=a*b;

b=a++ *c;b++;

return b;

ErsetzeMakroname

durchProgrammtext

• Die Definition eines Makros muß vorder ersten Expansion liegen

• Die Definition eines Makros geschiehtdurch die Präprozessoranweisung#define

B e i s p i e l :

/* Definition eines Makros ohne Parameter */

#define NEWLINE printf(„\n“);

/* Makroexpansion */

printf(“%i“,i);NEWLINE /* Der Makroname NEWLINE wird an dieser Stelle durch

den Programmtext printf(„\n“); ersetzt */b++;

Weitere Beispiele für Makros:

Makrodefinition Makroverwendung Programmtext nach derMakroexpansion

#define BUF_LEN 512 int puffer[BUF_LEN]; int puffer[512]

#define UEBERSCHRIFT printf(„ -- Tab ---“);\ printf(„ ----------“);\ NEWLINE

UEBERSCHRIFT printf(„ -- Tab ---“);printf(„ ----------“);printf(„\n“);

#define ADD( a,b) ( (a) + (b) ) erg=ADD(4*5,3); erg=( (4*5) + (3) );

Die Vereinbarung von Konstanten mit #define ist also eine Makrodefinition. Der Makroname ist indiesem Fall der symbolische Name für einen konstanten Wert. Der Konstantenname wird im Programmdurch den vereinbarten Wert ersetzt. Muß ein konstanter Wert, der mehrmals im Programm benötigt wirdgeändert werden, kann dies an genau einer Stelle erfolgen. Alle Vorkommen werden dann automatischdurch den Präprozessor geändert.

Ein Makro kann auch mehr als eine Programmzeile umfassen. Eine Folgezeile des Makrorumpfes wirddurch \ angezeigt. Das Makro UEBERSCHRIFT besteht im obigen Beispiel aus drei Programmzeilen.Bei der Makroexpansion wird der \ weggelassen.


Makros können geschachtelt werden. Im Makro UEBERSCHRIFT wurde das vorher definierte MakroNEWLINE verwendet.

Ein Makro kann auch mit Parametern definiert werden.Das Makro ADD im obigen Beispiel hat z.B. die beiden Parameter a und b. a und b wird im Makrorumpfdurch die entsprechenden aktuellen Parameter bei der Makroverwendung ersetzt.

Aber Vorsicht bei der Definition von Makros mit Parametern. Die Parameter eines Makros werden in ( )angegeben. Die öffnende Klammer ( muß direkt dem Makroname folgen. Steht ein Leerzeichen zwischenMakroname und ( wird das Makro als parameterlos angenommen und die Parameterliste einschließlichder () wird als Programmtext des Makrorumpfes interpretiert.

B e i s p i e l :

#define ADD (a,b) a + b

erg = ADD(2,4); /* wird expandiert zu erg=(a,b) a + b(2,4); */

Die Klammern im Programmteil des Makro ADD werden benötigt, damit keine ungewollten Fehlerpassieren. Hätte man das Makro folgendermaßen definiert

#define ADD(a,b) a+b , so würde die folgende Makroexpansion zu einem Fehler führen:

erg=5*ADD(3,4); wird ersetzt durch erg=5*3+4; Dies ist ungleich erg=5*(3+4);


4 . 4 . 1 V e r g l e i c h U n t e r p r o g r a m m t e c h n i k m i t M a k r o s


Makros

( (a) + (b) )

Makro Unter-programm

ADD(a,b)

ADD(5,2);ADD( 4, 6);ADD ( 2, 7);

( (5)+(2) );( (4)+(6) );( (2)+(7) );

{ return a+b; }int add(int a, int b)

add(5,2);add( 4, 6);add ( 2, 7);

Hole ParameteraHole Parameterba+b;

Unterprogramm add

wird ersetztdurch

W a s g e s c h i e h t b e i e i n e m U n t e r p r o g r a m m ?

Ein Unterprogramm wird zu einem eigenständigen Programmobjekt übersetzt. Dieses Programmobjektwird nur einmal in den Speicher geladen, auch wenn das Unterprogramm mehrfach verwendet wird.

Bei einem Unterprogrammaufruf werden die aktuellen Parameterwerte an eine bestimmte Stelle in denSpeicher kopiert. Dann wird das Hauptprogramm verlassen und in das Unterprogramm verzweigt. DasUnterprogramm holt sich die Parameterwerte aus dem Speicher ( der Ort ist vorgegeben ), arbeitet dieProgrammanweisungen ab, bis das Ende des Unterprogramms erreicht ist. Letzte Anweisung einesUnterprogramm ist ein Rücksprung zum Hauptprogramm, an die Programmanweisung, die demUnterprogrammaufruf folgt.Das Kopieren der Parameterwerte und das Verzweigen ins und vom Unterprogramm benötigt zusätzlicheRechenzeit.

W a s g e s c h i e h t b e i e i n e m M a k r o ?

Das Makro wird nicht als eigenständiges Programmobjekt übersetzt. Ein Makro entspricht nur einerTextersetzung. Bei jedem Makroaufruf wird der Programmtext in das Programm eingefügt und erstdanach wird das Programm übersetzt.

Z u s a m m e n f a s s u n g :

Ein Makro ist schneller, da keine Parameterübergabe und keine Programmverzweigung erfolgt. Beimehrfacher Verwendung eines Makros wird jedoch mehr Speicherplatz benötigt, da der Makrorumpfmehrmals im Speicher steht.

Ein weiterer Unterschied besteht darin, daß bei einem Unterprogramm der Compiler die Anzahl und denDatentyp der Parameter prüft. Bei einem Makro wird nur die Anzahl überprüft, eine Typprüfung entfällt.


B e i s p i e l :

Das Makro ADD kann sowohl mit ganzen Zahlen als auch mit reellen Zahlen korrekt verwendet werden.

erg=ADD(2.5,1.5); wird ersetzt durch erg=( (2.5) + (1.5 ) );

Bei einem Unterprogramm muß Typ des Ergebnisses und Typ der Parameter angegeben werden.

int add( int a, int b) { return a+b; }

Der Aufruf des Unterprogramms führt bei reellen Zahlen zu einem Fehler:

erg=add(2.5, 1.5 ); ergibt als Ergebnis nicht 4.0 sondern die ganze Zahl 3.

U m d e f i n i e r e n e i n e s v o r h a n d e n M a k r o s

Ein einmal definiertes Makro kann mit der Präprozessoranweisung

#undef <Makroname>

als ungültig gekennzeichnet und danach neu vereinbart werden.

B e i s p i e l

#define NEWLINE printf(„\n“);NEWLINE /* Erzeugt eine Leerzeile */#undef NEWLINE#define NEWLINE printf(„\n\n\n“);NEWLINE /* Erzeugt drei Leerzeilen */


E E R G Ä N Z U N G E N Z U O P E R A T O R E N U N D A U S D R Ü C K E N

E . 1 B e s o n d e r e O p e r a t o r e n

Neben den eingeführten arithmetischen Operatoren stellt C spezielle Operatoren zu Verfügung, dieeinerseits Schreibarbeit einsparen andererseit aber auch zur Optimierung des Programms dienen. Imfolgenden werden diese Operatoren beschrieben:

K O M B I N A T I O N V O N A R I T H M . O P E R A T O R E N M I T D E R Z U W E I S U N G

AbkürzendeSchreibweise

NormaleSchreibweise

a += b a = a + ba -= b a = a - ba *= b a = a * ba /= b a = a / ba %= b a = a % b

Mit der abkürzenden Schreibweise sollte jedoch möglichst Vorsichtig umgegangen werden, da sehrhäufig Fehler passieren.

So bedeutet die abkürzende Schreibweise links *= 3 + 4;in normaler Schreibweise links = links * ( 3 + 4 ); und nicht links = links * 3 + 4;

A D D I T I O N U N D S U B T R A K T I O N V O N 1

Der Sonderfall a = a + 1 wird in der Hardware durch spezielle schnelle Schaltnetze, dasInkrement ( a++ ) realisiert.

Ebenso wird der Sonderfall a = a - 1 durch das Dekrement ( a - - ) realisiert.

Inkrement und Dekrement sind schneller in der Programmausführung, als die herkömmliche Additionmit der Konstanten 1.

In C wird Inkrement und Dekrement in zwei unterschiedlichen Versionen zu Verfügung gestellt:

1. In Postfix schreibweise : a++ oder a - -.

In dieser Version wird in einem Ausdruck der Wert von a in eine unsichtbare Variable kopiert.Der Wert dieser Variablen wird im Ausdruck verwendet und erst später wird die Variable a um1 erhöht.

2. In Präfix schreibweise : ++a ode - - a

In dieser Version wird a zuerst um 1 erniedrigt, und dann wird der geänderte Wert von a imAusdruck verwendet.


B e i s p i e lint i=1, j=0;int x;x= i++ - --j;

Die Berechnung des rechten Ausdrucks ergibt:

i++ : der Wert von i, also 1 wird zur Werteberechnung verwendet,- - j : j wird um 1 erniedrigt und der veränderte Wert also -1 zur Wertberechnung des Ausdrucks

verwendet.

Der Wert des rechten Ausdrucks ist damit 1 - -1 also 2. x wird damit zu 2.

Seiteneffekt des Ausdrucks ist die gleichzeitige Änderung der Variablen i und j. Neben der Zuweisung2 -> x hat nach der Berechnung des Ausdrucks i den Wert 2 und j den Wert -1.Bei der Verwendung von Inkrement und Dekrement kann durch den Seiteneffekt des Operators inAusdrücken Fehler passieren.

B e i s p i e l :int a, b=5;a=b * b++;

Je nach Compiler kann der Ausdruck folgendes Ergebnis liefern:

1. Fall:

Zur Berechnung der rechten Seite wird zuerst der linke Operand und dann erst der rechte Operandausgewertet. Also wird das linke b ersetzt mit 5, das rechte b ebenfalls mit 5.

a= 5 * 5 ergibt 25.a erhält also den wert 25. Seiteneffekt des Ausdrucks: b erhält den Wert 6.

2. Fall:

Zur Berechnung der rechten Seite wird zuerst der rechte Operand und dann erst der linke Operandausgewertet. Also wird das rechte b ersetzt mit 5, danach wird das Inkrement ausgeführt. Also wird bum 1 erhöht und erhält den Wert 6. Danach wird das linke b ersetzt mit dem Wert 6.

a = 6 * 5 ergibt 30.a erhält also den wert 30. Seiteneffekt des Ausdrucks: b hat den Wert 6.

Um dieses Problem zu vermeiden sollte man folgende Regel einhalten:

Falls in einem Ausdruck ein Operand mit Seiteneffekt ( Inkrement oder Dekrement )auftritt, so darf die betroffene Variable nirgendwo sonst im Ausdruck vorkommen.

Mit dieser Regel kann a im obigen Beispiel wir folgt berechnet werden:

a = b * b ;b++;


B I T O P E R A T O R E N

Ein häufig benutzter Bitoperator ist das Schieben nach rechts oder links.Mit dem Schiebeoperator kann eine Multiplikation oder Division um eine Zweierpotenz wesentlichschneller ausgeführt werden.Eine Multiplikation mit 2 x entspricht einem schieben um x Positionen nach links ( Operator << ).

B e i s p i e l : 1 6 * 2 e r g i b t 3 2 .

Durch schieben der Dualzahl 00010000 um eine Stelle nach links ergibt sich die Zahl00100000.Beim schieben nach links wird immer eine 0 an die fehlende Stelle geschrieben.16 * 2 kann also ersetzt werden durch 16 << 1.

Eine Division durch 2 x entspricht einem schieben um x Positionen nach rechts ( Operator >> ).

B e i s p i e l : 3 2 d i v i d i e r t d u r c h 4 e r g i b t 8 .

Schieben der Dualzahl 00100000 um 2 Stellen nach rechts ergibt 00001000 .32 / 4 kann damit ersetzt werden durch 32 >> 2.

E . 2 I m p l i z i t e T y p w a n d l u n g i n A u s d r ü c k e n

In einer Zuweisung oder bei der Berechnung von Werten in Ausdrücken müssen die Operanden einesOperators vom gleichen Typs sein.

Will man z.B. in einer Variabel vom Typ int einen Wert speichern, so muß dieser Wert den Typ inthaben.Addiert man zwei Zahlen so müssen die beiden Zahlen vom gleichen Typ sein. In derProgrammiersprache PASCAL muß diese Regel auch strikt eingehalten werden.

Die Programmiersprache C erlaubt jedoch dem Programmierer die Typen zu mischen, um diese Regeljedoch dennoch einzuhalten wandelt der Compiler von sich aus die Typen. Diese impliziteTypwandlung erfolgt nach bestimmten Regeln.

1. Regel: Wandlung beim Zuweisungsoperator

Variable = Ausdruck

In einer Zuweisung hat immer die Variable auf der linken Seite den bestimmenden Typ. Der Wert desAusdrucks auf der rechten Seite wird daher immer in den Typ der linken Seite gewandelt.

B e i s p i e l :

long L;int i;char c;L = i; /* implizite Wandlung des Wertes von i in den Typ long */c = i ; /* Der wert von i wird automatisch in den Typ char

gewandelt. Ist der Wert von i > +127 entsteht ein Fehler*/


2. Regel: In Ausdrücken

In einem Ausdruck müssen die Operanden eines zweistelligen Operators gleichen Typ besitzen. DerOperand, dessen Typ einen kleineren Wertebeeich besitzt wird immer in den Typ mit dem größerenWerteber gewandelt.

char, unsigned char, short und unsigned short besitzen einen kleineren Wertebereich als int. int besitzteinen kleineren Wertebereich als long. Ganze Zahlen besitzen einen kleineren Wertebereich als reelleZahlen also werden diese nach float oder double gewandelt.

B e i s p i e l e :

double f;f=10; /* 10 ist eine Konstante vom Typ int. 10 wird daher in

double gewandelt */

Die Zuweisung ist eigentlich nicht korrekt, da links eine Variable vom Typ double steht, rechts jedochein Wert vom Typ int. C läßt diese Zuweisung jedoch zu und wandelt automatisch den int-Wert 10 ineine double-Konstante 10.0.

Man sollte solche Konstruktionen jedoch vermeiden.

float f,g;f + g + 2.5; /* 2.5 ist eine Konstante vom Typ double. f und

sind vom Typ float. double hat den höherenWerteberecih also wird der Wert von f und g nachdouble gewandelt */

int i;float a;i=a; /* Der Wert von a wird nach int gewandelt. Dies

geschieht durch abschneiden des rationalen Anteils.Die Variable i enthält nur noch den ganzzahligenAnteil */

unsigned long int i=2147483615UL;float a;a=i; /* Die ganze Zahl i wird in eine reelle zahl vom

Typ float gewandelt. Falls der Wert von i größerist als die maximale Genauigkeit einer float-Zahl (7 Stellen Genauigkeit ) entsteht ein Fehler */

float Zahlen sind nur auf 7 Stellen genau.

Druckt man den Wert von a am Bildschirm aus erhält man 2147483648.0. Die Zahl ist daher falsch.


5 Test von Programmen

Bei der Entwicklung von Programmen können folgende Arten von Fehlern auftreten:

1 . L o g i s c h e F e h l e r ( D e n k f e h l e r )

Hier arbeitet der entworfenen Algorithmus fehlerhaft. Das Programm produziert dadurchfalsche Ergebnisse oder läuft in eine Endlosschleife.

Diese Fehler werden erst zur Laufzeit des Programmes entdeckt.

2 . S y n t a k t i s c h e F e h l e r

Es werden unzulässige C Sprachelement verwendet z.B. fehlerhafte Schlüsselworte WHILEanstatt while , Trennzeichen ; am Ende einer Anweisung wird vergessen, nach eineröffnenden Klammer wird die schließende Klammer vergessen. Verwendung vonProgrammobjekten, die nicht deklariert wurden uva.

Diese Fehler werden vom Compiler entdeckt und angezeigt. Das Programm wird nichtübersetzt.

3 . L a u f z e i t f e h l e r

Diese Fehler treten nach dem Programmstart zur Laufzeit auf.Dazu gehören Fehler, die eine Programmunterbrechung bewirken wie z.B. Division durch 0,Zugriff auf geschützte Speicherbereiche und Programmierfehler wie z.B., Überschreiten vonZahlenbereichen ( Zahlenüberlauf ), Überschreiten oder Unterschreiten von array-Grenzenz.B. Zugriff auf das 11. Array-Element in einem array definiert mit 10 Werten.

Programmunterbrechungen werden vom Betriebssystem ausgelöst und bewirken eineFehlermeldung am Bildschirm mit sofortigem Programmabbruch.Programmierfehler führen analog den logischen Fehlern zu unvorhersehbarenProgrammergebnissen wie fehlerhafte Werte, Endlosschleifen, oder sonstigen nicht gewolltenReaktionen des Programms.

Zur Sicherstellung korrekter Programme muß der Entwickler seine Programme auf Korrektheit prüfen.Dazu sind für das Programm Testmuster anzugeben, die festlegen welche Ergebnisse das Programmfür bestimmte Eingaben produzieren muß.

Hierzu Testmuster für folgende Fälle anzugeben:

1. Für korrekte Eingabewerte müssen richtige Ergebniswerte produziert werden2. Auf fehlerhafte Eingabewerte darf das Programm nicht oder nur mit entsprechender

Fehlermeldung reagieren3. Alle Sonderfälle müssen korrekt abgearbeitet werden.

B e i s p i e l : U m r e c h n u n g e i n e r D e z i m a l z a h l i n e i n e 1 6 - B i t - D u a l z a h l

Es können folgende Testmuster angegeben werden:

û Korrekte Eingabewerte sind alle ganzen Zahlen zwischen 0 und 216-1.

Als Testmuster wird gewählt:

eine gerade Zahl 6 Programmergebnis: 0000 0000 0000 0110Eine ungerade Zahl: 7 0000 0000 0000 0111Eine Zweierpotenz: 1024 0000 0010 0000 0000Eine sonstige Zahl: 150 0000 0000 1001 0110


û Fehlerhafte Eingabewerte sind:

Negative Zahlen -1 Fehlermeldung: Zahl ist negativZahlen mit Wert größer 216-1 68500 Fehlermeldung: Zahl zu großReelle Zahlen 1.25 Fehlermeldung: keine ganze ZahlSonstige Eingabezeichen,die keine ganzen Zahlen darstellen a$23 Fehlermeldung: keine ganze Zahl

û Sonderfälle, die beiden Grenzwerte, also die Zahl 0 und die Zahl 216-1=65535

0 0000 0000 0000 000065535 1111 1111 1111 1111

Reagiert das Programm nicht wie erwartet auf die Testmuster, so ist das Programm fehlerhaft. Durcheingrenzen des Fehlerortes muß dann im Programm der oder die Fehler lokalisiert werden.Dazu hat der Programmierer zwei grundsätzliche Möglichkeiten:

1. Fehlereingrenzung durch die klassische Methode

In das Programm werden Ausgabe-Anweisungen eingebaut, mit deren Hilfe man den Kontrollflußund die Variablenwerte beobachten kann.

2. Fehlerlokalisierung mit einem Testhilfeprogramm ( Quellcode-Debugger )

Das Programm wird unter Kontrolle eines Testhilfeprogramms gestartet. Diese Systemprogrammüberwacht den Ablauf und die Variablenwerte des Programms.

B e i s p i e l :

Gegeben ist folgendes fehlerhafte Programm. Durch einen Programmfehler wird die do..while-Schleifeniemals beendet, es entsteht eine Endlosschleife.

int main()

{ int i, summe;

summe=0;

i=1;

do

{ summe=summe + i;

i=i+2;

}

while ( i != 20 );

printf("die summe ist: %i\n", summe);

return 0;

}


P r o g r a m m t e s t n a c h d e r k l a s s i s c h e n M e t h o d e

In das Programm wird eine Ausgabeanweisung eingebaut, so daß die Anzahl der Schleifendurchläufeund die Schleifenabbruch-Variable i beobachtet werde kann.

int main()

{ int i, summe;

summe=0;

i=1;

do

{ summe=summe + i;

i=i+2;

printf(„ i = %i\n“,i);

/* Die Werte von i werden in jedemSchleifendurchlauf am Bildschirm angezeigt.

So kann festgestellt werden daß i immer einenWert ungleich 20 besitzt und damit die Schleifeniemals endet. */

}

while ( i != 20 );

printf("die summe ist: %i\n", summe);

return 0;}

T e s t e n d e s P r o g r a m m s m i t e i n e m T e s t h i l f e p r o g r a m m

( D e b u g g e r )

Der Debugger ist ein Systemprogramm, der die Syntax der Programmiersprache kennt und unterdessen Kontrolle ein Programm abgearbeitet wird. Gestartet wird das Programm durch den Debugger,nicht direkt durch das Betriebssystem. Der Debugger überwacht den Programmablauf und dieVariablenwerte und erlaubt folgende Programmabläufe:

1. Starten des Programms und abarbeiten bis zu einem gesetzten Haltepunkt ( Breakpoint )2. Schrittweises abarbeiten jeweils einer Programmzeile angestoßen durch einen Tastendruck3. Anzeigen und Verändern von Variablenwerten ( im angehaltenen Zustand ).4. Weiterbearbeitung des Programms nach einem Haltepunkt.


6 Rekursive Algorithmen

Folgendes Bild veranschaulicht den Begriff Rekursion.


Rekursion im Bild

Ein rekursiver Algorithmus ist ein Algorithmus, der sich selbst verwendet.

Rekursion findet man auch in der Mathematik bei der Definition von Funktionen und Folgen. Dieeinfachste rekursive Funktion ist die Fakultät. Ein andere etwas komplexere Rekursion ist die Folge derFibonacci-Zahlen.

Man kann beweisen, daß jede Rekursion durch Iteration realisierbar ist. Ein rekursiver Algorithmus kannalso immer mit Hilfe von Schleifen ( Iteration ) formuliert werden. Häufig ist jedoch der rekursive Ansatzdie einfachere oder auch bessere Lösung.Algorithmen zum Sortieren und Suchen beruhten i.a. auf dem Prinzip „man durchlaufe eine Liste bis mandie Liste vollständig bearbeitet oder das gesuchte Element gefunden hat“. Dieses Prinzip verwendet alsKontrollstruktur die Schleife, auch Iteration genannt. Sortieren und Suchen kann jedoch auch rekursiverfolgen. So gibt es den Sortieralgorithmus Quicksort, der auf der Rekursion basiert, und als schnellsterAlgorithmus zum sortieren von linearen Listen gilt. Suchalgorithmen, die auf rekursiven Datenstrukturen,den Bäumen basieren, sind ebenfalls die effektivsten.

6 . 1 R E K U R S I O N V E R S U S I T E R A T I O N A M B E I S P I E L D E RF A K U L T Ä T

Mit der Unterprogrammtechnik ergibt sich die Möglichkeit Algorithmen nicht mit Hilfe einer Schleife, alsoals Iteration zu realisieren, sondern durch die rekursive Verwendung eines Unterprogramms. Rekursionheißt in diesem Fall ein Unterprogramm ruft zur Lösung des Problems ich selbst wieder auf.

Die Funktion Fakultät ist auf folgende zwei Arten definiert:

I t e r a t i v e D e f i n i t i o n n ! = 1 * 2 * 3 * . . . . . * n

R e k u r s i v e D e f i n i t i o n n ! = ( n - 1 ) ! * n

0 ! = 1


Zur iterativen Berechnung der Fakultät in einem C Programm benutzt man eine Zählschleife. Die C-Funktion sieht dann so aus:

/* ---- Definition der iterativen Funktion Fakultät(n) ----- */

unsigned int fac( unsigned int n )

{ unsigned int i, fakultaet=1;

if ( n == 0 ) fakultaet=1;

else for ( i=1; i<=n; i++ ) fakultaet=fakultaet*i;

return fakultaet;

}

Bei der rekursiven Berechnung der Fakultät wird eine Funktion fac() definiert, die sich selbst aufruft.

/* ---- Deklaration der rekursiven Funktion Fakultät(n) ----- */

unsigned int fac(unsigned int n )

{ unsigned int fakultaet;

if (n==0) fakultaet=1;

else fakultaet=n*fac(n-1);

return fakultaet;

}

Duch die Verwendung der Funktion fac bei der Definition von fac könnte man meinen, eine endlose Folgevon Funktionsaufrufen zu produzieren. Dies ist jedoch nicht der Fall. Jeder Funktionsaufruf führt zu einerVereinfachung ( von n nach n-1 bis zum einfachsten Wert 0 ). Die Rekursion endet beim einfachsten Fall,dies ist 0 ! . Zur Berechnung von 0 ! wird kein weiterer Funktionsaufruf mehr benötigt, da der Wert perDefinition bekannt ist. Im Programm ist das Ende der Rekursion erreicht, wenn man in dieFallunterscheidung mit n==0 eintritt. Dieser Programmteil verwendet nicht mehr die Funktion fac().

W i e f u n k t i o n i e r t d i e R e k u r s i o n ?

Es soll z.B. der Wert von 4! berechnet werden.

Das Hauptprogramm ruft daher die Funktion fac(4) auf.

fac(4) = 4 * fac(3) Also muß fac(3) aufgerufen werden bevor man fac(4) berechnen kann.

fac(3) = 3 * fac(2 )

fac(2) = 2 * fac(1)

fac(1) = 1 * fac(0) Beim Aufruf von fac(0) tritt man in die

Fallunterscheidung ein.

fac(0) erhält damit den Wert 1.

Damit kann man jetzt auch fac(1) berechnen.

fac(1) = 1 * 1 = 1

fac(2) = 2 * 1 = 2

fac(3) = 3 * 2 = 6

fac(4) = 4 * 6 = 24.


Wird ein Unterprogramm aufgerufen, dann werden die Parameter im Speicher in einer bestimmten Artund Weise dem Unterprogramm zu Verfügung gestellt. Da zur Ermöglichung der Rekursion die Aufrufegeschachtelt werden müssen und die Anzahl der geschachtelten Aufrufe erst zur Laufzeit bekannt sind,werden alle Parameter und lokale Variablen eines Unterprogramms auf einer dynamisch zu Laufzeitveränderbaren Datenstruktur abgelegt. Diese Datenstruktur ist der STACK.

Ein Stack ist ein Stapel von Werten. Die Höhe des Stapels kann sich zur Laufzeit dynamisch erhöhenoder erniedrigen.

Boden

Popholt oberstesElement vomStapel herunter

Pushlegt einElement obenauf den Stapel

Der Stapel hat einen Boden. Auf diesen Boden werden die Werte nacheinander immer von oben auf denStack gelegt. Jeder neue Wert wird daher auf den vorherigen Wert gelegt. Diesen Vorgang nennt manPUSH. Der letzte Wert liegt dann oben auf dem Stapel. Holt man die Werte wieder herunter, wird derWert an oberster Stelle genommen. Diesen Vorgang nennt man pop. Wird der letzte Wert geholt ist derStackboden erreicht. Der Stack ist dann leer. Ein Beispiel für einen Stack findet man z.B. im ChinaRestaurant. Dort gibt es ein Gerät „Tellerwärmer“. Saubere Teller werden nacheinander oben in dasGerät gelegt. Der Boden sinkt damit nach unten ab und der letzte Teller liegt oben auf dem Stapel.Benötigt man für einen Gast einen Teller wird der oberste Teller herausgenommen. Eine solcheDatenstruktur bezeichnet man auch als LIFO ( Last In First Out ). Der Wert der zuletzt auf den Stapelgelegt wurde, wird als erster wieder herunter genommen.Die Parameter eines Unterprogramms werden vom Hauptprogramm nacheinander auf den Stack gelegt (der Stack wird aufgebaut ). In C wird die Parameterliste von rechts nach links bearbeitet. So liegt dererste Parameter oben auf dem Stack.. Das Unterprogramm verwendet die Parameter auf dem Stack. Vordem Verlassen des Unterprogramms werden die Parameter wieder vom Stack genommen ( der Stackwird abgebaut ). Auch lokale Variablen, die im Unterprogramm definiert sind, werden vomUnterprogramm auf den Stack gelegt und vor Verlassen des Unterprogramms wiederheruntergenommen. Lokale Variablen eines Unterprogramms sind damit nur für die Zeit auf dem Stackvorhanden, in der das Unterprogramm abgearbeitet wird. Liefert das Unterprogramm im falle einerFunktion einen Wert an das Hauptprogramm zurück wird auch dieser Wert über den Stack übergeben.Nachdem die lokalen Variablen und die Unterprogrammparameter vom Stack genommen sind, wird dererrechnete Ergebniswert auf den Stack gelegt. Das Hauptprogramm nimmt diesen Wert dann wieder vomStack herunter.

Bei einer Rekursion wird daher der Stack langsam aufgebaut bis das Rekursionsende erreicht ist unddanach wird der Stack zur Werteberechnung wieder abgebaut. Im Falle der Fakultät sieht der Stack dannfolgendermaßen aus:



Aufbau und Abbau des Stack bei Rekursion

434

34

234

21

34

210

34

21

0 ! = 1

34

21*1=1

34

2*1=23*2=6

4 4*6=24

Rekursionsende ist erreicht

Stackaufbau Stackabbau

Aufruf von fac(4)

Aufruf fac(3)

Aufruf fac(0)

Aufruf fac(1)

Aufruf fac(2)

Ergebnisvon

fac(0)

Ergebnisvon

fac(3)

Ergebnisvon

fac(2)

Ergebnisvon

fac(1)

Ergebnisvon

fac(4)

W a n n v e r w e n d e t m a n d i e R e k u r s i o n ?

8 Falls eine rekursive Definitionen einer Funktion vorliegt, dann ist die Umsetzung in einProgramm trivial.

8 Es gibt rekursiv definierte Datenstrukturen, die Bäume, die sich über rekursive Algorithmeneinfach realisieren lassen

8 Es gibt Probleme, deren Lösung sich einfacher rekursiv anbieten. Ein Beispiel dafür ist dasProblem der Türme von Hanoi


6 . 2 D I E T Ü R M E V O N H A N O I

Es gibt eine Legende, die besagt, daß Mönche in Hanoi die Aufgabe hatten 64 Scheibenunterschiedlicher Größe von einem Stab A auf einen Stab C unter Verwendung eines dritten Stabes C zulegen.

Stab A Stab B Stab

Versetzte Turm mit n Scheibenvon A nach C

Bei der Lösung des Problems sollten folgende Randbedingungen eingehalten werden:8 Es darf immer nur eine Scheibe versetzt werden

8 Es darf niemals eine größere Scheibe auf einer kleineren Scheibe liegen

L ö s u n g s a n s a t z :

8 Probiere eine Lösung zu finden mit n = 1

8 Löse das Problem für den Fall n = 2

8 Löse das Problem für n Scheiben, indem man die Lösung zurückführt auf die Lösung mitkleinerem n. Der einfachste Fall ist der Fall mit n = 1

Dieses Vorgehen nennt man vollständige Induktion, und wird in der Mathematik zum beweisen vonSätzen benutzt.

L ö s u n g f ü r n = 1

Stab A Stab B Stab C

Versetzte vonA nach C

Die Lösung ist trivial. Man versetzt die Scheibe von A nach C ohne Verwendung von B.




Stab A Stab B Stab

Versetzteoberste Scheibevon A nac B


Versetzteunterste Scheibevon A nach C


VersetzteScheibe vonB nach C




N-te Scheibe

Versetzte n-1Scheibenvon A nach B

Versetzte n-1Scheibenvon B nach C

versetzte n-1 Scheibe von A nach B( n-1 ) = 2 Scheiben Start ist A und Ziel ist B

versetzte Scheibe von A nach C, versetzte Scheibe von A nach B, versetzte Scheibe von C nachBversetzte n-te Scheibe von A nach Cversetzte n-1 Scheiben von B nach C

( n-1 ) = 2 Scheiben , Start ist B und Ziel ist C versetzte Scheibe von B nach A, versetzte Scheibe von B nach C, versetzte Scheibe von Anach C

S t r u k t o g r a m m z u m A l g o r i t h m u s T ü r m e v o n H a n o i

Algorithmus Türme von Hanoi

Versetzt n Scheiben von Stab Start nach Stab Ziel über den Stab Lager

Objekte: n Anzahl der Scheiben

N gleich 1 ?Ja Nein

Versetzte Scheibe von Start nach Ziel Versetzte n-1 Scheiben von Start nachLager. Benutze Ziel als Zwischenlager

Versetzte Scheibe von Start nach Ziel

Versetze n-1 Scheiben von Lager nachZiel. Benutze Start als Zwischenlager


R e a l i s i e r u n g d e s A l g o r i t h m u s a l s C P r o g r a m m

#include <stdio.h>

void TuermeVonHanoi(void);

void VersetzeScheibe( int n ,char start,char ziel,char lager);

int main()

{ TuermeVonHanoi();

return 0;

}

void TuermeVonHanoi(void)

{ int n;

char start,ziel,lager;

start='A';

ziel= 'C';

lager='B';

printf(„Bitte geben Sie eine natürliche Zahl ein: „);

scanf(„%i“,&n);

printf(„Das Programm versetzt %i Scheiben von %c nac %c\n“,n,start,ziel);

VersetzeScheibe(n,start,ziel,lager);

}

void VersetzeScheibe( int n ,char start,char ziel,char lager)

{

if (n==1)

printf(„Versetze Scheibe von %c nach %c\n“,start,ziel );

else

{ VersetzeScheibe((n-1),start,lager,ziel);

printf(„Versetze Scheibe von %c nac %c\n“,start,ziel );

VersetzeScheibe((n-1),lager,ziel,start);

}

}


A u f w a n d s a b s c h ä t z u n g

Anzahl derScheiben

Anzahl der Versetzungen

1 1 vgl. 21=22 3 vgl. 22= 43 2*3 + 1 = 7 vgl. 2 3 = 84 2 * ( ( 2*3) +1 ) + 1 = 15 vgl. 2 4 = 165 2 * ( (2*7) + 1) +1 = 31 vgl. 2 5 = 32n ca. 2 n

Bei 64 Scheiben müssten die Mönche daher 2 64 Scheiben versetzen. Wenn das versetzen einer Scheibe1 Sekunde braucht, dann sind das 590 Milliarden Jahre. Für die Mönche also eine unlösbare Aufgabe.

5 . 3 R E K U R S I V E S S O R T I E R E N

Das schnellste Verfahren zum sortieren einer Liste von Zahlen hat C.A.R. Hoare erfunden. DerAlgorithmus beruht auf dem Prinzip Zerlegen und Mischen und heißt Quicksort.

D i e I d e e

Gegeben ist eine Liste von unsortierten Zahlen.

44 55 12 42 94 6 18 67-------->Durch-suchenvon links

Element x

<-----Durch-suchenvonrechts

Es wird ein Element x in der Mitte der Liste als Vergleichselement gewählt. Dieses Vergleichselementtrennt die Liste in zwei Teile. Eine Liste rechts davon und eine Liste links davon. Man durchsucht die linkeHälfte von links nach rechts und die rechte Hälfte von rechts nach links. Falls eine Zahl L in der linkenTeilhälfte größer dem Vergleichselement x und eine Zahl R in der rechten Teilhälfte kleiner demVergleichselement x ist, so werden die beiden Zahlen L und R miteinander vertauscht. Linke und rechteTeilhälfte werden solange durchsucht und gefundene Zahlen miteinander vertauscht bis sich linker Indexund rechter Index überholen, d.h. beide Teilhälften durchsucht worden sind. Danach ist die ursprünglicheListe in zwei Hälften zerlegt. Die linke Liste enthält Zahlen kleiner dem Vergleichselement, die rechteListe Zahlen größer dem Vergleichselement.

Das Verfahren an obigem Beispiel gezeigt:

Linke Position Links =1Rechte Position Rechts = 8Vergleichselement ist Liste[4] = 42

D u r c h s u c h e l i n k e n T e i l v o n l i n k s

Liste[Links] = Liste[1] = 44. 44 ist größer als 42. Also merke Position Links zum tauschen

D u r c h s u c h e r e c h t e n T e i l v o n r e c h t s

Liste[Rechts] = Liste[8] = 67. 67 ist größer als 42. Also ist die nächste Position Rechts=Rechts - 1 = 7Liste[Rechts] = Liste[7] =18. 18 ist kleiner als 42. Also merke diese Position zum tauschen


Falls links <= rechts ( die beiden Positionen haben sich noch nicht überholt ),dann tausche die beiden Zahlen und rücke Links und Rechts um eine Position weiter.Hier wird also 44 mit 18 vertauscht. Links = Links +1 = 2 und Rechts = Rechts -1 = 6

18 55 12 42 94 6 44 67

D u r c h s u c h e v o n l i n k sListe[Links]=Liste[2]=55. 55 ist größer 42. Also merke diese Position zum tauschen

D u r c h s u c h e v o n r e c h t sListe[rechts]=Liste[6]=6. 6 ist kleiner als 42. Also merke diese Position zum tauschen.Falls links <= rechts, dann tausche die beiden Zahlen und rücke links und rechts um eine Positionweiter.

Hier wird also 55 mit 6 vertauscht. Links = Links +1 = 3 und Rechts = Rechts -1 = 518 6 12 42 94 55 44 67

D u r c h s u c h e v o n l i n k s

Liste[Links]=Liste[3]=12. 12 ist kleiner als 42. Links = Links +1 = 4Liste[Links]=Liste[4]=42. 42 ist nicht größer als 42. Merke diese Position zum tauschen

D u r c h s u c h e v o n r e c h t sListe[rechts]=Liste[5]=94. 94 ist größer als 42. Rechts=Rechts -1 = 4.Liste[rechts]=Liste[4]=42. 42 ist nicht kleiner als 42. Merke diese Position zum tauschen

Falls links <= rechts, dann tausche die beiden Zahlen und rücke links und rechts um eine Positionweiter.

Hier wird also 42 mit 42 vertauscht. Links = Links +1 = 5 und rechts = rechts -1 =3Die beiden Positionen haben sich jetzt überholt, also endet das durchsuchen und tauschen.

18 6 12 42 94 55 44 67 | wende hier | | wende Quicksort | | Quicksort an | | an |

Die Liste ist jetzt in zwei Teile zerlegt. Der linke Teil enthält Zahlen kleiner 42. Der rechte Teil Zahlengrößer als 42. Die Liste ist jedoch noch nicht sortiert.

Möchte man die gesamte Liste sortieren, dann braucht man das Verfahren nur noch auf die linkeTeilhälfte und die rechte Teilhälfte anzuwenden. Dadurch erhält man eine rekursive Lösung. DieRekursion endet, wenn die zu sortierende Liste nur noch ein Element enthält.


C - P r o g r a m m f ü r Q u i c k s o r t

#include <stdio.h>

void quicksort(int anfang,int ende, int liste[] )

{ int startwert, links, rechts, hilf ;

links = anfang;

rechts = ende;

startwert = liste[(anfang+ende) / 2];

do

{ /* Durchlaufen von */

while ( liste[links] < startwert ) /* links nach rechts */

links = links + 1;

while ( liste[rechts] > startwert ) /* Durchlaufen von */

rechts = rechts - 1 ; /* rechts nach links */

if ( links <= rechts ) /* Tauschen falls noch nicht */

{ /* ueberholt */

hilf = liste[links];

liste[links]= liste[rechts];

liste[rechts]=hilf;

links = links + 1; /* Links und rechts um eine */

rechts = rechts - 1; /* Position vorschalten */

}

}

while ( links <= rechts) ; /* Abbruch falls links und */

/* rechts •berholt */

if (rechts > anfang) quicksort(anfang,rechts,liste);

/* Qsort linker Bereich */

if (links < ende) quicksort(links,ende,liste);

/* Qsort rechter Bereich */

}

int main ()

{ int i,liste[8]={44,55,12,42,94,6,18,67 }; /* Liste von Zahlen */

for ( i=0; i < 8; i++) printf(" %i ",liste[i]);

printf("\n");

quicksort(0,7,liste);

for ( i=0; i < 8; i++) printf(" %i ",liste[i]);

return 0;}


7 Sortieren und Suchen nach dem Hash-Verfahren

D A S P R O B L E M

Gegeben ist eine Liste von Namen. Diese Namen sind mit einem Verfahren so zusortieren, dass ein Name k mit dem gleichen Verfahren gesucht werden kann

D I E I D E E :

7 . 1 S O R T I E R E N M I T H A S H - F U N K T I O N E N

Man speichert die Namen in einer Liste mit M Elementen, also ein array, in dem M Werte Platz finden.

Name kPosition i

Liste mit M Werten

0

M-1

Hash-Funktion

Die Position eines zu sortierenden Namen k in der Liste berechnet man über eine Funktion, Hash-Funktion genannt.

Der in der Liste einzutragenden Name k ist Eingabeparameter der Hashfunktion H. Als Ergebnis liefertdie Hash-Funktion die Position i im array, in der der Name zu speichern ist. Die gleiche Funktion H wirdbenutzt, um die Position eines gesuchten Namen f in der Liste zu bestimmen. Der gesuchte Name f istdann ebenfalls Eingabeparameter der Hash-Funktion H. Ergebnis von H ist die Position in der Liste, ander der gesuchte Name f steht.

B e i s p i e l :

Die Liste enthält 10 Datenelemente, also ist M=10.

Zu sortieren sind die Namen: Keller, Hulin, Ertel, Gampp

Hash-Funktion H(k) ist die Ordnungsnummer des ersten Buchstabensdes Namen k modulo M

è Die Hash-Funktion muss immer einen Wert mitdem Modulo-Operator berechnen, damit dieberechnete Position i immer innerhalb des arrayliegt.

Zum Einfügen der Namen in die richtige Position wird die Hash-Funktion H(k) wie folgt auf die sortierendeNamen angewendet:


H(Keller)= 75 modulo 10 = 5H(Hulin) = 72 modulo 10 = 2

H(Ertel) = 69 modulo 10 = 9H(Gampp) = 71 modulo 10 = 1

Liste mit 10 Werten

0

9

Gampp

Hulin

Keller

Ertel

7 . 2 S U C H E N

Bei der Suche nach einem Namen wird ebenfalls die Hash-Funktion verwendet. Ein Suche nach demNamen Gampp ergibt:

H(Gampp) = 71 modulo 10 = 1An dieser Position steht tatsächlich auch der Name Gampp.

Eine Suche nach dem Namen „Brümmer“ ergibt:

H(Brümmer) = 66 modulo 10 = 6An dieser Position ist kein Name gespeichert

Ein Vergleich des gesuchten Namens „Brümmer“ mit dem Eintrag in der Liste ergibt jedoch – die Positionist leer. Der Name „Brümmer“ wurde nicht in die Liste eingetragen.

7 . 3 K O L L I S S I O N E N

Es soll ein weiterer Name „Koch“ in die Liste eingetragen werden.

Die Berechnung der Hash-Funktion ergibt:

H(Koch) = 75 modulo 10 = 5

An Position 5 ist jedoch schon der Name „Keller“ eingetragen. Die Berechnung des Namens „Koch“ führtezu einer Kollission.

Wie kann dieses Problem gelöst werden ?

I d e e

Zur Lösung der Kollission wird versucht für den Namen „Koch“ eine Ausweichposition zu bestimmen.Wenn also Position 5 schon mit dem Namen „Keller“ belegt ist, dann versuchen wir den Namen an diefolgende Position, also 6, zu schreiben. In unserem Fall ist die Position 6 frei und damit eine Lösung desProblems. „Koch“ wird also an die Position H(Koch ) + 1 eingetragen.

Wäre diese Position jedoch auch belegt, versucht man die nächste folgende Position also H(Koch ) + 2usw.


Diese Strategie eine Ausweichposition zu finden wird solange angewendet bis entweder ein freier Platzzur Speicherung des Namens gefunden ist oder aber die Liste vollständig ohne Resultat nach freienPositionen durchsucht wurde.

Zur Lösung der Kollission wird also eine weitere Funktion angewendet, Kollossions-Funktion genannt.Die oben beschriebene Strategie für die Kollssionsbehandlung wird lineares Sondieren genannt undversucht ausgehend von der berechneten Hash-Position H(Koch ) alle folgenden Positionen in der Liste:

(H(k) + i ) modulo M 1 <= i < M

Bei der Suche nach dem Namen „Koch“ liefert die Hash-Funktion die Position 5. Da bei jeder durch dieHash-Funktion errechneten Position eine Kollission möglich war, muss ein Vergleich des gesuchtenNamens mit dem Namen an der errechneten Position erfolgen. Steht der gesuchte Namen nicht an dererrechneten Position, wurde der gesuchte Name, wenn dieser überhaupt in der Liste vorkommt, übereine Kollissionsbehandlung an eine Ausweichposition geschrieben. Also muss auch beim Suchen alleAusweichpositionen nach dem Namen durchsucht werden. Die Suche endet dann, wenn entweder dergesuchte Name, hier „Koch“, in der Liste gefunden werden konnte, oder aber die errechnete Position freiist. Im letzten Fall kommt der gesuchte Name nicht in der Liste vor.

Im konkreten Beispiel wird zuerst an der errechneten Hash-Position 5 nach Koch gesucht, dann dieAusweichposition 6 berechnet. Hier endte die Suche, da der Eintrag Koch gefunden wurde.

7 . 4 L Ö S C H E N

Im obigen Beispiel soll nach Einfügen von „Koch“ der Name „Keller“ aus der Liste gelöscht werden. DieListe würde nach einem Löschvorgang folgendes Aussehen haben:

Liste mit 10 Werten

0

9

Gampp

Hulin

Koch

Ertel

Die Position 5 ist nach dem Löschen frei. Wollen wir jetzt nach demNamen „Koch“ suchen berechnet die Hash-Funktion die Position 5. An derPosition 5 steht kein Name mehr, also endet hier die Suche mit demErgebnis: Der Name „Koch“ kommt in der Liste nicht vor. Dies istaber nicht richtig, da Koch an der Position 6 steht.

D a s P r o b l e m

besteht darin, dass Koch vorher über eine Kollission in die Liste eingetragen wurde. Nach dem Löschenvon Keller tritt keine Kollssion mehr auf.

W i e k a n n m a n d i e s e s P r o b l e m l ö s e n ?

In der Liste wird eine gelöschte Position durch den Eintrag „Hier wurde was gelöscht“ gekennzeichnet.Nach der Berechnung der Hash-Funktion

H(Koch) = 5

findet man den Eintrag „ Hier wurde was gelöscht“, d.h. „Koch“ könnte durch eine Kollission an eineranderen Position stehen. Also muss die Kollissionsbehandlung angewendet werden. Entweder manfindet über die Kollissionsbehandlung den Namen „Koch“ ( in diesem Beispiel an der Position 6 ) oderaber man trifft auf eine freie Position. Im ersten Fall ist „Koch“ gefunden im zweiten Fall kommt der Name„Koch“ in der Liste tatsächlich nicht vor.


7 . 5 E I G E N S C H A F T E N E I N E R H A S H - F U N K T I O N

Das Hashverfahren arbeitet sehr schnell , wenn

1. Die Hash-Funktion sehr einfach zu berechnen ist2. als Ergebnis der Hash-Funktion alle möglichen Positionen von 0 bis M-1 in der Liste möglich

sind, d.h. die Hash-Funktion ist surjektiv3. die Hash-Funktion die Dateneelemente in der Liste gut streut4. möglichst wenig Kollssionen auftreten

7 . 5 . 1 B e i s p i e l f ü r ü b l i c h e H a s h - F u n k t i o n e n

Die zu sortierenden Werte werden im Folgenden als Schlüssel bezeichnet. Ein Schlüssel kann entwedereine Zahl oder eine Zeichenfolge sein.

û Sortiert werden soll eine Zeichenkette mit Anzahl k Zeichen z.B. es sollen Namen sortiert werden

∑=

=k

iiZeichenhlOrdnungszaSchlüsselH

1

)()( modulo M

û Es sollen natürliche Zahlen sortiert werden ( Divisionsmethode )

H(Schlüssel) = Zahl modulo M

û Es sollen natürliche Zahlen sortiert werden. Die Zahlen werden als Folge von Ziffern znzn-1...z1interpretiert ( Mittel-Quadrat-Methode )

H ( Schlüssel ) berechnet sich wie folgt:

• Bilde das Quadrat der Zahl. Der berechnete Wert ist neue Ziffernfolge mit einer Anzahl vonZiffern grösser oder gleich n

• Entnehme den mitteleren Block von n Ziffern. Diese Ziffern ergeben die Position in der Liste.

7 . 5 . 2 B e i s p i e l e f ü r K o l l i s s i o n s - F u n k t i o n e n

Die zu sortierenden Werte werden im Folgenden als Schlüssel bezeichnet. Ein Schlüssel kann entwedereine Zahl oder eine Zeichenfolge sein.

L i n e a r e s S o n d i e r e n

Ausweichpos i( Schlüssel ) = ( H(Schlüssel) + i ) modulo M, 1 <= i <= M-1

Q u a d r a t i s c h e s S o n d i e r e n

Ausweichpos i(Schlüssel ) = ( H(Schlüssel ) +(-) i 2 ) modulo M, 1 <= i <= M-1


Literaturverzeichnis

Darnell/Margolis: C – A software Engineering Approach (ANSI C), Springer

DIN 66 261: Sinnbilder für Struktogramme nach Nassi-Shneidermann, Beuth-Verlag, Berlin, 1985

Goll/Güner/Wiese: C als erste Programmiersprache, ISO-Standard, Teubner, 1999

Güting R. H.: Datenstrukturen und Algorithmen, Teubner, 1992

Hoare, C.A.R.: Quicksort, Computer Journal No. 1, 1962

Kernighan B.W./Ritchie D.M.: Programmieren in C, 2. Auflage, Hanser, München, 1990

Knuth, D.E. The Art of Computer Programming Vol.1 – Vol.3, AddisonWesley

Kurt Mehlhorn Datenstrukturen und effiziente Algorithmen

Lowes/Paulik : Programmieren mit C – ANSI Standard -, Teubner, 1992

Regionales RechenzentrumNiedersachsen / Uni Hannover(RRZN) *

C

T. Pratt, M. Zelkowitz Programmiersprachen, Design und Implementierung, PrenticeHall, 1997

Wirth, N:: Algorithmen und Datenstrukturen, Teubner, 1983

*: Dieses Nachschlageheft kann beim ASTA / Lehrmittelreferat für Preise unter 10.- DM erworbenwerden. Weitere Themenhefte: C++, JAVA, UNIX, Windows NT ......


A Anhang

A 1 R A N G F O L G E V O N O P E R A T O R E N

Priorität Operatoren Assoziativität1 ()

[]-> .

FunktionsaufrufArrayzugriffZugriff auf Komponenteneiner Struktur

Links -> Rechts

2 !~++ --sizeof+ -(Typname)*&

Logisch NICHTKomplementInkrement, Dekrement

VorzeichenExplizite TypwandlungZeiger DereferenzierungAdressbildung

Rechts -> Links

3 * /%

Multiplikation, DivisionModulo

Links -> Rechts

4 + - Addition, Subtraktion Links -> Rechts5 << >> Bitweises Schieben Links -> Rechts6 > >= < <= Vergleiche

grösser, grösser-gleich,kleiner, kleiner-gleich

Links -> Rechts

7 == != VergleicheGleich, Ungleich

Links -> Rechts

8 & Bitweises UND Links -> Rechts9 ^ Bitweise Exklusiv-ODER Links -> Rechts10 | Bitweise ODER Links -> Rechts11 && Logisches UND Links -> Rechts12 || Logisches ODER Links -> Rechts13 ?: Bedingte Auswertung Rechts -> Links14 = Zuweisung Rechts -> Links15 += -= *= /=

%= &= ^= |=<<= >>=

Kombinierte Zuweisung Rechts -> Links

16 , Komma-Operator Links -> Rechts

A 2 S y n t a x d i a g r a m m e

Syntaxdiagramme sind zu finden in :

Darnell/Margolis: C – A software Engineering Approach (ANSI C), SpringerLowes/Paulik : Programmieren mit C – ANSI Standard -, Teubner, 1992


A 3 A N S I - F u n k t i o n e n

Alle vorgegebenen Bibliotheksfunktionen sind in Klassen ( Bibliotheken ) eingruppiert.

Zu jeder Klasse existiert eine Headerdatei xxx.h , in der die Prototypen der Funktionen sowie allgemeineDatentypen und Konstanten definiert sind. Nach dem Standard sind folgende Klassen definiert:

Name der benötigten Headerdatei Inhalt der Funktionsbibliothek

assert.h Funktionen zur Fehlersuchectype.h Funktionen zur Konvertierung von Zeichenlocale.h Funktionen zur Einstellung länderspezifischer

Darstellungenmath.h Mathematische Funktionensignal.h Funktionen zur Signalbehandlungstdarg.h Funktionen zur Behandlung einer variablen

Parameterlistestdio.h Ein-/Ausgabe-Funktionenstdlib.h Stringkonvertierung, Speicherverwaltung,

Zufallszahlenstring.h Funktionen zu Bearbeitung von Zeichenketten

( strings )time.h Datum und Uhrzeit

Die fettgedruckten Bibliotheken werden in den Übungen zu Programmieren 1 / 2 benötigt. Eineausführliche Beschreibung der Funktionen sind aus der Online-Hilfe zu den Compilern zu entnehmen.

Documents

Grundlagen der Programmierung und Einführung in die …zeller/HomePage/VorlProg/programmieren1.pdf · textuelle Beschreibung nach formalen Regeln Natürliche Sprache - nicht formal