c++ - 在单向链表上实现选择排序

Question

嘿，我正在尝试在单链表上实现选择排序算法，我知道代码中存在一些问题，但尽管我的链表包含数字 7 1 2 6，但运行后的输出是 7777。任何帮助将不胜感激。

template<class Type>
void UnOrderedLinkedList<Type>::selectionSort()
{
nodeType<Type>* loc;
nodeType<Type>* minIndex;
nodeType<Type>* temp;
temp = first;
if(temp == NULL)
    cerr<<"Cannot sort an empty list."<<endl;
else
    if(temp->link == NULL)
    cerr<<"List has only one item so it is already sorted."<<endl;
else

while(temp != NULL)
{
    minIndex = minLocation(temp, last);
    swap(temp, minIndex);
    temp = temp->link;
}
}


template<class Type>
nodeType<Type>* UnOrderedLinkedList<Type>::minLocation(nodeType<Type>* first, nodeType<Type>* last)

nodeType<Type>* minIndex;
nodeType<Type>* other;

minIndex = first;
other = minIndex->link;

while(other != NULL)
{
    if(minIndex->info > other->info)
    {
        minIndex = other;
        other = other->link;
    }

    else
    {
        other = other->link;
    }

}
    return minIndex;
}

然后交换:

template<class Type>
void UnOrderedLinkedList<Type>::swap(nodeType<Type>* first, nodeType<Type>* second)
{
     nodeType<Type>* temp;
     temp->info = first->info;
     first->info = second->info;
     second->info = temp->info;
}

Answer 1

从您的 swap 函数:

 nodeType<Type>* temp;
 temp->info = first->info;

这是一个明显的未定义行为!你声明了一个局部变量，一个指针，没有初始化。然后你直接使用未初始化的变量，导致说UB。由于您使用了指针，您实际上应该为程序没有崩溃而感到高兴。

在这里您不需要指针或节点，因为您实际上并不交换节点。您只需要一个 info 的实例，然后使用它:

SomeType temp;
temp = first->info;
first->info = second->info;
second->info = temp;