c语言 链表 两个 链表 求 L1∩L2 和 L1∪L2 的 程序

Question

链表程序 L1∩L2 和 L1∪L2
最好是 实际可以运行的 例子
求 两个 链表中 数字 的 交集 和 并集

Answer 1

交集，并集？

========================================
晚上才有时间给你做，现在放出来了。
可以的话，最好能自己做出来。这才最有效果的。
//单链表
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
typedef struct LNode //单链基本存储结构
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

void InitList(LinkList *L)
{//初始化
if(!(*L=(LinkList)malloc(sizeof(LNode))))//分配空间
exit(EXIT_FAILURE);
(*L)->next = NULL;
}
void ListInsert(LinkList *L,int i,ElemType e)
{
//插入函数
LinkList p,newNode;
int j = 0;

p = *L;
while(p && j<i-1) //找到插入位置的前驱
{
p = p->next;
++j;
}
if(!p || j>i-1) exit(EXIT_SUCCESS); //找不到该位置则退出
if(!(newNode=(LinkList)malloc(sizeof(LNode))))
exit(EXIT_FAILURE);
newNode->data = e;
newNode->next = p->next;
p->next = newNode;
}
void CreateList(LinkList *L,int n)
{
//创建单链表函数
LinkList p,newNode;
int i;

printf("请输入元素\n");
p = *L;
for(i=0;i<n;++i)
{
if(!(newNode=(LinkList)malloc(sizeof(LNode))))
exit(EXIT_FAILURE);
scanf("%d",&newNode->data);
newNode->next = NULL;
p->next = newNode;
p = newNode;
}
}
void display(LinkList L)
{
LinkList dis;

printf("链表：");
dis = L->next;
while(dis)
{
printf("%d ",dis->data);
dis = dis->next;
}
printf("\n");
}//union并 intersection交
void unionList(LinkList La, LinkList Lb,LinkList *Lc)
{
//求La,Lb的并集，结果存在Lc
int i;
LinkList a,b,c,newNode,temp;

a = La->next;//指向第一个结点
b = Lb->next;
c = *Lc;
while(a) //先把链表La复制到LC
{
if(!(newNode=(LinkList)malloc(sizeof(LNode)))) exit(EXIT_FAILURE);
newNode->data = a->data;
newNode->next = NULL;
c->next = newNode;
c = newNode;
a = a->next;
}
while(b)//再把链表Lb复制到Lc
{
temp = (*Lc)->next;
while(temp)
{
if(b->data==temp->data)//查找原链表是否有相同元素
break;
temp = temp->next;
}
if(temp==NULL)
{//temp等于NULL说明没有相同元素,则进行以下操作
if(!(newNode=(LinkList)malloc(sizeof(LNode)))) exit(EXIT_FAILURE);
newNode->data = b->data;
newNode->next = NULL;
c->next = newNode;
c = newNode;
}
b = b->next; //本来上面几句可以做成一个方法，但因为连接第二链表的时候
//b=b->next需要放出来，所以就不做成方法了
}
}
void intersection(LinkList La, LinkList Lb,LinkList *Lc)
{
//求La,Lb的交集，结果存在Lc
LinkList a,b,c,newNode;

a = La->next;//取得第一个结点
c = *Lc;
while(a)
{
b = Lb->next;//取得第一个结点
while(b)
{
if(b->data==a->data)
{//相等则分配空间，生成新的链表
if(!(newNode=(LinkList)malloc(sizeof(LNode)))) exit(EXIT_FAILURE);
newNode->data = b->data;
newNode->next = NULL;
c->next = newNode;
c = newNode;
break;
}
b = b->next;
}
a = a->next;
}
}
int main(void)
{
LinkList L,L2,L3;

InitList(&L);//初始化
InitList(&L2);
InitList(&L3); //L3用于得到交/并集的结果
CreateList(&L,4);//创建链表，含4个元素
CreateList(&L2,4);
display(L);//显示链表
display(L2);
printf("\n");

//unionList(L,L2,&L3);
intersection(L,L2,&L3);
display(L3);
return 0;
}

示例，求交集
请输入元素
1
2
3
4
请输入元素
3
4
5
6
链表：1 2 3 4
链表：3 4 5 6

链表：3 4
请按任意键继续. . .