Zusammenfassung mit weiteren ausführlichen Beispielen PDF

Preview

Summary

Download Zusammenfassung mit weiteren ausführlichen Beispielen PDF

Description

Inhalt

Datentypen............................................................................................................................................3 Allgemeines zu Algorithmen..................................................................................................................5 Vererbung..............................................................................................................................................6 Statischer vs. Dynamischer Typ..........................................................................................................6 Überladen vs. Überschreiben.............................................................................................................7 Verdeckung von Variablen..............................................................................................................8 Statische vs. Dynamische Bindung......................................................................................................9 Geheimnisprinzip..........................................................................................................................10 Sichtbarkeiten......................................................................................................................................11 Abstrakte Klassen................................................................................................................................12 Abstract vs. Interfaces......................................................................................................................12 StringBuilder.....................................................................................................................................14 Exceptiones..........................................................................................................................................14 Fehlertypen und allgemeine Definition............................................................................................14 Fehlerbehandlung............................................................................................................................16 Ausnahme bei Runtime-Exceptions – Unchecked Exceptions...........................................................16 Klasse Error: StackOverflowError, OutOfMemorError......................................................................17 Sortieralgorithmen..............................................................................................................................18 Lineare Suche...................................................................................................................................18 Optimierung lineare Suche durch sortiertes Feld............................................................................18 Suche Teilfolge..............................................................................................................................19 Bubblesort........................................................................................................................................20 Sortieren durch Auswählen (Selectionsort)......................................................................................23 Binäre Suche.....................................................................................................................................24 Quicksort..........................................................................................................................................25 Def. Interpolarsuche.....................................................................................................................27 Sortieren durch Verschmelzen/Merge sort.......................................................................................29 Vergleich der Sortieralgorithmen anhand der Laufzeit.....................................................................32 Vergleiche der verschiedenen Sortier-Algorithmen:.....................................................................34 Rekursion..........................................................................................................................................35 Def. Konvergenz der Rekursion.........................................................................................................35 Def. StackOverflowError...............................................................................................................36 Dynamische Programmierung..........................................................................................................36 Def. Momisation...........................................................................................................................36 Def. Optimale Teilstruktur.............................................................................................................36 1

Überlappende Teilprobleme.........................................................................................................39 Verkettete Listen: LinkedList.............................................................................................................40 Mergesort als LinkedList:..................................................................................................................41 Graphen................................................................................................................................................42 Def. Label......................................................................................................................................42 Def. Pfad.......................................................................................................................................42 Def. Zyklus.....................................................................................................................................42 Def. Folge von Kanten...................................................................................................................42 Def. Gerichteter, azyklischer Graph...............................................................................................42 Def. Zusammenhängender Graph.................................................................................................42 Bäume..................................................................................................................................................45 Def. Baum.....................................................................................................................................45 Def. Wurzel...................................................................................................................................45 Def. Vorgängerknoten/Nachfolgerknoten.....................................................................................45 Typen von Bäumen...........................................................................................................................45 Durchlaufstrategien..........................................................................................................................46 Binäre Bäume...................................................................................................................................47 Def. Suchbaum..............................................................................................................................47 Suche in Graphen.................................................................................................................................48 Breitensuche.....................................................................................................................................48 Tiefensuche......................................................................................................................................49 Beispiel.........................................................................................................................................50 Generische Typen.................................................................................................................................52 Dokumentation JavaDoc.......................................................................................................................53

2

KE1           

In der Welt der objektorientierten Programmierung werden konkrete und abstrakte Gegenstände durch Objekte modelliert. Alle Objekte sind Exemplare einer Klasse. Die Klasse definiert die Eigenschaften und Fähigkeiten jedes Objekts dieser Klasse. Die Eigenschaften werden durch eine Menge von Attributen in der Klassendefinition bestimmt. Die jeweiligen Attributwerte der Attribute eines Objekts bestimmen seinen inneren Zustand. Die Fähigkeiten oder das Verhalten aller Objekte der Klasse werden durch die Methoden bestimmt. Die Beziehungen zwischen Klassen werden mit Hilfe von Assoziationen und Multiplizitäten modelliert. Eine Klasse kann die Spezialisierung einer oder mehrerer anderen Klasse sein und somit deren Eigenschaften und Verhalten erben. Mit Hilfe von UML-Anwendungsfalldiagrammen werden das System selbst, Akteure, Anwendungsfälle und die Beziehungen zwischen diesen Elementen dargestellt. Laufzeitfehler tauchen während des Programmdurchlaufs auf. Ein typisches Beispiel für einen solchen Fehler ist eine Division durch Null. Übersetzungsfehler sind syntaktische Fehler, z.B. Semikolon fehlt. Fehler wegen Überlauf: Wert war außerhalb des Wertebereichs des Datentyps

