6-101 LinkList11-求两个单链表的差集【有题解视频，可本地编译器调试】-Toy模板网

这篇具有很好参考价值的文章主要介绍了6-101 LinkList11-求两个单链表的差集【有题解视频，可本地编译器调试】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

已知两个单链表A与B，设计算法AdiffB( )，构造出A与B的差集新链表C，链表C中的元素值为A链表中有而B链表中无的元素值。
要求C表的链点为新开辟的链点，不采用A、B链表中原有链点，最后要求遍历A、B、C三个链表。

数据结构定义

带头结点的单链表结点定义如下：

typedef int DataType;
typedef struct Node
{
DataType data; // data域用于存储数据元素
struct Node *next; // next域用于存放指向其后继的指针
}LNode, *PNode, *LinkList; // LinkList为头指针

函数接口定义：

在这里描述函数接口。例如：
void AdiffB ( LinkList a, LinkList b, LinkList *c );

其中 a 、b和c 都是用户传入的参数，a和b分别为求差集的两个单链表的头指针，而c为求出来的差集单链表的头指针。

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node* next;
}LNode, * PNode, * LinkList;
int InitLinkList(LinkList* head)
{ // 初始化单链表，开辟头结点
*head = (LinkList)malloc(sizeof(LNode));
if (!head)
{
printf("初始化链表错误!\n");
return 0;
}
(*head)->next = NULL;
return 1;
}
PNode LinkListInsert(LinkList h, int pos, DataType x)
{ // 在单链表h的第pos个位置插入x值的元素
PNode p = h, q;
int i = 0;
while (p && i < pos - 1)
{
p = p->next;
i++;
}
if (!p || i > pos - 1)
{
printf("插入位置不合法!\n");
return NULL;
}
q = (PNode)malloc(sizeof(LNode));
if (!q)
{
printf("不能生成新结点\n");
return NULL;
}
q->data = x;
q->next = p->next;
p->next = q;
return q;
}
void DestroyLinkList(LinkList h)
{ // 销毁单链表
PNode p = h->next;
while (h)
{
p = h;
h = h->next;
free(p);
}
}
void TraverseLinkList(LinkList h)
{ // 遍历单链表
PNode p = h->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
/* 本题要求函数 */
void AdiffB(LinkList a, LinkList b, LinkList* c);
int main()
{
char ch;
LinkList aa, bb, cc;
DataType x;
int pos = 1;
InitLinkList(&aa);
InitLinkList(&bb);
InitLinkList(&cc);
do
{
scanf("%d", &x); // 某些编译器要求此处改为scanf_s
LinkListInsert(aa, pos++, x);
} while ((ch = getchar()) != '\n');
pos = 1;
do
{
scanf("%d", &x); // 某些编译器要求此处改为scanf_s
LinkListInsert(bb, pos++, x);
} while ((ch = getchar()) != '\n');
AdiffB(aa, bb, &cc);
printf("单链表A是\n");
TraverseLinkList(aa);
printf("单链表B是\n");
TraverseLinkList(bb);
if (cc->next != NULL)
{
printf("单链表C是\n");
TraverseLinkList(cc);
}
DestroyLinkList(aa);
DestroyLinkList(bb);
DestroyLinkList(cc);
}
/* 你的答案写在此处 */

输入样例：

98 76 54 50 38 9
89 50 40 38 20 11 5

输出样例：

单链表A是
98 76 54 50 38 9 
单链表B是
89 50 40 38 20 11 5 
单链表C是
98 76 54 9

void AdiffB(LinkList a, LinkList b, LinkList* c)
{
PNode pa = a->next;
PNode pb = b->next;
PNode pc = *c;

while (pa)
{
int found = 0;
pb = b->next;

while (pb)
{
if (pa->data == pb->data)
{
found = 1;
break;
}

pb = pb->next;
}

if (!found)
{
PNode newNode = (PNode)malloc(sizeof(LNode));
newNode->data = pa->data;
newNode->next = pc->next;
pc->next = newNode;
pc = newNode;
}

pa = pa->next;
}
}文章来源地址https://www.toymoban.com/news/detail-816979.html