0

我试试这个：

    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;}
    }

但是当我删除一个元素然后不起作用时，“子列表”的大小会变小，有什么想法吗？

4

1 回答 1

0

这种递归方法不会很好地工作，因为正如您所发现的，当您从数组中删除项目时，您必须将所有内容向下移动。这将弄乱父递归调用列表中的偏移量。

您可以修改调用，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;
    }
}

我假设您的列表next在此示例中由 NULL 指针终止，但它也应该很容易适应长度有界的列表。我还假设它只是单链接的——双向链接列表的基本方法是相似的，但当然你需要更新下一个和上一个指针。

于 2013-01-18T13:29:21.323 回答