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

この例では、リストが NULLnextポインターで終了していると想定していますが、長さ制限のあるリストにも簡単に適応できるはずです。また、単一リンクのみであると仮定しました.二重リンクリストの基本的なアプローチは似ていますが、もちろん、次のポインターと前のポインターの両方を更新する必要があります。

于 2013-01-18T13:29:21.323 に答える