在c++中使用数组对链表进行排序

Question

我尝试通过将每个节点的数据复制到列表中来排序一个数组。然后在排序数组的代码之后，我尝试将数组元素中的值复制到每个节点的列表。这有可能吗，我试着研究这个问题，但不行直截了当地回答"是"或"不是"。我不想使用cstdlib中的qsort，这个崩溃，我想知道是否有办法使这个工作。洞察力感激。

template <typename NODETYPE>  
void List<NODETYPE>::sort(){ 
ListNode<NODETYPE>* currentPtr = firstPtr;
    int N = sizeOfList();
    NODETYPE a[N];
    int l = 0;
    int r = 0;
    int i,j,min,imin,tmp;
    while(currentPtr != NULL){
        a[l] = currentPtr->data;
        currentPtr = currentPtr ->nextPtr;
        l++;
    }
for (i=0;i<N-1;i++)
{
    imin=i;
    min=a[i];
    for (j=i+1;j<N;j++)
        if (a[j]<min)
        {
            min=a[j];
            imin=j;
        }
    tmp=a[imin];
    a[imin]=a[i];
    a[i]=tmp;
}

    for ( int y = 0; y < N-1; y++ ){
        currentPtr->data = a[y];
        currentPtr = currentPtr->nextPtr;
    }
    lastPtr->data = a[N];

}

Answer 1

首先，使用std::sort代替手动排序代码。qsort()崩溃的原因是因为它是一个对c++类一无所知的C库函数。std::sort()将能够正确排序你的数组。

把这个放在一边，在排序之后执行的代码中有多个bug。当前代码执行以下操作:

for ( int y = 0; y < N-1; y++ ){
    currentPtr->data = a[y];
    currentPtr = currentPtr->nextPtr;
}
lastPtr->data = a[N];

这里的问题是currentPtr已经被使用，在排序之前，遍历列表，在这一点上它是NULL。如果你只是试着和你的橡皮鸭讨论你的代码，你的橡皮鸭会告诉你的。

所以这里的第一次迭代导致空指针解引用，并导致崩溃。

你只需要:

1. 复位currentPtr为listPtr

2. 可以去掉列表最后一个元素的特殊大小写。它完全没有实现任何有用的东西。此外，这是错误的:

   lastPtr->data = a[N];
   

由于a有N个元素，最后一个元素是a[N-1]，这将在数组的末尾运行，导致未定义的行为。

就像我说的，你可以完全删除这个，简单地遍历整个范围:

for ( int y = 0; y < N; y++ ){

最后，您似乎在使用gcc的可变长度数组扩展，这是不可移植的。而不是声明

NODETYPE a[N];

你应该简单地使用vector:

std::vector<NODETYPE> a;
a.reserve(n);

…然后push_back()每个值，在后面的循环中。

如果你不想使用std::vector，你可以暂时new数组，然后delete之后。