搜索
搜索

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

user081608 发表于 Dev
18
用户081608

我目前正在研究mergesort算法。我有三个功能。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。

我认为问题出在拆分功能上。

有人可以在这里看到我做错了吗？

乔纳森·莱夫勒

我最终重新实现了列表函数以适合自己，因为即使在注释中提示之后，我也无法弄清楚应如何使用代码中某些函数的接口。新代码仍可使用双向链表，但我将其重命名为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（下划线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 <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);
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

对链接列表进行排序

来自分类Dev

选择对链接列表进行排序

来自分类Dev

如何使用用户输入对链接列表进行排序？

来自分类Dev

使用mergesort vs自定义排序对arraylist进行排序

来自分类Dev

按链接名称对链接列表进行排序

来自分类Dev

如何使用 MergeSort 根据属性对泡菜对象进行排序？

来自分类Dev

对单链接列表进行并行排序

来自分类Dev

在链接列表中对最高编号进行排序

来自分类Dev

对链接列表节点的数组进行排序

来自分类Dev

对单链接列表进行并行排序

来自分类Dev

如何根据姓氏对链接列表进行排序？

来自分类Dev

在链接列表中对最高编号进行排序

来自分类Dev

如何对链接列表中的名称进行排序？

来自分类Dev

R对多个（链接的）列表进行排序

来自分类Dev

使用隔离对列表进行排序

来自分类Dev

使用c中的链接列表代码进行的插入排序有什么问题？

来自分类Dev

使用链接列表进行冒泡排序的实现有什么问题？

来自分类Dev

使用c中的链接列表代码进行的插入排序有什么问题？

来自分类Dev

列表中的Mergesort Python数值排序

来自分类Dev

使用排序函数对列表的嵌套列表进行排序。？

来自分类Dev

按字母顺序对名称的链接列表进行排序

来自分类Dev

在链接列表的方法内对日期进行排序

来自分类Dev

链接列表需要更长的时间进行排序吗？

来自分类Dev

在C中按字母顺序对链接列表进行排序

来自分类Dev

按日期对链接的哈希映射列表进行排序 Java

来自分类Dev

如何使用“最后的提示”对列表进行排序

来自分类Dev

使用jQuery对多个列表进行排序

来自分类Dev

使用sortWith对链式元组列表进行排序

来自分类Dev

使用itemgetter对字典列表进行排序

Related 相关文章

  1. 1

    对链接列表进行排序

  2. 2

    选择对链接列表进行排序

  3. 3

    如何使用用户输入对链接列表进行排序？

  4. 4

    使用mergesort vs自定义排序对arraylist进行排序

  5. 5

    按链接名称对链接列表进行排序

  6. 6

    如何使用 MergeSort 根据属性对泡菜对象进行排序？

  7. 7

    对单链接列表进行并行排序

  8. 8

    在链接列表中对最高编号进行排序

  9. 9

    对链接列表节点的数组进行排序

  10. 10

    对单链接列表进行并行排序

  11. 11

    如何根据姓氏对链接列表进行排序？

  12. 12

    在链接列表中对最高编号进行排序

  13. 13

    如何对链接列表中的名称进行排序？

  14. 14

    R对多个（链接的）列表进行排序

  15. 15

    使用隔离对列表进行排序

  16. 16

    使用c中的链接列表代码进行的插入排序有什么问题？

  17. 17

    使用链接列表进行冒泡排序的实现有什么问题？

  18. 18

    使用c中的链接列表代码进行的插入排序有什么问题？

  19. 19

    列表中的Mergesort Python数值排序

  20. 20

    使用排序函数对列表的嵌套列表进行排序。？

  21. 21

    按字母顺序对名称的链接列表进行排序

  22. 22

    在链接列表的方法内对日期进行排序

  23. 23

    链接列表需要更长的时间进行排序吗？

  24. 24

    在C中按字母顺序对链接列表进行排序

  25. 25

    按日期对链接的哈希映射列表进行排序 Java

  26. 26

    如何使用“最后的提示”对列表进行排序

  27. 27

    使用jQuery对多个列表进行排序

  28. 28

    使用sortWith对链式元组列表进行排序

  29. 29

    使用itemgetter对字典列表进行排序

热门标签

归档