c-Merge Sort连续循环并进入分段故障

Question

我正在尝试使用数组实现合并排序。我的代码正在跳到循环中并且没有停止。我需要使用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 %sn",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,"%dn",ssarray[i]);
        fclose(fp);
        printf("The output file is generated.Please check it inside the directory.n");
        printf("Time elapsed: %fn", ((double)clock() - start) / CLOCKS_PER_SEC);
        return;
}

Answer 1

我没有自己尝试代码，但使用这么大的数组作为局部变量听起来不是一个好主意。在读取文件时也不会进行任何边界检查。这可能会损坏堆栈并导致不可预测的结果。

更好的解决方案可能是：

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

和

while((fgets(line,80,fp) !=NULL) && (i < MAX_COUNT))

Answer 2

在mergesort中，您已经编写了int mid=0。相反：

int mid=(begin+end)/2;

这修复了分段错误。现在从main（）方法的末尾调用writesortedraytofile，而不是从merge（）调用。这将修复递归输出到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中得到排序的数字。还有一个问题。对于输入：（3，4，1，5，6，7，3，9，10）输出即将到来：（0，1，3，3，4、5，6、7，9）。不确定为什么最后一个数字被0替换。这个问题肯定是因为merge（）中的一个错误。

EDIT-发现0进入输出的问题。下一个修复方法是将counter-1而不是counter传递给mergesort（）。之后这个程序运行得很好。

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
}