求两个集合交集的算法用链表用c语言或c++都可以

求两个集合交集的算法用链表用c语言或c++都可以
求两个集合交集的算法
用链表
用c语言或c++都可以

求两个集合交集的算法用链表用c语言或c++都可以
我这里有一个很强的,是以前的作业,功能有很多!
有问题来找小斌
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
#include
#include
#include
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 {
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->datadata)
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->datadata)
{
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');
}

两个集合交集即相同的部分

交集为 {X/X＝k1ε1+k2ε2...+knεn且 X=m1η1+m2η2...+mnηn, k1,k2..kn 不同时为零且m1,m2...mn 不同时为零} 只要两线性空间相交，交集就不为零 ,不知道对不对啊，毕业很久了。。