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

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!
}

然后是主算法。在寻找具有最小值的节点时，使用先前的节点引用是相当乏味的。当您暂时使输入列表循环:

时，它会有所帮助。

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