Datentypen Ein Datentyp ist eine Menge von Werten und eine Menge von Operatoren, um diese Werte zu verknüpfen, zu vergleichen oder ineinander zu überführen.

Literale sind Folgen von Zeichen/Strings, die durch „…“ gekennzeichnet sind. Literale stellen Konstanten dar, da ihr Wert festgelegt ist und sich während der Ausführung eines Programms nicht verändert. Der Wert einer finalen Variablen kann, nachdem ihr zum ersten Mal ein Wert zugewiesen wurde, nicht mehr verändert werden. Um eine Variable als finale Variable zu deklarieren, final wird das Schlüsselwort final dem Variablentyp vorangestellt.

3

A) Wenn wir alle && durch & ersetzen, gibt es Eingaben, für die eine andere Ausgabe herauskommt. False B) Wenn wir alle || durch | ersetzen, gibt es Eingaben, für die eine andere Ausgabe herauskommt. false  saved einem nur Laufzeit, wenn nicht alles überprüft wird  „Lazy evaluation“: bei && wird nur das ausgerechnet, was notwendig ist  Wenn eine Seite schon zu false evaluiert, kann das alles ja nicht mehr true werden  beim doppelten && wird dann nicht mehr weiter gerechnet  Beim bitweisen & wird alles weiterhin berechnet Unterschied & und &&: Bei Verwendung des && Operators, wird sofort nach der ersten fehlerhaften Bedingung abgebrochen. Für die Performance ist dies optimal. Jedoch könnte es sein, dass sich in der Funktion B Programmcode befindet, der trotzdem auf jeden Fall ausgeführt werden soll, genauso wie in der Funktion A. Hier würde man den einfach & Operator verwenden.

4

Ein Ausdruck ist eine Folge von Variablen, Operatoren, Klammern und Literalen, die zu einem einzelnen Wert ausgewertet werden kann. Variablen eines primitiven Typs werden Wertvariablen genannt, Variablen eines Objekttyps werden Verweisvariablen genannt.

Schlüsselwort static:    

Attribute und Methoden können durch das Schlüsselwort static als Klassenattributen bzw. -methoden gekennzeichnet werden. existieren nur für die Klasse und sind unabhängig von Exemplaren der Klasse können nicht auf Exemplarvariablen und -methoden (alles was nicht static ist) zugreifen In Klassenmethoden ist keine this-Referenz verfügbar

Allgemeines zu Algorithmen Robustheit: Unter Robustheit verstehen wir die Eigenschaft eines Algorithmus, auch in ungewöhnlichen Situationen definiert zu arbeiten, d. h. fehlerhafte und widersprüchliche Eingabedaten abzuweisen und auch umfangreiche Eingabedaten abzuhandeln. Anpassbarkeit: Anpassbarkeit ist ein Maß für den Aufwand, mit dem ein Algorithmus an eine geänderte Spezifikation angepasst werden kann. Wiederverwendbarkeit: Die Wiederverwendbarkeit drückt aus, wie einfach ein Algorithmus in vielen verschiedenen Anwendungen ohne Änderung benutzt werden kann. Terminierung: Das Verfahren kommt in endlich vielen Schritten zu einem Ende. Finitheit der Beschreibung: Das Verfahren muss in einem endlichen Text vollständig beschrieben sein. Die elementaren Bestandteile der Beschreibung nennen wir Schritte. Effektivität: Jeder einzelne Schritt des Verfahrens muss tatsächlich ausführbarsein. Determiniertheit: Ein Algorithmus heißt determiniert, wenn er mit den gleichen Parametern und Startbedingungen stets das gleiche Ergebnis liefert. Determinismus: Der Ablauf des Verfahrens ist zu jedem Punkt fest vorgeschrieben. Korrektheit: Ein Algorithmus ist korrekt, wenn er sich bei der Ausführung so verhält, wie wir dies bei der Formulierung beabsichtigten. Korrektheit ist ein relativer Begriff, weil Korrektheit immer nur in Bezug auf eine explizite Vorgabe objektiv überprüft werden kann. Im Allgemeinen kann man mit Tests jedoch nur die Anwesenheit von Fehlern, nicht aber deren Abwesenheit nachweisen.

