2

我写了以下程序：

public class DLinkedList<T extends Comparable<T>> {

    private class DNode<T> {
        private DNode<T> prev, next;
        private T nodeValue;
        public DNode() {
            nodeValue = null;
            next = prev = this;
            }

        public DNode(T val) {
            nodeValue = val;
            next = prev = this;
            }
        }

    private DNode<T> header;

    private int size;

    public DLinkedList() {
        header = new DNode<T>();
        size = 0;
    }

    public Boolean empty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void addOrder(T val) {
        DNode<T> newNode = new DNode<T>(val);
        DNode<T> curr = header.next;
        int count = 0;

        while (curr != header &&
            curr.nodeValue.compareTo(newNode.nodeValue) < 0 ) {

            curr = curr.next;
            newNode.prev = curr;
            newNode.next = curr.next;
            newNode.next.prev = curr;
            count++;
        }

        if (count == 1) {
            newNode.prev = curr;
            newNode.next = curr.prev;
            curr.prev.next.next = newNode;

        } else {
            newNode.prev = curr.prev;
            newNode.next = curr;
            curr.prev.next = newNode;
            count++;
        }
    }

    public String toString() {
        String str = "";
        DNode<T> curr = header.next;
        while (curr != header) {
            str += curr.nodeValue + ", ";
            curr = curr.next;
        }
        if (str.length() > 0) {
            return str.substring(0, str.lastIndexOf(", "));
        } else {
            return str;
        }
    }

    public static void main(String[] args) {
            DLinkedList<String> d = new DLinkedList<String>();
            d.addOrder("t");
            d.addOrder("y");
            d.addOrder("e");
            d.addOrder("b");
            d.addOrder("p");
            System.out.println("List 1: t, y, e, b, p" + "\nList 1 added and sort : " +d);
    }
}

我对如何解决我的问题感到困惑/迷失。我想创建一个包含字符串值的节点的双链表，当我将这些字符串值添加到列表中时，列表会通过插入排序的方式对其进行自动排序。

我从一个具有空值的节点调用标头开始。然后，当我使用该方法将字符串“t，y，e，b，p”添加到列表中时，addOrder(T val)一切似乎都有效。它将按“b、e、p、t、y”的排序顺序打印出来。

如果我决定最后不打印“p”而是执行“t，y，e，b，c”，则会出现问题，我得到的打印结果是“b，c”而不是“b，c，e” , t, y”。如果我在列表末尾添加“a”而不是“p”或“c”，则所有内容似乎都可以很好地打印“a、b、e、t、y”。所以它似乎适用于所有不是“c，d，e”的东西。似乎我需要编写一个方法来添加一个新节点，该新节点将在它们之间传递，我现在不知道该怎么做。

如果我决定添加字符串“t、y、e、v、p”，则会出现另一个问题。看起来这只是打印“e，p”。看起来它添加了“t，y，e，v”但是当“p”进来时，它删除了“t，y，v”并留下了“e，p”。

似乎我无法在“ft”之间添加任何内容，但在此之前或之后的任何内容都可以。我感觉它与我的索引“curr”有关，它可能与我的节点标头卡住了。

4

2 回答 2

1

我同意代码有点混乱，您应该从 while 循环中删除分配，但修复似乎很简单。

在循环之后的部分中，您需要在不进行计数检查的情况下切换分配：

newNode.prev = curr.prev;
newNode.next = curr;
curr.prev.next = newNode;
curr.prev = newNode;

在插入“p”时使用“t, y, e, v, p”的示例中，当前光标位于字母“t”上。此时，您希望“p”指向“t”，而前一个是“t”，在本例中为“e”。

我还没有测试你的其他场景，但这看起来像你所缺少的。

于 2012-11-28T18:26:57.523 回答
1

您的某些代码似乎有些混乱。在找到插入点之前，您看起来像是一个循环，用于跳过列表，但它同时更改了新节点的指针和现有的指针。我只会curr = curr.next在那个循环中，并且在你找到插入位置之前对新节点的指针或现有列表不做任何更改，然后记住你总共需要更改四个指针：下一个和上一个新节点，其前任中的下一个指针，以及其后继中的前一个指针。

            while (curr != header &&
                    curr.nodeValue.compareTo(newNode.nodeValue) < 0 ) {

                    curr = curr.next;
                    newNode.prev = curr;
                    newNode.next = curr.next;
                    newNode.next.prev = curr;
                    count++;
            }

我有一个关于如何调试的网页，您可能会觉得有帮助。

于 2012-11-28T18:10:09.453 回答