Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Geleitwort des Fachgutachters
Vorwort
1 Einführung
2 Mathematische und technische Grundlagen
3 Hardware
4 Netzwerkgrundlagen
5 Betriebssystemgrundlagen
6 Windows
7 Linux
8 Mac OS X
9 Grundlagen der Programmierung
10 Konzepte der Programmierung
11 Software-Engineering
12 Datenbanken
13 Server für Webanwendungen
14 Weitere Internet-Serverdienste
15 XML
16 Weitere Datei- und Datenformate
17 Webseitenerstellung mit (X)HTML und CSS
18 Webserveranwendungen
19 JavaScript und Ajax
20 Computer- und Netzwerksicherheit
A Glossar
B Zweisprachige Wortliste
C Kommentiertes Literatur- und Linkverzeichnis
Stichwort

Download:
- ZIP, ca. 26,3 MB
Buch bestellen
Ihre Meinung?

Spacer
IT-Handbuch für Fachinformatiker von Sascha Kersken
Der Ausbildungsbegleiter
Buch: IT-Handbuch für Fachinformatiker

IT-Handbuch für Fachinformatiker
Galileo Computing
ca. 1172 S., 5., aktualisierte und erweiterte Auflage, geb.
ca. 34,90 Euro, ISBN 978-3-8362-1744-6
Pfeil 10 Konzepte der Programmierung
Pfeil 10.1 Algorithmen und Datenstrukturen
Pfeil 10.1.1 Ein einfaches Praxisbeispiel
Pfeil 10.1.2 Sortier-Algorithmen
Pfeil 10.1.3 Such-Algorithmen
Pfeil 10.1.4 Ausgewählte Datenstrukturen
Pfeil 10.2 Reguläre Ausdrücke
Pfeil 10.2.1 Muster für reguläre Ausdrücke
Pfeil 10.2.2 Programmierung mit regulären Ausdrücken
Pfeil 10.3 Systemnahe Programmierung
Pfeil 10.3.1 Prozesse und Pipes
Pfeil 10.3.2 Threads
Pfeil 10.4 Einführung in die Netzwerkprogrammierung
Pfeil 10.4.1 Die Berkeley Socket API
Pfeil 10.4.2 Ein praktisches Beispiel
Pfeil 10.4.3 Ein Ruby-Webserver
Pfeil 10.5 Verteilte Anwendungen mit Java Enterprise Edition
Pfeil 10.5.1 Enterprise Java Beans (EJB)
Pfeil 10.5.2 Java Servlets
Pfeil 10.5.3 Webservices
Pfeil 10.6 GUI- und Grafikprogrammierung
Pfeil 10.6.1 Zeichnungen und Grafiken erstellen
Pfeil 10.6.2 Animation
Pfeil 10.6.3 Programmierung fensterbasierter Anwendungen
Pfeil 10.6.4 Java-Applets
Pfeil 10.7 Zusammenfassung

Intelligente Fehler zu machen ist eine große Kunst.
– Federico Fellini

10 Konzepte der ProgrammierungZur nächsten Überschrift

Nachdem Sie im vorigen Kapitel die grundlegende Syntax der Programmierung in vier verschiedenen Sprachen erlernt haben, ist es nun Zeit, dieses Handwerkszeug in der Praxis einzusetzen. In diesem Kapitel werden deshalb verschiedene konkrete Aspekte der Programmierung vorgestellt, von der Implementierung wichtiger Algorithmen und Datenstrukturen über eine Einführung in die systemnahe Programmierung und Netzwerkprogrammierung bis hin zur GUI-Anwendungsentwicklung und zur Arbeit mit einer integrierten Entwicklungsumgebung.

Die Implementierung der verschiedenen Beispiele erfolgt jeweils in einer (in seltenen Fällen auch mehreren) der vier im vorigen Kapitel vorgestellten Programmiersprachen; es wird für jede Aufgabe eine passende Sprache ausgewählt.


Galileo Computing - Zum Seitenanfang

10.1 Algorithmen und DatenstrukturenZur nächsten ÜberschriftZur vorigen Überschrift

