已知两个顺序表A和B分别表示两个集合,其元素递增排列,编写一个函数求出A和B的交集C,要求C同样以元素递增的顺序表形式存储

Question

已知两个顺序表A和B分别表示两个集合,其元素递增排列,编写一个函数求出A和B的交集C,要求C同样以元素递增的顺序表形式存储

Answer 1

typedef struct link {
int data;
struct link *next ;
} LINK ;
LINK * your_func( LINK *A , LINK *B ) //设A、B是带头结点的顺序表
{
LINK *pa=A->next , *pb=B->next ,*pc=NULL , *pcH,*p;
//先创建表头
pcH=pc=new LINK ;
pc->next=NULL ;
while ( pa && pb ) //有一个结束,循环就结束
{
while( pa->data < pb->data )
{
pa=pa->next ; //pa 向 pb 靠拢
if ( !pa )
return pcH; //到pa的尾,结束
} //此时,pa的数据>=pb
while( pb->data < pa->data )
{
pb=pb->next ; //pb 向 pa 靠拢
if ( !pb )
return pcH; //到pa的尾,结束
}//此时,pb的数据>=pa
if ( pb->data == pa->data )
{
p = new LINK ;
p->data=pa->data;
p->next=NULL;

pc->next=p;
pc = p;

pa=pa->next;
pb=pb->next;
}
}
return pcH ;
}