#include<iostream>
#include<cstdlib>
using namespace std;
#define OK 1;
#define ERROR 0;
typedef int Status;
typedef int DataType;
typedef struct LNode//Linked list=链表
{
DataType data;
struct LNode *next;
}LNode,*LinkList;
Status InitLink(LinkList &L)
{
L=new(LNode);
L->next=NULL;
if(!L)
return ERROR;//生成失败
return OK;
}
Status InsertLink(LinkList &L,DataType e,int n)//在第i个元素之前插入
{//设计为有头结点
int j=0;//刚开始,p指向头结点,所以j=0
LNode *p,*s;//一个p拿来指向要插入的结点的前一个结点,s用来生成新的结点
p=L;
while(p&&j<n-1)
{
p=p->next;
j++;
}
if(!p||j>n-1)
return ERROR;
s=new(LNode);
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
void CreateLink(LinkList &L)
{
int a,i;
DataType b;
cout<<"输入这个链表的元素个数:";
cin>>a;
cout<<"输入这个链表的数据:";
for(i=1;i<=a;i++)//在第一个元素之前插入数据,插入的就是第一个元素了
{
cin>>b;
InsertLink(L,b,i);
}
}
void Print(LinkList L)
{
int i;
LNode *p;
p=L->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void Map(LinkList L1,LinkList L2,LinkList &Lc)
{
LNode *pa=L1->next,*pb=L2->next;
Lc=L1;
LNode *pc=Lc;
while(pa&&pb)
if(pa->data<pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else if(pa->data>pb->data)
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
else
{
pc->next=pa;
pc=pa;
pa=pa->next;
pb=pb->next;
}
if(pa)
pc->next=pa;
else pc->next=pb;
}
int main(void)
{
LinkList L1,L2,Lc;
if(!InitLink(L1))
{
cout<<"生成失败";
exit(1);
}
CreateLink(L1);
InitLink(L2);
CreateLink(L2);
cout<<"第一个链表为:";
Print(L1);
cout<<"第二个链表为:";
Print(L2);
cout<<"合并后为:";
Map(L1,L2,Lc);
Print(Lc);
}