并集链表

53 阅读 0 评论 35 点赞

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

概述

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node
{
int data;
struct node *next;
}linklist;

linklist *initLinkList();///初始化链表

void creatLinkList(linklist *);///创建链表

void combineLinkList(linklist *,linklist *,linklist *);///合并两个链表

void displayLinkList(linklist *);///输出链表

int main()
{
linklist *a,*b,*c;///c为合并后的链表
printf("A链表:");
a=initLinkList();///初始化a链表

printf("nB链表:");
b=initLinkList();///初始化b链表

printf("nC链表:");
c=initLinkList();///初始化c链表

printf("nA链表插入:n");
creatLinkList(a);///向a插入数据

printf("B链表插入:n");
creatLinkList(b);///向b插入数据

printf("AB的并集:");
combineLinkList(a,b,c);///合并
displayLinkList(c);///输出合并链表

return 0;
}

///初始化链表
linklist *initLinkList()
{
linklist *L;
L=(linklist *)malloc(sizeof(linklist));

if(!L)
printf("初始化失败n");
else
printf("初始化成功n");
L->next=NULL;
return L;
}

///创建链表
void creatLinkList(linklist *L)
{
int num,data;
linklist *p,*q;
p=L;
printf("请输入需要输入的数量:");
scanf("%d",&num);
printf("请输入%d个数据:",num);
while(num--)
{
scanf("%d",&data);
q=(linklist *)malloc(sizeof(linklist));
q->data=data;
q->next=p->next;
p->next=q;
p=q;
}
return ;
}

///合并链表
void combineLinkList(linklist *a,linklist *b,linklist *c)
{
linklist *A,*B,*C;
A=a->next;B=b->next;///a,b的头结点是空的，直接指向它的next
C=c;///C指向c
while(A&&B)///有一个的next是空的直接跳出，这种情况是两个链表的长度不等
{
///A，B已经是有序的且不相同，只判断大小就可以了
if(A->data<B->data)
{
C->next=A;///C的next指向A，
C=A;///紧接C就指向A，让C一直处于最近的头结点，那样就不会倒着输出了
A=A->next;///进行下一个
}
else
{
C->next=B;///C的next指向B
C=B;///紧接C就指向B，让C一直处于最近的头结点，那样就不会倒着输出了
B=B->next;;///进行下一个
}
}
C->next=A?A:B;///这个是三目运算符，C的next会指向较长的那个剩余的部分
///因为较短的那个链表本来指向A，但A进行了next也就跳出了，自然不会指向A了，也就衔接到B剩余的部分了
}

///输出链表
void displayLinkList(linklist *L)
{
linklist *p;
p=L;
while(p->next!=NULL)
{
p=p->next;
printf("%d ",p->data);
}
printf("n");
}