1

我正在尝试使用数组实现合并排序。我的代码正在跳入循环而不是停止。我需要使用 Ctrll+Z 来停止我的程序。基本上我正在从文件中读取并将该数组传递给合并排序函数,然后我再次写入文件。写入文件后,我计算编程时间并显示它。请检查我下面的代码。谢谢。

#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;

这修复了分段错误。现在从 main() 方法的末尾而不是从 merge() 调用 writesortedarraytofile。这会将递归输出修复到 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() 中的错误。

编辑 -发现 0 进入输出的问题。下一个解决方法是传递counter-1而不是countermergesort()。在这个程序工作得很好之后。

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 回答