2

所以我想做的是对链表进行排序。我被困在似乎永远不会逃脱的循环中。从示例中我发现我所要做的就是检查下一个值是否为空,那么我做错了什么?

另外,由于我不知道为什么这不会跳出循环,所以这段代码似乎应该正确地进行链表排序吗?

    public void sortFirst() { 
        do
        {
            if (first.iData >= first.next.iData)
            {
                int iTempData = first.iData;
                double dTempData = first.dData;

                first.iData = first.next.iData;
                first.dData = first.next.dData;

                Link newLink = new Link(iTempData, dTempData);
                newLink.next = first;
                first = newLink;
            }
        }
        while (first.next != null);
    }   
4

1 回答 1

1

好吧,马上,你在最后 3 行中有一个逻辑问题:

            Link newLink = new Link(iTempData, dTempData);
            newLink.next = first;
            first = newLink;

在这里,您首先设置 newLink.next =。因此它不为空。接下来设置 first = newLink。所以你可以很快看到 first.next 永远不会为空。

从我在您的循环中可以看出,您实际上并没有在列表中移动节点,而只是在节点中移动数据。在这种情况下,您只需要移动数据:

            int iTempData = first.iData;
            double dTempData = first.dData;

            first.iData = first.next.iData;
            first.dData = first.next.dData;

            first.next.iData = iTempData;
            first.next.dData = dTempData;

(并删除创建新节点的最后 3 行并将其错误地插入列表中)。当然,这有点难看。链表最酷的地方在于您可以简单地在列表中移动节点,因此您可以执行以下操作:

    current = head;
    prev = null;
    while( current != null && current.next != null ){
        next = current.next;

        if( current.iData > next.iData ) {
            // need to swap nodes
        if( prev == null ) {
            // special head case
            head = next;
            current.next = head.next;
            head.next = current;
            }
        else
        {
            prev.next = next;
            current.next = next.next;
            next.next = current;
        }
    }

    // increment pointer
    prev = current;
    current = current.next;
}
于 2012-10-20T03:58:46.700 回答