配列を使ってデータをソートするC++でリンクリストをソート

Question

各ノードのデータを配列 にコピーすることでリストをソートしようとしました。次に、配列をソートしたコードの後に​​、配列の要素の値を各ノードの リストにコピーするために を試しました。それも可能です、私は質問を研究しようとしたことができませんでした まっすぐにはいまたはいいえを見つけることができませんでした。私はcstdlibからqsortを使用したくないのですが、 このクラッシュは、私はこの作業を行う方法があるかどうかを知りたいと思います。 Insightが高く評価しました。すべての

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. listPtrに戻っcurrentPtrをリセットします。

   は、あなたは、単にする必要があります。

2. リストの最後の要素の特殊なケーシングを取り除くことができます。それは全く役に立たない何も達成しません。また、それは間違っている：

   lastPtr->data = a[N]; 
   

aがNの要素を持っているので、最後の要素はa[N-1]あり、これは未定義の動作で、その結果、配列の末尾をオフに実行されます。私が言ったように

、あなたは完全にこれを削除し、単純に全範囲を反復処理することができます。

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

は最後に、あなたは非ポータブルであるGCCの可変長配列の拡張機能を、使用しているように見えます。次のループでは、各値を

std::vector<NODETYPE> a; 

a.reserve(n); 

...そしてpush_back()：代わりに

NODETYPE a[N]; 

を宣言するあなたは、単にベクトルを使用する必要があります。

std::vectorを使用しない場合は、一時的にnewアレイを、次にdeleteアレイを使用できます。