求元素递增排列的线性表A和B的元素的交集并存入C中
时间: 2023-03-28 15:03:42 浏览: 81
好的,这个问题我可以回答。首先,我们需要将线性表A和B进行排序,然后使用双指针法来求它们的交集。具体来说,我们可以用两个指针i和j分别指向A和B的起始位置,然后比较A[i]和B[j]的大小关系,如果A[i]小于B[j],则将i向后移动一位,否则将j向后移动一位。如果A[i]等于B[j],则将它加入到C中,并将i和j都向后移动一位。重复这个过程直到其中一个指针到达了末尾。最后,C中存储的就是A和B的交集了。
相关问题
用线性表求线性表a和线性表b的差集
以下是用线性表求线性表a和线性表b的差集的方法:
```c++
template <class ElemType>
void Difference(SqList<ElemType>& La, SqList<ElemType>& Lb, SqList<ElemType>& Lc) {
int i = 1, j = 1, k = 1;
while (i <= La.Length() && j <= Lb.Length()) {
if (La.GetElem(i) < Lb.GetElem(j)) {
Lc.Insert(k++, La.GetElem(i++));
} else if (La.GetElem(i) == Lb.GetElem(j)) {
i++;
j++;
} else {
j++;
}
}
while (i <= La.Length()) {
Lc.Insert(k++, La.GetElem(i++));
}
}
```
其中,SqList是一个线性表类,Length()函数返回线性表的长度,GetElem(i)函数返回线性表中第i个元素,Insert(i, e)函数在线性表的第i个位置插入元素e,Traverse(print)函数遍历线性表并输出每个元素。
假设以两个元素依值严格递增排列的线性表a和b分别表示两个集合,现要求另外开辟空间构成一个线性表c,其元素为a和b元素的交集,且表c中的元素也依值严格递增。若使用单链表作为存储结构,编写求c的算法。
算法步骤如下:
1. 定义两个指针p和q分别指向线性表a和b的头结点。
2. 定义一个新的单链表c,初始化为空表。
3. 循环比较p和q指向的元素值,如果相等,则将该元素插入到c中,并将p和q同时后移一位;如果p指向的元素值小于q指向的元素值,则将p后移一位;如果p指向的元素值大于q指向的元素值,则将q后移一位。
4. 当p或q指向空节点时,结束循环。
5. 返回新的单链表c。
代码实现如下:
```
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* intersection(Node* a, Node* b) {
Node* p = a->next;
Node* q = b->next;
Node* c = (Node*)malloc(sizeof(Node));
c->next = NULL;
Node* tail = c;
while (p != NULL && q != NULL) {
if (p->data == q->data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = p->data;
node->next = NULL;
tail->next = node;
tail = node;
p = p->next;
q = q->next;
} else if (p->data < q->data) {
p = p->next;
} else {
q = q->next;
}
}
return c;
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)