1

配列を使用してマージソートを実装しようとしています.コードがループにジャンプして停止しません.Ctrll + Zを使用してプログラムを停止する必要があります.基本的に、ファイルから読み取り、その配列をmergesort関数に渡します.もう一度ファイルに書き込みます。ファイルに書き込んだ後、プログラミング時間を計算して表示します。以下のコードを確認してください。ありがとうございます。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

clock_t start=clock();
void mergesort(int *,int,int);
void merge(int *,int,int,int);
void writesortedrraytofile(int *,int);

static char *opfile=(char *)"output.txt";

int main(int argc,char* argv[])
{
        FILE *fp;
        char line[80];
        int array[1000000];
        int i=0,counter;
        int choice;


        printf("The command line arguments are:\n");
        printf("%d %s %s %s\n",argc,argv[0],argv[1],argv[2]);

        if(argc==3 && strcmp(argv[0],"./sorting")==0 && strcmp(argv[1],"input1.txt")==0 && strcmp(argv[2],"output.txt")==0)
        {
                printf("The command line arguments are correct.\n");
        }
        else
        {
                printf("The command line arguments are wrong.I am exiting.\n");
                exit (0);
        }
fp=fopen(argv[1],"r");
while(fgets(line,80,fp) !=NULL)
{
        sscanf(line,"%d",&array[i]);
        i++;
}
counter=i;
fclose(fp);
    mergesort(array,0,counter);
        }
        return 0;
}

void mergesort(int *temp,int begin,int end)
{
        int mid=0;
        if(begin<end)
        {
                mid=(begin+end)/2;
                mergesort(temp,begin,mid);
                mergesort(temp,mid+1,end);
        }
                merge(temp,begin,mid,end);
}

void merge(int *temp,int low,int mid,int high)
{
        int i,k;
        int *tmp = (int *) malloc((high - low +1)* sizeof(int));
        int begin1 = low;
        int end1 = mid;
        int begin2= mid +1;
        int end2 = high;

        for ( k = 0; begin1 <= end1 && begin2 <= end2; k++)
                if (temp[begin1] < temp[begin2])
                        tmp[k] = temp[begin1 ++];
                else
                        tmp[k] = temp[begin2 ++];
        while (begin1 <= end1)
                tmp[k++] = temp[begin1 ++];
        while (begin2 <= end2)
                tmp[k++] = temp[begin2 ++];
        for ( i =0;i < high -low +1; i ++)
                temp[low +i] = tmp[i];
        free(tmp);
        writesortedrraytofile(tmp,high-low+1);
        return;
}


void writesortedrraytofile(int *ssarray,int len)
{
        FILE *fp;
        fp=fopen(opfile,"w");
        for(int i=0;i<len;i++)
        fprintf(fp,"%d\n",ssarray[i]);
        fclose(fp);
        printf("The output file is generated.Please check it inside the directory.\n");
        printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
        return;
}
4

2 に答える 2

1

自分でコードを試したわけではありませんが、このような大きな配列をローカル変数として使用するのはあまり良い考えではないように思えます。また、ファイルへの読み込み時に境界チェックも行いません。これにより、スタックが破損し、予期しない結果が生じる可能性があります。

より良い解決策は次のとおりです。

#define MAX_COUNT 1000000
int* array = (int*)malloc(MAX_COUNT * sizeof(int));

と

while((fgets(line,80,fp) !=NULL) && (i < MAX_COUNT))
于 2012-09-01T07:02:37.743 に答える
0

マージソートでは、あなたは書いていint mid=0ます。代わりにこれを行います：

int mid=(begin+end)/2;

これにより、セグメンテーション違反が修正されます。merge() からではなく、main() メソッドの最後から writesortedrraytofile を呼び出すようになりました。これにより、再帰的な出力が output.txt に修正されます。

int main(int argc,char* argv[])
{
   ...
   ...
   ...
  counter=i;
  fclose(fp)
  mergesort(array,0,counter);
  writesortedrraytofile(array,counter); // call writesortedrraytofile from here
}

この後、output.txt でソートされた数値を取得します。それでももう1つ問題があります。入力の場合: (3, 4, 1, 5, 6, 7, 3, 9, 10) 出力が来ています: (0, 1, 3, 3, 4, 5, 6, 7, 9)。最後の番号が 0 に置き換えられる理由がわかりません。この問題は、merge() のバグによるものであることは間違いありません。

編集 -出力に 0 が入るという問題が見つかりました。次の修正は、mergesort()counter-1の代わりに渡すことです。counterこのプログラムの後、非常にうまく動作します。

int main(int argc,char* argv[])
{
   ...
   ...
   ...
  counter=i;
  fclose(fp)
  mergesort(array,0,counter-1); // pass counter-1 instead of counter
  writesortedrraytofile(array,counter); // call writesortedrraytofile from here
}
于 2012-09-01T07:14:19.207 に答える