Merge-Sortieren einer verketteten Liste
Bin ich verpflichtet, zu Sortieren, eine Verknüpfte Liste mit merge-sort. Ich habe diesen code, aber ich bin in einem seltsamen Fehler.
Meiner verlinkten Liste ist bevölkert von Zufallszahlen. Jedoch, nach dem Sortieren, es zeigt nur zahlen, die größer sind als das erste element der verketteten Liste, in sortierter Reihenfolge.
Hier ist mein code:
node* MergeSort(node *my_node)
{
node *secondNode;
if (my_node == NULL)
return NULL;
else if (my_node->next == NULL)
return my_node;
else
{
secondNode = Split(my_node);
return Merge(MergeSort(my_node),MergeSort(secondNode));
}
}
node* Merge(node* firstNode, node* secondNode)
{
if (firstNode == NULL) return secondNode;
else if (secondNode == NULL) return firstNode;
else if (firstNode->number <= secondNode->number) //if I reverse the sign to >=, the behavior reverses
{
firstNode->next = Merge(firstNode->next, secondNode);
return firstNode;
}
else
{
secondNode->next = Merge(firstNode, secondNode->next);
return secondNode;
}
}
node* Split(node* my_node)
{
node* secondNode;
if (my_node == NULL) return NULL;
else if (my_node->next == NULL) return NULL;
else {
secondNode = my_node->next;
my_node->next = secondNode->next;
secondNode->next = Split(secondNode->next);
return secondNode;
}
}
InformationsquelleAutor xbonez | 2011-04-12
Du musst angemeldet sein, um einen Kommentar abzugeben.
Habe ich versucht den code und es funktioniert perfekt.
Haben Sie bei uns die richtige Liste am Ende?
Ihre neuen Kopf der Liste ist nicht der vorherigen Kopf, aber der return-Wert
die Merge-Funktion.
und printList() ist die offensichtliche Funktion:
InformationsquelleAutor tgmath