用指针对单链接列表进行排序 [英] Sorting a Singly Linked List With Pointers

问题描述

我试图通过仅操作指针而不使用键来使用冒泡排序对单个链接列表进行排序。

I am trying to sort a singly linked list using bubble sort by manipulating ONLY the pointers, no keys.

以下内容陷入了for循环并无限循环。我不明白为什么会这样。有人可以向我解释为什么找不到列表的末尾吗？

The following gets stuck in the for loop and loops infinitely. I don't understand why this is. Can anybody explain to me why the end of the list is not being found?

Node* sort_list(Node* head)
{
    Node * temp;
    Node * curr;
    for(bool didSwap = true; didSwap; ) {
            didSwap = false;
            for(curr = head; curr->next != NULL; curr = curr->next) {
                    if(curr->key > curr->next->key) {
                            temp = curr;
                            curr = curr->next;
                            curr->next = temp;
                            didSwap = true;
                    }
                    cout << curr->next->key << endl;
            }
    }
    return head;

}

如果我更改代码这样就可以交换键（数据），然后该函数可以正常工作，但是由于某种原因，我无法通过仅操作指针来使其正常工作。

If I change the code so that the keys (data) are swapped, then the function works properly but for some reason I am not able make it work by manipulating only pointers.

推荐答案

逻辑错误，您正在使用以下代码创建无限循环-

Logical Error, you are creating an infinite loop with following code -

temp = curr;
curr = curr->next;
curr->next = temp;

I，e next_of_current指向current，所以curr-> next将始终是curr，并且永远不会为NULL；

I,e next_of_current is pointing to current, so curr->next will always be curr and never will be NULL;

接下来，您应该使用上一个指针来修复列表，因为列表可以在单个方向上遍历。因此，请考虑-
如果A-> B-> C-> NULL;并且您进行了C和B交换，那么新列表仍将指向A-> B，并且下一次迭代将是错误的……因为您没有修改先前的下一个。

Next you should use previous pointer to fix your list because your list can be traversed in a single direction. So, Think - If A->B->C->NULL; and you make C and B swap then the new list will still point to A->B and next iteration will be wrong ... because you are not modifying your previous next.

因此，另一种实现方式可能是-

So, another implementation may be -

Node* sort_list(Node* head) {
    Node * curr;
    Node * prev;
    for(bool didSwap = true; didSwap; ) {
        didSwap = false;
        prev = head;
        for(curr = head; curr->next != NULL; curr = curr->next) {
                if(curr->key > curr->next->key) {
                        if (head == curr) {
                            head = curr->next;      
                            curr->next = head->next; 
                            head->next = curr; 
                            prev = head;
                        } else {
                            prev->next = curr->next;
                            curr->next = prev->next->next;
                            prev->next->next = curr
                        }
                        didSwap = true;
                } else if (head != curr) {
                    prev = prev->next;
                } 
                //cout << curr->next->key << endl; // <- this may cause crash if curr->next now points to NULL; (i,e last element)
            }
    }
    return head;
}

希望这会有所帮助。

这篇关于用指针对单链接列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！