已知A、B和C为3个递增有序的线性表,现要求对A表做如下操作,删除那些既在B中出现,也在C中出现的元素。以带表头结点的单链表作为线性表的物理结构,编写实现上述操作的算法。 函数原型:void TriLinkList(LinkList A,LinkList B,LinkList C);
时间: 2023-05-29 22:06:12 浏览: 105
算法思路:
1. 初始化三个指针分别指向A、B、C的头结点;
2. 依次比较指针所指向的结点的值,如果A的当前结点的值小于B和C的当前结点的值,则将A的指针向后移动一位;
3. 如果A的当前结点的值等于B和C的当前结点的值,则删除A的当前结点,并将A的指针指向下一个结点;
4. 如果A的当前结点的值大于B和C的当前结点的值,则将B和C的指针分别向后移动一位;
5. 重复2-4步,直到A、B、C中有任何一个链表的结点为空为止。
代码实现:
void TriLinkList(LinkList A, LinkList B, LinkList C)
{
LNode *pa = A->next, *pb = B->next, *pc = C->next; // 初始化三个指针
LNode *pre = A; // 指向A链表当前结点的前一个结点,方便删除操作
while (pa && pb && pc) // 只要三个链表中有任何一个为空,就停止循环
{
if (pa->data < pb->data || pa->data < pc->data) // A链表当前结点的值小于B和C链表当前结点的值
{
pre = pa; // 记录A链表当前结点的前一个结点
pa = pa->next; // A链表的指针向后移动一位
}
else if (pa->data == pb->data && pa->data == pc->data) // A链表当前结点的值等于B和C链表当前结点的值
{
pre->next = pa->next; // 删除A链表的当前结点
free(pa); // 释放删除的结点的内存空间
pa = pre->next; // A链表的指针指向下一个结点
}
else // A链表当前结点的值大于B和C链表当前结点的值
{
if (pb->data < pc->data) // B链表当前结点的值小于C链表当前结点的值
pb = pb->next; // B链表的指针向后移动一位
else // C链表当前结点的值小于B链表当前结点的值
pc = pc->next; // C链表的指针向后移动一位
}
}
}
阅读全文