实现两个整数集合的并集、交集和差集运算------起泡运算基本要求1．采用数组作为存储结构2．用起泡排序方法对结果进行排序

Question

实现两个整数集合的并集、交集和差集运算------起泡运算
基本要求
1．采用数组作为存储结构
2．用起泡排序方法对结果进行排序

Answer 1

所用的语言应该是纯C吧？ 如果是C++又是容器，又是算法库的，应该容易很多。 之前正好有模拟C++ STL的set_intersection，set_union和set_difference的C 函数， 再配合一个BubbleSort的程序，修改后演示如下：

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

void BubbleSort(int *data, const size_t num);
int set_intersection (const int Set1[], const size_t SizeofSet1, 
                      const int Set2[], const size_t SizeofSet2,
                      int Res[], size_t* pSizeofRes);
int set_union (const int Set1[], const size_t SizeofSet1, 
                      const int Set2[], const size_t SizeofSet2,
                      int Res[], size_t* pSizeofRes);                      
int set_difference (const int Set1[], const size_t SizeofSet1, 
                      const int Set2[], const size_t SizeofSet2,
                      int Res[], size_t* pSizeofRes);                      

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};
    size_t 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]);

    BubbleSort(first, size1);
    BubbleSort(second, size2);
    
    /* 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;
}

int set_difference (const int Set1[], const size_t SizeofSet1, 
                      const int Set2[], const size_t SizeofSet2,
                      int Res[], size_t* 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 size_t SizeofSet1, 
                      const int Set2[], const size_t SizeofSet2,
                      int Res[], size_t* 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 size_t SizeofSet1, 
                      const int Set2[], const size_t SizeofSet2,
                      int Res[], size_t* 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 BubbleSort(int *data, const size_t num)
{
    int i, j, _temp;
    i = num;
    
    while (i > 0)     
    {
        for (j = 0; j < i-1; j++)
        {
            if (data[j] > data[j+1])            
            {
                _temp = data[j];
                data[j] = data[j+1];
                data[j+1] = _temp;
            }
        }        
        i--;
    }
}

void print_array(const int arr[], const size_t len)
{
    int i;
    
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
        
    printf("\n");            
}