free関数で動作が止まる

質問

freeしようとすると止まってしまいます。（１）
q4614822の質問では用意するサイズが間違っていると起こるらしいのですが、出力に問題はないようです。スタックトレースというものをやってみたいのですが、C言語でも出来ますか？
もう１つ質問ですがmerge_sortをmerge-sortで宣言するとコンパイルが通らない理由をお教え下さい。（２）

出力結果（１）
42 33 78 19 46 63 25 11 54 17
11 17 19 25 33 42 46 54 63 78
^C←ここで止まります。

出力結果（２）
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
main.c:
エラー E2449 main.c 5: 'merge' のサイズが不明、あるいはゼロ
エラー E2141 main.c 5: 宣言の構文エラー
エラー E2356 main.c 6: 'merge' の再宣言で型が一致していない
エラー E2344 main.c 5: 一つ前の 'merge' の定義位置
警告 W8065 main.c 15: プロトタイプ宣言のない関数 'sort' の呼び出し(関数 main )
警告 W8019 main.c 15: コードは効果を持たない(関数 main )
エラー E2356 main.c 23: 'merge' の再宣言で型が一致していない
エラー E2344 main.c 6: 一つ前の 'merge' の定義位置
エラー E2449 main.c 30: 'merge' のサイズが不明、あるいはゼロ
エラー E2356 main.c 30: 'merge' の再宣言で型が一致していない
エラー E2344 main.c 23: 一つ前の 'merge' の定義位置
エラー E2141 main.c 30: 宣言の構文エラー
*** 10 errors in Compile ***

#include<stdio.h>
#include<stdlib.h>
#define N 10
void merge_sort(int,int);
void merge(int,int);
int a[N]={42,33,78,19,46,63,25,11,54,17};
int *b;
int main(){
int i=0;
b=(int*)malloc(sizeof(int)*N);
while(i<N)printf("%3d",a[i++]);
printf("\n");
merge_sort(0,N-1);
free(b);
i=0;
while(i<N)printf("%3d",a[i++]);
printf("\n");
return 0;
}

void merge(int left,int right){
int half=(right+left-1)/2,i=left,j=half+1,k;
for(k=0;k<left+right+1;k++){
if((i<=half)&&(a[i]<a[j]||j==right+1))b[left+k]=a[i++];
else b[left+k]=a[j++];
}
}
void merge_sort(int left,int right){
if(left<right){
int half,k;
half=(right+left-1)/2;
merge_sort(left,half);
merge_sort(half+1,right);
merge(left,right);
for(k=left;k<=right;k++)a[k]=b[k];
}
}

回答No.9

maiko0318

＞ 19 33 42 46 63 25 11 54 17 78
＞↑こうなります

結果は
42 33 78 19 46 63 25 11 54 17
11 17 19 25 33 42 46 54 63 78

でしたが？あれっ？

補足

写し間違えがありました。申し訳ありません。
right以降の余分な走査はコピーしているだけなので、問題はありませんね。

回答No.8

AsarKingChang

maiko0318さん、むっちゃがんばったね＾＾

最後に、質問とは無関係ですが、
int *b;
この”グローバル”
あまり美しくないので、
void merge(int *b,int left,int right) ;;
void merge_sort(int *b,int left,int right) ;;
と中で消化させるようにすれば、
拡張性があがり、便利ですよ！
（ここは好みなので、ただの参考に。だけです。）

補足

ありがとうございます。
その点に関してはすでに改良してまして、merge_sortからmergeへ渡す方式に変更しております。

回答No.7

maiko0318

void merge(int left,int right){
int half=(right+left-1)/2,i=left,j=half+1,k;
for(k=0;k<N-left;k++){　　　　　　　　　　　　　　　　　　終了条件変更
if((i<=half)&&(a[i]<a[j]||j==right+1))b[left+k]=a[i++];
else b[left+k]=a[j++];
}
}

これでうまくいく

補足

ご回答ありがとうございます。
19 33 42 46 63 25 11 54 17 78
↑こうなります
不正アクセスはありませんが、余分に回す場合が出てくるのでうまくはいかなかったです。

回答No.6

maiko0318

void merge(int left,int right){
int half=(right+left-1)/2,i=left,j=half+1,k;
for(k=0;k<left+right+1;k++){
if((i<=half)&&(a[i]<a[j]||j==right+1))b[left+k]=a[i++];
else b[left+k]=a[j++];
}
}

