C++ Bubble trier une liste doublement chaînée

Question

Je sais que le tri des bulles n'est probablement pas le moyen le plus rapide de le faire, mais c'est acceptable. J'ai juste du mal à ajuster l'algorithme pour doubler les listes de tableaux.

Mes listes doubles liées ont un type int et une chaîne de type pour contenir un nombre et un mot. Ma liste a été triée avec un tri d'insertion que j'ai écrit pour trier par ordre alphabétique, maintenant je dois réordonner numériquement ma liste double liée, le plus grand au moins. Mon problème est de savoir comment exécuter cette boucle afin qu'elle soit correctement triée et non pas une seule fois.

Voici ce que j'ai réussi à descendre jusqu'à présent:

void DblLinkedList::ReorderListNumeric() 
{ 
dummy = new Node(); 
temphead = head; 
temp = head->next; 

while(tempTwo->next != NULL) 
{ 
    if(temp->wordCount < tempTwo->wordCount) 
    {    
     dummy->word = tempTwo->word; 
     dummy->wordCount = tempTwo->wordCount; 

     tempTwo->word = temp->word; 
     tempTwo->wordCount = temp->wordCount; 

     temp->word = dummy->word; 
     temp->wordCount = dummy->wordCount; 
    } 
    temp = tempTwo; 
    tempTwo = tempTwo->next; 
} 
} 

Answer 1

Mon point névralgique est comment exécuter cette boucle afin qu'il soit bien réglé à fond et pas seulement une fois.

Si vous avez déjà une boucle qui avec succès faire un passage et d'échange est correct, la façon habituelle de faire des passes multiples est relativement efficace:

set swapped = true 
while swapped: 
    set swapped = false 
    do your one pass, setting swapped to true whenever you swap 

On évite ainsi le n naïf solution les débutants commenceront invariablement avec.

Et c'est tout.

Vous avez défini swapped sur true de manière à ce que vous accédiez initialement à la liste, puis définissez-le sur false immédiatement, à l'intérieur de la boucle.

Votre passe unique sera définie swapped uniquement si un échange a lieu. Si aucun swap n'a lieu dans votre passe, la liste est triée et vous quittez la boucle.

Si un swap a lieu, le drapeau swapped est réglé et vous devrez exécuter une autre passe. En effet, l'échange pourrait être à la fin de la liste et invalider l'ordre plus tôt, tels que:

Initial: 1 2 3 4 6 7 5 
    Pass1: 1 2 3 4 6 5<=>7 (swap) 
    Pass2: 1 2 3 4 5<=>6 7 (swap) 
    Pass3: 1 2 3 4 5 6 7 (no swap, so exit loop) 

Donc, en supposant que votre code est correct, commencez par quelque chose comme:

void DblLinkedList::ReorderListNumeric() { 
    Node *ptr, *dummy = new Node(); 

    // Zero or one element, no sort required. 

    if (head == NULL) return; 
    if (head->next == NULL) return; 

    // Force initial entry. 

    int swapped = 1; 
    while (swapped) { 
     // Flag as last time, then do one pass. 

     swapped = 0; 

     ptr = head; 
     while (ptr->next != NULL) { 
      if (ptr->wordCount < ptr->next->wordCount) { 
       // Swapping, need another pass. 

       swapped = 1; 

       dummy->word = ptr->word; 
       ptr->word = ptr->next->word; 
       ptr->next->word = dummy->word; 

       dummy->wordCount = ptr->wordCount; 
       ptr->wordCount = ptr->next->wordCount; 
       ptr->next->wordCount = dummy->wordCount; 
      } 
      ptr = ptr->next; 
     } 
    } 
} 

Answer 2

Utilisez 2 boucles pour trier la liste à fond (je ne considère pas l'efficacité ici car ce n'est pas important pour vous en ce moment). Donc itérer la liste des pointeurs avec 2 comme vous le feriez avec des tableaux -

void DblLinkedList::ReorderListNumeric() 
{ 
    NODE* temphead = NULL; // assuming your list is made of NODEs 
    NODE* temp = NULL; 

    for(temphead = head; temphead && temphead->next != NULL; ++ temphead) 
    { 
     for(temp = temphead->next; temp && temp->next != NULL; ++temp) 
     { 
      if(temphead->wordCount < temp->wordCount) 
      { 
       std::string dummyWord = temp->word; 
       int dummyCount = temp->wordCount; 

       temp->word = temphead->word; 
       temp->wordCount = temphead->wordCount; 

       temphead->word = dummyWord; 
       temphead->wordCount = dummyCount; 
      } 
     } 
    } 
} 

BTW, Pourquoi voulez créer un nœud factice pour échanger, quand tout ce que vous voulez faire est de changer les valeurs.