基于Wikipedia网站上用于合并排序的伪代码,我可以找到一个节点正确合并为两个节点列表的基本情况但是,我认为合并的部分在向递归链上移动时会反转。
我正在使用Makefile:
sort: main.c sort.c
gcc -Wall -std=c99 -o $@ main.c sort.c ll.c
我使用的是包含头指针和尾指针的列表头结构头指向第一个节点,尾指向最后一个节点。
合并函数正在工作,但这里是排序函数。
void list_sort(list_t *list)
{
printf("in sort 1\n");
//base case of 0 or 1 element
if (list->head == NULL || list->head->next == NULL) {
return;
}
list_t *sublistA = list_create();
assert(sublistA);
list_t *sublistB = list_create();
assert(sublistB);
int len = Length(list);
int mid = (len) / 2;
printf("mid is %d\n", mid);
int i = 0;
element_t *current = list->head;
//make sublists
while (i < len) {
if (i < mid) {
printf("append sublistA\n");
list_append(sublistA, current->val);
} else {
printf("append sub B\n");
list_append(sublistB, current->val);
}
i++;
current = current->next;
}
list_print(sublistA);
list_print(sublistB);
printf("going to sort A\n");
list_sort(sublistA);
printf("going to sort B\n");
list_sort(sublistB);
//this was just added to capture returned list from merge
list_t* capture = NULL;
assert(capture);//the assertion failed
capture = merge(sublistA, sublistB);
}
编辑:
断言失败,因此我切换到:
list_t* capture = list_create();
assert(capture);
capture = merge(sublistA, sublistB);
我确信在main、merge和sort的printf语句中没有正确捕获它。
下面是显示意外反转的命令行输出:
/* left and right lists to merge://at the start of the merge function
{ 8, }
{ 7, }
in merge while 1
in merge else 1
{ 7, }
final result
{ 7, 8, }//yay! this is the last line of merge function
in merge//came right back again to merge
left and right lists to merge:
{ 9, }
{ 8, 7, }//doh!*/
编辑:下面是合并函数:
list_t *merge(list_t *left, list_t *right) {
printf("in merge\n");
list_t *result = list_create();
assert(result);
element_t *curr1 = left->head;
element_t *curr2 = right->head;
//list_t *result = list_create();
printf("left and right lists to merge: \n");
list_print(left);
list_print(right);
while (curr1 != NULL && curr2 != NULL) {
printf("in merge while 1\n");
if (curr1->val <= curr2->val) {
list_append(result, curr1->val);
printf("merge while 1 if\n");
curr1 = curr1->next;
//curr2 = curr2->next;
}
else //curr1->val > curr2->val
{
printf("in merge else 1\n");
list_append(result, curr2->val);
curr2 = curr2->next;
}
}
list_print(result);
//leftovers need to be allocated
while (curr1 != NULL) {
list_append(result, curr1->val);
curr1 = curr1->next;
}
while (curr2 != NULL) {
list_append(result, curr2->val);
curr2 = curr2->next;
}
//printf("curr1->val is %d\n", curr1->val);
//printf("curr2->val is %d\n", curr2->val);
list_destroy(left);
list_destroy(right);
printf("final result\n");
list_print(result);
return result;
}
最佳答案
我注意到merge
函数的工作方式是破坏性地修改输入列表:将两个列表作为输入,生成一个新的合并列表作为输出,然后返回结果列表但是,在list_sort
函数中,您不会捕获返回的新列表,因此您不会更新提供的输入列表来保存新排序的序列尝试从merge
捕获返回值并使用它更新输入列表参数。
关于c - C:合并链表的排序,排序函数中未正确捕获合并的子数组,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/45555053/