双链表、MergeSort，得到未定义和不可靠的结果
Doubly Linked List, MergeSort, getting undefined and unreliable results
我会尽力在此处提问之前查找问题的解决方案，但我遇到了一些困难。虽然有一个用于 Java，但它并没有帮助我理解我的实现哪里出了问题。所以事不宜迟，这里是一些背景，然后是问题。
Background/Reason 尝试这个
简而言之，我做这个的原因不仅仅是为了学习目的，不，这不是家庭作业，因为我的数据结构和算法 class 是一年后的，它是对于实际的一般用途，无需过多担心优化。因此，如果它看起来有点低效，请随时指出并告诉我如何改进它，但 100% 优化不是我的真正目标。我还创建了一个简单的日志记录工具来帮助我跟踪链表中的所有元素以帮助调试算法，即使它按照我的意图进行，我仍然无法弄清楚如何修复它。
问题
似乎有些运行非常完美，我可以看到它正确地划分和征服了列表，但其他时候，在随机的地方我看到重复的地方。例如，here is a good run from the Linked List. Then if I run it again, I either get similar good results or bad ones like 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 个短期锁的开销没有多大意义。因此，mini/sub 列表更容易也更好，IMO。
这里实现了将每个 sub_list 拆分和合并为最终列表 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 分钟内......但我一直在努力做合并排序大约 2 天无济于事。但我仍然不知道它到底是如何工作的。
自下而上的合并排序更适合对链表进行排序。一种有效的方法是使用指向列表第一个节点的指针数组，其中 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;
}
我会尽力在此处提问之前查找问题的解决方案，但我遇到了一些困难。虽然有一个用于 Java，但它并没有帮助我理解我的实现哪里出了问题。所以事不宜迟，这里是一些背景，然后是问题。
Background/Reason 尝试这个
简而言之，我做这个的原因不仅仅是为了学习目的，不，这不是家庭作业，因为我的数据结构和算法 class 是一年后的，它是对于实际的一般用途，无需过多担心优化。因此，如果它看起来有点低效，请随时指出并告诉我如何改进它，但 100% 优化不是我的真正目标。我还创建了一个简单的日志记录工具来帮助我跟踪链表中的所有元素以帮助调试算法，即使它按照我的意图进行，我仍然无法弄清楚如何修复它。
问题
似乎有些运行非常完美，我可以看到它正确地划分和征服了列表，但其他时候，在随机的地方我看到重复的地方。例如，here is a good run from the Linked List. Then if I run it again, I either get similar good results or bad ones like 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 个短期锁的开销没有多大意义。因此，mini/sub 列表更容易也更好，IMO。
这里实现了将每个 sub_list 拆分和合并为最终列表 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 分钟内......但我一直在努力做合并排序大约 2 天无济于事。但我仍然不知道它到底是如何工作的。
自下而上的合并排序更适合对链表进行排序。一种有效的方法是使用指向列表第一个节点的指针数组，其中 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;
}