求2个链表的并集

75 阅读 0 评论 50 点赞

我是靠谱客的博主爱笑月饼，最近开发中收集的这篇文章主要介绍求2个链表的并集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode
{	ElemType data;
	struct LNode *next;
} LinkNode;
void InitList(LinkNode *&L)                       //初始化线性表
{	L=(LinkNode *)malloc(sizeof(LinkNode));
	L->next=NULL;
}
void CreateListR(LinkNode *L,ElemType a[],int n)   //尾插法建立链表
{	LinkNode *s,*r;
	r=L;
	for(int i=0; i<n; i++)
	{	s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;
}
void HeBin(LinkNode *C,LinkNode *A,LinkNode *B)     //求A，B链的并集，放在C链中
{	LinkNode *s,*tail,*pa,*pc,*pb;
	tail=C;                 //用tail一直指向C链的最后一个结点 
	pa=A->next;
	while(pa!=NULL)         //把A链复制到C链
	{	s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=pa->data;
		tail->next=s;
		tail=s;
		pa=pa->next;
	}
	tail->next=NULL;
	pb=B->next;           //pb遍历B链
	while(pb!=NULL)
	{	pc=C->next;         //用pc遍历C链表
		while(pc!=NULL)
		{	if(pb->data==pc->data)
				break;
			pc=pc->next;
		}
		if(pc==NULL)       //说明遍历完，没有重复的,链到C链后面
		{	s=(LinkNode *)malloc(sizeof(LinkNode));
			s->data=pb->data;
			tail->next=s;
			tail=s;
			tail->next=NULL;
		}
		pb=pb->next;
	}
	tail->next=NULL;
}
void DispList(LinkNode *L)    //输出链表
{	LinkNode *p=L->next;
	while(p!=NULL)
	{	printf("%d ",p->data);
		p=p->next;
	}
	printf("n");
}
int main()
{	LinkNode *A,*B,*C;
	ElemType a[100],b[100];
	int i,t;
	InitList(A);
	InitList(B);
	InitList(C);
	printf("请输入A集合元素(0结束):");
	for(i=0; i<100; i++)
	{	scanf("%d",&t);
		if(t==0)
			break;
		else
			a[i]=t;
	}
	CreateListR(A,a,i);
	printf("请输入B集合元素(0结束):");
	for(i=0; i<100; i++)
	{	scanf("%d",&t);
		if(t==0)
			break;
		else
			b[i]=t;
	}
	CreateListR(B,b,i);
	HeBin(C,A,B);
	DispList(C);
}