集合的合并 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; }