0

我似乎在完成这项任务。即使把它画出来似乎也没有给我一个可行的解决方案。有人可以帮我找到我的思维过程在这里崩溃的地方吗？

// method receives node ins to be inserted
// and node prev in front of which ins should be inserted
public void insertIntermediate(DLLNode ins, DLLNode prev)
{
    ins.pred = prev ; // update node ins' predecessor information
    ins.succ = prev.succ ; // update node ins' successor information 
    prev.succ = ins ; // update list's information
    prev.succ.pred = ins ; // update list's information
}

[EDIT2]（删除了 edit1 以减少混乱）

@Andrew，好的，我找到了：上面的问题是第 3 行和第 4 行的顺序：

第 3 行导致我无法访问 prev.succ.pred。

通过交换两条线，我解决了这个问题。感谢您的提示！

附加问题：

不过，我遇到了另一个奇怪的问题，这就是为什么我浪费了这么多时间来寻找解决方案：如果我再次重新插入一个已经存在的元素，由于某种原因，当我打印它时，整个事情都会进入无限循环......例如

myList.addBeforeFirst(B) ;
myList.addBeforeFirst(B) ;

导致循环，而：

myList.addBeforeFirst(B) ;
myList.addBeforeFirst(C) ;

工作正常

这是方法：

public void addBeforeFirst(DLLNode ins)
{
    ins.succ = first ;
    ins.succ.pred = ins ;
    first = ins ;
}

和节点：

DLLNode B = new DLLNode("Hi", null, null) ;
DLLNode C = new DLLNode("Salut", null, null) ;

为什么会这样？

4

1 回答 1

1

这是一个双向链表，是吗？这意味着什么？确保以正确的顺序更新所有相关链接。另外，确保所有相关节点都存在。

编辑：

让我们按顺序浏览您的陈述。

在开始之前，您有prev，其属性succ指向后继节点。（或者是吗？会有例外吗？如果存在这种例外，您将如何处理？） prev.succ.pred应该与指向后继节点的情况prev相同prev.succ。

现在，您的前两个语句设置ins.pred和ins.succ. 这基本上是正确的想法，但请参阅我上面的问题。

现在，您设置prev.succ为ins. 专注于这个声明。你现在有丢失的信息吗？那么下面的语句究竟做了什么？是你想要的吗？

我认为这是在不完全放弃解决方案的情况下我能做的最好的事情。

编辑无限循环问题：

您遇到的问题是按值传递参数和按引用传递参数之间的区别。因为您是通过引用传递的，所以您两次传递了对同一个对象 (B) 的引用。这意味着您最终执行了以下操作：

第一次调用：

B.succ = first;
B.succ.pred = B; /* why not just first.pred = ins? */
first = B;

现在，第一个设置为 B。所以，第二个调用，使用 B：

B.succ = B;
B.succ.pred = B; /* so, now B is its own pred and succ */
first = B; /* no change here */

所以，现在，first 是 B，first.succ 是 B，first.succ.succ 是 B，等等，因此是无限循环。

于 2011-03-21T22:03:50.810 回答