我写这是链表的归并,归并的结果是放在A里了,你参考一下吧:
#include"LinkedList.h"
//实现两个有序链表的归并,并不占用额外的内存空间
//////////////////////////////////////////////////////////////////
//unionList()函数
归并两个有序链表,最后的结果链表以A返回
//////////////////////////////////////////////////////////////////
template<class T>
void unionList(List<T>& A,List<T>& B)
{
//判断是否为空的情况分类
if(A.IsEmpty() && B.IsEmpty())
{
cout<<"A,B两个链表都为空!"<<endl;
exit(1);
}
else if(A.IsEmpty() && !B.IsEmpty())
{
//A空,B不空
//把B中的元素全部复制到A中
T tempt;//暂存取出的结点数据
LinkNode<T>* srcptr=B.getHead()->link;
for(int i=1;i<=B.Length();i++)
{
//取出源链表中的数据
tempt=srcptr->data;
//插入到链表A中去
A.Insert(i-1,tempt);
//指针向后推进一格
srcptr=srcptr->link;
}
}
else if(!A.IsEmpty() && B.IsEmpty())
{
//A不空,B空,直接输出A的结果
return;
}
else
{
//A,B都不空
LinkNode<T>* ptrA=A.getHead()->link;
LinkNode<T>* ptrB=B.getHead()->link;
LinkNode<T>* ptr=A.getHead();
int count=0;//计数器
while(ptrB!=NULL)
{
//复位
ptrA=A.getHead()->link;
while(ptrA!=NULL)
{
//如果发现A中结点值比B中的结点值大
//则把B中当前结点插入到A中当前结点的前面
if((ptrA->link!=NULL)
&& ((ptrB->data)>=(ptrA->data))
&& ((ptrB->data)<(ptrA->link->data)))
{
//把ptrB所指向的元素插入到ptrA所指向的元素的后面
//得到ptrA指针所指向的结点的序号
ptr=A.getHead();//复位
count=0;//计数器复位
while(ptr!=ptrA)
{
count++;
ptr=ptr->link;
};
//进行插入
A.Insert(count,ptrB->data);
ptrB=ptrB->link;
break;
}
else if(ptrB->data<=A.getHead()->link->data)
{
//如果插入的位置在最A的前面
A.Insert(0,ptrB->data);
ptrB=ptrB->link;
break;
}
else if(ptrB->data>=A.Locate(A.Length())->data)
{
//如果是在尾部插入
A.Insert(A.Length(),ptrB->data);
ptrB=ptrB->link;
break;
}
else
{
//A的指针向后推进
ptrA=ptrA->link;
}
};
}
}
};
///////////////////////////////////////////////unionList()函数结束