zwei listen zusammenfuehren
-
hola leute
gibt es einen algo mit dem man 2 sortierte listen, ohne zuhilfenahme einer dritten liste, zusammenfuegen kann ? genauer gesagt hab ich die zwei listen hintereinander in einem vector stehen. also technisch gesehen is es dann eine liste. naja, ich hoff ihr wisst was ich meine.
cermy
Meep Meep
-
Gehst halt immer durch Liste eins, bis du an der Stelle bist, wo du Element 1 aus Liste 2 einfügst, usw. bist Liste 2 leer ist.
Bye, TGGC (Wähle deine Helden)
-
dmit es keine missverstaendnisse gibt:
es ist ein array, in dem 2 sortierte arrays vorhanden sind. listen meinte ich nicht im sinne von std::list.
@TGGC so funkt des leider nicht.
Meep Meep
-
wenn du arrays meinst, dann sag nicht listen.
aber dann geht es nicht performant ohne 3. array, weil du sonst sehr viel kopieren müsstest...
-
Es ist nicht besonders gut Listen so in den Vektoren zu halten. Dafür gibt es schliesslich std::list, dass angepasste Methoden bietet und Listenoperationen effizient ausführen kann.
Aber in diesem Fall gibt es wohl eine Lösung:
1. Du machst den ersten Vektor groß genug für beide Listen.
2. Du legst dir Iteratoren A,B auf die letzten elemente beider Listen vor der Vergrößerung an.
3. Du erzeugst dir einen Iterator Z auf das letzte Element der vergrößerten ersten Liste
4. Solange es Elemente in einer Liste gibt, nimmst du das größere der beiden und fügst es dort ein wohin Z zeigt. Dann dekrementierst du Z und den Iterator, dessen Element du genommen hast.Dieser Algorithmus sollte dafür sorgen, dass in der ersten Liste, dann die Elemente sortiert sind und dass keines überschrieben wurde.