基于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/

10-10 14:08
查看更多