0

そこで、ArrayList(C ++ではベクトル)の独自の実装を作成し、それにいくつかのアルゴリズムを含めました。今、私のマージソートメソッドはメモリリークを起こしているようですが、コードを1行ずつ調べて、割り当てから削除までを追跡しました。すべてうまくいっているようです。

ArrayListのすべてのメソッドにテストスクリプトがあり、クラッシュが発生していたので、マージソートテストを削除しようとしましたが、クラッシュは発生しませんでした。しかし、興味深いのは...常にクラッシュするわけではなく、時々動作し、他の人もクラッシュすることです。

2つのメソッドのコードは次のとおりです。

簡単な変数の列挙:

array=arrayListをサポートする配列

size=配列のサイズを追跡するint。

ソート済み=リストがソートされているかどうかを示すブール値

/**
 * Runs merge sort on this ArrayList<T>. Interface function to the central,
 * recursive, merge sort function.
 *
 * Runs in O(nlogn) time. However it consumes extra memory.
 */
template<class T>
void ArrayList<T>::mergeSort() {

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

/**
 * Runs merge sort on the passed in array. Recursive.
 *
 * Runs in O(nlogn) time. However it consumes extra memory.
 *
 * @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;

    //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);

        //Allocate memory for return array.
        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++;
        }

        //Free the memory allocated in the recursive calls.

        delete [] array1;
        delete [] array2;
        array1 = 0;
        array2 = 0;
    }
    //If one element is in the passed array.
    else {

        //Allocate memory for new array, and assign passed value to it.
        //This is done so delete can be called in the calling function.
        returnArray = new T[1];
        returnArray[0] = array[0];
    }

    return returnArray;
}
4

1 に答える 1

3

array1 [ j ]であるかどうかを確認する前にアクセスしていますj < size1。その場合j >= size1、そのインデックスの配列にアクセスすることは違法です。ヒープ内のメモリレイアウトによっては、常にクラッシュするとは限りませんが、クラッシュする場合があります。チェックは次のようになります。

if (((j < size1) && (array1[j] <= array2[k])) || k == size2) {
...
于 2012-09-22T21:37:16.303 に答える