Hallo Ihr Nerds,
Ich habe ein Problem mit einem meiner Programme:
Ich möchte ein Programm schreiben, das aus einer Liste von Wörtern Kreuzworträtsel zusammenstellt. Für den Algorithmus brauche ich eine Datenstruktur, in der ich alle möglichen Überschneidungen von zwei Wörtern speichern kann. Ich brauche also eine Dimensoin für das erste Wort, eine weitere für das zweite und dann noch eine dritte Dimension für die verschiedenen Kombinationen, die möglich sind. Da vor allem letztere sehr unterschiedlich groß sein kann, je nachdem welche Wörter man kreuzt ("Rhabarbermarmelade" und "Hasenbraten" haben mehr Möglichkeiten als "Boot" und "Pfund"), wollte ich kein dreidimensionales Array aufstellen. Da ich sowieso schon LinkedLists verwende habe ich es mit LinkedList[][] versucht, was jedoch mit der Bemerkung "generic array creation" abgewimmelt wurde. Auch drei LinkedLists ineinandergeschachtelt wollte nicht compiliert werden.
Die Extremlösung wäre ein Array mit [Wortzahl] [Wortzahl - 1] [Länge_des_längsten_Wortes * Länge_des_zweitlängsten_Wortes] als Dimensionen. Somit wären dann die theoretisch möglichen maximalen Ausmaße berücksichtigt.
Meine Frage ist nun: Wie kann ich eine möglichst platzsparende Datenstruktur erstellen, die meinen Anforderungen genügt? Ich brauche theoretisch eine dreieckige Form in den ersten beiden Dimensionen und eine erweiterbare Liste, möglichst mit individueller Länge in der dritten.
(Java) Problem: "generic array creation"
- Tobias1595
- Geschlossen
-
Ich würde das eher mit einer LinkedList einer Klasse lösen, der du im Konstruktor einfach die beiden Wörter übergibst, die Klasse sich dann alle Überschneidungen ausrechnet und diese in eine LinkedList oder in einem ähnlich dynamischen Speicherobjekt ablegt.
Um das Grafisch darzustellen:
Code
Alles anzeigenLinkedList<CrossComparer> lComparisons { [0] { String strWord1; String strWord2; LinkedList<CrossOverlap> lOverlaps { [0] { int nVal1; int nVal2; } } } }Mit dieser dynamischen Variante wärst du am speicherschonendsten und du kannst dir auch ne Menge Hilfsfunktionen basteln :3
EDIT: ArrayList wäre noch etwas schlanker als LinkedList
-
Ok, ich verstehe, was Du meinst.
Und wie kann ich dann schnell und einfach auf die Liste lOverlaps für ein bestimmtes Wörterpaar zugreifen?
Die Liste lComparisons wird durch die systematische Aufstellung halbwegs geordnet sein. Wenn die Worte sich nicht überschneiden können, ist lOverlaps leer, aber das lComparisons existiert. Das ganze ist dreieckig aufgebaut, wenn man es gedanklich nach erstem und zweitem Wort tabellarisch ordnen würde. Für die Paare mit dem ersten Wort vorne kann man das zweite Wort minus 1 als Index nehmen. Ist das zweite Wort das vordere, das ich suche, muss ich die Wortzahl zum Index addieren und 2 subtrahieren. In der dritten Zeile wären das 2 mal die Wortzahl minus 4, in der vierten 3 mal Wortzahl minus 7. Ich suche also nach
(IndexVonWort1) * Wortzahl - (Dreieckszahl(IndexVonWort1) + 1) + IndexVonWort2
Ja, Danke nochmal!
-
-
AlexVermilion
Hat das Thema aus dem Forum Alte Threads nach Technische Probleme verschoben.
