[PR]

整列済み配列から重複する要素を取り除く

戻る

 整列済み配列から重複する要素を取り除く関数を作る。

//*********************************************************
// unique
//    比較関数 comp によって整列された配列 array の
//    重複する要素を1つにまとめる。
//    配列 array に含まれる要素の種類の数を返す。
//    例:[aabccdeee] -> [abcde], 返値 5 
//*********************************************************
size_t
unique
	(
		void *array,
		size_t num,
		size_t size,
		int (*comp)(const void *, const void *)
	)
{
	// すべての要素を走査
	char *start = (char *)array;
	char *stop  = (char *)array + (size*(num-1)); // ちょうど最後の要素
	char *dst   = start;
	char *p     = start;
	while( p <= stop )
	{
		// 重複のない要素列 p 〜 q の末尾 q を決定する
		char *q = p;
		while( (q < stop) && (0!=comp(q,q+size)) )
			q = q + size;

		// dst に要素列 p 〜 q を複写
		size_t elements = ((q - p)/size) + 1;
		memmove( dst, p, size * elements );
		dst = dst + size * elements; // 次の複写開始位置へ

		// q と重複する要素を全てスキップ
		p = q + size;
		while( (p <= stop) && (0==comp(q,p)) )
			p = p + size;
	}
	return (dst-start) / size; // 要素数を返す
}//unique

使用例

//*********************************************************
// comp_char は、整列済み配列要素の順序関係を
//  a[0] <= a[1] <= a[2] <= …… <= a[n-2] <= a[n-1] 
// としたときの2つの要素 p, q の順序関係が
//   *p <  *q であれば負を
//   *p == *q であれば0を
//   *p >  *q であれば正を
//  を返す。
//*********************************************************
static int comp_char( const void *p, const void *q )
{
	const char *cp = (const char *)p;
	const char *cq = (const char *)q;

 	if ( *cp < *cq ) return -1;
	if ( *cp > *cq ) return  1;
	return 0;
}//comp_char
//*********************************************************
// 関数 unique() の使用例です。
//*********************************************************
int main( void )
{
#define print_array(title,array,num)  \
	{printf("%s:",title);for(size_t i=0;i<num;i++){printf("%d, ",array[i]);}puts("");}

	size_t n;
	char   array_orig[16];
	char   array_copy[numof(array_orig)];

	// 整列済み配列の作成
	srand( time(NULL) );
	for( int i = 0; i < numof(array_orig); i++ )
	{
		array_orig[i] = (char)(rand() % 16);
	}
	qsort( array_orig, numof(array_orig), sizeof(char), comp_char );
	memcpy( array_copy, array_orig, sizeof(array_orig) );

	// 重複要素の取り除き
	n = unique( array_orig, numof(array_orig), sizeof(char), comp_char );

	// 配列の表示
	print_array( "unique 前", array_copy, numof(array_orig) );
	print_array( "unique 後", array_orig, n );
	return 0;

#undef print_array // #define print_array(title,array,num)
}//main

実行結果

unique 前:0, 0, 0, 1, 1, 3, 3, 3, 4, 8, 10, 11, 11, 14, 15, 15, 
unique 後:0, 1, 3, 4, 8, 10, 11, 14, 15, 

関連

配列の要素を逆順に並べ替える
配列の要素を回転移動する
配列が整列されているかどうか調べる
配列から要素を検索する
配列をランダムに並べ替える



Google
ご意見・ご感想をお聞かせ下さい。匿名で送信できます。

 * 返信が必要な場合には postmaster@katsura-kotonoha.sakura.ne.jp へ直接メールしてください。

水無瀬 優 postmaster@katsura-kotonoha.sakura.ne.jp
IDGは全世界85カ国でIT関連雑誌を発行する出版社です。