求交并集
#include<iostream.h>#include<malloc.h>
#define NULL 0
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}Linklist;
void initlist(Linklist *&L)//初始化单链表
{
L=(Linklist *)malloc(sizeof(Linklist));
L->next=NULL;
}
void creatList(Linklist *&L,int a[],int n)//建立单链表
{
Linklist *r,*s;
r=L;
int i;
for(i=0;i<n;i++)
{
s=(Linklist *)malloc(sizeof(Linklist));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
void list(Linklist *L)// 输出单链表
{
Linklist *p;
p=L->next;
if(p==NULL)
cout<<"no list"<<endl;
else
{
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
cout<<endl;
}
void freeList(Linklist *&L)//释放单链表
{
Linklist *p,*q;
p=L;
while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}
}
void sort(Linklist *&L)
{
Linklist *p=L->next,*q,*r;
if(p!=NULL)
{
r=p->next;
p->next=NULL;
p=r;
}
while(p!=NULL)
{
r=p->next;
q=L;
while(q->next!=NULL&&q->next->data<p->data)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
void add(Linklist *La,Linklist *Lb,Linklist *&Lc)//求交集
{
Linklist *Pa,*Pb,*r;
r=Lc;
Pa=La->next;
Pb=Lb->next;
while(Pa)
{
if(Pa->data==Pb->data)
{
r->next=Pa;
r=Pa;
Pa=Pa->next;
Pb=Pb->next;
}
else
{
if(Pb->next==NULL)
{
Pb=Lb;
Pa=Pa->next;
}
Pb=Pb->next;
}
}
//q=Pa->next;
}
void unionset(Linklist *La,Linklist *Lb,Linklist *&Lc)//求并集；
{
Linklist *pa,*pb,*r;
pa=La->next;
pb=Lb->next;
r=Lc;
while(pa->next||pb->next)
{
if(pa->data<pb->data)
{
r->next=pa;
r=pa;
pa=pa->next;
}
else if(pa->data>pb->data)
{
r->next=pb;
r=pb;
pb=pb->next;
}
else
{
r->next=pa;
r=pa;
pa=pa->next;
pb=pb->next;
}
// cout<<r->next->data<<endl;
}
}
void main()
{
Linklist *p,*q,*r,*m;
int a[5]={1,2,5,9,8};
int b[5]={1,2,9,7,6};
initlist(p);
creatList(p,a,5);
list(p);
cout<<endl;
sort(p);
list(p);
initlist(q);
creatList(q,b,5);
list(q);
cout<<endl;
sort(q);
list(q);
// cout<<"求交集"<<endl;
// initlist(r);
//add(p,q,r);
//list(r);
cout<<"并并集："<<endl;
initlist(m);
unionset(p,q,m);
list(m);
}
#include<iostream.h>
#include<malloc.h>
#define NULL 0
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}Linklist;
void initlist(Linklist *&L)//初始化单链表
{
L=(Linklist *)malloc(sizeof(Linklist));
L->next=NULL;
}
void creatList(Linklist *&L,int a[],int n)//建立单链表
{
Linklist *r,*s;
r=L;
int i;
for(i=0;i<n;i++)
{
s=(Linklist *)malloc(sizeof(Linklist));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
void list(Linklist *L)// 输出单链表
{
Linklist *p;
p=L->next;
if(p==NULL)
cout<<"no list"<<endl;
else
{
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
cout<<endl;
}
void freeList(Linklist *&L)//释放单链表
{
Linklist *p,*q;
p=L;
while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}
}
void sort(Linklist *&L)
{
Linklist *p=L->next,*q,*r;
if(p!=NULL)
{
r=p->next;
p->next=NULL;
p=r;
}
while(p!=NULL)
{
r=p->next;
q=L;
while(q->next!=NULL&&q->next->data<p->data)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
void add(Linklist *La,Linklist *Lb,Linklist *&Lc)//求交集
{
Linklist *Pa,*Pb,*r;
r=Lc;
Pa=La->next;
Pb=Lb->next;
while(Pa)
{
if(Pa->data==Pb->data)
{
r->next=Pa;
r=Pa;
Pa=Pa->next;
Pb=Pb->next;
}
else
{
if(Pb->next==NULL)
{
Pb=Lb;
Pa=Pa->next;
}
Pb=Pb->next;
}
}
//q=Pa->next;
}
void unionset(Linklist *La,Linklist *Lb,Linklist *&Lc)//求并集；
{
Linklist *pa,*pb,*r;
pa=La->next;
pb=Lb->next;
r=Lc;
while(pa->next||pb->next)
{
if(pa->data<pb->data)
{
r->next=pa;
r=pa;
pa=pa->next;
}
else if(pa->data>pb->data)
{
r->next=pb;
r=pb;
pb=pb->next;
}
else
{
r->next=pa;
r=pa;
pa=pa->next;
pb=pb->next;
}
// cout<<r->next->data<<endl;
}
}
为什么上面和下面求出的并集不同啊 求解释！！！！！！！
void main()
{
Linklist *p,*q,*r,*m;
int a[5]={1,2,5,9,8};
int b[5]={1,2,9,7,6};
initlist(p);
creatList(p,a,5);
list(p);
cout<<endl;
sort(p);
list(p);
initlist(q);
creatList(q,b,5);
list(q);
cout<<endl;
sort(q);
list(q);
cout<<"求交集"<<endl;
initlist(r);
add(p,q,r);
list(r);
cout<<"并并集："<<endl;
initlist(m);
unionset(p,q,m);
list(m);
}
