集合运算器-C
顺序表：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<set>
#include<iostream>
using namespace std;
#define MAX 1000
//冒泡排序
void Sort(int *A,int len) {
int i,j,t;
for(i = 0;i < len-1;i++) {
for(j = 0;j < len-i-1;j++) {
if(A[j] > A[j+1]) {
t = A[j+1];
A[j+1] = A[j];
A[j] = t;
}
}
}
}
/*
把B集合赋值给buffer，然后从A中找B中不一样的。
每找到一个,就接到buffer后面，再排序，得到顺序的并集
*/
void unionSet(int *A,int *B,int lenA,int lenB) {
int i,j;
int flag,index = lenB;
//开辟空间
int *buffer = (int *)malloc(sizeof(int) * (lenA+lenB));
//初始化buffer
for(i = 0;i< lenA+lenB;i++) {
buffer[i] = -1;
}
for(i = 0;i < lenB;i++) {
buffer[i] = B[i];
}
for(i = 0;i < lenA;i++) {
flag = 1;
for(j = 0;j < lenB;j++) {
if(A[i] == B[j]) {
flag = 0;
}
}
if(flag) {
buffer[index] = A[i];
index++;
}
}
Sort(buffer,lenA+lenB);
for(i = 0;i < lenA+lenB;i++) {
if(buffer[i] != -1)
printf("%d ",buffer[i]);
}
printf("\n");
}
/*
交集思路：遍历数组A，和B中的每一个值比较，如果相同，flag = 1，就加入到buffer缓冲数组中，就可以找到所有的相同元素
因为输入本来就是有序的，所以不需要排序。
*/
void intersection(int *A,int *B,int lenA,int lenB) {
int i,j;
int flag,index = 0,len = lenA > lenB ? lenA:lenB;
int *buffer = (int *)malloc(sizeof(int) * len);
//遍历A集合
for(i = 0;i < lenA;i++) {
flag = 0;
//遍历B集合
for(j = 0;j < lenB;j++) {
//如果有相等
if(A[i] == B[j]){
flag = 1;
}
}
for(j = 0;j < index;j++) {
if(A[i] == buffer[j])
flag = 0;
}
if(flag) {
buffer[index] = A[i];
index++;
}
}
for(i = 0;i< index;i++) printf("%d ",buffer[i]);
printf("\n");
}
//差与交集相反
void complementary(int *A,int *B,int lenA,int lenB) {
int i,j;
int flag,index = 0;
int *buffer = (int *)malloc(sizeof(int) * lenA);
for(i = 0;i < lenA;i++) {
flag = 1;
for(j = 0;j < lenB;j++) {
if(A[i] == B[j]) flag = 0;
}
if(flag) {
buffer[index] = A[i];
index++;
}
}
for(i = 0;i < index;i++) printf("%d ",buffer[i]);
printf("\n");
}
int main() {
srand(15);
int a[MAX],b[MAX];//存储输入的集合
int i = 0,m = 0,n = 0;
printf("请输入集合A的元素个数：");
scanf("%d",&n);
for(i = 0;i < n;i++) a[i] = rand()%10;
printf("请输入集合B的元素个数：");
scanf("%d",&m);
for(i = 0;i < n;i++) b[i] = rand()%10;
cout<<"随机生成的集合A：";
for(i = 0;i < n;i++) cout<<a[i]<<" ";
cout<<endl;
cout<<"随机生成的集合B：";
for(i = 0;i < n;i++) cout<<b[i]<<" ";
cout<<endl;
cout<<"合并：";
unionSet(a,b,n,m);
cout<<"交集：";
intersection(a,b,n,m);
cout<<"差：";
complementary(a,b,n,m);
} 链表：
#include <iostream>
#include<stdio.h>
#include<malloc.h>
#include<cstdio>
#include<time.h>
#include<stdlib.h>
using namespace std;
typedef char ElemType;
//结构体
typedef struct LNode {
ElemType data;
struct LNode *next;
} LinkList;
void DispList(LinkList*L) {
LinkList *p=L->next;
while(p!=NULL) {
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void DestroyList(LinkList *&L) {
LinkList*p=L->next,*pre=L;
while(p!=NULL) {
free(pre);
pre=p;
p=pre->next;
}
free(pre);
}
//尾插法建表
void CreatListR(LinkList *&L,ElemType a[],int n) {
LinkList *s,*r;
L=(LinkList*)malloc(sizeof(LinkList));
r=L;
for(int i=0; i<n; i++) {
s=(LinkList*)malloc(sizeof(LinkList));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
//从小到大排序
void sort(LinkList *&L) {
LinkList *pre,*p,*q;
p=L->next->next;
L->next->next=NULL;
while(p!=NULL) {
q=p->next;
pre=L;
while(pre->next!=NULL && pre->next->data<p->data)
pre=pre->next;
p->next=pre->next;
pre->next=p;
p=q;
}
}
//求集合的并
void Union(LinkList *ha,LinkList*hb,LinkList*&hc) {
LinkList *pa=ha->next,*pb=hb->next,*pc,*s;
hc=(LinkList*)malloc(sizeof(LinkList));
pc=hc;
while(pa!=NULL &&pb!=NULL ) {
if(pa->data<pb->data) {
s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
}
else if(pa->data>pb->data) {
s=(LinkList*)malloc(sizeof(LinkList));
s->data=pb->data;
pc->next=s;
pc=s;
pb=pb->next;
} else {
s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
pb=pb->next;
}
}
if(pb!=NULL) pa=pb;
while(pa!=NULL) {
s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
}
pc->next=NULL;
}
///求两个有序集合的交用尾插法
void InterSect(LinkList *ha,LinkList*hb,LinkList*&hc) {
LinkList *pa=ha->next,*pb,*pc,*s;
hc=(LinkList*)malloc(sizeof(LinkList));
pc=hc;
while(pa!=NULL) {
pb=hb->next;
while(pb!=NULL&&pb->data<pa->data)
pb=pb->next;
if(pb!=NULL &&pb->data==pa->data)//B节点在A节点中复制A节点
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
}
pa=pa->next;
}
pc->next=NULL;
}
///求两个有序集合的差
void Subs(LinkList *ha,LinkList*hb,LinkList*&hc) {
LinkList *pa=ha->next,*pb,*pc,*s;
hc=(LinkList*)malloc(sizeof(LinkList));
pc=hc;
while(pa!=NULL){
pb=hb->next;
while(pb!=NULL&&pb->data<pa->data)
pb=pb->next;
//B节点不在A节点中复制A节点
if(!(pb!=NULL &&pb->data==pa->data)) {
s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
}
pa=pa->next;
}
pc->next=NULL;
}
int main() {
srand(15);
LinkList *ha,*hb,*hc;
ElemType a[10000];
ElemType b[10000];
int len1,len2;
cout<<"请输入集合A的元素个数：";
cin>>len1;
for(int i=0;i<len1;i++){
a[i] = rand()%10;
}
cout<<"请输入集合B的元素个数：";
cin>>len2;
for(int i=0;i<len2;i++){
b[i] = rand()%10;
}
//创建链表
CreatListR(ha,a,len1);
CreatListR(hb,b,len2);
printf("随机生成的集合A: ");
//输出A
DispList(ha);
printf("随机生成的集合B: ");
//输出B
DispList(hb);
//排序
sort(ha);
sort(hb);
// printf(" 有序集合A: ");
// DispList(ha);
// printf(" 有序集合B: ");
// DispList(hb);
//合并
Union(ha,hb,hc);
printf("合并: ");
DispList(hc);
//交集
InterSect(ha,hb,hc);
printf("交集: ");
DispList(hc);
//差
Subs(ha,hb,hc);
printf("差: ");
DispList(hc);
//清空内存节点
DestroyList(ha);
DestroyList(hb);
DestroyList(hc);
return 0;
}