C言語,配列の要素削除問題

Question

【問題文】下記の関数 make array(n) を用い,作成した配列を標準出力に出力する.つぎに,下記の関数 unique() に
より,同じ値がある場合は 2 回目以降に出現する同じ値を詰めて更新を行い,更新した配列を標準出力に
出力する.
int *make array(int n) n 個の整数からなる一次元配列を作成し,その配列の先頭アドレスを返値とす
る関数を作成せよ.なお,各配列の要素の値は 0 から 9 の整数値をランダム関数によりランダムに設
定すること.
int unique(int *array, int num)
• 配列 array で格納している整数を調べ,相異なるデータのみを有効とし配列中に先頭から前づめに
して残す、後ろの要素は無効とする.関数の返り値は有効データの入った要素数とする.つまり,
同じ整数を格納している場合は,2 回目以降に出現する同じ整数を無効データとし,配列 array
の格納する整数がすべて異なるように更新する.
• array が NULL の場合は 0 を返り値とすること.
void print array(int *array, int num) 配列 array で格納している整数を添え字の小さい順に標準出力
へ出力する関数を作成せよ.なお,void print array(int *array, int num) では,array が NULL の場
合は ”NULL ”を出力すること.

といった問題を解こうとしています。C言語です。コンパイルは通るのですが全く思い通りに動きません。どこが間違っているでしょうか。（make_array, print_arrayはあっていると思います。）そもそももっと簡単に書ける方法があればぜひ教えていただきたいです。

以下の通りにソースコードを書きました。（Main文まではテンプレートです。）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20

int *make_array(int n);
int unique(int *array, int n);
void print_array(int *array, int num);

int main(void)
{
int *array, num;
int *make_array(int n);
int unique(int *array, int n);
void print_array(int *array, int num);
srandom(time(NULL));
array = make_array(N);
print_array(array, N);
num = unique(array,N);
print_array(array, num);
return 0;
}
【以下、自分が作成】
int *make_array(int n){
int i, *array;

array = (int *)malloc(sizeof(int) * n);
for(i = 0 ; i < n ; i++){
*(array+i) = random() % 10;
}
return array;
}

int unique(int *array, int n){
int i, V;
int sakuzyo(int *ar, int in);

for(i = 0 ; *(array + i) != '\0' ; i++){
V += sakuzyo(array, *(array + i));
}

return V;
}

void print_array(int *array, int num){
int i;
if(array == NULL)printf("NULL\n");
else{
for(i = 0 ; i < num ; i++){
printf("%d ", *(array+i));
}
printf("\n");
}
}

int sakuzyo(int *ar, int in){
int b, c = 0, i = 0, bc = 0, vvv = 0;
b = (int )malloc(sizeof(int));
while((ar + i) != '\0'){
if((ar + i) != in){
*(b + bc) = *(ar + i);
bc++;
}else{
c++;
if(c == 1){
*(b + bc) = *(ar + i);
bc++;
}else{
vvv++;
}
}
i++;
}
ar = b;
return vvv;
}

Comments

[y_waiwai]

思い通りに動かないとはどういうふうに動くんでしょうか。
また、
このままではコードが読みづらいので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

[episteme]

関数 srandom, random が見当たりません。

Answer 1

そもそももっと簡単に書ける方法があればぜひ教えていただきたいです。

int unique(int *array, int n) {
  if ( array == NULL ) return 0;
  int* dst = array; // 重複を取り除いた列 : [array, dst) 最初は空
  // [array, array+n) 内の各値 *src に対し: 
  for( int* src = array; src != array+n; ++src ) {
    int* p;
    // [array, dst) つまり重複を取り除いた列の中から *src を探し 
    for ( p = array; p != dst && *p != *src; ++p ) { }
    // 見つからなかったら(重複しないんだから)末尾に追加する
    if ( p == dst ) *dst++ = *src;
  }
  return dst - array; // [array, dst) の要素数を返す
}

※ begin から始まり end に満たない(begin以上/end未満)範囲を [begin,end) と表記しています。

Answer 2

１つの作例として。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int *make_array( int );
int unique( int *, int );
void print_array( int *, int );

int main( void ) {
    int * arr;
    int n = 30; /* 適当値 */
    int num;

    srand( time( NULL ) );
    arr = make_array( n );
    print_array( arr, n );
    num = unique( arr, n );
    print_array( arr, num );
    return 0;
}

