典型查找算法.pptx

1
第9章典型查找算法
实例:学生分配座位
静态查找
动态查找
散列查找
本章总结
2
实例:学生分配座位
问题描述
问题的分析
实现算法
基本概念
3
问题描述
教室中的学生座位分配是一个最简单的例子。假定某教室有35个座位,如果不加限定任意就坐或按某种规律就座,则要查找某学生时就要将待查找的学生与当前座位上的学生进行比较。
4
问题的分析
用计算机来解决查找学生问题,通常需要做以下工作:
第一,学生信息以什么形式表示和存储;
第二,查找的具体实现方法(算法)。
5
struct student
{
int num1; // 表示座号
int num2; // 表示学号
char name[12]; // 表示姓名
┆
};
struct list
{
Student stu[size]; //保存学生记录
Int len; //学生人数
};
学生信息的存储方式:
6
从第一个学生开始,依次与查找的学生进行比较。在查找过程中,若某个学生的记录与所查找学生记录相等,则查找成功,返回该学生在表中位置;若全部比较完毕,没有符合条件的学生记录,则查找不成功,返回-1。
查找学生的方法:
7
实现算法
int search ( List &L , int s )
//[0],[1],……[n-1]的n个元素中查找关键字为S的元素,若查找成功返回该生学号,否则返回-1
{
int i;
for (i=0; i<; i++)
if ( [i]==s) break;
if (i<) return [i].num2;
else return -1;
}
8
基本概念
查找表:由同一类型的数据元素构成的集合。
静态查找表:只做查找操作的查找表。
动态查找表:在查找过程中做插入和删除操作的查找表。
关键字、主关键字、次关键字
查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。
9
查找运算的主要操作是关键字的比较,所以,通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。
平均查找长度定义为:
其中,n是结点的个数;pi 是查找第i个结点的概率,ci 是找到第i个结点所需要的比较次数
10
静态查找
顺序查找
折半查找
分块查找