２次元配列の動的メモリ確保とコアダンプ修正

Question

前提・実現したいこと

k近傍による判断結果を出力するコードを書いている途中です。
実現したいこと
・a配列の２次元配列（nxd）の動的メモリ確保の仕方
・mergesort関数によるコアダンプの修正

発生している問題・エラーメッセージ

セグメンテーション違反です (コアダンプ)

該当のソースコード

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define k 3 
int merge(double *arr,int p,int q,int r){
  int i,j=0,bi=p,ci=q+1;
  double *T=(double*)malloc((r-p+1)*sizeof(double));
  while(bi!=q+1){
    if(arr[bi]<=arr[ci]){
      T[j]=arr[bi];
      ++j;
      ++bi;
    }else{
      T[j]=arr[ci];
      ++j;
      ++ci;
    }
    if(ci==r+1){
      break;
    }
  }
  if(bi==q+1){
    while(j!=r-p+1){
      T[j]=arr[ci];
      ++j;
      ++ci;
    }
  }else if(ci==r+1){
    while(j!=r-p+1){
      T[j]=arr[bi];
      ++j;
      ++bi;
    }
  }
  for(i=0;i<r-p+1;++i){
    arr[i+p]=T[i];
  }
  free(T);
  return 0;
}
int mergesort(double *arr,int a,int b){
  int mid;
  double t=0;
  if(a+1==b){
    if(arr[a]>arr[b]){
      t=arr[a];
      arr[a]=arr[b];
      arr[b]=t;
    }
    return 1;
  }
  mid=(a+b)/2;
  mergesort(arr,a,mid);
  mergesort(arr,mid+1,b);
  merge(arr,a,mid,b);
  return 0;
}
double dis(int size1,int size2,double a[size1][size2],double *s){
  double u,v,ans1=0,ans=0;
  int i=0;
  for(i=0;i<size2;++i){
    u=a[size1][i];
    v=s[i];
    ans1+=pow((u-v),2);
  }
  ans=sqrt(ans1);
  printf("%lf ",ans);
  return ans;
}
int knn_diag(double *s,int n,int d,double a[n][d]){
  int i=0,c=0;
  double b[5]={};
  for(i=0;i<n;++i){
    b[i]=dis(i,d,a,s);//距離をbに代入
  }
  /*for(i=0;i<n;++i){
    printf("%lf ",b[i]);
    }*/
  c=mergesort(b,0,n-1);//小さい方から順に並べる
  for(i=0;i<k;++i){
    printf("%lf \n",b[i]);//k番目まで出力
    }
  return 0;
}
int main(){
  int n,d,i=0,j=0,c=0;
  scanf("%d %d",&n,&d);
  //n=5,d=2;
  double a[5][2]={{180.0,60.0},{164.0,90.0},{151.0,80.0},{153.0,50.0},{172.0,40.0}};//aをnxd配列の動的メモリ確保

  //aにnxd個のデータを標準入力で代入
  /*for(i=0;i<n;++i){
    for(j=0;j<d;++j){
      scanf("%lf",&a[i][j]);
    }
  }*/
  double *s=(double*)malloc(d*sizeof(double));
  //s配列にd個のデータを標準入力で代入
  for(i=0;i<d;++i){
    scanf("%lf",&s[i]);
  }
  c=knn_diag(s,n,d,a);
  if(c==0){
    printf("You are healthy!\n");
  }else{
    printf("You have a heart disease!\n");
  }
  return 0;
}

試したこと

knn_diag関数でmergesort関数による並び替えをするところでコアダンプが発生したと思います。

補足情報（FW/ツールのバージョンなど）

標準入力
5 2
150 60

Answer 1

プログラム自体の期待する動作がいまいちよくわかりませんが。

・mergesort関数によるコアダンプの修正

mergesortに渡されるパラメータをちょっとトレースしてみましょう。
n=5として。
knn_diag()から呼び出しmergesort(b,0,4)
mergesortに入って、
mid=(0+4)/2;
でmidは2
mergesort(arr,0,2); ...A
mergesort(arr,3,4); ...B

Aのmergesortに入って
mid=(0+2)/2;
で1
mergesort(arr,0,1) ...AA
mergesort(arr,2,2) ...AB

AAはa+1==bの条件にハマって素直にreturn。ABに入って
mid=(2+2)/2;
で2
mergesort(arr,2,2) ...ABA
mergesort(arr,3,2) ...ABB

あれれ? ABとABAは同じ。つまり、ABAからはまたmergesort(arr,2,2);が呼ばれて、そこからまた...永遠にmergesort(arr,2,2);の呼び出しが続いてスタックを消費し尽くして、なおメモリを消費してコアダンプ、ということが想定されますね。

mergesortの後ろ2つのパラメータが等しくなるというのはどういうことか、そのときどうするべきかが考えられていません。
(それ以外の間違いがあるかどうかはチェックしていません)

・a配列の２次元配列（nxd）の動的メモリ確保の仕方

先に言っておきますけれど、動的配列ということはプログラム中でサイズが変わる可能性があるということなので、生成した配列にソースコード上の初期値記述で初期値を与えることは出来ませんよ。

gccだとCのオプション機能「可変長配列」が使えるので、サイズの小さな(スタック上に置いても問題ないサイズの)配列なら、例えば

int n,d;
//n,dを適宜設定する
double a[d][n];

でいいです。
サイズが大きくてヒープにとりたいのなら

double (*a)[n];
a = malloc( sizeof(double)*d*n );

でいいでしょう。(もちろん、メモリを確保できたかの確認はして下さい)

可変長配列が使えないMicrosoft Cなどでは、素直な「2次元配列の動的確保」は出来ないと思ってもいいかも知れません。もちろん、それに相当する結果は得られますけれど。「2次元配列」を確保したら、そのポインタは「1次元配列へのポインタ」型変数に格納するわけですが、この1次元配列の要素数を動的に指定する手段がないからです。

---

余計なツッコミかもしれませんが、

	scanf("%d %d", &n, &d);
	//n=5,d=2;
	double a[5][2] = {{180.0, 60.0}, {164.0, 90.0}, {151.0, 80.0}, {153.0, 50.0}, {172.0, 40.0}}; //aをnxd配列の動的メモリ確保

nやdはどんな値になるか、ユーザー入力次第なわけで、それをint knn_diag(double *s, int n, int d, double a[n][d])に与えるようなことは私にはとてつもなく危険なことに思えます。

Answer 2

#include<stdio.h>
#include<stdlib.h>
int main(){
  int i,j,n=5;
  double **a=(double**)malloc(n*sizeof(double*));
  for(i=0;i<6;++i){
    a[i]=(double*)malloc(n*sizeof(double));
  }
  for(i=0;i<5;++i){
    for(j=0;j<5;++j){
      scanf("%lf",&a[i][j]);
    }
  }
  for(i=0;i<5;++i){
    for(j=0;j<5;++j){
      printf("%.2lf",a[i][j]);
    }
  }
}

Answer 3

int mergesort(double *arr, int a, int b)のarrが壊れています。

原因を確かめましょう。