c - 双链表、MergeSort，得到未定义和不可靠的结果

Question

在此处提问之前，我会尽力查找问题的解决方案，但我遇到了一些困难。虽然有一个用于 Java 的，但它并没有帮助我理解我的实现哪里出了问题。因此，事不宜迟，这里是一些背景，然后是问题。

尝试此操作的背景/原因

简而言之，我做这个的原因不仅仅是为了学习目的，不，这不是家庭作业，因为我的数据结构和算法课是一年后的，它是为了实际的一般用途，没有过于担心优化。因此，如果它看起来有点低效，请随时指出并告诉我如何改进它，但 100% 优化不是我的真正目标。我还创建了一个简单的日志记录工具来帮助我跟踪链表中的所有元素以帮助调试算法，即使它按照我的预期进行，我仍然无法弄清楚如何修复它。

问题

似乎有些运行非常完美，我可以看到它正确地划分和征服了列表，但其他时候，在随机的地方我看到了重复的地方。例如，here是从链接列表运行的很好。然后，如果我再次运行它，我要么得到类似的好结果，要么得到类似 this 的坏结果。

从坏处可以看出，我好像哪里搞砸了，其中一个节点指向一个直接或间接指向自己的节点。

我尝试过的。

我试图创建一个较小的数据结构来跟踪每个拆分列表的头节点和尾节点，恰本地称为 sub_list_t。

typedef struct {
    Node *head;
    Node *tail;
    size_t size;
} sub_list_t;

这背后的原因是，我认为它会让交互变得更容易，我什至拥有它自己的独立功能；原始链表也相当大，每次排序都不必要地创建 3 个链表(List_One、List_Two 和 Final_List)。原始列表包含 rwlocks 以尝试使它们并发，因此创建 3n 个短期锁的开销没有多大意义。因此，IMO，迷你/子列表更容易也更好。

这里实现了将每个子列表拆分合并成最终列表sort_lists的函数。

static sub_list_t *sort_list(sub_list_t *list, Linked_List_Compare compare){
    if(list->size == 1) {
        return list;
    }
    size_t mid = list->size / 2;
    sub_list_t *list_one = sub_list_of(list, 0, mid-1);
    list_one = sort_list(list_one, compare);
    sub_list_t *list_two = sub_list_of(list, mid, list->size - 1);
    list_two = sort_list(list_two, compare);
    sub_list_t *final_list = merge_lists(list_one, list_two, compare);
    free(list_one);
    free(list_two);
    return final_list;
}

将每个 sub_list 拆分为更多 sub_list 的函数在此处实现...

static sub_list_t *sub_list_of(sub_list_t *list, unsigned int begin, unsigned int end){
    sub_list_t *sub_list = malloc(sizeof(sub_list_t));
    int i = 0;
    size_t size = 0;
    Node *node = list->head;
    while(i < begin) {
        node = node->next;
        i++;
    }
    sub_list->head = node;
    while(i++ <= end){
        node = node->next;
        size++;
    }
    sub_list->tail = node;
    sub_list->size = size;
    return sub_list;
}

我感觉问题出在上面。我不得不多次更改它，因为我不确定。它应该准确地得到头部，但是尾部，我不确定，虽然它看起来足够好。

static void append_to_list(sub_list_t *list, Node *node){
    if(!list->size){ // If list->size == 0
        list->tail = list->head = node;
        list->size++;
        return;
    }
    // The problem must be here then? This is the only part of code that modifies what the nodes point to.
    list->tail->next = node;
    node->prev = list->tail;
    list->tail = node;
    list->size++;
}

sub_list 的简单构造函数在这里，仅在 Linked_List 创建 sub_list 或在 merge_list 中创建一个空的 final_list 时使用，在下面实现。

static sub_list_t *sub_list_create(Node *head, Node *tail, size_t size){
    sub_list_t *list = malloc(sizeof(sub_list_t));
    list->head = head;
    list->tail = tail;
    list->size = size;
    return list;
}

将列表的其余部分附加到最终列表的函数，这也可能是罪魁祸首，尽管我找不到其中的错误。

static void append_list_to_list(sub_list_t *list_src, sub_list_t *list_dst){
    Node *node = NULL;
    int i = 0;
    size_t old_size = list_dst->size;
    for(node = list_src->head; i++ < list_src->size; node = node->next) append_to_list(list_dst, node);
}

最后，处理合并和比较的 merge_list 似乎是问题的根源，因为它会调用 append_to_list 和 append_list_to_list...

static sub_list_t *merge_lists(sub_list_t *list_one, sub_list_t *list_two, Linked_List_Compare compare){
    sub_list_t *final_list = sub_list_create(NULL, NULL, 0);
    while(list_one->size > 0 && list_two->size > 0){
        if(compare(list_one->head->item, list_two->head->item) <= 0){
            append_to_list(final_list, list_one->head);
            list_one->head = list_one->head->next;
            list_one->size--;
        } else {
            append_to_list(final_list, list_two->head);
            list_two->head = list_two->head->next;
            list_two->size--;
        }
    }
    if(list_one->size > 0) {
        append_list_to_list(list_one, final_list);
    }
    if(list_two->size > 0) {
        append_list_to_list(list_two, final_list);
    }
    return final_list;
}

如果我做错了什么，请告诉我。另外，如果这被认为是一种不好的提问方式，也请告诉我。我将立即在 ideone 中处理一个可运行的示例。

编辑:Here .主要是复制结果、无限循环、节点间接指向自身等。

Edit2:我设法相当轻松地实现了插入排序，只需换出节点持有的数据而不是节点指向的位置......在 2 分钟内......但我一直在尝试做merge sort 大概2天没用。但我仍然不知道它究竟是如何工作的。

Answer 1

自下而上的合并排序更适合于对链表进行排序。一种有效的方法是使用指向列表第一个节点的指针数组，其中 array[i] 指向的节点数是 2^i(2 的 i 次方)，或者 array[i] 是一个空列表。

双链表在归并排序时可以当作单链表处理，一旦列表排序后，之前的链表就固定了。

节点从原始列表中一次一个地删除并合并到数组中，然后合并数组中的列表以形成单个排序列表。由于您似乎很快需要此代码，因此这里是示例 C 代码:

#define NUMLISTS 32                     /* number of lists */

typedef struct NODE_{
struct NODE_ * next;
int data;
}NODE;

NODE * MergeLists(NODE *, NODE *);

NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS];                 /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
    if(pList == NULL)                   /* check for empty list */
        return NULL;
    for(i = 0; i < NUMLISTS; i++)       /* zero array */
        aList[i] = NULL;
    pNode = pList;                      /* merge nodes into aList[] */
    while(pNode != NULL){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
            pNode = MergeLists(aList[i], pNode);
            aList[i] = NULL;
        }
        if(i == NUMLISTS)
            i--;
        aList[i] = pNode;
        pNode = pNext;
    }
    pNode = NULL;                       /* merge array into one list */
    for(i = 0; i < NUMLISTS; i++)
        pNode = MergeLists(aList[i], pNode);
    return pNode;
}

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    while(1){
        if(pSrc1 == NULL){
            *ppDst = pSrc2;
            break;
        }
        if(pSrc2 == NULL){
            *ppDst = pSrc1;
            break;
        }
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            continue;
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            continue;
        }
    }
    return pDst;
}