Как объединить два отсортированных связанных списков в C? - PullRequest
Новая
       10

Как объединить два отсортированных связанных списков в C?

0 голосов
/ 20 мая 2018

Я пытаюсь объединить два отсортированных связанных списка, но не получаю требуемый O / P.Я думаю, что есть некоторая проблема с распределением адресов, но я не уверен.Кто-нибудь может подсказать, почему я не получаю o / p?

struct Node* SortedMerge(struct Node* a, struct Node* b)
{
    struct Node *head;
    struct Node  **tail=&head;

    while(1)
    {
        if(a==NULL)
        {
           *tail=b;
            break;
        }

        if(b==NULL)
        {
            *tail=a;
            break;
        }

        if(a->data<=b->data)
        {
            *tail=a;
            a=a->next;
            (*tail)->next=NULL;
        }
        else
        {
            *tail=b;
            b=b->next;
            (*tail)->next=NULL;
        }

        (*tail)=(*tail)->next;
    }
    return head;

}

Ответы [ 2 ]

0 голосов
/ 20 мая 2018

Вы должны рассмотреть возможность использования функции добавления, чтобы упростить ваш код.Вот пример: 

#include <stdio.h>
#include <stdlib.h>

struct List {
    struct Node *head;
    struct Node *tail;
};

struct Node {
    int data;
    struct Node *next;
};

void append(struct List *list, struct Node *node) {
    struct Node *nodeCopy = malloc(sizeof(struct Node));
    nodeCopy->data = node->data;
    nodeCopy->next = NULL;

    if (list->head == NULL) { // Empty list
        list->head = nodeCopy;
        list->tail = nodeCopy;
    } else {
        list->tail->next = nodeCopy;
        list->tail = nodeCopy;
    }
}

void print(struct List *list) {
    for (struct Node *node = list->head; node != NULL; node = node->next) {
        printf("%d,", node->data);
    }
    printf("\n");
}

struct List* SortedMerge(struct Node* a, struct Node* b)
{
    struct List *list = malloc(sizeof(struct List));
    list->head = NULL;
    list->tail = NULL;

    while(1)
    {
        if(a==NULL && b==NULL)
        {
            break;
        }

        if(a==NULL && b!=NULL)
        {
            append(list, b);
            b = b->next;
        }

        else if(b==NULL && a!=NULL)
        {
            append(list, a);
            a = a->next;
        }

        else if(a->data<=b->data)
        {
            append(list, a);
            a = a->next;
        }
        else
        {
            append(list, b);
            b = b->next;
        }
    }

    return list;
}

int main() {
    struct List listA = { NULL, NULL };
    struct List listB = { NULL, NULL };

    struct Node node1 = { 1, NULL };
    struct Node node2 = { 2, NULL };
    struct Node node3 = { 3, NULL };
    struct Node node4 = { 4, NULL };
    struct Node node5 = { 5, NULL };

    append(&listA, &node1);
    append(&listA, &node4);
    print(&listA);

    append(&listB, &node2);
    append(&listB, &node3);
    append(&listB, &node5);
    print(&listB);

    struct List *mergedList1 = SortedMerge(listA.head, listB.head);
    print(mergedList1);

    struct List *mergedList2 = SortedMerge(listB.head, listA.head);
    print(mergedList2);

    return 0;
}
0 голосов
/ 20 мая 2018 
(*tail)=(*tail)->next;

Замените это на: - 

tail = &( (*tail)->next );

Я надеюсь, что это будет работать.

...