第8章查找 8.1查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则 白若千个数据项组成,并假设每个记录都有一个能唯一标识该 记录的关键字。 在这种条件下查找的定义是:给定一个值k,在含有n个记 录的表中找出关键字等于k的记录。若找到查找成功,返回该 记录的信息或该记录在表中的位置;否则查找失败,返回相关 的指示信息
8.1 查找的基本概念 被查找的对象是由一组记录组成的表或文件，而每个记录则 由若干个数据项组成，并假设每个记录都有一个能唯一标识该 记录的关键字。 在这种条件下,查找的定义是：给定一个值k，在含有n个记 录的表中找出关键字等于k的记录。若找到查找成功，返回该 记录的信息或该记录在表中的位置；否则查找失败，返回相关 的指示信息。 第8章 查 找
查找有内查找和外查找之分。若整个查找过程都在内 存进行,则称之为内查找; 反之,若查找过程中需要访问外存,则称之为外查找
查找有内查找和外查找之分。若整个查找过程都在内 存进行，则称之为内查找； 反之，若查找过程中需要访问外存，则称之为外查找
采用何种查找方法? (1)使用哪种数据结构来表示“表”,即表中记录是按 何种方式组织的。 (2)表中关键字的次序。是对无序集合查找还是对有 序集台查找? 若在查找的同时对表做修改运算(如插入和删除), 则相应的表称之为动态查找表,否则称之为静态查找表
采用何种查找方法? （1）使用哪种数据结构来表示“表” ,即表中记录是按 何种方式组织的。 （2）表中关键字的次序。是对无序集合查找还是对有 序集合查找? 若在查找的同时对表做修改运算（如插入和删除）， 则相应的表称之为动态查找表，否则称之为静态查找表
由于查找运算的主要运算是关键字的比较所以通常把查找 过程中对关键字需要执行的平均比较次数(也称为平均查找长 度)作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL( Average search length)定义为: ASL=∑PC 其中,n是查找表中记录的个数。P是查找第个记录的概率, 般地,均认为每个记录的查找概率相等,即=lMm(1n) c是找到第论个记录所需进行的比较次数 平均查找长度分为成功情况下的平均查找长度和不成功 情况下的平均查找长度
由于查找运算的主要运算是关键字的比较,所以通常把查找 过程中对关键字需要执行的平均比较次数（也称为平均查找长 度）作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL（Average Search Length）定义为： = = n i i i ASL p c 1 其中，n是查找表中记录的个数。pi是查找第i个记录的概率， 一般地，均认为每个记录的查找概率相等，即pi=1/n（1≤i≤n）， ci是找到第i个记录所需进行的比较次数。 平均查找长度分为成功情况下的平均查找长度和不成功 情况下的平均查找长度
8.2性表的查找 在表的组织方式中线性表是最简单的一种。三种在线性表 上进行查找的方法: (1)顺序查找 (2)二分查找 (3)分块查找 因为不考虑在查找的同时对表做修改故上述三种查找操作 都是在静态查找表上实现的
8.2 线性表的查找 在表的组织方式中,线性表是最简单的一种。三种在线性表 上进行查找的方法： （1）顺序查找 （2） 二分查找 （3）分块查找 因为不考虑在查找的同时对表做修改,故上述三种查找操作 都是在静态查找表上实现的
定义被查找的顺序表中每个记录的类型如下: struct RecType ∥记录类型 public int key;/存放关键字,假设关鍵字为int类型 public string data;/存放其他数据,假设为 Istring类型 定义一个顺序表查找类 SqlistSearch class如下 class salistsearchClass const int MaxSize=100; 顺序表中最多元素个数 public ectype r; 顺序表 public int length; 存放顺序表的长度 public ldxTypell I; /索引表 BTNode ra /拆半查找判定树根结点 string sstr /用于返回结果 public sqlistsearchClasso/构造函数,用于查找顺序表的初始化 i rnew BTNodeo; R=new RecType MaxSize]; I=new IdxType MaxSize]; length=0 /顺序表的基本运算算法和查找算法
定义被查找的顺序表中每个记录的类型如下： struct RecType //记录类型 { public int key; //存放关键字，假设关键字为int类型 public string data; //存放其他数据，假设为string类型 }; 定义一个顺序表查找类SqListSearchClass如下 ： class SqListSearchClass { const int MaxSize=100; //顺序表中最多元素个数 public RecType[] R; //顺序表 public int length; //存放顺序表的长度 public IdxType[] I; //索引表 BTNode r; //拆半查找判定树根结点 string sstr; //用于返回结果 public SqListSearchClass() //构造函数，用于查找顺序表的初始化 { r=new BTNode(); R=new RecType[MaxSize]; I=new IdxType[MaxSize]; length=0; } //顺序表的基本运算算法和查找算法 }
82.1顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是:从表的一端开始顺序扫描顺序表 依次将扫描到的元素关键字和给定值相比较,若当前扫描 到的元素关键字与k相等,则查找成功;着扫描结束后,仍 未找到关键字等于k的元素,则查找失败
8.2.1 顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是：从表的一端开始顺序扫描顺序表， 依次将扫描到的元素关键字和给定值k相比较，若当前扫描 到的元素关键字与k相等，则查找成功；若扫描结束后，仍 未找到关键字等于k的元素，则查找失败
顺序查找的算法如下 public int SeqSearch(int k) /顺序查找算法 int i=0 while(i=length) 未找到返回0 return 0; else return i+l /找到后返回其逻辑序号计+1
顺序查找的算法如下 ： public int SeqSearch(int k) //顺序查找算法 { int i=0; while (i=length) //未找到返回0 return 0; else return i+1; //找到后返回其逻辑序号i+1 }
从顺序查找过程可以看到(不考虑越界比较n),c取 决于所查记录在表中的位置。如查找表中第1个记录R[0时, 仅需比较一次;而查找表中最后一个记录Rm-1时,需比较n 次,即c-。因此成功时的顺序查找的平均查找长度为: ASL=∑PC=-∑i=-x2(n+ n+ L n n 2 查找成功时的平均比较次数约为表长的一半。 思考题:不成功时的平均查找长度是多少?
从顺序查找过程可以看到（不考虑越界比较i<n），ci取 决于所查记录在表中的位置。如查找表中第1个记录R[0]时, 仅需比较一次；而查找表中最后一个记录R[n-1]时，需比较n 次，即ci=i。因此,成功时的顺序查找的平均查找长度为： 2 1 2 1 1 ( 1) 1 1 + = + = = = = = n n n n i i n c i p sq ASL n i n i 查找成功时的平均比较次数约为表长的一半 。 思考题：不成功时的平均查找长度是多少？
8.2,2折半查找 折半查找也称为二分查找,要求线性表中的节点必须己按 关键字值的递增或递减顺序排列。 思路:首先用要查找的关键字与中间位置的节点的关键 字相比较,这个中间节点把线性表分成了两个子表,若比较结 果相等则查找完成;若不相等,再根据k与该中间节点关键字的 比较大小确定下一步查找哪个子表,这样递归进行下去,直到 找到满足条件的节点或者该线性表中没有这样的节点
8.2.2 折半查找 折半查找也称为二分查找，要求线性表中的节点必须己按 关键字值的递增或递减顺序排列。 思路：首先用要查找的关键字k与中间位置的节点的关键 字相比较，这个中间节点把线性表分成了两个子表，若比较结 果相等则查找完成;若不相等，再根据k与该中间节点关键字的 比较大小确定下一步查找哪个子表，这样递归进行下去，直到 找到满足条件的节点或者该线性表中没有这样的节点