0

単純なマージソートアルゴリズムを実装しようとしています。私が非常に混乱しているのは、「array2」が削除された直後に次のエラーメッセージが表示され続けることです。

"free（）：無効な次のサイズ（高速）"

お知らせ下さい。どうもありがとうございます！

#include <iostream>
#include <limits.h>

using namespace std;

void merge_sort(int*,int,int);

int main(){
  //cout << "Max int: " << INT_MAX <<endl;
  int n;
  cin >> n;
  int* array = new int(n+1);
  for (int i=1; i<=n; i++)
    cin >> array[i];
  merge_sort(array,1,n);
  cout << "--------------------------------------------" <<endl;
  for (int i=1; i<=n; i++)
    cout << array[i] <<endl;
}

void merge_sort(int* array,int p,int r){
  cout << p << ' ' << r <<endl;
  if (p == r)
    return;
  int q = int((p+r)/2);
  merge_sort(array,p,q);
  merge_sort(array,q+1,r);
  //(p..q)  and (q+1 .. r) sorted, then merge this two sorted array
  int n1 = q-p+1;
  int n2 = r-q;
  cout << "Mark1 " <<n1<<' '<<n2<<endl;
  int *array1;
  array1 = new int(n1+1);
  int *array2;
  array2 = new int(n2+1);
  for (int i=p; i<=q; i++)
    array1[i-p] = array[i];
  for (int i=q+1; i<=r; i++)
    array2[i-q-1] = array[i];
  array1[n1] = INT_MAX;
  array2[n2] = INT_MAX;  //CONSTANT, serve as sentinel

  int p1 = 0;
  int p2 = 0;
  cout << "Mark2" << endl;
  for (int i=p; i<=r; i++){
    if (array1[p1]<array2[p2]){
      array[i] = array1[p1];
      p1++;
    }else{
      array[i] = array2[p2];
      p2++;`enter code here`
    }
  }   
  cout << "Mark3" << endl;
  delete [] array2;
  cout << "Delete array2 " << endl;

  delete [] array1;
  cout << "Delete array1 " << endl;
}
4

1 に答える 1

1

構文

new int(n+1)

intフリーストアでシングルを作成し、で初期化します。n+1すぐに、で範囲外にアクセスしますarray[1]。ブラケットが必要です：

new int[n + 1]

配列を作成します。同じことがプログラムの他のすべての場所にも当てはまります。

また、でループを開始しているため1、オブジェクトarray[0]は初期化されておらず、アクセスすると未定義の動作が発生します。これは、配列要素を無駄にし、自分でトラップを設定することです。配列サイズに1を追加せず、インデックスを0から開始することをお勧めします。

于 2013-01-25T03:25:50.870 に答える