c - c中的基数排序算法

Question

我曾尝试在 c 中编写基数排序。当我使用静态数组运行代码时，它运行良好。但是当我尝试从文件中获取随机输入时，它在运行时给我一个“段错误”。help 请帮助修改此代码 这是我的代码:

 #include <stdio.h>
 #include <stdlib.h>
 #include<math.h>
 #include<string.h>
 int getMax(int arr[], int n)
 {
    int mx = arr[0];
    int i;
    for (i = 1; i < n; i++)
      if (arr[i] > mx)
        mx = arr[i];
    return mx;
 }
 void countSort(int arr[], int n, int exp,int base)
 {
   int output[n]; 
   int i;
   int count[base];
   memset(count, 0, sizeof count);
   for (i = 0; i < n; i++)
     count[ (arr[i]/exp)%base]++;
   for (i = 1; i < base; i++)
     count[i] += count[i - 1];
   for (i = n - 1; i >= 0; i--)
   {
     output[count[ (arr[i]/exp)%base ] - 1] = arr[i];
     count[ (arr[i]/exp)%base ]--;
   }
   for (i = 0; i < n; i++)
     arr[i] = output[i];
 }
void radixsort(int arr[], int n,int base)
{
  int m = getMax(arr, n);
  int exp;
  for (exp = 1; m/exp > 0; exp *= 10)
    countSort(arr, n, exp , base);
}
void print(int arr[], int n)
{
  int i;
  for (i = 0; i < n; i++)
    printf("%d ",arr[i]);
}
int main(int argc,int argv[])
{
  int base=atoi(argv[1]);
  int num,i;
  FILE *fp1=fopen("myFile1.txt","r");
  int arr[50];
  while(fscanf(fp1,"%d",&num)==1)
  {
        arr[i]=num;
        i++;
  }
  int n = sizeof(arr)/sizeof(arr[0]);
  radixsort(arr, n ,base);
  print(arr, n);
  fclose(fp1);
  return 0;
}

Answer 1

您假设编译器已将 i 的初始值设置为 0。但是，不能保证这一点。虽然许多编译器将变量重置为 0，但许多其他编译器只是将内存设置保留在编译时或加载时发生的任何位置。使用前需要先初始化该值。

此外，您无需进行测试以确保不会超出 arr 缓冲区。例如，考虑一下如果您碰巧打开一个包含 51 个条目的文件，arr[] 会发生什么情况。您将尝试向 arr[50] 添加一个条目，这会超出缓冲区。

您需要将 i 初始化为 0并且确保在 i 变得太大时突破。

n 的计算结果始终为 50，因为 arr 是 50 个整数。您应该使用 i 作为已读入的条目数。

int main(int argc,int argv[])
{
  int base=atoi(argv[1]);
  // int num,i;  // This is the line that causes the error
  int num;
  int i = 0;  // This needs to be initialized before use.
  FILE *fp1=fopen("myFile1.txt","r");
  int arr[50];
  // You need to ensure that i does not overrrun the buffer.
  while(fscanf(fp1,"%d",&num)==1 && (i < 49))
  {
        arr[i]=num;
        i++;
  }
  // Since i was defined before the while, it should have the correct count
  // This calculation of n is wrong if fewer than a full buffer is read
  int n = sizeof(arr)/sizeof(arr[0]); 
  radixsort(arr, n, base);
  print(arr, n);
  fclose(fp1);
  return 0;
}