0

そのため、マージソートの実装を終了しましたが、破棄していた再帰呼び出しから返されたメモリを削除していないことに気付きました。そのため、array1 と array2 の削除ステートメントを追加したところ、突然マージソートが行われなくなりました。作業.....関数の末尾近くに削除ステートメントを追加すると、すべてが台無しになるのはなぜですか? メモリを解放する必要がありますか?

コードは以下のとおりです。

/**
 * Runs merge sort on this ArrayList<T>. Interface function to the central,
 * recursive, merge sort function.
 */
template<class T>
void ArrayList<T>::mergeSort() {

    T* temp = mergeSort(array, size);
    delete [] array;
    array = temp;
}

/**
 * Runs merge sort on the passed in array. Recursive.
 *
 * @param array the array to sort.
 * @param arraySize the size of the array that is to be sorted.
 * @return the sorted array.
 */
template<class T>
T* ArrayList<T>::mergeSort(T* array, int arraySize) {

    T* returnArray = array;

    //If the array is more than one element.
    if (arraySize > 1) {

        int size1 = arraySize / 2;
        int size2 = arraySize - size1;

        T* array1;
        T* array2;

        //Recurse.
        array1 = mergeSort(array, size1);
        array2 = mergeSort(array + size1, size2);

        returnArray = new T[arraySize];

        //Loop through all elements in returnArray.
        int i = 0, j = 0, k = 0;
        while (i < arraySize) {

            //Place the lesser of two elements in returnArray.
            if ((array1[j] <= array2[k] && j < size1)
                    || k == size2) {

                returnArray[i] = array1[j];
                j++;
            }
            else {

            returnArray[i] = array2[k];
                k++;
            }

            i++;
        }

/---これらは問題の削除です!!---/

        delete [] array1;
        delete [] array2;
    }

    return returnArray;
}
4

2 に答える 2

3

あなたが呼び出すので、配列サイズが2に等しいときに問題が発生します

array1 = mergeSort(array, size1);
array2 = mergeSort(array + size1, size2);

および size1=1,size2=1 の場合、これらの呼び出しは両方とも返され、変数には次の値が含まれます

array1 = array;
array2 = array+1;

array2は割り当てられたメモリアドレスではないため、削除するとエラーで失敗するか、未定義の処理が行われるため、続行する前に修正することをお勧めします

于 2012-08-07T04:42:31.863 に答える
1

詳細は見ていませんが、1 つのことが頭に浮かびます:mergeSortサイズが の配列で が呼び出されると<= 1、新しい配列を割り当てずに渡された配列を返しますが、再帰呼び出しから戻ると、とにかくそれを削除しようとします。以下を追加することで、コードを改善できます。

if (size1 > 1)
   delete [] array1;
if (size2 > 1)
   delete [] array2;
于 2012-08-07T04:54:31.597 に答える