Question

数据结构算法 两线性表A，B求交集。。。请高手指点！！！

已知按值递增有序排练的两个线性表A和B，且每个线性表内部各元素互不相同。试构造线性表C，使其是A和B的交集，且其中的数字同样按值递增排列。 要求： 1）分别采用顺序表、单链表、双链表三种数据结构存储上述线性表A、B、C 2）编写一个通用的程序（无论线性表A、B和C采用顺序表、单链表还是双链表存储，该程序完全通用），实现对线性表C的构造-Known to increase the value ordered by the two linear tables A rehearsal and B, and each of the elements within the linear table from each other. Linear table test structure C, it is the intersection of A and B, and the same number of them increasing order by value. Requirements: 1) were used to order table, a single list, double-linked list data structure stored in the linear three tables A, B, C 2) write a generic program (either the linear form A, B and C using the order form, a single list, or double-linked list storage, the program is completely general), to achieve the construction of the linear form C

Answer 1

将A与B分别排序，然后求交。
例如：将A与B按升序排列，设A表头为P，B表头为Q，若A[P]>B[Q]那么Q++，若A[P]<B[Q]那么P++；如果A[P]=B[Q]，Q++、P++，Count++，And[Count]=B[Q-1]；当P或者Q其中一个达到了A或者B的表尾 算法结束。

以下是参考程序：
//----------------------------------------

#include <stdio.h>

int A[100001],B[100001];
int Ans[100001],Count,N,M;

void Swap(int &a,int &b)
{
int Temp=a;
a=b;
b=Temp;
}

void Sort(int L,int R,int A[])
{
int p,q,Mid;
if (L==R) return ;
Mid=A[(L+R)/2];
p=L-1;q=R+1;
do
{
p++;q--;
while (A[p]<Mid) p++;
while (A[q]>Mid) q--;
if (p<q) Swap(A[p],A[q]);
}while (p<q);
Sort(L,q,A);
Sort(q+1,R,A);
}

void Init()
{
int p,q;
p=q=1;
for (int i=2;i<=N;i++)
{
if (A[i]!=A[p])
{
p++;
A[p]=A[i];
}
}
for (int i=2;i<=M;i++)
{
if (A[i]!=B[q])
{
q++;
B[q]=A[i];
}
}

}

int main(void)
{
int p,q;
scanf("%d %d",&N,&M);//输入两个集合的元素的个数
for (int i=1;i<=N;i++)
scanf("%d",&A[i]);// 读取A集合
for (int i=1;i<=M;i++)
scanf("%d",&B[i]);//读取B集合
Sort(1,N,A);//A集合排序
Sort(1,M,B);//B集合排序
Init();//剔除同一集合的相同元素
p=q=1;
Count=0;
while (p<=N&&q<=M)//求解.
{
if (A[p]<B[q])
{
p++;
continue;
}
if (A[p]>B[q])
{
q++;
continue;
}
if (A[p]==B[q])
{
p++;q++;
Count++;
Ans[Count]=B[q-1];
continue;
}
}
for (int i=1;i<=Count;i++)
printf("%d ",Ans[i]);
return 0;
}

Answer 2

A的元素，如果有相同的就存入LC中，然后再LB的第二个元素........