使用mergesort对链接列表进行排序

我目前正在研究mergesort算法。 我有三个function。 list_sort_merge，mergelist和splitlist。 list_sort_merge调用另外两个来拆分和合并列表。 我无法正常工作。 那么当我运行GDB时会发生的事情是我通过split函数并自己获取每个数字，例如以下示例：

427 42.7 4.2.7 

然后mergesort出现了，并且我发生了段错误。 会发生什么是right_list和left_list没有传递给mergesort。 当mergesort在函数comp_proc中进行比较时，它表示它们都是NULL。

我认为问题来自分裂function。

谁能看到我在这里做错了什么？

Answer 1

我最终重新实现了列表函数以适合我自己，因为我无法弄清楚代码中某些函数的接口应该如何工作，即使在注释中提示之后也是如此。 新代码仍在使用双向链表，但我将list_node_t重list_node_t为node_t并将current_list_size缩短为size 。 有一个function可以插入尾部，另一个可以从头部移除; 其他function相当简单。

现在有三个文件：主合并排序源代码（ mergelist.c ），包括测试main()程序和问题中三个函数的修订版本; 列表头（ list.h ）定义list_t类型的接口; 以及实现list_t类型的列表源代码（ list.c ）。

兴奋主要是在主要代码中，但其余部分是让事情发挥作用所必需的。 排序按降序排序（最大值为第一个）。 mergelist.c的代码中突出显示了关键的更改（我记得，而不是列表函数的接口）。 关键的调试工具是dump_list()函数。 类似的东西是调试排序和列表等的必要条件 。

严格地说，以_t结尾的类型名称是为实现保留的（请参阅_t （下划线t）后面的类型代表什么？ ）。

样本输出

在Mac OS X 10.8.5上使用GCC 4.8.1编译，64位指针。

 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

splitlist()最大的问题是列表没有被彻底切断。 如果您追踪左侧列表，则也会遍历右侧列表。 这可能会导致问题 - 事实上很多问题。

 #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); } 

Answer 2

以下是解释： http ： //www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

和示例代码： http ： //www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c