2.7.1 线性表的合并
【问题描述】
已知两个集合A 和 B, 现要求一个新的集合A = AUB。 例如, 设 A = (7, .5, 3, 11) B=(2, 6, 3) 合并后 A = (7 , 5 , 3 , 11 , 2 , 6)
【问题分析】
可以利用两个线性表 LA 和 LB 分别表示集合A和 B (即线性表中的数据元素为集合中的成 员), 这样只需扩大线性表 LA, 将存在千 LB-中而不存在千 LA 中的数据元素插入到 LA 中去。 只要从 LB 中依次取得每个数据元素, 并依值在 LA 中进行查访, 若不存在, 则插入之。
【算法步骤】
1.先创建两个链表,用尾插法插入数据
2.依次遍历b链表中的数据(直到b链表中没有元素,即只剩下头结点),将b中的每一个数据都与a中的每个数据做对比,若a链表中存在b链表的当前结点,将此结点抛弃,否则将此结点连接到a链表的最后,同时脱离b链表,
3.遍历a链表
【代码】
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct LNode{ 5 int data; 6 struct LNode *next; 7 }LNode,*Linklist; 8 void CreatLinklist(Linklist s,int m){ 9 //用尾插法插入m个元素 10 int n; 11 Linklist p=s; 12 for(int i=0;i<m;i++){ 13 scanf("%d",&n);//输入添加的元素 14 Linklist u=(Linklist)malloc(sizeof(LNode));//创建新结点用于存放新元素 15 u->data=n;//为新结点的data赋值 16 u->next=NULL; 17 p->next=u;//将新结点连接到整个链表的最后 18 p=u;//将p指向最后一个结点 19 } 20 p->next=NULL;//确保最后一个结点的指针域为空 21 } 22 void Input(Linklist s){ 23 //遍历链表 24 Linklist q=s->next; 25 while(q){ 26 printf("%d ",q->data); 27 q=q->next; 28 } 29 printf("\n"); 30 } 31 int main() { 32 //初始化两个头结点 33 Linklist a=(Linklist)malloc(sizeof(LNode)); 34 a->next=NULL; 35 Linklist b=(Linklist)malloc(sizeof(LNode)); 36 b->next=NULL; 37 //创建链表 38 CreatLinklist(a,4); 39 CreatLinklist(b,3); 40 41 Linklist p=b; 42 while(p->next){//当p为最后一个结点时停止循环 43 p=p->next;//只要进入循环,说明p不是最后一个结点,则让p指向p的下一个结点 44 int flag=1;//作为标志,当p的数值不等于q时为1否则为0 45 Linklist q=a; 46 while(q->next){//遍历a链表中的数据 47 q=q->next; 48 if(q->data==p->data){ 49 flag=0; 50 break; 51 } 52 } 53 if(flag==1){//a链表中没有和p相同的数字 54 q->next=p;//此时的q必定是a链表中的最后一个结点,把p结点连接到q结点后 55 } 56 b->next=p->next;//将b链表的头指针连接到p的下一个结点上 ,此时p脱离b链表 57 if(flag==1){ 58 p->next=NULL;//p作为a链表的最后一个结点,把其下一跳指针设置为空 59 }else{ 60 free(p);//释放p所指向的结点 61 } 62 p=b;//将p指针重新指向b链表的头节点 63 } 64 65 //遍历连接后的a链表 66 Input(a); 67 }
本人技术一般,也是第一次发博客,有什么问题,欢迎各位大神们指点!
原文:https://www.cnblogs.com/bin-/p/14552048.html