已知两个链表A和B分别表示两个集合, 其元素递增排列. 设计算法求出两个集合A和B的差集(即仅由在A中出现而不在B中出现的元素所构成的集合), 结果存放在链表A中, 同时返回所求差集中元素的个数
程序员文章站
2022-03-10 12:08:36
...
#include<stdio.h>
#include<stdlib.h>
short InitHeadNode(struct Node* &, struct Node* &);
short RearInsert(struct Node* &, struct Node* &, short);
short GetListLength(struct Node* &);
short IsElemIn(struct Node* &, short);
short DeleteNodeIn1andIn2(struct Node* &, struct Node* &);
void Traversal(struct Node* &);
/* 链表结点定义 */
struct Node
{
short data;
struct Node *next;
};
int main()
{
struct Node *head1;
struct Node *rear1;
struct Node *head2;
struct Node *rear2;
/* 初始化1#链表的头结点 */
if(InitHeadNode(head1, rear1) == -1)
{
/* 头结点申请失败, 程序直接结束 */
exit(0);
}
short temp;
/* 向链表中插入数据结点 */
while(1)
{
while(scanf("%hd", &temp) != 1)
{
while(getchar() != '\n') ;
printf("请输入合法数据.\n");
}
if(temp == -1)
{
break;
}
if(RearInsert(head1, rear1, temp) == -1)
{
/* 申请结点失败 */
exit(0);
}
}
/* 初始化2#链表的头结点 */
if(InitHeadNode(head2, rear2) == -1)
{
/* 头结点申请失败, 程序直接结束 */
exit(0);
}
/* 向链表中插入数据结点 */
while(1)
{
while(scanf("%hd", &temp) != 1)
{
while(getchar() != '\n') ;
printf("请输入合法数据.\n");
}
if(temp == -1)
{
break;
}
if(RearInsert(head2, rear2, temp) == -1)
{
/* 申请结点失败 */
exit(0);
}
}
/* 至此, A链表和B链表均已初始化 */
printf("\nA链表中还剩%3hd个元素.\n", DeleteNodeIn1andIn2(head2, head1));
Traversal(head1);
/* */
return 0;
}
/* 判断数据元素value是否在链表中 */
short IsElemIn(struct Node* &head, short value)
{
struct Node *p = head -> next;
while(p != NULL)
{
if(p -> data == value)
{
/* 找到数据元素value */
return 1;
}
p = p -> next;
}
/* 未找到数据元素value */
return -1;
}
/* 删除以下2#集合中的元素结点: 在2#集合中出现且也在1#集合中出现的元素结点 */
short DeleteNodeIn1andIn2(struct Node* &head1, struct Node* &head2)
{
struct Node *p2 = head2 -> next;
struct Node *q2 = head2;
/* 删除在集合2中出现且也在集合1中出现的结点 */
while(p2 != NULL)
{
if(IsElemIn(head1, p2 -> data) == 1)
{
/* 删除该结点 */
q2 -> next = p2 -> next;
free(p2);
p2 = q2 -> next;
}
else
{
p2 = p2 -> next;
q2 = q2 -> next;
}
}
/* 返回经历删除操作后2#链表的表长 */
return GetListLength(head2);
}
/* 遍历单链表并输出 */
void Traversal(struct Node* &head)
{
struct Node *p = head -> next;
while(p != NULL)
{
printf("%3hd", p -> data);
p = p -> next;
}
putchar('\n');
}
/* 获取表长 */
short GetListLength(struct Node* &head)
{
struct Node *p = head -> next;
short length = 0;
while(p != NULL)
{
length ++;
p = p -> next;
}
return length;
}
/* 尾插法 */
short RearInsert(struct Node* &head, struct Node* &rear, short value)
{
struct Node *p = (struct Node*)malloc(sizeof(struct Node));
if(p != NULL)
{
/* 结点申请成功 */
rear -> next = p;
p -> next = NULL;
p -> data = value;
rear = p;
return 1;
}
else
{
/* 结点申请失败 */
return -1;
}
}
/* 初始化头结点 */
short InitHeadNode(struct Node* &head, struct Node* &rear)
{
struct Node *p = (struct Node*)malloc(sizeof(struct Node));
if(p != NULL)
{
/* 头结点申请成功 */
head = p;
head -> data = 0;
head -> next = NULL;
rear = head;
return 1;
}
else
{
/* 头结点申请失败 */
return -1;
}
}
上一篇: C++ rapidjson 基础入门
下一篇: matlab画圆