sorting rapide avec des listes chaînées

J’ai écrit le programme suivant qui utilise l’algorithme quicksort pour sortinger le nombre d’intes insérés dans la ligne de commande à l’aide de listes chaînées. Non seulement je reçois une erreur ISO C90 à propos de déclarations mixtes, mais il y a une fuite de mémoire quelque part dans mon code et je ne suis pas sûr de la façon de la réparer. Toute aide serait appréciée!

#include  #include "linked_list.h" #include  #include "memcheck.h" #include  #include  node *quicksort(node *list); int ListLength (node *list); int main(int argc, char *argv[]) { if (argc == 1) { fprintf(stderr, "usage: %s [-q] number1 number2 ... \ (must enter at least one argument)\n", argv[0]); exit(1); } node *list; node *sorted_list; int i; int intArg = 0; /* number of integer arguments */ int print = 1; /* if -q is found anywhere then we are going * to change the behavior of the program so that * it still sorts but does not print the result */ for ( i = 1 ; i < argc; i++) { if (strcmp(argv[i], "-q") == 0) { print = 0; } else { list = create_node(atoi(argv[i]), list); /* memory allocation in the create_node function */ intArg++; } } if (intArg == 0) { fprintf(stderr, "usage: %s [-q] number1 number2 ...\ (at least one of the input arguments must be an integer)\n", argv[0]); exit(1); } sorted_list = quicksort(list); free_list(list); list = sorted_list; if (print == 1) { print_list(list); } print_memory_leaks(); return 0; } /* This function sorts a linked list using the quicksort * algorithm */ node *quicksort(node *list) { node *less=NULL, *more=NULL, *next, *temp=NULL, *end; node *pivot = list; if (ListLength(list) next; list = next; /* split into two */ temp = list; while(temp != NULL) { next = temp->next; if (temp->data data) { temp->next = less; less = temp; } else { temp->next = more; more = temp; } temp = next; } less = quicksort(less); more = quicksort(more); } /* appending the results */ if (less != NULL) { end = less; while (end->next != NULL) { end = end->next; } pivot->next = more; end->next = pivot; return less; } else { pivot->next = more; return pivot; } } int ListLength (node *list) { node *temp = list; int i=0; while(temp!=NULL) { i++; temp=temp->next; } return i; } 

    Dans main , vous libérez un noeud, la tête d’origine de la liste:

     sorted_list = quicksort(list); free_list(list); 

    Mais vous ne libérez jamais aucun autre noeud, même si vous les copiez. Ainsi, tous les noeuds de la liste originale sauvegardés à partir du premier flottent dans une mémoire inaccessible. Soit free sur copie, mais alors ne free pas dans main ou ne copiez pas du tout (et libérez tous les nœuds dans main , mais seulement après que vous n’en ayez plus besoin).

    Eh bien, vous n’avez pas posté le code pour free_list() ou create_node() qui sont les premiers candidats pour les memory leaks potentielles, mais je crois que votre code quicksort() a une fuite de mémoire ici:

      less = quicksort(less); more = quicksort(more); } 

    si l’une ou l’autre liste n’a qu’un seul élément, alors ce code:

     if (ListLength(list) <= 1) { node *listCopy; listCopy = copy_list(list); return listCopy; } 

    renvoie une copie de l'un des éléments. En définissant le more pointeurs de more bas, vous risquez de perdre un seul nœud.

    Considérez la liste: 2 1 3

    Le code appendait 1 à la liste less et 3 à la liste more . Ensuite, il exécutera quicksort() sur ces deux listes à un élément, retournera une copie de la liste et perdra les pointeurs sur les listes de less more nombreuses, ce qui entraînerait une fuite de mémoire de deux nœuds.

    Par coïncidence, il serait préférable de remplacer la vérification de la déclaration if ci-dessus par:

     if (list == NULL || list->next == NULL) { 

    Cela évite de devoir parcourir une liste potentiellement longue pour vérifier si elle ne contient que 0 ou 1 élément.