第二章 线性表
程序员文章站
2022-05-26 12:00:08
...
(4) 巳知两个链表 A 和 B 分别表示两个集合,其元素递增排列。请设计算法 求出两个集合 A
和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以 同样的形式存储,
同时返回该集合的元素个数。
#include <stdio.h>
#include <iostream>
#define LENGTH 5
typedef struct LNode
{
int data;
struct LNode *next;
} LNode, *LinkList;
void CreatList_R(LinkList &L, int n)
{
L = new LNode;
L->next = NULL;
LNode *r = L;
for (int i = 0; i < n; i++)
{
LNode *p = new LNode;
printf("请输入第%d个结点data值:", i + 1);
std::cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
void ShowList(LinkList L)
{
LNode *p = L->next; // 指向首元结点
while (p)
{
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}
void SubList(LinkList &L1, LinkList &L2, LinkList &L3)
{
L3 = L1;
L3->data = 0;
LNode *r = L3;
LNode *p2 = L2->next;
LNode *p1 = L1->next;
while (p1 && p2)
{
if (p1->data == p2->data)
{
p1 = p1->next;
p2 = p2->next;
}
else if (p1->data > p2->data)
p2 = p2->next;
else
{
r->next = p1;
r = p1;
p1 = p1->next;
L3->data++;
}
}
while (p1)
{
r->next = p1;
r = p1;
p1 = p1->next;
L3->data++;
}
if (r->next)
r->next = NULL;
delete L2;
}
int main(void)
{
LinkList L1, L2, L3;
CreatList_R(L1, LENGTH);
printf("L1:");
ShowList(L1);
CreatList_R(L2, LENGTH);
printf("L2:");
ShowList(L2);
SubList(L1, L2, L3);
printf("L3 = L1 - L2\n");
printf("L3有%d个结点,且data分别为:", L3->data);
ShowList(L3);
delete L3;
return 0;
}
运行结果:
有时候可能会理解错题义,做错了请告诉一下小茅芦。