int *make_array( int n ) {
    int i;
    int * arr = NULL;

    if ( n > 0 ) {
        arr = ( int * )malloc( sizeof( int ) * n );
        for ( i = 0 ; i < n ; i ++ ){
            arr[ i ] = rand() % 10;
        }
    }
    return arr;
}

int unique( int * arr, int n ) {
    int i, j;

    if ( arr == NULL ) {
        n = 0; /* 題意により */
    }
    if ( n > 0 ) {
        for ( i = 0; i < n - 1; i ++ ) {
            for ( j = i + 1; j < n; ) {
                if ( arr[ i ] == arr[ j ] ) {
                    arr[ j ] = arr[ n - 1 ];
                    n --;
                }
                else {
                    j ++;
                }
            }
        }
        realloc( arr, sizeof( int ) * n ); /* 題意により */
    }
    return n;
}

void print_array( int * arr, int n ) {
    int i;

    if ( arr != NULL && n > 0 ) {
        printf( "arr[]={ " );

        for ( i = 0; i < n; i ++ ) {
            printf( "%d", arr[ i ] );
            if ( i < n - 1 ) {
                printf( ", " );
            }
        }
        puts( " }" );
    }
}

２重ループで着目している２つの要素が同値だったら、２つ目の要素を最後尾の要素で上書きして、配列のサイズを１つ縮める、という動作を配列の要素全体について実行し、ユニークな配列を得ています。　考え方はシンプルなので分かりやすいと思います。

題意には「同じ値を詰めて」「相異なるデータのみを有効とし」と明示されてはいますが、要素の順番が安定である事は求められていないので、これで良かろうと考えました。
realloc() は「後ろの要素は無効とする.」という題意を満たすためだけに書きましたが、実用上は不要だと思います。

なお、本作例は for ループがコンパイラによって最適化されると正しく動作しないおそれが有ります。　そのような場合には volatile を使うか、while で書き直すか、となるでしょう。

Comments

[episteme]

> realloc() は「後ろの要素は無効とする.」という題意を満たすためだけに書きましたが、実用上は不要だと思います。

realloc によってサイズが小さくなる時、アドレスが変化しない保証はないんじゃなかったっけ。

さらに、関数 unique に与える配列(ポインタ)は「ヒープから確保したものでなければならない」って制約を課すことにもなるし。

であるなら、不要どころか「やってはいけない」んじゃないかと。

[kurai]

コメントありがとうございます。
確かにそうだったような(汗)。　ならば int *unique( int *, int ) として、realloc() の結果を返し、更に、もらった領域は unique() の中で free() も……とか考えると、やはり realloc() はスッキリしません。
「後ろの要素は無効とする.」という題意の意図がどうにも掴みかねます。　「番人」でも置いて、各関数はそこ以降処理しないようにせよ、という事なのかどうか……。

[episteme]

> 後ろの要素は無効とする.

僕は「(範囲外だから)どうなってようが構わない」を意図していると解釈するのが妥当と判断しましたが。

Answer 3

episteme さんのコードは、ポインタを使って配列の要素にアクセスしていますが、
添字を使うようにすると、次のようなコードになります。

int unique(int *array, int n)
{
	int i, j, k = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < k && array[j] != array[i]; j++) ;
		if (j == k) array[k++] = array[i];
	}
	return k;
}

Answer 4

while(*(ar + i) != '\0'){

データが\0で終了するとは限りません。多くの場合0=\0がデータに含まれているので想定よりも早く終了する事でしょう。

ar = b;

arはint*型の仮引数なので代入しても呼び出し元のarrayが書き換わったりはしません。

// int* array [in/out]  data
// int  n     [in]      length(data)
// return: 有効データの入った要素数
int unique(int *array, int n){
    int V = 0; // 有効データの入った要素数
    for(int i = 0; i < n; i++){
        int num = array[i];
        int j;
        // データが有効かを検証する
        for(j = 0; j < V; j++){
            if(num == array[j]) break; // 無効
        }
        if(j == V){ // データが有効な場合
            array[V++] = num;
        }
    }
    return V;
}

他に、10種類の数値しか入らないことを利用して出現順を計測しそれを元にarrayを書き換えるのも手ではあります。