Wenn Sie Programmieraufgaben lösen müssen, genügt es nicht, die einzelnen Befehle und Datentypen der gewählten Programmiersprache zu kennen. Sie benötigen vor allem ein Gespür dafür, wie sich Informationen und Tätigkeiten aus der realen Welt am effektivsten in einem Computerprogramm darstellen lassen. Für die Speicherung der verschiedenen Arten von Informationen werden mit Hilfe der Datentypen einer Programmiersprache sogenannte Datenstrukturen entwickelt. Die Strategien zur Verarbeitung der Datenstrukturen werden als Algorithmen bezeichnet – der theoretische Hintergrund der Algorithmik wurde bereits in Kapitel 2, »Mathematische und technische Grundlagen«, angesprochen. In diesem Abschnitt werden einige verbreitete Standard-Algorithmen und Datenstrukturen dargestellt.


Galileo Computing - Zum Seitenanfang

10.1.1 Ein einfaches PraxisbeispielZur nächsten ÜberschriftZur vorigen Überschrift

Die Entwicklung eines Algorithmus soll hier zunächst Schritt für Schritt an einem Beispiel erläutert werden. Bevor Sie nämlich konkreten Programmcode hinschreiben, sollten Sie sich zunächst mit Papier und Bleistift theoretische Gedanken über den Ablauf des gewünschten Programms machen. Das Ergebnis solcher Überlegungen ist ein Flussdiagramm.

Es soll ein Algorithmus entwickelt werden, um den größten gemeinsamen Teiler (GGT) zweier ganzzahliger Werte zu ermitteln. Dies ist eine der wichtigsten Aufgaben im Bereich der Bruchrechnung. Der GGT zweier Werte m und n ist im günstigsten Fall m/2 oder n/2, im ungünstigsten Fall 1. Hat er den Wert 1, werden die beiden Zahlen als teilerfremd bezeichnet.

Abbildung 10.1 zeigt ein Flussdiagramm, das einen Ansatz für eine mögliche Lösung tipp_li beschreibt. In einem solchen Diagramm steht ein Rechteck für einen einfachen linearen Arbeitsschritt, eine Raute für eine Ja-Nein-Fallunterscheidung und ein abgerundetes Rechteck für Start oder Ende.

Abbildung

Abbildung 10.1 Flussdiagramm für einen einfachen Algorithmus zur Berechnung des größten gemeinsamen Teilers (GGT)

Es gibt erheblich effizientere Verfahren zur GGT-Berechnung. Hier geht es aber nur um das grundlegende Prinzip.

Erheblich mehr Darstellungsmöglichkeiten bieten die im nächsten Kapitel vorgestellten Diagrammtypen der UML. Sie beziehen nicht nur Algorithmus und Programmablauf ein, sondern zum Beispiel auch die Aktionen verschiedener beteiligter Personen, Geräte und Programme.

Wie die Diagramme zeigen, werden Schritt für Schritt alle in Frage kommenden Werte ausprobiert. Begonnen wird bei der Hälfte der größeren Zahl. Hier sehen Sie eine Implementierung dieses Algorithmus in Java:

static int ggt(int m, int n) {
// Trivialer Fall: m und n gleich:
if (m == n)
return m;
// Größeren und kleineren Wert ermitteln:
int gr = (m > n) ? m : n;
int kl = (m < n) ? m : n;
// Jeden möglichen Teiler testen:
for (int i = gr / 2; i >= gr / kl; i--) {
// Sind beide Werte durch i teilbar?
if (gr % i == 0 && kl % i == 0)
return i;
}
// Hier bleibt nur noch die 1:
return 1;
}

Da die Methode ggt() als static deklariert wurde, kann sie innerhalb einer Programmklasse von der Methode main() aus aufgerufen werden, ohne dass ein Objekt der Klasse bestehen muss. static-Methoden sind gewissermaßen der Java-Ersatz für imperative Funktionen. Hier sehen Sie ein Beispiel für eine main()-Methode, die den GGT zweier Kommandozeilenparameter ausgibt:

