1.2　順序查找

猜數字游戲的策略可以轉換為不同的查找算法。首先，我們學習最簡單的順序查找算法。假設要在圖1-3所示的數組中查找數字7。

圖1-3

順序查找算法首先檢查數組中的第一個元素5，將之與待查找數字7進行比較，如圖1-4所示。如果相等，則查找結束；如果不等，則繼續向右查找。

圖1-4

5不等于7，繼續比對第二個元素，如圖1-5所示。

圖1-5

1不等于7，繼續向右查找，直到找到數字7，查找結束，如圖1-6所示。

圖1-6

假設數組nums中存儲了n個數字，變量key中存儲要查找的數字。順序查找算法從數組nums中的第一個元素開始，依次與變量key進行比較；直至找到相等的元素，循環停止。順序查找算法的偽代碼如下。

 1    for i從0到n-1
 2        if nums[i]==key
 3            查找成功，結束for循環
 4    if i==n
 5        查找失敗

順序查找算法的完整代碼如1-2-1.cpp所示。

1-2-1.cpp

 1    #include <stdio.h>
 2    #include <stdlib.h>  
 3    #include <conio.h>  
 4    #include <time.h>  
 5      
 6    int main() // 主函數  
 7    {  
 8        srand((unsigned)time(NULL)); // 初始化隨機種子  
 9        int nums[100]; // 數組存儲多個數字  
10        int i;  
11      
12        // 數組元素初始化為1到100  
13        for (i = 0; i < 100; i++)  
14            nums[i] = 1 + i;  
15      
16        // 隨機交換數組中元素的順序
17        for (i = 0; i < 50; i++)  
18        {  
19            int ri = rand() % 100; // 第1個數字的索引
20            int rj = rand() % 100; // 第2個數字的索引
21            // 交換數組中這兩個數字的順序  
22            int temp = nums[ri];  
23            nums[ri] = nums[rj];  
24            nums[rj] = temp;  
25        }  
26      
27        printf("隨機數組為：");  
28        for (i = 0; i < 100; i++)  
29            printf("%4d", nums[i]);  
30        printf("\n");  
31      
32        // 生成要查找的數字，為1到100之間的隨機整數  
33        int key = 1 + rand() % 100;  
34      
35        // 以下開始順序查找  
36        for (i = 0; i < 100; i++)  
37        {  
38            if (key != nums[i])  
39            {  
40                printf("%d：%d不是要查找的數字\n", i, nums[i]);  
41            }  
42            else  
43            {  
44                printf("%d：查找到了，%d是要查找的數字\n", i, nums[i]);  
45                break; // 終止for循環  
46            }  
47        }  
48        if (i == 100)  
49            printf("沒有找到數字%d\n", key);  
50        _getch();  
51        return 0;  
52    }  

1-2-1.cpp的運行效果如圖1-7所示。

圖1-7

為了展示順序查找算法的動態過程，可以利用Sleep()函數暫停若干毫秒，利用system("cls")清空畫面，利用SetConsoleTextAttribute()設置字符顯示不同的顏色，如代碼1-2-2.cpp所示。

1-2-2.cpp

 1    #include <stdio.h>
 2    #include <windows.h>  
 3    #include <conio.h>  
 4    int main()  
 5    {  
 6        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 8);  
 7        printf("已查找過的顯示為灰色\n");  
 8      
 9        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);  
10        printf("正在查找的顯示為紅色\n");  
11      
12        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);  
13        printf("未查找的顯示為白色\n");  
14          
15        Sleep(5000); // 暫停  
16        system("cls"); // 清空畫面  
17      
18        _getch();  
19        return 0;  
20    } 

運行代碼1-2-2.cpp后，首先輸出不同顏色的字符，如圖1-8所示，5秒后清除所顯示的內容。

圖1-8

將1-2-2.cpp和1-2-1.cpp結合，即可實現對順序查找算法的動態過程的可視化，如代碼1-2-3.cpp所示，運行效果參見圖1-9，掃描下方二維碼觀看視頻效果“1.2 順序查找”。

圖1-9

1.2 順序查找

1-2-3.cpp

 1    #include <stdio.h>
 2    #include <stdlib.h>  
 3    #include <conio.h>  
 4    #include <time.h>  
 5    #include <windows.h>  
 6      
 7    #define LEN 100  
 8      
 9    int main() // 主函數  
10    {  
11        srand((unsigned)time(NULL)); // 初始化隨機種子  
12        int nums[LEN]; // 數組存儲多個數字  
13        int i;  
14      
15        // 數組元素初始化為1到100  
16        for (i = 0; i < LEN; i++)  
17            nums[i] = 1 + i;  
18      
19        // 隨機交換數組中元素的順序
20        for (i = 0; i < 50; i++)  
21        {  
22            int ri = rand() % 100; // 第1個數字的索引
23            int rj = rand() % 100; // 第2個數字的索引
24            // 交換數組中這兩個數字的順序  
25            int temp = nums[ri];  
26            nums[ri] = nums[rj];  
27            nums[rj] = temp;  
28        }  
29      
30        // 生成要查找的數字，為1到100之間的隨機整數  
31        int key = 1 + rand() % LEN;  
32        int id = 0; // 當前查找到的數組元素的索引  
33      
34        // 以下開始順序查找  
35        for (id = 0; id < LEN; id++)  
36        {  
37            Sleep(100); // 暫停100毫秒  
38            system("cls"); // 清空畫面  
39            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 白色
40            printf("在數組中查找：%d\n", key);  
41      
42            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 8); // 灰色
43            // 已經查找過的元素顯示為灰色  
44            for (i = 0; i < id; i++)  
45                printf("%4d", nums[i]);  
46      
47            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4); // 紅色
48            // 正在被查找的元素顯示為紅色  
49            printf("%4d", nums[id]);  
50      
51            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 白色
52            // 還沒有被查找的元素顯示為白色  
53            for (i = id + 1; i < LEN; i++)  
54                printf("%4d", nums[i]);  
55            printf("\n查找次數：%d次\n", id);  
56      
57            if (key == nums[id])  
58                break; // 查找到了，跳出for循環語句  
59        }  
60        _getch();  
61        return 0;  
62    }