0

//I wrote java code for insertion method on doubly linked list but there is a infinite loop //when I run it. I'm trying to find a bug, but have not found so far. any suggestions? //it is calling a helper function

 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;

}

4

1 回答 1

1

您的代码有点难以阅读，但我注意到了一些问题

首先：处理在列表开头插入数字的情况：

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

特别是线路q=head;和回报。q=head可以删除，它应该返回qnot head 因为q是新的 head。我想你的意思是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 的构造函数中正确初始化为 null。

免责声明我没有机会测试我在这里添加的代码，但希望它至少能让你思考解决方案。

几个文体注释（只是一个旁注）：

  1. 在我看来，重复的 if->return 格式并不是最干净的。我通常会尝试限制函数中的退出点
  2. 使用了很多中间变量，并且名称非常模糊。至少尝试使用一些更具描述性的变量名称。
  3. 评论总是一个好主意。只要确保他们不只是解释代码在做什么 - 而是尝试传达思维过程以及试图完成的事情。
于 2013-08-08T05:25:19.823 回答