insertion сортировать по связанному списку

Question

// Я написал код Java для метода вставки в дважды связанном списке, но при его запуске существует бесконечный цикл //. Я пытаюсь найти ошибку, но пока не нашел. какие-либо предложения? // это вызов вспомогательной функции

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

Ваш код является немного трудно прочитать, но я заметил несколько проблем

Первый: обработки случае, когда вы вносят номер в начало списка:

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

В частности, линия q=head; и возврат. q=head может быть удален, и он должен вернуть q не головой, потому что q - это новая голова. Я думаю, что вы хотели сделать, это head=q; return head;. Текущий код по существу добавит новый узел вперед, но никогда не вернет обновленную голову, чтобы они «упали с края».

Второго: Я предполагаю, myTail некоторые опорный узел вы оставляете как myHead к первоначальному списку. Я не думаю, что вы хотите использовать его так же, как и для сортированного списка, который вы строите. Когда вы просматриваете место для вставки в новый список, используйте это, чтобы определить ссылку на хвост и использовать это вместо этого.

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; 
    } 

Наконец убедитесь myPrev и myNext будут должным образом инициализируется нулем в конструкторе DListNode.

отказ от ответственности У меня не было возможности проверить код, который я добавил здесь, но, надеюсь, он по крайней мере заставляет задуматься о решении.

---

Пара стилистические ноты (только Sidenote):

1. неоднократное если-> возвращение формат не является самым чистым на мой взгляд. Обычно я пытаюсь ограничить точки выхода в функциях
2. Используется много промежуточных переменных, и имена супер неоднозначны. По крайней мере, попробуйте использовать более дескриптивные имена переменных .
3. комментарии всегда являются хорошей идеей. Просто убедитесь, что они не просто объясняют, что делает код - вместо этого попробуйте и передать мыслительный процесс и что нужно сделать.