C基数排序字符串数组

Question

首先，我要感谢您允许我慢慢来。我也想为我的英语道歉，它不是我的第一语言。

我写了一个小程序，用基数排序和计数排序对字符串数组进行排序。问题是它不能正常工作。当所有字符串的长度都相同时，输出是正确的，但当字符串名称超过 10 个字符时，程序会给出错误的答案。我发现在 sortPozycyjne 函数中增加 NAJDLUZSZY 之后一切正常，但我不明白为什么。

代码如下:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>      // na potrzeby tolower

#define DLUGOSC_NAPISU  30
#define ILOSC_NAPISOW   7
#define ZAKRES_WARTOSCI_A 128

char **A; // input array to sort
char **B; // output sorted array
char **pom;

// Sortowanie pozycyjne - tablice indeksowane od 1

void sortPrzezZliczanie(char **A, char **B, int ilosc, int pozycja) { //counting sort
    int i, j;
    int C[2048]; // pomocnicza tablica 'licznikow', ile razy wystepuje jaki znak w A

    for (i = 0; i <= ZAKRES_WARTOSCI_A; i++)
        C[i] = 0;
    for (j = 1; j <= ilosc; j++)
         C[A[j][pozycja]] += 1;
    for (i = 1; i <= ZAKRES_WARTOSCI_A; i++)
         C[i] = C[i] + C[i - 1];
    for (j = ilosc; j > 0; j--) {
        B[C[A[j][pozycja]]] = A[j];
        C[A[j][pozycja]] = C[A[j][pozycja]] - 1;
    }
}

void sortPozycyjne(char **A, char **B, int NAJDLUZSZY) {   // radix sort
    int i;
    for (i = NAJDLUZSZY; i >= 0; i--) {
        sortPrzezZliczanie(A, B, ILOSC_NAPISOW, i);
        pom = A; A = B; B = pom;     // input array to output
    }
}

void drukuj(char **tablica, int ilosc) {
    FILE *fp;

    if ((fp = fopen("output.txt", "w")) == NULL) {
        printf("Nie mogê otworzyæ pliku input.txt do zapisu!\n");
        return;
    }

    int i;
    for (i = 1; i <= ilosc; i++)
        //tablica[i]=toupper(tablica[i]);               
        fprintf(fp, "%s \n", tablica[i]);

    fclose(fp);
}

void czytaj(char **tablica, int ilosc) {
    FILE *fp;
    //int tmp;
    if ((fp = fopen("input.txt", "r")) == NULL) {
        printf("Nie mogê otworzyæ pliku output.txt do zapisu!\n");
        return;
    }

    char slowo[DLUGOSC_NAPISU];
    int i, j;
    for (i = 1; i <= ilosc; i++) {
        //fscanf (fp, "%d", &tmp);
        fscanf(fp, "%s", &slowo);
        // for (j = 0; j < strlen(slowo); j++)
        //     slowo[j] = tolower(slowo[j]); // zmniejszam wielkosc litery
        tablica[i] = (char*) malloc(sizeof(char) * DLUGOSC_NAPISU);
        strcpy(tablica[i], slowo);
    }
    fclose (fp);
}

int najdluzszyNapis(char **tablica, int ilosc) {  // finds maximum length of word
    int i, max = 0;
    for (i = 1; i <= ilosc; i++)
        if (strlen(tablica[i]) > max)
            max = strlen(tablica[i]);
    return max;
}

void taSamaDlugosc(char **tablica, int ilosc, int NAJDLUZSZY) {  
    // if string is lower than maximum then fill with nulls

    int i, j;
    for (i = 1; i <= ilosc; i++)
        for (j = 0; j <= NAJDLUZSZY; j++)
            if (!(96 < (int)tablica[i][j] && (int)tablica[i][j] < 123)) 
                tablica[i][j] = 0;
}

int main() {
    A = (char**)malloc(ILOSC_NAPISOW * sizeof(char*));
    B = (char**)malloc(ILOSC_NAPISOW * sizeof(char*));
    pom = (char**)malloc(ILOSC_NAPISOW * sizeof(char*));
    int NAJDLUZSZY; // length of the longest word

    printf("Wpisz napisy do tablicy A:\n");
    czytaj(A, ILOSC_NAPISOW);
    NAJDLUZSZY = najdluzszyNapis(A, ILOSC_NAPISOW);
    taSamaDlugosc(A, ILOSC_NAPISOW, NAJDLUZSZY);

    sortPozycyjne(A, B, NAJDLUZSZY);

    printf("\nSlownikowo posortowana tablica:\n");
    drukuj(B, ILOSC_NAPISOW);
    printf("%d", NAJDLUZSZY);
    return 0;
}

对于变量和函数的波兰语名称，我深表歉意。减小 NAJDLUZSZY 也会使答案正确。

Answer 1

我重新格式化了您的代码以使其可读。使用正确和一致的缩进和间距是清晰的关键。尝试并学习这种风格。

这是我的笔记:

• 如果您要在代码中使用波兰语，请将其用于注释，而不是函数或变量名。注释将帮助波兰语读者理解代码，非波兰语读者仍然有机会从变量和函数名称中理解代码。此外，它更一致，因为关键词无论如何都是英文的。我在法国与讲法语的程序员一起生活和工作，我们甚至不再用法语发表评论......

• 所有 <=很可能不正确。数组是 0基于 C:数组索引值通常从 0 运行至 n排除依据:

  for (i = 0; i < size; i++) {
      ...
  }
  

• 类型转换返回返回值malloc()被认为是糟糕的风格。我建议你使用 calloc()分配初始化为所有位零的数组:

  A = calloc(ILOSC_NAPISOW, sizeof(*A));
  ...
  

• 始终使用 {}用于非平凡循环和测试的大括号:您有一些包含 3 层无大括号语句的结构，这很容易出错。

• 你应该避免使用全局变量，尤其是像 A 这样的名字。 , B或 pom .

这是我能在几分钟内给出的尽可能多的建议，尽管基数排序是您最喜欢的算法之一，但试图理解波兰语太费力了。