C語言實現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

本文實例講述了C語言實現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法，分享給大家供大家參考。具體分析如下：

題目：數(shù)組A和數(shù)組B均有序，數(shù)組A有足夠大內(nèi)存來容納數(shù)組B，將數(shù)組B有序合并到數(shù)組A中

分析：如果由前至后合并，復(fù)雜度將會是O(N2)，這樣的復(fù)雜度顯然不是最優(yōu)解，利用兩個指針指向兩個數(shù)組的尾部，從后往前遍歷，這樣的復(fù)雜度為O(n2)

由此可以寫出下面的代碼：

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int arrayA[10] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};
const int sizeB = sizeof arrayB / sizeof *arrayB;
const int sizeA = sizeof arrayA / sizeof *arrayA - sizeB;

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = 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");
 }

 return arrayA;
}

void main()
{
 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
首元素用例
const int size = 6;
int arrayA[size] = {2};
int arrayB[] = {0, 1, 1, 1, 1};
反之
const int size = 6;
int arrayA[size] = {0, 1, 1, 1, 1};
int arrayB[] = {2};

3. 正常用例：

const int size = 10;
int arrayA[size] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};

const int size = 10;
int arrayA[size] = {2, 4, 6, 8, 10};
int arrayB[] = {1, 3, 5, 7, 9};

const int size = 10;
int arrayA[size] = {1, 2, 3, 4, 5};
int arrayB[] = {6, 7, 8, 9, 10};

const int size = 10;
int arrayA[size] = {6, 7, 8, 9, 10};
int arrayB[] = {1, 2, 3, 4, 5};

經(jīng)過上面的測試，不難發(fā)現(xiàn)在邊界條件用例中，代碼已經(jīng)不能正確運行出結(jié)果，在測試用例的驅(qū)動下，不難寫出正確代碼如下：

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = 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");
 }

 //出現(xiàn)兩種情形：
 //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--;
 }
 } 
 return arrayA;
}

相信本文所述對大家C程序算法設(shè)計的學(xué)習(xí)有一定的借鑒價值。

上一篇：C++設(shè)計模式之簡單工廠模式實例

欄目：C語言

下一篇：C++實現(xiàn)尋找最低公共父節(jié)點的方法

本文標題：C語言實現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/3353.html

更多C語言

欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

C語言

C語言實現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機閱讀