C Сортировка массива Radix строки

Question

Прежде всего я хочу поблагодарить вас за то, что вы позволите мне не спешить. Я также хочу извиниться за свой английский, это не мой первый язык.

Я написал небольшую программу, которая сортирует массив строк с сортировкой и сортировкой по основанию. Проблема в том, что она работает неправильно. Когда длина всех строк одинакова, то вывод правилен, но когда имя строки имеет более 10 символов, программа дает плохой ответ. Я узнал, что после увеличения NAJDLUZSZY в функции sortPozycyjne все работает нормально, но я не понимаю, почему.

Вот код:

#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.

Это столько же совет, как я могу дать в течение нескольких минут, пытаясь понять польский слишком много усилий, несмотря на Radix сорта является одним из любимых у алгоритмов.