0

私は最近、しばらくCに触れなかった後、Cを再びブラッシュアップし始めました。それで、私はマージソートを実装しようとすることから始めましたが、これらの行を約1時間調べた後、何が悪いのかを判断できませんでした。

int main(int argc,char** argv){
    printf("test\n");
    int x;
    int input[] = {1,2,3};
        int start=0;
        int end=2;
    for (x=0;x<5;x++){
        //printf("%i\n",x);
    }
    printf("Run mergeSort in main \n");
    mergeSort(input,start,end);

}

void mergeSort(int input[], int start, int end){
    printf("Running merge %i %i",start,end);
    int middle = (start + end)/2;
    if (start < end){
        mergeSort(input,start,middle);
        mergeSort(input,middle+1,end);
        merge(input,start,middle,end);
    }
}

このプログラムを実行すると、最初の行の「test」が出力され、次に「Run merge sort inmain」が出力されますが、

printf("Running merge %i %i",start,end);

実行されないので、混乱します。メモリ割り当ての問題が見つからないか、非常に明白なものが欠落している可能性があります。

マージ関数は側面に実装されていますが、コードのその部分はこの問題に直接関連していなかったため、含めなかったことに注意してください。

残りのコードを編集します：

void merge(int input[],int start, int middle, int end){
    int save_start = start;
    int temp[end-start+1];
    int index = 0;
    printf("Start merge");
    while (start<=middle || middle+1<=end){
        if (input[start]<input[middle]){
            temp[index] = input[start];
            start++;
        } else {
            temp[index] = input[middle];
            middle++;
        } 
        index++;
    }
    while  (start<=middle){
        temp[index] = input[start];
        start++;
    }

    while (middle+1<=end){
        temp[index] = input[middle];
        middle++;
    }

    int i=0;
    int a;
    for (a=save_start;i<index;a++,i++){
        input[a]=temp[i];
    }

}
4

2 に答える 2

1

ほとんどの場合、出力はバッファリングされ、印刷されるのを待っています。その文字列にを追加する\nか、を呼び出しますfflush(stdout)。

セグメンテーション違反に関する限り、十分なコードが表示されていません。デバッガーを使用してバックトレースを取得すると、さらに多くの情報が得られる場合があります。

編集：関数にいくつかの配列インデックスのバグがありますmerge。そこの最初のループの間に中央に移動していることに注意してください-それはループ状態に何をしますか？ヒント：実際の中間位置で停止する必要がありますstart。そのポイントを超えたら、続行しないでください。

編集2：そこにもいくつかのオフバイワンエラーがあります。

編集3：あなた||はする必要があります&&。

于 2013-03-04T23:43:42.523 に答える
1

私はあなたの間違いがここにあると信じています：while (start<=middle || middle+1<=end)。

start<=middle || middle+1<=endこれらの1つ以上がtrueの場合、true：start<=middleまたはmiddle+1<=end、コードがそのループ内の配列の範囲外で読み取りおよび書き込みを行うようにします。

start<=middle && middle+1<=endこれらすべてが真の場合は真です：start<=middleおよびmiddle+1<=end、配列の範囲外で読み取りおよび書き込みを行う可能性がある場合にループが中断します。

あなたはおそらく意味しwhile (start<=middle && middle+1<=end)ます。

于 2013-03-05T00:35:41.023 に答える