logo标签列表

使用归并排序对链表进行排序

calgorithmlinked-listmergesort
4

我目前正在研究归并排序算法。我有三个函数，list_sort_merge、mergelist和splitlist。list_sort_merge调用其他两个函数来拆分和合并列表。我在尝试正确运行此功能时遇到了困难。 当我运行GDB时，会通过split函数并逐个获取每个数字，例如以下示例：

427
42.7
4.2.7

然后，归并排序出现了，并使我崩溃。问题在于right_list和left_list没有被传递给归并排序。这意味着当归并排序在函数comp_proc中进行比较时，它会说它们都是空的。
我认为问题来自于split函数。
有人能看到我在这里做错了什么吗？
好的。只是想知道正在发生什么...然后问题就出现了。在left_list->current_list_size = list_size(list_ptr)/2; right_list->current_list_size = list_size(list_ptr)/2; if(list_size(list_ptr) % 2 == 1) { left_list->current_list_size++; }中，可以简化为：right_list->current_list_size = list_size(list_ptr) / 2; left_list->current_list_size = list_size(list_ptr) - list_size(list_ptr) / 2;。这有点技巧性。 - Jonathan Leffler
如果你只是对链表进行归并排序（这种数据结构非常适合该算法），那么这比必要的复杂度要高得多。 - WhozCraig
我即将开始可怕的通勤回家，但如果今晚（美国太平洋时间）这个还在，我会发帖的。很抱歉让你们久等了，但是我的妻子比SO重要。=P - WhozCraig
@JonathanLeffler 我的splitlist似乎已经将它分割到了我认为应该分割的位置。只是当我尝试在mergesort中调用right_list和left_list时，它们都是NULL。 - user081608
1
@philliesws10 很抱歉让你等那么久，家庭事务耽搁了一下。无论如何，你可以在这个链接找到一个非常简单的示例。当然，使用头尾指针等附加清理工作还是需要的。我想传达的是算法，在进行一些复杂的指针操作后，合并排序链表会变得非常简单。很抱歉让你等了那么久，并且我没有清除内存泄漏，但我很匆忙为你解决问题。希望没关系。 - WhozCraig
显示剩余7条评论
2个回答
1

我最终重新实现了列表函数以适应自己的需求，因为即使在注释中有提示，我也无法弄清楚代码中某些函数的接口应该如何工作。新代码仍然使用双向链表，但我将list_node_t重命名为node_t并将current_list_size缩短为size。它有一个在尾部插入的函数，还有一个从头部删除的函数；其他函数都相对简单。

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

兴奋点主要在主代码中，但其余部分是必要的以使事情正常运行。排序按降序排序（最大值在前）。关键更改（我记得的除了列表函数接口之外）在mergelist.c代码中突出显示。关键调试工具是dump_list()函数。类似于此的东西对于调试排序、列表等非常重要。
严格来说，以_t结尾的类型名称是保留给实现的（请参见以_t结尾的类型表示什么？）。

样例输出

使用GCC 4.8.1在Mac OS X 10.8.5上编译，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 <assert.h>

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 <stdio.h>

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 <assert.h>
#include <inttypes.h>
#include <stdlib.h>

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);
}
哇！非常感谢你的帮助！我已经编辑了我的代码，加入了那个部分，但是当我进入mergelist的comp_proc部分时，仍然出现了segfault。它说在比较它们时它们是NULL。 - user081608
由于我无法看到您的实际列表函数或实际 comp_proc()，我不确定您遇到了什么问题。我作弊了，将数据成员（我的代码中的整数）直接传递给了 comp_proc，因此我的代码中没有空指针。尽管传递两个节点不难，但并不清楚比较器是否需要理解 node_t 结构（您代码中的 list_node_t）。将 typedef int data_t; 替换为 typedef char *data_t 并在 comp_proc() 和 node_construct() 中进行适当更改以及打印代码应该很容易理解。 - Jonathan Leffler
好的，我明白了。经过进一步的GDB调试，我发现当它进入mergelist函数时，数据为NULL。因此，它没有从splitlist传递过来。 - user081608
assert()是你的好朋友...还有dump_list()函数。 - Jonathan Leffler
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接