单链表的合并.cpp

可以将两个无序的单链表和并成一个单链表！表的长度自己可以改！

#include <iostream.h>
#include <stdlib.h>

typedef int datatype;
struct LNode//结构定义
{datatype data;
 struct LNode *next;
};

void InitList (LNode *  HL)//初始化
{
	HL->next=NULL;
}


void TraverseList(LNode *  HL)//遍历线性表
{
    LNode *p=HL->next;
    while(p!=NULL) {
	    cout << p->data <<" ";
        p=p->next;
    }
    cout<<endl;
}


void InsertRear(LNode *  HL, datatype item)//表尾插入
{
	LNode *newptr;
    newptr=new LNode;//为保存新元素动态分配结点,newptr指向该结点
    if(newptr==NULL)//未分配到结点
    {
		cerr<<"Memory allocation failare !"<<endl;
        exit(1);
    }
    newptr->data=item;//给新结点值域赋值
    newptr->next=NULL;//给新结点指针域赋值
    
		LNode * p=HL;
        while(p->next!= NULL)//从表头遍历,p指向表尾元素
			p=p->next;
            p->next=newptr;//将新结点链接到表尾
	
}


void Mergelist(LNode *La,LNode *Lb,LNode *&Lc)//将两个有序链表并为一个有序链表,"*&Lc"为指针的引用
{ 
	LNode *Pa,*Pb,*Pc;	
    Pa=La->next;Pb=Lb->next;
	Lc=La;Pc=Lc;
	while(Pa!=NULL&&Pb!=NULL)
	{
		if(Pa->data<=Pb->data)
		{
			Pc->next=Pa;Pc=Pa;Pa=Pa->next;
		}
		else
		{
			Pc->next=Pb;Pc=Pb;Pb=Pb->next;
		}		
    }
	if(Pa!=NULL)
		Pc->next=Pa;
	else
		Pc->next =Pb;
	delete Lb;
}

void main()//主程序
{
	LNode *La,*Lb,*Lc;
	La=new LNode;
	Lb=new LNode;
	Lc=new LNode;
    InitList(La);
    InitList(Lb);
    InitList(Lc);
    int n,i,j,x,m,y;
    cout<<"输入La的元素个数";
    cin>>n;
    cout<<"输入La的元素";
    for(i=1;i<=n;i++)
       {
        cin>>x;
        InsertRear(La,x);
       }
	TraverseList(La);
    cout<<endl;
    cout<<"输入Lb的元素个数:";
    cin>>m;
    cout<<"输入Lb的元素:";
    for(j=1;j<=m;j++)
       {
        cin>>y;
        InsertRear(Lb,y);
       }
	TraverseList(Lb);
	cout<<endl;

Mergelist(La,Lb,Lc);//调用函数Mergelist

TraverseList(Lc);//遍历新的单链表
}