public static void main (String args[]) {
int m = Integer.parseInt (args[0]);
int n = Integer.parseInt (args[1]);
System.out.println ("Der GGT von " + m + " und "
+ n + " ist " + ggt(m, n));
}

Nach dem Kompilieren können Sie das Programm beispielsweise folgendermaßen aufrufen, falls die Klasse GGTtest heißt:

$ java GGTtest 18 24
Der GGT von 18 und 24 ist 6.

Die statische Methode parseInt() der Klasse Integer (einer objektorientierten Umhüllung für einen int-Wert) wandelt den übergebenen String in eine Ganzzahl um.


Galileo Computing - Zum Seitenanfang

10.1.2 Sortier-AlgorithmenZur nächsten ÜberschriftZur vorigen Überschrift

Zu den häufigsten Aufgaben bei der Programmierung gehört die Sortierung von Daten nach einem bestimmten Kriterium. Im Laufe der Informatikgeschichte wurden Dutzende von verschiedenen Sortier-Algorithmen entwickelt, die für unterschiedliche Einsatzzwecke geeignet sind. In diesem Abschnitt werden zwei davon vorgestellt. Der erste ist intuitiv verständlich, der zweite gerade für größere Datenmengen besonders effizient.

BubbleSort

Dieser einfachste aller Sortier-Algorithmen durchwandert ein Array elementweise: Er vergleicht jedes Element mit seinem direkten Nachbarn. Falls die beiden Nachbarn in der falschen Reihenfolge stehen, ist es erforderlich, sie zu vertauschen. Außerdem steht dann fest, dass das Array noch nicht fertig sortiert ist, so dass ein weiterer Durchgang erforderlich ist.

BubbleSortin Perl

Hier sehen Sie eine Implementierung von BubbleSort als Perl-Subroutine, die eine Listenreferenz entgegennimmt und die zugrundeliegende Liste nach diesem Schema sortiert:

sub bubblesort {
$listref = shift; # Listenreferenz entgegennehmen
@liste = @$listref; # Kopie der Liste anfertigen
do {
$sortiert = 1; # Annahme: Bereits sortiert.
for ($i = 0; $i < $#liste; $i++) {
# Element i größer als Element i + 1?
if ($liste[$i] > $liste[$i + 1]) {
# Die beiden Elemente vertauschen:
($liste[$i], $liste[$i + 1])
= ($liste[$i + 1], $liste[$i]);
# Aha! Noch nicht sortiert:
$sortiert = 0;
}
}
} while (!$sortiert);
return @liste; # Sortiert zurückgeben
}

Das Kopieren der Liste und die Rückgabe der Kopie sind nicht unbedingt erforderlich, verhindern aber das umständliche Hantieren mit Dereferenzierungen im Kern des eigentlichen Algorithmus. Wenn am Anfang nicht die Kopie @liste angefertigt würde, müsste zum Beispiel der eigentliche Tauschbefehl folgendermaßen lauten:

($$listref[$i], $$listref[$i + 1])
= ($$listref[$i + 1], $$listref[$i]);

Die spezielle Formulierung $#array gibt übrigens den höchsten Index des Arrays @array zurück, bei einem Array mit 13 Elementen also beispielsweise 12. Da für den Vergleich jedes Elements mit seinem rechten Nachbarn eine Schleife vom ersten bis zum vorletzten Element benötigt wird, lautet die Bedingung der for()-Schleife im vorliegenden Fall $i < $#liste.

Die Subroutine bubblesort können Sie zum Beispiel so aufrufen:

@zahlen = qw(2 7 9 1 3 8 6 7);
@zahlen = bubblesort(\@zahlen);
print join(", ", @zahlen);

Die Ausgabe dieses Beispiels lautet:

1, 2, 3, 6, 7, 7, 8, 9

Beachten Sie, dass für die Sortierung von Strings eine separate Fassung erforderlich wäre, die den Vergleichsoperator gt statt des numerischen > verwendet (siehe voriges Kapitel). Wenn Sie im Übrigen nicht aufsteigend, sondern absteigend sortieren möchten, muss statt > der Operator < eingesetzt werden, bei Strings entsprechend lt.

