1

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

以下内容卡在 for 循环中并无限循环。我不明白为什么会这样。谁能向我解释为什么找不到列表的末尾？

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;

}

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

4

4 回答 4

3

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

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

我，e next_of_current 指向当前，所以 curr->next 将永远是 curr 并且永远不会是 NULL；

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

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

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;
}

希望这会有所帮助，问候。

于 2013-10-24T04:47:58.713 回答
0

您要交换的字段是value. 但是，如果交换node，next字段会发生变化，问题会变得有点复杂，您需要保持next字段正确。总之，改变value是一种简单而好的方法。

于 2013-10-24T04:42:56.283 回答
0

您有以下问题：

让您拥有包含三个成员的列表：ptr1->ptr2->ptr3。在交换之前，您设置了以下指针：curr=ptr1; curr->next=ptr2; curr->next->next=ptr3. 当您执行交换时，您会收到curr=ptr2; curr->next=ptr1; curr->next->next=ptr2.

例如，您丢失了 ptr3。您需要使用以下内容更改内部循环的代码：

temp = curr;
temp->next = curr->next->next;    // Save ptr3
curr = curr->next;
curr->next = temp;
didSwap = true;
于 2013-10-24T03:53:41.440 回答
0 
node *sorted_list(node *head) {
    node *index1,*index2;
    for(index1=head;index1->next!=NULL;index1=index1->next) {
        for(index2=index1->next;index2!=NULL;index2=index2->next) {
            if(index1->data>index2->data) {
                int temp=index1->data;
                index1->data=index2->data;
                index2->data=temp;
            }
        }
    }
    return head;
}
于 2017-09-11T19:28:27.023 回答