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

Question

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

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

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时，将是空指针访问。

只需添加

newTail = smallest

在

之后

newHead = smallest

Answer 2

添加后

newTail = smallest

将最小元素放入第一个节点时，加上

smallest = head

到我的外部 while 循环的顶部，我仍然运行进入无限循环。我想通了，首先，我需要通过说

将 tail 指向 newTail 最后

tail = newTail

在那之后，我的函数仍然导致了段错误。这个段错误是由于我试图访问 NULL 的 prev 成员。

head = head->next //head is now NULL
head->prev = NULL //segfault

这种情况发生在未排序列表中只剩下一个节点时。我通过在 if 语句中添加一个 if 语句来检查最小节点是否是第一个节点来解决这个问题。里面的 if 语句检查它是否也是最后一个节点（也就是剩下的最后一个节点）

//smallest is first node
        if(smallest->prev == NULL)
        {
            //check if smallest is the ONLY node left
            //if it is only node left, head = head->next makes head NULL 
            //                         so then head->prev = NULL causes segfault
            if(smallest->next == NULL)
            {
                //break leaves while loops 
                //which is why you have to add the final node 
                //outside of the while loops
                break;
            }

            else
            {
                head = head->next;
                head->prev = NULL;

            }
        }

当剩下一个节点时，它会中断，并退出两个while循环。这意味着最终节点从未添加到排序列表中。为了解决这个问题，我只是在将 head 和 tail 指向他们的新列表之前使用了以下代码。

smallest->prev = newTail;
smallest->next = NULL;
newTail->next = smallest;
newTail = smallest;

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

Sorting a linked list using selection sort in C++

c++

doubly-linked-list

selection-sort