差集运算(线性表)

sdibt oj2625http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2625
这部分掌握的不是很好,所以那一道基础题来再分析一下。
题意即是,将A中存在且不在B中的元素筛选出来,并记录个数。题意很简单,只要将a中元素逐个在b中检查,将所求元素存入另一个链表即可。
一下是ac代码

#include”stdio.h”
#include”stdlib.h”
int n,i,x=0;//x记录个数
struct node{
int date;
struct node *next;
};
struct node *creat(struct node *head)
{
struct node *p1=NULL,*p2=NULL;
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
p1=(struct node*)malloc(sizeof(struct node));
scanf(“%d”,&p1->date);
p1->next=NULL;
if(i==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}//初始化线性表
struct node *find(struct node *head1,struct node *head2)//找出所求元素的find函数
{
struct node *head,*temp,*temp1;//另开辟head记录所求元素
int flag;
while(head1)//以A数组为基础,逐个在B中检查
{
flag=0;//默认flag=0时表示当下检查的A中的数不存在于B
temp=head2;//temp临时充当B
while(temp)//在B中遍历
{
if(temp->date==head1->date)
{
flag=1;//flag=1表示存在于B中
break;
}
else
temp=temp->next;
}
if(flag==0)//如果不在B中进行
{
if(x==0)
{
head=head1;//让head等于找出的第一个节点
head1=head1->next;//head1(数组A)后移
temp1=head;//之后用temp1操作,因为要return head
}//找出第一个独立数时要单另判断,因为存在temp1指针指向的问题
else
{
temp1->next=head1;
head1=head1->next;
temp1=temp1->next;
}与if(x==0)中大体类似,只是要用temp1记录元素
x++;//个数加1
}
else
head1=head1->next;
}
temp1->next=NULL;
return head;
}
int main(){
struct node *head1=NULL,*head2=NULL,*temp;
head1=creat(head1);
head2=creat(head2);
temp=find(head1,head2);
while(temp)
{
printf(“%d “,temp->date);
temp=temp->next;

}
printf(“\n%d\n”,x);
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation