0

この形式の単一リンクリストでそれぞれ表される2つのセットの交差と差を取得しようとしています

struct node{
    unsigned n;
    struct node *next;
};

リスト内の要素の数を計算し、特定の要素がリストに含まれているかどうかを判断する前のタスクで、この関数を既に作成しました。

int cardinality(struct node *s){
    struct node *tmp = s;
    int count = 0;

    while(tmp != NULL){
    tmp = tmp->next;
    count++;
    }

    return count;
}

int contains(struct node *s, int v){ /* returns 0 if in list, 1 if not in list */
    struct node *tmp = s;
    int contains = 1;

    while(tmp->next != NULL){
    if(tmp->n == v){
        contains = 0;
        break;
        } else{
        if(tmp == NULL) break;
        tmp = tmp->next;
    }
    }
    return contains;
}

次の関数をコーディングする必要がありますが、その方法がわかりません。1 つのリストをループし、リスト内のすべての要素について 2 番目のリストをループして、2 番目のリストに含まれているかどうか (違い) を確認する必要がありますか? このタスクは複雑に思えますが、もっと簡単な方法があるはずです。あなたが私を助けてくれることを願っています

void intersection(struct node *s1, struct node *s2, struct node **result){

}

void difference(struct node *s1, struct node *s2, struct node **result){

}
4

2 に答える 2

0

次にこれらを実装します。

// Copy one node s, giving the copy a NULL next pointer.
struct node *copy_one(struct node *s);

// Add the given node s to an existing list.
void add(struct node *s, struct node **existing);

これらは多くの目的に役立ちますが、ここではそれらを構成します。

add(copy_one(s), &existing_list);

あなたの結果を構築します。

交差のアルゴリズムは次のようになります。

set result empty
for all elements e in s1
   if e->val is contained in s2
       add a copy of e to result

違いについてs1 - s2は、

set result empty
for all elements e in s1
   if e is _not_ contained in s2
       add a copy of e to result

私はあなたに C を解決させます。私があなたに完全な答えを与えるのは楽しいことではありません。

セットを表現するための連結リストの選択は、C と連結リストについて学習するのに適していますが、大きなセットのパフォーマンスが低下するため、多くの場合、最良の選択ではないことに注意してください。

于 2013-11-24T19:23:10.420 に答える
0

1 つのリストをループし、リスト内のすべての要素について 2 番目のリストをループして、2 番目のリストに含まれているかどうか (違い) を確認する必要がありますか?

セットをソートされていない連結リストとして表現する場合は、そうです。集合演算 (ソートされた配列など) を実装するために使用できる、より効率的なデータ構造とアルゴリズムがありますが、これが宿題である場合は、リンクされたリストで行き詰まっている可能性があります。

これはこのタスクには複雑すぎるように思えます。これを行うためのより簡単な方法があるはずです。

これは C です。この言語は組み込みのデータ構造やアルゴリズムをあまり提供しないため、多くの低レベルの詳細を自分で処理することに慣れる必要があります。しかし、いくつかのネストされたループは、実際には大したことではありません。

于 2013-11-24T19:28:29.530 に答える