这道题为A,B两个集合，用链表表示，有序，然后求在A中不在B中的集合。
其实，不用想过多，只要去掉A中A与B相同的部分即可实现。由于有序，则两个链表开始比较，从最小开始，一个一个比较，小的则将指针往前移一位，用来寻找两者之间相同的部分，知道两链表中一者为空。
#include<iostream>
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode;
struct LNode *creat(LNode *head)
{
struct LNode *p1,*p2;
p1=(LNode*)malloc(sizeof(LNode));
if (head==NULL) head=p1;
while(p1->data!=0)
{
p2=p1;
p1=(LNode*)malloc(sizeof(LNode));
cin>>p1->data;
p2->next=p1;
}
p2->next=NULL;
return head;
}
void print(struct LNode *head)
{
struct LNode *temp;
temp=head->next;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
void Difference(LNode *a,LNode *b)
{
LNode *p=a->next,*q=b->next;
LNode *pre=a;
LNode *r;
while(p!=NULL&&q!=NULL)
{
if(p->data<q->data)
{
pre=p;
p=p->next;
}
else if(p->data>q->data)
q=q->next;
else
{
pre->next=p->next;
r=p;
p=p->next;
free(r);
}
}
}
int main()
{
LNode *a=NULL,*b=NULL;
cout<<"请输入有序链表a(以零结束)：";
a=creat(a);
print(a);
cout<<"请输入有序链表b(以零结束)：";
b=creat(b);
print(b);
Difference(a,b);
cout<<"A与B的差集为："<<endl;
print(a);
return 0;
}
posted on 2012-08-21 18:53
yyj 阅读(294)
评论(0) 编辑 收藏 引用