ここでleft+kは９を超えます。ちなみに２６まで使います。
b=(int*)malloc(sizeof(int)*N*3);　　ここで、bを３０個作るとfree(b)は問題無いです。

回答No.5

maiko0318

原因を特定しました。

#include<stdio.h>
#include<stdlib.h>
#define N 10
void merge_sort(int,int);
void merge(int,int);
int a[N]={42,33,78,19,46,63,25,11,54,17};
int b[N];　　　　　　　　　　　　　　　　　　普通の配列で良いのでは？
int main(){
int i=0;
//b=(int*)malloc(sizeof(int)*N);　　　　　　　不要
while(i<N)printf("%3d",a[i++]);
printf("\n");
merge_sort(0,N-1);
//free(b);　　　　　　　　　　　　　　　　　　　不要
i=0;
while(i<N)printf("%3d",a[i++]);
printf("\n");
return 0;
}

void merge(int left,int right){
int half=(right+left-1)/2,i=left,j=half+1,k;
for(k=0;k<half+1;k++){　　　　　　　　　　　　　　　　　　終了は　k<half+1
if((i<=half)&&(a[i]<a[j]||j==right+1))b[left+k]=a[i++];
else b[left+k]=a[j++];
}
}
void merge_sort(int left,int right){
if(left<right){
int half,k;
half=(right+left-1)/2;
merge_sort(left,half);
merge_sort(half+1,right);
merge(left,right);
for(k=left;k<=right;k++)a[k]=b[k];
}
}

お礼

ありがとうございます。
left+right+1だと普通に考えてサイズ超えますよね
なんでこんな当たり前のことに気付かなかったのか…

回答No.4

maiko0318

merge内

for(k=0;(k<left+right+1);k++){
printf("\npoint3:left=%d,k=%d,i=%d,j=%d,half=%d",left,k,i,j,half);
if((i<=half)&&(a[i]<a[j]||j==right+1))b[left+k]=a[i++];
else b[left+k]=a[j++];
}

このループ、aやbの[]内が９を超えています。
試しにa[20],bも２０個用意したらきちんと終わりました。

回答No.3

AsarKingChang

>出力結果（１）
>42 33 78 19 46 63 25 11 54 17
>11 17 19 25 33 42 46 54 63 78
>^C←ここで止まります。

GCC にてコンパイルしてみました。
>42 33 78 19 46 63 25 11 54 17
この直後、コアダンプを吐いてます（つまりスタックを壊したということ）

>merge_sortをmerge-sort

merge + (-sort)
つまり、mergeやsortは変数名になっちゃいますよ。

void merge(int left,int right){
～～～～～～～
if((i<=half)&&(a[i]<a[j]||j==right+1))b[left+k]=a[i++];
～～～～～～～
}
ここなんですが、
void merge(int left,int right){
int half=(right+left-1)/2,i=left,j=half+1,k;
for(k=0;k<left+right+1;k++){
if((i<=half)&&(a[i]<a[j]||j==right+1)){
if (left+k>=N) printf("left=%d k=%d\n",left,k);
b[left+k]=a[i++];
}
else {
if (left+k>=N) printf("left=%d k=%d\n",left,k);
b[left+k]=a[j++];
}
}
}
bのサイズを大きく超えるエリアの配列へアクセスしています。
left=8 k=17 ですら呼ばれているのを確認しました。

質問は、スタックトレースのやり方でしたが、BCCは所有していないので、
わかりませんでしたが、
こんな感じで、ポインタ変数へのエリアチェックをするだけでも、
相当ヒントになるので、一度お試しください。

何をするプログラムかは、見てないので、もっと簡単な
”答え”があるのかについては、見ていない回答になります。

お礼

ありがとうございます。
丁寧に出力を見ながらデバッグしてみたところ、問題なく動いてくれました。
今はもう少し読みやすいコードになるよう努めております。

回答No.2

maiko0318

動かしてみました。問題はfree(b);ではなく、merge_sort(0,N-1);のようです。
(merge_sort(0,N-1);をコメントアウトしたら正常終了しました)

複雑なロジックですので、今わかっているのは以上になります。

こちらの環境win7,vs2013

回答No.1

Hayashi_Trek

＞もう１つ質問ですがmerge_sortをmerge-sortで宣言するとコンパイルが通らない理由をお教え下さい。（２）
「merge-sort」は、「merge引くsort」と解釈されるから。

お礼

関数名内を式として認識するのは初めて聞きました。
ありがとうございます。