Die Überschriften a) und b) verweisen auf die vorhergehenden Seiten, d) bis h) auf die nachfolgende Seite.| www.r-krell.de |
| Webangebot für Schule und Unterricht, Software, Fotovoltaik und mehr |
Willkommen/Übersicht > Informatik > Informatik-Seite c)
Teil c) Sortieren und Suchen
sowie Programmieren mit der Java-AWT
Die Überschriften a) und b) verweisen auf die vorhergehenden Seiten, d) bis h) auf die nachfolgende Seite.
a) Grundlegendes zu Java, benötigte Software (inkl. Downloadadressen) und Installation
b) Programmieren mit Java - erste Programme, Kontrollstrukturen, Autorennen, Aufzug, Objekte
sowie Verweise auf fremde Java-Seiten
c) Sortieren und Suchen in Java; GUI-Oberfläche mit der Java-AWT
d) Adressbuch- bzw. Fuhrpark-Verwaltung mit Java; Dateioperationen
e) Lineare Abstrakte Datentypen (Keller, Schlangen, Listen) und einige Anwendungen (z.B. Tiefen- und Breitensuche im Labyrinth)
f) Abstrakter Datentyp Baum ([binärer] Sortierbaum, Rechenbaum, Spielbaum)
g) Abstrakter Datentyp Graph (Adjazenzmatrix u. -listen, typische Fragestellungen, Tiefen- u. Breitensuche)
h) Bau eines Compilers Java -> 1_AMOR (Syntaxdiagramm, Scanner, Parser, Variablentabelle, Codeerzeuger)
Eine vollständige Übersicht aller Java-Seiten gibt's auf der Informatik-Hauptseite!
zum Seitenanfang / zum Seitenende
Voraussetzungen und neue Überlegungen
Im Folgenden wird davon ausgegangen, dass Sie wie in Teil a) beschrieben, die JDK >= 1.1.8 und einen Editor (z.B. den „Java-Editor" oder „RealJ") sowie die Bibliothek „Stift&Co" installiert haben und über erste Programmiererfahrung in Java verfügen, wie sie etwa im Teil b) meiner Java-Seiten beschrieben werden. Außerdem sollten Sie bereits wissen, was eine Reihung ist. Denn diese Zusammenfassung gleichartiger Komponenten zu einer Variable, wobei der Zugriff auf einzelne Komponenten über den in eckigen Klammern angegebenen numerischen Index erfolgt, ist die Grundstruktur, in der im Folgenden sortiert und gesucht wird. [Im Hochhaus und beim Aufzug auf der Java-Seite b) kamen bereits Reihungen vor!]
Dann können Sie sich dem Sortieren und Suchen zuwenden, und allgemeine Strategien der Informatik kennen lernen. Natürlich lernt man bei der Realisierung der Algorithmen auch die Umsetzung in die Programmiersprache und sprachspezifische Eigenheiten von Java kennen, so dass hier Informatik und Programmiertechnik nebeneinander weiter entwickelt werden. Da „Stift & Co" in der älteren, bisher im Unterricht verwendeten Form keine eigenen Eingabefelder bereit stellte, wird hier auch die Java-AWT-Bilbliothek eingesetzt und deren Möglichkeiten besprochen (Die jetzt in Knopf&Co realisierten Eingabefelder und Schaltflächen begeistern mich allerdings auch nicht. Insbesondere stört, dass die Schaltflächen regelmäßig abgefragt werden müssen. Da ist mir das Ereignis-Modell der Java-AWT doch lieber).
Wesentliche Teile der nachfolgenden Darstellung habe ich bereits 2001 bei meinem ersten Informatikkurs mit Java geschrieben. Jetzt, beim zweiten und dritten Durchgang, habe ich einiges anders gemacht. Insbesondere überlege ich, ob es sinnvoll ist, weiterhin wie hier mit dem Sortieren und Suchen ganzer Zahlen anzufangen. Wenn man direkt Reihungen beliebiger Objekte nimmt (also wirklich Object[] reihung und erst bei Bedarf die Komponenten durch Type-Casting spezialisiert) wird der Objektgedanke deutlicher. Außerdem wird direkt klar, dass man die Vergleiche zum Sortieren nicht einfach wie unten mit if (reihung[stelle] > reihung[stelle+1]) machen kann, sondern dafür spezielle Objekt-Methoden braucht, die auch die Auswahl verschiedener Sortierkriterien zu lassen. Mehr darüber später auf der „Informatik mit Java"-Seite d)!
zum Seitenanfang / zum Seitenende
Hier geht es um Standardverfahren der Informatik. Ausgehend vom manuellen
Sortieren von Karteikarten, Spielkarten oder CDs in ein CD-Regal (wobei das
Regal eine gute Repräsentation einer Reihung ist) wurden im Unterricht die
üblichen Verfahren gefunden und zunächst umgangssprachlich beschrieben. Die
Algorithmen lassen sich jeweils durch schrittweise Verfeinerung und nach
Zeichnen eines Struktogramms schließlich in Java-Methoden umsetzen. Die von
verschiedenen Schüler-Gruppen gefunden und implementierten unterschiedlichen
Algorithmen fordern einen Vergleich heraus, der über Zeitmessungen oder den
Einbau von Zählern (z.B. für Vergleiche und/oder für Kopieren von
Reihungskomponenten) in theoretische Überlegung zur Aufwandsabschätzung
mündet.
In den nachfolgend abrufbaren Java-Quelltexten sind jeweils fünf einfache Sortierverfahren und zusätzlich das Bucket-Sort-Verfahren in einem geeigneten Testrahmen dargestellt. In der ersten Datei wurde die „Stift&Co"-Bibliothek verwendet. Auf Schülerwunsch, endlich mal 'richtiges Java' zu machen, wurden dann auch Fassungen ohne diese Bibliothek erstellt. Natürlich ändern sich dadurch die Sortier-Algorithmen nicht: Lediglich Ein- und Ausgabe müssen neu geschrieben werden bzw. der Zufallszahl-Generator zur anfänglichen Füllung der Ganzzahlen-Reihung wird durch eine andere Version ersetzt.
Die Benutzung der zeichenorientierten Konsolen-Oberfläche (Dos-Box) ist beim Verzicht auf „Stift&Co" leicht zu programmieren, aber wegen des kargen Aussehens optisch
unbefriedigend. Deshalb sollte eine grafische Oberfläche benutzt werden (siehe Bildschirmausdruck unten). Da inzwischen gesehen wurde, dass nur die Ein-/Ausgabeteile
verändert werden mussten, liegt eine Aufteilung des Programms in die oberflächenunabhängigen Methoden in einer Klasse und in eine zweite, kommunikative Klasse nahe, die
in der dritten Fassung dann auch realisiert wurde. Natürlich wären auch schon die früheren Versionen besser mit dieser Trennung geschrieben worden - aber mangels
entsprechender Erfahrung der Schülerinnen und Schüler wäre eine solche Trennung anfangs künstlich (bzw. lehrergewollt) erschienen. Jetzt ist sie motiviert.
Java-Quelltext; Sortierverfahren mit Stift&Co (pdf-Datei, 63 kB)
Java-Quelltext, Sortieren ohne Stift&Co, zeichenorientiert (pdf-Datei, 64 kB)
Java-Quelltext, Sortieren ohne Stift&Co, graf. Oberfläche (pdf-Datei, 91 kB inkl. Bild)
zum Seitenanfang / zum Seitenende
Allgemeines zum Suchen
Sind die Daten oder Zahlen ungeordnet - man stelle sich nur ein zufällig zusammen gemischtes Telefonbuch vor, wo die Namen nicht dem Alphabet folgen - muss man im schlimmsten Fall das ganze Buch von Anfang bis Ende Namen für Namen durchlesen, um eine gesuchte Person zu finden. Bei 200000 Einträgen bedeutet das bis zu 200000 Lesezugriffe und Vergleiche mit dem gesuchten Namen. Natürlich kann man Glück haben und findet den Namen schon früh. Aber genauso wahrscheinlich ist das Pech, dass der Namen erst weit hinten steht. Im statistischen Mittel muss man mit 100000 Vergleichen rechnen, wenn der Name tatsächlich im Telefonbuch steht. Ob ein Name fehlt, kann man hingegen erst am Ende nach 200000 Vergleichen sicher wissen.
Gleiches gilt für Reihungen mit ganzen Zahlen, die hier die Rolle des Telefonbuchs übernehmen: In ungeordneten Reihen kann eine vorhandene Zahl nach durchschnittlich 0.5*reihung.length Vergleichen gefunden werden; eine nicht vorhandene Zahl zwingt immer zum vollständigen Durchsuchen der Reihung mit reihung.length Vergleichen.
Geordnete Telefonbücher und Zahlenreihen erleichtern hingegen die Suche (und deswegen treibt man den oben beschriebenen Sortieraufwand
überhaupt): Selbst wenn man weiterhin von vorne an jeden Namen liest, weiß man spätestens bei 'Mozilla', dass der gesuchte 'Mozart' keinen Eintrag
mehr im Telefonbuch besitzt. Also auch bei der Suche nach nicht vorhandenen Elementen braucht die durchschnittliche Suche nur noch
0.5*reihung.length Vergleiche, was immerhin einer Reduzierung auf die Hälfte entspricht. Bei vorhandenen Namen hat man aber mit der
einfachen sequentiellen Suche keinen Vorteil.
Wie wir alle wissen, kann man aber viel geschickter suchen: selbst wenn man das Telefonbuch aufs Gratewohl irgendwo auf schlägt, sieht man sofort, ob der gesuchte Name weiter vorne oder weiter hinten stehen muss. Wenn man jetzt zunehmend kleinere Seitenpäckchen umblättert, kommt man rasch zum gesuchten Namen - hier reichen log2 (reihung.length) Vergleiche, d.h. im Telefonbuch mit 200000 Einträgen kommt man spätestens nach log2(200000) = 18 Vergleichen (aufgerundet) zum Ergebnis - entweder dem Auffinden des gesuchten Namens oder der Gewissheit, dass der gesuchte Name nicht vorhanden ist. Achtzehn Schritte statt zweihunderttausend - das ist eine ganz erhebliche Ersparnis!
Das Übungsblatt zum Thema kann durch Anklicken lesbarer vergrößert oder (viel besser) hier als pdf-Datei (14 kB) abgerufen werden!
Allerdings stellte sich im Unterricht heraus, dass das in Aufgabe 2b) vorgeschlagene Vorgehen mit fortgesetztem Halbieren der Sprungweite wegen der Kumulierung von
Rundungsfehlern (Halbe werden immer wieder abgerundet) ungeschickt ist: Ein Halbieren des jeweils tatsächlich übrig bleibenden Bereichs erwies sich als günstiger!
Umfangreiche Untersuchungen und Bleistifttest führten schließlich zu einem brauchbaren Algorithmus, der weiter unten auf dieser Seite (nämlich im übernächsten Abschnitt)
vorgestellt wird.
zum Seitenanfang / zum Seitenende
Frame, Label, Button, Textfeld und -area:
Ein- und Ausgabe-Elemente der Java-AWT
Parallel zur Entwicklung des Suchprogramms wurde die Frage lauter, wie man statt des festen Einbaus der Suchzahl in den
Programmtext eine Eingabe während der Laufzeit hinkriegt. Nun ist in Java zwar noch eine zeichenorientierte Eingabe über
die Konsole, Kommandozeile bzw. Dos-Box möglich (siehe oben, zweite Version des Sortierprogramms). Angestrebt wurde
aber eine moderne Oberfläche. Java bietet mit seiner AWT-Bibliothek (AWT = Advanced Windows Toolkit) sowie mit der
hier nicht verwendeten, noch umfangreicheren Swing-Bibliothek alle Elemente moderner, grafikorientierter Oberflächen
(GUI = graphic user interface).
Klassen, die einen Grafikbildschirm verwenden wollen, müssen von der Klasse Frame abgeleitet werden. Beim Bildschirm
funktioniert dann aber der Schließknopf noch nicht - die entsprechende Methode muss noch vom Programmierer gefüllt
werden. Schaltflächen und Eingabefeldern müssen noch ActionListener mitgegeben werden, die auf die Bedienung des
Knopfes oder auf den Eingabe-Abschluss warten. Eigene ActionPerformed-Methoden reagieren dann, wenn eine solche
Aktion entdeckt wurde, mit individuell programmierten Befehlen bzw. Methoden-Aufrufen. Nachfolgender Java-Text stellt einige Möglichkeiten vor
(Betrachtung als pdf-Dokument bzw. Download [mit rechter Maustaste klicken und „Ziel speichern unter..": wählen]: javaawtdemo.pdf (25 k) ):
// Demo: Ein-/Ausgabe mit der Java-AWT
// Java jdk 1.1.18 -- R. Krell, www.r-krell.de
import java.awt.*;
import java.awt.event.*;
public class JavaEA extends Frame // Frame ist die Fensterklasse
{
Label ausgabezeile; // Deklaration der Bildschirmobjekte
Button knopf;
TextField eingabezeile;
TextArea mehrzeiligesTextfenster;
int zähler = 0; // für Beispiel: Knopfdrücke werden gezählt
public void richteFensterEin() // Fenster initalisieren und beschreiben
{
//WindowsListener hinzufügen, damit Schließknopf funktioniert
addWindowListener (
new WindowAdapter ()
{
public void windowClosing (WindowEvent ereignis)
{ //ersetzt bisher leere Methode
setVisible (false);
dispose();
System.exit(0);
}
}
); // runde Klammer vom Windowlistener geschlossen;
setTitle("Das hier ist die Überschrift"); // Fenster mit Titel versehen
setSize (420,200); // Fenstergröße (Breite und Höhe in Pixeln) festlegen
setLayout (new FlowLayout()); // innere Unterteilung des Fensters,
// kann auch später in führeAus() vor den add(..)-Befehlen stehen
// ohne besondere Definition ist FlowLayout voreingestellt.
}
public void richteAusgabeEin()
{
ausgabezeile = new Label("------------------------------------");
// Erzeugen des Ausgabelabels; Größe richtet sich nach Text!
}
public void richteKnopfEin()
{
// Knöpfe definieren und beschriften (Größe richtet sich nach Beschriftung)
knopf = new Button ("Knopf-Beschriftung");
// oder: .. = new Button(); knopf.setLabel ("Knopf-Beschriftung")
//Funktion der Knöpfe festlegen
knopf.addActionListener (
new ActionListener ()
{
public void actionPerformed (ActionEvent e)
{
// hier steht der Programmtext, der ausgeführt werden
// soll, wenn der Knopf gedrückt wird. z.B.:
zähler++;
ausgabezeile.setText ("Knopf wurde "+zähler+"x gedrückt");
}
}); // runde Klammer (von addActionListener)
}
public void richteEingabezeileEin ()
{
eingabezeile = new TextField("Hier tippen und <Enter>",30);
// 30 = Breite für 30 Zeichen
// spätere Textänderung mit eingabezeile.setText("Neuer Text");
eingabezeile.addActionListener (
new ActionListener ()
{
public void actionPerformed (ActionEvent e)
{
// hier steht der Programmtext, der nach der Eingabe (wenn die
// <Eingabe>-Taste gedrückt wurde) ausgeführt werden soll, z.B.:
ausgabezeile.setText ("Eingabe '"+eingabezeile.getText()+"'");
// Zahleingaben können wie folgt in Kommazahlen verwandelt werden:
Double hilfszahlobjekt = Double.valueOf (eingabezeile.getText());
double kommazahl = hilfszahlobjekt.doubleValue();
mehrzeiligesTextfenster.append ("Als Dezimalbruch="+kommazahl+"\n");
// oder -- weniger aufwändig (in JDK 1.3 geht's so auch bei Double
// und Float) -- in Ganzzahlen:
int ganzzahl = Integer.parseInt (eingabezeile.getText());
mehrzeiligesTextfenster.append ("Ganze Zahl="+ganzzahl+"\n");
// Falls die Eingabe gelöscht werden soll:
eingabezeile.setText("");
}
}); // runde Klammer (von addActionListener)
}
public void richteTextfensterEin ()
{
mehrzeiligesTextfenster = new TextArea("Zeile1\nZeile2\nZeile3\n",4,30);
// 4 Zeilen hoch, 30 Zeichen breit. (Anfangs-)Text kann auch später eingefügt
// werden mit: mehrzeiligesTextfenster.setText("Zeile1\nZeile2\nZeile3\n");
mehrzeiligesTextfenster.setEditable(false);
// bei true kann der Textfensterinhalt auf dem Bildschirm vom Benutzer verändert
// werden (Normalfall), bei false nicht.
// Üblicherweise kein ActionListener, sondern Button für Aktionen!
}
public void führeAus ()
{
richteFensterEin(); // Aufruf der Methoden zum Erzeugen der
richteKnopfEin(); // Bildschirmobjekte und der Definition
richteAusgabeEin(); // der bei Ereignissen auszuführenden Methoden
richteEingabezeileEin();
richteTextfensterEin();
add (knopf); // Anordnung der Objekte auf dem Bildschirm
add (ausgabezeile); // in der hier gewählten Reihenfolge bzw.
add (eingabezeile); // mit dem hier gültigen Layout-Manager
add (mehrzeiligesTextfenster);
setVisible(true); // Macht Bildschirm mit allen angeordneten
// Objekten sichtbar und startet damit das Programm
}
}
Diese AWT-Demo kann - wie üblich - mit nachfolgender Startdatei als Application gestartet werden:
public class JavaEAStart
{
public static void main (String[] s)
{
JavaEA demo;
demo = new JavaEA();
demo.führeAus();
}
}
zum Seitenanfang / zum Seitenende
Finden in Java
Mit den vorgenannten AWT-Grundkenntnissen und den Überlegungen zum Algorithmus aus dem Unterricht kann jetzt das Suchen (nach dem Halbierungsverfahren, auch binäre Suche genannt) programmiert werden. Die drei Dateien werden auf einer Extra-Seite gezeigt bzw. zum Download angeboten, wo das Suchen auch als Applet ausprobiert werden kann. Die Anordnung der Elemente auf dem Bildschirm ist noch nicht perfekt - Interessenten empfehle ich den GridBagLayout-Manager, der auch pixelgenaue Anordnungen auf dem Bildschirm erlaubt (oder die J*-Komponenten der Swing-Erweiterung, die seit der JDK 1.2 zum Java-Standard-Umfang gehören):
Extra-Seite „Sortieren & Finden" mit funktionsfähigem Applet
zum Seitenanfang / zum Seitenende
Alles dreht sich ums Geld
Natürlich sollen die neu erworbenen AWT-Kenntnisse nicht nur am Beispiel des Suchens mit dem Halbierungsverfahren ausprobiert, sondern auch an einer Reihe kleinerer Beispiel geübt werden. Nachdem inzwischen der Euro vertraut ist, müsste jetzt wohl eher ein Umrechner zwischen Euro und Dollar oder anderen Währungen programmiert werden. Applet (das nebenstehende Bild bietet nur einen statischen Vorgeschmack) und Quelltext finden sich auf einer Extra-Seite:
Extra-Seite „Euro-Umrechner" mit funktionsfähigem Applet
Etwas anspruchsvoller ist ein Automat mit Geldrückgabe, wie er zum Fahrscheinverkauf oder in Parkhäusern zu finden ist: Bezahlt man mehr als den Fahrpreis oder das Parkgeld, so erhält man den überzähligen Betrag in Münzgeld zurück. Hier werden Oberfläche (GUI) und Funktion getrennt; für die Zählwerksfunktion werden sogar vier alternative Möglichkeiten vorgeschlagen, wobei fortlaufend kleinere Verbesserungen vorgenommen wurden - was aber die Oberfläche nicht verändert. Das ist natürlich auch der Sinn modularen Programmierens: Wie bei einer Einbauküche soll z.B. der Austausch des Kühlschranks gegen ein leistungsfähigeres Gerät zu keinerlei zusätzlichen Umbauten führen: Schränke, Herd und Spüle sind gar nicht betroffen und die Küche funktioniert als Ganzes wie gewohnt (nur eben mit besserer Kühlung). Deshalb sind die Einbaugeräte in einer Küche auch genormt und mit wenigen, genau festgelegten Verbindungsstellen (Stecker, Wasseranschlüsse, Türen) versehen, sonst aber voneinander unabhängig. Genau das ist auch beim Programmieren anzustreben und mit getrennten, gut geplanten Klassen bzw. Objekten möglich.
Extra-Seite „Geldautomat" mit funktionsfähigem Applet
Zur Übung: Mit ganz analogen Mitteln wie beim Geldautomat (statt Münzen werden allerdings römische Zahlzeichen wie X, IV oder I ausgegeben) kann die Umwandlung von dezimalen arabischen Zahlen in römische Zahlen bewerkstelligt werden!
zum Seitenanfang / zum Seitenende
Mehr zum Üben?
Alles verstanden? Dann können Sie sich an den Punkten orientieren, die ich meinen Schülerinnen und Schülern zur Klausurvorbereitung genannt habe. Das sollten Sie jetzt können:
· Umgang mit der Java-AWT (mit dem Blatt „Demo: Ein-/Ausgabe mit der Java-AWT" wie oben abgedruckt als erlaubter Hilfe) am Beispiel kleinerer Programme wie etwa dem Euro-Umrechner u.ä.
· Programme mit geschachtelten Schleifen (z.B. Automat mit Geldrückgabe oder römische Zahlen (und zwar Verwandlung arabischer/dezimaler Zahlen in römische -- hierzu mögen die beigefügten vier verscheidenen Dateien der Geldautomaten-Rechnung interessant sein)
· Umgang mit Reihungen (z.B. Hausaufgabe: aus einer Reihung von 90 Zahlen die kleinste/die größte herausfinden und in einer Java-AWT-Oberfläche zeigen)
· Das Halbierungsverfahren als Suchverfahren in einer geordneten Reihung (außer "unserem" Verfahren sollten auch Abwandlungen -- z.B. wie in älterer Hausaufgabe mit <= statt < -- untersucht und ggf. im Bleistifttest untersucht werden)
An neuen Beispielen / Übungen schlage ich vor:
· Aus einer Reihung mit 90 zufälligen Zahlen die größte Differenz zweier aufeinanderfolgender Zahlen zu finden
· als kleines Programm: einen Text einzutippen und (1) die Anzahl der Buchstaben (einschl. Leerzeichen) ausgeben zu lassen -- ganz einfach mit length -- und/oder (2) die Anzahl der 'e' zu zählen (Hinweis: mit For-Schleife und .charAt)
· ein abgewandeltes Halbierungsverfahren auszuprobieren
Viel Erfolg!
zurück zur Informatik-Hauptseite
(Die anderen „Informatik mit Java"-Seiten werden am besten auch dort ausgewählt)