Помогите с рекурсивной функцией - PullRequest
Новая
       27

Помогите с рекурсивной функцией

2 голосов
/ 04 февраля 2011

У меня есть следующий код для объединения двух отсортированных связанных списков: 

struct node* merge(struct node* a, struct node* b)
{
        struct node dummy;     

        struct node* tail = &dummy; 

        dummy.next = NULL;
        while(1)
        {
                if(a == NULL)
                {
                        tail->next = b;
                        break;
                }
                else if (b == NULL)
                {
                        tail->next = a;
                        break;
                }
                if (a->data <= b->data)
                {
                        MoveNode(&(tail->next), &a);
                }
                else
                {
                        MoveNode(&(tail->next), &b);
                }
                tail = tail->next;
        }
        return(dummy.next);
} 

void MoveNode(struct node** destRef, struct node** sourceRef)
{
        struct node* newNode = *sourceRef;

        *sourceRef = newNode->next;

        newNode->next = *destRef;

        *destRef = newNode;
}

И все работало нормально.Я пытался превратить его в рекурсивный метод, и вот что я получил: 

struct node* Merge(struct node* a, struct  node* b)
{
        struct node* result;

        if (a == NULL)
                return(b);
        else if (b==NULL)
                return(a);

        if (a->data <= b->data)
        {                
                result = Merge(a->next, b);
        }
        else
        {                
                result = Merge(a, b->next);
        }
        return(result);
}

Но в результате этого многие узлы отсутствуют.Что не так?

1 Ответ

3 голосов
/ 04 февраля 2011

Ваши базовые условия верны.Но есть проблема с вашим рекурсивным состоянием.

Когда вы сравниваете данные a с данными b, вы не копируете узел a или узел b в result.

Попробуйте: 

struct node* result; 

if (a == NULL)         
        return(b);                     
else if (b==NULL)                              
        return(a);                                             

if (a->data <= b->data)                                                
{          
        // make result point to node a.                                        
        result = a;      
        // recursively merge the remaining nodes in list a & entire list b
        // and append the resultant list to result.
        result->next = Merge(a->next, b);
}
else                                    
{                
        result = b;
        result->next = Merge(a, b->next);               
}
return(result);
...