RSS
以下は目次です。
配列の中に、同じ値をもった要素があった場合に、１つだけ残して、ほかを取り除いてしまいたいとします。
たとえば、{7, 2, 6, 7, 4, 9, 8} という要素をもった配列には、7 が重複しています。この場合、7 を１つだけ残して、{7, 2, 6, 4, 9, 8} という配列に変更したいということです。
しかし、Ｃ言語では、配列の要素数は固定されているため、対象の配列の要素数を直接減らすことはできません。そこで、以下のような方法を使います。
(a) の方法の場合は、次のような仕様の関数にすることを考えます。
/*
配列から重複を取り除く
引数
array: 対象の配列
size: array の要素数
戻り値
重複を取り除いたあとの要素数
*/
size_t array_unuque(int* array, size_t size);重複する要素を取り除いたあと、正しい要素数を戻り値で返すようにします。「現在の要素数は本当はこの数なのだ」と、呼び出し元が細心の注意を払いながらプログラムを書くことになります。危なっかしいのですが、Ｃ言語ではやむを得ないところです。
引数 array は 関数内で直接変更されます。それが問題ならば、呼び出し元でコピーを作るか、(b) の方法を使うことになります。
一方、(b) の方法の場合は、次のような仕様の関数になります。
/*
配列から重複を取り除く
引数
array: 対象の配列
size: array の要素数
result_size: 重複を取り除いた後の要素数を受け取るポインタ
戻り値
重複を取り除いた配列へのポインタ。失敗したらヌルポインタ。
malloc関数によって動的にメモリ割り当てされているので、
不要になったら free関数で解放すること。
*/
int* array_unuque(const int* array, size_t size, size_t* result_size);動的メモリ割り当てを使うので、最終的に解放しなければなりません。その責任は呼び出し元にあります。また、結果的に要素数がどれだけになったのかを知る手段が必要ですから、引数 result_size にポインタを渡して、要素数を格納してもらうようにします。
この方法はとにかく遅いことが欠点です。
ところで、重複さえ取り除ければ、要素の並び順はどうでもいいのか？ という部分も検討されるべきでしょう。極端ですが、先ほどの例の結果が {2, 6, 7, 4, 8, 9} のようにシャッフルされたような状態になってしまうのは、不自然ではあります。
(a) の方法では、並び順を保つように実装することはできますが、効率が落ちます。並び順を気にしなければ効率を上げられます。
(b) の方法では、並び順を保つことは容易です。
また、配列がソートされているかどうか（あるいはソートしてもよいか）によっても、効率に違いが生まれます。逆引き「配列に値の重複がないことを調べる」で取り上げていますが、配列内の値の重複を調べるとき、ソートされていれば効率を上げられるためです。
このページの最初で取り上げた、(a) の方法です。ただし、あらかじめソートされていることを前提にします。ソートできない場合は、方法② を使ってください。
#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 の要素数
戻り値
重複を取り除いたあとの要素数
*/
size_t array_unuque(int* array, size_t size)
{
size_t end = 0; // 現在の末尾要素の位置
// array[0] は必ずそのまま使うので、0 で開始
for (size_t i = 1; i < size; ++i) {
if (array[i] != array[end]) {
// 重複していない
++end;
array[end] = array[i];
}
}
return end + 1; // end は末尾要素の添字なので、要素数は +1 したもの
}
void print_array(const int* array, size_t size)
{
for (size_t i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main(void)
{
int array1[] = {7, 2, 6, 7, 4, 9, 8};
int array2[] = {7, 2, 6, 7, 7};
int array3[] = {7, 7, 7};
// 配列を昇順にソートする
qsort(array1, SIZE_OF_ARRAY(array1), sizeof(int), compare_int);
qsort(array2, SIZE_OF_ARRAY(array2), sizeof(int), compare_int);
qsort(array3, SIZE_OF_ARRAY(array3), sizeof(int), compare_int);
size_t size1 = array_unuque(array1, SIZE_OF_ARRAY(array1));
size_t size2 = array_unuque(array2, SIZE_OF_ARRAY(array2));
size_t size3 = array_unuque(array3, SIZE_OF_ARRAY(array3));
print_array(array1, size1);
print_array(array2, size2);
print_array(array3, size3);
}実行結果：
2 4 6 7 8 9
2 6 7
7逆引き「配列に値の重複がないことを調べる」で取り上げているとおり、配列がソートされているのなら、値の重複は１つ後ろの要素との一致だけを確認するだけで済みます。
この array_unuque関数の実装では、配列の先頭近くから順番に確定させていきます。
変数 end に、現時点までで確定している部分の末尾の位置を記憶させています。array[0] 単体で重複することはないので、array[0] は最初から確定しています。
for文のところでは、変数 i を 1 からカウントしています。そして、array[i] と array[end] とで一致を調べます。
一致しなければ重複していないので、array[i] の要素は取り除きませんから、この要素は確定です。end を 1つ進めてから array[end] の位置にコピーします。
値が一致した場合は重複していますから、array[i] は取り除きます。確定済みの範囲へコピーすることなく、i を進めてしまえばいいだけです。
最後に、end + 1 したものを return して終了です。
array_unuque関数の呼び出し元では、戻り値を必ず受け取り、以降はそれを本当の要素数として取り扱います。
なお、ここでは配列を、qsort関数を使ってソートしていますが、ソートの処理が加わったことで結局、遅くなる可能性に注意してください（配列をソートする方法については、「逆引き 配列をソートする」を参照）。
このページの最初で取り上げた、(a) の方法です。
配列はソートされていないし、ソートできないものとします。また、ソートできない事情があるのなら、おそらく要素の並び順を変えることも許されないでしょう。並び順を変えないように実装します。
#include <stdio.h>
#include <string.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
/*
配列から重複を取り除く
引数
array: 対象の配列
size: array の要素数
戻り値
重複を取り除いたあとの要素数
*/
size_t array_unuque(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]) {
// 重複している
// array[j] を上書きするように、
// array[j + 1]～array[size - 1] の範囲からコピーする。
memmove(&array[j], &array[j + 1], sizeof(int) * (size - j - 1));
// 実質の要素数を減らす
--size;
// 重複が３個以上連続している可能性があるので、
// j の位置をもう１度確認するため、j をデクリメント
--j;
}
}
}
return size;
}
void print_array(const int* array, size_t size)
{
for (size_t i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main(void)
{
int array1[] = {7, 2, 6, 7, 4, 9, 8};
int array2[] = {7, 2, 6, 7, 7};
int array3[] = {7, 7, 7};
size_t size1 = array_unuque(array1, SIZE_OF_ARRAY(array1));
size_t size2 = array_unuque(array2, SIZE_OF_ARRAY(array2));
size_t size3 = array_unuque(array3, SIZE_OF_ARRAY(array3));
print_array(array1, size1);
print_array(array2, size2);
print_array(array3, size3);
}実行結果：
7 2 6 4 9 8
7 2 6
7逆引き「配列に値の重複がないことを調べる」で取り上げているとおり、配列がソートされていないのなら、総当たりで一致を調べる必要があります。
二重ループの内側の if (array[i] == array[j]) で値の重複を確認しています。重複した場合は、配列内の位置が後ろ側にあたる array[j] を上書きするように、array[j+1] 以降の要素をコピーしてきます。コピー元範囲とコピー先範囲が重なり合うので、memmove関数を使います。
そして、変数 size と変数 j をデクリメントしています。ループの途中で、ループ制御変数や、ループの条件に使う変数を書き換えることは危険な場合もありますが、どちらも 1 以上であることが保証されているので、ここでは安全です。
このページの最初で取り上げた、(b) の方法です。
動的メモリ割り当てを使えば、メモリ使用量を、重複をなくした後の要素数に合わせて縮小できます。また、必然的に、結果が元の配列とは別のところに作られます。
この方法には欠点があります。
2 に絡んで、結果の配列をポインタとして扱わなければならない点も、多少不便を強いることになるかもしれません。
重複があったときのメモリ使用量の削減効果は、よほど重複が多くなければ大したことはありません。また、メモリ使用量の観点でいえば、元の配列がそのまま残っている点にも注意が必要です。そのため、これはあまり利点にならないかもしれません。
次のサンプルプログラムでは、#if ～ #endif でコードを切り分けられる箇所があり、重複があったときにメモリ使用慮を減らすか減らさないかを選択できるようにしています。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
/*
配列から重複を取り除く
引数
array: 対象の配列
size: array の要素数
戻り値
重複を取り除いたあとの要素数
*/
size_t array_unuque_inner(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]) {
// 重複している
// array[j] を上書きするように、
// array[j + 1]～array[size - 1] の範囲からコピーする。
memmove(&array[j], &array[j + 1], sizeof(int) * (size - j - 1));
// 実質の要素数を減らす
--size;
// 重複が３個以上連続している可能性があるので、
// j の位置をもう１度確認するため、j をデクリメント
--j;
}
}
}
return size;
}
/*
配列から重複を取り除く
引数
array: 対象の配列
size: array の要素数
result_size: 重複を取り除いた後の要素数を受け取るポインタ
戻り値
重複を取り除いた配列へのポインタ。失敗したらヌルポインタ。
malloc関数によって動的にメモリ割り当てされているので、
不要になったら free関数で解放すること。
*/
int* array_unuque(const int* array, size_t size, size_t* result_size)
{
assert(array != NULL);
assert(result_size != NULL);
// いったん、元の配列と同じ要素数で確保し、コピーをつくる
int* array_copy = malloc(sizeof(int) * size);
memcpy(array_copy, array, sizeof(int) * size);
// 重複を取り除く
*result_size = array_unuque_inner(array_copy, size);
#if 1
// そのまま返す
return array_copy;
#else
// 新しい大きさで割り当て直して返す
int* result = realloc(array_copy, sizeof(int) * (*result_size));
if (result == NULL) {
free(array_copy);
return NULL;
}
return result;
#endif
}
void print_array(const int* array, size_t size)
{
for (size_t i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main(void)
{
int array1[] = {7, 2, 6, 7, 4, 9, 8};
int array2[] = {7, 2, 6, 7, 7};
int array3[] = {7, 7, 7};
int* result1;
int* result2;
int* result3;
size_t result_size1, result_size2, result_size3;
result1 = array_unuque(array1, SIZE_OF_ARRAY(array1), &result_size1);
result2 = array_unuque(array2, SIZE_OF_ARRAY(array2), &result_size2);
result3 = array_unuque(array3, SIZE_OF_ARRAY(array3), &result_size3);
if (result1 != NULL) {
print_array(result1, result_size1);
}
if (result2 != NULL) {
print_array(result2, result_size2);
}
if (result3 != NULL) {
print_array(result3, result_size3);
}
free(result3);
free(result2);
free(result1);
}実行結果：
7 2 6 4 9 8
7 2 6
7array_unuque関数内で、まず malloc関数を使って、元の配列と同じ要素数をもった配列をつくり、中身もコピーします。この部分の処理はとても遅い可能性があります。
そして、方法①、方法② の関数のいずれかを使って、コピーの方の配列から重複を取り除きます。方法① の関数はソートしなければ使えませんから、ここでは 方法② の array_unuque関数を、array_unuque_inner という名前に変えて使っています。
このあと単に、重複が取り除かれた配列を返すだけで済ませるか、きちんと要素数を減らすかを選択できます（#if のところで切り替える）。
要素数を変えずにそのまま返したほうが効率はいいですが、重複が多いと、メモリ使用量の面では無駄が大きくなります。
きちんとメモリの使用量を減らしたいなら、realloc関数を使って、再割り当てを行います。ここまですると、処理はさらに遅くなります。
realloc関数の失敗に備えるコードの書き方には注意が必要です。あまり詳しくない場合は、第３５章を参照してください。
{ の直後と、} の直前に空白を入れない）return 0; を削除（Ｃ言語編全体でのコードの統一）
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |