C语言实现在数组A上有序合并数组B的方法
本文实例讲述了C语言实现在数组A上有序合并数组B的方法，分享给大家供大家参考。具体分析如下：
题目：数组A和数组B均有序，数组A有足够大内存来容纳数组B，将数组B有序合并到数组A中
分析：如果由前至后合并，复杂度将会是O(N2)，这样的复杂度显然不是最优解，利用两个指针指向两个数组的尾部，从后往前遍历，这样的复杂度为O(n2)
由此可以写出下面的代码：
#include<iostream>
#include<algorithm>
#include<iterator>
usingnamespacestd;
intarrayA[10]={1,3,5,7,9};
intarrayB[]={2,4,6,8,10};
constintsizeB=sizeofarrayB/sizeof*arrayB;
constintsizeA=sizeofarrayA/sizeof*arrayA-sizeB;
int*mergeArray(int*arrayA,intsizeA,int*arrayB,intsizeB)
{
if(arrayA==NULL||arrayB==NULL||sizeA<0||sizeB<0)
returnNULL;
intposA=sizeA-1;
intposB=sizeB-1;
while(posA>=0&&posB>=0)
{
if(arrayA[posA]<arrayB[posB])
{
arrayA[posA+posB+1]=arrayB[posB];
posB--;
}
else
{
arrayA[posA+posB+1]=arrayA[posA];
posA--;
}
copy(arrayA,arrayA+10,ostream_iterator<int>(cout,""));
system("pause");
}
returnarrayA;
}
voidmain()
{
int*result=mergeArray(arrayA,sizeA,arrayB,sizeB);
copy(result,result+10,ostream_iterator<int>(cout,""));
cout<<endl;
}
代码写完后似乎完成了所需功能，但还不止于此，必须对上述代码做UT
1.健壮性
arrayA或arrayB为空，长度小于0
2.边界用例
arrayA为空，长度为1；arrayB不为空，长度大于1
首元素用例
constintsize=6;
intarrayA[size]={2};
intarrayB[]={0,1,1,1,1};
反之
constintsize=6;
intarrayA[size]={0,1,1,1,1};
intarrayB[]={2};
3.正常用例：
constintsize=10;
intarrayA[size]={1,3,5,7,9};
intarrayB[]={2,4,6,8,10};
constintsize=10;
intarrayA[size]={2,4,6,8,10};
intarrayB[]={1,3,5,7,9};
constintsize=10;
intarrayA[size]={1,2,3,4,5};
intarrayB[]={6,7,8,9,10};
constintsize=10;
intarrayA[size]={6,7,8,9,10};
intarrayB[]={1,2,3,4,5};
经过上面的测试，不难发现在边界条件用例中，代码已经不能正确运行出结果，在测试用例的驱动下，不难写出正确代码如下：
int*mergeArray(int*arrayA,intsizeA,int*arrayB,intsizeB)
{
if(arrayA==NULL||arrayB==NULL||sizeA<0||sizeB<0)
returnNULL;
intposA=sizeA-1;
intposB=sizeB-1;
while(posA>=0&&posB>=0)
{
if(arrayA[posA]<arrayB[posB])
{
arrayA[posA+posB+1]=arrayB[posB];
posB--;
}
else
{
arrayA[posA+posB+1]=arrayA[posA];
posA--;
}
copy(arrayA,arrayA+size,ostream_iterator<int>(cout,""));
system("pause");
}
//出现两种情形：
//1.posA<0&&posB>=0
//2.posA>=0&&posB<0
//只有第1种情形需要进行处理
if(posA<0&&posB>=0)
{
while(posB>=0)
{
arrayA[posA+posB+1]=arrayB[posB];
posB--;
}
}
returnarrayA;
}
相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。