C 語言初學教材 - 第五章 線性搜尋的函數版本

陣列中搜尋元素,在登入程式用的是一個 for 迴圈

for (j = 0;j < SIZE; j++) {
    if (!strcmp(userID[j], searchname)) {
        state = Y;
        break;
    }
}


依陣列的索引,依序比對每個元素是否與搜尋目標相同,如果找到就把變數 state 設成 Y ,然後用 break 陳述跳出迴圈,迴圈變數 j 會記錄找到的索引值。


現在我們來將線性搜尋寫成函數,先思考比較簡單的例子,於整數陣列中搜尋整數,例如以下的整數陣列
int testa[10] = {3, 2, 8, 1, 9, 4, 7, 6, 5, 0};


我們自然希望函數可以找到與目標相符的元素就回傳索引值,因此設定回傳值為整數型態,參數需要陣列、陣列大小及搜尋目標,函數原型如下
int nsearch(int array[], int size, int target);


這裡用為參數的陣列 array[] 並不需要提供元素個數,因為陣列名稱等同於指標,需要中括弧 [] 說明是陣列即可,所以另外需要表示陣列大小的參數 size ,以及搜尋目標的參數 target 。實際的搜尋整數陣列的函數如下
int nsearch(int array[], int size, int target)
{
    int i;
    
    for (i = 0; i < size; i++) {
        if (target == array[i]) {
            return i;
        }
    }
    
    return -1;
}


若是找到目標,函數 nsearch() 直接回傳索引值,若是 for 迴圈走完一次都沒有找到目標,函數回傳 -1 當警示值。


如果是搜尋字元陣列,這跟搜尋整數陣列極為相似,例如打算對以下的字元陣列進行搜尋
char testb[10] = {'d', 't', '7', '#', 'c', 'q', 'n', ' ', 'o', 'v'};


函數原型如下
int csearch(char array[], int size, char target);


搜尋字元陣列的函數定義如下
int csearch(char array[], int size, char target)
{
    int i;
    
    for (i = 0; i < size; i++) {
        if (target == array[i]) {
            return i;
        }
    }
    
    return -1;
}


回到我們登入程式的例子,我們需要的是逐一比對字串的搜尋函數,假設要搜尋以下的二維字元陣列
char testc[10][10] = {"john", "mary", "tommy", "lily", "blue", "park", "tony", "sam", "bill", "bruse"};


二維字元陣列也就是字串陣列,這跟下面的指標陣列是相同的
char *testc[10] = {"john", "mary", "tommy", "lily", "blue", "park", "tony", "sam", "bill", "bruse"};


字串陣列中的 testc[0] 是指向 "john" 的第一個字元 'j' 的指標,類似的,二維字元陣列的 testc[0] 也是等同指向 "john" 的第一個字元 'j' 的指標,而 testc[0][0] 則表示 'j' 這個字元型態的元素。


利用二維字元陣列當作函數的參數,必須提供每個陣列元素的大小,也就是第二個索引值。搜尋字串陣列的函數原型宣告如下
int ssearch(char array[][10], int size, char *target);


搜尋字串陣列的函數定義如下
int ssearch(char array[][10], int size, char *target)
{
    int i;
    
    for (i = 0; i < size; i++) {
        if (!strcmp(array[i], target)) {
            return i;
        }
    }
    
    return -1;
}


注意,字串是字元陣列,只有基本資料型態及指標的變數可以直接用 == 運算子測試相等,若是這裡用
if (array[i] == target) 


這樣是比較 array[i] 與 target 的記憶體位址是否相同,而非比對兩個是否含有相同元素的字串。


完整的範例程式碼及編譯執行,請繼續參考


問題與討論
  1. 為什麼搜尋不同型態的陣列要設計成不同的函數?
  2. 為什麼沒找到目標要給搜尋函數回傳 -1 ?
  3. 為什麼比較字串的想等不能用 == 運算子?




沒有留言: