RSS
以下は目次です。
配列の要素の中に、同じ値をもった要素がないことを確認したいとします。
要素の型は、同じ値かどうかを「==」で調べられるものであれば、何でも構いません。
array_is_unique という関数にすることを考えます。引数には、配列（を指すポインタ）と、その配列の要素数を渡し、戻り値は、重複がなければ true、重複があれば false を返すようにします。
#include <stdio.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
int main(void)
{
int array1[] = {7, 2, 6, 1, 4, 9, 8};
int array2[] = {7, 2, 6, 7, 4, 9, 8};
printf("%d\n", array_is_unique(array1, SIZE_OF_ARRAY(array1)));
printf("%d\n", array_is_unique(array2, SIZE_OF_ARRAY(array2)));
}望む結果は、次のとおりです。
1
0SIZE_OF_ARRAYマクロは、配列の要素数を取得するものです。詳細は「逆引き 配列の要素数を求める」を参照してください。
二重のループをつくって、すべての要素を総当たりで調べて、重複を探します。
この方法はいつでも使えます。
#include <stdbool.h>
#include <stdio.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
/*
配列内に値の重複がないかどうかを返す
引数
array: 対象の配列
size: array の要素数
戻り値
重複がなければ true、重複があれば false
*/
bool array_is_unique(const int* array, size_t size)
{
for (size_t i = 0; i < size - 1; ++i) {
for (size_t j = i + 1; j < size; ++j) {
if (array[i] == array[j]) {
return false;
}
}
}
return true;
}
int main(void)
{
int array1[] = {7, 2, 6, 1, 4, 9, 8};
int array2[] = {7, 2, 6, 7, 4, 9, 8};
printf("%d\n", array_is_unique(array1, SIZE_OF_ARRAY(array1)));
printf("%d\n", array_is_unique(array2, SIZE_OF_ARRAY(array2)));
}実行結果：
1
0array[i] と array[j] の比較を繰り返し、１度でも同じ値になることがあったら、重複があると判断できます。
変数 i は外側の for文で制御しており、変数 j は内側の for文で制御していますから、j のほうが次々と値が変化します。
注意すべき点は２つです。
１つは、変数 j の初期値を i + 1 で始めることです。i == j となる瞬間ができないようにしなければなりません。i == j のときに、array[i] と array[j] を比較したら、当然同じ値なので、誤って重複していると判定してしまいます。
もう１つは、j は末尾の要素の位置（array[size-1]）まで進むのに対して、i はその１つ手前までしか進まないことです。j の初期値は i + 1 なので、i を size - 1 まで進めてしまうと、array[size] の位置を参照してしまいます（範囲外アクセス）。
配列がソートされているのなら、その状態を利用して効率を上げられます。
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
int compare_int(const void* a, const void* b)
{
int a_num = *(int*)a;
int b_num = *(int*)b;
return a_num - b_num;
}
/*
配列内に値の重複がないかどうかを返す
※ソート済みでなければならない
引数
array: 対象の配列
size: array の要素数
戻り値
重複がなければ true、重複があれば false
*/
bool array_is_unique(const int* array, size_t size)
{
for (size_t i = 0; i < size - 1; ++i) {
if (array[i] == array[i + 1]) {
return false;
}
}
return true;
}
int main(void)
{
int array1[] = {7, 2, 6, 1, 4, 9, 8};
int array2[] = {7, 2, 6, 7, 4, 9, 8};
// 配列を昇順にソートする
qsort(array1, SIZE_OF_ARRAY(array1), sizeof(int), compare_int);
qsort(array2, SIZE_OF_ARRAY(array2), sizeof(int), compare_int);
printf("%d\n", array_is_unique(array1, SIZE_OF_ARRAY(array1)));
printf("%d\n", array_is_unique(array2, SIZE_OF_ARRAY(array2)));
}実行結果：
1
0ソートされているのなら、もし値が重複する要素があれば、必ず隣り合ったところにあるはずです。よって、先頭から順番に走査しつつ、１つ後ろの要素との一致だけを確認すればいいことになります。
ここでは配列を、qsort関数を使ってソートしていますが、ソートの処理が加わったことで結局、遅くなる可能性に注意してください（配列をソートする方法については、「逆引き 配列をソートする」を参照）。
{
の直後と、} の直前に空白を入れない）(
の直後、) の直前に空白を入れない）return 0;
を削除（Ｃ言語編全体でのコードの統一）新規作成。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |