交集问题(线性表)

交集问题(线性表)

时间: 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; 
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注