典型查找算法编程.ppt
《典型查找算法编程.ppt》由会员分享,可在线阅读,更多相关《典型查找算法编程.ppt(32页珍藏版)》请在三一办公上搜索。
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个座位,如果不加限定任意就坐或按某种规律就座,则要查找某学生时就要将待查找的学生与当前座位上
2、的学生进行比较。,8.1.2 问题的分析,用计算机来解决查找学生问题,通常需要做以下工作:第一,学生信息以什么形式表示和存储;第二,查找的具体实现方法(算法)。,struct student int num1;/表示座号int num2;/表示学号char name12;/表示姓名;struct listStudent stusize;/保存学生记录Int len;/学生人数;,学生信息的存储方式:,从第一个学生开始,依次与查找的学生进行比较。在查找过程中,若某个学生的记录与所查找学生记录相等,则查找成功,返回该学生在表中位置;若全部比较完毕,没有符合条件的学生记录,则查找不成功,返回-1。,
3、查找学生的方法:,8.1.3 实现算法,int search(List,8.1.4 基本概念,查找表:利用计算机查找时,首先要确定原始数据的逻辑结构和存储结构,变为计算机中处理的数据结构,这种数据结构称为存储表。查找:在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。查找成功,返回该记录的存储位置;查找失败,返回一个特定值。平均查找长度:在查找成功情况下的平均比较次数。对于含有n个记录的表,查找成功时的平均查找长度为:ASL=其中:Ci为查找第i个元素时同给 定值K进行比较的次数;Pi为查找第i个记录的概率,且 在等概率情况下,则P1=P2=Pn=,8.2 静态查
4、找,8.2.1 顺序查找 8.2.2 折半查找 8.2.3 分块查找,8.2 静态查找,查找过程中,进行如下操作:查询某个特定的数据元素是否在查找表中或检索某个数据元素的各种属性。此查找表称为静态查找表(Static Search Table)。查找表定义为顺序存储的线性表,数据类型定义如下:struct Elemtype/数据元素类型定义keytype key;/关键字项;#define maxlen maxsize/分配的存储单元个数struct ListSq Elemtype e maxsize;int len;,8.2.1 顺序查找,顺序查找(线性查找)基本思想:从线性表的一端开始,依
5、次将每个元素的关键字同给定值K进行比较,若某元素关键字与K相等,则查找成功;若所有元素都比较完毕,仍找不到关键字为K的元素,则查找失败。实现算法:(略)ASL:等概率前提下,ASL=(n+1)/2;若查找失败,需要比较n+1次,所以时间复杂为O(n)。,8.2.2 折半查找,使用折半查找(二分查找)的前提:有序表形式表示。折半查找的思想:设存在顺序有序表ListSq L,表中元素的下界为0,上界为L.len-1。先取整个有序表的中间点元素L.emid(mid=((上界+下界)/2)的关键字同给定值K进行比较。若相等,则查找成功,返回该元素的下标mid;若KL.emid.key,则说明待查元素若
6、存在只能在右子表(下标从mid+1到n1的范围)中,只要在右子表中继续二分查找即可。重复执行,直到找到关键字为K的元素或当前查找区间为空(即表明查找失败)为止。,实现算法:(略)二叉判定树:表示折半查找的查找过程。树中的每个结点表示表中一个元素,每棵子树的根结点表示当前查找区间的中间点元素,它的左子树和右子树分别对应该区间的左子表和右子表。二叉判定树是一棵二叉排序树。二分查找的平均查找长度为:,8.2.3 分块查找,分块查找(索引顺序查找)基本思想:首先把一个线性表(即主表)按照一定的函数关系或条件划分成若干个逻辑子表,为每个子表分别建立一个索引项,由所有子表的索引项构成一个索引表。当进行分块
7、查找时,先根据所给的关键字查找索引表,从中查找出给定值K刚好小于等于索引值的那个索引项,找到待查块,然后再到主表中查找该块,从中查找待查的记录。实现算法:(略)索引表是有序的,所以在索引表上既可以采用顺序查找,也可以采用折半查找,而每个块中的记录排列是任意的,所以在块内只能采用顺序查找。,平均查找长度为:设将长度为n的表均匀分成b块,每块有s个记录,则b=n/s,查找表中每条记录的概率相等,则每块查找的概率为1/b,块中每条记录的查找概率为1/s。则顺序查找索引表时:,8.3 动态查找,8.3.1 二叉排序树查找 8.3.2 二叉平衡树 动态查找表特点:表结构本身是在查找过程中动态生成的,即对



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 典型 查找 算法 编程

链接地址:https://www.31ppt.com/p-6092195.html