找相同元素(线性表)

找相同元素(线性表)

时间: 1ms        内存:128M

描述:

(线性表)已知三个带头结点的线性链表ABC中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对A表进行如下操作:使操作后的链表A中仅留下三个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为Om+n+p),其中mnp分别为三个表的长度。

输入:

输入A的长度m:5

输入A:1 2 3 4 5

输入B的长度n:4

输入B: 2 3 4 5

输入C的长度p: 3

 输入C:3 4 5

输出:

输出:3 4 5

示例输入:

5
5 5 6 8 9
6
5 6 7 8 9 10
4
1 2 5 6

示例输出:

5 6 

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)

int t;
struct date
{
	int num;
	struct date *next;
};
struct date * creat(int m)
{
	struct date *head;
	struct date *p1,*p2;
	t=0;
	p1=p2=(struct date *)malloc(LEN);
	head=NULL;
	while(m--)
	{
		scanf("%d",&p1->num);
		t++;
		if(t==1)
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(struct date *)malloc(LEN);
	}
	p2->next=NULL;
	return (head);
}


void print(struct date *head)
{
	struct date *p;
	p=head;
	if(head!=NULL)
		do
		{
			printf("%d ",p->num);

			p=p->next;
		}while(p!=NULL);
	printf("\n");
}

int main()
{
	struct date *p1,*p2,*p3,*p4,*p5;
	int m,n,p;
	scanf("%d",&m);
	p1=creat(m);
	scanf("%d",&n);
	p2=creat(n);
	scanf("%d",&p);
	p3=creat(p);
	p4=p1;
	p5=p1->next;
	while(p5)
	{
		if(p4->num==p5->num)
		{
			p4->next=p5->next;
			p5=p4->next;
		}
		p4=p4->next;
		p5=p5->next;
	}
	while(p1)
	{
		while(p2)
		{
			if(p2->num==p1->num)
			{
				while(p3)
				{
					if(p3->num==p1->num)
					{
						printf("%d ",p1->num);
						break;
					}
					else
						p3=p3->next;
				}
				break;
			}
			else
				p2=p2->next;
		}
		p1=p1->next;
	}
	printf("\n");
	return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)

int t;
struct date
{
	int num;
	struct date *next;
};
struct date * creat(int m)
{
	struct date *head;
	struct date *p1,*p2;
	t=0;
	p1=p2=(struct date *)malloc(LEN);
	head=NULL;
	while(m--)
	{
		scanf("%d",&p1->num);
		t++;
		if(t==1)
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(struct date *)malloc(LEN);
	}
	p2->next=NULL;
	return (head);
}


void print(struct date *head)
{
	struct date *p;
	p=head;
	if(head!=NULL)
		do
		{
			printf("%d ",p->num);

			p=p->next;
		}while(p!=NULL);
	printf("\n");
}

int main()
{
	struct date *p1,*p2,*p3,*p4,*p5;
	int m,n,p;
	scanf("%d",&m);
	p1=creat(m);
	scanf("%d",&n);
	p2=creat(n);
	scanf("%d",&p);
	p3=creat(p);
	p4=p1;
	p5=p1->next;
	while(p5)
	{
		if(p4->num==p5->num)
		{
			p4->next=p5->next;
			p5=p4->next;
		}
		p4=p4->next;
		p5=p5->next;
	}
	while(p1)
	{
		while(p2)
		{
			if(p2->num==p1->num)
			{
				while(p3)
				{
					if(p3->num==p1->num)
					{
						printf("%d ",p1->num);
						break;
					}
					else
						p3=p3->next;
				}
				break;
			}
			else
				p2=p2->next;
		}
		p1=p1->next;
	}
	printf("\n");
	return 0;
}

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

点赞

发表评论

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