c言語で2種類の配列で、数字がどちらにも入っているものと、どちらかに入っているもの(積集合、和集合)を表示したいです

Question

C言語で以下のプログラムを作りたいです。

大きさが10の整数型の配列を２つ作り、それぞれに１から10の乱数を代入して、共通する数とどちらかにある数をそれぞれ昇順に表示させる。

例えば
配列1：5 8 4 3 7 9 7 9 5 1
配列2：7 6 1 5 9 9 10 8 4 3
共通する数：1 3 4 5 7 8 9
どちらかにある数：1 3 4 5 6 7 8 9 10

自分はまず乱数を発生させて、それぞれの配列で複数回ある数を除き、それから&&や||を使って求めて、昇順に並べようと思いましたが、配列で複数回ある数を除く方法と昇順に並べる方法がわかりませんでした。
なので、その複数回ある数を除く事と昇順に並べる事の方法や考え方など教えてください。
ちなみに、配列で複数回ある数を除くとは
配列1：5 8 4 3 7 9 7 9 5 1では7が2回出てきているので1つにするという事です。

また、別の方法が良ければそれも教えて欲しいです。

Answer 1

ビット演算を学習しましょう。

#include <stdio.h>

#define N 10 // 配列の要素数
#define A 1  // 要素の値の範囲 A以上 B以下
#define B 10

void print(int b)
{
	for (int i = A; i <= B; i++)
        if (b >> i & 1) printf(" %d", i);
	putchar('\n');
}

int main(void)
{
	int a1[N] = { 5, 8, 4, 3, 7, 9, 7, 9, 5, 1 };
	int a2[N] = { 7, 6, 1, 5, 9, 9, 10, 8, 4, 3 };
	int b1 = 0, b2 = 0;
	for (int i = 0; i < N; i++) b1 |= 1 << a1[i], b2 |= 1 << a2[i];
	printf("共通する数:"), print(b1 & b2);
	printf("どちらかにある数:"), print(b1 | b2);
}

追記
ビット演算を使わないやり方です。

#include <stdio.h>

#define N 10 // 配列の要素数
#define A 1  // 要素の値の範囲 A以上 B以下
#define B 10

void print(int b[B+1])
{
    for (int i = A; i <= B; i++)
        if (b[i]) printf(" %d", i);
    putchar('\n');
}

int main(void)
{
    int a1[N] = { 5, 8, 4, 3, 7, 9, 7, 9, 5, 1 };
    int a2[N] = { 7, 6, 1, 5, 9, 9, 10, 8, 4, 3 };
    int b1[B+1] = { 0 }, b2[B+1] = { 0 }, c[B+1] = { 0 }, d[B+1] = { 0 };
    for (int i = 0; i < N; i++) b1[a1[i]] = b2[a2[i]] = 1;
	for (int i = A; i <= B; i++) {
		c[i] = b1[i] * b2[i];  // 積集合
		d[i] = b1[i] + b2[i];  // 和集合
	}
    printf("共通する数:"), print(c);
    printf("どちらかにある数:"), print(d);
}

ビット演算を使わなければ理解できるのでしょうか？
コメントをお願いします。

追記2
ソートした 2つの配列を先頭から見ていって、積集合と和集合を求めるやり方。

#include <stdio.h>

#define N 10 // 配列の要素数
#define A 1  // 要素の値の範囲 A以上 B以下
#define B 10

void print(int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf(" %d", a[i]);
    putchar('\n');
}

void sort(int a[])
{
	for (int i = 0; i < N-1; i++)
		for (int j = i+1; j < N; j++)
			if (a[i] > a[j]) {
				int t = a[i]; a[i] = a[j]; a[j] = t;
			}
}

int intersection(int a1[], int a2[], int b[])
{
	int i = 0, j = 0, k = 0, t = A-1;
	while (i < N && j < N)
		if (a1[i] < a2[j])
			i++;
		else if (a1[i] > a2[j])
			j++;
		else {
			if (a1[i] != t) b[k++] = t = a1[i];
			i++, j++;
		}
	return k;
}

int union_set(int a1[], int a2[], int b[])
{
	int i = 0, j = 0, k = 0, t = A-1;
	while (i < N && j < N)
		if (a1[i] < a2[j]) {
			if (a1[i] != t) b[k++] = t = a1[i];
			i++;
		}
		else {
			if (a2[j] != t) b[k++] = t = a2[j];
			j++;
		}
    for (; i < N; i++)
		if (a1[i] != t) b[k++] = t = a1[i];
    for (; j < N; j++)
		if (a2[j] != t) b[k++] = t = a2[j];
	return k;
}

