假设有两个集合A和B,分别用两个顺序表La和Lb表示,即顺序表中的数据元素即为集合中的元素,利用顺序表的基本运算编写一个算法实现集合的交运算,即求一个新集合C=A∩B。
时间: 2023-05-20 18:02:54 浏览: 72
集合的并、交和差运算的算法.docx
可以使用双指针的方法来实现集合的交运算。首先将两个顺序表分别按照从小到大的顺序排序,然后定义两个指针i和j,分别指向La和Lb的第一个元素。然后比较La[i]和Lb[j]的大小,如果相等,则将该元素加入新集合C中,并将i和j都加1;如果La[i]小于Lb[j],则将i加1;如果La[i]大于Lb[j],则将j加1。重复上述过程直到其中一个顺序表遍历完为止。
以下是示例代码:
void intersection(int La[], int Lb[], int n, int m, int C[], int &len) {
sort(La, La + n);
sort(Lb, Lb + m);
int i = 0, j = 0;
len = 0;
while (i < n && j < m) {
if (La[i] == Lb[j]) {
C[len++] = La[i];
i++;
j++;
} else if (La[i] < Lb[j]) {
i++;
} else {
j++;
}
}
}
其中La和Lb分别表示集合A和B的顺序表,n和m分别表示它们的长度,C表示新集合C的顺序表,len表示新集合C的长度。
阅读全文