下载掌阅APP，畅读海量书库
立即打开
猜数字游戏的策略可以转换为不同的查找算法。首先，我们学习最简单的顺序查找算法。假设要在图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 }