按升序对链接列表进行排序并打印排序列表

Question

我正在尝试按升序对链表进行排序，但卡在了这里。其余代码工作正常（附加、前置函数）。我在这里尝试使用冒泡排序算法。

但是，输出显示分段错误。我在这里做错了什么？

void sortLinkedList(Node** head_ref)
{
    Node* slow_node =(*head_ref);
    Node* fast_node=NULL;
    Node* temp=NULL;
    while(slow_node->next!=NULL)
    {
        fast_node=slow_node->next;
        while(fast_node->next!=NULL)
        {
            if(fast_node->data>fast_node->next->data)
            {
                temp->data=fast_node->data;
                fast_node->data=fast_node->next->data;
                fast_node->next->data=temp->data;
            }   
            fast_node=fast_node->next;
        }
        slow_node=slow_node->next;
    }
}

void printList(Node** head_ref)
{
    Node* new_node=(*head_ref);

    while(new_node!=NULL)
    {
        cout<<new_node->data<<"-->";
        new_node=new_node->next;
    }
    cout<<"NULL";
    cout<<endl;
}



int main()
{
    Node* head=new Node();

    head=NULL;

    insertAtEnd(&head,2);
     printList(&head);
    insertAtEnd(&head,3);
     printList(&head);  
    insertAtEnd(&head,2);
     printList(&head);  
    insertAtEnd(&head,4);
     printList(&head);  
     insertAtEnd(&head,5);
     printList(&head);  

    cout<<"Sorted List"<<endl;
    sortLinkedList(&head);
    printList(&head);

}

输出

2-->NULL
2-->3-->NULL
2-->3-->2-->NULL
2-->3-->2-->4-->NULL
2-->3-->2-->4-->5-->NULL
Sorted List
Segmentation fault (Core dumped)

Answer 1

冒泡排序的问题是交换操作。您使用为 NULL 的 temp，并尝试访问数据元素。这会触发分段错误。

在最简单的情况下，您可以使用 std::swap。你的冒泡排序看起来像

void sortLinkedList(Node** head_ref)
{
    Node* slow_node =(*head_ref);
    Node* fast_node=NULL;
    while(slow_node->next!=NULL)
    {
        fast_node=slow_node->next;
        while(fast_node->next!=NULL)
        {
            if(fast_node->data>fast_node->next->data)
            {
                std::swap(fast_node->data, fast_node->next->data);
            }   
            fast_node=fast_node->next;
        }
        slow_node=slow_node->next;
    }
}

Answer 2

你有

Node* temp=NULL;

然后是你

temp->data=fast_node->data;

它会爆炸，因为 temp 是一个空指针。

如果您要交换节点的数据，则不需要整个节点，只需 data 中的一种类型即可：

 if(fast_node->data>fast_node->next->data)
 {
     whatever_data_is temp = fast_node->data;
     fast_node->data = fast_node->next->data;
     fast_node->next->data = temp;
 }

但是你的标准库中已经有一个交换函数，所以你可以简化：

 if (fast_node->data>fast_node->next->data)
 {
     std::swap(fast_node->data, fast_node->next->data);
 }

按升序对链接列表进行排序并打印排序列表

Sorting a Linked List in ascending order and printing sorted List

c++

linked-list

c++14

bubble-sort