您所在的位置： 首页 > 最新热文 > 计算机探索

    使用归并到链表排序并到、链表

    2023-09-11 23:15:26 作者：一抹残阳╮念离殇

    我目前工作的归并排序算法。我有三个功能。 list_sort_merge，mergelist和splitlist。 list_sort_merge调用其他两个分裂和合并清单。我无法得到这个才能正常工作。

    I am currently working on the mergesort algorithm. I have three functions. list_sort_merge, mergelist and splitlist. list_sort_merge calls the other two to split and merge the list. I am having trouble getting this to work correctly. So what happens when I run GDB is that I get through the split function and get each number by itself such as the following example:

    427
42.7
4.2.7

    然后归并出现了，出现segfaults我。会发生什么事是right_list和left_list不会被传递到合并排序。含义时，归并进去功能comp_proc来比较，它说，它们都为null。

    Then the mergesort comes along and segfaults me. What happens is the right_list and left_list are not being passed to mergesort. Meaning when mergesort goes to compare in the function comp_proc, it says that they are both NULL.

    我认为这个问题是从分割函数来了。

    I think the problem is coming from the split function.

    有人能看到我在做什么错在这里？

    Can anyone see what I am doing wrong here?

    推荐答案

    我最终重新实现列表功能以适应自己，因为我不知道如何接口的一些在code中的功能被认为工作，即使在注释中的提示。新的code仍然是工作用双向链表，但我改名 list_node_t 到 node_t 缩短 current_list_size 到尺寸。有一个功能以插入在尾，而另一个从头部移除;其他功能是相当直接的。

    I ended up reimplementing the list functions to suit myself because I couldn't work out how the interfaces to some of the functions in the code were supposed to work, even after the hints in the comments. The new code is still working with a doubly-linked list, but I renamed list_node_t to node_t and shortened current_list_size to size. There's a function to insert at the tail, and another to remove from the head; the other functions are fairly straight-forward.

    现在有三个文件：主合并排序源$ C ​​$ C（ mergelist.c ），其中包括测试的main（） 程序，并在问题的三种功能的修订版;列表头（ list.h ）定义的接口 list_t 类型;而列表源$ C ​​$ C（ list.c ）实施 list_t 键入

    There are now three files: the main merge-sort source code (mergelist.c), including a test main() program and the revised versions of the three functions in the question; the list header (list.h) defining the interface to the list_t type; and the list source code (list.c) implementing the list_t type.

    兴奋主要是在主code，但其余是必要的，把事情的工作。排序排序中（第一最大值）降序排列。关键的变化（即我记得了，比接口列表功能等）在code都强调了 mergelist.c 。关键的调试工具是 dump_list（）功能。同样的事情也该是的先决条件的用于调试排序和列表等。

    The excitement is mostly in the main code, but the rest was necessary to get things to work. The sort sorts in descending order (largest value first). The crucial changes (that I recall, and other than the interface to the list functions) are highlighted in the code for mergelist.c. The key debugging tool was the dump_list() function. Something similar to that is a sine qua non for debugging sorts and lists and so on.

    严格，在 _t 结尾类型的名称被保留用于执行（见What没有一个类型，然后按 _t （下划线T）重新present ？）。

    Strictly, type names ending in _t are reserved for the implementation (see What does a type followed by _t (underscore t) represent?).

    与GCC 4.8.1在Mac OS X 10.8.5编译，64位指针。

    Compiled with GCC 4.8.1 on Mac OS X 10.8.5, 64-bit pointers.

    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（）是，名单中没有完全切断。如果你找到了左侧的列表中，你走过的右侧列表了。这可能导致问题。 - 很多问题，实际上

    mergelist.c

    The biggest problem in splitlist() was that the lists were not cleanly severed. If you tracked down the left list, you traversed the right list too. This could lead to problems — lots of problems, in fact.

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

    上一篇：则为a.length和A.heap尺寸之间的区别是什么？则为、尺寸、区别、heap

    下一篇：一个更好的青蛙交叉算法算法、青蛙

    相关推荐
     
    猜您喜欢
    电冰箱夏天启几档最适合，1到3挡最适合制冷效验佳省电还没有结冰

    电冰箱夏天启几档最适合，1到3挡最适合制冷

    精彩图集
    精彩推荐
    图片推荐

    探秘家（tanmijia.com），深层探秘世界自然奇观未解之谜，揭秘宇宙空间、人类、生物未解之谜,世界传闻、奇闻异事ufo未解之谜。有效真实科学探索天下奇观猎奇世界。

    © 2016-2021 探秘家. All Rights Reserved 浙ICP备20029812号-3