在链表上实现mergesort

我的任务是在用C / C ++编写的列表上实现合并排序算法。 我有一般的想法，编写我的代码并成功编译它。 但是，当我运行它时，它会开始正常，但然后挂起“准备好的列表，现在开始排序”而不会出现任何错误。 我试图查看我的代码，但我完全不知道问题是什么。 我也非常业余的调试，所以使用gdb尽我最大的能力导致我没有在哪里。 任何建议或提示都将是一个巨大的帮助，谢谢大家！

#include  #include  struct listnode { struct listnode *next; int key; }; //Finds length of listnode int findLength (struct listnode *a) { struct listnode *temp = a; int i = 0; while (temp != NULL) { i++; temp = temp->next; } return i; } struct listnode * sort (struct listnode *a) { // Scenario when listnode is NULL if (findLength (a) <= 1) return a; //Find middle int mid = findLength (a) / 2; struct listnode *temp = a; struct listnode *first = a; struct listnode *second; for (int i = 0; i next; } second = temp->next; temp->next = NULL; //Recursive calls to sort lists first = sort (first); second = sort (second); if (first != NULL && second != NULL) { if (first->key key) { a = first; first = first->next; } else { a = second; second = second->next; } } struct listnode *head = a; struct listnode *tail = a; while (first != NULL && second != NULL) { if (first->key key) { tail = first; first = first->next; tail = tail->next; } else { tail = second; second = second->next; tail = tail->next; } } if (first == NULL) { while (second != NULL) { tail = second; second = second->next; tail = tail->next; } } while (first != NULL) { tail = first; first = first->next; tail = tail->next; } return a; } 

这是提供的测试代码，用C：int编写

 main (void) { long i; struct listnode *node, *tmpnode, *space; space = (struct listnode *) malloc (500000 * sizeof (struct listnode)); for (i = 0; i key = 2 * ((17 * i) % 500000); (space + i)->next = space + (i + 1); } (space + 499999)->next = NULL; node = space; printf ("\n prepared list, now starting sort\n"); node = sort (node); printf ("\n checking sorted list\n"); for (i = 0; i key != 2 * i) { printf ("Node contains wrong value\n"); exit (0); } node = node->next; } printf ("Sort successful\n"); exit (0); } 

Answer 1

你很亲密，但有一些愚蠢的错误。 检查合并步骤中的追加操作。 他们没有做你认为他们的事。 当然你的意思是temp = temp->next; 在分裂循环中。

如果gdb压倒性的话，添加printf是一个非常好的方法来调试这样的代码。 实际上，您希望编写列表打印function，并在每个递归级别打印子列表以及合并步骤的结果。 看起来很有趣。 只要整洁，删除完成后的所有内容。

这里的代码可供参考：

 struct listnode *sort(struct listnode *lst) { if (!lst || !lst->next) return lst; struct listnode *q = lst, *p = lst->next->next; while (p && p->next) { q = q->next; p = p->next->next; } struct listnode *mid = q->next; q->next = NULL; struct listnode *fst = sort(lst), *snd = sort(mid); struct listnode rtn[1], *tail = rtn; while (fst && snd) { if (fst->key < snd->key) { tail->next = fst; tail = fst; fst = fst->next; } else { tail->next = snd; tail = snd; snd = snd->next; } } while (fst) { tail->next = fst; tail = fst; fst = fst->next; } while (snd) { tail->next = snd; tail = snd; snd = snd->next; } tail->next = NULL; return rtn->next; } 

在我原来的MacBook上，这有点超过4秒的1000万随机整数，这似乎并不太糟糕。

您还可以将追加操作放在宏中，并使其非常简洁：

 struct listnode *sort(struct listnode *lst) { if (!lst || !lst->next) return lst; struct listnode *q = lst, *p = lst->next->next; while (p && p->next) { q = q->next; p = p->next->next; } struct listnode *mid = q->next; q->next = NULL; struct listnode *fst = sort(lst), *snd = sort(mid); struct listnode rtn[1], *tail = rtn; #define APPEND(X) do { tail->next = X; tail = X; X = X->next; } while (0) while (fst && snd) if (fst->key < snd->key) APPEND(fst); else APPEND(snd); while (fst) APPEND(fst); while (snd) APPEND(snd); tail->next = NULL; return rtn->next; } 

Answer 2

它必须是自上而下的合并排序吗？ 为了让你开始，这是一个部分修复，没有检查其他东西。 | if（first！= NULL && second！= NULL）| 因为事先检查长度<= 1，所以不需要检查，但不会导致问题。

  while (first != NULL && second != NULL) { if (first->key < second->key) { tail->next = first; tail = first; first = first->next; } else { tail->next = second; tail = second; second = second->next; } } if (first == NULL) { tail->next = second; } else { tail->next = first; } }