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年贵州轻工职业技术学院单招职业倾向性测.. 75页

2025年幼儿园园长述职报告4篇 18页

礼仪培训策划书(9篇) 39页

2025年郴州思科职业学院单招职业倾向性测试题.. 76页

2025年鄂尔多斯生态环境职业学院单招综合素质.. 74页

地铁安装工程中预留与预埋工作的质量控制分析.. 3页

2025年辽宁机电职业技术学院单招职业技能考试.. 74页

2025年辽宁生态工程职业学院单招职业技能考试.. 75页

2025年幼儿园体育游戏接力教案 13页

Objective-C内存泄漏检测技术研究-全面剖析 23页

2025年辽宁金融职业学院单招职业倾向性考试题.. 74页

圬工拱桥病害机理及耐久性加固技术 3页

公路安全台账 14页

2025年重庆市广安市单招职业倾向性测试题库带.. 72页

2025年重庆市资阳地区单招职业倾向性测试题库.. 73页

土地利用转型的生态系统服务价值效应分析——.. 3页

图像信息识别的智能处理方法分析 3页

2025年郑州理工职业学院单招职业适应性测试题.. 74页

2025年重庆电信职业学院单招综合素质考试题库.. 71页

国有企业集团管控体系建设问题研究 3页

2025年重庆电讯职业学院单招职业适应性测试题.. 73页

2025年年终总结通用250字 4页

2025年重庆能源职业学院单招职业倾向性测试题.. 75页

钢结构检测原始记录23张 23页

创意英语数字教案:提升学生学习兴趣 9页

人教版一年级数学下册各单元知识点 14页

2024年小学生知识竞赛问答试题及答案(共44题).. 7页

plc1200六层三部电梯控制系统的设计模板 38页

小学音乐-上海教育出版社-五年级(下册)-全册教.. 5页

事业单位财务管理培训课件(ppt 72页) 72页