对计数数组长度为 27 的字符串进行基数排序

Question

我想创建一个基数 LSD 来对字符串进行排序。我试图适应

count[27]

而不是

count[256]

，因为练习需要它。我尝试使用

A[I][d] - 'a' + 1

表示 [a-z]，使用

0

表示空格，但排序不正确。我的测试中的一些字符串已重复。我该如何解决这个问题？

#define MAX 15
void foo(char** A, int n, int k, int max) {
  int i, d;
  char** B = (char**)malloc(sizeof(char*) * n);

  for(i = 0; i < n; i++)
    B[i] = (char*)malloc(sizeof(char) * max);

  for (d = max - 1; d >= 0; d--) {
    int* count = (int*)malloc(sizeof(int) * k);
    
    for(i = 0; i < k; i++)
      count[i] = 0;

    for (i = 0; i < n; i++) {
      if(A[i][d] == 32) count[0]++;
      else count[A[i][d] - 'a' + 1]++;
    }

    for (i = 1; i < k; i++)
      count[i] += count[i - 1];
    
    for (i = n - 1; i >= 0; i--) {
      if(A[i][d] == 32) {
        strcpy(B[count[0] - 1], A[i]);
        count[0]--;
      }
      else {
        strcpy(B[count[A[i][d] - 'a' + 1] - 1], A[i]);
        count[A[i][d]]--;
     }
    }

    for (i = 0; i < n; i++)
      strcpy(A[i], B[i]);

    free(count);
  }

  for(i = 0; i < n; i++) free(B[i]);
  free(B);
}

int main() {
  int n, i, j, max = 0;

  scanf("%d", &n);

  char** A = (char**)malloc(sizeof(char*) * n);

  for (i = 0; i < n; i++)
    A[i] = (char*)malloc(sizeof(char) * MAX);

  for(i = 0; i < n; i++) {
    scanf("%s", A[i]);
    if(strlen(A[i]) > max) max = strlen(A[i]);
  }

  for (i = 0; i < n; i++) {
    for (j = 0; j < MAX; j++) {
      if (A[i][j] >= 65 && A[i][j] <= 90) A[i][j] += 32;
      else if(A[i][j] == 0) A[i][j] = 32;
    }
  }

  foo(A, n, 27, max);

  for(i = 0; i < n; i++)
    printf("%s\n", A[i]);

  for(i = 0; i < n; i++) free(A[i]);
  free(A);
  
  return 0;
}

Answer 1

该程序存在很多风格和效率问题，但我只发现了三个实际错误：

1. 您依赖于每个

   A[i]

   的所有元素的值，但您无法可靠地设置所有元素。具体来说，

   malloc()

   不会初始化它分配的内存，并且

   scanf()

   不会在字符串终止符之后写入任何字节。您可以通过通过

   calloc()

   而不是

   malloc()

   分配来解决此问题。

2. 您一开始就没有为字符串分配足够的空间。您依赖于

   MAX

   个字符 加上 字符串终止符的空间，但您仅为

   MAX

   个字符分配空间。

3. （可能是导致观察到的不当行为的问题）您的排序函数无法正确管理其

   count

   数组。具体来说，这是错误的：

           count[A[i][d]]--;
   

   应该是

           count[A[i][d] - 'a' + 1]--;