アルゴリズム学習の配列要素検索
【要約】ここ2ヶ月はLinuxドライバを勉強していますが、途中で多くの問題が発生し、進度が遅いです.クラス科で生まれたわけではないが、アルゴリズムを学ぶ必要があると思っている.そこで配列要素を自分のアルゴリズムとして最初のブログを探して、平凡なプログラマーのブログについてよく勉強して、内容は基本的に持ってくる主義です.
次の配列で検索する関数について説明します.ひとつひとつ書き始めると、まず最も簡単な関数の構造から始めます.
ここで、検索関数は普通の関数にすぎません.まず、パラメータの合法性を判断する必要があります.
ここでは,パラメータの正当性を判断していないが,元のルックアップ関数はどのように修正すべきかを見ることができる.
上のコードを見て、私たちが入口パラメータを判断したことを説明します.では、次はコードを書き始めます.
上のコードはすでに完全に近づいていますが、テスト例はどのように作成すればいいのでしょうか.
すべてのテスト例を実行した後、元のコードに最適化できる場所があるかどうかを見てみましょう.実は、配列をポインタに変えることができます.
上のコードパラメータが共通のデータ型でなければならない場合は?
新しいテストケース
次の配列で検索する関数について説明します.ひとつひとつ書き始めると、まず最も簡単な関数の構造から始めます.
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));
}
ここでは,パラメータの正当性を判断していないが,元のルックアップ関数はどのように修正すべきかを見ることができる.
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;
}
上のコードはすでに完全に近づいていますが、テスト例はどのように作成すればいいのでしょうか.
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 ((int)start - (int)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 ((int)start - (int)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));// , 0
}
static void test2()//
{
int array[10] = {1, 2};
assert(0 == find<int>(array, 10, 1));//
assert(FALSE == find<int>(array, 10, 10));//
}