Morsealphabet als Binärbaum programmieren? What?

[Clashhelfer]

Zitat:

Zitat von KodeZwerg (Beitrag 1415910)

sorry, ich gebe es auf. Anhang 50101 bzw probiere es später von zu hause nochmal :)

Gerne, Edit: Das Ganze soll doch implementiert werden[in Delphi]

Die Unit dafür habe ich schon geschrieben.. Inhalt brauch ich nurnoch und da fehlt mir das nötige Wissen.. Bzw. ich verstehe es nicht.

Delphi-Quellcode:

unit uTMorsecode;

interface

uses
  uBinTree, graphics;

implementation


type
 TMorsecode = class(TBinTree)

  public
     constructor Create (canvas: TCanvas);
     function code (text: String): String;
     function decode(Text: String): String;
  private
     function charcode (c: char; node: TNode; code: string): string;
     function chardecode (c: char; node: TNode; code: string): string;
 end;

implementation
 
.
.
.

end.

[hoika]

Hallo,
hast du dir uBinTree.pas und dessen Klasse/Methoden schon angesehen?

Bsp:

Delphi-Quellcode:

function TBinTree.insertleft(c: char): boolean;
  // Es wird an der Cursorposition ein neues Blatt an den Baum gehängt, wenn
  // der Cursorknoten links einen leeren Teilbaum besitzt. Bei einem leeren Baum
  // wird der Wurzelknoten erzeugt. War das Einfügen erfolgreich, wird das
  // Zeichen "c" als Knoteninhalt gespeichert "true" zurückgegeben - sonst "false".

Ich fange ich mit einem leeren Binärbaum an:

var 
  BinTree: TBinTree;
begin
  BinTree:= TBinTree.Create;
  BinTree.Empty;  // eigentlich nicht notwendig, weil der Baum ja eh leer ist

  BinTree.insertleft('E');
  // Der "Cursor", also der aktuelle Knoten ist jetzt
  BinTree.insertleft('I');

  so dann erst mal alle ganz linken rein ('S', 'H','5').
  Danach mit Reset wieder auf Root.
  BinTree.Reset;
  auf 'E' springen
  BinTree.Left;
  BinTree.InsertRight('A');

So kannst Du dir schrittweise deinen Baum aufbauen.

[Klaus01]

.. ist es in dem Beispielbaum (in dem .odt) nicht so , das man vom root node wenn ein "-" kommt nach rechts im Baum abzweigt, und wenn ein "." nach links.

T(-) steht dann rechts vom root-node
M(--) steht rechts vom T node
N(-.) steht dann links vom T node.

E(.) steht dann entsprechend links vom root-node.


Grüße
Klaus

[Sherlock]

OK, die Aufgabe erfordert etwas Textverständnis und ein paar Stunden Beschäftigung mit ObjectPascal. Ich bin heute aber in Erklärbär Laune.

Zusammenfassung:
Was der Morsecode ist, wird in dem .odt erklärt. Warum er so ist leider nicht, aber dazu hat Daniel ja einen Link präsentiert. Kurz geht es darum über ein Kabel (oder Lichtsignale oder später auch per Funk) Mitteilungen zu übertragen. Diese Mitteilungen sollen zum einen beliebige Texte beinhalten und zum anderen möglichst zeitsparend übertragen werden können. Weil es zum Zeitpunkt der Erfindung nicht möglich war gesprochene Sprache zu übertragen, sondern nur zwischen "Strom fließt" (dabei kann man auch auf die Dauer dieses Zustands achten, Kernpunkt des Morse-Codes) und "Strom fließt nicht" unterscheiden konnte, kam man auf den Code. Er nutzte den "Strom fließt" Zustand samt der Möglichkeit unterschiedlicher Dauer für die Übertragung zweier verschiedener Zeichen:
* ein kurzes "Strom fließt" symbolisiert als .
* und ein langes "Strom fließt" symbolisiert durch ein -
Zusammen mit einem etwas längeren "Strom fließt nicht" als Trenner kompletter Buchstaben, konnte er fortan seinen Code sinnvoll nutzen.

