Ce code de l'algorithme TRIE s'exécute sur le compilateur IDE CS50, mais entre dans une boucle infinie dans TDM-GCC sous Windows

Question

Le code de ce code a été écrit pour rechercher un mot dans un dictionnaire en utilisant la structure de données TRIE. Ce code fonctionne parfaitement sur mon compilateur IDE CS50 en utilisant à la fois make (Clang) et GCC et donne toujours la bonne réponse mais quand je lance le même code sur mon compilateur GCC (TDM-GCC), il passe en boucle infinie. il a commencé à utiliser beaucoup de RAM (512 Mo jusqu'à ce que je l'ai fermé avec force). Le code que j'ai exécuté était exactement le même dans les deux cas. Aussi dans les deux cas, le code compilé parfaitement.

#include <stdio.h> 
#include <string.h> 
#include <ctype.h> 
#include <stdlib.h> 

struct trieblock123; 
typedef struct trieblock123 trieblock; 
typedef trieblock *node; 
struct trieblock123 
{ 
    char alphabet; 
    char reply[5]; 
    node pnt; 
}; 


typedef struct 
{ 
    node first; 
    int count; 
}head; 

void load(FILE* dict, head* header); 
void init(node pointer); 

int main(void) 
{ 
    FILE* dict = fopen("large", "r"); 

    head* header = malloc(sizeof(head)); 
    (*header).count = 0; 
    (*header).first = NULL; 


    node curtrie = NULL; 
    node temptrie = NULL; 
    node temptrie1 = NULL; 
    char temp; 
    temp = fgetc(dict); 
    int counter = 0; 
    temptrie = (node)(malloc(26 * sizeof(trieblock))); 
    int i; 
    for(i = 0; i < 26; i++) 
    { 
     (temptrie[i]).alphabet = (char)(((int)('a')) + i); 
     (temptrie[i]).pnt = NULL; 
    } 
    if(counter == 0) 
    { 
     (*header).first = temptrie; 
    } 
    while(((int)(temp) <= (int)('z') && (int)(temp) >= (int)('a')) || temp == '\n') 
    { 
     if(((int)(temp) > (int)('z') || (int)(temp) < (int)('a')) && temp != '\n') 
      break; 
     curtrie = temptrie; 

     while(temp != '\n') 
     { 
      char temp1; 
      temp1 = fgetc(dict); 
      if((curtrie[(int)(temp) - (int)('a')]).pnt == NULL) 
      { 
       if(temp1 != '\n') 
       { 
        temptrie1 = (node)(malloc(26 * sizeof(trieblock))); 
        for(i = 0; i < 26; i++) 
        { 
         (temptrie1[i]).alphabet = (char)(((int)('a')) + i); 
         (temptrie1[i]).pnt = NULL; 
        } 

        (curtrie[(int)(temp) - (int)('a')]).pnt = temptrie1; 
        curtrie = temptrie1; 
       } 
       else 
       { 
        strcpy((curtrie[(int)(temp) - (int)('a')]).reply, "yes"); 
       } 
      } 
      else if((curtrie[(int)(temp) - (int)('a')]).pnt != NULL) 
      { 
       curtrie = (curtrie[(int)(temp) - (int)('a')]).pnt; 
      } 
      fseek(dict, -1 * sizeof(char), SEEK_CUR); 
      temp = fgetc(dict); 
     } 


     if(temp == '\n') 
     { 
      temp = fgetc(dict); 
     } 

     counter++; 
    } 
    (*header).count = counter; 

    char tocheck[100]; 
    scanf("%s", tocheck); 

    i = 0; 
    node start = NULL; 
    start = temptrie; 

    for(i = 0; i < strlen(tocheck); i++) 
    { 
     char cha = tocheck[i]; 
     if(i != strlen(tocheck) - 1) 
     { 
      if((start[(int)(cha) - (int)('a')]).pnt == NULL) 
      { 
       printf("mis-spelled\n"); 
       break; 
      } 
      else 
      { 
       start = (start[(int)(cha) - (int)('a')]).pnt; 
      } 
     } 
     else 
     { 
      if(strcmp(((start[(int)(cha) - (int)('a')]).reply), "yes") == 0) 
      { 
       printf("correctly spelled\n"); 
       break; 
      } 
      else 
      { 
       printf("mis-spelled\n"); 
       break; 
      } 
     } 
    } 
    return 0; 
} 

