文档介绍：实用数据结构基础
第8章查找
第 8 章查找
知识点
查找的基本概念
静态查找的基本方法:顺序查找、二分查找和分块查找
二叉排序树查找
哈希函数和解决冲突的方法
难点
二叉排序树查找
平衡树二叉树
要求
熟练掌握以下内容:
三种基本查找方法的基本思想和算法
二叉排序树查找的基本思想和算法
散列函数的常用构造方法及解决冲突方法
了解以下内容:
平衡树及平衡树的调整
第 8 章目录
8-1 查找的基本概念
8-2 静态查找表
8-3 动态查找表
8-4 哈希表
小结
实验8 查找子系统<br****题8
8-1 查找的基本概念
图8-1 学生招生录取登记表
学号
姓名
性别
入学总分
录取专业
┊
┊
┊
┊
┊
20010983
张三
女
438
计算机
20010984
李四
男
430
计算机
20010985
王五
女
445
计算机
┊
┊
┊
┊
┊
20010998
张三
男
458
计算机
┊
┊
┊
┊
┊
首先介绍几个有关查找的基本概念:
(1)查找表——由同一类型的数据元素(或记录)构成的集合称为查找表。如图8-1的学生招生录取登记表。
(2)对查找表进行的操作:
查找某个特定的数据元素是否存在;
  检索某个特定数据元素的属性;
  在查找表中插入一个数据元素;
  在查找表中删除一个数据元素。
(3)静态查找(Static Search Table)——在查找过程中仅查找某个特定元素是否存在或它的属性的,称为静态查找。
(4)动态查找(Dynamic Search Table)——在查找过程中对查找表进行插入元素或删除元素操作的,称为动态查找。
(5)关键字(Key)——数据元素(或记录)中某个数据项的值,用它可以标识数据元素(或记录)。
(6)主关键字(Primary Key)——可以唯一地标识一个记录的关键字称为主关键字。如图8-1的“学号”。
(7)次关键字(Secondary Key)——可以标识若干个记录的关键字称为次关键字。如图8-1的“姓名”,其中张三就有两位。
(8)查找(Searching)——在查找表中确定是否存在一个数据元素的关键字等于给定值的操作,称为查找(也称为检索)。若表中存在这样一个数据元素(或记录),则查找成功;否则,查找失败。
(9)内查找和外查找
若整个查找过程全部在内存进行,则称为内查找;若在查找过程中还需要访问外存,则称为外查找。本书仅介绍内查找。
(10)平均查找长度ASL
查找算法的效率,主要是看要查找的值与关键字的比较次数,通常用平均查找长度来衡量。
对一个含n个数据元素的表,查找成功时:
其中:Pi为找到表中第i个数据元素的概率,且有:
Ci为查找表中第i个数据元素所用到的比较次数。不同的查找方法有不同的Ci。
查找是许多程序中最消耗时间的一部分。因而,一个好的查找方法会大大提高运行速度。
静态查找表是数据元素的线性表,可以是基于数组的顺序存储或者以链表存储。
(1) 顺序存储结构定义
typedef struct
{ ElemType *elem; // 数组基址
int length; // 表长度
}S_TBL;
(2) 链式存储结构结点定义
typedef struct NODE
{ ElemType elem; // 结点的值域
struct NODE *next; // 下一个结点指针域
}NodeType;
8-2 静态查找表
8-2-1 顺序查找
顺序查找又称线性查找,是最基本的查找方法之一。顺序查找既适用于顺序表,也适用于链表。
从表的一端开始,顺序扫描线性表,依次按给定值kx与关键字(Key)进行比较,若相等,则查找成功,并给出数据元素在表中的位置;若整个表查找完毕,仍未找到与kx相同的关键字,则查找失败,给出失败信息。
现以顺序存储为例,数据元素从下标为1的数组单元开始存放,0号单元留作为监测哨,用来存放待找的值kx。