典型查找算法编程.ppt

《典型查找算法编程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章典型查找算法顺序查找、折半查找和分块查找的方法和算法，相应的平均查找长度二叉排序树查找方法和算法，二叉平衡树概念散列表的概念，散列函数的构造方法，处理冲突的方法及散列表各种运算的实现算法第8章典型查找算法8.1实例：学生分配座位8.2静态查找8.3动态查找8.4散列查找本章总结8.1实例：学生分配座位8.1.1问题描述8.1.2问题的分析8.1.3实现算法8.1.4基本概念8.1.1问题描述教室中的学生座位分配是一个最简单的例子。假定某教室有35个座位，如果不加限定任意就坐或按某种规律就座，则要查找某学生时就要将待查找的学生与当前座位上的学生进行比较。8.1.2问题的分析用计算机

2、来解决查找学生问题，通常需要做以下工作：第一，学生信息以什么形式表示和存储；第二，查找的具体实现方法(算法)。structstudent{intnum1;//表示座号intnum2;//表示学号charname[12];//表示姓名┆}；structlist{Studentstu[size];//保存学生记录Intlen;//学生人数};学生信息的存储方式：从第一个学生开始，依次与查找的学生进行比较。在查找过程中，若某个学生的记录与所查找学生记录相等，则查找成功，返回该学生在表中位置；若全部比较完毕，没有符合条件的学生记录，则查找不成功，返回-1。查找学生的方法：8.1.3实现算法in

3、tsearch(List&L,int,s)//从表L.stu[0],L.stu[1],……L.stu[n-1]的n个元素中查找关键字为S元素，若查找成功返回该生学号，否则返回-1{inti;for(i=0;i

4、记录的存储位置；查找失败，返回一个特定值。平均查找长度：在查找成功情况下的平均比较次数。对于含有n个记录的表，查找成功时的平均查找长度为：ASL=其中：Ci为查找第i个元素时同给定值K进行比较的次数；Pi为查找第i个记录的概率，且在等概率情况下，则P1=P2=…=Pn=8.2静态查找8.2.1顺序查找8.2.2折半查找8.2.3分块查找8.2静态查找查找过程中，进行如下操作：查询某个特定的数据元素是否在查找表中或检索某个数据元素的各种属性。此查找表称为静态查找表(StaticSearchTable)。查找表定义为顺序存储的线性表，数据类型定义如下：structElemtype//数据元

5、素类型定义{keytypekey;//关键字项┆}；#definemaxlenmaxsize//分配的存储单元个数structListSq{Elemtypee[maxsize];intlen;};8.2.1顺序查找顺序查找（线性查找）基本思想：从线性表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。实现算法：（略）ASL：等概率前提下，ASL==(n+1)/2；若查找失败，需要比较n+1次，所以时间复杂为O(n)。8.2.2折半查找使用折半查找（二分查找）的前提：有序表形式表示。折半查

6、找的思想：设存在顺序有序表ListSqL，表中元素的下界为0，上界为L.len-1。先取整个有序表的中间点元素L.e[mid](mid=（(上界+下界)/2）的关键字同给定值K进行比较。若相等，则查找成功，返回该元素的下标mid；若KL.e[mid].key，则说明待查元素若存在只能在右子表(下标从mid+1到n－1的范围)中，只要在右子表中继续二分查找即可。重复执行，直到找到关键字为K的元素或当前查找区间为空(即表明查找失败)为止。实现算法：（略）二叉判

7、定树：表示折半查找的查找过程。树中的每个结点表示表中一个元素，每棵子树的根结点表示当前查找区间的中间点元素，它的左子树和右子树分别对应该区间的左子表和右子表。二叉判定树是一棵二叉排序树。二分查找的平均查找长度为：8.2.3分块查找分块查找(索引顺序查找)基本思想：首先把一个线性表(即主表)按照一定的函数关系或条件划分成若干个逻辑子表，为每个子表分别建立一个索引项，由所有子表的索引项构成一个索引表。当进行分块查找时，先根据所给的关键字查找索引表，