C++归并算法实例
本文实例讲述了C++归并算法。分享给大家供大家参考。具体如下：
/*
归并算法：把两个或两个以上的线性表合并在一起，形成一个新的线性表
函数模版的基本使用
程序意图：将两个相同类型的线性表元素排好序，然后将他们组合成一个排好的线性表
*/
#include<iostream>
usingnamespacestd;
constintn=5;//5个元素
//输出数据元素
template<classT1>
voidOutPut(T1out[(2*n)])
{
for(inti=0;i<(2*n);i++)
{
cout<<out[i]<<"";
}
cout<<endl;
}
//输入数据元素
template<classT2>
voidInPut(T2in[n])
{
cout<<"请输入5个数据元素：";
for(inti=0;i<n;i++)
{
cin>>in[i];
cout<<"";
}
cout<<endl;
}
//模版函数输入线性表元素并将其排序
template<classT3>
voidMySort(T3a[2*n])
{
inttemp;//交换数据临时变量
//冒泡锚序
for(inti=0;i<2*n-1;i++)
{
for(intj=0;j<2*n-1-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
//模版函数归并
template<classT>
voidMergeList(TLa[n],TLb[n],TLc[(2*n)])
{
inti=0;//作为La的下标
intj=0;//Lb下标
intk=0;//Lc下标
//将LaLb组合成在一起
while(i<n&&j<n)
{
if(La[i]<Lb[j])
{
Lc[k]=La[i];
k++;
Lc[k]=Lb[j];
}
else
{
if(La[i]==Lb[j])
{
Lc[k]=La[i];
k++;
Lc[k]=Lb[j];
}
else
{
Lc[k]=Lb[j];
k++;
Lc[k]=La[i];
}
}
//各下标往下移动
i++;
j++;
k++;
}
//如果La中的数据没有取完，及La比Lb长，则将La剩下的元素插入Lc中这里是进行扩展
while(i<=n)
{
Lc[k++]=La[i++];
}
//如果Lb中的数据没有取完，及Lb比La长，则将Lb剩下的元素插入Lc中
while(j<=n)
{
Lc[k++]=Lb[j++];
}
//对组合好的元素进行排序
MySort(Lc);
}
intmain()
{
inta1[n],a2[n],a[(2*n)];
doubleb1[n],b2[n],b[(2*n)];
charm1[n],m2[n],m[(2*n)];
//输入数据归并输出
/*InPut(a1);
InPut(a2);
MergeList(a1,a2,a);
OutPut(a);*/
InPut(m1);
InPut(m2);
MergeList(m1,m2,m);
OutPut(m);
system("pause");
return0;
}
希望本文所述对大家的C++程序设计有所帮助。