假设以两个元素依值严格递增排列的线性表a和b分别表示两个集合,现要求另外开辟空间构成一个线性表c,其元素为a和b元素的交集,且表c中的元素也依值严格递增。若使用单链表作为存储结构,编写求c的算法。
时间: 2023-04-27 20:02:15 浏览: 93
算法步骤如下:
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;
}
```
阅读全文