集合的合并 C语言实现

深藏阁楼爱情的钟 2022-12-12 04:42 160阅读 0赞

## 数据结构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;
    }