内存:128  时间:1

题目描述

(线性表)已知三个带头结点的线性链表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

提示

代码如下

#include <iostream>
#include <string>
using namespace std;
struct line
{
	int num;
	struct line* rear;
};
line *creat()
{
	int n;
	line *head;
	line *p;
	cin>>n;
	p=head=new line;
	while(--n)
	{
		cin>>p->num;
		p->rear=new line;
		p=p->rear;
	}
	cin>>p->num;
	p->rear=NULL;
	return head;
}
/*
line *insert(line *head)
{

}
void dele(line *head,int n)
{
	line *front;
	while(head->rear)
	{
		front=head;
		head=head->rear;
		if(head->num==n)
		{
			if(head->rear)
			{
				front->rear=head->rear;
			}
			else
			{
				front->rear=NULL;
			}
			head=front;
		}
	}
}
void deleteSame(line *head)
{
	line *p1;
	p1=head;
	int count=1;
	while(p1->rear)
	{
		dele(p1,p1->num);
		if(p1->rear==NULL)break;
		p1=p1->rear;
	}
}
void sortLine(line **head)
{
	line *p1,*p2;
	line *p1Front;
	p1=*head;
	int min;
	while(p1->rear)
	{
		line *pMin=p1;  // 3
		line *p2Front,*pMinFront;
		p2Front=p1;     // 3
		min=p1->num;   // 3
		p2=p1->rear;  //  2
		while(p2)
		{
			if(p2->num < min)
			{	//
				pMinFront=p2Front;  // 3
				pMin=p2;      //2
				min=p2->num;  //2
			}
			p2Front=p2;
			p2=p2->rear;//  1 3  2 4
		}
		if(pMin!=p1)
		{
			line *pMinNext=pMin->rear; // 4
			if(*head==p1)
			{
				*head=pMin;
				if(p1->rear!=pMin)
                {
                    pMin->rear=p1->rear;
                    pMinFront->rear=p1;
                }
                else
                {
                    pMin->rear=p1;
                }
			}
			else
			{
				p1Front->rear=pMin;
				if(pMin!=p1->rear)
				{
					pMin->rear=p1->rear;
					pMinFront->rear=p1;
				}
				else
				{
					pMin->rear=p1;
				}
			}
            p1->rear=pMinNext;
			p1=pMin;
		}
		p1Front=p1;
		p1=p1->rear;
	}
}
line *nizhi(line *head)
{
	line *pFront,*p,*pRear;
	p=pFront=pRear=head;
	p=p->rear;
	pFront->rear=NULL;
	if(p==NULL)return head;
	pRear=p->rear;
	p->rear=pFront;
	while(pRear)
	{
		pFront=p;
		p=pRear;
		pRear=p->rear;
		p->rear=pFront;
	}
	head=p;
	return head;
}
void printfLine(line *head)
{
	while(head)
	{
		cout<<head->num<<" ";
		head=head->rear;
	}
}*/
bool notNull(line *head[])
{
	for(int i=0;i<3;i++)
	{
		if(head[i]==NULL)return false;
	}
	return true;
}
int main()
{
	int i;
	bool first=true;
	line *temp;
	line *head[3];
	line *frontHead;
	for(i=0;i<3;i++)
		head[i]=creat();
	line *A=head[0];
	int last;
	while(notNull(head))
	{	
		int min;
		int same=0;
		int count_min;
		min=head[0]->num;
		count_min=0;
		for(i=1;i<3;i++)
		{
			if(head[i])
			{
				if(head[i]->num<min)
				{
					min=head[i]->num;
					count_min=i;
				}
				else if(head[i]->num==min)same++;
			}
		}
		if(same==2)   //同  全进
		{	
			if((!first)&&head[0]->num==last)
			{
				frontHead->rear=head[0]->rear; 	
				delete head[0];
				head[0]=frontHead->rear;
			}
			else 
			{
				first=false;
				last=head[0]->num;
				frontHead=head[0];
				head[0]=head[0]->rear;
			}
			for(i=1;i<3;i++)
			{
				temp=head[i];
				head[i]=head[i]->rear;
				delete temp;
			}
		}
		else      //不同   小进
		{	
			temp=head[ count_min ];
			if(count_min==0)
			{	
				if(first)
				{	
					frontHead=NULL;
					A=A->rear;
				}
				else
				{
					frontHead->rear=head[0]->rear; 
				}
			}
			head[ count_min ]=head[ count_min ]->rear;
			delete temp;
		}
	}
	while(A!=head[0])
	{
		cout<<A->num<<" ";
		A=A->rear;
	}
	return 0;
}


代码来源于互联网,仅供参考!