集合的合并 C语言实现

数据结构c语言单链表对集合的合并

首先初始化一个链表，并判断是否为空（这里就不写了）
然后就是对链表的创建，将数据输入到链表中，但是不知道要输入的集合中有多少数据，所以改成直接插入数据，不用输入要输入多长的集合。

LinkList CreatList(LinkList &L)//创建链表 
{
	int a;
	LNode *s,*r=L; 
	printf("请输入链表数据：");
	while(1)
	{
		scanf("%d",&a);//输入要链表数据 
		s = (LNode *)malloc(sizeof(LNode));//创建一个结点 
		s->data = a;
		r->next = s;
		r = s; 
		if(getchar()=='\n')//死循环结束条件 
			break;
	}
	r->next = NULL;//将r设置为尾结点 
	return L;
}

**查找并输出链表L的第i位上的数据。**建立一个for循环使创建的p结点指向第i个结点，输出的p->data便是第i位上的值。

int GetElem(LinkList L,int i)//查找第i位的值，并返回第i的值 
{
	int j;
	LNode *p = L;//创建一个结点并指向头结点 
	for(j=0;j<i;j++)//利用循环，是p结点指向第i位 
		p = p->next;
	return p->data;//返回第i的值 
}

建立一个bool类型的函数来判断输入的链表是否为集合，因为集合中的数不能重复。将链表导入该函数中，先创建一个变量a，b，利用两个for循环使a依次被赋值链表头到链表尾的数据。使变量a被赋值为链头结点的下一个结点数据，然后和该链表结点后面每个数b作比较，如果存在相等的（a==b），直接跳出函数。如果不存在，则变量a被赋值为下一个结点，以此循环，直到最后。

bool JudgeSet(LinkList L)//建立一个bool类型的函数来判断输入的链表是否为集合（集合中的数不能重复） 
{
	int i,j,a,b; 
	for(i=1;i<=Length(L);i++)
	{
		a = GetElem(L,i);//用变量a接链表第i个位置， 
		for(j=i+1;j<=Length(L);j++)//利用循环让第i个位置的和i之后的位置的数分别做比较 
		{
			b = GetElem(L,j);//用变量b接链表第j个位置，
			if(a==b)//出现a等于b，说明不是集合 
			{
				printf("输入的不是数组\n");
				return false;
			}
		}
	}
	return true;
}

**建立一个链表对集合的合并函数。**这是整篇的核心。重要思路是：创建一个野结点r，使L链表头结点的下一个结点元素赋值给野结点r，然后野结点r，进入遍历链表P的循环中，依次和链表P中的数据元素作比较，如果遍历到P链表尾结点都没有出现野结点r上的数据元素等于链表P的某结点上的数据，那么使野结点r导入链表P中，一次循环结束。创建一个野结点r，使L链表头结点的下下一个结点元素赋值给野结点r，重复上述操作，二次循环结束。以此循环直至到达循环结束条件结束，使链表L中的数据元素都导入到链表P中，并且是链表L和链表P中存在相同的数据元素剔除。

void MergeList(LinkList L,LinkList &P)//集合合并函数 
{
	int i = 1;
	for( ;i<=Length(L);i++)//利用循环分别导出L链表中的数据 
	{
		LNode* r;
		r = (LNode*)malloc(sizeof(LNode));//建立一个野结点 
		r -> data = GetElem(L,i);//将L链表中第i位的数据赋值给r结点 
		LNode* s = P;//建立一个s结点，将P链表的头结点赋值给s 
		while(1)
		{
			s = s->next;//利用循环遍历P链表 
			if(s->data == r->data)//如果出现野结点上的数据等于P链表上的数据，跳出循环 
				break;
			if(s->next == NULL)//如果没出现野结点上的数据等于P链表上的数据，使野结点r插入链表L尾部 
			{
				s->next = r;
				r->next = NULL;
				break;
			}
		}
	}
}

总的代码如下：

#include <stdio.h> 
#include <stdlib.h>
#include <string.h> 

typedef struct LNode
{
	int data;//结点的数据域 
	struct LNode *next;//结点的指针域 
}LNode,*LinkList;//LinkList为指向结构体LNode的指针类型 

