1 / 43
文档名称:

数据结构与算法_第九章.ppt

格式:ppt   大小:968KB   页数:43页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构与算法_第九章.ppt

上传人:63229029 2017/6/7 文件大小:968 KB

下载得到文件列表

数据结构与算法_第九章.ppt

相关文档

文档介绍

文档介绍:第9章查找查找的基本概念静态查找表动态查找表哈希表主要知识点查找的基本概念查找表: 同一类型数据元素构成的集合。(集合则无相同元素) 查找:查询关键字是否在(数据元素集合)表中的过程。也称作检索。主关键字:能够惟一区分各个不同数据元素的关键字次关键字:通常不能惟一区分各个不同数据元素的关键字查找成功:在数据元素集合中找到了要查找的数据元素查找不成功:在数据元素集合中没有找到要查找的数据元素静态查找:只查找,不改变数据元素集合内的数据元素动态查找:既查找,又改变(增减)集合内的数据元素静态查找表:静态查找时构造的查找表动态查找表:动态查找时构造的查找表平均查找长度:查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为: 其中, P i是要查找数据元素出现的概率, C i是查找相应数据元素的比较次数。??? ni iiCP ASL 静态查找表静态查找表主要有三种结构: 顺序表有序顺序表索引顺序表静态查找表的顺序存储结构: typedef struct{ ElemType * elem; // 数据元素存储空间基址, 0号单元留空 int length / *表长度*/ } SSTable; typedef int KeyType; typedef char * InfoType; 定义要查找数据元素的结构体为: typedef struct{ KeyType key; / *关键字域*/ InfoType otherinfo; / *其他域*/ } ElemType; . 1 顺序表顺序查找的基本思想是: 从顺序表的一端开始,用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较,若在顺序表中查找到要查找的数据元素,则查找成功,函数返回该数据元素在顺序表中的位置;否则查找失败,函数返回 0。查找函数设计如下: int Search_Seq(SSTable ST, KeyType key) { // 算法 // 在顺序表 ST 中顺序查找其关键字等于 key 的数据元素。 // 若找到,则函数值为该元素在表中的位置,否则为 0。 int i=0; [0].key=key; // " 哨兵" for (i=; [i].key!=key; --i); // 从后往前找 return i; // 找不到时, i为0 } // Search_Seq 利用监视哨的算法。思考: 监视哨作用? 算法分析(顺序表)查找成功时的平均查找长度 ASL 成功为: ASL= ?P iC i = 1/n * (n-i+1) = (n+1)/2 ( 约表长的一半) 查找失败时的平均查找长度 ASL 失败显然为 n+1 有序表的查找有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。一、有序表的顺序查找有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同二、二分查找( 又称折半查找) 算法的基本思想: 先给数据排序(一般按升序排好),形成有序表, 然后再将 key 与正中元素相比,若 key 小,则缩小至前半部内查找;再取其中值比较,每次缩小 1/2 的范围,直到查找成功或失败为止。反之,如果 key 大,则缩小至后半部内查找。查找 21 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low (a) 查找成功示例算法示例如图 (a) , (b) 所示。查找 71 -5 13 17 2

最近更新

2025年手术室的疾病常规 18页

2025年驻马店幼儿师范高等专科学校单招职业倾.. 74页

2025年鹤壁汽车工程职业学院单招职业技能考试.. 73页

2025年顺德职业技术学院单招职业倾向性考试题.. 72页

2025年房屋租赁合同10篇 12页

县级电网自动化升级改造的建设方案分析 4页

2025年黎明职业大学单招职业倾向性考试题库附.. 72页

2025年黑龙江省七台河市单招职业适应性测试题.. 74页

2025年黔西南民族职业技术学院单招职业适应性.. 75页

2025年齐齐哈尔高等师范专科学校单招职业适应.. 73页

高中英语圈题课件《语法填空连词的用法》 15页

2025年一级注册建筑师之建筑结构考试题库【达.. 137页

2025年一级注册建筑师之建筑结构考试题库附参.. 137页

2025年公用设备工程师之专业案例(动力专业).. 36页

县乡教师选调考试《教师职业道德》题库含答案.. 46页

2025年县乡教师选调考试《教师职业道德》题库.. 49页

2025年国家电网招聘之电网计算机考试题库及参.. 159页

高中生励志思想教育 17页

2025年微地形微气象地区输电线路覆冰受损及优.. 3页

完整版安利42天纤体食谱 4页

坝顶门机安装施工组织设计 18页

菜鸟驿站员工工作合同 5页

学徒工聘用劳动协议汇编3篇 10页

2025年农村别墅可行性方案模板 31页

钢结构厂房施工合同范本 11页

员工入职健康体检表健康证明 2页

基地种植主管岗位职责(共8篇) 14页

北师大版数学四年级下册第二单元三角形分类同.. 5页

《基本要道》 187页

《GJB2650-1996 微波元器件性能测试方法》.pd.. 68页