时间戳

首页 > 解决方案 > 不使用交换的单链表中的选择排序

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

问题描述

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

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

标签： c++calgorithmdata-structureslinked-list

解决方案

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

您的函数中还有一个小问题AddLastNODE：它不会强制尾节点将 null 作为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!
}

然后是主算法。在查找具有最小值的节点时，使用先前的节点引用是非常乏味的。当您暂时使输入列表循环时，它会有所帮助：

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有空指针。

推荐阅读