BubbleSortin Java

Zu Vergleichszwecken sehen Sie hier eine weitere Implementierung von BubbleSort als Java-Methode, die ein Array von int-Werten sortiert:

static int[] bubbleSort(int[] liste) {
boolean sortiert;
do {
sortiert = true;
for (int i = 0; i < liste.length - 1; i++) {
if (liste[i] > liste[i + 1]) {
// Tauschen:
int temp = liste[i];
liste[i] = liste[i + 1];
liste[i + 1] = temp;
// Nicht sortiert!
sortiert = false;
}
}
} while (!sortiert);
return liste;
}

Die folgende main()-Methode generiert ein Array mit unsortierten Werten, ruft bubbleSort() auf und gibt anschließend die sortierte Liste aus:

public static void main (String args[]) {
int[] werte = {3, 7, 1, 9, 2, 5, 2};
werte = bubbleSort(werte);
for (int i = 0; i < werte.length; i++) {
System.out.print(werte[i] + " ");
}
}

Die Ausgabe sieht natürlich folgendermaßen aus:

1 2 2 3 5 7 9
Rekursion

Im nächsten Abschnitt wird ein sehr komplexer, aber erheblich effizienterer Sortier-Algorithmus vorgestellt. Dieser verwendet die besondere Technik der Rekursion, bei der eine Funktion sich selbst mit geänderten Parametern aufruft. Rekursion ist immer dann nützlich, wenn Sie gleichartige, ineinander verschachtelte Aufgaben lösen müssen. Beispielsweise lässt sich die Fakultät eines Werts sehr leicht rekursiv berechnen. Die Fakultät n! einer natürlichen Zahl n ist das Ergebnis der Multiplikation 1 * 2 * 3 * ...* n. Durch Rekursion lässt sich das Problem schrittweise reduzieren, beispielsweise gilt im ersten Schritt: n! = n * (n – 1)! Das folgende Beispiel zeigt eine rekursive C-Funktion, die auf diese Weise die Fakultät eines übergebenen Werts berechnet:

int fakultaet (int n) {
if (i > 1)
return n * fakultaet (n – 1);
else
return 1;
}
Solange das übergebene n noch größer als 1 ist, wird das Problem an einen weiteren Aufruf von fakultaet() delegiert; das aktuelle n wird mit dem Rückgabewert dieses Aufrufs multipliziert. Die Aufrufe werden schließlich von innen nach außen abgearbeitet: Der letzte oder innerste Aufruf gibt 1 zurück, die mit der 2 des darüberliegenden Aufrufs multipliziert wird, und so weiter. Der Gegenbegriff zur Rekursion ist übrigens Iteration. Natürlich lässt sich die Fakultät auch iterativ (in einer Schleife) berechnen, allerdings ist der Aufwand größer und die Schreibweise umständlicher:
int fakultaet (int n) {
int i;
int fak = 1;
for (i = 2; i <= n; i++) {
fak *= i;
}
return fak;
}

QuickSort

Wie der Name vermuten lässt, handelt es sich bei QuickSort um einen besonders geschwindigkeitsoptimierten Sortier-Algorithmus. Für eine ausreichend große Anzahl von Elementen ist er tatsächlich eines der schnellsten verfügbaren Sortierverfahren. Bei einer zu kleinen Elementanzahl kann er seinen theoretischen Geschwindigkeitsvorteil wegen der relativ aufwendigen Initialisierung nicht ausspielen.

QuickSort-Funktionsweise

QuickSort funktioniert nach dem Verfahren »Teile und herrsche«: Das gesamte zu sortierende Array wird in zwei Teile unterteilt (partitioniert), die an rekursive Aufrufe der Funktion übergeben werden. Dazu wird zunächst ein Vergleichselement namens Median gesucht; die Daten rechts des Medians müssen größer sein, die Daten links von ihm kleiner. Dies geschieht für jede Partition so lange immer wieder, bis jeweils nur noch zwei Elemente übrig sind, die in die richtige Reihenfolge gebracht werden. Hier eine QuickSort-Implementierung in Java:

