固定计数数组的 LSD 基数

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);
}

Answer 1

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

1. 您依赖于每个

   A[i]

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

   malloc()

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

   scanf()

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

   calloc()

   而不是

   malloc()

   分配来解决此问题。

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

   MAX

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

   MAX

   个字符分配空间。

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

   count

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

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

   应该是

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