实现两个整数集合的并集、交集和差集运算------起泡运算
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");
}
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询