Codieren (besser: Encodieren) bedeutet dabei, den Text, den man durch die Leitung schicken will, in die entsprechende Form zu bringen. Dies geschah in der Vergangenheit von Hand, jetzt soll dieses Programm das automatisieren. Aus zB DELPHI muss dann -... . .-.. .--. .... .. werden.

Decodieren beschreibt die Umkehrung des obigen Prozesses, also die Empfängerseite. Man hat eine Menge von durch Pausen getrennte . und - die man eben in Buchstaben und hoffentlich sinnvolle Wörter decodieren muss. Also ist aus -... . .-.. .--. .... .. wieder DELPHI herzustellen. Damit ist codieren/decodieren nichts anderes als eine Übersetzung wie zB von Deutsch nach Englisch und Umgekehrt.

Zwischenstand:
Jetzt sollte man begriffen haben, worum es beim Morsen geht (die Sache geht eigentlich noch tiefer und begründet fast schon einen wichtigen Teilbereich der Informatik, genannt Informationstheorie, weil man sich ein paar wichtige Gedanken bei der Code Erstellung gemacht hat: Stichworte Entropiekodierung, Präfixfreiheit).

Interessanterweise schreibst Du, daß Du weißt, was es mit einem Baum in der Informatik auf sich hat. Ich hab daran seinerzeit etwas länger knabbern müssen, und (wissentlich) nie eingesetzt. Kurz das wichtigste zu einem Baum: Einen bestimmten Wert in einem Baum zu suchen, ist aufgrund der Regeln, die zu seinem Aufbau führen, im Schnitt schneller, als eine simple Liste von vorne nach hinten abzusuchen. Es gibt freilich Suchstrategien für Listen, die schneller sind als die lineare Suche, aber ein Baum wird in der Regel dennoch vorgezogen.

Was haben wir jetzt also:
Wir wissen was Morsen ist, können mit Stift und Papier (zu Deutsch: schriftlich!) codieren und decodieren und haben sowohl eine Tabelle des Morsecodes als auch ein Bild der Repräsentation als Baum (gepunktete Linien für . und gestrichelte Linien für -). Bleibt noch zu klären, was es mit dem Klassendiagramm (das offenbar in der für so ziemlich alle unlesbaren .urd Datei liegt, glücklicherweise aber auch in der Aufgabenstellung angegeben wurde) und dem Quellcode auf sich hat.

Schauen wir uns die Klassen mal an:
(Vorbemerkung: Nach meinem Kenntnisstand sind ! und ? nicht Bestandteil von UML, werden aber immer wieder mal genommen, um Prozeduren von Funktionen zu unterscheiden, was durch den Rückgabewert bei Funktionen eigentlich unnötig ist)

TBinTree und sein Anhängsel TNode sind des Pudels Kern, TMorsecode ist die Aufgabe und TForm1 ist schließlich schlicht ein Muß um das ganze visuell hinzubekommen. Alle Klassen sollten wissen, was beim Erzeugen und Freigeben gegebenenfalls zu beachten ist (create und destroy).
Bereits implementiert sind TBinTree und TNode.
TBinTree: Es werden uns drei Prozeduren geboten, die selbsterklärende Namen haben: eine zeichnet, eine entfernt den Baum und eine setzt etwas im Baum zurück (was klärt sich gleich). Dann haben wir einige Funktionen mit ebenso selbsterklärenden Namen, die gleichzeitig Schlüsse auf die allgemeine Implementierung der Klasse zulassen: Die Klasse erlaubt es abhängig von der aktuellen Position im Baum zu navigieren, nennen wir diese Position einfach mal Cursor, so wie der Cursor hier im Editor. Alle Funktionen beziehen sich immer auf die Position des Cursors:

