求两个单循环链表的并集-爱代码爱编程
今天数据结构留的作业里包含这样一道题,题目如下:假设递增有序的带头结点的单循环链表A、B分别表示两个集合,设计算法以求解A=AUB。
思路大概就是创建两个单循环链表A、B,然后将B里的元素依次插入到A里的合适位置,如果某元素为A、B集合共有,则不进行插入操作。最后输出并集链表。
为此,我们应创建四个函数,分别为:1.单链表创建函数,2.判断数值是否在链表里的函数、3.链表取交集函数、4.链表遍历输出函数
实现代码如下:
#include<iostream>
#define LEN sizeof(Listpoint)
using namespace std;
//定义链表结点
typedef struct Listpoint
{
int data;
//指向下一个结点
Listpoint* next;
}Listpoint;
//创建长度为Listlen的链表并返回头结点的指针
Listpoint* creat_normal_list(int Listlen)
{
//创建头结点并开辟空间
Listpoint* head = NULL, * normal = NULL, * end = NULL;
head = (Listpoint*)malloc(LEN);
end = head;
printf("输入%d个数值:", Listlen);
for (int i = 0; i < Listlen; i++) {
normal = (Listpoint*)malloc(LEN);
if (normal != NULL) {
cin >> normal->data;
}
if (end != NULL) {
end->next = normal;
}
end = normal;
}
//链表尾结点的next指向头结点
if (end != NULL) {
end->next = head;
}
return head;
}
//依次输出单循环链表结点的值
void put_list(Listpoint* head)
{
Listpoint* H;
H = head->next;
while (H != head)
{
printf("%d ", H->data);
H = H->next;
}
}
//判断某值是否在某链表里,存在返回false,不存在返回ture
bool judge(Listpoint* head, int x)
{
Listpoint* H = head->next;
while (H != head) {
if (H->data == x) {
return false;
}
else {
H = H->next;
}
}
return true;
}
//合并链表
void combine_list(Listpoint* Fhead, Listpoint* Shead)
{
Listpoint* FH = NULL, *FE = NULL, * S = NULL;
FH = Fhead->next;
S = Shead->next;
FE = FH;
while (FE->next != Fhead) {
FE = FE->next;
}
while (S != Shead) {
//如果S->data的值不在F链表里,则进行插入操作
if (judge(FH, S->data)) {
//创建新的待插入的结点
Listpoint* r = (Listpoint*)malloc(LEN);
if (r != NULL) {
r->data = S->data;
}
//寻找正确位置插入
if (S->data < FH->data) { //情况一:待插入元素小于该链表中最小的元素
Fhead->next = r;
r->next = FH;
FH = r;
}
else if (S->data > FE->data) { //情况二:待插入元素大于该链表中最大的元素
FE->next = r;
r->next = Fhead;
FE = r;
}
else { //情况三:待插入元素介于链表最小和最大元素中间
while (FH != FE) {
FH = FH->next;
if (r->data > FH->data && r->data < FH->next->data) {
FH->next = r;
r->next = FH->next;
}
}
FH = Fhead->next;
}
}
S = S->next;
}
}
int main(void)
{
Listpoint* Fhead = NULL, * Shead = NULL;
//创建两个链表
int ListlenA, ListlenB;
printf("请输入第一个链表的长度:");
cin >> ListlenA;
Fhead = creat_normal_list(ListlenA);
printf("请输入第二个链表的长度:");
cin >> ListlenB;
Shead = creat_normal_list(ListlenB);
//取两个链表的并集,即令A=AUB
combine_list(Fhead, Shead);
//输出取并集后的列表
printf("取交集后的链表为:");
put_list(Fhead);
free(Fhead);
free(Shead);
}
运行结果如图所示:
新人程序员,能力不足,如有错误,还望谅解。