簡単な和集合の実装

今回はCで簡単に和集合を実装する方法を書いていきます。簡単になので処理速度などについては一旦おいておきます。

考え方

何らかの集合A,Bがあるとします(面倒なのでプログラム中で定義します)。和集合の格納先はU(Union)とし,適当なサイズの配列として定義します。
まずAの要素をAに全て格納します。この時点でUのサイズはAのサイズと同一になります。次にBの要素のうち,Uの要素でないものを格納していきます。

実装

char *a[]={"aの要素1","aの要素2"},char *b[]={"bの要素1","bの要素2"},u[100];
int size_a=sizeof(a)/sizeof(char*),size_b=sizeof(b)/sizeof(char*),size_u,flag=0;
for(int i=0;i<size_a;i++){
  u[i]=a[i];
}
size_u=size_a;
for(int i=0;i<size_b;i++){
  for(int j=0;j<size_u;j++){
    if(strcmp(b[i],u[j])==0){
      flag=1;
      break;
    }
  }
  if(flag==0){
    c[size_u]=b[i];
    size_u++;
  }else{
    flag=0;
  }
}

変数の説明

• a,b,u : 集合の要素を格納する配列
• size_a,size_b,size_u : 配列のサイズ
• flag : bの要素がuの要素と一致した場合に1になる

最後に

以上で部分集合を作成する処理自体は実装できます。
今回は出現回数をカウントする必要等がないので一致した時点でbreakしてますが,回数を数えたい場合はcounterなどを用意してインクリメントするのが楽です。