static int[] quickSort(int[] liste) {
/* quickSort ist nur ein bequemer Starter für die
eigentliche Arbeits-Methode qSort(). */
// qSort mit dem gesamten Array aufrufen:
qSort (liste, 0, liste.length - 1);
return liste;
}

static void qSort(int[] liste, int lo, int hi) {
if (lo < hi) {
// Vergleichselement Median ermitteln:
median = liste[hi];
int i = lo - 1;
int j = hi;
for ( ; ; ) {
// Werte von beiden Enden aus vergleichen:
while (liste[--i] < median);
while (j > 1 && liste[--j] > median);
// Schleife verlassen, falls sortiert:
if (j < i)
break;
// Tauschen
int temp = liste[i];
liste[i] = liste[j];
liste[j] = temp;
}
liste[hi] = liste[i];
liste[i] = median;
// Linke/rechte Partition sortieren:
qSort (liste, lo, i - 1);
qSort (liste, i + 1, hi);
}
}

Die Verwendung von quickSort() könnte beispielsweise genauso aussehen wie der weiter oben gezeigte Aufruf von bubbleSort(); Sie müssten lediglich den Namen der aufgerufenen Methode ändern und könnten alles andere stehenlassen.

Auffällig sind an dieser Implementierung von QuickSort die etwas gewöhnungsbedürftigen Schleifenkonstruktionen. for ( ; ; ) ist eine Endlosschleife, die allerdings durch den gezielten Aufruf von break; verlassen wird. Eine solche Schreibweise ist immer dann nützlich, wenn sich erst während der Ausführung des Schleifenrumpfs herausstellt, dass der weitere Ablauf nicht mehr erforderlich ist.

Ähnlich seltsam sind die beiden in sich geschlossenen while()-Schleifen wie diese:

while (liste[--i] < median);

Da nichts weiter getan werden muss, als die Elemente der Liste nacheinander mit dem Median zu vergleichen, ist dies eine erheblich kompaktere Schreibweise für die folgende Fassung:

do {
--i;
} while (liste[i] < median);

Galileo Computing - Zum Seitenanfang

10.1.3 Such-AlgorithmenZur nächsten ÜberschriftZur vorigen Überschrift

Eine weitere häufig gestellte Aufgabe bei der Entwicklung von Computerprogrammen ist die Suche nach Elementen in Arrays. Es gibt zwei grundsätzliche Arten dieser Suche: Die lineare Suche durchsucht nacheinander die einzelnen Elemente des Arrays, die binäre Suche erfordert dagegen ein bereits sortiertes Array und sucht darin durch fortgesetztes Halbieren und rekursives Durchsuchen der einzelnen Teilbereiche.

Lineare Suche

Die einfachste Art der Suche ist die lineare. Der Algorithmus besteht einfach darin, die Elemente eines Arrays nacheinander mit einem Suchwert zu vergleichen. Sobald der gesuchte Wert das erste Mal gefunden wird, wird dessen Index zurückgegeben; eine andere Variante würde alle Fundstellen zurückliefern. Es folgt eine Implementierung dieses Algorithmus in Java. Die Methode suchen() erwartet die Übergabe eines Arrays von int-Werten und den gesuchten Wert. Sie gibt den Index des ersten Vorkommens dieses Werts im Array zurück oder –1, falls der gesuchte Wert nicht im Array vorkommt. Hier der Code:

static int suchen(int[] liste, int wert) {
for (i = 0; i < liste.length; i++) {
if (liste[i] == wert)
return i;
}
// Nicht gefunden:
return -1;
}

Dieser Code sollte im Großen und Ganzen selbsterklärend sein. Ein Aufruf dieser Methode könnte folgendermaßen aussehen:

public static void main (String args[]) {
int zahlen[] = {5, 1, 8, 3, 9, 2, 7};
int suchwert = 8;
System.out.println (suchwert +
" kommt in der Liste an Position " +
suchen (zahlen, suchwert) + " vor.");
}

Die Ausgabe dieses Hauptprogramms sieht natürlich so aus:

8 kommt in der Liste an Position 2 vor.

Binäre Suche

