miss_num_finder.c

#include <stdio.h>
#include <stdlib.h> // malloc
#include <string.h> // memset

#include <time.h> // shuffle

// dest : 被找出的数字存储的数组
// src : 被shuffle并取走数字的数组
// len : src数组的长度
// return : dest有效内容长度
int miss_num_finder(int * dest ,int * src , int len)
{
	int i;
	int j = 0;
	int * hs = (int *) malloc(sizeof(int) * 1000); // hash space
	memset(hs,0,sizeof(int) * 1000);
	memset(dest,0,sizeof(int) * (1000 - len));
	for(i = 0 ; i < len ; i ++)
	{
		hs[src[i] - 1] = 1;
	}
	for(i = 0 ; i < 1000 ; i ++ )
	{
		if(hs[i] == 0 )
		{
			dest[j] = i + 1;
			j ++ ;
		}
	}
	free(hs);
	return j;
}

#define decl_shuffle(type)\
	void shuffle_##type(type *list, size_t len) {		\
		int j;						\
		type tmp;					\
		while(len) {					\
			j = rand() % len;				\
			if (j != len - 1) {			\
				tmp = list[j];			\
				list[j] = list[len - 1];	\
				list[len - 1] = tmp;		\
			}					\
			len--;					\
		}						\
	}
 
/* declare and define int type shuffle function from macro */
decl_shuffle(int);


int main()
{
	int i ;
	int src[1000];
	int dest[1000];
	int rm_len;
	int rm_off;
	int rm_tmp;
	int find_size;
	srand((unsigned int) time(NULL));
	
	for(i = 0 ; i < 1000; i ++ )
	{
		src[i] = i + 1;
	}
	
	rm_len = rand() % 20 + 3; // number of to delete  in range [3,22]
	printf("try remove size : %d\n",rm_len);
	for(i = 0 ; i < rm_len ; i ++ )
	{
		rm_off = rand() % (1000 - i - 1);
		rm_tmp = src[rm_off];
		src[rm_off] = src[1000 - i - 1] ;
		printf("[remove] : %d \n" , rm_tmp );
	}
	
	shuffle_int(src,1000 - rm_len);
	
	find_size = miss_num_finder(dest,src,1000 - rm_len);
	
	printf ("found size : %d \n" , find_size);
	for(i = 0 ; i < find_size ; i ++)
	{
		printf("[found] : %d \n" , dest[i]);
	}
	
	return 0;
}

/*
//sample result 
yu:test_code yu$ gcc miss_num_finder.c -o  miss_num_finder
yu:test_code yu$ ./miss_num_finder
try remove size : 12
[remove] : 30
[remove] : 863
[remove] : 293
[remove] : 243
[remove] : 830
[remove] : 763
[remove] : 445
[remove] : 508
[remove] : 125
[remove] : 510
[remove] : 222
[remove] : 389
found size : 12
[found] : 30
[found] : 125
[found] : 222
[found] : 243
[found] : 293
[found] : 389
[found] : 445
[found] : 508
[found] : 510
[found] : 763
[found] : 830
[found] : 863
*/