本人碰见一道C语言难题,利用C语言实现：求任意两个集合的交集、并集、差集,

本人碰见一道C语言难题,利用C语言实现：求任意两个集合的交集、并集、差集,

以前写过一个纯C的, 用的是数组,模拟C++ STL里面的set_intersection,set_union和set_difference的实现. 稍作了修改,添加了些注释,希望能帮到你.注意：必须先对输入集合排序；输出结果和C++ STL的测试结果吻合.#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int set_intersection (const int Set1[], const unsigned int SizeofSet1,
                      const int Set2[], const unsigned int SizeofSet2,
                      int Res[], unsigned int* pSizeofRes);
int set_union (const int Set1[], const unsigned int SizeofSet1,
                      const int Set2[], const unsigned int SizeofSet2,
                      int Res[], unsigned int* pSizeofRes);                     
int set_difference (const int Set1[], const unsigned int SizeofSet1,
                      const int Set2[], const unsigned int SizeofSet2,
                      int Res[], unsigned int* pSizeofRes);                     
int compare (const void * a, const void * b);
void print_array(const int arr[], const size_t len);
int main(int argc, char** argv)
{
    int first[] = {5,10,15,20,25};
    int second[] = {50,40,30,20,10};
    unsigned int size1, size2, size_intxn, size_union, size_diff, retcode;
    int *pr_intxn, *pr_union, *pr_diff;
    /* Pre-requirement, set MUST be sorted. */
    size1 = sizeof(first) / sizeof(first[0]);
    size2 = sizeof(second) / sizeof(second[0]);
    qsort(first, size1, sizeof(int), compare);
    qsort(second, size2, sizeof(int), compare);
           
    /* Intersection */
    size_intxn = (size1 > size2) ? size1 : size2; /* estimate size of result */
       
    pr_intxn = (int *)malloc(sizeof(int) * size_intxn); /* pre-allocate result */
    if (NULL == pr_intxn) {
        printf("Intersection memory error.\n");
        return -1;
    }
           
    printf("1) Set of Intersection:\n");   
    retcode = set_intersection(first, size1, second, size2, pr_intxn, &size_intxn);
    if (retcode == 0)
        print_array(pr_intxn, size_intxn);
    else
       printf("Error in set_intersection, code %d\n", retcode);
          
    free(pr_intxn);
       
    /* Union */
    size_union = size1 + size2; /* estimate size of result */
       
    pr_union = (int *)malloc(sizeof(int) * size_union); /* pre-allocate result */
    if (NULL == pr_union) {
        printf("Union memory error.\n");
        return -1;
    }
           
    printf("2) Set of Union:\n");   
    retcode = set_union(first, size1, second, size2, pr_union, &size_union);
    if (retcode == 0)
       print_array(pr_union, size_union);
    else
       printf("Error in set_union, code %d\n", retcode);
    free(pr_union);
       
    /* Difference */
    size_diff = size1 + size2; /* estimate size of result */
       
    pr_diff = (int *)malloc(sizeof(int) * size_diff); /* pre-allocate result */
    if (NULL == pr_diff) {
        printf("Difference memory error.\n");
        return -1;
    }
           
    printf("3) Set of Difference:\n");   
    retcode = set_difference(first, size1, second, size2, pr_diff, &size_diff);
    if (retcode == 0)
       print_array(pr_diff, size_diff);
    else
       printf("Error in set_difference, code %d\n", retcode);
           
    free(pr_diff);
       
       
    return 0;
}
/*
  Input:
    Set1 - First set.
    Set2 - Second set.
    SizeofSet1 - Set length of First set.
    SizeofSet2 - Set length of Second set.
  Input/Output: 
    Res - Set for storing results.
    pSizeofRes - Point to SizeofRes, length of result. If SizeofRes is less than
                 expected, a proper size will be returned to caller.
  Return:
    0 - If successfully.              
    1 - SizeofRes is smaller than expected.
    -1 - Internal memory error.
*/
int set_difference (const int Set1[], const unsigned int SizeofSet1,
                      const int Set2[], const unsigned int SizeofSet2,
                      int Res[], unsigned int* pSizeofRes)
{
    int i, j, k;
    unsigned int size_pre;   
    int *pr = 0;
       
    size_pre = SizeofSet1 + SizeofSet2;
    if ( *pSizeofRes < size_pre)
    {
        *pSizeofRes = size_pre;
        return 1;
    }
       
    pr = (int *)malloc(size_pre * sizeof(int));
    if ( pr == NULL )
       return -1;
          
    i = 0; j = 0; k = 0;
    while ( i < SizeofSet1 && j < SizeofSet2 )
    {
        if (Set1[i] < Set2[j]) pr[k++] = Set1[i++];       
        else if (Set2[j] < Set1[i]) ++j;
        else
        { i++; j++;}
    }
    memcpy(pr+k, Set1+i-1, sizeof(int)*(SizeofSet1-i+1));
    k += SizeofSet1-i;
               
    memcpy(Res, pr, k*sizeof(int));
    *pSizeofRes = k;       
    free(pr);
       
    return 0;       
}                     
int set_union (const int Set1[], const unsigned int SizeofSet1,
                      const int Set2[], const unsigned int SizeofSet2,
                      int Res[], unsigned int* pSizeofRes)
{
    int i, j, k;
    unsigned int size_pre;   
    int *pr = 0;
       
    size_pre = SizeofSet1 + SizeofSet2;
    if ( *pSizeofRes < size_pre)
    {
        *pSizeofRes = size_pre;
        return 1;
    }
       
    pr = (int *)malloc(size_pre * sizeof(int));
    if ( pr == NULL )
       return -1;
          
    i = 0; j = 0; k = 0;
    while ( 1 )
    {
        if (i > SizeofSet1 - 1)
        {
            memcpy(pr+k, Set2+j-1, sizeof(int)*(SizeofSet2-j+1));
            k += SizeofSet2 - j;
            break;
        }
           
        if (j > SizeofSet2 - 1)
        {
            memcpy(pr+k, Set1+i-1, sizeof(int)*(SizeofSet1-i+1));
            k += SizeofSet1 - i;
            break;
        }
        if (Set1[i] < Set2[j]) pr[k] = Set1[i++];       
        else if (Set2[j] < Set1[i]) pr[k] = Set2[j++];       
        else { pr[k] = Set1[i]; ++i; ++j; }
        ++k;
    }
    memcpy(Res, pr, k*sizeof(int));
    *pSizeofRes = k;       
    free(pr);
       
    return 0;       
}                     
                         
int set_intersection (const int Set1[], const unsigned int SizeofSet1,
                      const int Set2[], const unsigned int SizeofSet2,
                      int Res[], unsigned int* pSizeofRes)
{
    int i, j, k;
    unsigned int size_pre;   
    int *pr = 0;
       
    size_pre = (SizeofSet1 > SizeofSet2) ? SizeofSet1 : SizeofSet2;
    if ( *pSizeofRes < size_pre)
    {
        *pSizeofRes = size_pre;
        return 1;
    }
       
    pr = (int *)malloc(size_pre * sizeof(int));
    if ( pr == NULL )
       return -1;
          
    i = 0; j = 0; k = 0;
    while ( i < SizeofSet1 && j < SizeofSet2 )
    {
        if (Set1[i] < Set2[j]) ++i;
        else if (Set2[j] < Set1[i]) ++j;
        else
        {
            pr[k++] = Set1[i];
            i++; j++;
        }
    }
    memcpy(Res, pr, k*sizeof(int));
    *pSizeofRes = k;       
    free(pr);
       
    return 0;   
}
void print_array(const int arr[], const size_t len)
{
    int i;
       
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
           
    printf("\n");           
}
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}