//結點的結構定義
typedef struct lnode
{
	int data;
	struct lnode *next;
}lnode,*linklist;

//出錯信息處理函數
void errormessage(char *s)
{
	cout<<s<<endl;
}

//初始化鏈式表(逆序創建鏈式表)
void creatlist(linklist &l,int n)
{
	linklist p;
	l=NULL;
	for(int i=n;i>0;i--)
	{
		p=new lnode;
		cin>>p->data;
		p->next=l;
		l=p;
	}
	cout<<"創建的鏈式表元素是:";
	for(i=1;i<=n;i++)
	{
		cout<<p->data<<'\t';
		p=p->next;
	}
}

//遍歷鏈式表的元素
void traverselist(linklist l,int n)
{
	linklist p;
	p=l;
	for(int i=1;i<=n;i++)
	{
		cout<<p->data<<'\t';
		p=p->next;
	}
}

//求長度
int lengthlist(linklist l)
{
	linklist p;
	p=l;
	int k=0;
	while(p)
	{
		k++;
		p=p->next;
	}
	return k;
}

//取元素
int getlnode(linklist l,int i)
{
	linklist p;
	if(i<1||i>lengthlist(l))	
	{
		errormessage("輸入值非法!");
		return 0;
	}
	else{
	p=l;
	int k;
	for(k=1;k<i;k++)
	{
		p=p->next;
	}
	return p->data;
	}
}

//求前導
int prelnode(linklist l,int e)
{
	linklist p,q;
	if(lengthlist(l)==1)	return 0;
	else{
	q=p=l;
	while(p&&p->data!=e)
	{
		p=p->next;
		while(q->next!=p)	q=q->next;
	}
	return q->data;}
}

//求后繼
int postlnode(linklist l,int e)
{
	linklist p;
	p=l;
	while(p&&p->data!=e)
		p=p->next;
	p=p->next;
		return p->data;
}

//查找元素
int findlnode(linklist l,int e)
{
	linklist p;
	p=l;
	int k=0;
	while(p&&p->data!=e) 
	{
		p=p->next;
		k++;
	}
	if(k<lengthlist(l)) return k+1;
	else{
		errormessage("未找到!");}
}

//插入元素
void insertlnode(linklist &l,int i,lnode *s)
{
	linklist p;
	int j;
	if(i<1||i>lengthlist(l))	errormessage("i值非法!");
	else{
	if(i==1)
	{
		s->next=l;
		l=s;
	}//在表頭插入
	else
	{
	p=l;
	j=1;
	while(p->next&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i-1)	errormessage("Error!");
	s->next=p->next;
	p->next=s;
	}
	cout<<"插入元素后的鏈表各個元素分別是:";
	traverselist(l,lengthlist(l));
	}
	
}

//刪除元素
void deletelnode(linklist &l,int i)
{
	int e,j;
	linklist p,q;
	if(i<1||i>lengthlist(l))	errormessage("i值非法!");
	else{
	if(i==1) 
	{
		q=l;
		l=l->next;
	}
	else
	{
		p=l;j=1;
		while(p->next&&j<i-1)
		{
			p=p->next;
			++j;
		}
		q=p->next;
		p->next=q->next;
	}
	e=q->data;
	delete q;
	traverselist(l,lengthlist(l));
	}
}

//判定空表
void chargelist(linklist l)
{
	if(l=NULL)	cout<<"表為空!"<<endl;
	else cout<<"表非空"<<endl;
}

//置空鏈式表
void emptylist(linklist &l)
{
	linklist p;
	p=l;
	while(p)
	{
		p->data=0;
		p=p->next;
	}
}

//合并兩個有序鏈表
void mergelist(linklist &la,linklist &lb,linklist &lc)
{
	lnode *pa,*pb,*pc;
	pa=la;
	pb=lb;//明確合并后鏈表的頭
	if(pa->data<=pb->data)
	{
		lc=pc=la;
		pa=pa->next;
	}
	else
	{
		lc=pc=lb;
		pb=pb->next;
	}
	while(pa&&pb)
	{
		if(pa->data<=pb->data)
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else
		{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
	}
	pc->next=pa?pa:pb;
}