搜尋

在這一節裡，我們考慮兩種搜尋問題及它們的解決方案。 首先是在數列中尋找一個數值， 其次是比對兩個數列中是否有相同的元素。

最基本的搜尋問題就是，現在有一個序列 v[]，和一個數 x。 我們要知道，v[] 中是否有一個位置的值是 x？ 底下這個函式 search()，是針對 int 型態的資料而設計。 如果 v[] 中有一個元素是 x， 它就返回使得 v[i] == x 的最小足標 i。 如果沒有，就返回 -1 (序列的足標不可能是 -1)。

int search(int v[], unsigned int n, int x) {
int i;
for (i=0; i < n && v[i] != x; ++i) ;
return (i==n) ? -1 : i;
}

其次，若有兩個序列 u[] 和 v[]， 要檢查兩者之間是否有相同的元素。 底下這個函式 vsearch()，是針對 int 型態的資料而設計。 如果 u[] 中有一個元素是 v[] 中的元素， 它就返回使得 u[i] == v[j] 的最小足標 i。 如果沒有，就返回 -1。

int vsearch(int u[], unsigned int m, int v[], unsigned int n) {
    int i, j, found=0;
    for (i=0; i < m && !found; ++i)
        for (j=0; j < n && !found; ++j)
            if (u[i] == v[j])
                found = 1;
    return found ? i-1 : -1;
}

vsearch() 有一個明顯的困難，就是它如果找到了 u[i] == v[j] 的情況，只能返回 i 或 j，不能兩個都回來。 這是因為，C 的函式只能返回一個值。 如果要返回兩個，或更多的值，目前我們只知道，要使用序列變數。 這是因為，序列能夠達到 call by name 的效果。 以後，我們會知道，如果讓一般的變數也可以 call by name。

習題

[ 前一節 ]‧[ 後一節 ]‧[ 回目錄 ]

注意：此處所有文件均為原著，個別的版權宣告日後會一一公布， 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片，以免觸犯著作權法。

Created: May 21, 2000
Last Revised: May 21, 2000
© Copyright 2000 Wei-Chang Shann 單維彰

• Back to the home page of Wei-Chang Shann.
• Connect to the home page of Department of Mathematics, National Central University, Taiwan.