Answer 1

Ce n'est peut-être pas le genre de réponse que vous attendez.

Votre code est difficile à déboguer et à maintenir à cause de ce problème:

1. répétitions - ce qui est sujette à l'erreur, utiliser les fonctions au lieu
2. trop de moulages inutiles - vérifier le système de type C et comment les types sont implicitement converti à l'autre
3. typedefs étranges - redéfinissent pas les types de pointeur sauf si vous utilisez une sorte de suffixe ou préfixe pour indiquer que le typedef respectif est en effet un pointeur
4. trop de parenthèses, vous n'avez pas besoin plupart d'entre eux (es) pecially le genre de choses (* s) .a = utilisation de quelque chose -> au lieu)

D'autres problèmes sont les suivants:

1. Chaque fois que vous malloc ne vous attendez pas seulement d'avoir des zéros là-dedans (en fait ne vous attendez pas à avoir de la mémoire à tout moment), votre code d'origine peut segfault dans le cas où la réponse est initialisée avec des déchets.
2. Les chaînes de C sont terminées par zéro, donc faire strlen implique une itération sur la chaîne entière, à moins que vous ne la modifiez, il suffit de mettre en cache le résultat une fois dans une variable et de l'utiliser.
3. Suivre vos instructions conditionnelles il n'est pas nécessaire de vérifier les conditions négatives.
4. En travaillant avec IO, essayez de minimiser les appels lorsque cela est approprié.
5. Ne pas mélanger la responsabilité. Par exemple, la vérification du code pour l'existence d'une chaîne dans votre structure ne devrait pas être la responsabilité d'imprimer la réponse.
6. N'utilisez pas de chaînes comme des drapeaux, cela est tout simplement déroutant.

Celui-ci devrait être un équivalent (à moins que je foiré):

#include <stdio.h> 
#include <string.h> 
#include <ctype.h> 
#include <stdlib.h> 

typedef struct node_s node_t; 
struct node_s { 
    char alphabet; 
    char present; 
    node_t *pnt; 
}; 

typedef struct { 
    node_t *first; 
    int count; 
} head_t; 

#define NLETTERS 26 
inline static int is_letter(char c) { return c <= 'z' && c >= 'a'; } 

inline static node_t* new_trieblock() { 
    const int size = NLETTERS * sizeof(node_t); 
    node_t* block = malloc(size); 
    memset(block, 0, size); 
    for (int i = 0; i < NLETTERS; i++) { 
    block[i].alphabet = 'a' + i; 
    } 
    return block; 
} 

inline static int trie_has(node_t *n, char *str) { 
    node_t *trie = n; 
    int len = strlen(str); 
    for (int i = 0; i < len - 1; i++) { 
    trie = trie[str[i] - 'a'].pnt; 
    if (!trie) return 0;  
    } 
    return trie[str[len-1] - 'a'].present; 
} 

int main(void) { 
    FILE* dict = fopen("large", "r"); 

    head_t *header = malloc(sizeof(head_t)); 
    header->count = 0; 
    header->first = new_trieblock(); 

    node_t *trie = header->first; 
    char c = fgetc(dict); 
    int nc; 
    while(is_letter(c) || c == '\n') { 
     nc = fgetc(dict); 

     if (nc == '\n' || nc == EOF) { 
      trie[c - 'a'].present = 1; 
      header->count++; 
     } else { 
      if (!trie[c - 'a'].pnt) { 
      trie = trie[c - 'a'].pnt = new_trieblock(); 
      } else { 
      trie = trie[c - 'a'].pnt; 
      } 
     } 

     c = nc; 
     while (c == '\n') { 
      trie = header->first; 
      c = fgetc(dict); 
     } 
    } 

    char tocheck[100]; 
    scanf("%s", tocheck); 

    if (trie_has(header->first, tocheck)) { 
     printf("correctly spelled\n"); 
    } else { 
     printf("mis-spelled\n"); 
    } 

    return 0; 
}