最近学校在开《数据结构》这门课程，想要借此机会顺便整理一下关于查找排序等基础方面的算法流程，之后会持续更新，并且编写更加有深度的算法。
顺序查找
定义：顺序查找就是在文件的关键字集合key[1,2,…,n]中找出与给定的关键字key相等的文件记录。
步骤：1.从文件的第一个记录开始，将每个记录的关键字与给定的关键字key进行比较；
2.如果查找到某个记录的关键字等于key，则查找成功，返回该记录的地址；如果所有关键字都与key进行了比较，但都未匹配，则本次查找失败，返回失败标志；
其算法描述如下:
1 int search(keytype key[],int n,keytype key) 2 { 3 int i; 4 for(i=0;i<n;i++) 5 if(key[i]==key) //查找成功 6 return i; 7 return -1; //查找失败 8 }
在算法中，n表示记录的个数。key表示要查找的关键字。key[]为关键字顺序表，每个元素都是对应记录的关键字。例如key[0]为第0个记录的关键字。如果每条记录的信息与它的关键字都存放在一个记录中，如下定义：
1 typedef struct 2 { 3 keytype key; //key类型的关键字 4 datatype data; //记录中的其他信息 5 }RecordType;
每个记录中包含一个关键字域key和一个数据域data。这种记录的顺序查找算法可描述为：
1 int search(RecordType r[],int n,keytype key) 2 { 3 int i; 4 for(i=0;i<n;i++) 5 if(r[i].key==key) //查找成功 6 return i; 7 return -1; //查找失败 8 }
顺序查找方法的优点：简单直观，对于被查找的记录在文件中的排列顺序没有限制，较适合顺序文件的查找，这种查找思想也同时适用于对顺序表数据结构和链表数据结构中元素的查找；
顺序查找方法的缺点：平均查找长度过大，查找效率低。
【实例】
| 1004 | ZHAO | 100 |
| 1002 | QIAN | 95 |
| 1001 | SUN | 93 |
| 1003 | LI | 98 |
编写一个程序，要求输出1001编号同学的具体信息。
【分析】
首先要定义结构体类型:
1 typedef struct student 2 { 3 int num; //学生编号 4 char name[20]; //学生姓名 5 float score; //学生成绩 6 }Student;
为方便起见，这里直接初始化给结构体数组赋值。但在实际应用中，记录的获得往往都是从文件中读取的。
接下来采用顺序查找的方法找到所需编号1001学生的具体信息。这里的关键字为学生的学号，因为在学生记录中，只有学号是能唯一标识学生身份的，姓名和成绩都有可能相同故不能作为关键字。
具体代码如下：
1 #include<stdio.h> 2 typedef struct student 3 { 4 int num; //学生编号 5 char name[20]; //学生姓名 6 float score; //学生成绩 7 }Student; 8 int search(Student stu[],int n,int key) 9 { 10 int i; 11 for(i=0;i<n;i++) 12 if(stu[i].num==key) //查找成功 13 return i; 14 return -1; //查找失败 15 } 16 main() 17 { 18 Student stu[4]={ 19 {1004,"ZHAO",100}, 20 {1002,"QIAN",95}, 21 {1001,"SUN",93}, 22 {1003,"LI",98}; //初始化结构体数组 23 int addr; //要查找的记录的地址 24 addr=search(stu,4,1001); 25 printf("Student num : %d\n",stu[addr].num); //输出查找到的记录的信息 26 printf("Student name : %s\n",stu[addr].name); 27 printf("Student score : %f\n",stu[addr].score); 28 return 0; 29 }
运行结果如图所示：
谢谢大家还能看到这里【鞠躬】~