int main(void)
{
    int a1[N] = { 5, 8, 4, 3, 7, 9, 7, 9, 5, 1 };
    int a2[N] = { 7, 6, 1, 5, 9, 9, 10, 8, 4, 3 };
	printf("配列1:"), print(a1, N);
	printf("配列2:"), print(a2, N);
	sort(a1);
	printf("配列1(昇順):"), print(a1, N);
	sort(a2);
	printf("配列2(昇順):"), print(a2, N);
    int b[B-A+1], n;
	n = intersection(a1, a2, b);
    printf("共通する数:"), print(b, n);
	n = union_set(a1, a2, b);
    printf("どちらかにある数:"), print(b, n);
}

実行結果

配列1: 5 8 4 3 7 9 7 9 5 1
配列2: 7 6 1 5 9 9 10 8 4 3
配列1(昇順): 1 3 4 5 5 7 7 8 9 9
配列2(昇順): 1 3 4 5 6 7 8 9 9 10
共通する数: 1 3 4 5 7 8 9
どちらかにある数: 1 3 4 5 6 7 8 9 10

Comments

[tsuyoku-naritai]

回答ありがとうございます。ビット演算を学習してから参考にしてもう一回作ってみます。

[tsuyoku-naritai]

返信遅れてすいません。#difineが何なのかはわかりませんでした。でも別のやり方で解決しました。ありがとうございました。

Answer 2

複数回あるのを除くには、ソートしてから新しい配列を用意して、元の配列の小さい方から順に、数値が大きくなったときだけ、新しい配列に数値を入れていけばいいです。
「2つの配列を1つにまとめる→ソート→重複を除く」で和集合はできます。
積集合は「2つの配列をそれぞれソート→小さい方から比べつつ共通の数値があったら新しい配列に入れる」というような動作になります。添字の進め方に工夫が必要なので考えてみてください。

また、1~10ということがわかっているなら、ビット演算を用いることでもっと楽にできます。
0に対して元の配列から1<<(数値)との論理和を取っていけば、たとえば{1,2,3,5,5,5,8,8,9,9}なら2進数で1100101110になるので、2つの配列をこのようにint型の数値に変換してからビット論理和、論理積をそれぞれとって配列にもどせば終わりです。

---

追記
回答修正が迷走してしまってすみません。
「重複を消す」の例はこんな感じですね

int main(void) {
  int ab[20] = {1,1,2,3,3,4,5,6,7,7,7,7,7,8,8,9,9,9,9,10}; // aとbを連結してソートした配列
  int or[10];
  or[0] = ab[0];
  for (int i=0,j=0;i<20;i++) {
    if (ab[i] > or[j]) or[++j] = ab[i];
  }
}

Comments

[tsuyoku-naritai]

回答ありがとうございます。
複数回あるのを除くところまでやってみたのですが、数値が大きくなった時だけ、新しい配列に入れるところがうまくいきません。
```C
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(void){
int a[10],a2[10],b[10],b2[10],i,j,x;
srand((unsigned)time(NULL));
printf("配列1：");
for(i = 0;i < 10;i++){
a[i] = rand() % 10 + 1;
printf("%d ",a[i]);
}
printf("\n配列2：");
for(i = 0;i < 10;i++){
b[i] = rand() % 10 + 1;
printf("%d ",b[i]);
}
for(i = 0;i < 10;i++){
for(j = i+1;j < 10;j++){
if(a[i]>a[j]){
x = a[i];
a[i] = a[j];
a[j] = x;
}
}
}
for(i = 0;i < 10;i++){
for(j = i+1;j < 10;j++){
if(b[i]>b[j]){
x = b[i];
b[i] = b[j];
b[j] = x;
}
}
}

printf("\n");
for(i = 0;i < 10;i++){
printf("%d ",a[i]);
}
printf("\n");
for(i = 0;i < 10;i++){
printf("%d ",b[i]);
}
printf("\n");
for(i = 0;i < 10;i++){
for(j = 0;j < 10;j++){
if(a[j]<a[j+1]){
a2[j] = a[i];
}
}
}
for(i = 0;i < 10;i++){
for(j = 0;j < 10;j++){
if(b[j]<b[j+1]){
b2[j] = b[i];
}
}
}
for(i = 0;i < 10;i++){
printf("%d ",a2[i]);
}
printf("\n");
for(i = 0;i < 10;i++){
printf("%d ",b2[i]);
}
printf("\n");

}
```
(途中のprintfは確認用です)
これが自分で考えてみたものなのですが、何かアドバイスいただけないでしょうか？

[tsuyoku-naritai]

うまくいきました。ありがとうございます。

Answer 3

それぞれに１から10の乱数を代入

ということで，値の種類が少ないので，
1~10 のそれぞれの値が，｛配列１にあるか？，配列２にあるか？｝を調べるのが手っ取り早いように思います．

