c++ - 使用数组对 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() 将能够正确排序您的数组。

撇开这一点不谈，排序后执行的代码中存在多个错误。当前代码执行以下操作:

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

这里的问题是 currentPtr 在排序之前已经被用来遍历列表，此时它是 NULL。如果您只是尝试 discussing your code with your rubber duck ，你的橡皮鸭会告诉你的。

因此这里的第一次迭代导致空指针取消引用和崩溃。

您只需要:

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，您可以暂时新建数组，然后再删除它。