Sortieren von zwei verknüpften Listen nach Speicherort

Question

Ich muss zwei doppelt verknüpfte Listen zusammenführen, aber nicht nach ihren Werten (die Listen sind nicht sortiert). Ich möchte eine einzelne Liste erhalten, die alle Knoten von den beiden hat, aber in der Reihenfolge, in der sie im Speicher erscheinen.

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 das ein bisschen 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 befinden, da die Listen den freien Speicherplatz in einem großen Speicherblock verfolgen (in einem Speicherzuordner verwendet).
• Ich arbeite in C++.

Vielen Dank im Voraus!

Answer 1

Nun, es klingt, als ob Sie nicht std::list verwenden, also werde ich mit der generischen Lösung gehen. Da ist Ihre Anforderung, die Listen zusammenzuführen, aber die Knoten in der Reihenfolge ihres physischen Speicherorts zu haben. Sie können wahrscheinlich nur die beiden Listen anhängen und dann die Knoten nach der Adresse der Knoten sortieren.

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

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

Answer 2

"Merge" ist hier ein bisschen irreführend, da Sie nur sortierte Listen zusammenführen können, und Ihre werden nicht sortiert.

Sie müssen sortieren, nicht zusammenführen.

Versetzen Sie die Zeiger zu Knoten in einen Vektor. Verwenden Sie std :: sort für den Vektor und übergeben Sie einen Vergleichsfunktor, der jeden Zeiger auf size_t (ich denke) umsetzt und die resultierenden Zahlen vergleicht.

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