0

私はマージソート用のプログラムを書きました (基本的なアルゴリズムを書きました) - そしてそれはうまくいきます。ただし、非常に大きなファイルから整数を読み取る必要があるため、再帰呼び出しで配列を動的に宣言したいと考えていました。したがって、次のコードを書きましたが、いくつかのエラーが発生しています。どこで間違いを犯しているのかを特定するのを手伝ってもらえますか?

プログラムは、実際には配列内の反転の数をカウントすることです ( i < j および arr[i]>arr[j] の場合、これは反転です)。私が書いたプログラムは以下の通りです:

私が得るエラーは次のとおりです: std::bad_alloc at memory location 0x004dd940.. エラーメッセージが含まれるように質問を編集しました。実行が中断し、Visual Studio がデバッグ モードになり、ファイル osfinfo.c が開きます。

    #include<stdio.h>
    #include <iostream>
    using namespace std;
    unsigned int mixAndCount(int * arr,int low, int mid,int high) {
        int *num = new int[high-low+1];// THIS IS WHERE THE ERROR OCCURS
        int l = low ;
        int r = mid+1;
        unsigned int count=0;
        int i =low;

        while((l<=mid)&&(r<=high))
     {
      if(arr[l]<=arr[r])
      {
       num[i]=arr[l];
       l++;

      }
      else
      {
      num[i]=arr[r];
       r++;
       count=count + (mid-l+1);

      }
      i++;
         }
     if(l>mid)
     {
      for(int k=r;k<=high;k++)
      {
       num[i]=arr[k];
       i++;
        }
     }
     else
     {
      for(int k=l;k<=mid;k++)
      {
       num[i]=arr[k];
       i++;
        }
     }
     for(int k=low;k<=high;k++) arr[k]=num[k];
delete[] num;    
return count;
    }

    unsigned int mergeAndCount(int * arr, int low , int high ) {
        if(low>=high) {
        return 0;
        }
        else {
            int mid = (low+high)/2;

            unsigned int left = mergeAndCount(arr, low , mid);
            unsigned right = mergeAndCount(arr, mid+1, high);
            unsigned int split = mixAndCount(arr, low , mid , high);
            return left+right+split;

        }

    }
    int main ()
    {
        int  numArr[100000];
        FILE * input = fopen("IntegerArray.txt", "r");
        int i =0;
        while(!feof(input)) {
            int num;
        fscanf(input, "%d", &num);
        numArr[i] = num;
        i++;
        }
        fclose(input);
        unsigned int count = mergeAndCount(numArr,0, i-1  );
        cout<<count<<endl;
        return 0;
    }
4

2 に答える 2

3
 std::bad_alloc at memory location 0x004dd940..

new要求されたメモリを正常に割り当てることができない場合にスローされる例外です。

int *num = new int[high-low+1];  

要求されたメモリ サイズが大きすぎるようです。つまり、 の値を追跡する必要がありhighますlow

于 2012-09-22T10:15:18.010 に答える
1

動的メモリ割り当てに注意してください。本当に遅いです。コードをこの形式で残す前に、2 回検討してください。で簡単なテストケースを作成できますstd::chrono

http://en.cppreference.com/w/cpp/chrono/duration

動的割り当ては必要ありません。すべてが 1 つのローカル名前空間で行われます。

于 2012-09-22T10:16:13.487 に答える