//1～10の値が，｛配列１にあるか？，配列２にあるか？｝を調べた結果を入れる用．
//各 CheckFlag[x] はbitフラグの組み合わせとして，
//配列1にある場合は．0x01 を，配列2にある場合は0x02 をORする形で結果を作るとか，そんな感じで．
unsigned char CheckFlag[10] = { 0,0,0,0,0, 0,0,0,0,0 };

---

こんな感じで．

#define ARRAY1_SIZE 10
#define ARRAY2_SIZE 10

int main(void)
{
    //配列１と配列２
    const int Array1[ARRAY1_SIZE] = { 5, 8, 4, 3, 7, 9, 7, 9, 5, 1 };
    const int Array2[ARRAY2_SIZE] = { 7, 6, 1, 5, 9, 9, 10, 8, 4, 3 };

    //調べる処理
    unsigned char CheckFlag[10] = { 0,0,0,0,0, 0,0,0,0,0 };
    for( int i=0; i<ARRAY1_SIZE; ++i ){ CheckFlag[ Array1[i]-1 ] |= 0x01;   }
    for( int i=0; i<ARRAY2_SIZE; ++i ){ CheckFlag[ Array2[i]-1 ] |= 0x02;   }

    //結果表示
    printf( "共通 : " );
    for( int i=0; i<10; ++i )
    {
        if( CheckFlag[i]==0x03 ){   printf( "%d ", i+1 );   }
    }
    printf( "\n" );

    printf( "どっちかにある : " );
    for( int i=0; i<10; ++i )
    {
        if( CheckFlag[i] ){ printf( "%d ", i+1 );   }
    }
    printf( "\n" );

    return 0;
}

「bitがどうの」的な話が嫌なら，
配列１の調査結果と配列２の調査結果を別個に持てばいい．
調査結果データの表現方法が異なるだけで，やってることは一緒．

//調べる処理
unsigned char CheckResult1[10] = { 0,0,0,0,0, 0,0,0,0,0 };
unsigned char CheckResult2[10] = { 0,0,0,0,0, 0,0,0,0,0 };
for( int i=0; i<ARRAY1_SIZE; ++i ){ CheckResult1[ Array1[i]-1 ] = 1;    }
for( int i=0; i<ARRAY2_SIZE; ++i ){ CheckResult2[ Array2[i]-1 ] = 1;    }

//結果表示
printf( "共通 : " );
for( int i=0; i<10; ++i )
{
    if( CheckResult1[i] && CheckResult2[i] ){   printf( "%d ", i+1 );   }
}
printf( "\n" );

printf( "どっちかにある : " );
for( int i=0; i<10; ++i )
{
    if( CheckResult1[i] || CheckResult2[i] ){   printf( "%d ", i+1 );   }
}
printf( "\n" );

---

値の種類が少ないことを利用すれば，「重複を除去して昇順に」の話も同じ考えでやれる．

#define ARRAY_SIZE  10

int main(void)
{
    //元の配列
    const int SrcArray[ARRAY_SIZE] = { 5, 8, 4, 3, 7, 9, 7, 9, 5, 1 };
    //結果配列用
    int ResultArraySize = 0;
    int ResultArray[ARRAY_SIZE] = { 0,0,0,0,0, 0,0,0,0,0 };

    //1～10の各値が元の配列に存在するか調べる
    unsigned char CheckResult[10] = { 0,0,0,0,0, 0,0,0,0,0 };
    for( int i=0; i<ARRAY_SIZE; ++i ){  CheckResult[ SrcArray[i]-1 ] = 1;   }
    //調べた結果から，結果配列を作る
    for( int i=0; i<10; ++i )
    {
        if( CheckResult[i] ){   ResultArray[ ResultArraySize++ ] = i+1; }
    }

    //結果表示
    printf( "重複を取り除いてソートした結果(%d 個になった)\n", ResultArraySize );
    for( int i=0; i<ResultArraySize; ++i ){    printf( "%d ", ResultArray[i] );    }
    printf( "\n" );

    return 0;
}

Comments

[tsuyoku-naritai]

すいません、まだC言語をはじめて間もないので、bitフラグの組み合わせが何なのかわかりません。なので、できればbitフラグというものを使わない方法を知りたいです。

[fana]

コード例を追加した．
要は，1～10 の各値に関して，

・どちらの配列にも無い場合は 0
・配列1にだけある場合は 1
・配列2にだけある場合は 2
・どちらにもある場合は 1+2 = 3

という形で，調査結果情報を作る．それだけの話．

[fana]

「bitがどうの」という話が慣れないなら，
1～10 の各値が
・配列１にあるかどうか
・配列２にあるかどうか
という別個の調査結果を作ってやる形にすれば良いかと．

[tsuyoku-naritai]

回答ありがとうございます。自分はまだ知識不足で十分に理解できませんでした。何度も回答してくださったのに、すいません。