集合交集演算法
① 如何寫一個c語言程序求兩個集合的交集
定義兩個數組存放這兩個集合，再定義一個數組存放它們的集合，用類似冒泡排序的演算法，遍歷數組1中的第一個元素和數組2中每一個元素，若有相同的，則把這個元素放入第三個數組，繼續遍歷，知道數組1遍歷完所有元素，那數組3中的元素，即為兩個數組(集合)的交集。
② 集合的交集與並集
【補充：A∩D={直角三角形}，B∩D={等腰直角三角形}】
交集就是既要屬於A又要屬於B，且的關系，類似於演算法中的乘法，
而並集是屬於A或者屬於B，或的關系，類似於演算法中的加法。
已知集合A={三角形}，B={等腰三角形}，C={等邊三角形}，D={直角三角形}，那麼A交B，B並C，C交D，A並D，B交C，B並D。
解：
A∩B={等腰三角形}，
B∪C={等腰三角形}，
C∩D=空集
A∪D={三角形}
B∩C={等邊三角形}
B∪D={等腰三角形和直角三角形}
③ 求兩個集合的交集，用c++語言寫
#include<stdio.h>
double P[n1],Q[n2]; //R=P∩Q
double R[];
double TEMP;
for(i=0;i<n1;i++)
{for(j=0;j<n2;j++)
if(P[i]==Q[j])
{
TEMP=P[i];
R[m]=TEMP;
m++;
}
}
④ 集合的運算（交集，並集）
1、a≥2
2,a≥3,
3,∵M:x＜-2或x＞4,N:x＜1，或x＞3,
∴M∪N=N={x│x＜1，或x＞3}
4,B:x≥0
∴AUB={x│x＞2},
∴A∩B={x│0≤x＜2,x∈Z}={0,1},
5,同上，
6，解：設X^2+pX-6=0兩根為x1,x2,且設x1＜x2,
∴x1+x2=-p,x1x2=-6,
解集A={x│x≤x1，或x≥x2}
設X^2-2pX+q=0兩根為x3,x4,且設x3＜x4,
∴x3+x4=2p,x3x4=q,
解集B={x│x3＜x＜x4}
∵A∩B={X|2<=X<4},
∴只有x1＜x3＜x2＜x4,且x2=2,x4=4，
則x1=-3,p=-(x1+x2)=1,
x3=2-x4=-2,q=x3x4=-8,
此時A:x≤-3，或x≥2
B:-2＜x＜4
∴AUB={x│x≤-3，或x＞-2}
⑤ 求兩個集合交集的演算法
我這里有一個很強的，是以前的作業，功能有很多！
有問題來找小斌
QQ：504449327
#define
TRUE
1
#define
FALSE
0
#define
OK
1
#define
ERROR
0
#define
INFEASIBLE
-1
#define
OVERFLOW
-2
typedef
int
Status;
typedef
char
ElemType;
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<conio.h>
typedef
struct
NodeType
{
ElemType
data;
struct
NodeType
*next;
}
NodeType,*LinkType;
typedef
struct
{
LinkType
head,tail;
int
size;
}OrderedList;
ElemType
a[100]="magazine";
ElemType
b[100]="paper";
OrderedList
L1,L2,L3;
Status
MakeNode(LinkType
&p,ElemType
e)/*函數功能，創建一個結點，用p指向它，並把e的值賦給date*/
{
p=(LinkType)malloc(sizeof(NodeType));
if(!p)
return
FALSE;
p->data=e;
p->next=NULL;
return
TRUE;
}
Status
InitList(OrderedList
&L)
/*函數功能，建立空棧*/
{
if(MakeNode(L.head,'
'))
{
L.tail=L.head;
L.size=0;
return
TRUE;
}
else
{
L.head=NULL;
return
FALSE;
}
}
Status
LocateElem(OrderedList
L,
ElemType
e,
LinkType
&p)
{
NodeType
*pre;
if(L.head)
/*棧建立成功*/
{
pre=L.head;
p=pre->next;
while(p
&&
p->data<e)
/*第二個結點中的data比e小，就讓p和pre指向下一個結點*/
{
pre=p;
p=p->next;
}
if(p
&&
p->data==e)/*找到和e相等的date，p指向這個結點*/
{
return
TRUE;
}
else
/*如果找不到，p指向剛好比e小的結點*/
{
p=pre;
return
FALSE;
}
}
else
return
FALSE;
}
void
InsertAfter(OrderedList
L,
LinkType
q,
LinkType
s)
/*在結點q之後插入s結點*/
{
if(L.head
&&
q
&&
s)
{
s->next=q->next;
q->next=s;
if(L.tail==q)
L.tail=s;
L.size++;
}
}
void
CreateSet(OrderedList
&T,
char
*s)/*將s中的元素按從小到大的順序插入到T控制的鏈表中*/
{
unsigned
i;
LinkType
p
,q;
if(InitList(T))
/*建立一個空棧*/
{
for(i=0;i<=strlen(s);i++)
{
if(s[i]>='a'
&&
s[i]<='z'
&&
!LocateElem(T,s[i],p))
{
if(MakeNode(q,s[i]))
{
InsertAfter(T,p,q);
}
}
}
}
}
Status
Print(LinkType
p)/*輸出一個鏈表*/
{
if(p)
{
printf("%c",p->data);
return
TRUE;
}
else
return
FALSE;
}
void
ListTraverse(LinkType
p,
Status
(*visit)(
LinkType
))
{
printf("%c",'\t');
while(p)
{
visit(p);
//這句看不懂
p=p->next;
}
printf("%c",'\n');
}
void
Append(OrderedList
&L,LinkType
s)
{
if(L.head
&&
s)
{
if(L.tail!=L.head)
L.tail->next=s;
else
L.head->next=s;
L.tail=s;
L.size++;
}
}
void
Union(OrderedList
&T,OrderedList
S1,OrderedList
S2)
{
LinkType
p1,p2,p;
if(InitList(T))
{
p1=S1.head->next;
p2=S2.head->next;
while(
p1
&&
p2)
{
if(p1->data<=p2->data)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
if(p1->data==p2->data)
p2=p2->next;
p1=p1->next;
}
else
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p2->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
}
}
while(p1)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
while(p2)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p2->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
}
}
}
void
Intersection(OrderedList
&T,OrderedList
S1,OrderedList
S2)
{
LinkType
p1,p2,p;
if(!InitList(T))
T.head=NULL;
else
{
p1=S1.head->next;
p2=S2.head->next;
while(
p1
&&
p2)
{
if(p1->data<p2->data)
p1=p1->next;
else
if(p1->data>p2->data)
p2=p2->next;
else
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
p1=p1->next;
}
}
}
}
void
Difference(OrderedList
&T,OrderedList
S1,OrderedList
S2)
{
LinkType
p1,p2,p;
if(!InitList(T))
T.head=NULL;
else
{
p1=S1.head->next;
p2=S2.head->next;
while(
p1
&&
p2)
{
if(p1->data<p2->data)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
else
if(p1->data>p2->data)
p2=p2->next;
else
{
p1=p1->next;
p2=p2->next;
}
}
while(p1)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
}
}
void
ReadCommand(char
&cmd)
{
printf("\n
------------------------------------------------------------------------\n");
printf("\n\t\t\t\t操
作
提
示");
printf("\n
------------------------------------------------------------------------\n");
printf("\tMakeSet1------1\t\t\t\tMakeSet2--------2\n\tUnion---------u\t\t\t\tIntersection----i\n\tDifference----d\t\t\t\tQuit------------q\n\tDisplay-------y");
do{
printf("\n\n\t請選擇操作：");
cmd=getch();
printf("\n--------------------------------------------------------------------------\n");
}while(cmd!='1'
&&
cmd!='2'
&&
cmd!='u'
&&
cmd!='i'
&&
cmd!='d'
&&
cmd!='q'
&&
cmd!='y');
}
void
Interpret(char
&cmd)
{
system("cls");
switch(cmd)
{
case
'1':
printf("\n\t請輸入字元串：");
gets(a);
printf("\t原始字元串:");
printf("\t%s\n",a);
CreateSet(L1,
a);
printf("\t構建的集合:");
ListTraverse(L1.head->next,Print);
break;
case
'2':
printf("\n\t請輸入字元串：");
gets(b);
printf("\t原始字元串:");
printf("\t%s\n",b);
CreateSet(L2,
b);
printf("\t構建的集合:");
ListTraverse(L2.head->next,Print);
break;
case
'u':
CreateSet(L1,
a);
CreateSet(L2,
b);
Union(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t並集:");
ListTraverse(L3.head->next,Print);
break;
case
'i':
CreateSet(L1,
a);
CreateSet(L2,
b);
Intersection(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t交集:");
ListTraverse(L3.head->next,Print);
break;
case
'd':
CreateSet(L1,
a);
CreateSet(L2,
b);
Difference(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t差集:");
ListTraverse(L3.head->next,Print);
break;
case
'y':
printf("\n\t原始字元串:\n");
printf("\t\t%s\n\t\t%s\n",a,b);
CreateSet(L1,
a);
CreateSet(L2,
b);
printf("\t由字元串構建的集合:\n");
printf("\t");
ListTraverse(L1.head->next,Print);
printf("\t");
ListTraverse(L2.head->next,Print);
Union(L3,L1,L2);
printf("\t並集:");
ListTraverse(L3.head->next,Print);
Intersection(L3,L1,L2);
printf("\t交集:");
ListTraverse(L3.head->next,Print);
Difference(L3,L1,L2);
printf("\t差集:");
ListTraverse(L3.head->next,Print);
break;
}
}
void
main()
{
char
cmd;
do
{
ReadCommand(cmd);
Interpret(cmd);
}while(cmd!='q');
}
⑥ c語言中有沒有比較簡單的演算法來判斷兩個集合有交集
只判斷有沒有交集的話很簡單了，直接挨個比較就可以了，如果有相同的返回1，沒相同的返回0。
如果要求2個數組相交的元素的話自己寫一個代碼也可以，或者可以直接使用STL演算法中的set_intersection函數。