5

Vererbung Substitutionsprinzip Vererbung bedeutet, dass jedes Objekt der Unterklasse auch eines der Oberklasse ist. Ein Objekt der Unterklasse kann somit überall verwendet werden, wo ein Objekt der Oberklasse erwartet wird. Diesen Umstand nennen wir Substitutionsprinzip. Objekte der Unterklasse substituieren Substitutionsprinzip Objekte der Oberklasse. Bsp: Artikel a = new Pflanze();  a greift auf Attribute von Artikel zu  a kann dann auf Methoden der Klasse Pflanze zugreifen, wenn diese auch in Artikel existieren -> sonst kein Zugriff bzw. Cast notwendig o ((Pflanze) a).liefereLagertemp(); o ansonsten ClassCastException Fehler  Zugriffsreihenfolge: Pflanze -> Artikel 

Jede Klasse hat eine Oberklasse, auch wenn nicht explizit angegeben. Die Oberklasse ALLER Klassen heißt „Object“. Wenn eine Klassendefinition keinen extends-Ausdruck enthält, fügt der Java-Übersetzer implizit den extendsAusdruck für die Klasse Object hinzu.

Methoden der Klasse Object:

Laufzeitfehler: Eine explizite Typumwandlung (A) x ist genau dann möglich, wenn der Typ des Objekts, auf das x verweist, mit A verträglich ist. Andernfalls wird zur Laufzeit eine ClassCastException auftreten. -> kann ein Übersetzungsfehler auftreten, wenn es zwischen den Typen auf Grund der Typhierarchie auf keinen Fall eine Subtypbeziehung geben kann. Statischer vs. Dynamischer Typ Statischer Typ einer Verweisvariablen Der statische Typ einer Verweisvariablen ist immer der Typ, der bei der Deklaration vereinbart wurde. Er kann sich nicht im Laufe eines Programms verändern. z.B. Artikel a; Dynamischer Typ einer Verweisvariablen Unter dem dynamischen Typ einer Verweisvariablen verstehen wir den Typ des Objekts, auf das die Variable zu diesem Zeitpunkt verweist. Da eine Verweisvariable im Laufe eines Programms auf verschiedene Objekte verweisen kann, kann sich auch der dynamische Typ ändern. Der dynamische Typ ist immer ein Subtyp des statischen Typs. Z.B. Artikel a = new Pflanze();

6

Bei Methoden: Z.B. public long legeFest(); return new Pflanze(); statisch, dynamisch

z.B. Pflanze ist Subtyp von Artikel Artikel a = new Pflanze(); -> Artikel = statischer Typ; Pflanze = dynamischer Typ!

Überladen vs. Überschreiben Überladen von Methodennamen, wo mehrere Methoden mit dem gleichen Namen, aber verschiedenen Signaturen implementiert, z.B. int a(String name) und int a(double x) 

gleicher Namen, aber verschiedene Parametertypen

Fehlerquellen beim Überschreiben von Methoden

Merke: Überschreiben von Methoden oder weitere Vererbung kann immer mit dem Zusatz „Final“ in der Signatur verhindert werden. Finale Klasse: Von dieser Klasse kann keine Unterklasse erstellt werden.

7

Verdeckung von Variablen Wenn in einer Methode eine lokale Variable den gleichen Namen wie ein Attribut trägt, so akzeptiert der Übersetzer dies, allerdings wird das Attribut innerhalb dieser Methode von der lokalen Variable verdeckt. Mit Hilfe von this kann immer auf das Attribut zugegriffen werden.



Ohne „This“ wird nur lokale Variable beachtet

