C語言實現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法
本文實例講述了C語言實現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法，分享給大家供大家參考。具體分析如下：
題目：數(shù)組A和數(shù)組B均有序，數(shù)組A有足夠大內(nèi)存來容納數(shù)組B，將數(shù)組B有序合并到數(shù)組A中
分析：如果由前至后合并，復雜度將會是O(N2)，這樣的復雜度顯然不是最優(yōu)解，利用兩個指針指向兩個數(shù)組的尾部，從后往前遍歷，這樣的復雜度為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程序算法設計的學習有一定的借鑒價值。
相關文章
這篇文章主要介紹了C++設計模式編程中使用Bridge橋接模式的完全攻略,Bridge將抽象部分與它的實現(xiàn)部分分離,使它們都可以獨立地變化需要的朋友可以參考下2016-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)電話簿項目管理，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
在w7 32位系統(tǒng)下把c文件匯編后，確實與mac后的差異很大?？刹粌H僅是寄存器eax與rax的區(qū)別。我想說的是函數(shù)參數(shù)傳遞的不同2013-11-11
C語言數(shù)據(jù)結(jié)構的時間復雜度和空間復雜度
算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間(內(nèi)存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度，感興趣的同學可以參考閱讀2023-04-04
這篇文章主要介紹了純C語言:折半查找源碼，有需要的朋友可以參考一下2014-01-01
C語言連接并操作Sedna XML數(shù)據(jù)庫的方法
這篇文章主要介紹了C語言連接并操作Sedna XML數(shù)據(jù)庫的方法,實例分析了C語言操作XML文件的相關技巧,需要的朋友可以參考下2015-06-06
Qt Design Studio創(chuàng)建工程的實現(xiàn)方法
Qt Design Studio它允許設計人員和開發(fā)人員使用通用的設計、開發(fā)、分析和調(diào)試工具在不同的開發(fā)平臺上共享一個項目，本文主要介紹了Qt Design Studio創(chuàng)建工程的實現(xiàn)方法，具有一定的參考價值，感興趣的可以了解一下2022-05-05
本文主要介紹了Qt實現(xiàn)部件透明及陰影效果的示例代碼，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要介紹了C++ namespace相關語法實例分析,對C++初學者有很好的參考借鑒價值,需要的朋友可以參考下2014-08-08
以下是對C/C++語言中，typedef和#define的用法以及區(qū)別進行了詳細的介紹，需要的朋友可以過來參考下2013-10-10