void Interrupt(void)//创建一个中断函数 
{
	while(1) //用于检测换行符，使函数脱离scanf的连续输出 
		if(getchar()=='\n')
			break;
}

bool InitList(LinkList &L)//初始化链表  构建一个空的线性表 
{
	L = (LNode *)malloc(sizeof(LNode));
	if (L == NULL)
        return false;
    L->next = NULL;//定义头结点 
    return true;
}

bool Empty(LinkList L)//判断链表是否为空 
{
    if (L->next == NULL)//若L为空，返回true，否则返回false 
        return true;
    return false;
}

LinkList CreatList(LinkList &L)//创建链表 
{
	int a;
	LNode *s,*r=L; 
	printf("请输入链表数据：");
	while(1)
	{
		scanf("%d",&a);//输入要链表数据 
		s = (LNode *)malloc(sizeof(LNode));//创建一个结点 
		s->data = a;
		r->next = s;
		r = s; 
		if(getchar()=='\n')//死循环结束条件 
			break;
	}
	r->next = NULL;//将r设置为尾结点 
	return L;
}

void traverseLNode(LinkList L)//遍历链表，并输出链表 
{
	LNode *p=L->next;//创建一个结点并指向头结点的下一个结点 
	while(1)//建立一个死循环，链表最后一个结点指向NULL，以此为判断break循环条件 
	{
		printf("%d  ",p->data);//输出p结点中的数据 
		if(p->next==NULL)
		{
			printf("\n");
			break;
		}	
		p = p->next;//使p结点指向p的下一个结点 
	}
}

int Length(LinkList L)//求链表长度 
{
	int j=0;
	LNode *p = L;
	while(1)//建立死循环，以尾结点指向NULL为判断条件，使循环break 
	{
		p = p->next;
		j++;
		if(p->next==NULL)
			break;
	}
	return j;//返回链表长度 
}
int GetElem(LinkList L,int i)//查找第i位的值，并返回第i的值 
{
	int j;
	LNode *p = L;//创建一个结点并指向头结点 
	for(j=0;j<i;j++)//利用循环，是p结点指向第i位 
		p = p->next;
	return p->data;//返回第i的值 
}

bool JudgeSet(LinkList L)//建立一个bool类型的函数来判断输入的链表是否为集合（集合中的数不能重复） 
{
	int i,j,a,b; 
	for(i=1;i<=Length(L);i++)
	{
		a = GetElem(L,i);//用变量a接链表第i个位置， 
		for(j=i+1;j<=Length(L);j++)//利用循环让第i个位置的和i之后的位置的数分别做比较 
		{
			b = GetElem(L,j);//用变量b接链表第j个位置，
			if(a==b)//出现a等于b，说明不是集合 
			{
				printf("输入的不是数组\n");
				return false;
			}
		}
	}
	return true;
}

void MergeList(LinkList L,LinkList &P)//集合合并函数 
{
	int i = 1;
	for( ;i<=Length(L);i++)//利用循环分别导出L链表中的数据 
	{
		LNode* r;
		r = (LNode*)malloc(sizeof(LNode));//建立一个野结点 
		r -> data = GetElem(L,i);//将L链表中第i位的数据赋值给r结点 
		LNode* s = P;//建立一个s结点，将P链表的头结点赋值给s 
		while(1)
		{
			s = s->next;//利用循环遍历P链表 
			if(s->data == r->data)//如果出现野结点上的数据等于P链表上的数据，跳出循环 
				break;
			if(s->next == NULL)//如果没出现野结点上的数据等于P链表上的数据，使野结点r插入链表L尾部 
			{
				s->next = r;
				r->next = NULL;
				break;
			}
		}
	}
}

int main()
{
	LNode* L;
	InitList(L);//初始化链表L 
	CreatList(L);//创建链表L 
	LNode* P;
	InitList(P);//初始化链表P 
	CreatList(P); 
	if(JudgeSet(L) && JudgeSet(P))//判断链表L和链表P是否同时为集合 
	{
		MergeList(L,P);//合并集合L和集合P 
		traverseLNode(P);//遍历并输出P（因为合并的集合便是链表P） 
	}	
	free(L);
	free(P); 
	return 0;
}