Bogue de tri par insertion de liste à liens doubles

Question

J'ai implémenté un tri d'insertion dans une liste de liens doubles (du plus élevé au plus bas) à partir d'un fichier de 10 000 ints, et de le sortir dans le fichier dans l'ordre inverse. À ma connaissance, j'ai mis en œuvre un tel programme, mais j'ai remarqué dans le fichier de sortie, un seul numéro est hors de propos. Tous les autres numéros sont dans le bon ordre.

Le numéro déplacé est un nombre répété, mais les autres répétitions de ce nombre sont dans le bon ordre. C'est juste étrange comment ce numéro est incorrectement placé. De plus, le nombre non trié n'est que 6 places désynchronisées.

J'ai regardé mon programme depuis des jours sans aucune idée de l'origine du problème, alors je me tourne vers vous pour obtenir de l'aide.

Voici le code en question,

(Note: can ma question est supprimé par moi-même plutôt mes collèges DonT thieve mon code, sinon comment peut-il être supprimé)

void DLLIntStorage::insertBefore(int inValue, node *nodeB) 
{ 
    node *newNode; 
    newNode = new node(); 
    newNode->prev = nodeB->prev; 
    newNode->next = nodeB; 
    newNode->value = inValue; 

    if(nodeB->prev==NULL) 
    { 
     this->front = newNode; 
    } 
    else 
    { 
     nodeB->prev->next = newNode; 
    } 
    nodeB->prev = newNode; 
} 
void DLLIntStorage::insertAfter(int inValue, node *nodeB) 
{ 
    node *newNode; 
    newNode = new node(); 
    newNode->next = nodeB->next; 
    newNode->prev = nodeB; 
    newNode->value = inValue; 

    if(nodeB->next == NULL) 
    { 
     this->back = newNode; 
    } 
    else 
    { 
     nodeB->next->prev = newNode; 
    } 
    nodeB->next = newNode; 
} 
void DLLIntStorage::insertFront(int inValue) 
{ 
    node *newNode; 
    if(this->front == NULL) 
    { 
     newNode = new node(); 
     this->front = newNode; 
     this->back = newNode; 
     newNode->prev = NULL; 
     newNode->next = NULL; 
     newNode->value = inValue; 
    } 
    else 
    { 
     insertBefore(inValue, this->front); 
    } 

} 
void DLLIntStorage::insertBack(int inValue) 
{ 
    if(this->back == NULL) 
    { 
     insertFront(inValue); 
    } 
    else 
    { 
     insertAfter(inValue, this->back); 
    } 
} 

ifstream& operator>> (ifstream &in, DLLIntStorage &obj) 
{ 
    int readInt, counter = 0;    

    while(!in.eof()) 
    { 
     if(counter==dataLength) //stops at 10,000 
     { 
      break; 
     } 

     in >> readInt; 

     if(obj.front != NULL) 
     { 
      obj.insertion(readInt);   
     } 
     else 
     { 
      obj.insertBack(readInt); 
     } 
     counter++; 
    }  
    return in; 
} 
void DLLIntStorage::insertion(int inValue) 
{ 
    node* temp; 
    temp = this->front; 

    if(temp->value >= inValue) 
    { 
     insertFront(inValue); 
     return; 
    } 
    else 
    {  
     while(temp->next!=NULL && temp!=this->back) 
     { 
      if(temp->value >= inValue) 
      { 
       insertBefore(inValue, temp); 
       return; 
      } 
      temp = temp->next; 
     } 
    } 

    if(temp == this->back) 
    { 
     insertBack(inValue); 
    } 
} 

Merci pour votre temps.

Answer 1

Je n'aime pas cette partie

else 
{  
    while(temp->next!=NULL && temp!=this->back) 
    { 
     if(temp->value >= inValue) 
     { 
      insertBefore(inValue, temp); 
      return; 
     } 
     temp = temp->next; 
    } 
} 

if(temp == this->back) 
{ 
    insertBack(inValue); 
} 

Imaginez ce qui se passe si inValue est supérieure à toutes les valeurs sauf valeur this-> back>. Il est inséré à la fin au lieu de cela avant le retour. En passant, vous insérez des entiers égaux dans l'ordre inverse, ils sont lus. Pour les entiers, cela n'a pas beaucoup d'importance, mais cela pourrait être le cas si vous insériez d'autres objets. Je voudrais changer le code de la méthode d'insertion à ceci:

node* temp; 
temp = this->front; 
while(temp!=NULL) 
{ 
    if(temp->value > inValue) 
    { 
     insertBefore(inValue, temp); 
     return; 
    } 
    temp = temp->next; 
} 
insertBack(inValue); 

Answer 2

Juste quelques remarques. Cela n'empêchera pas l'intérieur de la boucle de voir une erreur EOF. Cela n'empêchera pas l'intérieur de la boucle de voir une erreur EOF. Vous voulez

while (in >> readInt) 

---

En outre,

if(this->front == NULL) 

et

void DLLIntStorage::insertion(int inValue) 
{ 
    node* temp; 
    temp = this->front; 

    if(temp->value >= inValue) 

ne se mélangent pas. Soit le front peut être NULL, soit il ne peut pas. De même, vous devez décider d'utiliser temp->next!=NULL ou temp!=this->back, mais pas les deux, comme condition de fin de boucle.

---

Je dirais que certaines incohérences entre plusieurs conventions de liaison est à l'origine de la valeur errante pour obtenir poussé dans le milieu de la liste.