c - 我需要使用 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 指针终止，但它也应该很容易适应长度有限的列表。我还假设它只是单链表 - 双链表的基本方法类似，但当然您需要更新下一个和上一个指针。