Bei der binären Suche muss zunächst ein sortiertes Array vorliegen. Dieses sortierte Array wird anschließend durch eine rekursive Methode immer weiter unterteilt, dadurch kann der gesuchte Wert sehr schnell gefunden werden.

Hier sehen Sie eine Implementierung dieses Algorithmus in Java. Die Methode binSuche() erwartet die Übergabe eines sortierten Arrays (die Sortierung wird nicht überprüft!) und den gesuchten Wert. Der Rückgabewert ist wieder der Index des gesuchten Elements oder –1, falls das Element nicht gefunden wird:

int binSuche (int[] liste, int wert) {
//Initialisierung der eigentlichen Methode bSuche()
return bSuche (liste, wert, 0, liste.length);
}

int bSuche (int[] liste, int wert, int lo, int hi) {

// Nicht gefunden?
if (lo > hi)
return -1;
int m = (lo + hi) / 2;
int mwert = liste[m];
if (mwert == wert)
return wert;
if (wert < mwert)
return bSuche (liste, wert, lo, m - 1);
if (wert > mwert)
return bSuche (liste, wert, m + 1, hi);
}

Galileo Computing - Zum Seitenanfang

10.1.4 Ausgewählte DatenstrukturenZur nächsten ÜberschriftZur vorigen Überschrift

Auf der Basis der grundlegenden Datentypen, die im vorigen Kapitel vorgestellt wurden, lassen sich diverse komplexe Datenstrukturen für die Darstellung der verschiedensten Arten von Informationen aus der Realität einrichten. Einige wichtige Datenstrukturen, die häufig für Programmieraufgaben verwendet werden, werden nun vorgestellt.

Stacks und Queues

Die Eigenschaften von Stacks (Stapeln) und Queues (Warteschlangen) wurden bereits im vorigen Kapitel bei der Vorstellung der Programmiersprache Perl erwähnt. Es handelt sich um Arrays mit einer dynamischen Anzahl von Elementen. Bei einem Stack werden Elemente nacheinander am Ende angehängt und bei Bedarf von diesem Ende wieder entfernt. Es handelt sich also um einen »Last In, First Out«-(LIFO)-Speicher. Eine Queue ist dagegen ein »First In, First Out«-Speicher (FIFO): Elemente werden am Anfang der Liste hineingeschoben und am Ende nacheinander entnommen.

In Perl ist die Unterstützung für Stacks und Queues bereits eingebaut. Mit Hilfe der Funktionen push(@liste, $wert) und pop(@liste) wird ein Stack realisiert: push hängt den angegebenen Wert an das Ende der Liste an, pop entfernt das letzte Element und gibt es zurück. Mit Hilfe von unshift und pop lässt sich dagegen eine Queue einrichten: Mit unshift (@liste, $wert) wird ein Wert am Anfang einer Liste eingefügt, pop entfernt wie gehabt den letzten Wert.

Listen in C

In anderen Programmiersprachen ist die Implementierung dieser Datenstrukturen dagegen ein wenig schwieriger. In C und Java haben die eingebauten Arrays eine feste Anzahl von Elementen, sind also zur Darstellung dynamischer Listen nicht geeignet. In C wird in der Regel ein struct definiert, der jeweils einen einzelnen Wert und einen Zeiger auf das nächste dieser Elemente enthält. Eine solche Struktur sieht also beispielsweise so aus:

struct element {
int wert;
struct element *nachfolger;
}

Auch wenn es ein wenig seltsam aussieht, dass innerhalb der struct-Definition ein Zeiger auf diesem Datentyp selbst steht, ist dies überhaupt kein Problem. Zwar kann eine Struktur keine Variable enthalten, deren Datentyp die Struktur selbst ist, aber ein Zeiger darauf funktioniert.

Hier ein kleines C-Beispielprogramm, in dem eine Liste verwendet wird, um zehn eingegebene Werte aufzunehmen, die anschließend durch sequentielles Durchwandern der Liste wieder ausgegeben werden:

#include <stdio.h>
#include <stdlib.h>

struct liste {
int wert;
struct liste *nachfolger;
};

