Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Informatik in der Schule » Huffmanbaum Delphi » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Huffmanbaum Delphi
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
uhr123
unregistriert
Huffmanbaum Delphi Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo,

ich habe eine Frage: Wie kann ich, wenn ich Buchstaben sortiert in einem BinarySearchTree habe, als einelementige Bäume in eine Liste schreiben und dann jeweils aus der Liste die beiden kleinsten Objekte (also in der Liste sollen die dann aber schon nach Häufigkeit eines Buchstabens einsortiert sein) zusammenfügen und wieder in die Liste tun?

Kommentare in Delphi sind folgende:
// ermittelt die vorkommenden Zeichen und deren Häufigkeiten und erstellt
// als Funktionsergebnis einen alphabetisch geordneten Baum aller im Klartext
// auftretenden Zeichen und deren Häufigkeit. Die Inhaltsobjekte des Baums
// sind vom Typ TZeichenObjekt
//erzeugt aus dem alphabetisch geordneten Zeichenbaum pZeichenBaum durch einen
//inorder-Durchlauf die nach Häufigkeiten geordnete Liste der einelementigen Huffman-Bäume
//und liefert diese als Funktionsergebnis zurück.
//erzeugt aus der nach Häufigkeiten geordneten Lise der einelementigen
//Huffmanbäume pHuffmanBaumListe den endgültigen HuffmanBaum als Funktionsergebnis

Aber irgendwie bekomme ich in die Liste nur TZeichenobjekte rein, keine elementigen Bäume... und das Zusammenfassen der Kleinsten klappt auch nicht.
Kann mir jemand helfen, wie ich das in Delphi schreiben muss?
03.03.2013 18:56
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

RE: Huffmanbaum Delphi Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo,

mit Delphi kenne ich mich leider nicht aus. Aber vlt reicht eine methodische Beschreibung um deinem Problem auf die Spur zu kommen.

Zitat:
Original von uhr123
Wie kann ich, wenn ich Buchstaben sortiert in einem BinarySearchTree habe, als einelementige Bäume in eine Liste schreiben


Ich würde eine Funktion schreiben, welche Huffman-Bäume und eine Liste von Huffman-Bäumen entgegen nimmt schreiben. Dann eine leere Liste anlegen und danach beim in-order-traversieren immer einen neuen Huffman-Baum erstellen, welcher nur den betroffenen Buchstaben enthält.
Ich nehme an, dazu sollte es Baum- und Blattknoten geben. Der Baumknoten hält die Häufigkeit und die Kinder, wobei Kinder entweder 2 Baumknoten sind oder ein Blattknoten. Die Blattknoten beinhalten dann das Zeichen.... Dann jeden Baum und die Liste an die geschriebene Funktion übergeben, welche das geordnete einfügen in die Liste übernimmt.

Zitat:
Original von uhr123
und dann jeweils aus der Liste die beiden kleinsten Objekte (also in der Liste sollen die dann aber schon nach Häufigkeit eines Buchstabens einsortiert sein) zusammenfügen und wieder in die Liste tun?


Hier müssen einfach die zwei Bäume mit der kleinsten häufigkeit aus der Liste entnommen werden (also nicht nur abrufen, sondern auch wirklich entnehmen) und anschließend wird ein neuen Huffman-Baum erstelllt, welcher als Kinder die beiden kleineren Bäume hat. Diesen dann wieder mit der oben genannten funktion sortiert in die Liste einfügen. Und das so lange, Bis die Liste nur noch ein Element hat.

Wo ist genau das Problem?

VG,

Karlito
04.03.2013 11:55 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Informatik in der Schule » Huffmanbaum Delphi