2011-02-04 71 views
2

我有下面的代碼合併兩個排序鏈表:幫助與遞歸函數

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

我想你忘記真正建立在你的遞歸函數的輸出列表。在你的歸納情況下,你爲什麼不添加一些你從遞歸調用中得到的列表? – 2011-02-04 04:32:11

回答

3

您的基本情況是正確的。但是遞歸條件存在問題。

當你比較a的數據與b的數據你是不是複製節點a或節點bresult

嘗試:

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); 
+0

感謝codaddict。它現在有效。 – user602623 2011-02-04 04:37:51