insertion trier sur liste chaînée

Question

// J'ai écrit du code java pour la méthode d'insertion sur une liste doublement chaînée mais il y a une boucle // infinie quand je l'exécute. J'essaie de trouver un bug, mais je n'ai pas trouvé jusqu'à présent. Aucune suggestion? // il appelle une fonction d'assistance

public IntList insertionSort () { 
    DListNode soFar = null; 
    for (DListNode p=myHead; p!=null; p=p.myNext) { 
     soFar = insert (p, soFar); 
    } 
    return new IntList (soFar); 
} 


// values will be in decreasing order. 
private DListNode insert (DListNode p, DListNode head) { 
    DListNode q=new DListNode(p.myItem); 
    if(head==null){ 
     head=q; 
     return head; 
    } 
    if(q.myItem>=head.myItem){ 
     DListNode te=head; 
     q.myNext=te; 
     te.myPrev=q; 
     q=head; 
     return head; 
    } 
    DListNode a; 
    boolean found=false; 
    for(a=head; a!=null;){ 
     if(a.myItem<q.myItem){ 
      found=true; 
      break; 
     } 
     else{ 
      a=a.myNext; 
     } 
} 
    if(found==false){ 
     DListNode temp=myTail; 
     temp.myNext=q; 
     q.myPrev=temp; 
     myTail=q; 
     return head; 
    } 
    if(found==true){ 
    DListNode t; 
    t=a.myPrev; 
    a.myPrev=q; 
    t.myNext=q; 
    q.myPrev=t; 
    q.myNext=a; 
} 
    return head; 

}

Answer 1

Votre code est un peu difficile à lire, mais j'ai remarqué quelques problèmes

Première: manutention le cas où vous sont en insérant un nombre en tête de la liste:

if(q.myItem>=head.myItem){ 
     DListNode te=head; 
     q.myNext=te; 
     te.myPrev=q; 
     q=head; 
     return head; 
    } 

spécifiquement la ligne q=head; et le retour. q=head peut être retiré, et il devrait retourner q pas la tête parce que q est la nouvelle tête. Je pense que ce que vous vouliez faire était head=q; return head;. Le code actuel ajoutera essentiellement le nouveau noeud sur le front mais ne retournera jamais la tête mise à jour pour qu'ils "tombent du bord" d'une certaine manière.

Deuxième: Je suppose myTail est une référence de nœud que vous souhaitez conserver comme myHead à la liste originale. Je ne pense pas que vous vouliez l'utiliser comme vous l'êtes pour la liste triée que vous construisez. Lorsque vous parcourez en boucle la recherche de l'emplacement à insérer dans la nouvelle liste, utilisez-la pour déterminer la référence de queue et utilisez-la à la place.

DListNode lastCompared = null; 
for(a=head; a!=null; a=a.myNext) { 
    lastCompared = a; 
    if(a.myItem<q.myItem) { 
     break; 
     } 
    } 
if(a) 
    { 
    // insert node before a 
    ... 
    } 
else 
    { 
    // smallest value yet, throw on the end 
    lastCompared.myNext = q; 
    q.myPrev = lastCompared; 
    return head; 
    } 

Enfin font myPrev sûr et myNext sont correctement initialisé à NULL dans le constructeur de DListNode.

déni de responsabilité Je n'ai pas eu l'occasion de tester le code que j'ai ajouté ici, mais j'espère que cela vous fera au moins penser à la solution.

---

Un couple de notes de style (juste un sidenote):

1. le> Format de retour répété ne sont pas les si- plus propre à mon avis. J'essaie généralement de limiter les points de sortie dans les fonctions
2. Il y a beaucoup de variables intermédiaires utilisées et les noms sont superbes . À tout le moins essayer et utiliser des noms de variables plus descriptifs .
3. Les commentaires sont toujours une bonne idée. Assurez-vous simplement qu'ils n'expliquent pas simplement ce que fait le code - au lieu de cela, essayez et exprimez ce qui est en train d'être accompli.