我需要使用遞歸合併原則用C

Question

我試試這個從列表中刪除重複項：

void 
    remove_duplicate(List l, int p, int r){ 
     if(p<r){ 
      int q =(r+p)/2; 
      remove_duplicate(l,p,q); 
      remove_duplicate(l,q+1,r); 
      merge_(l,p,q,r); 
     } 
    } 

    void 
    merge_(List lst, int p, int q, int r){ 
     int i = p; 
     int j=q+1; 
     int l = r; 
     link lp = retNode(lst,p); 
     link lq = retNode(lst,q+1); 
     while(i<=q){ 
      j=q+1; 
      while(j<=l){ 
       if(lp->item==lq->item){remNode(lst,j);j--;l--;} 
       j++;lq=lq->next;} 
       i++;lp = lp->next;} 
    } 

但是，「子列表」的大小變得更低，當我刪除一個元素，然後不工作， 有任何想法嗎？

Answer 1

這個遞歸方法不會很好地工作，因爲當你從數組中移除項目時，你必須將所有東西都移下來。這會弄亂父遞歸調用列表中的偏移量。

您可以將調用修改爲merge，以便參數是指針，如果列表調整大小，它們會更新爲新值。然後，您還必須讓remove_duplicates以相同的方式返回這些值。這很可能非常複雜，但是如果您要更改列表的大小，那麼我不會看到任何其他方法 - 遞歸鏈中的父調用需要知道它們的邊界因內部調用從列表。只要記住在將指針傳遞給下一次調用之前，先獲取指針傳入的值的副本，否則您只會指向相同的變量，並且會導致可怕的結果。

但是，您是否真的需要使用遞歸方法？我不認爲它是最簡單或最有效的方法 - 在這種情況下，迭代方法可能更容易實現。

你似乎使用鏈表，那麼迭代的方法可能是這樣的：

void remove_duplicates(ListItem *items) 
{ 
    while (items) { 
     ListItem *current = items; 
     while (current->next) { 
      if (current->next->item == items->item) { 
       current->next = current->next->next; 
      } else { 
       current = current->next; 
      } 
     } 
     items = items->next; 
    } 
} 

我假定你的名單是在這個例子中一個NULL指針next終止，但它應該很容易以適應長度有限的列表。我也假定它只是單鏈接的 - 雙鏈表的基本方法是相似的，但是當然你需要更新下一個和前一個指針。