05070202224.cpp

数据结构（清华版）

#include<iostream.h>
typedef int Elemtype;
//构建结构体
typedef struct LNode
{
	Elemtype data;
	LNode *next;
}*LList ;
//创建链表
void ListCreate(LList &L,int n,Elemtype a[])
{
	LList s;
	L=new LNode;L->next=NULL;
	for(int i=n-1;i>=0;i--)
	{
		s=new LNode;
		s->data=a[i];
		s->next=L->next;

		L->next=s;
	}
}

//创建函数将AB递增连接
void DZLink(LList &A,LList &B,LList &C)
{
	LList p,q,r; 
    p=A->next;q=B->next;
	r=C=A;
	while(p&&q)
	{
		if(p->data<q->data)
		{
			r->next=p;r=p;p=p->next; //将A的元素插入新表
		}
		else
		{
			r->next=q;r=q;q=q->next; //将B的元素插入新表
		}
		r->next=p?p:q;
		delete B;//删除B
	}
	
}
//创建就地逆置函数
void ListJDNZ(LList &L)
{
    LList  p, q,r;
	p=L->next;
	r=NULL;
	if(p) q=p->next;
	else q=NULL;
	while (q)
	{
		p->next=r;
		r=p;
		p=q;
		q=p->next;
	}
	p->next=r ;
	L->next=p;
}

void main ()
{
	LList A,B,C,r;
	int a[]={1,2,4};
	int b[]={1};
	ListCreate(A, 3,a);	
	ListCreate(B, 1,b);	
    DZLink( A, B, C);//调用函数连接
	ListJDNZ( C);//调用函数逆置
	cout <<"交替相连倒序得:";
	r=C->next ;
	//函数输出
	while(r)
	{
		cout<<" "<<r->data<<"  ";	
		r=r->next;
	}
}