第4章-1 查找.ppt

* 数据结构 之 查找 * 地址冲突 上面讨论的散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址，这样，将导致后放的关键字无法存贮，我们把这种现象叫做冲突（collision）。在散列存贮中，冲突是很难避免的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。 数据结构 之 查找 * 数据结构 之 查找 * 第4章 查找与排序 * 数据结构 之 查找 * 4.1 查找 查找概述 数据项（项或字段）：项是具有独立含义的标识单位，是数据不可分割的最小单位。 组合项：由若干项、组合项构成。 数据元素（记录）：由若干项、组合项构成的数据单位，是进行数据处理的基本单位。 * 数据结构 之 查找 * 查找概述 查找：按照某种规则在记录表寻找与给定值kx相等的记录是否存在的过程称为查找。 结果： 找到---查找成功； 找不到---查找失败。 关键字(key)---能唯一确定结点的一个或多个域。 平均查找长度---查找一个结点所作的平均比较次数（衡量一个查找算法优劣的主要标准）。 * 数据结构 之 查找 * 查找概述 静态查找： 只在记录表中查询与给定值相等的记录是否存在，不进行插入与删除操作称为静态查找 。 动态查找 在记录表中查询与给定值相等的记录是否存在。并可能进行插入、删除操作。 * 数据结构 之 查找 * 查找概述 在研究各种查找算法时，必须先弄清这些方法所需要的数据结构，特别是存储结构。 查找运算的主要操作是关键字的比较，所以，通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度定义为： 其中，n是结点的个数；pi 是查找第i个结点的概率，p1=p2=...=pn=1/n；ci是找到第i个结点所需要的比较次数。 * 数据结构 之 查找 * 顺序查找(Sequential Search) 适用于顺序存储和链表存储的查找表。对无序的顺序表只能采用顺序查找方法。 顺序查找的方法： 从表的任一端开始逐个与给定值相kx比较： 若相等，则查找成功。返回值为该记录在表中的位置序号； 若超出界限，则查找失败。失败。返回值为零。 * 数据结构 之 查找 * 顺序查找(Sequential Search) 顺序查找的类型描述： typedef struct elemtype{ keytype key; datatype data}elemtype; typedef struct sstab { elemtype elem[Maxsize]; int length; } s_tab; * 数据结构 之 查找 * 顺序查找(Sequential Search) int S_SEARCH(s_tab tb1,keytype kx) { tb1.elem[0].key = kx; i = tb1.length; while (tb1.elem[i].key != kx) i--; if (i==0) return(-1); //失败 else return i;} //成功 * 数据结构 之 查找 * 顺序查找的性能分析 算法中监视哨tb1.elem[0].key的作用是为了在while循环中省去判定下标越界的条件i1，从而节省比较的时间。 顺序查找的平均查找长度为： 查找失败的比较次数是n+1。 顺序查找算法的运算量可估计为o(n)。 * 数据结构 之 查找 * 顺序查找的几点说明 有时，表中各结点的查找概率并不相等。因此若事先知道表中各结点查找概率的分布情况，则可将表中结点按查找概率从大到小排列，以便提高顺序查找的效率。 顺序查找的特点：算法简单，但查找效率低。 * 数据结构 之 查找 * 二分查找 二分查找又称为折半查找。适用于顺序存储的线性表。二分查找要求线性表是有序的。 二分查找的基本思想是：首先将待查的kx值与有序表的中间位置mid上的结点的关键字进行比较，若相等，则查找完成；否则，若给定值kx elem[mid]，则说明待查找的结点只可能在左子表中，只需在左子表中继续查找；否则在右子表中继续查找。这样，经过一次关键字的比较就缩小了一半的查找区间。如此进行下去，直到找到为止（也存在最后找不到的可能）。 * 数据结构 之 查找 * 二分查找示例 查找K=21的过程（查找成功） [05 13 19 21 37 56 64 75 80 88 92] low=1 mid=6 high=11 [05 13 19