双链表上的BubbleSort [英] BubbleSort on Double Linked List

问题描述

public Node get(int i) {  
    if (!isEmpty()) {  
        int j = 0;  
        Node element = head;  
        while (j++ < i) {  
            element = element.getNext();  
            if (element == null)  
                return null;  
        }  
        return element;  
    }  
    return null;  
}  



private void bubbleSort() {  
    for (int i = 0; i < size - 1; i++) {  
        boolean changed = false;  
        for (int j = 0; j < size - i - 1; j++) {  
            if (get(j + 1) != null) {  
                if (get(j).getValue() > get(j + 1).getValue()) {  
                    //System.out.println("Swapping: " + get(j).getValue() + " : " + get(j + 1).getValue());  
                    swap(get(j), get(j + 1));  
                    changed = true;  
                }  
            }  
        }  
        if (!changed)  
            return;  
    }  
}  

public void swap(Node first, Node mid) {  
    if (first == head)  
        head = mid;  
    if (mid == tail) {  
        tail = first;  
    }  
    first.setNext(mid.getNext());  
    mid.setPrev(first.getPrev());  
    first.setPrev(mid);  
    mid.setNext(first);  
}

我不知道丢失了什么...

I dont know what is missing...

列表，值：

6

2

4

5

7



排序后：

2

6

7



辅助输出：

交换：6<> 2

交换：6< > 4

交换：6<> 5

List, value:
6
2
4
5
7

After sort:
2
6
7

Auxiliar outputs:
Swapping: 6 <> 2
Swapping: 6 <> 4
Swapping: 6 <> 5

请帮帮我，我不知道排序双重链接列表.....

Please, some on help-me, I don't know sort a double linked list.....

public void swap(Node first, Node mid) {  
    if (first == head)  
        head = mid;  
    if (mid == tail) {  
        tail = first;  
    }  
    first.setNext(mid.getNext());  
    mid.setPrev(first.getPrev());  
    first.setPrev(mid);  
    mid.setNext(first);  
}

请参见以下代码：swap函数。

See the code following : swap function.

推荐答案

由于这似乎是一项家庭作业问题，因此我不会为您提供完整的答案。我很肯定问题出在交换功能上。考虑在纸上绘制节点并通过交换功能，看看哪些节点指向何处会发生什么。考虑要交换的节点的上一个和下一个节点，并且还必须更新它们的上一个/下一个！当然，除非您的setNext和setPrev函数已经做到了。

Since this is appears to be a homework question I will not give you the full answer. I am fairly positive that the problem lies in your swap function. Consider drawing the nodes on paper and going through your swap function and seeing what happens to which nodes pointing where. Consider the previous and next nodes of the nodes you are swapping and that you have to update their previous/next as well! Unless of course your setNext and setPrev functions already do that.

如果需要其他帮助，请随时发表评论。

Feel free to comment if you need additional help.

编辑1：

此外，不使用索引（i和j）来跟踪您正在使用的节点，而是考虑使用节点本身。然后，当您调用i ++或j ++时，请改为调用node = node.getNext（）。这样，您就不会在运行时中添加n的额外因数，并且可以完全消除交换功能。

Also, as a side note, rather than using indices (i and j) to keep track of which node you're using, consider just using the node itself. And then when you call i++ or j++, call node = node.getNext() instead. This way you aren't adding an additional factor of n to your runtime, and you can eliminate your swap function altogether.

编辑2：

我在纸上画出的意思是将每个值水平地依次写在纸上。然后在每个圆圈周围画一个圆圈，并分别指向下一个圆圈和上一个圆圈的箭头。用铅笔画箭头！然后在逐步执行交换功能时相应地更新箭头。您甚至不必移动/擦除圆圈，只需擦除箭头并查看其下一个指向的位置。

What I mean by drawing it out on paper is write each of the values out on paper, in order, horizontally. Then draw a circle around each one and an arrow pointing to the next circle and the previous circle in each case. Draw the arrows in pencil! Then update the arrows accordingly as you step through your swap function. You don't even have to move/erase the circles, just erase the arrows and see where they point next.

编辑3：

好吧，您有两个要交换的圈子。这些圆圈都有向外的箭头，而它们的邻居都有向内的箭头。那就是每个圆圈4个箭头（2进2出，除非您要处理头/尾）。因为您要移动2个圆圈，所以您必须总共更改8个箭头（除非处理头/尾）-每个圆圈4个。每个setPrev / setNext可能只更改一个箭头。这意味着这些通常应该在交换函数中被调用8次。您只给他们打电话了4次。

Okay so you've got two circles that you want to swap. These circles both have arrows going outwards, and their neighbors both have arrows going inwards. That's 4 arrows per circle (2 in, 2 out, unless you're dealing with the head/tail). Since you are moving 2 circles, that means you have to change a total of 8 arrows (unless dealing with head/tail) - 4 per circle. You're probably only changing one arrow per setPrev/setNext. Which implies that these should usually be called 8 times in your swap function. You're only calling them 4 times.

编辑4：

您正在更新上一个/下一个交换的节点，但不是邻居的节点。您将要执行诸如first.getNext（）。setPrev（second）等操作，以更新邻居的reference / prev / next / arrows。

You are updating the prev/next of the swapped nodes, but not of their neighbors. You're going to want to do something like first.getNext().setPrev(second), etc. to update the references/prev/next/arrows of the neighbors.

编辑5：

请记住空检查（您不能在a上调用setPrev或setNext为null，因此请确保在您设置邻居的上一个/下一个邻居时，该邻居确实存在（因为prev在头部不存在，next在尾部​​不存在）。

Keep in mind null checks though (you can't call setPrev or setNext on a null, so make sure when you set the neighbor's prev/next that the neighbor actually exists (because prev doesn't exist for head and next doesn't exist for tail)).

编辑6：

我猜，如果您说，您不是在做作业...；

I guess if you say you aren't doing homework... ;)

void swap(Node first, Node second) {
    Node firstPrev = first.getPrev();
    Node firstNext = first.getNext();
    Node secondPrev = second.getPrev();
    Node secondNext = second.getNext();

    if (firstPrev) {
        firstPrev.setNext(second);
    }
    if (firstNext) {
        firstNext.setPrev(second);
    }
    if (secondPrev) {
        secondPrev.setNext(first);
    }
    if (secondNext) {
        secondNext.setPrev(first);
    }

    second.setPrev(firstPrev);
    second.setNext(firstNext);
    first.setPrev(secondPrev);
    first.setNext(secondNext);
}

这篇关于双链表上的BubbleSort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！