Polymorphie: Die Eigenschaft, dass der formal gleiche Aufruf einer Methode unterschiedliche Reaktionen (je nach adressiertem Objekt) auslösen kann, wird als Polymorphie (Vielgestaltigkeit) bezeichnet.

8

Statische vs. Dynamische Bindung

Durchlauf von Methoden am Bsp Pflanze, Artikel Wie durchläuft Compiler die Methoden?

   

Wenn in Klasse Pflanze Methode vorhanden, verwende diese Methode Falls nicht, suche in Klasse Artikel und verwende diese Methode Entspricht „Suche während der Laufzeit“ Man kann auch zuvor bereits festlegen, welche Methode immer verwendet werden soll -> Klassenmethoden. Hier spricht man von statischer Bindung. Klassenmethoden können nicht überschrieben werden.

9

Beispiel Statischer Bindung

-> A ab = new B(); -> Verwende Attribute von Klasse A, Methoden von Klasse B WENN diese auch in A existieren -> Sonst Methode von Klasse B nicht sichtbar -> Cast!! -> Funktioniert nur, wenn B Subtyp von A -> ansonsten CastClassfehler 

Eigenschaften sind statisch gebunden, d.h. Eigenschaften kommen vom statischen Typ, Methoden jedoch vom dynamischen.

Merke: Besitzt die direkte Oberklasse einen Standardkonstruktor und die erste Anweisung im Konstruktor der Unterklasse ist kein this()- oder super()-Aufruf, so wird implizit ein super()-Aufruf für den Standardkonstruktor eingefügt.

Geheimnisprinzip Für die Verwendung eines Programms bzw. einer Klasse muss lediglich bekannt sein, was für eine Funktionalität geboten wird, aber nicht wie genau sie umgesetzt ist. Dieses Konzept nennen wir auch Geheimnisprinzip, da die genaue Implementierung für Außenstehende ein Geheimnis ist.

10

Sichtbarkeiten

   

Public int a: Nicht sicherbar in M, N, da Classe K nicht public, sondern protected.-> Variablen in K sind nur in Klassen innerhalb des Paketes a sichtbar. Protected Class K kann außerhalb des eigenen Paketes nicht vererben. Wenn nicht explizit „Public“ -> Protected -> „Protected Class…“ gibt es nämlich so nicht Protected: Sichtbar im eigenen Paket und in abgeleiteten Klassen

Merke: Geschützte Klassenelemente Ein Klassenelement, das als protected deklariert ist, ist innerhalb des Paketes der Klasse sichtbar. Eine Unterklasse U hat auch außerhalb des Pakets der Oberklasse O Zugriff auf dieses Element. Dazu muss jedoch O als public deklariert sein, und der Zugriff muss an einem Element vom Typ U oder einem Subtyp von U ausgeführt werden. Prüfkette: 1. Sichtbarkeit Klasse -> 2. Sichtbarkeit Variable Zugriff beim Überschreiben von Methoden Beim Überschreiben von Methoden darf der Zugriff in der Unterklasse höchstens erweitert, aber niemals eingeschränkt werden. d. h. der Zugriffsmodifikator der Methode in der Unterklasse muss größer oder gleich dem der Oberklasse sein: public > protected > Standardzugriff> private

11

Abstrakte Klassen  Sinnvoll, um bestimmte Methoden und Attribute vorzugeben. Diese müssen dann in abgeleiteten Klassen initialisiert werden.  In der abstrakten Klasse selbst, brauchen Methoden keinen Rumpf, da diese erst in der vererbten Klasse implementiert werden. Bsp.: public static essen(String lebensmittel); -



kann so ohne weitere Funktion implementiert werden. Die abgeleitete Klasse muss diese dann definieren, bsp: public class essen (String lebensmittel){ lieblingsessen = lebensmittel; } Wenn eine Klasse, eine öffentliche abstrakte Methode beinhaltet, so muss sie selbst abstrakt sein (protected Methoden funktionieren auch nicht abstrakt)

Einschränkungen:

-

Methode kann nicht static und abstract sein Wenn eine oder mehrere abstrakte Methoden der abstrakten Oberklasse in der Unterklasse nicht implement...