求两个整数集合的公共元素

求两个整数集合的公共元素。

大致思路就是对一个集合求hash,然后遍历另一个集合,如果在hash中就打印...程序内面有很多无用的个人认为是技巧的技巧

 

 

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

#define N1 10
#define N2 5
#define MAX 15

typedef struct hash
{
  int num;
  struct hash* next;
}HASH;

int C[MAX];
HASH* H[10];

int swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
  
int get_rand(int start, int end)
{
  int rand_num = rand()%(end-start+1)+start;
  printf("rand_num is %d\n",rand_num);
  swap(C+start, C+rand_num);
  
  return C[start];
}

void init_array_a(int A[])
{
  int i = 0;
  for(i=0;i<N1;i++)
   A[i] = get_rand(i,MAX);
     
}

void init_array_b(int B[])
{
   int i;
   for(i=0;i<N2;i++)
    B[i] = get_rand(i,MAX);
 }
 
void init_hash()
{
  int i;
  for(i=0;i<10;i++)
   {
    H[i] = (HASH*)malloc(sizeof(HASH));
    H[i]->next = NULL;
   }
}

void add_hash(int num)
{
  int hash_num = num%10;
  HASH* p = (HASH*)malloc(sizeof(HASH));
  p->num = num;
  p->next = H[hash_num]->next;
  H[hash_num]->next = p;
}

int exist(int num)
{
 int hash_num = num%10;
 HASH* p = H[hash_num]->next;
 while(p!=NULL)
  {
   if(p->num == num)
     return 1;
   p = p->next;
  }
  return 0;
}

int main(int argc, char *argv[])
{
  int A[N1];
  int B[N2];
  int i;
    
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX;i++)
   C[i] = i+1;
   
 init_array_a(A);
 init_array_b(B);
 init_hash();
   
  printf("array A is:\n");
  for(i=0;i<N1;i++)
   {
    printf("%d ",A[i]);
    add_hash(A[i]);
   }
  printf("\narray B is:\n");
  for(i=0;i<N2;i++)
    printf("%d ",B[i]);
  
    
  printf("\n交集is:\n");
  for(i=0;i<N2;i++)
   {
     if(exist(B[i]))
         printf("%d ",B[i]);
   }
  system("PAUSE");    
  return 0;
}