Springer-Lehrbuch Springer-Verlag Berlin Heidelberg GmbH Wolfgang Kiichlin· Andreas Weber Einfiihrung in die Informatik Objektorientiert mit Java Mit 32 Abbildungen und 2 Tabellen Springer Professor Dr. Wolfgang Kuchlin Wilhelm-Schickard-Institut fur Informatik UniversiHit Tiibingen Sand 13,72076 Tubingen [email protected] http://www-sr.informatik.uni-tuebingen.de Dr. Andreas Weber Fraunhofer-Institut fUr Graphische Datenverarbeitung Rundeturmstr. 6, 64283 Darmstadt [email protected] http://www.igd.fhg.de/-aweber ACM Computing Classification (1998): A.I, D.I-3, F.2-3 ISBN 978-3-54D-67384-2 Die Deutsche Bibliothek - CIP-Einheitsaufnahme Kiichlin, Wolfgang: Einfiihrung in die Informatik: objektorientiert mit Java/Wolfgang Kiichlin; Andreas Weber. (Springer-Lehrbuch) ISBN 978-3-540-67384-2 ISBN 978-3-662-06854-0 (eBook) DOI 10.1007/978-3-662-06854-0 Dieses Werk ist urheberrechtlich geschiitzt. Die dadurch begriindeten Rechte, insbesondere die der Dbersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfaltigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugs weiser Verwertung, vorbehalten. Eine Vervielfaltigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der je weils geltenden Fassung zulassig. Sie ist grundsatzlich vergiitungspflichtig. Zuwiderhand lungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. © Springer-Verlag Berlin Heidelberg 2000 Ursprlinglich erschienen bei Springer-Verlag Berlin Heidelberg New York 2000 Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, daB solche Namen im Sinne der Warenzeichen-und Markenschutz-Gesetzgebung als frei zu betrachten waren und daher von jedermann benutzt werden diirften. Umschlaggestaltung: design & production GmbH, Heidelberg SPIN 10717065 45/3142SR - 5 4 3 2 1 0 - Gedruckt auf saurefreiem Papier Unseren Familien gewidmet WK,AW Vorwort The Analytical Engine is therefore a machine of the most general nature. Charles Babbage (1864) Der Computer ist eine Universalmaschine zur Informationsverarbeitung, und die Informatik (Computer Science) als Wissenschaft der Theorie, Technik und Anwen dung von Computern ist eine universelle Querschnittswissenschaft wie kaum eine andere. Bereits die Pioniere Babbage (urn 1840) und Turing (urn 1940) hatten er kannt, daB der Computer yom Konzept her Teile der Mathematik revolutionieren bzw. dariiber hinaus als universeller Symbolverarbeiter dienen wiirde. In jiingster Zeit riickt mit dem Internet insbesondere der Computer als universelles Kommu nikationswerkzeug in den Vordergrund. Heute, runde 150 Jahre nach Babbage, ist der Einsatz von Computern nicht mehr auf das klassische Gebiet des technisch wissenschaftlichen Rechnens konzentriert, sondern dringt auf breiter Front in alle Bereiche von Wissenschaft, Wirtschaft und Gesellschaft vor. Die neuen Einsatzge biete, wie z. B. moderne Client-Server-Informationssysteme, verlangen in der Pra xis aber neue Werkzeuge und Methoden, auch wenn die alten rein theoretisch noch geniigen wiirden. Kaum eine andere Wissenschaft befindet sich daher noch so im Umbruch wie die Informatik. Objektorientierte Software-Entwicklung und die Programmiersprache Java sind vielleicht die wichtigsten neuen Hilfsmittel, mit denen man der Herausforderung immer vielseitigerer, vielschichtigerer und vernetzter Software begegnet. Objekt orientierte Methoden haben in der Praxis wesentlich dazu beigetragen, den Kom plexitatsschub in Entwurf, Programmierung und Wartung moderner Systeme in den Griff zu bekommen. Java, als Prograrnmiersprache des Internet bekannt gewor den, ist eine moderne objektorientierte Sprache, die sowohl durch klare theoretische Konzepte besticht als auch, insbesondere durch vielerlei standardisierte Schnittstel len von grafischen Oberflachen bis Datenbanken und Netzen, fiir den Einsatz in der breiten Praxis geeignet ist. Der zentrale Beweggrund fiir dieses neue Lehrbuch der Informatik ist das Er reichen einer Balance zwischen Theorie und Praxis, also zwischen theoretisch konzeptuellen Grundlagen und unmittelbar praxisrelevantem Wissen. Dieses Lehr buch solI die traditionellen Konzepte, die in der Einfiihrungsvorlesung Informa tik an Universitaten gelehrt werden, urn den Gesichtspunkt der Objektorientierung erganzen und aus dieser Sicht neu prasentieren sowie anhand von Java einiiben. Der Leser solI insbesondere VIII Vorwort - grundlegende Konzepte der Software-Entwicklung und des Programmierens (ob jektorientiertes Modellieren, Datenstrukturen, Programmierkonstrukte) verste hen, - eine modeme objektorientierte Sprache erlemen, die diese Konzepte umsetzt und auch in der breiten Praxis von Wissenschaft und Wirtschaft in allen Anwendungs gebieten und bei groBen komplexen Aufgaben verwendet wird, - hahere Datenstrukturen, Algorithmen und deren zugrundeliegende Entwurfsmu ster anhand des Standardrepertoires der Informatik kennenlemen und - ein zukunftsfestes Wissen der logischen und mathematischen Grundlagen der praktischen Informatik erwerben, urn eine Basis fiir lebenslanges Lemen zu er halten. Danksagung. Dieses Buch fuBt auf den VOrlesungen Informatik I und II an der Uni versitat Tiibingen in den Jahren 1994/95 (mit C++) und 1997/98 und 1998/99 (mit Java). Wir schulden allen Dank, die am Zustandekommen dieser VOrlesungen in irgendeiner Form mitgewirkt haben, insbesondere natiirlich den Mitarbeitem am Arbeitsbereich Symbolisches Rechnen. Wolfgang Blochinger hat drei Semester lang verantwortlich die Ubungen orga nisiert, die ein wichtiger Bestandteil der Vorlesungen waren; ein Teil seiner Auf gaben ist auch in dieses Buch eingefiossen. Beitrage fiir die Ubungen kamen auch von Dr. Jens Hahn und Stefan Miiller sowie von studentischen Tutoren, insbeson dere von Christoph Ludwig. Ideen fiir einige der Ubungen gehen noch auf die C++ basierte VOrlesung des Jahres 1994/95 zuriick, deren Ubungen zu graBeren Teilen von Frau Dr. Beatrice Amrhein erstellt wurden. Sie iiberarbeitete auch ein Skriptum fiir die C++-Vorlesung, das fiir die Erstellung eines ersten Vorlesungsskriptums fur die jetzt mit Java gehaltenen Vorlesungen sehr niitzlich war. Kapitel 9 beruht zu wesentlichen Teilen auf Vorlagen von Dr. Jens Hahn, die er uns freundlicherweise zur Verfiigung gestellt hat und die fiir uns sehr wertvoll waren. GroBe Teile des Manuskripts wurden von Herm O. Bausinger, Frau M. Quen zer, Frau M. Ludwig und Herrn C. Pomm erfaBt. Herr Bausinger iiberarbeitete und testete dariiber hinaus einige der Programme. Fiir sein Engagement bei all diesen Arbeiten, die uns sehr geholfen haben, sei ihm herzlich gedankt. Fiir viele Korrekturen und niitzliche Anregungen machten wir Herm Prof. Dr. U. Giintzer und Herm Prof. Dr. M. Kaufmann herzlich danken, die mit erheblichem Zeitaufwand eine Vorversion des Manuskripts durchgesehen haben. Teile des Ma nuskripts wurden femer von Dieter Biihler, Dr. Georg Hagel, Andreas Kaiser, Dr. Thomas Lumpp, Patrick Maier, Gerd Nusser, Ralf-Dieter Schimkat, Carsten Sinz und Dr. Andreas Speck korrekturgelesen. Viele Fehler konnnten durch ihre Hilfe gefunden werden. Fiir aIle verbliebenen Fehler und Ungereimtheiten tragen wir aber natiirlich allein die Verantwortung. Nicht zuletzt machten wir Herm Dr. Hans Wossner vom Springer-Verlag fiir die gute und hilfreiche Zusammenarbeit danken. Tiibingen, Darmstadt, August 2000 W. Kiichlin, A. Weber Inhaltsverzeichnis 1. Einfiihrung und Uberblick ................................... . 1.1 Bedeutung und Grundprobleme der Informatik . . . . . . . . . . . . . . . . . . 1 1.1.1 Die Bedeutung des Berechnens von Funktionen . . . . . . . . . . . 2 1.1.2 Das Problem der Komplexitat . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Konzeption des Buches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Objektorientierung und Java. . . ..... .. . .. . .. .. . . . .. . . .. 5 1.2.2 Aufbau des Buches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.3 Verwendung in der Grundvorlesung Informatik . . . . . . . . . . . 9 1.2.4 Englische Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Teil I. Konzepte der Software-Entwicklung 2. Datenstrukturen.... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 13 2.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 13 2.2 Reihungen (arrays) ......................................... 14 2.3 Verbunde (records, structs). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 14 2.4 Typ-Kombinationen von Reihung und Verbund. . .. . .. .. . . . .. .. .. 16 2.5 Modellierung des Enthaltenseins - Referenzen . . . . . . . . . . . . . . . . .. 16 2.6 Abstrakte Datentypen und Objekte . . . . . . . . . . . . . . . . . . . . . . . . . . .. 18 3. Objektorientierte Software-Entwicklung . . . . . . . . . . . . . . . . . . . . . . .. 21 3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 21 3.2 Objekte, Klassen, abstrakte Datentypen . . . . . . . . . . . . . . . . . . . . . . .. 22 3.3 Objektbeziehungen......................................... 25 3.3.1 InformationsfluB-und Client/Server-Beziehungen ......... 26 3.3.2 EinschluBbeziehungen (has-a) ......................... 29 3.3.3 SUbtyp-bzw. Vererbungsbeziehungen (is-a) ........... '" 31 3.4 Objektorientierte Analyse und Entwurf ........................ 32 3.4.1 Analyse einer Werkstiick-Vereinzelungseinheit ........... 33 3.5 Entwurfsmuster............................................ 38 X Inhaltsverzeichnis 3.5.1 Beispiel: Architekturmuster einer Geratefernsteuerung . . . .. 38 3.6 Ubungen.................................................. 42 4. Algorithmen und algorithmische Sprachkonzepte ................ 43 4.1 Einleitung und Begriffsdefinition ............................. 43 4.2 Beispiel: Berechnung der modulus-Funktion . . . . . . . . . . . . . . . . . . .. 46 4.2.1 Der rekursive Ansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 46 4.2.2 Ein rekursives Verfahren in mathematischer Notation . . . . .. 46 4.2.3 Ein rekursives Verfahren in Java ....................... 48 4.2.4 Der strukturiert-iterative Ansatz . . . . . . . . . . . . . . . . . . . . . . .. 49 4.2.5 Ein strukturiert-iteratives Verfahren in Java. . . . . . . . . . . . .. 49 4.3 Algorithmische Notation und abstrakte Sprachkonzepte .......... 51 4.3.1 Abstrakte Beschreibung von Algorithmen. . . . . . . . . . . . . . .. 52 4.3.2 Programmiersprachliche Grundkonzepte zur Beschreibung von Algorithmen. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 54 4.4 Ubungen.................................................. 60 Teil II. Sprachkonzepte und ihre Verwirklichung in Java 5. Grundlagen der Rechnerarchitektur und elementare Datentypen . .. 63 5.1 Speicheraufbau............................................ 64 5.2 Binare Reprasentation ganzer Zahlen . . . . . . . . . . . . . . . . . . . . . . . . .. 65 5.2.1 Reprasentation von Bitrnustern. . . . . . . . . . . . . . . . . . . . . . . .. 68 5.3 Binare Reprasentation von Zeichen. . . . . . . . . . . . . . . . . . . . . . . . . . .. 68 5.3.1 Der ASCII-Zeichensatz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 68 5.4 Gleitkommazahlen......................................... 70 5.5 Arithmetik in Java. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 71 5.5.1 Ganzzahl-Arithmetik ................................. 71 5.5.2 Gleitkomma-Arithmetik.............................. 72 5.6 Ubungen .................................................. 73 6. Grundkonzepte von Programmiersprachen. . . . . . . . . . . . . . . . . . . . .. 77 6.1 Einleitung und Ubersicht ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 77 6.2 Programmentwicklung in Java. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 79 6.2.1 Die Struktur von Java. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 79 6.2.2 Ein Rahmenprogramm fur Java-Anweisungen . . . . . . . . . . .. 80 6.3 Elementare Datentypen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 82 6.4 Variablen, Referenzen, Zuweisungen .......... . . . . . . . . . . . . . . .. 83 6.4.1 Reihungsvariablen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 85 6.5 Operatoren und Ausdriicke. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 86 6.5.1 Zuweisungsoperatoren................................ 86 Inhaltsverzeichnis XI 6.5.2 Arithmetische Operatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 87 6.5.3 Boolesche Operatoren .............. . . . . . . . . . . . . . . . . .. 87 6.5.4 Bitmuster........................................... 89 6.5.5 Ausdriicke.......................................... 90 6.5.6 Syntax von Ausdriicken ............................... ·91 6.5.7 Prazedenz von Operatoren. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 91 6.5.8 Semantik von Ausdriicken . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 92 6.5.9 Bedingte Ausdriicke. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 94 6.5.10 Typkonversionen ..................................... 95 6.6 Anweisungen.............................................. 98 6.6.1 B16cke, Giiltigkeitsbereich und Lebensdauer ............. 99 6.6.2 Bedingte Anweisungen (i fund swi tch) ............... 102 6.6.3 Schleifenkonstrukte (while, do-while, for) .......... 105 6.6.4 Marken, break und continue ....................... 108 6.7 Unterprogramme - Prozedoren und Funktionen ................. 110 6.7.1 Konzepte und Terminologie ........................... 11 0 6.7.2 Unterprogramme in Java .............................. 114 6.7.3 Parameteriibergabe und Laufzeitstapel. .................. 116 6.7.4 Spezifikation von Unterprogrammen .................... 124 6.7.5 Rekursion .......................................... 128 6.7.6 Allgemeine Rekorsion und Speicherverwaltung ........... 131 6.8 Ubungen .................................................. 134 7. Klassen nnd hohere Datentypen ............................... 137 7.1 Einfiihrung und Uberblick ................................... 137 7.2 Objekte, Felder und Methoden ................................ 138 7.2.1 Uberladen von Methoden ............................. 141 7.2.2 Klassenvariablen und Klassenmethoden ................. 142 7.2.3 Pakete (packages) .................................... 143 7.2.4 Kapselung und Zugriffskontrolle ....................... 144 7.2.5 Kontrakt und Aufrufschnittstelle ....................... 145 7.2.6 Verwaltung von Objekten im Speicher ................... 146 7.2.7 Initialisierung und Konstruktoren ....................... 149 7.2.8 Selektoren .......................................... 151 7.2.9 Beispiel eines Datentyps: komplexe Zahlen .............. 154 7.3 Objekte fiir Ausnahmen (exceptions) .......................... 156 7.3.1 Einleitung und Uberblick .............................. 156 7.3.2 Ausnahmeklassen .................................... 158 7.3.3 Die throw-Anweisung ............................... 160 7.3.4 Der Rahmen try-catch-finally ................... 161 7.3.5 Deklaration von Ausnahmen mit throws ............... 162