Sortier zwei verkettete Listen nach Speicherplatz

Question

Ich brauche zwei zu verschmelzen doppelt verknüpfte Listen, aber nicht durch ihre Werte (die Listen sind nicht sortiert). Ich möchte eine einzige Liste erhalten, die alle Knoten von den beiden, aber in der Reihenfolge, in der sie erscheinen im Speicher.

Vielleicht hilft das Bild mehr: http://img140.imageshack.us/i/drawing2.png/

Gibt es einen Algorithmus (vorzugsweise ein schnelles), die diese Art von Merge tun kann? Vielleicht ist dies ein wenig hilfreich:

• der Startknoten der Listen ist immer vor den anderen.
• eine Liste kann bis zu 8192 Knoten haben.
• Ich weiß, wo die Knoten im Speicher befindet, weil die Listen in einem großen Speicherblock Spur freier Position halten (in einem Speicherzuordner verwendet wird).
• Ich arbeite in C ++.

Vielen Dank im Voraus!

Answer 1

Nun, es klingt wie Sie nicht std::list verwenden, so dass ich mit der generischen Lösung gehen. Da Ihre Anforderung die Listen zu verschmelzen, sondern haben die Knoten in der Reihenfolge der dort physischen Ort in Erinnerung sein. Sie können die beiden Listen wahrscheinlich nur anhängen, dann die Knoten nach Adressen der Knoten sortiert werden.

siehe: http: //www.chiark.greenend. org.uk/~sgtatham/algorithms/listsort.html für einen Sortieralgorithmus für verkettete Listen.

Beim Sortieren statt Vergleich node1->value < node2->value nur tun (size_t)node1 < (size_t)node2 , oder etwas dieser Art.

Answer 2

„Merge“ ist ein bisschen hier irreführend, da Sie nur sortierten Listen zusammenführen können, und bei Ihnen sind nicht sortiert.

Sie müssen sortieren, nicht fusionieren.

Setzen Sie die Zeiger auf Knoten in einen Vektor. std :: sort auf dem Vektor verwendet werden, und einen Vergleich Funktor übergeben, die jeden Zeiger wirft size_t (glaube ich) und vergleicht die daraus resultierenden Zahlen.

Sie können dann Ihre verknüpften Listen entsprechend der resultierenden Reihenfolge in dem Vektor neu anordnen.