ich lerne gerade für meine anstehende Programmierungsklausur und bin als einzigstes bei der Frage "Worin unterscheiden sich die Implementation einer Liste, eines Baumes und eines Graphen in Java? Welche Alternativen gibt es bei einem Graphen?" hängen geblieben - da ich nicht genau weiß, worauf der Prof. hier abzielt, deshalb wollte ich Euch um Hilfestellung bitten.
Da er mit Implementierung die Umsetzung meint, gehe ich stark davon aus, dass er wissen möchte, wo die größten Unterschiede zwischen Liste, Baum und Graph bestehen und wie sich diese im Java Code widerspiegeln. Liste - einfache Verkettung über Zeiger - absolute Referenzierung - Link
Baum - spezielle Form eines Graphen - bildet Monohierarchie ab - maximal zwei Söhne (bei binärem Baum) - Link
Graph - Mehrfachhierarchie - gerichtet oder ungerichtet - Link
Das lässt sich natürlich weiter fortsetzen, ebenso die unterschiedlichen Implementierungen eines jeden Modells. Frage wäre jetzt, worauf du mehr Wert legst - auf die Umsetzung in Java oder die allgemeinen Definitionen und Vorgehensweisen.
//EDIT Das Ganze ist nur ein Schnellschuss, da ich gerade auf der Arbeit bin. Ich kann dir auch noch ein Dokument einer Uni zukommen lassen, in welcher alles nochmal beschrieben und ausführlich aufgezeigt wird. Ebenfalls mit Beispielen und Berechnung der Dauer von Operationen.
Generell beinhaltet das Dokument alles zur Berechnung von Algorithmen (Kollege schreibt ebenfalls bald dazu eine Klausur). Bei Interesse schick mir einfach deine Mail als PN.
Ich würde nicht sagen, dass ein Baum(knoten) maximal zwei Söhne haben kann (das ist wohl bei einem Binärbaum so), aber das trifft z.B. für einen B-Baum nicht zu.
Worauf dein Prof. hier ganu abzielt, kann ich Dir leider auch nicht sagen. Wenn Du eine Liste in Java implemnentierst und ich auch, dann werden sich die zwei sehr wahrscheinlich voneinander unterscheiden. Allerdings will der Prof. das wahrscheinlich auch nicht wissen. Deshalb ein paar ernsthafte Anregungen aus der Praxis, die nicht den Anspruch auf akademische Korrektheit und Vollständigkeit erheben (dazu sind die entsprechenden Vorlesungen bei mir einfach schon zu lange her):
Liste
Eine Liste bietet normalerweise einen RandomAccess mit Hilfe eines Index
Eine Liste kann man recht gut mit einem Array als Datenspeicher implementieren
Neue Elemente werden normalerweise ans Ende angefügt
Eine Liste ist per se erstmal nicht sortiert
Das Suchen in einer Liste ist eine O(n/2) (Average) Operation
Baum Bäume gibt es in vielen Ausprägungen, daher tu ich mich da etwas schwer, aber manche Dinge gelten woll generell:
Ein Baum bietet normalerweise keinen RandomAccess mit Hilfe eines Index
Einen Baum implementiert man mit Knoten, wobei jeder Knoten Referenzen auf seine Kinder hat. Man benötigt lediglich den Wurzelknoten, um Zugriff auf alle Knoten im Baum zu erlangen.
Die Traversierung eines Baums kann auf unterscheidliche Weise erfolgen, z.B. Inorder, Postorder, ...
Neue Elemente werden je nach Baum an einer während des Einfügevorgangs zu bestimmenden Stelle eingefügt. Manche Einfügeoperationen verändern dann auch die Baumstruktur durch Umhängen von Teilbäumen, um z.B. die Balance im Baum aufrecht zu erhalten.
Eine Baum ist normalerweise geordnet, allerdings ist nicht jede Traversierung geeignet, den Inhalt des Baums sortiert auszugeben.
In einem balancierten Suchbaum kann eine Suche mit Komplexität O(n log n) (Average) durchgeführt werden.
Graph
Graphen kann man mit einer Adjazenzliste bzw. Adjazenzmatrix implementieren, das ist die Alternative zur Implementierung mit Knoten
Auch hier gibt es ähnlich wie bei den Bäumen eine Vielzahl von Algorithmen, Eigenschaften, ... da kann ich nicht annähernd soviel beitragen wie ein gutes Buch zum Thema (aber die hast Du ja sicherlich :-)
Bei den Eigenschaften der Liste werden zwei verschiedene Sachen (Liste und Array) in einem Topf geworfen, da deren konzepte unterschiedlich sind. Bei einer Liste kann man nur über den Kopf oder Sentinel einsteigen (kein Index) und dann, je nach implementierung (einfach oder doppelt verkettet) die Liste durchlaufen. Weiterhin liegen bei einer Liste die Daten ungeordnet im Speicher, weshalb sie relativ einfach erweitert werden kann. Ein Array besitzt eine festen zusammenhängenden! Bereich im Speicher, weshalb der zugriff per Index geht (dafür nicht erweiterbar).
Für eine einfach oder doppelt verkettete Liste mag das richtig sein, das vervollständigt auf jeden Fall meine Antwort (danke), denn darauf bin ich nicht eingegangen. Allerdings gibt es sehr wohl Listen mit wahlfreiem Zugriff über einen Index, die mit einem dynamisch wachsenden Array als Backingstore implementiert werden (wenn man "Liste" in diesem Zusammenhang als Schnittstelle auffasst, dann gibt es sicherlich noch zig andere Impl.); für einen wahlfreien Zugriff wäre eine verkettete Liste keine gute Wahl und ein Array vom Interface her zu unhandlich.
