c++ - 在 C++ 中使用选择排序对链表进行排序

Question

我在尝试测试我的排序方法时遇到了某种运行时错误。在我的实现中，我试图在链表中找到最小的节点……然后我测试最小的节点是第一个节点、最后一个节点，还是就在中间。在对这些情况进行测试后，我尝试将最小值添加到新的链表中。我这样做是为了对所有值进行排序，然后将 head(我类中的私有(private)变量)指向新排序的列表...如果我需要包含我的头文件或其他任何内容，请告诉我。感谢您的帮助。

明确地说，没有实际的错误消息，程序只是在我调用排序函数时终止。

void Linkedlist::sort()
{
    Node * current = head;
    Node * smallest = head;
    Node * newHead = NULL;
    Node * newTail = NULL;

    while(head != NULL)
    {
        current = head;
        while(current != NULL)
        {
            if(current->elem < smallest->elem)
            {
                smallest = current;
            }
            current = current->next; 
        }

        //smallest is first node
        if(smallest->prev == NULL)
        {
            head = head->next;
            head->prev = NULL;
        }

        //smallest is last node
        else if(smallest->next == NULL)
        {
            tail = tail->prev;
            tail->next = NULL;
        }

        else
        {
            smallest->prev->next = smallest->next;
            smallest->next->prev = smallest->prev;
        }

        //adding smallest to a new linked list
        if(newHead == NULL)
        {
            smallest->prev = NULL;
            smallest->next = NULL;
            newHead = smallest;
        }
        else
        {
            smallest->prev = newTail;
            smallest->next = NULL;
            newTail->next = smallest;
            newTail = smallest;
        }
    }
    //point head to new linked list
    head = newHead;

}

Answer 1

将第一个元素添加到新链表时需要设置newTail。

否则当newTail->next = smallest对第二个new entry执行时，会是空指针访问。

只需添加

newTail = smallest

之后

newHead = smallest