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

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

//*********************************************************
// unique
//    比較関数 comp によって整列された配列 array の
//    重複する要素を１つにまとめる。
//    配列 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] 
// としたときの２つの要素 p, q の順序関係が
//   *p <  *q であれば負を
//   *p == *q であれば０を
//   *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, 

関連

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