电量寄貅状学学 软件技术基础 3.7.2查找算洁（二) 主讲教师：刘民岷 ■ 航空航天学院 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
分块查找 分块查找又称索引顺序查找，这是顺序查找的一种改进方 法。 方法描述：将n个数据元素“按块有序”划分为m块(m≤n。每一块 中的结点不必有序，但块与块之间必须“按块有序”；即第1快中任 一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任 一元素又都必须小于第3块中的任一元素，.…。每个块中元素不一 定是有序的。 11 93014 3550 6555 86707867 30 65 86 电子科技大学刘民岷 查找算法 2
电子科技大学 刘民岷 查找算法 2 • 分块查找又称索引顺序查找，这是顺序查找的一种改进方 法。 • 方法描述：将n个数据元素“按块有序”划分为m块(m n)。每一块 中的结点不必有序，但块与块之间必须“按块有序”；即第1快中任 一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任 一元素又都必须小于第3块中的任一元素，……。每个块中元素不一 定是有序的。 11 9 30 14 35 50 65 55 86 70 78 67 30 65 86
4、分块查找（续） 查找过程： 一先选取各块中的最大关键字构成一个索引表； 一查找分两个步骤： >先对索引表进行二分查找或顺序查找，以确定待查记录在哪一 块中 >在已确定的块中用顺序法进行查找 119 3014 35506555867078 67 30 65 86 电子科技大学刘民岷 查找算法 3
电子科技大学 刘民岷 查找算法 3 11 9 30 14 35 50 65 55 86 70 78 67 30 65 86 • 查找过程： – 先选取各块中的最大关键字构成一个索引表； – 查找分两个步骤： ➢先对索引表进行二分查找或顺序查找，以确定待查记录在哪一 块中； ➢在已确定的块中用顺序法进行查找
树表查找 前三种查找方法各有千秋。二分法查找效率高，顺序法可 以采用链表存储结构，操作灵活。 但最好是既有二分法的高效率，又有链表灵活性的查找方法。 二叉排序树实际上就是将数据元素组织成二叉树形式，以 达到与二分法相同的查找效率，而又具有链表的插入、删 除操作的灵活性。 。1 根据二叉排序树的定义，在二叉排序树中，左子树上所有 结点的关键字都小于根结点的关键字；右子树上所有结点 的关键字都大于根结点的关键字。 电子科技大学刘民岷 查找算法 4
电子科技大学 刘民岷 查找算法 4 • 前三种查找方法各有千秋。二分法查找效率高，顺序法可 以采用链表存储结构，操作灵活。 但最好是既有二分法的高效率，又有链表灵活性的查找方法。 • 二叉排序树实际上就是将数据元素组织成二叉树形式，以 达到与二分法相同的查找效率，而又具有链表的插入、删 除操作的灵活性。 • 根据二叉排序树的定义，在二叉排序树中，左子树上所有 结点的关键字都小于根结点的关键字；右子树上所有结点 的关键字都大于根结点的关键字
树表查找（续） 5.1二叉排序树查找基本思想 当二叉排序树不空时，首先将给定值k与根结点的关键字进行 比较，若相等则查找成功； 若给定值k小于根结点的关键字，则下一次与左子树的根结点 的关键字进行比较，否则与右子树的根结点的关键字进行比较 。如此递归地进行下去直到某一次比较相等，查找成功。 5.2二叉排序树查找算法 :oooos:bsnode *bs_search(bsnode *t,keytype k) 00006:{ 00007: bsnode *s; 00008: if(t==NULL) 00009: 00010: printf("empty tree"); 00011: return(t); 00012: 00013: s=t; 00014: if((s->data).key==k) 00015: 00016: printf("searching sucess"); 00017: return(s); 00018: 00019: else if((s->data).key>k)//searching Left Tree 00020: return(bs_search(s->LC,k)); 00021: else //searching Right Tree 00022: return(bs_search(s->RC,k)); 00023:} 电子科技大学刘民岷 查找算法 5
电子科技大学 刘民岷 查找算法 5 5.1 二叉排序树查找基本思想 • 当二叉排序树不空时，首先将给定值k与根结点的关键字进行 比较，若相等则查找成功； • 若给定值k小于根结点的关键字，则下一次与左子树的根结点 的关键字进行比较，否则与右子树的根结点的关键字进行比较 。如此递归地进行下去直到某一次比较相等，查找成功。 5.2 二叉排序树查找算法