数据结构中的查找算法.docx

第九章 查找
教学目的要求：
通过静态查找表（顺序表,有序表,索引顺序表）；动态查找表（二叉排序树,平衡 二叉树的建立和查找；哈希表的建立，查找及分析的学习，学生应该可以在应用 中选择合适的查找方法。
教学内容和学时安排：
静态查找t linklist {
keytype key; //结点的关键字类型
anytype otherelem; //结点的其他成分
struct linklist *next; //指向链表结点的指针
}Link_Linklist,*Link; 将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。 对链表实现顺寻查找就是在有头结点的链式查找表中查找关键字值等于给定值 的记录，若查找成功，返回指向相应结点的指针，否则返回空指针。
Link_Linklist *link_search (Link h , keytype k)
{//link为带头结点链表的头指针，查找关键字值等于k的记录， //查找成功，返回指向找到的结点的指针，查找失败返回空指针 p=h->next;
while ((p!=NULL) && (p->key!=k)) p=p->next;
return p;
}
顺序查找算法简单，对表的结构无任何要求；但是执行效率较低，尤其当n较大 时，不宜采用这种查找方法。
2．折半查找
折半查找的基本思想 折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序(升序或隆 序)排列，也就是说折半查找只适用于对有序顺序表进行查找。
折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值 k 与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩 小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据 元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折 半查找；若 k 的值大于中间结点的关键字值，则可以判定查找的数据元素只有可 能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。 每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如 此重复，直到查找成功或查找范围缩小为空即查找失败为止。
折半查找过程示例
假设特弯有序「(升序)顺序表中数据元素的关键字序列为•(名氓刀血,4可処范 68^120),用折半劃湎趣歸字值为刀和刃的数据元素,
a[l]^ a亦
a[7H
述:]衣a■開4 a■卩QpR
1沖
27^
42^
W
g刃
loivt
¥
nudt
r迦id*
,尊斤叩
loivt
rnidt*
lugt
+1
k=a[,董鹹功
1™计屮
lugt
4
4
'1'
折半查找算法 假设查找表存放在数组a的a[1]~a[n]中，且升序，查找关键字值为k。 折半查找的主要步骤为：
置初始查找范围：low=l, high二n;
求查找范围中间项： mid=(low+high)/2
将指定的关键字值 k 与中间项 a[mid].key 比较