2

我正在学习 Coursera 课程,我得到了一个包含 100,000 个整数的文件,可以使用合并排序进行排序。现在,我的函数恰好在前 1000 个整数上工作,但由于某种原因,一旦我达到 10000+,它就停止工作了。是的,我#define根据要测试的整数数量来修改顶部的 。我打算使用我在网上找到的另一个实现,但为什么我的代码不起作用?我想我错过了一些非常明显的东西。

哦,对于家庭作业,我需要上交对其进行排序所需的反转次数(多少次,想象一下冒泡排序,是否需要将较早/较小的数字移到较晚/较大的数字后面)。因此是全局变量。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define fileLineNumber 1000

void MergeSortL1 ( int arrayIn[], int arraySize );
int inversionCounter = 0;

int main (int argc, const char * argv[])
{
 // Declarations. Whee. Typical counter variable, i, arrayInOrder for boolean logic, a char for the file read type... and the array of so many bits...
 int array[fileLineNumber];
 int i, temp;
 FILE *fp;
 char* filePath = "/Users/TMC/Code/algorithmsCoursera/lesson1/IntegerArray.txt";
 char arrayInOrder = 1, fileOpenType;
 // Here, open a file.
 fileOpenType = 'r';
 fp = fopen( filePath, &fileOpenType);
 // Here, read into an array.
 for ( i = 0; i < fileLineNumber; i ++)
 {
  fscanf(fp,"%d", &temp);
  array[i] = temp;
 }
 fclose(fp);
 MergeSortL1(array, sizeof(array)/sizeof(int*));
 // Maybe check if it is in order.....
 for ( i = 0; i < fileLineNumber - 1; i++)
 {
  if ( array[i] > array[i+1] )
  {
   arrayInOrder = 0;
  }
 }
 /* Shorter, harder to read, have a 2 dimension array, a[2][4]. a[0] == " not" a[1] == ""      *
  * Just would need to printf ( "Array is%s in order.\n", a[arrayInOrder] ); Hard to maintian. */
 printf ("Array is" );
 if ( !arrayInOrder )
 {
  printf ( " not" );
 }
 printf (" in order.\n");
 printf ( "Inversion Counter says: %d\n\n", inversionCounter );
 // Write back to the file.
 fileOpenType = 'w';
 fp = fopen( filePath, &fileOpenType);
 for ( i = 0; i < fileLineNumber; i ++)
 {
  fprintf(fp, "%d", array[i]);
  fputc( '\n', fp );
 }
 fclose ( fp );
 return 0;
}

void MergeSortL1 ( int arrayIn[], int arraySize ) // Arrays are a pointer, so we don't need to capture a return...
{
    printf ( "------------------\nIn MergeSortL1, arraySize = %d\n------------------\n", arraySize );
    if ( arraySize <= 1 ) // Base Case.
    {
     printf ( "Base Case: Returning\n" );
     return;
    }
    else
    {
     int i = 0; // Counter variable
     char loopStillValid = 1, a1HasMore = 1, a2HasMore = 1;
     int temp1 = 0, temp2 = 0;
     int lenArray1 = ( floor(arraySize/2.0) ); // floor() and ceil() are just here in case we have an odd number of variables.
     int lenArray2 = ( ceil(arraySize/2.0) );
     int* array1 = malloc ( lenArray1 * sizeof (int) );
     int* array2 = malloc ( lenArray2 * sizeof (int) );
     for ( i = 0; i < lenArray1; i ++ ) // Assign values.
     {
      array1 [i] = arrayIn[i];
     }
     for ( i = 0; i < lenArray2; i ++ )
     {
      array2 [i] = arrayIn[i+lenArray1];
     }
     MergeSortL1 ( array1, lenArray1 );
     MergeSortL1 ( array2, lenArray2 );
     a1HasMore = lenArray1;
     a2HasMore = lenArray2;
     temp1 = 0;
     temp2 = 0;
     for ( i = 0; i < arraySize; i++)
     {
      loopStillValid = a2HasMore && a1HasMore;
      if ( loopStillValid && (array1[temp1] <= array2[temp2] ) )
      {
       arrayIn[i] = array1[temp1];
       temp1++;
      }
      else if ( loopStillValid && (array1[temp1] > array2[temp2] ) )
      {
       arrayIn[i] = array2[temp2];
       temp2++;
       inversionCounter ++;
      }
      else if (a2HasMore && !a1HasMore /*&& (array1[temp1] <= array2[temp2] )*/)
      {
       arrayIn[i] = array2[temp2];
       temp2++;
      }
      else if (!a2HasMore && a1HasMore /*&& (array1[temp1] > array2[temp2] )*/)
      {
       arrayIn[i] = array1[temp1];
       temp1 ++;
      }
      else
      {
       printf ("\n--------------\nERROR: UNCAUGHT STATUS\ni = %d\narray1[%d] = %d\narray2[%d] = %d\na1HasMore = %d\na2HasMore = %d\n--------------\n\n", i, temp1, array1[temp1], temp2, array2[temp2], a1HasMore, a2HasMore );
      }
      if ( temp1 >= a1HasMore )
      {
       temp1 --;
       a1HasMore = 0;
      }
      if ( temp2 >= a2HasMore )
      {
       temp2 --;
       a2HasMore = 0;
      }
     }
     free(array1);
     free(array2);
    }
}
4

2 回答 2

6

您的数组正在堆栈上分配,并且堆栈大小有限制。您需要在堆上分配大型数组。您可以在 c 中使用 malloc 执行此操作。

于 2012-06-24T05:31:39.910 回答
1

好的,事实证明,在存储 500、1000 和 100000 之类的值时,char 没有用。我解决了这个问题,感谢所有提出建议的人,我的写作风格也因此得到了改善。

char loopStillValid = 1, a1HasMore = 1, a2HasMore = 1;

我使用 a1HasMore 和 a2HasMore 作为布尔值。现在,作为字符,当输入的数字太高时,它们会环绕为负值。

a1HasMore = lenArray1;
a2HasMore = lenArray2;

当 lenArray1 和 lenArray2 为 500 时,这些字符被分配了负值......所以我进入了 if 语句的错误部分(-1 && -1 != true)

于 2012-06-24T16:04:59.087 回答