本人碰见一道C语言难题，寻大神帮助，利用C语言实现：求任意两个集合的交集、并集、差集，
2个回答
展开全部
以前写过一个纯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 );
}
本回答由提问者推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
