Utilisation de mergesort pour sortinger les listes chaînées

Je travaille actuellement sur l’algorithme mergesort. J’ai trois fonctions. list_sort_merge, mergelist et splitlist. list_sort_merge appelle les deux autres à se scinder et à fusionner la liste. J’ai du mal à faire en sorte que cela fonctionne correctement. Donc, ce qui se passe lorsque je lance GDB, c’est que j’obtiens la fonction de division et que je reçois chaque numéro seul, comme dans l’exemple suivant:

427 42.7 4.2.7 

Ensuite, le mergesort arrive et me sépare par défaut. Ce qui se passe, c’est que right_list et left_list ne sont pas transmises à mergesort. Cela signifie que mergesort doit comparer dans la fonction comp_proc, il est dit qu’ils sont tous deux NULL.

Je pense que le problème vient de la fonction split.

Quelqu’un peut-il voir ce que je fais mal ici?

    J’ai fini par réimplémenter les fonctions de liste à ma guise car je ne pouvais pas comprendre comment les interfaces de certaines fonctions du code étaient censées fonctionner, même après les astuces des commentaires. Le nouveau code fonctionne toujours avec une liste doublement chaînée, mais j’ai renommé list_node_t en node_t et raccourci current_list_size en size . Il y a une fonction à insérer à la queue et une autre à retirer de la tête; les autres fonctions sont assez simples.

    Il existe maintenant trois fichiers: le code source principal de fusion-sorting ( mergelist.c ), comprenant un programme test main() et les versions révisées des trois fonctions de la question; l’en-tête de liste ( list.h ) définissant l’interface avec le type list_t ; et le code source de la liste ( list.c ) implémentant le type list_t .

    L’excitation est principalement dans le code principal, mais le rest était nécessaire pour que les choses fonctionnent. Le sorting se fait par ordre décroissant (la plus grande valeur en premier). Les modifications cruciales (dont je me souviens et autres que l’interface avec les fonctions de liste) sont mises en évidence dans le code de mergelist.c . L’outil de débogage de clé était la fonction dump_list() . Quelque chose de semblable à cela est une condition sine qua non pour les sortes et les listes de débogage, etc.

    Ssortingctement, les noms de type se terminant par _t sont réservés à la mise en oeuvre (voir Que représente un type suivi de _t (trait de soulignement t)? ).

    Échantillon de sortie

    Compilé avec GCC 4.8.1 sur Mac OS X 10.8.5, pointeurs 64 bits.

     List Before (0x7FEC21C039A0) Head 0x7FEC21C039C0, Tail 0x7FEC21C03AE0, Size 10 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A20, Data 7 6: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x7FEC21C03A40, Data 5 7: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 8: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 9: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 10: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List -->>list_sort_merge() (0x7FEC21C039A0) Head 0x7FEC21C039C0, Tail 0x7FEC21C03AE0, Size 10 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A20, Data 7 6: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x7FEC21C03A40, Data 5 7: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 8: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 9: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 10: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List Split-L (0x7FEC21C03B20) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A40, Size 5 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List Split-R (0x7FEC21C03B00) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AE0, Size 5 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 4: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 5: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List -->>list_sort_merge() (0x7FEC21C03B20) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A40, Size 5 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List Split-L (0x7FEC21C03B60) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A00, Size 3 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 9 List Split-R (0x7FEC21C03B40) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A40, Size 2 1: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 2 2: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List -->>list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A00, Size 3 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 9 List Split-L (0x7FEC21C03BA0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039E0, Size 2 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 3 List Split-R (0x7FEC21C03B80) Head 0x7FEC21C03A00, Tail 0x7FEC21C03A00, Size 1 1: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x000000000000, Data 9 List -->>list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039E0, Size 2 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 3 List Split-L (0x7FEC21C03BE0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039C0, Size 1 1: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x000000000000, Data 1 List Split-R (0x7FEC21C03BC0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039E0, Size 1 1: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x000000000000, Data 3 -->>list_sort_merge() List List-L (0x7FEC21C03BE0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039C0, Size 1 1: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x000000000000, Data 1 List List-R (0x7FEC21C03BC0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039E0, Size 1 1: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x000000000000, Data 3 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039C0, Size 2 1: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x000000000000, Data 3 2: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 -->>list_sort_merge() List List-L (0x7FEC21C03BA0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039C0, Size 2 1: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x000000000000, Data 3 2: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 List List-R (0x7FEC21C03B80) Head 0x7FEC21C03A00, Tail 0x7FEC21C03A00, Size 1 1: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x000000000000, Data 9 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 3 1: Node 0x7FEC21C03A00, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x7FEC21C03A00, Data 3 3: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 List -->>list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A40, Size 2 1: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 2 2: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List Split-L (0x7FEC21C03B80) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A20, Size 1 1: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x000000000000, Data 2 List Split-R (0x7FEC21C03BA0) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A40, Size 1 1: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x000000000000, Data 7 -->>list_sort_merge() List List-L (0x7FEC21C03B80) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A20, Size 1 1: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x000000000000, Data 2 List List-R (0x7FEC21C03BA0) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A40, Size 1 1: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x000000000000, Data 7 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A20, Size 2 1: Node 0x7FEC21C03A40, Next 0x7FEC21C03A20, Prev 0x000000000000, Data 7 2: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x7FEC21C03A40, Data 2 -->>list_sort_merge() List List-L (0x7FEC21C03B60) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 3 1: Node 0x7FEC21C03A00, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x7FEC21C03A00, Data 3 3: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 List List-R (0x7FEC21C03B40) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A20, Size 2 1: Node 0x7FEC21C03A40, Next 0x7FEC21C03A20, Prev 0x000000000000, Data 7 2: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x7FEC21C03A40, Data 2 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B20) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 5 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A40, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A00, Data 7 3: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03A40, Data 3 4: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 5: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 1 List -->>list_sort_merge() (0x7FEC21C03B00) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AE0, Size 5 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 4: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 5: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List Split-L (0x7FEC21C03B40) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AA0, Size 3 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 6 List Split-R (0x7FEC21C03B60) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AE0, Size 2 1: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x000000000000, Data 0 2: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List -->>list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AA0, Size 3 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 6 List Split-L (0x7FEC21C03BA0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A80, Size 2 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x7FEC21C03A60, Data 8 List Split-R (0x7FEC21C03B80) Head 0x7FEC21C03AA0, Tail 0x7FEC21C03AA0, Size 1 1: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x000000000000, Data 6 List -->>list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A80, Size 2 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x7FEC21C03A60, Data 8 List Split-L (0x7FEC21C03BE0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A60, Size 1 1: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x000000000000, Data 5 List Split-R (0x7FEC21C03BC0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A80, Size 1 1: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x000000000000, Data 8 -->>list_sort_merge() List List-L (0x7FEC21C03BE0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A60, Size 1 1: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x000000000000, Data 5 List List-R (0x7FEC21C03BC0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A80, Size 1 1: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x000000000000, Data 8 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 2 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03A60, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 5 -->>list_sort_merge() List List-L (0x7FEC21C03BA0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 2 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03A60, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 5 List List-R (0x7FEC21C03B80) Head 0x7FEC21C03AA0, Tail 0x7FEC21C03AA0, Size 1 1: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x000000000000, Data 6 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 3 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03AA0, Data 5 List -->>list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AE0, Size 2 1: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x000000000000, Data 0 2: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List Split-L (0x7FEC21C03B80) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AC0, Size 1 1: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x000000000000, Data 0 List Split-R (0x7FEC21C03BA0) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AE0, Size 1 1: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x000000000000, Data 4 -->>list_sort_merge() List List-L (0x7FEC21C03B80) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AC0, Size 1 1: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x000000000000, Data 0 List List-R (0x7FEC21C03BA0) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AE0, Size 1 1: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x000000000000, Data 4 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AC0, Size 2 1: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x000000000000, Data 4 2: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 -->>list_sort_merge() List List-L (0x7FEC21C03B40) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 3 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03AA0, Data 5 List List-R (0x7FEC21C03B60) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AC0, Size 2 1: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x000000000000, Data 4 2: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B00) Head 0x7FEC21C03A80, Tail 0x7FEC21C03AC0, Size 5 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 4: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A60, Data 4 5: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 -->>list_sort_merge() List List-L (0x7FEC21C03B20) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 5 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A40, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A00, Data 7 3: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03A40, Data 3 4: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 5: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 1 List List-R (0x7FEC21C03B00) Head 0x7FEC21C03A80, Tail 0x7FEC21C03AC0, Size 5 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 4: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A60, Data 4 5: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C039A0) Head 0x7FEC21C03A00, Tail 0x7FEC21C03AC0, Size 10 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 8 3: Node 0x7FEC21C03A40, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A80, Data 7 4: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A40, Data 6 5: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 6: Node 0x7FEC21C03AE0, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A60, Data 4 7: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03AE0, Data 3 8: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 9: Node 0x7FEC21C039C0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A20, Data 1 10: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 0 List After (0x7FEC21C039A0) Head 0x7FEC21C03A00, Tail 0x7FEC21C03AC0, Size 10 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 8 3: Node 0x7FEC21C03A40, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A80, Data 7 4: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A40, Data 6 5: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 6: Node 0x7FEC21C03AE0, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A60, Data 4 7: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03AE0, Data 3 8: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 9: Node 0x7FEC21C039C0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A20, Data 1 10: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 0 

    mergelist.c

    Le plus gros problème de splitlist() était que les listes n'étaient pas scindées proprement. Si vous avez suivi la liste de gauche, vous avez également parcouru la liste de droite. Cela pourrait conduire à des problèmes - beaucoup de problèmes, en fait.

     #include "list.h" #include  static void mergelist(list_t *list_ptr, list_t *left_list, list_t *right_list); static void splitlist(list_t *list_ptr, list_t *left_list, list_t *right_list); static int comp_proc(data_t d1, data_t d2) { if (d1 > d2) return +1; else if (d1 < d2) return -1; else return 0; } void list_sort_merge(list_t *list_ptr) { if (list_ptr->size > 1) // 1, not 0 — do not try splitting a singleton list. { dump_list(stdout, "-->>list_sort_merge()", list_ptr); // Debug list_t *right_list = list_construct(); list_t *left_list = list_construct(); splitlist(list_ptr, left_list, right_list); dump_list(stdout, "Split-L", left_list); // Debug dump_list(stdout, "Split-R", right_list); // Debug list_sort_merge(left_list); list_sort_merge(right_list); dump_list(stdout, "Sort-L", left_list); // Debug dump_list(stdout, "Sort-R", right_list); // Debug list_ptr->head = NULL; list_ptr->tail = NULL; list_ptr->size = 0; // Additional mergelist(list_ptr, left_list, right_list); list_destruct(right_list); list_destruct(left_list); dump_list(stdout, "<<--list_sort_merge()", list_ptr); // Debug } } static void mergelist(list_t *list_ptr, list_t *left_list, list_t *right_list) { node_t *holder; fprintf(stdout, "-->>list_sort_merge()\n"); dump_list(stdout, "List-L", left_list); dump_list(stdout, "List-R", right_list); while (left_list->size > 0 && right_list->size > 0) { assert(left_list->head != 0 && right_list->head != 0); /* Sort into descending order */ if (comp_proc(left_list->head->data, right_list->head->data) > 0) { holder = list_remove_head(left_list); list_insert_tail(list_ptr, holder); } else { holder = list_remove_head(right_list); list_insert_tail(list_ptr, holder); } } while (left_list->size > 0) { holder = list_remove_head(left_list); list_insert_tail(list_ptr, holder); } while (right_list->size > 0) { holder = list_remove_head(right_list); list_insert_tail(list_ptr, holder); } fprintf(stdout, "<<--list_sort_merge()\n"); } static void splitlist(list_t *list_ptr, list_t *left_list, list_t *right_list) { if (list_ptr->size > 1) { size_t temp = 0; node_t *holder = list_ptr->head; right_list->size = list_ptr->size / 2; left_list->size = list_ptr->size - right_list->size; left_list->head = list_ptr->head; right_list->tail = list_ptr->tail; while (temp < left_list->size) { temp++; holder = holder->next; } /* Make sure the two lists are separate — a major issue */ right_list->head = holder; left_list->tail = holder->prev; left_list->tail->next = NULL; left_list->head->prev = NULL; right_list->tail->next = NULL; right_list->head->prev = NULL; } } int main(void) { int values[] = { 1, 3, 9, 2, 7, 5, 8, 6, 0, 4 }; enum { NUM_VALUES = sizeof(values)/sizeof(values[0]) }; list_t *list = list_construct(); //dump_list(stdout, "Empty list", list); for (size_t i = 0; i < NUM_VALUES; i++) { node_t *node = node_construct(values[i]); list_insert_tail(list, node); //dump_list(stdout, "Inserting", list); } dump_list(stdout, "Before", list); list_sort_merge(list); dump_list(stdout, "After", list); list_destruct(list); return 0; } 

    list.h

     #ifndef LIST_H_INCLUDED #define LIST_H_INCLUDED #include  typedef int data_t; typedef struct node_t node_t; struct node_t { node_t *next; node_t *prev; data_t data; }; typedef struct list_t list_t; struct list_t { node_t *head; node_t *tail; size_t size; }; extern node_t *node_construct(data_t data); extern void node_destruct(node_t *node); extern size_t list_size(list_t *list); extern void list_insert_tail(list_t *list, node_t *node); extern node_t *list_remove_head(list_t *list); extern void list_destruct(list_t *list); extern list_t *list_construct(void); extern void dump_list(FILE *fp, const char *tag, list_t *list); extern void list_sort_merge(list_t *list_ptr); #endif /* LIST_H_INCLUDED */ 

    list.c

     #include "list.h" #include  #include  #include  extern node_t *list_head(list_t *list); extern node_t *list_tail(list_t *list); extern void list_destruct(list_t *list); extern list_t *list_construct(void); size_t list_size(list_t *list) { return list->size; } void list_insert_tail(list_t *list, node_t *node) { assert(list != 0); assert(node != 0); if (list->tail == 0) { assert(list->tail == 0 && list->head == 0 && list->size == 0); list->tail = node; list->head = node; node->prev = 0; node->next = 0; list->size = 1; } else { list->tail->next = node; node->prev = list->tail; node->next = 0; list->size++; list->tail = node; } } node_t *list_remove_head(list_t *list) { assert(list != 0); node_t *node = list->head; if (list->head != 0) { assert(list->size > 0); list->head = node->next; if (node->next != 0) node->next->prev = 0; node->prev = 0; node->next = 0; list->size--; } return node; } void list_destruct(list_t *list) { assert(list != 0); node_t *next; for (node_t *node = list->head; node != 0; node = next) { next = node->next; node_destruct(node); } free(list); } void dump_list(FILE *fp, const char *tag, list_t *list) { assert(list != 0); fprintf(fp, "List %s (0x%.12" PRIXPTR ")\n", tag, (uintptr_t)list); fprintf(fp, "Head 0x%.12" PRIXPTR ", Tail 0x%.12" PRIXPTR ", Size %zu\n", (uintptr_t)list->head, (uintptr_t)list->tail, list->size); size_t i = 0; for (node_t *node = list->head; node != 0; node = node->next) fprintf(fp, "%2zu: Node 0x%.12" PRIXPTR ", Next 0x%.12" PRIXPTR ", Prev 0x%.12" PRIXPTR ", Data %d\n", ++i, (uintptr_t)node, (uintptr_t)node->next, (uintptr_t)node->prev, node->data); } list_t *list_construct(void) { list_t *list = malloc(sizeof(*list)); if (list != 0) { list->head = 0; list->tail = 0; list->size = 0; } return list; } node_t *node_construct(data_t data) { node_t *node = malloc(sizeof(*node)); if (node != 0) { node->data = data; node->next = 0; node->prev = 0; } return node; } void node_destruct(node_t *node) { free(node); }