#include<iostream.h>
#include<fstream.h>
#include<time.h>
#include<math.h>
//string.h
clock_t start; //定义时间变量用于计算程序执行时间
struct Node //定义结构体
{
int x; //整型数据
struct Node *next; //指向下一个结点的指针
};
Node *p,*q,*La,*Lb,*pa,*pb,*Lc,*pc;
//本程序段的目的是将单链顺序线性表La和Lb的元素合并，元素不重复，得到新的单链顺序表Lc
void main()
{
start=clock(); //开始记时
ifstream fin("input.txt",ios::in); //定义fin作为文本读入的语句
if(!fin)
cout<<"Can't open file"<<endl;
ofstream fout("output.txt",ios::out); //定义fout作为文本输出的语句
int a,b;
fin>>a>>b;
p=new Node;
La=p;
q=p;
for(int i=1;i<=a;i++) //分别输入La、Lb的元素
{
p=new Node;
fin>>p->x;
q->next=p;
p->next=NULL;
q=p;
}
p=new Node;
Lb=p;
q=p;
for( i=1;i<=b;i++)
{
p=new Node;
fin>>p->x;
q->next=p;
p->next=NULL;
q=p;
}
pa=La->next;pb=Lb->next;
Lc=pc=La; //用La的头结点作为Lc的头结点
while(pa&&pb){
if(pa->x<pb->x){
pc->next=pa;pc=pa;pa=pa->next;
}
else if(pa->x==pb->x){ //比较pa、pb对应元素的大小，把较小数传给Lc，相等时只传一个
pa=pa->next;}
else{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb;
for(pc=Lc->next;pc!=NULL;pc=pc->next) //输出Lc的元素
{
fout<<pc->x<<" ";
}
cout<<clock()-start<<endl; //记时结束，输出时间到控制台
fin.close(); //关闭输入语句
fout.close(); //关闭输出语句
}
