交集问题(线性表)
时间: 1ms 内存:128M
描述:
设有两个单链表A,B,求出A,B的交集元素放到A中
输入:
1 4 5 6 7 8
1 3 6 9 10 33
输出:
1 6
示例输入:
11 14 54 6 4 83
11 3 6 9 10 83
示例输出:
11 6 83
提示:
参考答案(内存最优[748]):
#include <stdio.h>
#include <stdlib.h>
typedef struct s
{
int date;
struct s *link;
}S;
S *creat(int n)
{
S *p,*q,*head;
head=p=q=malloc(sizeof(S));
scanf("%d",&p->date);
while(--n)
{
p=malloc(sizeof(S));
scanf("%d",&p->date);
q->link=p;
q=p;
}
q->link=NULL;
return head;
}
void play(S *a,S *b)
{
S *p,*q,*r=a;
for(p=a;p!=NULL;p=p->link)
for(q=b;q!=NULL;q=q->link)
{
if((p->date)==(q->date))
{
r->date=p->date;
r=r->link;
break;
}
}
r->link=NULL;
for(r=a;r->link!=NULL;r=r->link)
printf("%d ",r->date);
}
int main()
{
S *head1,*head2;
head1=creat(6);
head2=creat(6);
play(head1,head2);
return 0;
}
参考答案(时间最优[0]):
#include<stdio.h>
#include<cstring>
#include <stdlib.h>
typedef struct s
{
int date;
struct s *link;
}S;
S *creat()
{
char str1[100],str2[80];
int len = 0,len1,a[10],b,i=0;
int n=-1;
gets(str1);
len1=strlen(str1);
while(n){
sscanf(str1+len,"%s",str2);
sscanf(str2,"%d",&n);
a[i]=n;
len+=strlen(str2);
while(str1[len]==' ')
len++;
i++;
//printf("%4d",n);
if(len>=len1)
break;
}
b=i-1;
i=0;
S *p,*q,*head;
head=p=q=(S*)malloc(sizeof(S));
p->date=a[i];
while(b--)
{ i++;
p=(S*)malloc(sizeof(S));
p->date=a[i];
q->link=p;
q=p;
}
q->link=NULL;
return head;
}
void play(S *a,S *b)
{
S *p,*q,*r=a;
for(p=a;p!=NULL;p=p->link)
for(q=b;q!=NULL;q=q->link)
{
if((p->date)==(q->date))
{
r->date=p->date;
r=r->link;
break;
}
}
r->link=NULL;
for(r=a;r->link!=NULL;r=r->link)
printf("%d ",r->date);
}
int main()
{
char s[10];
S *head1,*head2;
head1=creat();
gets(s);
head2=creat();
play(head1,head2);
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。