1

是的，这是我的家庭作业项目之一 - 实施基于单链表的循环链表。这很简单，代码很容易阅读。我所有的属性都是公开的，以避免getter和setter以及私人业务。就本项目而言，公众就足够了。

我在属性字段中初始化了我的nItems计数器（列表中的项目数）和链接头，但稍后我将通过在构造函数中初始化它来更改它。

我的step()方法似乎根本不起作用。我的编译器只是冻结了一会儿，然后什么都没有出现。如果我调用它 4 次，这就是 step() 方法的工作方式：

List: 40 80 30 20 10 70 50 
List: 80 30 20 10 70 50 40 
List: 30 20 10 70 50 40 80 
List: 20 10 70 50 40 80 30

Find()方法可以正常工作，只要我们要搜索的值在链接列表中。如果不是，它将永远持续下去。如果这是我的列表，如果您搜索不存在的值（我逐步调试它）， find()方法会发生这种情况：

70 60 50 40 30 20 10 10 10 10 10 10 10 10...and 10 forever

原因：如果我们正在搜索的键值不存在，它将永远不会从 while 循环中退出，因此永远重复current = current.next。

while(current.dData != key) {
current = current.next;

我的删除方法说它删除了值 60，就像我想要的那样，但这是我得到的：

Deleted link with key 60
70 60 40 30 20 10       // lie! it deletes 50 instead of 60

另请查看我的 display() 和 insert() 方法。它们对我来说看起来不错，但我可能错了，这可能是我在使用 find() 和 delete() 方法时遇到的所有问题的根源。

提前非常感谢你！！！

class Link {
    public int dData;
    public Link next;

    public Link(int dd) {
        dData = dd;
    }

    public void displayLink() {
        System.out.print(dData + " ");
    }
}

class CircList {
    public Link head = null;
    int nItems = 0;

    public boolean isEmpty() {
        return (nItems == 0);
    }
    // INSERT
    public void insert(int key) { 

        Link current = new Link(key);
        if(isEmpty())
            head = current;

        current.next = head;
        head = current;
        nItems++;
    }
    // STEP
    public void step() {
        Link current = head;
        do {
            current = current.next;
        } while(current != head);
    }
    // FIND
    public Link find (int key) {
        Link current = head;
        while(current.dData != key) {
            current = current.next;
        }
        return current;
    }
     // DELETE
    public Link delete(int key) {
    Link current = head;
    while(current.dData != key) {
        current = current.next;
    }
    if(current == head)
        head = head.next;
    else {
        current.next = current.next.next;
        nItems--;
    }
    return current;
}
    // DISPLAY
    public void displayList() {
        Link current = head; // start at beginning
        int counter = nItems;
        while(true) {
            if(counter != 0) {
                current.displayLink();
                current = current.next; // move to next link
                counter--;
            }
            else 
                break;
        }
    }
}

class CircListApp {
    public static void main(String[] args) {
    Link f, d;
    CircList theList = new CircList();


    theList.insert(10);      // insert items
    theList.insert(20);
    theList.insert(30);
    theList.insert(40);
    theList.insert(50);
    theList.insert(60);
    theList.insert(70);

    //System.out.println(theList.nItems + " ");
    theList.displayList();              // display list

    System.out.println("");

    f = theList.find(30);               // find item
    if( f != null)
       System.out.println("Found link with key " + f.dData);
    else
       System.out.println("Can't find link with key 30");

//    theList.step();

//
//    System.out.println("Inserting link with key 80");
//    theList.insert(80);
//    theList.displayList();              // display list
//
    d = theList.delete(60);             // delete item

    if( d != null )
       System.out.println("Deleted link with key " + d.dData);
    else
       System.out.println("Can't delete link with key 60");
    theList.displayList();              // display list
//
//    f = theList.find(99);               // find item
//    if( f != null)
//       System.out.println("Found link with key " + f.dData);
//    else
//       System.out.println("Can't find link with key 99" );
//    theList.displayList();              // display list
//
//    d = theList.delete(13);             // delete item
//    if( d != null )
//       System.out.println("Deleted link with key " + d.dData);
//    else
//       System.out.println("Can't delete link with key 13");
//    theList.displayList();              // display list
//
//    System.out.println("Stepping through list");
//    for(int j=0; j<theList.getSize; j++)
//       {
//       theList.step();
//       theList.displayList();
//       }
//
//    System.out.println("Will delete and step one by one");
//    while(theList.isEmpty() == false)
//       {
//       theList.delete();
//       theList.step();
//       theList.displayList();
//       }
    }  // end main()

}
4

1 回答 1

1

对于您的“步骤”方法：您创建一个名为 current 的本地引用，它最初指向 head。后

current = current.next

它引用了 head 的继任者。在下一步中，它引用了它的继任者，依此类推。但它是本地参考，因此您不会更改列表中的任何内容。

正如我从你想要的输出中推断的那样，你必须做的很简单

if( head != null && head.next != null )
    head = head.next

下一步：对于您的查找方法：嗯，从您的循环条件来看，很明显，如果键不在列表中，它将永远运行，因为这是您唯一的中断条件。您应该考虑一种机制，使其在您查看完列表中的每个项目后停止。提示：看看你在你的 step() 方法版本中做了什么。

对于您的删除方法：第一部分（部分）没问题（它与您的查找方法具有相同的无限循环问题）。您所做的是遍历列表，直到当前的数据等于键。没关系。

但是现在， current 是对要删除的元素的引用。但是您所做的是将 current.next 设置为 current.next.next，这意味着您正在删除 current 的后继者，而不是 current 本身！在您搜索密钥的循环中，您必须跟踪前任，以便您可以将前任.next 更改为 current.next，这是您真正想要做的。

然后，当然，您必须检查它是否是您要删除的头，如果是这样，您必须将其设置为前任或后继。

最后，我发现您的 insert() 方法有问题！我不明白这如何产生循环链表，因为您让新插入的元素指向头部并使其成为新头部，但没有任何东西指向它。所以你只创建一个单链表？您在 head （ current.next = head ）“之前”插入一个新项目，但是您还应该让 head 的前任现在指向新项目 current！

于 2010-11-16T18:17:47.380 回答