int main (int argc, char *argv[]) {
int i;
int w;
/* Element erzeugen */
struct liste *aktuell = malloc(sizeof *aktuell);
struct liste *erster = aktuell; /* Anfang merken */
printf ("Bitte 10 int-Werte!\n");
for (i = 0; i < 10; i++) {
scanf ("%d", &w);
aktuell->wert = w;
aktuell->nachfolger = malloc(sizeof *aktuell);
aktuell = aktuell->nachfolger;
}
aktuell = erster;
printf ("\n");
printf ("Ihre Eingaben:\n");
for (i = 0; i < 10; i++) {
printf ("%d\n", aktuell->wert);
aktuell = aktuell->nachfolger;
}
return 0;
}

malloc( )

Die Funktion malloc() dient dazu, dynamisch Speicher zu allozieren. Das bedeutet, dass ein Bereich im Arbeitsspeicher für einen neuen Wert reserviert wird. Die Speicherverwaltungsfunktionen sind in der Header-Datei stdlib.h definiert. malloc() besitzt einen etwas merkwürdigen Datentyp: void *. Dies ist nicht etwa ein »Zeiger auf gar nichts«, sondern einfach ein Zeiger auf einen beliebigen Datentyp. Damit die richtige Menge Speicher reserviert wird, benötigt malloc() die gewünschte Speichermenge (Datentyp size_t) als Argument. Hierzu bietet sich der Operator sizeof an, der die Speichergröße einer Variablen oder eines Datentyps angibt.

In robusten Programmen für echte Anwendungszwecke sollten Sie malloc() stets mittels if überprüfen, damit Sie Fälle abfangen können, in denen die Speicherzuteilung nicht möglich ist (etwa wenn insgesamt zu wenig Speicher zur Verfügung steht).

In diesem Beispielprogramm werden zwei verschiedene Zeiger auf ein Listenelement verwendet, damit das erste Element der Liste auch dann noch verfügbar ist, falls der andere Zeiger zum Durchwandern der Liste genutzt wird.

In Java lässt sich eine Liste noch erheblich einfacher realisieren: Wegen der Objektorientierung können Sie leicht eine Klasse implementieren, die ein Listenelement und einen Verweis auf seinen Nachfolger darstellt. Eine solche Klasse könnte beispielsweise so aussehen:

public class Element {
private int wert;
private Element nachfolger;
}

Es ist leicht vorstellbar, dass sich Funktionen zum Hinzufügen oder Entfernen von Elementen als Methoden einer solchen Klasse implementieren lassen.

Es folgt ein kleines Beispiel für die praktische Anwendung von Listen. Das Programm ist in Perl geschrieben, weil Listen in dieser Sprache bereits eingebaut sind und keinen komplexen Programmieraufwand erfordern. Das Beispiel verwendet einen Stack, um die Wörter in einem String umzukehren:

#!/usr/bin/perl -w
use strict;
print "Bitte eine Zeile eingeben:\n";
my $line = <>;
chomp $line;
# An Leerzeichen zerlegen:
my @words = split (/\s+/, $line);
# Umgekehrte Liste erstellen:
my @rwords;
while (@words) {
push (@rwords, pop (@words));
}
# Umgekehrte Liste ausgeben:
print join (" ", @rwords);

Die Ausgabe des Programms sieht beispielsweise so aus:

Bitte eine Zeile eingeben:
Diese Liste wird nun umgekehrt

umgekehrt nun wird Liste Diese

Die wichtige Anweisung in diesem Programm ist folgende:

push (@rwords, pop (@words));

Mit Hilfe von pop wird jeweils das letzte Zeichen der Liste @words entnommen und mittels push an die Liste @rwords angehängt.

Bäume

Eine weitere interessante Datenstruktur ist der Baum. Die einzelnen Elemente eines Baums ähneln denjenigen einer Liste, mit dem Unterschied, dass ein Element eines Baums jeweils mehrere Nachfolger haben kann. Die wichtigste Art der Baumstruktur ist der Binärbaum. Jedes Element dieses Baums kann genau zwei Nachfolger besitzen. Mit Hilfe von Binärbäumen werden beispielsweise schnelle Such- und Sortierverfahren implementiert.

