本文實例講述了C語言實現在數組A上有序合并數組B的方法，分享給大家供大家參考。具體分析如下：
題目：數組A和數組B均有序，數組A有足夠大內存來容納數組B，將數組B有序合并到數組A中
分析：如果由前至后合并，復雜度將會是O(N2)，這樣的復雜度顯然不是最優解，利用兩個指針指向兩個數組的尾部，從后往前遍歷，這樣的復雜度為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};
經過上面的測試，不難發現在邊界條件用例中，代碼已經不能正確運行出結果，在測試用例的驅動下，不難寫出正確代碼如下：
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"); } //出現兩種情形： //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程序算法設計的學習有一定的借鑒價值。
新聞熱點
疑難解答
圖片精選