• GetChar holt das Zeichen an der aktuellen Cursorposition
• left und right bewegen zum linken oder rechten Unterknoten falls möglich und melden den Erfolg
• die beiden inserts hängen vom aktuellen Cursor ausgehend, Knoten an die gegebene Position und füllen sie mit dem übergebenen Zeichen, wenn dort nicht bereits etwas steht. Die Erfolgsmeldung ist der Rückgabewert.
• Empty ist eine Abfrage ob der Baum leer ist
  Damit ist auch klar, daß die Postion des Cursors mit Reset auf die Wurzel zurückgesetzt wird.

TNode: Die Klasse repräsentiert einen Knoten im Baum, sie umfaßt den Knoteninhalt und die Speicherstellen für ihre Unterknoten. Jedes Mal wenn TBinTree einen Knoten erzeugen möchte oder abfragt, landen wir in einer Instanz hiervon.

Nun die nicht implementierte Klasse TMorseCode:
Wir haben zwei Funktionen code und decode die offensichtlich mit einen kompletten Text bzw. eine Folge von Morsecodes arbeiten sollen. Und zwei Funktionen die dem Namen nach das gleiche für jeweils ein einfaches Zeichen tun sollen.

Jetzt kommt die Preisfrage:
Mit dem bis hierhin erlangten Wissen: Was bedeutet es, den Binärbaum zum Morsecode aufzubauen? Welche Methoden von TMorseCode wären dazu nötig, und warum und eventuell schon wie? Dann, welche Methoden von TBinTree wären nötig, wieder warum?

Sherlock

[DieDolly]

Zitat:

Die Unit dafür habe ich schon geschrieben.. Inhalt brauch ich nurnoch und da fehlt mir das nötige Wissen.. Bzw. ich verstehe es nicht.

Ich kann mir nur bedingt vorstellen, dass ein Lehrer Schülern eine Aufgabe gibt, die aufgrund von Unwissen unmöglich zu erledigen ist.
Das Grundwissen wurde sicher schon vermittelt. Der Rest liegt an dir.

[QuickAndDirty]

Also ohne mir die Aufgabenstellung angesehen zu haben, denke ich mal er soll 'nen Morsecode-Parser bauen und exemplarisch einen Suchbaum der ein schnelles parsen ermöglicht aufbauen?
Das kann ja nun wirklich nicht schwer sein wenn man die Klassen schon vor die Füße geschmissen bekommt.

Du musst es auch nicht selbst programmieren. Gut gegooglet ist auch eine legitime Lösung.

BST
Binary search tree
Morse code
Pascal
Delphi
parse

auf den ersten Blick , viele Lösungen in Java und c# ....

[Daniel]

hm - jetzt von oben herab zu sagen, es läge an ihm oder auch ohne die Aufgabenstellung gelesen zu haben, zu mutmaßen hilft niemandem.
In dem Fall ist "nichts beitragen" die beste Option.

[Sherlock]

Ich vermute das Schlimmste, denn die Aufgabe wurde gestern für heute gestellt...der Käse ist gegessen.

Was schade ist, denn interessant ist es allemal, aber ich hab jetzt keinen Antrieb, das zu programmieren...so ganz ohne Nutzen für Dritte :wink:

Interessant sind Übrigens die Möglichkeiten das Encodieren zu realisieren, also von Klartext zu Morse. Der Baum gibt das ja eigentlich nur umständlich her...eigentlich.

Hier (https://www.pocketmagic.net/morse-encoder/) hab ich eine elegante Methode gesehen, wie das Encoden ohne eine Tabelle sondern mit dem Baum ginge. Gut, der Baum wird nur einmal dabei genutzt, dann nie wieder, aber immerhin.

Sherlock

[DieDolly]

Es gibt zwei Möglichkeiten

der Lehrer hat keine Ahnung, dass das zu kompliziert für das erste Ausbildungsjahr ist
oder der Lehrer will die Spreu vom Weizen trennen und austesten, wer welche Kenntnisse hat.

[hoika]

Hallo,
wenn man sich die Aufgabenstellung liest,
soll doch kein Binärbaum selbst programmiert werden,
sondern die existierende Unit benutzt werden.

Ob das jetzt zu kompliziert ist, weiß ich nicht.

Mein Beispiel weiter oben hatte ich in 10 min zusammen.