上QQ阅读APP看书，第一时间看更新
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 }