Binärbäume in C

In der Sprache C sieht die Datenstruktur für ein einzelnes Element eines Binärbaums beispielsweise so aus:

struct baum {
int wert;
struct baum *links;
struct baum *rechts;
}

Hier sehen Sie eine Variante des Listenbeispiels von oben, bei der Eingabewerte zwischen 1 und 100 erwartet werden. Sie werden jeweils nach ihrer Größe in den Binärbaum einsortiert; bei der Ausgabe wird der Baum rekursiv von ganz links nach ganz rechts durchwandert.

#include <stdio.h>
#include <mem.h>

struct baum {
int wert;
struct baum *links;
struct baum *rechts;
};
void zeige_baum (struct baum *aktuell) {
if (aktuell->links)
zeige_baum (aktuell->links);
printf ("%d\n", aktuell->wert);
if (aktuell->rechts)
zeige_baum (aktuell->rechts);
}

int main (int argc, char *argv[]) {
int i;
int w;
/* Element erzeugen: */
struct baum *aktuell = malloc (sizeof *aktuell);
/* Anfangsposition merken: */
struct baum *erster = aktuell;
/* mittleren Wert speichern: */
aktuell->wert = 50;
printf ("Bitte 10 Werte von 1 bis 100 eingeben.\n");
for (i = 0; i < 10; i++) {
printf ("%2d. ", i + 1);
scanf ("%d", &w);
/* Wert einsortieren */
aktuell = erster;
for ( ; ; ) {
if (w <= aktuell->wert) {
if (aktuell->links) {
aktuell = aktuell->links;
} else {
aktuell->links =
malloc (sizeof *aktuell);
aktuell = aktuell->links;
break;
}
}
else {
if (aktuell->rechts) {
aktuell = aktuell->rechts;
} else {
aktuell->rechts =
malloc (sizeof *aktuell);
aktuell = aktuell->rechts;
break;
}
}
}
aktuell->wert = w;
}
printf ("\n");
printf ("Ihre Eingaben:\n");
zeige_baum (erster);
return 0;
}

Interessant ist, wie dieses Programm die einzelnen Werte in den Baum einsortiert. Für jedes einzelne Element wird bei der Wurzel des Baums begonnen: Wenn das Element kleiner oder gleich dem Wert an der Wurzel ist, wird weiter nach links gewandert, andernfalls weiter nach rechts. Auf diese Weise sucht sich jeder Wert seinen passenden Platz im Baum. Je kleiner ein Wert ist, desto weiter links steht er im fertigen Baum.

Die rekursive Funktion zeige_baum() wird zunächst mit der Wurzel des Baums aufgerufen. Falls das Baumelement, mit dem sie aufgerufen wurde, einen linken Nachfolger hat, wird sie zuerst für diesen aufgerufen. Anschließend wird der Wert das Element selbst ausgegeben, schließlich wird die Funktion noch einmal für den rechten Nachfolger aufgerufen, falls er existiert. Auf diese Weise wird der Baum nacheinander von links nach rechts ausgegeben.



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.

>> Zum Feedback-Formular
<< zurück




Copyright © Galileo Press 2011
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Galileo Computing]

Galileo Press, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de


  Zum Katalog
Zum Katalog: IT-Handbuch für Fachinformatiker






IT-Handbuch für Fachinformatiker
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchempfehlungen
Zum Katalog: Java ist auch eine Insel






 Java ist auch
 eine Insel


Zum Katalog: Android 3






 Android 3


Zum Katalog: Linux






 Linux


Zum Katalog: Ubuntu GNU/Linux






 Ubuntu
 GNU/Linux


Zum Katalog: Windows Server 2008 R2






 Windows Server
 2008 R2


Zum Katalog: PHP & MySQL






 PHP & MySQL


Zum Katalog: Visual C# 2010






 Visual C# 2010


Zum Katalog: C von A bis Z






 C von A bis Z


Zum Katalog: C++ von A bis Z






 C++ von A bis Z


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo