您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

演算法實戰：測試驅動開發下的線性搜尋演進之路

編輯：關於C

前言

演算法是軟體的靈魂。本系列「一步一步寫演算法」核心原則：

演算法必須經測試案例驗證。
任何優化建立在測試通過之上。
測試與程式碼同步編寫。
每一步成功建立在前一步成功之上。

以線性搜尋 int find(int array[], int length, int value) 為例，示範從最小可行版本演進到泛型指標版的完整 TDD 過程。

Step 1：骨架與參數檢查

/* find_v1.c */
int find(int array[], int length, int value)
{
    if (array == NULL || length == 0) return -1;  /* FALSE 用 -1 表示 */
    return -1;  /* 暫時未實作搜尋 */
}

/* test_v1.c */
void test_null_and_zero_length(void)
{
    int arr[10] = {0};
    assert(find(NULL, 10, 10) == -1);
    assert(find(arr, 0, 10) == -1);
}

Step 2：基本線性掃描

/* find_v2.c */
int find(int array[], int length, int value)
{
    if (array == NULL || length == 0) return -1;
    for (int i = 0; i < length; ++i)
        if (array[i] == value) return i;
    return -1;
}

/* test_v2.c */
void test_basic_search(void)
{
    int arr[10] = {1, 2};
    assert(find(arr, 10, 1) == 0);
    assert(find(arr, 10, 10) == -1);
}

Step 3：指標版優化

用指標走訪避免索引運算，回傳索引時用指標差除以元素大小。

/* find_v3.c */
int find(int array[], int length, int value)
{
    if (array == NULL || length == 0) return -1;
    int *start = array;
    int *end   = array + length;
    while (start < end) {
        if (*start == value)
            return (start - array) / sizeof(int);
        ++start;
    }
    return -1;
}

Step 4：C++ 模板泛型化

支援任意可比較型別。

/* find_v4.hpp */
template 
int find(T array[], int length, T value)
{
    if (array == NULL || length == 0) return -1;
    T *start = array, *end = array + length;
    while (start < end) {
        if (*start == value) return (start - array) / sizeof(T);
        ++start;
    }
    return -1;
}

/* test_v4.cpp */
void test_template(void)
{
    double arr[10] = {1.5, 2.5};
    assert(find(arr, 10, 1.5) == 0);
    assert(find(arr, 10, 9.9) == -1);
}