不使用交换的单链表中的选择排序

Question

我一直在尝试在不使用交换节点的情况下解决单链表中的选择排序问题。使用临时列表存储节点并将当前列表分配给新节点

//my addlastnode function
void AddLastNODE(LIST &mylist, NODE *p)
{
//Check the list is empty or not
    if(isEmpty(mylist))
        mylist.pHead = mylist.pTail = p;
    else
        mylist.pTail->pNext = p;
        mylist.pTail = p;
}

void selectionSort(LIST &mylist)
{
//Initialize a temp list to store nodes 
    LIST mylisttemp;
    IntList(mylisttemp);
//Create node
    NODE *p;
    NODE *i;
//Create min node
    NODE *min;
//Check if list is empty or has one node
    if(mylist.pHead == mylist.pTail)
        return;
//Traverse the list till the last node
    for(p=mylist.pHead; p->pNext!=NULL && p!=NULL; p = p->pNext)
        {
            min=p;
                for(i=p->pNext; i!=NULL;i=i->pNext)
                {
////Find the smallest data in list
                    if(i->data < min->data)
                        min=i;
                }
////Add the smallest to a new list
                AddLastNODE(mylisttemp, min);
        }
//Fill the current list to the new list
    if(!isEmpty(mylisttemp))
    mylist = mylisttemp;
}

Answer 1

您的代码不会减少您从中选择节点的列表：应从中删除所选节点。为此，您需要在 所选节点之前引用节点 ，以便您可以重新连接列表以排除所选节点。

您的 AddLastNODE 函数中还有一个小问题：它不会强制尾节点将空值作为 pNext 指针。当使用仍然具有非空 pNext 指针的节点调用函数时，这可能是导致错误的原因。其次，else 块周围的缩进关闭。在这种情况下它不会导致错误，但最好还是避免混淆：

void AddLastNODE(LIST &mylist, NODE *p)
{
    if(isEmpty(mylist))
        mylist.pHead = p;
    else
        mylist.pTail->pNext = p;
    mylist.pTail = p; // indentation!
    p->pNext = nullptr; // <--- better safe than sorry!
}

然后是主要算法。在查找具有最小值的节点时，使用 previous 节点引用非常繁琐。当您临时制作输入列表 cyclic:

时，它会有所帮助

void selectionSort(LIST &mylist) {
    if (mylist.pHead == mylist.pTail) return;
    // Make list temporarily cyclic
    mylist.pTail->pNext = mylist.pHead;

    LIST mytemplist;
    IntList(mytemplist);

    while (mylist.pHead != mylist.pTail) {
        // Select node:
        NODE * beforemin = mylist.pTail;
        for (NODE * prev = mylist.pHead; prev != mylist.pTail; prev = prev->pNext) {
            if (prev->pNext->data < beforemin->pNext->data) {
                beforemin = prev;
            }
        }
        NODE * min = beforemin->pNext;
        // Extract selected node:
        if (min == mylist.pTail) mylist.pTail = beforemin;
        if (min == mylist.pHead) mylist.pHead = min->pNext;
        beforemin->pNext = min->pNext;
        // And insert it:
        AddLastNODE(mytemplist, min);
    }
    // Move last remaining node
    AddLastNODE(mytemplist, mylist.pHead);
    // Copy back
    mylist = mytemplist;
}

附带说明：您甚至可能希望始终保持列表循环。这将意味着您可能拥有的其他功能会发生一些变化，因为届时将没有 pNext 为空的指针。

不使用交换的单链表中的选择排序

Selection sort in single linked list without using swap

c

c++

algorithm

linked-list

data-structures