程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法（開篇）

一步一步寫算法（開篇）

編輯：關於C語言

算法是計算機的生命。沒有算法，就沒有軟件，計算機也就成了一個冰冷的機器，沒有什麼實用價值。很多人認為，算法是數學的內容，學起來特別麻煩。我們不能認為這種觀點是錯誤的。但是我們也知道，軟件是一種復合的技術，如果一個人只知道算法，但是不能用編程語言很好地實現，那麼再優秀的算法也不能發揮作用。一個人只有有了很好的計算機知識和數學知識，才能在算法的學習上不斷進步。不管算法都麼簡單，都要自己親手實踐，只有不斷認識錯誤、不斷發現錯誤，才能不斷提高自己的編程能力，不斷提高自己的業務水平。

這裡取名一步一步寫算法的目的主要有兩個：第一，保證我們的算法都是大家可以學得會，看的懂的；第二，保證我們的算法是健壯的、可以測試的。所以在編寫的過程中，我們的算法開發過程是伴隨著測試用例增加的，沒有測試用例保證的代碼只是一段無序的字符而已，沒有什麼價值。

其實任何算法都有自己的應用環境和應用場景，沒有算法可以適用於所有的場景。這一點希望大家明白。同時，我們也要清楚復雜的算法都是由普通的算法構成的，沒有普通的算法就沒有復雜的算法可言，所以復雜變簡單，由大化小，這就是算法分治遞歸的基本思想。

我們可以下面一個數組查找的函數說起。一句一句寫起，首先我們開始從最簡單的函數構造開始：

int find(int array[], int length, int value)
{
    int index = 0;
    return index;
}
int find(int array[], int length, int value)
{
int index = 0;
return index;
}    這裡看到，查找函數只是一個普通的函數，那麼首先需要判斷的就是參數的合法性：

static void test1()
{
    int array[10] = {0};
    assert(FALSE == find(NULL, 10, 10));
    assert(FALSE == find(array, 0, 10));
}
static void test1()
{
int array[10] = {0};
assert(FALSE == find(NULL, 10, 10));
assert(FALSE == find(array, 0, 10));
}    這裡可以看到，我們沒有判斷參數的合法性，那麼原來的查找函數應該怎麼修改呢？

int find(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    int index = 0;
    return index;
}
int find(int array[], int length, int value)
{
if(NULL == array || 0 == length)
  return FALSE;

int index = 0;
return index;
} 看到上面的代碼，說明我們的已經對入口參數進行判斷了。那麼下面就要開始寫代碼了。

int find(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    int index = 0;
    for(; index < length; index++){
        if(value == array[index])
            return index;
    }

    return FALSE;
}
int find(int array[], int length, int value)
{
if(NULL == array || 0 == length)
  return FALSE;

int index = 0;
for(; index < length; index++){
if(value == array[index])
return index;
}

return FALSE;
}
上面的代碼已經接近完整了，那麼測試用例又該怎麼編寫呢？

static void test2()
{
    int array[10] = {1, 2};
    assert(0 == find(array, 10, 1));
    assert(FALSE == find(array, 10, 10));
}
static void test2()
{
int array[10] = {1, 2};
assert(0 == find(array, 10, 1));
assert(FALSE == find(array, 10, 10));
}    運行完所有的測試用例後，我們看看對原來的代碼有沒有什麼可以優化的地方。其實，我們可以把數組轉變成指針。

int find(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    int* start = array;
    int* end = array + length;
    while(start < end){
        if(value == *start)
            return (start - array)/(sizeof(int));
        start ++;
    }

    return FALSE;
}
int find(int array[], int length, int value)
{
if(NULL == array || 0 == length)
  return FALSE;

int* start = array;
int* end = array + length;
while(start < end){
  if(value == *start)
   return (start - array)/(sizeof(int));
  start ++;
}

return FALSE;
}

如果上面的代碼參數必須是通用的數據類型呢？

template<typename type>
int find(type array[], int length, type value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    type* start = array;
    type* end = array + length;
    while(start < end){
        if(value == *start)
            return (start - array)/(sizeof(type));
        start ++;
    }

    return FALSE;
}
template<typename type>
int find(type array[], int length, type value)
{
if(NULL == array || 0 == length)
  return FALSE;

type* start = array;
type* end = array + length;
while(start < end){
  if(value == *start)
   return (start - array)/(sizeof(type));
  start ++;
}

return FALSE;
} 此時，測試用例是不是也需要重新修改呢？

static void test1()
{
    int array[10] = {0};
    assert(FALSE == find<int>(NULL, 10, 10));
    assert(FALSE == find<int>(array, 0, 10));
}

static void test2()
{
    int array[10] = {1, 2};
    assert(0 == find<int>(array, 10, 1));
    assert(FALSE == find<int>(array, 10, 10));
}
static void test1()
{
int array[10] = {0};
assert(FALSE == find<int>(NULL, 10, 10));
assert(FALSE == find<int>(array, 0, 10));
}